1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef nsTHashtable_h__
8 #define nsTHashtable_h__
9
10 #include "PLDHashTable.h"
11 #include "nsPointerHashKeys.h"
12 #include "mozilla/Assertions.h"
13 #include "mozilla/Attributes.h"
14 #include "mozilla/fallible.h"
15 #include "mozilla/MemoryChecking.h"
16 #include "mozilla/MemoryReporting.h"
17 #include "mozilla/Move.h"
18 #include "mozilla/OperatorNewExtensions.h"
19 #include "mozilla/PodOperations.h"
20 #include "mozilla/TypeTraits.h"
21
22 #include <new>
23
24 /**
25 * a base class for templated hashtables.
26 *
27 * Clients will rarely need to use this class directly. Check the derived
28 * classes first, to see if they will meet your needs.
29 *
30 * @param EntryType the templated entry-type class that is managed by the
31 * hashtable. <code>EntryType</code> must extend the following declaration,
32 * and <strong>must not declare any virtual functions or derive from classes
33 * with virtual functions.</strong> Any vtable pointer would break the
34 * PLDHashTable code.
35 *<pre> class EntryType : public PLDHashEntryHdr
36 * {
37 * public: or friend nsTHashtable<EntryType>;
38 * // KeyType is what we use when Get()ing or Put()ing this entry
39 * // this should either be a simple datatype (uint32_t, nsISupports*) or
40 * // a const reference (const nsAString&)
41 * typedef something KeyType;
42 * // KeyTypePointer is the pointer-version of KeyType, because
43 * // PLDHashTable.h requires keys to cast to <code>const void*</code>
44 * typedef const something* KeyTypePointer;
45 *
46 * EntryType(KeyTypePointer aKey);
47 *
48 * // A copy or C++11 Move constructor must be defined, even if
49 * // AllowMemMove() == true, otherwise you will cause link errors.
50 * EntryType(const EntryType& aEnt); // Either this...
51 * EntryType(EntryType&& aEnt); // ...or this
52 *
53 * // the destructor must be defined... or you will cause link errors!
54 * ~EntryType();
55 *
56 * // KeyEquals(): does this entry match this key?
57 * bool KeyEquals(KeyTypePointer aKey) const;
58 *
59 * // KeyToPointer(): Convert KeyType to KeyTypePointer
60 * static KeyTypePointer KeyToPointer(KeyType aKey);
61 *
62 * // HashKey(): calculate the hash number
63 * static PLDHashNumber HashKey(KeyTypePointer aKey);
64 *
65 * // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
66 * // to use the copy constructor?
67 * enum { ALLOW_MEMMOVE = true/false };
68 * }</pre>
69 *
70 * @see nsInterfaceHashtable
71 * @see nsDataHashtable
72 * @see nsClassHashtable
73 * @author "Benjamin Smedberg <bsmedberg@covad.net>"
74 */
75
76 template<class EntryType>
77 class MOZ_NEEDS_NO_VTABLE_TYPE nsTHashtable
78 {
79 typedef mozilla::fallible_t fallible_t;
80 static_assert(mozilla::IsPointer<typename EntryType::KeyTypePointer>::value,
81 "KeyTypePointer should be a pointer");
82
83 public:
84 // Separate constructors instead of default aInitLength parameter since
85 // otherwise the default no-arg constructor isn't found.
nsTHashtable()86 nsTHashtable()
87 : mTable(Ops(), sizeof(EntryType), PLDHashTable::kDefaultInitialLength)
88 {}
nsTHashtable(uint32_t aInitLength)89 explicit nsTHashtable(uint32_t aInitLength)
90 : mTable(Ops(), sizeof(EntryType), aInitLength)
91 {}
92
93 /**
94 * destructor, cleans up and deallocates
95 */
96 ~nsTHashtable();
97
98 nsTHashtable(nsTHashtable<EntryType>&& aOther);
99
100 /**
101 * Return the generation number for the table. This increments whenever
102 * the table data items are moved.
103 */
GetGeneration()104 uint32_t GetGeneration() const { return mTable.Generation(); }
105
106 /**
107 * KeyType is typedef'ed for ease of use.
108 */
109 typedef typename EntryType::KeyType KeyType;
110
111 /**
112 * KeyTypePointer is typedef'ed for ease of use.
113 */
114 typedef typename EntryType::KeyTypePointer KeyTypePointer;
115
116 /**
117 * Return the number of entries in the table.
118 * @return number of entries
119 */
Count()120 uint32_t Count() const { return mTable.EntryCount(); }
121
122 /**
123 * Return true if the hashtable is empty.
124 */
IsEmpty()125 bool IsEmpty() const { return Count() == 0; }
126
127 /**
128 * Get the entry associated with a key.
129 * @param aKey the key to retrieve
130 * @return pointer to the entry class, if the key exists; nullptr if the
131 * key doesn't exist
132 */
GetEntry(KeyType aKey)133 EntryType* GetEntry(KeyType aKey) const
134 {
135 return static_cast<EntryType*>(
136 const_cast<PLDHashTable*>(&mTable)->Search(EntryType::KeyToPointer(aKey)));
137 }
138
139 /**
140 * Return true if an entry for the given key exists, false otherwise.
141 * @param aKey the key to retrieve
142 * @return true if the key exists, false if the key doesn't exist
143 */
Contains(KeyType aKey)144 bool Contains(KeyType aKey) const { return !!GetEntry(aKey); }
145
146 /**
147 * Get the entry associated with a key, or create a new entry,
148 * @param aKey the key to retrieve
149 * @return pointer to the entry class retreived; nullptr only if memory
150 can't be allocated
151 */
PutEntry(KeyType aKey)152 EntryType* PutEntry(KeyType aKey)
153 {
154 // infallible add
155 return static_cast<EntryType*>(mTable.Add(EntryType::KeyToPointer(aKey)));
156 }
157
158 MOZ_MUST_USE
PutEntry(KeyType aKey,const fallible_t &)159 EntryType* PutEntry(KeyType aKey, const fallible_t&)
160 {
161 return static_cast<EntryType*>(mTable.Add(EntryType::KeyToPointer(aKey),
162 mozilla::fallible));
163 }
164
165 /**
166 * Remove the entry associated with a key.
167 * @param aKey of the entry to remove
168 */
RemoveEntry(KeyType aKey)169 void RemoveEntry(KeyType aKey)
170 {
171 mTable.Remove(EntryType::KeyToPointer(aKey));
172 }
173
174 /**
175 * Remove the entry associated with a key.
176 * @param aEntry the entry-pointer to remove (obtained from GetEntry)
177 */
RemoveEntry(EntryType * aEntry)178 void RemoveEntry(EntryType* aEntry)
179 {
180 mTable.RemoveEntry(aEntry);
181 }
182
183 /**
184 * Remove the entry associated with a key, but don't resize the hashtable.
185 * This is a low-level method, and is not recommended unless you know what
186 * you're doing. If you use it, please add a comment explaining why you
187 * didn't use RemoveEntry().
188 * @param aEntry the entry-pointer to remove (obtained from GetEntry)
189 */
RawRemoveEntry(EntryType * aEntry)190 void RawRemoveEntry(EntryType* aEntry)
191 {
192 mTable.RawRemove(aEntry);
193 }
194
195 // This is an iterator that also allows entry removal. Example usage:
196 //
197 // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
198 // Entry* entry = iter.Get();
199 // // ... do stuff with |entry| ...
200 // // ... possibly call iter.Remove() once ...
201 // }
202 //
203 class Iterator : public PLDHashTable::Iterator
204 {
205 public:
206 typedef PLDHashTable::Iterator Base;
207
Iterator(nsTHashtable * aTable)208 explicit Iterator(nsTHashtable* aTable) : Base(&aTable->mTable) {}
Iterator(Iterator && aOther)209 Iterator(Iterator&& aOther) : Base(aOther.mTable) {}
~Iterator()210 ~Iterator() {}
211
Get()212 EntryType* Get() const { return static_cast<EntryType*>(Base::Get()); }
213
214 private:
215 Iterator() = delete;
216 Iterator(const Iterator&) = delete;
217 Iterator& operator=(const Iterator&) = delete;
218 Iterator& operator=(const Iterator&&) = delete;
219 };
220
Iter()221 Iterator Iter() { return Iterator(this); }
222
ConstIter()223 Iterator ConstIter() const
224 {
225 return Iterator(const_cast<nsTHashtable*>(this));
226 }
227
228 /**
229 * Remove all entries, return hashtable to "pristine" state. It's
230 * conceptually the same as calling the destructor and then re-calling the
231 * constructor.
232 */
Clear()233 void Clear()
234 {
235 mTable.Clear();
236 }
237
238 /**
239 * Measure the size of the table's entry storage. Does *not* measure anything
240 * hanging off table entries; hence the "Shallow" prefix. To measure that,
241 * either use SizeOfExcludingThis() or iterate manually over the entries,
242 * calling SizeOfExcludingThis() on each one.
243 *
244 * @param aMallocSizeOf the function used to measure heap-allocated blocks
245 * @return the measured shallow size of the table
246 */
ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf)247 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
248 {
249 return mTable.ShallowSizeOfExcludingThis(aMallocSizeOf);
250 }
251
252 /**
253 * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
254 */
ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf)255 size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
256 {
257 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
258 }
259
260 /**
261 * This is a "deep" measurement of the table. To use it, |EntryType| must
262 * define SizeOfExcludingThis, and that method will be called on all live
263 * entries.
264 */
SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf)265 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
266 {
267 size_t n = ShallowSizeOfExcludingThis(aMallocSizeOf);
268 for (auto iter = ConstIter(); !iter.Done(); iter.Next()) {
269 n += (*iter.Get()).SizeOfExcludingThis(aMallocSizeOf);
270 }
271 return n;
272 }
273
274 /**
275 * Like SizeOfExcludingThis, but includes sizeof(*this).
276 */
SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf)277 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
278 {
279 return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
280 }
281
282 /**
283 * Swap the elements in this hashtable with the elements in aOther.
284 */
SwapElements(nsTHashtable<EntryType> & aOther)285 void SwapElements(nsTHashtable<EntryType>& aOther)
286 {
287 MOZ_ASSERT_IF(this->mTable.Ops() && aOther.mTable.Ops(),
288 this->mTable.Ops() == aOther.mTable.Ops());
289 mozilla::Swap(this->mTable, aOther.mTable);
290 }
291
292 #ifdef DEBUG
293 /**
294 * Mark the table as constant after initialization.
295 *
296 * This will prevent assertions when a read-only hash is accessed on multiple
297 * threads without synchronization.
298 */
MarkImmutable()299 void MarkImmutable()
300 {
301 mTable.MarkImmutable();
302 }
303 #endif
304
305 protected:
306 PLDHashTable mTable;
307
308 static PLDHashNumber s_HashKey(const void* aKey);
309
310 static bool s_MatchEntry(const PLDHashEntryHdr* aEntry,
311 const void* aKey);
312
313 static void s_CopyEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom,
314 PLDHashEntryHdr* aTo);
315
316 static void s_ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
317
318 static void s_InitEntry(PLDHashEntryHdr* aEntry, const void* aKey);
319
320 private:
321 // copy constructor, not implemented
322 nsTHashtable(nsTHashtable<EntryType>& aToCopy) = delete;
323
324 /**
325 * Gets the table's ops.
326 */
327 static const PLDHashTableOps* Ops();
328
329 // assignment operator, not implemented
330 nsTHashtable<EntryType>& operator=(nsTHashtable<EntryType>& aToEqual) = delete;
331 };
332
333 //
334 // template definitions
335 //
336
337 template<class EntryType>
nsTHashtable(nsTHashtable<EntryType> && aOther)338 nsTHashtable<EntryType>::nsTHashtable(nsTHashtable<EntryType>&& aOther)
339 : mTable(mozilla::Move(aOther.mTable))
340 {
341 // aOther shouldn't touch mTable after this, because we've stolen the table's
342 // pointers but not overwitten them.
343 MOZ_MAKE_MEM_UNDEFINED(&aOther.mTable, sizeof(aOther.mTable));
344 }
345
346 template<class EntryType>
~nsTHashtable()347 nsTHashtable<EntryType>::~nsTHashtable()
348 {
349 }
350
351 template<class EntryType>
352 /* static */ const PLDHashTableOps*
Ops()353 nsTHashtable<EntryType>::Ops()
354 {
355 // If this variable is a global variable, we get strange start-up failures on
356 // WindowsCrtPatch.h (see bug 1166598 comment 20). But putting it inside a
357 // function avoids that problem.
358 static const PLDHashTableOps sOps =
359 {
360 s_HashKey,
361 s_MatchEntry,
362 EntryType::ALLOW_MEMMOVE ? PLDHashTable::MoveEntryStub : s_CopyEntry,
363 s_ClearEntry,
364 s_InitEntry
365 };
366 return &sOps;
367 }
368
369 // static definitions
370
371 template<class EntryType>
372 PLDHashNumber
s_HashKey(const void * aKey)373 nsTHashtable<EntryType>::s_HashKey(const void* aKey)
374 {
375 return EntryType::HashKey(static_cast<const KeyTypePointer>(aKey));
376 }
377
378 template<class EntryType>
379 bool
s_MatchEntry(const PLDHashEntryHdr * aEntry,const void * aKey)380 nsTHashtable<EntryType>::s_MatchEntry(const PLDHashEntryHdr* aEntry,
381 const void* aKey)
382 {
383 return ((const EntryType*)aEntry)->KeyEquals(
384 static_cast<const KeyTypePointer>(aKey));
385 }
386
387 template<class EntryType>
388 void
s_CopyEntry(PLDHashTable * aTable,const PLDHashEntryHdr * aFrom,PLDHashEntryHdr * aTo)389 nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable* aTable,
390 const PLDHashEntryHdr* aFrom,
391 PLDHashEntryHdr* aTo)
392 {
393 EntryType* fromEntry =
394 const_cast<EntryType*>(static_cast<const EntryType*>(aFrom));
395
396 new (mozilla::KnownNotNull, aTo) EntryType(mozilla::Move(*fromEntry));
397
398 fromEntry->~EntryType();
399 }
400
401 template<class EntryType>
402 void
s_ClearEntry(PLDHashTable * aTable,PLDHashEntryHdr * aEntry)403 nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable* aTable,
404 PLDHashEntryHdr* aEntry)
405 {
406 static_cast<EntryType*>(aEntry)->~EntryType();
407 }
408
409 template<class EntryType>
410 void
s_InitEntry(PLDHashEntryHdr * aEntry,const void * aKey)411 nsTHashtable<EntryType>::s_InitEntry(PLDHashEntryHdr* aEntry,
412 const void* aKey)
413 {
414 new (mozilla::KnownNotNull, aEntry) EntryType(static_cast<KeyTypePointer>(aKey));
415 }
416
417 class nsCycleCollectionTraversalCallback;
418
419 template<class EntryType>
420 inline void
ImplCycleCollectionUnlink(nsTHashtable<EntryType> & aField)421 ImplCycleCollectionUnlink(nsTHashtable<EntryType>& aField)
422 {
423 aField.Clear();
424 }
425
426 template<class EntryType>
427 inline void
428 ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
429 nsTHashtable<EntryType>& aField,
430 const char* aName,
431 uint32_t aFlags = 0)
432 {
433 for (auto iter = aField.Iter(); !iter.Done(); iter.Next()) {
434 EntryType* entry = iter.Get();
435 ImplCycleCollectionTraverse(aCallback, *entry, aName, aFlags);
436 }
437 }
438
439 /**
440 * For nsTHashtable with pointer entries, we can have a template specialization
441 * that layers a typed T* interface on top of a common implementation that
442 * works internally with void pointers. This arrangement saves code size and
443 * might slightly improve performance as well.
444 */
445
446 /**
447 * We need a separate entry type class for the inheritance structure of the
448 * nsTHashtable specialization below; nsVoidPtrHashKey is simply typedefed to a
449 * specialization of nsPtrHashKey, and the formulation:
450 *
451 * class nsTHashtable<nsPtrHashKey<T>> : protected nsTHashtable<nsPtrHashKey<const void>
452 *
453 * is not going to turn out very well, since we'd wind up with an nsTHashtable
454 * instantiation that is its own base class.
455 */
456 namespace detail {
457
458 class VoidPtrHashKey : public nsPtrHashKey<const void>
459 {
460 typedef nsPtrHashKey<const void> Base;
461
462 public:
VoidPtrHashKey(const void * aKey)463 explicit VoidPtrHashKey(const void* aKey) : Base(aKey) {}
464 };
465
466 } // namespace detail
467
468 /**
469 * See the main nsTHashtable documentation for descriptions of this class's
470 * methods.
471 */
472 template<typename T>
473 class nsTHashtable<nsPtrHashKey<T>> : protected nsTHashtable<::detail::VoidPtrHashKey>
474 {
475 typedef nsTHashtable<::detail::VoidPtrHashKey> Base;
476 typedef nsPtrHashKey<T> EntryType;
477
478 // We play games with reinterpret_cast'ing between these two classes, so
479 // try to ensure that playing said games is reasonable.
480 static_assert(sizeof(nsPtrHashKey<T>) == sizeof(::detail::VoidPtrHashKey),
481 "hash keys must be the same size");
482
483 nsTHashtable(const nsTHashtable& aOther) = delete;
484 nsTHashtable& operator=(const nsTHashtable& aOther) = delete;
485
486 public:
487 nsTHashtable() = default;
nsTHashtable(uint32_t aInitLength)488 explicit nsTHashtable(uint32_t aInitLength)
489 : Base(aInitLength)
490 {}
491
492 ~nsTHashtable() = default;
493
494 nsTHashtable(nsTHashtable&&) = default;
495
496 /* Wrapper functions */
497 using Base::GetGeneration;
498 using Base::Count;
499 using Base::IsEmpty;
500 using Base::Clear;
501
502 using Base::ShallowSizeOfExcludingThis;
503 using Base::ShallowSizeOfIncludingThis;
504
505 #ifdef DEBUG
506 using Base::MarkImmutable;
507 #endif
508
GetEntry(T * aKey)509 EntryType* GetEntry(T* aKey) const
510 {
511 return reinterpret_cast<EntryType*>(Base::GetEntry(aKey));
512 }
513
Contains(T * aKey)514 bool Contains(T* aKey) const
515 {
516 return Base::Contains(aKey);
517 }
518
PutEntry(T * aKey)519 EntryType* PutEntry(T* aKey)
520 {
521 return reinterpret_cast<EntryType*>(Base::PutEntry(aKey));
522 }
523
524 MOZ_MUST_USE
PutEntry(T * aKey,const mozilla::fallible_t &)525 EntryType* PutEntry(T* aKey, const mozilla::fallible_t&)
526 {
527 return reinterpret_cast<EntryType*>(
528 Base::PutEntry(aKey, mozilla::fallible));
529 }
530
RemoveEntry(T * aKey)531 void RemoveEntry(T* aKey)
532 {
533 Base::RemoveEntry(aKey);
534 }
535
RemoveEntry(EntryType * aEntry)536 void RemoveEntry(EntryType* aEntry)
537 {
538 Base::RemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
539 }
540
RawRemoveEntry(EntryType * aEntry)541 void RawRemoveEntry(EntryType* aEntry)
542 {
543 Base::RawRemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
544 }
545
546 class Iterator : public Base::Iterator
547 {
548 public:
549 typedef nsTHashtable::Base::Iterator Base;
550
Iterator(nsTHashtable * aTable)551 explicit Iterator(nsTHashtable* aTable) : Base(aTable) {}
Iterator(Iterator && aOther)552 Iterator(Iterator&& aOther) : Base(mozilla::Move(aOther)) {}
553 ~Iterator() = default;
554
Get()555 EntryType* Get() const { return reinterpret_cast<EntryType*>(Base::Get()); }
556
557 private:
558 Iterator() = delete;
559 Iterator(const Iterator&) = delete;
560 Iterator& operator=(const Iterator&) = delete;
561 Iterator& operator=(Iterator&&) = delete;
562 };
563
Iter()564 Iterator Iter() { return Iterator(this); }
565
ConstIter()566 Iterator ConstIter() const
567 {
568 return Iterator(const_cast<nsTHashtable*>(this));
569 }
570
SwapElements(nsTHashtable & aOther)571 void SwapElements(nsTHashtable& aOther)
572 {
573 Base::SwapElements(aOther);
574 }
575 };
576
577 #endif // nsTHashtable_h__
578