Line data Source code
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.
86 8556 : nsTHashtable()
87 8556 : : mTable(Ops(), sizeof(EntryType), PLDHashTable::kDefaultInitialLength)
88 8556 : {}
89 2221 : explicit nsTHashtable(uint32_t aInitLength)
90 2221 : : mTable(Ops(), sizeof(EntryType), aInitLength)
91 2221 : {}
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 : */
104 12014 : 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 : */
120 14095 : uint32_t Count() const { return mTable.EntryCount(); }
121 :
122 : /**
123 : * Return true if the hashtable is empty.
124 : */
125 1198 : 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 : */
133 144152 : EntryType* GetEntry(KeyType aKey) const
134 : {
135 144152 : return static_cast<EntryType*>(
136 258516 : 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 : */
144 47337 : 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 : */
152 40398 : EntryType* PutEntry(KeyType aKey)
153 : {
154 : // infallible add
155 40398 : return static_cast<EntryType*>(mTable.Add(EntryType::KeyToPointer(aKey)));
156 : }
157 :
158 : MOZ_MUST_USE
159 32822 : EntryType* PutEntry(KeyType aKey, const fallible_t&)
160 : {
161 32822 : return static_cast<EntryType*>(mTable.Add(EntryType::KeyToPointer(aKey),
162 32822 : mozilla::fallible));
163 : }
164 :
165 : /**
166 : * Get the entry associated with a key, or create a new entry using infallible
167 : * allocation and insert that.
168 : * @param aKey the key to retrieve
169 : * @param aEntry will be assigned (if non-null) to the entry that was found
170 : * or created
171 : * @return true if a new entry was created, or false if an existing entry
172 : * was found
173 : */
174 : MOZ_MUST_USE
175 280 : bool EnsureInserted(KeyType aKey, EntryType** aEntry = nullptr)
176 : {
177 280 : auto oldCount = Count();
178 280 : EntryType* entry = PutEntry(aKey);
179 280 : if (aEntry) {
180 0 : *aEntry = entry;
181 : }
182 280 : return oldCount != Count();
183 : }
184 :
185 : /**
186 : * Remove the entry associated with a key.
187 : * @param aKey of the entry to remove
188 : */
189 7199 : void RemoveEntry(KeyType aKey)
190 : {
191 7199 : mTable.Remove(EntryType::KeyToPointer(aKey));
192 7199 : }
193 :
194 : /**
195 : * Lookup the entry associated with aKey and remove it if found, otherwise
196 : * do nothing.
197 : * @param aKey of the entry to remove
198 : * @return true if an entry was found and removed, or false if no entry
199 : * was found for aKey
200 : */
201 113 : bool EnsureRemoved(KeyType aKey)
202 : {
203 113 : auto* entry = GetEntry(aKey);
204 113 : if (entry) {
205 113 : RemoveEntry(entry);
206 113 : return true;
207 : }
208 0 : return false;
209 : }
210 :
211 : /**
212 : * Remove the entry associated with a key.
213 : * @param aEntry the entry-pointer to remove (obtained from GetEntry)
214 : */
215 1748 : void RemoveEntry(EntryType* aEntry)
216 : {
217 1748 : mTable.RemoveEntry(aEntry);
218 1748 : }
219 :
220 : /**
221 : * Remove the entry associated with a key, but don't resize the hashtable.
222 : * This is a low-level method, and is not recommended unless you know what
223 : * you're doing. If you use it, please add a comment explaining why you
224 : * didn't use RemoveEntry().
225 : * @param aEntry the entry-pointer to remove (obtained from GetEntry)
226 : */
227 0 : void RawRemoveEntry(EntryType* aEntry)
228 : {
229 0 : mTable.RawRemove(aEntry);
230 0 : }
231 :
232 : // This is an iterator that also allows entry removal. Example usage:
233 : //
234 : // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
235 : // Entry* entry = iter.Get();
236 : // // ... do stuff with |entry| ...
237 : // // ... possibly call iter.Remove() once ...
238 : // }
239 : //
240 : class Iterator : public PLDHashTable::Iterator
241 : {
242 : public:
243 : typedef PLDHashTable::Iterator Base;
244 :
245 1908 : explicit Iterator(nsTHashtable* aTable) : Base(&aTable->mTable) {}
246 80 : Iterator(Iterator&& aOther) : Base(aOther.mTable) {}
247 1988 : ~Iterator() {}
248 :
249 4072 : EntryType* Get() const { return static_cast<EntryType*>(Base::Get()); }
250 :
251 : private:
252 : Iterator() = delete;
253 : Iterator(const Iterator&) = delete;
254 : Iterator& operator=(const Iterator&) = delete;
255 : Iterator& operator=(const Iterator&&) = delete;
256 : };
257 :
258 776 : Iterator Iter() { return Iterator(this); }
259 :
260 37 : Iterator ConstIter() const
261 : {
262 37 : return Iterator(const_cast<nsTHashtable*>(this));
263 : }
264 :
265 : /**
266 : * Remove all entries, return hashtable to "pristine" state. It's
267 : * conceptually the same as calling the destructor and then re-calling the
268 : * constructor.
269 : */
270 743 : void Clear()
271 : {
272 743 : mTable.Clear();
273 743 : }
274 :
275 : /**
276 : * Measure the size of the table's entry storage. Does *not* measure anything
277 : * hanging off table entries; hence the "Shallow" prefix. To measure that,
278 : * either use SizeOfExcludingThis() or iterate manually over the entries,
279 : * calling SizeOfExcludingThis() on each one.
280 : *
281 : * @param aMallocSizeOf the function used to measure heap-allocated blocks
282 : * @return the measured shallow size of the table
283 : */
284 84 : size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
285 : {
286 84 : return mTable.ShallowSizeOfExcludingThis(aMallocSizeOf);
287 : }
288 :
289 : /**
290 : * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
291 : */
292 0 : size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
293 : {
294 0 : return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
295 : }
296 :
297 : /**
298 : * This is a "deep" measurement of the table. To use it, |EntryType| must
299 : * define SizeOfExcludingThis, and that method will be called on all live
300 : * entries.
301 : */
302 21 : size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
303 : {
304 21 : size_t n = ShallowSizeOfExcludingThis(aMallocSizeOf);
305 52 : for (auto iter = ConstIter(); !iter.Done(); iter.Next()) {
306 31 : n += (*iter.Get()).SizeOfExcludingThis(aMallocSizeOf);
307 : }
308 21 : return n;
309 : }
310 :
311 : /**
312 : * Like SizeOfExcludingThis, but includes sizeof(*this).
313 : */
314 0 : size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
315 : {
316 0 : return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
317 : }
318 :
319 : /**
320 : * Swap the elements in this hashtable with the elements in aOther.
321 : */
322 1 : void SwapElements(nsTHashtable<EntryType>& aOther)
323 : {
324 1 : MOZ_ASSERT_IF(this->mTable.Ops() && aOther.mTable.Ops(),
325 : this->mTable.Ops() == aOther.mTable.Ops());
326 1 : mozilla::Swap(this->mTable, aOther.mTable);
327 1 : }
328 :
329 : #ifdef DEBUG
330 : /**
331 : * Mark the table as constant after initialization.
332 : *
333 : * This will prevent assertions when a read-only hash is accessed on multiple
334 : * threads without synchronization.
335 : */
336 12 : void MarkImmutable()
337 : {
338 12 : mTable.MarkImmutable();
339 12 : }
340 : #endif
341 :
342 : protected:
343 : PLDHashTable mTable;
344 :
345 : static PLDHashNumber s_HashKey(const void* aKey);
346 :
347 : static bool s_MatchEntry(const PLDHashEntryHdr* aEntry,
348 : const void* aKey);
349 :
350 : static void s_CopyEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom,
351 : PLDHashEntryHdr* aTo);
352 :
353 : static void s_ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
354 :
355 : static void s_InitEntry(PLDHashEntryHdr* aEntry, const void* aKey);
356 :
357 : private:
358 : // copy constructor, not implemented
359 : nsTHashtable(nsTHashtable<EntryType>& aToCopy) = delete;
360 :
361 : /**
362 : * Gets the table's ops.
363 : */
364 : static const PLDHashTableOps* Ops();
365 :
366 : // assignment operator, not implemented
367 : nsTHashtable<EntryType>& operator=(nsTHashtable<EntryType>& aToEqual) = delete;
368 : };
369 :
370 : //
371 : // template definitions
372 : //
373 :
374 : template<class EntryType>
375 0 : nsTHashtable<EntryType>::nsTHashtable(nsTHashtable<EntryType>&& aOther)
376 0 : : mTable(mozilla::Move(aOther.mTable))
377 : {
378 : // aOther shouldn't touch mTable after this, because we've stolen the table's
379 : // pointers but not overwitten them.
380 : MOZ_MAKE_MEM_UNDEFINED(&aOther.mTable, sizeof(aOther.mTable));
381 0 : }
382 :
383 : template<class EntryType>
384 4718 : nsTHashtable<EntryType>::~nsTHashtable()
385 : {
386 4718 : }
387 :
388 : template<class EntryType>
389 : /* static */ const PLDHashTableOps*
390 10777 : nsTHashtable<EntryType>::Ops()
391 : {
392 : // If this variable is a global variable, we get strange start-up failures on
393 : // WindowsCrtPatch.h (see bug 1166598 comment 20). But putting it inside a
394 : // function avoids that problem.
395 : static const PLDHashTableOps sOps =
396 : {
397 : s_HashKey,
398 : s_MatchEntry,
399 : EntryType::ALLOW_MEMMOVE ? PLDHashTable::MoveEntryStub : s_CopyEntry,
400 : s_ClearEntry,
401 : s_InitEntry
402 : };
403 10777 : return &sOps;
404 : }
405 :
406 : // static definitions
407 :
408 : template<class EntryType>
409 : PLDHashNumber
410 199533 : nsTHashtable<EntryType>::s_HashKey(const void* aKey)
411 : {
412 199533 : return EntryType::HashKey(static_cast<const KeyTypePointer>(aKey));
413 : }
414 :
415 : template<class EntryType>
416 : bool
417 93714 : nsTHashtable<EntryType>::s_MatchEntry(const PLDHashEntryHdr* aEntry,
418 : const void* aKey)
419 : {
420 : return ((const EntryType*)aEntry)->KeyEquals(
421 93714 : static_cast<const KeyTypePointer>(aKey));
422 : }
423 :
424 : template<class EntryType>
425 : void
426 1596 : nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable* aTable,
427 : const PLDHashEntryHdr* aFrom,
428 : PLDHashEntryHdr* aTo)
429 : {
430 : EntryType* fromEntry =
431 1596 : const_cast<EntryType*>(static_cast<const EntryType*>(aFrom));
432 :
433 1596 : new (mozilla::KnownNotNull, aTo) EntryType(mozilla::Move(*fromEntry));
434 :
435 1596 : fromEntry->~EntryType();
436 1596 : }
437 :
438 : template<class EntryType>
439 : void
440 11593 : nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable* aTable,
441 : PLDHashEntryHdr* aEntry)
442 : {
443 11593 : static_cast<EntryType*>(aEntry)->~EntryType();
444 11593 : }
445 :
446 : template<class EntryType>
447 : void
448 66245 : nsTHashtable<EntryType>::s_InitEntry(PLDHashEntryHdr* aEntry,
449 : const void* aKey)
450 : {
451 66245 : new (mozilla::KnownNotNull, aEntry) EntryType(static_cast<KeyTypePointer>(aKey));
452 66245 : }
453 :
454 : class nsCycleCollectionTraversalCallback;
455 :
456 : template<class EntryType>
457 : inline void
458 0 : ImplCycleCollectionUnlink(nsTHashtable<EntryType>& aField)
459 : {
460 0 : aField.Clear();
461 0 : }
462 :
463 : template<class EntryType>
464 : inline void
465 0 : ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
466 : nsTHashtable<EntryType>& aField,
467 : const char* aName,
468 : uint32_t aFlags = 0)
469 : {
470 0 : for (auto iter = aField.Iter(); !iter.Done(); iter.Next()) {
471 0 : EntryType* entry = iter.Get();
472 0 : ImplCycleCollectionTraverse(aCallback, *entry, aName, aFlags);
473 : }
474 0 : }
475 :
476 : /**
477 : * For nsTHashtable with pointer entries, we can have a template specialization
478 : * that layers a typed T* interface on top of a common implementation that
479 : * works internally with void pointers. This arrangement saves code size and
480 : * might slightly improve performance as well.
481 : */
482 :
483 : /**
484 : * We need a separate entry type class for the inheritance structure of the
485 : * nsTHashtable specialization below; nsVoidPtrHashKey is simply typedefed to a
486 : * specialization of nsPtrHashKey, and the formulation:
487 : *
488 : * class nsTHashtable<nsPtrHashKey<T>> : protected nsTHashtable<nsPtrHashKey<const void>
489 : *
490 : * is not going to turn out very well, since we'd wind up with an nsTHashtable
491 : * instantiation that is its own base class.
492 : */
493 : namespace detail {
494 :
495 7545 : class VoidPtrHashKey : public nsPtrHashKey<const void>
496 : {
497 : typedef nsPtrHashKey<const void> Base;
498 :
499 : public:
500 12862 : explicit VoidPtrHashKey(const void* aKey) : Base(aKey) {}
501 : };
502 :
503 : } // namespace detail
504 :
505 : /**
506 : * See the main nsTHashtable documentation for descriptions of this class's
507 : * methods.
508 : */
509 : template<typename T>
510 : class nsTHashtable<nsPtrHashKey<T>> : protected nsTHashtable<::detail::VoidPtrHashKey>
511 : {
512 : typedef nsTHashtable<::detail::VoidPtrHashKey> Base;
513 : typedef nsPtrHashKey<T> EntryType;
514 :
515 : // We play games with reinterpret_cast'ing between these two classes, so
516 : // try to ensure that playing said games is reasonable.
517 : static_assert(sizeof(nsPtrHashKey<T>) == sizeof(::detail::VoidPtrHashKey),
518 : "hash keys must be the same size");
519 :
520 : nsTHashtable(const nsTHashtable& aOther) = delete;
521 : nsTHashtable& operator=(const nsTHashtable& aOther) = delete;
522 :
523 : public:
524 1209 : nsTHashtable() = default;
525 89 : explicit nsTHashtable(uint32_t aInitLength)
526 89 : : Base(aInitLength)
527 89 : {}
528 :
529 296 : ~nsTHashtable() = default;
530 :
531 : nsTHashtable(nsTHashtable&&) = default;
532 :
533 : using Base::GetGeneration;
534 : using Base::Count;
535 : using Base::IsEmpty;
536 : using Base::Clear;
537 :
538 : using Base::ShallowSizeOfExcludingThis;
539 : using Base::ShallowSizeOfIncludingThis;
540 :
541 : #ifdef DEBUG
542 : using Base::MarkImmutable;
543 : #endif
544 :
545 : /* Wrapper functions */
546 128 : EntryType* GetEntry(T* aKey) const
547 : {
548 128 : return reinterpret_cast<EntryType*>(Base::GetEntry(aKey));
549 : }
550 :
551 25639 : bool Contains(T* aKey) const
552 : {
553 25639 : return Base::Contains(aKey);
554 : }
555 :
556 13527 : EntryType* PutEntry(T* aKey)
557 : {
558 13527 : return reinterpret_cast<EntryType*>(Base::PutEntry(aKey));
559 : }
560 :
561 : MOZ_MUST_USE
562 0 : EntryType* PutEntry(T* aKey, const mozilla::fallible_t&)
563 : {
564 : return reinterpret_cast<EntryType*>(
565 0 : Base::PutEntry(aKey, mozilla::fallible));
566 : }
567 :
568 : MOZ_MUST_USE
569 0 : bool EnsureInserted(T* aKey, EntryType** aEntry = nullptr)
570 : {
571 0 : return Base::EnsureInserted(aKey, reinterpret_cast<::detail::VoidPtrHashKey**>(aEntry));
572 : }
573 :
574 7092 : void RemoveEntry(T* aKey)
575 : {
576 7092 : Base::RemoveEntry(aKey);
577 7092 : }
578 :
579 0 : bool EnsureRemoved(T* aKey)
580 : {
581 0 : return Base::EnsureRemoved(aKey);
582 : }
583 :
584 25 : void RemoveEntry(EntryType* aEntry)
585 : {
586 25 : Base::RemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
587 25 : }
588 :
589 : void RawRemoveEntry(EntryType* aEntry)
590 : {
591 : Base::RawRemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
592 : }
593 :
594 : class Iterator : public Base::Iterator
595 : {
596 : public:
597 : typedef nsTHashtable::Base::Iterator Base;
598 :
599 1095 : explicit Iterator(nsTHashtable* aTable) : Base(aTable) {}
600 : Iterator(Iterator&& aOther) : Base(mozilla::Move(aOther)) {}
601 1095 : ~Iterator() = default;
602 :
603 1140 : EntryType* Get() const { return reinterpret_cast<EntryType*>(Base::Get()); }
604 :
605 : private:
606 : Iterator() = delete;
607 : Iterator(const Iterator&) = delete;
608 : Iterator& operator=(const Iterator&) = delete;
609 : Iterator& operator=(Iterator&&) = delete;
610 : };
611 :
612 329 : Iterator Iter() { return Iterator(this); }
613 :
614 710 : Iterator ConstIter() const
615 : {
616 710 : return Iterator(const_cast<nsTHashtable*>(this));
617 : }
618 :
619 1 : void SwapElements(nsTHashtable& aOther)
620 : {
621 1 : Base::SwapElements(aOther);
622 1 : }
623 : };
624 :
625 : #endif // nsTHashtable_h__
|
