1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsTHashtable.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,540 @@
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 nsTHashtable_h__
1.10 +#define nsTHashtable_h__
1.11 +
1.12 +#include "nscore.h"
1.13 +#include "pldhash.h"
1.14 +#include "nsDebug.h"
1.15 +#include "mozilla/MemoryChecking.h"
1.16 +#include "mozilla/MemoryReporting.h"
1.17 +#include "mozilla/Move.h"
1.18 +#include "mozilla/fallible.h"
1.19 +#include "mozilla/PodOperations.h"
1.20 +
1.21 +#include <new>
1.22 +
1.23 +// helper function for nsTHashtable::Clear()
1.24 +NS_COM_GLUE PLDHashOperator
1.25 +PL_DHashStubEnumRemove(PLDHashTable *table,
1.26 + PLDHashEntryHdr *entry,
1.27 + uint32_t ordinal,
1.28 + void *userArg);
1.29 +
1.30 +
1.31 +/**
1.32 + * a base class for templated hashtables.
1.33 + *
1.34 + * Clients will rarely need to use this class directly. Check the derived
1.35 + * classes first, to see if they will meet your needs.
1.36 + *
1.37 + * @param EntryType the templated entry-type class that is managed by the
1.38 + * hashtable. <code>EntryType</code> must extend the following declaration,
1.39 + * and <strong>must not declare any virtual functions or derive from classes
1.40 + * with virtual functions.</strong> Any vtable pointer would break the
1.41 + * PLDHashTable code.
1.42 + *<pre> class EntryType : public PLDHashEntryHdr
1.43 + * {
1.44 + * public: or friend nsTHashtable<EntryType>;
1.45 + * // KeyType is what we use when Get()ing or Put()ing this entry
1.46 + * // this should either be a simple datatype (uint32_t, nsISupports*) or
1.47 + * // a const reference (const nsAString&)
1.48 + * typedef something KeyType;
1.49 + * // KeyTypePointer is the pointer-version of KeyType, because pldhash.h
1.50 + * // requires keys to cast to <code>const void*</code>
1.51 + * typedef const something* KeyTypePointer;
1.52 + *
1.53 + * EntryType(KeyTypePointer aKey);
1.54 + *
1.55 + * // A copy or C++11 Move constructor must be defined, even if
1.56 + * // AllowMemMove() == true, otherwise you will cause link errors.
1.57 + * EntryType(const EntryType& aEnt); // Either this...
1.58 + * EntryType(EntryType&& aEnt); // ...or this
1.59 + *
1.60 + * // the destructor must be defined... or you will cause link errors!
1.61 + * ~EntryType();
1.62 + *
1.63 + * // KeyEquals(): does this entry match this key?
1.64 + * bool KeyEquals(KeyTypePointer aKey) const;
1.65 + *
1.66 + * // KeyToPointer(): Convert KeyType to KeyTypePointer
1.67 + * static KeyTypePointer KeyToPointer(KeyType aKey);
1.68 + *
1.69 + * // HashKey(): calculate the hash number
1.70 + * static PLDHashNumber HashKey(KeyTypePointer aKey);
1.71 + *
1.72 + * // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
1.73 + * // to use the copy constructor?
1.74 + * enum { ALLOW_MEMMOVE = true/false };
1.75 + * }</pre>
1.76 + *
1.77 + * @see nsInterfaceHashtable
1.78 + * @see nsDataHashtable
1.79 + * @see nsClassHashtable
1.80 + * @author "Benjamin Smedberg <bsmedberg@covad.net>"
1.81 + */
1.82 +
1.83 +template<class EntryType>
1.84 +class nsTHashtable
1.85 +{
1.86 + typedef mozilla::fallible_t fallible_t;
1.87 +
1.88 +public:
1.89 + // Separate constructors instead of default aInitSize parameter since
1.90 + // otherwise the default no-arg constructor isn't found.
1.91 + nsTHashtable()
1.92 + {
1.93 + Init(PL_DHASH_MIN_SIZE);
1.94 + }
1.95 + explicit nsTHashtable(uint32_t aInitSize)
1.96 + {
1.97 + Init(aInitSize);
1.98 + }
1.99 +
1.100 + /**
1.101 + * destructor, cleans up and deallocates
1.102 + */
1.103 + ~nsTHashtable();
1.104 +
1.105 + nsTHashtable(nsTHashtable<EntryType>&& aOther);
1.106 +
1.107 + /**
1.108 + * Return the generation number for the table. This increments whenever
1.109 + * the table data items are moved.
1.110 + */
1.111 + uint32_t GetGeneration() const { return mTable.generation; }
1.112 +
1.113 + /**
1.114 + * KeyType is typedef'ed for ease of use.
1.115 + */
1.116 + typedef typename EntryType::KeyType KeyType;
1.117 +
1.118 + /**
1.119 + * KeyTypePointer is typedef'ed for ease of use.
1.120 + */
1.121 + typedef typename EntryType::KeyTypePointer KeyTypePointer;
1.122 +
1.123 + /**
1.124 + * Return the number of entries in the table.
1.125 + * @return number of entries
1.126 + */
1.127 + uint32_t Count() const { return mTable.entryCount; }
1.128 +
1.129 + /**
1.130 + * Get the entry associated with a key.
1.131 + * @param aKey the key to retrieve
1.132 + * @return pointer to the entry class, if the key exists; nullptr if the
1.133 + * key doesn't exist
1.134 + */
1.135 + EntryType* GetEntry(KeyType aKey) const
1.136 + {
1.137 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.138 +
1.139 + EntryType* entry =
1.140 + reinterpret_cast<EntryType*>
1.141 + (PL_DHashTableOperate(
1.142 + const_cast<PLDHashTable*>(&mTable),
1.143 + EntryType::KeyToPointer(aKey),
1.144 + PL_DHASH_LOOKUP));
1.145 + return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nullptr;
1.146 + }
1.147 +
1.148 + /**
1.149 + * Return true if an entry for the given key exists, false otherwise.
1.150 + * @param aKey the key to retrieve
1.151 + * @return true if the key exists, false if the key doesn't exist
1.152 + */
1.153 + bool Contains(KeyType aKey) const
1.154 + {
1.155 + return !!GetEntry(aKey);
1.156 + }
1.157 +
1.158 + /**
1.159 + * Get the entry associated with a key, or create a new entry,
1.160 + * @param aKey the key to retrieve
1.161 + * @return pointer to the entry class retreived; nullptr only if memory
1.162 + can't be allocated
1.163 + */
1.164 + EntryType* PutEntry(KeyType aKey)
1.165 + {
1.166 + EntryType* e = PutEntry(aKey, fallible_t());
1.167 + if (!e)
1.168 + NS_ABORT_OOM(mTable.entrySize * mTable.entryCount);
1.169 + return e;
1.170 + }
1.171 +
1.172 + EntryType* PutEntry(KeyType aKey, const fallible_t&) NS_WARN_UNUSED_RESULT
1.173 + {
1.174 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.175 +
1.176 + return static_cast<EntryType*>
1.177 + (PL_DHashTableOperate(
1.178 + &mTable,
1.179 + EntryType::KeyToPointer(aKey),
1.180 + PL_DHASH_ADD));
1.181 + }
1.182 +
1.183 + /**
1.184 + * Remove the entry associated with a key.
1.185 + * @param aKey of the entry to remove
1.186 + */
1.187 + void RemoveEntry(KeyType aKey)
1.188 + {
1.189 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.190 +
1.191 + PL_DHashTableOperate(&mTable,
1.192 + EntryType::KeyToPointer(aKey),
1.193 + PL_DHASH_REMOVE);
1.194 + }
1.195 +
1.196 + /**
1.197 + * Remove the entry associated with a key, but don't resize the hashtable.
1.198 + * This is a low-level method, and is not recommended unless you know what
1.199 + * you're doing and you need the extra performance. This method can be used
1.200 + * during enumeration, while RemoveEntry() cannot.
1.201 + * @param aEntry the entry-pointer to remove (obtained from GetEntry or
1.202 + * the enumerator
1.203 + */
1.204 + void RawRemoveEntry(EntryType* aEntry)
1.205 + {
1.206 + PL_DHashTableRawRemove(&mTable, aEntry);
1.207 + }
1.208 +
1.209 + /**
1.210 + * client must provide an <code>Enumerator</code> function for
1.211 + * EnumerateEntries
1.212 + * @param aEntry the entry being enumerated
1.213 + * @param userArg passed unchanged from <code>EnumerateEntries</code>
1.214 + * @return combination of flags
1.215 + * @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink ,
1.216 + * @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink ,
1.217 + * @link PLDHashOperator::PL_DHASH_REMOVE PL_DHASH_REMOVE @endlink
1.218 + */
1.219 + typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
1.220 +
1.221 + /**
1.222 + * Enumerate all the entries of the function.
1.223 + * @param enumFunc the <code>Enumerator</code> function to call
1.224 + * @param userArg a pointer to pass to the
1.225 + * <code>Enumerator</code> function
1.226 + * @return the number of entries actually enumerated
1.227 + */
1.228 + uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg)
1.229 + {
1.230 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.231 +
1.232 + s_EnumArgs args = { enumFunc, userArg };
1.233 + return PL_DHashTableEnumerate(&mTable, s_EnumStub, &args);
1.234 + }
1.235 +
1.236 + /**
1.237 + * remove all entries, return hashtable to "pristine" state ;)
1.238 + */
1.239 + void Clear()
1.240 + {
1.241 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.242 +
1.243 + PL_DHashTableEnumerate(&mTable, PL_DHashStubEnumRemove, nullptr);
1.244 + }
1.245 +
1.246 + /**
1.247 + * client must provide a <code>SizeOfEntryExcludingThisFun</code> function for
1.248 + * SizeOfExcludingThis.
1.249 + * @param aEntry the entry being enumerated
1.250 + * @param mallocSizeOf the function used to measure heap-allocated blocks
1.251 + * @param arg passed unchanged from <code>SizeOf{In,Ex}cludingThis</code>
1.252 + * @return summed size of the things pointed to by the entries
1.253 + */
1.254 + typedef size_t (* SizeOfEntryExcludingThisFun)(EntryType* aEntry,
1.255 + mozilla::MallocSizeOf mallocSizeOf,
1.256 + void *arg);
1.257 +
1.258 + /**
1.259 + * Measure the size of the table's entry storage, and if
1.260 + * |sizeOfEntryExcludingThis| is non-nullptr, measure the size of things
1.261 + * pointed to by entries.
1.262 + *
1.263 + * @param sizeOfEntryExcludingThis the
1.264 + * <code>SizeOfEntryExcludingThisFun</code> function to call
1.265 + * @param mallocSizeOf the function used to measure heap-allocated blocks
1.266 + * @param userArg a pointer to pass to the
1.267 + * <code>SizeOfEntryExcludingThisFun</code> function
1.268 + * @return the summed size of all the entries
1.269 + */
1.270 + size_t SizeOfExcludingThis(SizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
1.271 + mozilla::MallocSizeOf mallocSizeOf,
1.272 + void *userArg = nullptr) const
1.273 + {
1.274 + if (sizeOfEntryExcludingThis) {
1.275 + s_SizeOfArgs args = { sizeOfEntryExcludingThis, userArg };
1.276 + return PL_DHashTableSizeOfExcludingThis(&mTable, s_SizeOfStub, mallocSizeOf, &args);
1.277 + }
1.278 + return PL_DHashTableSizeOfExcludingThis(&mTable, nullptr, mallocSizeOf);
1.279 + }
1.280 +
1.281 +#ifdef DEBUG
1.282 + /**
1.283 + * Mark the table as constant after initialization.
1.284 + *
1.285 + * This will prevent assertions when a read-only hash is accessed on multiple
1.286 + * threads without synchronization.
1.287 + */
1.288 + void MarkImmutable()
1.289 + {
1.290 + NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
1.291 +
1.292 + PL_DHashMarkTableImmutable(&mTable);
1.293 + }
1.294 +#endif
1.295 +
1.296 +protected:
1.297 + PLDHashTable mTable;
1.298 +
1.299 + static const void* s_GetKey(PLDHashTable *table,
1.300 + PLDHashEntryHdr *entry);
1.301 +
1.302 + static PLDHashNumber s_HashKey(PLDHashTable *table,
1.303 + const void *key);
1.304 +
1.305 + static bool s_MatchEntry(PLDHashTable *table,
1.306 + const PLDHashEntryHdr *entry,
1.307 + const void *key);
1.308 +
1.309 + static void s_CopyEntry(PLDHashTable *table,
1.310 + const PLDHashEntryHdr *from,
1.311 + PLDHashEntryHdr *to);
1.312 +
1.313 + static void s_ClearEntry(PLDHashTable *table,
1.314 + PLDHashEntryHdr *entry);
1.315 +
1.316 + static bool s_InitEntry(PLDHashTable *table,
1.317 + PLDHashEntryHdr *entry,
1.318 + const void *key);
1.319 +
1.320 + /**
1.321 + * passed internally during enumeration. Allocated on the stack.
1.322 + *
1.323 + * @param userFunc the Enumerator function passed to
1.324 + * EnumerateEntries by the client
1.325 + * @param userArg the userArg passed unaltered
1.326 + */
1.327 + struct s_EnumArgs
1.328 + {
1.329 + Enumerator userFunc;
1.330 + void* userArg;
1.331 + };
1.332 +
1.333 + static PLDHashOperator s_EnumStub(PLDHashTable *table,
1.334 + PLDHashEntryHdr *entry,
1.335 + uint32_t number,
1.336 + void *arg);
1.337 +
1.338 + /**
1.339 + * passed internally during sizeOf counting. Allocated on the stack.
1.340 + *
1.341 + * @param userFunc the SizeOfEntryExcludingThisFun passed to
1.342 + * SizeOf{In,Ex}cludingThis by the client
1.343 + * @param userArg the userArg passed unaltered
1.344 + */
1.345 + struct s_SizeOfArgs
1.346 + {
1.347 + SizeOfEntryExcludingThisFun userFunc;
1.348 + void* userArg;
1.349 + };
1.350 +
1.351 + static size_t s_SizeOfStub(PLDHashEntryHdr *entry,
1.352 + mozilla::MallocSizeOf mallocSizeOf,
1.353 + void *arg);
1.354 +
1.355 +private:
1.356 + // copy constructor, not implemented
1.357 + nsTHashtable(nsTHashtable<EntryType>& toCopy) MOZ_DELETE;
1.358 +
1.359 + /**
1.360 + * Initialize the table.
1.361 + * @param initSize the initial number of buckets in the hashtable
1.362 + */
1.363 + void Init(uint32_t aInitSize);
1.364 +
1.365 + // assignment operator, not implemented
1.366 + nsTHashtable<EntryType>& operator= (nsTHashtable<EntryType>& toEqual) MOZ_DELETE;
1.367 +};
1.368 +
1.369 +//
1.370 +// template definitions
1.371 +//
1.372 +
1.373 +template<class EntryType>
1.374 +nsTHashtable<EntryType>::nsTHashtable(
1.375 + nsTHashtable<EntryType>&& aOther)
1.376 + : mTable(mozilla::Move(aOther.mTable))
1.377 +{
1.378 + // aOther shouldn't touch mTable after this, because we've stolen the table's
1.379 + // pointers but not overwitten them.
1.380 + MOZ_MAKE_MEM_UNDEFINED(&aOther.mTable, sizeof(aOther.mTable));
1.381 +
1.382 + // Indicate that aOther is not initialized. This will make its destructor a
1.383 + // nop, which is what we want.
1.384 + aOther.mTable.entrySize = 0;
1.385 +}
1.386 +
1.387 +template<class EntryType>
1.388 +nsTHashtable<EntryType>::~nsTHashtable()
1.389 +{
1.390 + if (mTable.entrySize)
1.391 + PL_DHashTableFinish(&mTable);
1.392 +}
1.393 +
1.394 +template<class EntryType>
1.395 +void
1.396 +nsTHashtable<EntryType>::Init(uint32_t aInitSize)
1.397 +{
1.398 + static const PLDHashTableOps sOps =
1.399 + {
1.400 + ::PL_DHashAllocTable,
1.401 + ::PL_DHashFreeTable,
1.402 + s_HashKey,
1.403 + s_MatchEntry,
1.404 + EntryType::ALLOW_MEMMOVE ? ::PL_DHashMoveEntryStub : s_CopyEntry,
1.405 + s_ClearEntry,
1.406 + ::PL_DHashFinalizeStub,
1.407 + s_InitEntry
1.408 + };
1.409 +
1.410 + PL_DHashTableInit(&mTable, &sOps, nullptr, sizeof(EntryType), aInitSize);
1.411 +}
1.412 +
1.413 +// static definitions
1.414 +
1.415 +template<class EntryType>
1.416 +PLDHashNumber
1.417 +nsTHashtable<EntryType>::s_HashKey(PLDHashTable *table,
1.418 + const void *key)
1.419 +{
1.420 + return EntryType::HashKey(reinterpret_cast<const KeyTypePointer>(key));
1.421 +}
1.422 +
1.423 +template<class EntryType>
1.424 +bool
1.425 +nsTHashtable<EntryType>::s_MatchEntry(PLDHashTable *table,
1.426 + const PLDHashEntryHdr *entry,
1.427 + const void *key)
1.428 +{
1.429 + return ((const EntryType*) entry)->KeyEquals(
1.430 + reinterpret_cast<const KeyTypePointer>(key));
1.431 +}
1.432 +
1.433 +template<class EntryType>
1.434 +void
1.435 +nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable *table,
1.436 + const PLDHashEntryHdr *from,
1.437 + PLDHashEntryHdr *to)
1.438 +{
1.439 + EntryType* fromEntry =
1.440 + const_cast<EntryType*>(reinterpret_cast<const EntryType*>(from));
1.441 +
1.442 + new(to) EntryType(mozilla::Move(*fromEntry));
1.443 +
1.444 + fromEntry->~EntryType();
1.445 +}
1.446 +
1.447 +template<class EntryType>
1.448 +void
1.449 +nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable *table,
1.450 + PLDHashEntryHdr *entry)
1.451 +{
1.452 + reinterpret_cast<EntryType*>(entry)->~EntryType();
1.453 +}
1.454 +
1.455 +template<class EntryType>
1.456 +bool
1.457 +nsTHashtable<EntryType>::s_InitEntry(PLDHashTable *table,
1.458 + PLDHashEntryHdr *entry,
1.459 + const void *key)
1.460 +{
1.461 + new(entry) EntryType(reinterpret_cast<KeyTypePointer>(key));
1.462 + return true;
1.463 +}
1.464 +
1.465 +template<class EntryType>
1.466 +PLDHashOperator
1.467 +nsTHashtable<EntryType>::s_EnumStub(PLDHashTable *table,
1.468 + PLDHashEntryHdr *entry,
1.469 + uint32_t number,
1.470 + void *arg)
1.471 +{
1.472 + // dereferences the function-pointer to the user's enumeration function
1.473 + return (* reinterpret_cast<s_EnumArgs*>(arg)->userFunc)(
1.474 + reinterpret_cast<EntryType*>(entry),
1.475 + reinterpret_cast<s_EnumArgs*>(arg)->userArg);
1.476 +}
1.477 +
1.478 +template<class EntryType>
1.479 +size_t
1.480 +nsTHashtable<EntryType>::s_SizeOfStub(PLDHashEntryHdr *entry,
1.481 + mozilla::MallocSizeOf mallocSizeOf,
1.482 + void *arg)
1.483 +{
1.484 + // dereferences the function-pointer to the user's enumeration function
1.485 + return (* reinterpret_cast<s_SizeOfArgs*>(arg)->userFunc)(
1.486 + reinterpret_cast<EntryType*>(entry),
1.487 + mallocSizeOf,
1.488 + reinterpret_cast<s_SizeOfArgs*>(arg)->userArg);
1.489 +}
1.490 +
1.491 +class nsCycleCollectionTraversalCallback;
1.492 +
1.493 +struct MOZ_STACK_CLASS nsTHashtableCCTraversalData
1.494 +{
1.495 + nsTHashtableCCTraversalData(nsCycleCollectionTraversalCallback& aCallback,
1.496 + const char* aName,
1.497 + uint32_t aFlags)
1.498 + : mCallback(aCallback),
1.499 + mName(aName),
1.500 + mFlags(aFlags)
1.501 + {
1.502 + }
1.503 +
1.504 + nsCycleCollectionTraversalCallback& mCallback;
1.505 + const char* mName;
1.506 + uint32_t mFlags;
1.507 +};
1.508 +
1.509 +template <class EntryType>
1.510 +PLDHashOperator
1.511 +ImplCycleCollectionTraverse_EnumFunc(EntryType *aEntry,
1.512 + void* aUserData)
1.513 +{
1.514 + auto userData = static_cast<nsTHashtableCCTraversalData*>(aUserData);
1.515 +
1.516 + ImplCycleCollectionTraverse(userData->mCallback,
1.517 + *aEntry,
1.518 + userData->mName,
1.519 + userData->mFlags);
1.520 + return PL_DHASH_NEXT;
1.521 +}
1.522 +
1.523 +template <class EntryType>
1.524 +inline void
1.525 +ImplCycleCollectionUnlink(nsTHashtable<EntryType>& aField)
1.526 +{
1.527 + aField.Clear();
1.528 +}
1.529 +
1.530 +template <class EntryType>
1.531 +inline void
1.532 +ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
1.533 + nsTHashtable<EntryType>& aField,
1.534 + const char* aName,
1.535 + uint32_t aFlags = 0)
1.536 +{
1.537 + nsTHashtableCCTraversalData userData(aCallback, aName, aFlags);
1.538 +
1.539 + aField.EnumerateEntries(ImplCycleCollectionTraverse_EnumFunc<EntryType>,
1.540 + &userData);
1.541 +}
1.542 +
1.543 +#endif // nsTHashtable_h__
