1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsBaseHashtable.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,418 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef nsBaseHashtable_h__
1.10 +#define nsBaseHashtable_h__
1.11 +
1.12 +#include "mozilla/MemoryReporting.h"
1.13 +#include "mozilla/Move.h"
1.14 +#include "nsTHashtable.h"
1.15 +#include "prlock.h"
1.16 +#include "nsDebug.h"
1.17 +
1.18 +template<class KeyClass,class DataType,class UserDataType>
1.19 +class nsBaseHashtable; // forward declaration
1.20 +
1.21 +/**
1.22 + * the private nsTHashtable::EntryType class used by nsBaseHashtable
1.23 + * @see nsTHashtable for the specification of this class
1.24 + * @see nsBaseHashtable for template parameters
1.25 + */
1.26 +template<class KeyClass,class DataType>
1.27 +class nsBaseHashtableET : public KeyClass
1.28 +{
1.29 +public:
1.30 + DataType mData;
1.31 + friend class nsTHashtable< nsBaseHashtableET<KeyClass,DataType> >;
1.32 +
1.33 +private:
1.34 + typedef typename KeyClass::KeyType KeyType;
1.35 + typedef typename KeyClass::KeyTypePointer KeyTypePointer;
1.36 +
1.37 + nsBaseHashtableET(KeyTypePointer aKey);
1.38 + nsBaseHashtableET(nsBaseHashtableET<KeyClass,DataType>&& toMove);
1.39 + ~nsBaseHashtableET();
1.40 +};
1.41 +
1.42 +/**
1.43 + * templated hashtable for simple data types
1.44 + * This class manages simple data types that do not need construction or
1.45 + * destruction.
1.46 + *
1.47 + * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h
1.48 + * for a complete specification.
1.49 + * @param DataType the datatype stored in the hashtable,
1.50 + * for example, uint32_t or nsCOMPtr. If UserDataType is not the same,
1.51 + * DataType must implicitly cast to UserDataType
1.52 + * @param UserDataType the user sees, for example uint32_t or nsISupports*
1.53 + */
1.54 +template<class KeyClass,class DataType,class UserDataType>
1.55 +class nsBaseHashtable :
1.56 + protected nsTHashtable< nsBaseHashtableET<KeyClass,DataType> >
1.57 +{
1.58 + typedef mozilla::fallible_t fallible_t;
1.59 +
1.60 +public:
1.61 + typedef typename KeyClass::KeyType KeyType;
1.62 + typedef nsBaseHashtableET<KeyClass,DataType> EntryType;
1.63 +
1.64 + using nsTHashtable<EntryType>::Contains;
1.65 +
1.66 + nsBaseHashtable()
1.67 + {
1.68 + }
1.69 + explicit nsBaseHashtable(uint32_t aInitSize)
1.70 + : nsTHashtable<EntryType>(aInitSize)
1.71 + {
1.72 + }
1.73 +
1.74 + /**
1.75 + * Return the number of entries in the table.
1.76 + * @return number of entries
1.77 + */
1.78 + uint32_t Count() const
1.79 + { return nsTHashtable<EntryType>::Count(); }
1.80 +
1.81 + /**
1.82 + * retrieve the value for a key.
1.83 + * @param aKey the key to retreive
1.84 + * @param pData data associated with this key will be placed at this
1.85 + * pointer. If you only need to check if the key exists, pData
1.86 + * may be null.
1.87 + * @return true if the key exists. If key does not exist, pData is not
1.88 + * modified.
1.89 + */
1.90 + bool Get(KeyType aKey, UserDataType* pData) const
1.91 + {
1.92 + EntryType* ent = this->GetEntry(aKey);
1.93 +
1.94 + if (!ent)
1.95 + return false;
1.96 +
1.97 + if (pData)
1.98 + *pData = ent->mData;
1.99 +
1.100 + return true;
1.101 + }
1.102 +
1.103 + /**
1.104 + * For pointer types, get the value, returning nullptr if the entry is not
1.105 + * present in the table.
1.106 + *
1.107 + * @param aKey the key to retrieve
1.108 + * @return The found value, or nullptr if no entry was found with the given key.
1.109 + * @note If nullptr values are stored in the table, it is not possible to
1.110 + * distinguish between a nullptr value and a missing entry.
1.111 + */
1.112 + UserDataType Get(KeyType aKey) const
1.113 + {
1.114 + EntryType* ent = this->GetEntry(aKey);
1.115 + if (!ent)
1.116 + return 0;
1.117 +
1.118 + return ent->mData;
1.119 + }
1.120 +
1.121 + /**
1.122 + * put a new value for the associated key
1.123 + * @param aKey the key to put
1.124 + * @param aData the new data
1.125 + * @return always true, unless memory allocation failed
1.126 + */
1.127 + void Put(KeyType aKey, const UserDataType& aData)
1.128 + {
1.129 + if (!Put(aKey, aData, fallible_t()))
1.130 + NS_ABORT_OOM(this->mTable.entrySize * this->mTable.entryCount);
1.131 + }
1.132 +
1.133 + bool Put(KeyType aKey, const UserDataType& aData, const fallible_t&) NS_WARN_UNUSED_RESULT
1.134 + {
1.135 + EntryType* ent = this->PutEntry(aKey);
1.136 +
1.137 + if (!ent)
1.138 + return false;
1.139 +
1.140 + ent->mData = aData;
1.141 +
1.142 + return true;
1.143 + }
1.144 +
1.145 + /**
1.146 + * remove the data for the associated key
1.147 + * @param aKey the key to remove from the hashtable
1.148 + */
1.149 + void Remove(KeyType aKey) { this->RemoveEntry(aKey); }
1.150 +
1.151 + /**
1.152 + * function type provided by the application for enumeration.
1.153 + * @param aKey the key being enumerated
1.154 + * @param aData data being enumerated
1.155 + * @parm userArg passed unchanged from Enumerate
1.156 + * @return either
1.157 + * @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink or
1.158 + * @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink
1.159 + */
1.160 + typedef PLDHashOperator
1.161 + (* EnumReadFunction)(KeyType aKey,
1.162 + UserDataType aData,
1.163 + void* userArg);
1.164 +
1.165 + /**
1.166 + * enumerate entries in the hashtable, without allowing changes
1.167 + * @param enumFunc enumeration callback
1.168 + * @param userArg passed unchanged to the EnumReadFunction
1.169 + */
1.170 + uint32_t EnumerateRead(EnumReadFunction enumFunc, void* userArg) const
1.171 + {
1.172 + NS_ASSERTION(this->mTable.entrySize,
1.173 + "nsBaseHashtable was not initialized properly.");
1.174 +
1.175 + s_EnumReadArgs enumData = { enumFunc, userArg };
1.176 + return PL_DHashTableEnumerate(const_cast<PLDHashTable*>(&this->mTable),
1.177 + s_EnumReadStub,
1.178 + &enumData);
1.179 + }
1.180 +
1.181 + /**
1.182 + * function type provided by the application for enumeration.
1.183 + * @param aKey the key being enumerated
1.184 + * @param aData Reference to data being enumerated, may be altered. e.g. for
1.185 + * nsInterfaceHashtable this is an nsCOMPtr reference...
1.186 + * @parm userArg passed unchanged from Enumerate
1.187 + * @return bitflag combination of
1.188 + * @link PLDHashOperator::PL_DHASH_REMOVE @endlink,
1.189 + * @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink, or
1.190 + * @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink
1.191 + */
1.192 + typedef PLDHashOperator
1.193 + (* EnumFunction)(KeyType aKey,
1.194 + DataType& aData,
1.195 + void* userArg);
1.196 +
1.197 + /**
1.198 + * enumerate entries in the hashtable, allowing changes. This
1.199 + * functions write-locks the hashtable.
1.200 + * @param enumFunc enumeration callback
1.201 + * @param userArg passed unchanged to the EnumFunction
1.202 + */
1.203 + uint32_t Enumerate(EnumFunction enumFunc, void* userArg)
1.204 + {
1.205 + NS_ASSERTION(this->mTable.entrySize,
1.206 + "nsBaseHashtable was not initialized properly.");
1.207 +
1.208 + s_EnumArgs enumData = { enumFunc, userArg };
1.209 + return PL_DHashTableEnumerate(&this->mTable,
1.210 + s_EnumStub,
1.211 + &enumData);
1.212 + }
1.213 +
1.214 + /**
1.215 + * reset the hashtable, removing all entries
1.216 + */
1.217 + void Clear() { nsTHashtable<EntryType>::Clear(); }
1.218 +
1.219 + /**
1.220 + * client must provide a SizeOfEntryExcludingThisFun function for
1.221 + * SizeOfExcludingThis.
1.222 + * @param aKey the key being enumerated
1.223 + * @param aData Reference to data being enumerated.
1.224 + * @param mallocSizeOf the function used to measure heap-allocated blocks
1.225 + * @param userArg passed unchanged from SizeOf{In,Ex}cludingThis
1.226 + * @return summed size of the things pointed to by the entries
1.227 + */
1.228 + typedef size_t
1.229 + (* SizeOfEntryExcludingThisFun)(KeyType aKey,
1.230 + const DataType &aData,
1.231 + mozilla::MallocSizeOf mallocSizeOf,
1.232 + void* userArg);
1.233 +
1.234 + /**
1.235 + * Measure the size of the table's entry storage and the table itself.
1.236 + * If |sizeOfEntryExcludingThis| is non-nullptr, measure the size of things
1.237 + * pointed to by entries.
1.238 + *
1.239 + * @param sizeOfEntryExcludingThis
1.240 + * the <code>SizeOfEntryExcludingThisFun</code> function to call
1.241 + * @param mallocSizeOf the function used to meeasure heap-allocated blocks
1.242 + * @param userArg a point to pass to the
1.243 + * <code>SizeOfEntryExcludingThisFun</code> function
1.244 + * @return the summed size of the entries, the table, and the table's storage
1.245 + */
1.246 + size_t SizeOfIncludingThis(SizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
1.247 + mozilla::MallocSizeOf mallocSizeOf, void *userArg = nullptr)
1.248 + {
1.249 + return mallocSizeOf(this) + this->SizeOfExcludingThis(sizeOfEntryExcludingThis,
1.250 + mallocSizeOf, userArg);
1.251 + }
1.252 +
1.253 + /**
1.254 + * Measure the size of the table's entry storage, and if
1.255 + * |sizeOfEntryExcludingThis| is non-nullptr, measure the size of things pointed
1.256 + * to by entries.
1.257 + *
1.258 + * @param sizeOfEntryExcludingThis the
1.259 + * <code>SizeOfEntryExcludingThisFun</code> function to call
1.260 + * @param mallocSizeOf the function used to measure heap-allocated blocks
1.261 + * @param userArg a pointer to pass to the
1.262 + * <code>SizeOfEntryExcludingThisFun</code> function
1.263 + * @return the summed size of all the entries
1.264 + */
1.265 + size_t SizeOfExcludingThis(SizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
1.266 + mozilla::MallocSizeOf mallocSizeOf, void *userArg = nullptr) const
1.267 + {
1.268 + if (sizeOfEntryExcludingThis) {
1.269 + s_SizeOfArgs args = { sizeOfEntryExcludingThis, userArg };
1.270 + return PL_DHashTableSizeOfExcludingThis(&this->mTable, s_SizeOfStub,
1.271 + mallocSizeOf, &args);
1.272 + }
1.273 + return PL_DHashTableSizeOfExcludingThis(&this->mTable, nullptr,
1.274 + mallocSizeOf);
1.275 + }
1.276 +
1.277 +#ifdef DEBUG
1.278 + using nsTHashtable<EntryType>::MarkImmutable;
1.279 +#endif
1.280 +
1.281 +protected:
1.282 + /**
1.283 + * used internally during EnumerateRead. Allocated on the stack.
1.284 + * @param func the enumerator passed to EnumerateRead
1.285 + * @param userArg the userArg passed to EnumerateRead
1.286 + */
1.287 + struct s_EnumReadArgs
1.288 + {
1.289 + EnumReadFunction func;
1.290 + void* userArg;
1.291 + };
1.292 +
1.293 + static PLDHashOperator s_EnumReadStub(PLDHashTable *table,
1.294 + PLDHashEntryHdr *hdr,
1.295 + uint32_t number,
1.296 + void *arg);
1.297 +
1.298 + struct s_EnumArgs
1.299 + {
1.300 + EnumFunction func;
1.301 + void* userArg;
1.302 + };
1.303 +
1.304 + static PLDHashOperator s_EnumStub(PLDHashTable *table,
1.305 + PLDHashEntryHdr *hdr,
1.306 + uint32_t number,
1.307 + void *arg);
1.308 +
1.309 + struct s_SizeOfArgs
1.310 + {
1.311 + SizeOfEntryExcludingThisFun func;
1.312 + void* userArg;
1.313 + };
1.314 +
1.315 + static size_t s_SizeOfStub(PLDHashEntryHdr *entry,
1.316 + mozilla::MallocSizeOf mallocSizeOf,
1.317 + void *arg);
1.318 +};
1.319 +
1.320 +class nsCycleCollectionTraversalCallback;
1.321 +
1.322 +struct MOZ_STACK_CLASS nsBaseHashtableCCTraversalData
1.323 +{
1.324 + nsBaseHashtableCCTraversalData(nsCycleCollectionTraversalCallback& aCallback,
1.325 + const char* aName,
1.326 + uint32_t aFlags)
1.327 + : mCallback(aCallback),
1.328 + mName(aName),
1.329 + mFlags(aFlags)
1.330 + {
1.331 + }
1.332 +
1.333 + nsCycleCollectionTraversalCallback& mCallback;
1.334 + const char* mName;
1.335 + uint32_t mFlags;
1.336 +
1.337 +};
1.338 +
1.339 +template <typename K, typename T>
1.340 +PLDHashOperator
1.341 +ImplCycleCollectionTraverse_EnumFunc(K aKey,
1.342 + T aData,
1.343 + void* aUserData)
1.344 +{
1.345 + nsBaseHashtableCCTraversalData* userData =
1.346 + static_cast<nsBaseHashtableCCTraversalData*>(aUserData);
1.347 +
1.348 + CycleCollectionNoteChild(userData->mCallback,
1.349 + aData,
1.350 + userData->mName,
1.351 + userData->mFlags);
1.352 + return PL_DHASH_NEXT;
1.353 +}
1.354 +
1.355 +//
1.356 +// nsBaseHashtableET definitions
1.357 +//
1.358 +
1.359 +template<class KeyClass,class DataType>
1.360 +nsBaseHashtableET<KeyClass,DataType>::nsBaseHashtableET(KeyTypePointer aKey) :
1.361 + KeyClass(aKey)
1.362 +{ }
1.363 +
1.364 +template<class KeyClass,class DataType>
1.365 +nsBaseHashtableET<KeyClass,DataType>::nsBaseHashtableET
1.366 + (nsBaseHashtableET<KeyClass,DataType>&& toMove) :
1.367 + KeyClass(mozilla::Move(toMove)),
1.368 + mData(mozilla::Move(toMove.mData))
1.369 +{ }
1.370 +
1.371 +template<class KeyClass,class DataType>
1.372 +nsBaseHashtableET<KeyClass,DataType>::~nsBaseHashtableET()
1.373 +{ }
1.374 +
1.375 +
1.376 +//
1.377 +// nsBaseHashtable definitions
1.378 +//
1.379 +
1.380 +template<class KeyClass,class DataType,class UserDataType>
1.381 +PLDHashOperator
1.382 +nsBaseHashtable<KeyClass,DataType,UserDataType>::s_EnumReadStub
1.383 + (PLDHashTable *table, PLDHashEntryHdr *hdr, uint32_t number, void* arg)
1.384 +{
1.385 + EntryType* ent = static_cast<EntryType*>(hdr);
1.386 + s_EnumReadArgs* eargs = (s_EnumReadArgs*) arg;
1.387 +
1.388 + PLDHashOperator res = (eargs->func)(ent->GetKey(), ent->mData, eargs->userArg);
1.389 +
1.390 + NS_ASSERTION( !(res & PL_DHASH_REMOVE ),
1.391 + "PL_DHASH_REMOVE return during const enumeration; ignoring.");
1.392 +
1.393 + if (res & PL_DHASH_STOP)
1.394 + return PL_DHASH_STOP;
1.395 +
1.396 + return PL_DHASH_NEXT;
1.397 +}
1.398 +
1.399 +template<class KeyClass,class DataType,class UserDataType>
1.400 +PLDHashOperator
1.401 +nsBaseHashtable<KeyClass,DataType,UserDataType>::s_EnumStub
1.402 + (PLDHashTable *table, PLDHashEntryHdr *hdr, uint32_t number, void* arg)
1.403 +{
1.404 + EntryType* ent = static_cast<EntryType*>(hdr);
1.405 + s_EnumArgs* eargs = (s_EnumArgs*) arg;
1.406 +
1.407 + return (eargs->func)(ent->GetKey(), ent->mData, eargs->userArg);
1.408 +}
1.409 +
1.410 +template<class KeyClass,class DataType,class UserDataType>
1.411 +size_t
1.412 +nsBaseHashtable<KeyClass,DataType,UserDataType>::s_SizeOfStub
1.413 + (PLDHashEntryHdr *hdr, mozilla::MallocSizeOf mallocSizeOf, void *arg)
1.414 +{
1.415 + EntryType* ent = static_cast<EntryType*>(hdr);
1.416 + s_SizeOfArgs* eargs = static_cast<s_SizeOfArgs*>(arg);
1.417 +
1.418 + return (eargs->func)(ent->GetKey(), ent->mData, mallocSizeOf, eargs->userArg);
1.419 +}
1.420 +
1.421 +#endif // nsBaseHashtable_h__
