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/. */
7 // See the comment at the top of mfbt/HashTable.h for a comparison between
8 // PLDHashTable and mozilla::HashTable.
10 #ifndef nsTHashtable_h__
11 #define nsTHashtable_h__
15 #include <type_traits>
18 #include "PLDHashTable.h"
19 #include "mozilla/Assertions.h"
20 #include "mozilla/Attributes.h"
21 #include "mozilla/Maybe.h"
22 #include "mozilla/MemoryReporting.h"
23 #include "mozilla/OperatorNewExtensions.h"
24 #include "mozilla/PodOperations.h"
25 #include "mozilla/fallible.h"
26 #include "nsPointerHashKeys.h"
27 #include "nsTArrayForwardDeclare.h"
29 template <class EntryType
>
33 class nsTHashtableIteratorBase
{
35 using EndIteratorTag
= PLDHashTable::Iterator::EndIteratorTag
;
37 nsTHashtableIteratorBase(nsTHashtableIteratorBase
&& aOther
) = default;
39 nsTHashtableIteratorBase
& operator=(nsTHashtableIteratorBase
&& aOther
) {
40 // User-defined because the move assignment operator is deleted in
41 // PLDHashtable::Iterator.
42 return operator=(static_cast<const nsTHashtableIteratorBase
&>(aOther
));
45 nsTHashtableIteratorBase(const nsTHashtableIteratorBase
& aOther
)
46 : mIterator
{aOther
.mIterator
.Clone()} {}
47 nsTHashtableIteratorBase
& operator=(const nsTHashtableIteratorBase
& aOther
) {
48 // Since PLDHashTable::Iterator has no assignment operator, we destroy and
49 // recreate mIterator.
50 mIterator
.~Iterator();
51 new (&mIterator
) PLDHashTable::Iterator(aOther
.mIterator
.Clone());
55 explicit nsTHashtableIteratorBase(PLDHashTable::Iterator aFrom
)
56 : mIterator
{std::move(aFrom
)} {}
58 explicit nsTHashtableIteratorBase(const PLDHashTable
& aTable
)
59 : mIterator
{&const_cast<PLDHashTable
&>(aTable
)} {}
61 nsTHashtableIteratorBase(const PLDHashTable
& aTable
, EndIteratorTag aTag
)
62 : mIterator
{&const_cast<PLDHashTable
&>(aTable
), aTag
} {}
64 bool operator==(const nsTHashtableIteratorBase
& aRhs
) const {
65 return mIterator
== aRhs
.mIterator
;
67 bool operator!=(const nsTHashtableIteratorBase
& aRhs
) const {
68 return !(*this == aRhs
);
72 PLDHashTable::Iterator mIterator
;
75 // STL-style iterators to allow the use in range-based for loops, e.g.
77 class nsTHashtableEntryIterator
: public nsTHashtableIteratorBase
{
78 friend class nsTHashtable
<std::remove_const_t
<T
>>;
81 using iterator_category
= std::forward_iterator_tag
;
83 using difference_type
= int32_t;
84 using pointer
= value_type
*;
85 using reference
= value_type
&;
87 using iterator_type
= nsTHashtableEntryIterator
;
88 using const_iterator_type
= nsTHashtableEntryIterator
<const T
>;
90 using nsTHashtableIteratorBase::nsTHashtableIteratorBase
;
92 value_type
* operator->() const {
93 return static_cast<value_type
*>(mIterator
.Get());
95 value_type
& operator*() const {
96 return *static_cast<value_type
*>(mIterator
.Get());
99 iterator_type
& operator++() {
103 iterator_type
operator++(int) {
104 iterator_type it
= *this;
109 operator const_iterator_type() const {
110 return const_iterator_type
{mIterator
.Clone()};
114 template <typename EntryType
>
115 class nsTHashtableKeyIterator
: public nsTHashtableIteratorBase
{
116 friend class nsTHashtable
<EntryType
>;
119 using iterator_category
= std::forward_iterator_tag
;
120 using value_type
= const std::decay_t
<typename
EntryType::KeyType
>;
121 using difference_type
= int32_t;
122 using pointer
= value_type
*;
123 using reference
= value_type
&;
125 using iterator_type
= nsTHashtableKeyIterator
;
126 using const_iterator_type
= nsTHashtableKeyIterator
;
128 using nsTHashtableIteratorBase::nsTHashtableIteratorBase
;
130 value_type
* operator->() const {
131 return &static_cast<const EntryType
*>(mIterator
.Get())->GetKey();
133 decltype(auto) operator*() const {
134 return static_cast<const EntryType
*>(mIterator
.Get())->GetKey();
137 iterator_type
& operator++() {
141 iterator_type
operator++(int) {
142 iterator_type it
= *this;
148 template <typename EntryType
>
149 class nsTHashtableKeyRange
{
151 using IteratorType
= nsTHashtableKeyIterator
<EntryType
>;
152 using iterator
= IteratorType
;
154 explicit nsTHashtableKeyRange(const PLDHashTable
& aHashtable
)
155 : mHashtable
{aHashtable
} {}
157 auto begin() const { return IteratorType
{mHashtable
}; }
159 return IteratorType
{mHashtable
, typename
IteratorType::EndIteratorTag
{}};
161 auto cbegin() const { return begin(); }
162 auto cend() const { return end(); }
164 uint32_t Count() const { return mHashtable
.EntryCount(); }
167 const PLDHashTable
& mHashtable
;
170 template <typename EntryType
>
171 auto RangeSize(const ::detail::nsTHashtableKeyRange
<EntryType
>& aRange
) {
172 return aRange
.Count();
175 } // namespace detail
178 * a base class for templated hashtables.
180 * Clients will rarely need to use this class directly. Check the derived
181 * classes first, to see if they will meet your needs.
183 * @param EntryType the templated entry-type class that is managed by the
184 * hashtable. <code>EntryType</code> must extend the following declaration,
185 * and <strong>must not declare any virtual functions or derive from classes
186 * with virtual functions.</strong> Any vtable pointer would break the
188 *<pre> class EntryType : public PLDHashEntryHdr
190 * public: or friend nsTHashtable<EntryType>;
191 * // KeyType is what we use when Get()ing or Put()ing this entry
192 * // this should either be a simple datatype (uint32_t, nsISupports*) or
193 * // a const reference (const nsAString&)
194 * typedef something KeyType;
195 * // KeyTypePointer is the pointer-version of KeyType, because
196 * // PLDHashTable.h requires keys to cast to <code>const void*</code>
197 * typedef const something* KeyTypePointer;
199 * EntryType(KeyTypePointer aKey);
201 * // A copy or C++11 Move constructor must be defined, even if
202 * // AllowMemMove() == true, otherwise you will cause link errors.
203 * EntryType(const EntryType& aEnt); // Either this...
204 * EntryType(EntryType&& aEnt); // ...or this
206 * // the destructor must be defined... or you will cause link errors!
209 * // KeyEquals(): does this entry match this key?
210 * bool KeyEquals(KeyTypePointer aKey) const;
212 * // KeyToPointer(): Convert KeyType to KeyTypePointer
213 * static KeyTypePointer KeyToPointer(KeyType aKey);
215 * // HashKey(): calculate the hash number
216 * static PLDHashNumber HashKey(KeyTypePointer aKey);
218 * // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
219 * // to use the copy constructor?
220 * enum { ALLOW_MEMMOVE = true/false };
223 * @see nsInterfaceHashtable
224 * @see nsClassHashtable
226 * @author "Benjamin Smedberg <bsmedberg@covad.net>"
229 template <class EntryType
>
230 class MOZ_NEEDS_NO_VTABLE_TYPE nsTHashtable
{
231 typedef mozilla::fallible_t fallible_t
;
232 static_assert(std::is_pointer_v
<typename
EntryType::KeyTypePointer
>,
233 "KeyTypePointer should be a pointer");
236 // Separate constructors instead of default aInitLength parameter since
237 // otherwise the default no-arg constructor isn't found.
239 : mTable(Ops(), sizeof(EntryType
), PLDHashTable::kDefaultInitialLength
) {}
240 explicit nsTHashtable(uint32_t aInitLength
)
241 : mTable(Ops(), sizeof(EntryType
), aInitLength
) {}
244 * destructor, cleans up and deallocates
246 ~nsTHashtable() = default;
248 nsTHashtable(nsTHashtable
<EntryType
>&& aOther
);
249 nsTHashtable
<EntryType
>& operator=(nsTHashtable
<EntryType
>&& aOther
);
251 nsTHashtable(const nsTHashtable
<EntryType
>&) = delete;
252 nsTHashtable
& operator=(const nsTHashtable
<EntryType
>&) = delete;
255 * Return the generation number for the table. This increments whenever
256 * the table data items are moved.
258 uint32_t GetGeneration() const { return mTable
.Generation(); }
261 * KeyType is typedef'ed for ease of use.
263 typedef typename
EntryType::KeyType KeyType
;
266 * KeyTypePointer is typedef'ed for ease of use.
268 typedef typename
EntryType::KeyTypePointer KeyTypePointer
;
271 * Return the number of entries in the table.
272 * @return number of entries
274 uint32_t Count() const { return mTable
.EntryCount(); }
277 * Return true if the hashtable is empty.
279 bool IsEmpty() const { return Count() == 0; }
282 * Get the entry associated with a key.
283 * @param aKey the key to retrieve
284 * @return pointer to the entry class, if the key exists; nullptr if the
287 EntryType
* GetEntry(KeyType aKey
) const {
288 return static_cast<EntryType
*>(
289 mTable
.Search(EntryType::KeyToPointer(aKey
)));
293 * Return true if an entry for the given key exists, false otherwise.
294 * @param aKey the key to retrieve
295 * @return true if the key exists, false if the key doesn't exist
297 bool Contains(KeyType aKey
) const { return !!GetEntry(aKey
); }
300 * Infallibly get the entry associated with a key, or create a new entry,
301 * @param aKey the key to retrieve
302 * @return pointer to the entry retrieved; never nullptr
304 EntryType
* PutEntry(KeyType aKey
) {
305 // Infallible WithEntryHandle.
306 return WithEntryHandle(
307 aKey
, [](auto entryHandle
) { return entryHandle
.OrInsert(); });
311 * Fallibly get the entry associated with a key, or create a new entry,
312 * @param aKey the key to retrieve
313 * @return pointer to the entry retrieved; nullptr only if memory can't
316 [[nodiscard
]] EntryType
* PutEntry(KeyType aKey
, const fallible_t
& aFallible
) {
317 return WithEntryHandle(aKey
, aFallible
, [](auto maybeEntryHandle
) {
318 return maybeEntryHandle
? maybeEntryHandle
->OrInsert() : nullptr;
323 * Get the entry associated with a key, or create a new entry using infallible
324 * allocation and insert that.
325 * @param aKey the key to retrieve
326 * @param aEntry will be assigned (if non-null) to the entry that was
328 * @return true if a new entry was created, or false if an existing entry
331 [[nodiscard
]] bool EnsureInserted(KeyType aKey
,
332 EntryType
** aEntry
= nullptr) {
333 auto oldCount
= Count();
334 EntryType
* entry
= PutEntry(aKey
);
338 return oldCount
!= Count();
342 * Remove the entry associated with a key.
343 * @param aKey of the entry to remove
345 void RemoveEntry(KeyType aKey
) {
346 mTable
.Remove(EntryType::KeyToPointer(aKey
));
350 * Lookup the entry associated with aKey and remove it if found, otherwise
352 * @param aKey of the entry to remove
353 * @return true if an entry was found and removed, or false if no entry
356 bool EnsureRemoved(KeyType aKey
) {
357 auto* entry
= GetEntry(aKey
);
366 * Remove the entry associated with a key.
367 * @param aEntry the entry-pointer to remove (obtained from GetEntry)
369 void RemoveEntry(EntryType
* aEntry
) { mTable
.RemoveEntry(aEntry
); }
372 * Remove the entry associated with a key, but don't resize the hashtable.
373 * This is a low-level method, and is not recommended unless you know what
374 * you're doing. If you use it, please add a comment explaining why you
375 * didn't use RemoveEntry().
376 * @param aEntry the entry-pointer to remove (obtained from GetEntry)
378 void RawRemoveEntry(EntryType
* aEntry
) { mTable
.RawRemove(aEntry
); }
383 EntryHandle(EntryHandle
&& aOther
) = default;
384 ~EntryHandle() = default;
386 EntryHandle(const EntryHandle
&) = delete;
387 EntryHandle
& operator=(const EntryHandle
&) = delete;
388 EntryHandle
& operator=(const EntryHandle
&&) = delete;
390 KeyType
Key() const { return mKey
; }
392 bool HasEntry() const { return mEntryHandle
.HasEntry(); }
394 explicit operator bool() const { return mEntryHandle
.operator bool(); }
396 EntryType
* Entry() { return static_cast<EntryType
*>(mEntryHandle
.Entry()); }
398 void Insert() { InsertInternal(); }
400 EntryType
* OrInsert() {
407 void Remove() { mEntryHandle
.Remove(); }
409 void OrRemove() { mEntryHandle
.OrRemove(); }
412 template <typename
... Args
>
413 void InsertInternal(Args
&&... aArgs
) {
414 MOZ_RELEASE_ASSERT(!HasEntry());
415 mEntryHandle
.Insert([&](PLDHashEntryHdr
* entry
) {
416 new (mozilla::KnownNotNull
, entry
) EntryType(
417 EntryType::KeyToPointer(mKey
), std::forward
<Args
>(aArgs
)...);
422 friend class nsTHashtable
;
424 EntryHandle(KeyType aKey
, PLDHashTable::EntryHandle
&& aEntryHandle
)
425 : mKey(aKey
), mEntryHandle(std::move(aEntryHandle
)) {}
428 PLDHashTable::EntryHandle mEntryHandle
;
432 auto WithEntryHandle(KeyType aKey
, F
&& aFunc
)
433 -> std::invoke_result_t
<F
, EntryHandle
&&> {
434 return this->mTable
.WithEntryHandle(
435 EntryType::KeyToPointer(aKey
),
436 [&aKey
, &aFunc
](auto entryHandle
) -> decltype(auto) {
437 return std::forward
<F
>(aFunc
)(
438 EntryHandle
{aKey
, std::move(entryHandle
)});
443 auto WithEntryHandle(KeyType aKey
, const mozilla::fallible_t
& aFallible
,
445 -> std::invoke_result_t
<F
, mozilla::Maybe
<EntryHandle
>&&> {
446 return this->mTable
.WithEntryHandle(
447 EntryType::KeyToPointer(aKey
), aFallible
,
448 [&aKey
, &aFunc
](auto maybeEntryHandle
) {
449 return std::forward
<F
>(aFunc
)(
451 ? mozilla::Some(EntryHandle
{aKey
, maybeEntryHandle
.extract()})
452 : mozilla::Nothing());
457 class ConstIterator
{
459 explicit ConstIterator(nsTHashtable
* aTable
)
460 : mBaseIterator(&aTable
->mTable
) {}
461 ~ConstIterator() = default;
463 KeyType
Key() const { return Get()->GetKey(); }
465 const EntryType
* Get() const {
466 return static_cast<const EntryType
*>(mBaseIterator
.Get());
469 bool Done() const { return mBaseIterator
.Done(); }
470 void Next() { mBaseIterator
.Next(); }
472 ConstIterator() = delete;
473 ConstIterator(const ConstIterator
&) = delete;
474 ConstIterator(ConstIterator
&& aOther
) = delete;
475 ConstIterator
& operator=(const ConstIterator
&) = delete;
476 ConstIterator
& operator=(ConstIterator
&&) = delete;
479 PLDHashTable::Iterator mBaseIterator
;
482 // This is an iterator that also allows entry removal. Example usage:
484 // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
485 // Entry* entry = iter.Get();
486 // // ... do stuff with |entry| ...
487 // // ... possibly call iter.Remove() once ...
490 class Iterator final
: public ConstIterator
{
492 using ConstIterator::ConstIterator
;
494 using ConstIterator::Get
;
496 EntryType
* Get() const {
497 return static_cast<EntryType
*>(this->mBaseIterator
.Get());
500 void Remove() { this->mBaseIterator
.Remove(); }
503 Iterator
Iter() { return Iterator(this); }
505 ConstIterator
ConstIter() const {
506 return ConstIterator(const_cast<nsTHashtable
*>(this));
509 using const_iterator
= ::detail::nsTHashtableEntryIterator
<const EntryType
>;
510 using iterator
= ::detail::nsTHashtableEntryIterator
<EntryType
>;
512 iterator
begin() { return iterator
{mTable
}; }
513 const_iterator
begin() const { return const_iterator
{mTable
}; }
514 const_iterator
cbegin() const { return begin(); }
516 return iterator
{mTable
, typename
iterator::EndIteratorTag
{}};
518 const_iterator
end() const {
519 return const_iterator
{mTable
, typename
const_iterator::EndIteratorTag
{}};
521 const_iterator
cend() const { return end(); }
523 void Remove(const_iterator
& aIter
) { aIter
.mIterator
.Remove(); }
526 * Return a range of the keys (of KeyType). Note this range iterates over the
527 * keys in place, so modifications to the nsTHashtable invalidate the range
528 * while it's iterated, except when calling Remove() with a key iterator
529 * derived from that range.
532 return ::detail::nsTHashtableKeyRange
<EntryType
>{mTable
};
536 * Remove an entry from a key range, specified via a key iterator, e.g.
538 * for (auto it = hash.Keys().begin(), end = hash.Keys().end();
539 * it != end; * ++it) {
540 * if (*it > 42) { hash.Remove(it); }
543 void Remove(::detail::nsTHashtableKeyIterator
<EntryType
>& aIter
) {
544 aIter
.mIterator
.Remove();
548 * Remove all entries, return hashtable to "pristine" state. It's
549 * conceptually the same as calling the destructor and then re-calling the
552 void Clear() { mTable
.Clear(); }
555 * Measure the size of the table's entry storage. Does *not* measure anything
556 * hanging off table entries; hence the "Shallow" prefix. To measure that,
557 * either use SizeOfExcludingThis() or iterate manually over the entries,
558 * calling SizeOfExcludingThis() on each one.
560 * @param aMallocSizeOf the function used to measure heap-allocated blocks
561 * @return the measured shallow size of the table
563 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
564 return mTable
.ShallowSizeOfExcludingThis(aMallocSizeOf
);
568 * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
570 size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
571 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf
);
575 * This is a "deep" measurement of the table. To use it, |EntryType| must
576 * define SizeOfExcludingThis, and that method will be called on all live
579 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
580 size_t n
= ShallowSizeOfExcludingThis(aMallocSizeOf
);
581 for (auto iter
= ConstIter(); !iter
.Done(); iter
.Next()) {
582 n
+= (*iter
.Get()).SizeOfExcludingThis(aMallocSizeOf
);
588 * Like SizeOfExcludingThis, but includes sizeof(*this).
590 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
591 return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf
);
595 * Swap the elements in this hashtable with the elements in aOther.
597 void SwapElements(nsTHashtable
<EntryType
>& aOther
) {
598 MOZ_ASSERT_IF(this->mTable
.Ops() && aOther
.mTable
.Ops(),
599 this->mTable
.Ops() == aOther
.mTable
.Ops());
600 std::swap(this->mTable
, aOther
.mTable
);
604 * Mark the table as constant after initialization.
606 * This will prevent assertions when a read-only hash is accessed on multiple
607 * threads without synchronization.
609 void MarkImmutable() { mTable
.MarkImmutable(); }
614 static PLDHashNumber
s_HashKey(const void* aKey
);
616 static bool s_MatchEntry(const PLDHashEntryHdr
* aEntry
, const void* aKey
);
618 static void s_CopyEntry(PLDHashTable
* aTable
, const PLDHashEntryHdr
* aFrom
,
619 PLDHashEntryHdr
* aTo
);
621 static void s_ClearEntry(PLDHashTable
* aTable
, PLDHashEntryHdr
* aEntry
);
624 // copy constructor, not implemented
625 nsTHashtable(nsTHashtable
<EntryType
>& aToCopy
) = delete;
628 * Gets the table's ops.
630 static const PLDHashTableOps
* Ops();
632 // assignment operator, not implemented
633 nsTHashtable
<EntryType
>& operator=(nsTHashtable
<EntryType
>& aToEqual
) =
640 // Like PLDHashTable::MoveEntryStub, but specialized for fixed N (i.e. the size
641 // of the entries in the hashtable). Saves a memory read to figure out the size
642 // from the table and gives the compiler the opportunity to inline the memcpy.
644 // We define this outside of nsTHashtable so only one copy exists for every N,
645 // rather than separate copies for every EntryType used with nsTHashtable.
647 static void FixedSizeEntryMover(PLDHashTable
*, const PLDHashEntryHdr
* aFrom
,
648 PLDHashEntryHdr
* aTo
) {
649 memcpy(aTo
, aFrom
, N
);
652 } // namespace detail
653 } // namespace mozilla
656 // template definitions
659 template <class EntryType
>
660 nsTHashtable
<EntryType
>::nsTHashtable(nsTHashtable
<EntryType
>&& aOther
)
661 : mTable(std::move(aOther
.mTable
)) {}
663 template <class EntryType
>
664 nsTHashtable
<EntryType
>& nsTHashtable
<EntryType
>::operator=(
665 nsTHashtable
<EntryType
>&& aOther
) {
666 mTable
= std::move(aOther
.mTable
);
670 template <class EntryType
>
671 /* static */ const PLDHashTableOps
* nsTHashtable
<EntryType
>::Ops() {
672 // If this variable is a global variable, we get strange start-up failures on
673 // WindowsCrtPatch.h (see bug 1166598 comment 20). But putting it inside a
674 // function avoids that problem.
675 static const PLDHashTableOps sOps
= {
676 s_HashKey
, s_MatchEntry
,
677 EntryType::ALLOW_MEMMOVE
678 ? mozilla::detail::FixedSizeEntryMover
<sizeof(EntryType
)>
680 // Simplify hashtable clearing in case our entries are trivially
682 std::is_trivially_destructible_v
<EntryType
> ? nullptr : s_ClearEntry
,
683 // We don't use a generic initEntry hook because we want to allow
684 // initialization of data members defined in derived classes directly
685 // in the entry constructor (for example when a member can't be default
691 // static definitions
693 template <class EntryType
>
694 PLDHashNumber nsTHashtable
<EntryType
>::s_HashKey(const void* aKey
) {
695 return EntryType::HashKey(static_cast<KeyTypePointer
>(aKey
));
698 template <class EntryType
>
699 bool nsTHashtable
<EntryType
>::s_MatchEntry(const PLDHashEntryHdr
* aEntry
,
701 return (static_cast<const EntryType
*>(aEntry
))
702 ->KeyEquals(static_cast<KeyTypePointer
>(aKey
));
705 template <class EntryType
>
706 void nsTHashtable
<EntryType
>::s_CopyEntry(PLDHashTable
* aTable
,
707 const PLDHashEntryHdr
* aFrom
,
708 PLDHashEntryHdr
* aTo
) {
709 auto* fromEntry
= const_cast<std::remove_const_t
<EntryType
>*>(
710 static_cast<const EntryType
*>(aFrom
));
712 new (mozilla::KnownNotNull
, aTo
) EntryType(std::move(*fromEntry
));
714 fromEntry
->~EntryType();
717 template <class EntryType
>
718 void nsTHashtable
<EntryType
>::s_ClearEntry(PLDHashTable
* aTable
,
719 PLDHashEntryHdr
* aEntry
) {
720 static_cast<EntryType
*>(aEntry
)->~EntryType();
723 class nsCycleCollectionTraversalCallback
;
725 template <class EntryType
>
726 inline void ImplCycleCollectionUnlink(nsTHashtable
<EntryType
>& aField
) {
730 template <class EntryType
>
731 inline void ImplCycleCollectionTraverse(
732 nsCycleCollectionTraversalCallback
& aCallback
,
733 nsTHashtable
<EntryType
>& aField
, const char* aName
, uint32_t aFlags
= 0) {
734 for (auto iter
= aField
.Iter(); !iter
.Done(); iter
.Next()) {
735 EntryType
* entry
= iter
.Get();
736 ImplCycleCollectionTraverse(aCallback
, *entry
, aName
, aFlags
);
741 * For nsTHashtable with pointer entries, we can have a template specialization
742 * that layers a typed T* interface on top of a common implementation that
743 * works internally with void pointers. This arrangement saves code size and
744 * might slightly improve performance as well.
748 * We need a separate entry type class for the inheritance structure of the
749 * nsTHashtable specialization below; nsVoidPtrHashKey is simply typedefed to a
750 * specialization of nsPtrHashKey, and the formulation:
752 * class nsTHashtable<nsPtrHashKey<T>> :
753 * protected nsTHashtable<nsPtrHashKey<const void>
755 * is not going to turn out very well, since we'd wind up with an nsTHashtable
756 * instantiation that is its own base class.
760 class VoidPtrHashKey
: public nsPtrHashKey
<const void> {
761 typedef nsPtrHashKey
<const void> Base
;
764 explicit VoidPtrHashKey(const void* aKey
) : Base(aKey
) {}
767 } // namespace detail
770 * See the main nsTHashtable documentation for descriptions of this class's
773 template <typename T
>
774 class nsTHashtable
<nsPtrHashKey
<T
>>
775 : protected nsTHashtable
<::detail::VoidPtrHashKey
> {
776 typedef nsTHashtable
<::detail::VoidPtrHashKey
> Base
;
777 typedef nsPtrHashKey
<T
> EntryType
;
779 // We play games with reinterpret_cast'ing between these two classes, so
780 // try to ensure that playing said games is reasonable.
781 static_assert(sizeof(nsPtrHashKey
<T
>) == sizeof(::detail::VoidPtrHashKey
),
782 "hash keys must be the same size");
784 nsTHashtable(const nsTHashtable
& aOther
) = delete;
785 nsTHashtable
& operator=(const nsTHashtable
& aOther
) = delete;
788 nsTHashtable() = default;
789 explicit nsTHashtable(uint32_t aInitLength
) : Base(aInitLength
) {}
791 ~nsTHashtable() = default;
793 nsTHashtable(nsTHashtable
&&) = default;
797 using Base::GetGeneration
;
800 using Base::MarkImmutable
;
801 using Base::ShallowSizeOfExcludingThis
;
802 using Base::ShallowSizeOfIncludingThis
;
804 /* Wrapper functions */
805 EntryType
* GetEntry(T
* aKey
) const {
806 return reinterpret_cast<EntryType
*>(Base::GetEntry(aKey
));
809 bool Contains(T
* aKey
) const { return Base::Contains(aKey
); }
811 EntryType
* PutEntry(T
* aKey
) {
812 return reinterpret_cast<EntryType
*>(Base::PutEntry(aKey
));
815 [[nodiscard
]] EntryType
* PutEntry(T
* aKey
,
816 const mozilla::fallible_t
& aFallible
) {
817 return reinterpret_cast<EntryType
*>(Base::PutEntry(aKey
, aFallible
));
820 [[nodiscard
]] bool EnsureInserted(T
* aKey
, EntryType
** aEntry
= nullptr) {
821 return Base::EnsureInserted(
822 aKey
, reinterpret_cast<::detail::VoidPtrHashKey
**>(aEntry
));
825 void RemoveEntry(T
* aKey
) { Base::RemoveEntry(aKey
); }
827 bool EnsureRemoved(T
* aKey
) { return Base::EnsureRemoved(aKey
); }
829 void RemoveEntry(EntryType
* aEntry
) {
830 Base::RemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey
*>(aEntry
));
833 void RawRemoveEntry(EntryType
* aEntry
) {
834 Base::RawRemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey
*>(aEntry
));
838 class EntryHandle
: protected Base::EntryHandle
{
840 using Base
= nsTHashtable::Base::EntryHandle
;
842 EntryHandle(EntryHandle
&& aOther
) = default;
843 ~EntryHandle() = default;
845 EntryHandle(const EntryHandle
&) = delete;
846 EntryHandle
& operator=(const EntryHandle
&) = delete;
847 EntryHandle
& operator=(const EntryHandle
&&) = delete;
851 using Base::HasEntry
;
853 using Base::operator bool;
855 EntryType
* Entry() { return reinterpret_cast<EntryType
*>(Base::Entry()); }
859 EntryType
* OrInsert() {
868 using Base::OrRemove
;
871 friend class nsTHashtable
;
873 explicit EntryHandle(Base
&& aBase
) : Base(std::move(aBase
)) {}
877 auto WithEntryHandle(KeyType aKey
, F aFunc
)
878 -> std::invoke_result_t
<F
, EntryHandle
&&> {
879 return Base::WithEntryHandle(aKey
, [&aFunc
](auto entryHandle
) {
880 return aFunc(EntryHandle
{std::move(entryHandle
)});
885 auto WithEntryHandle(KeyType aKey
, const mozilla::fallible_t
& aFallible
,
887 -> std::invoke_result_t
<F
, mozilla::Maybe
<EntryHandle
>&&> {
888 return Base::WithEntryHandle(
889 aKey
, aFallible
, [&aFunc
](auto maybeEntryHandle
) {
890 return aFunc(maybeEntryHandle
? mozilla::Some(EntryHandle
{
891 maybeEntryHandle
.extract()})
892 : mozilla::Nothing());
897 class ConstIterator
{
899 explicit ConstIterator(nsTHashtable
* aTable
)
900 : mBaseIterator(&aTable
->mTable
) {}
901 ~ConstIterator() = default;
903 KeyType
Key() const { return Get()->GetKey(); }
905 const EntryType
* Get() const {
906 return static_cast<const EntryType
*>(mBaseIterator
.Get());
909 bool Done() const { return mBaseIterator
.Done(); }
910 void Next() { mBaseIterator
.Next(); }
912 ConstIterator() = delete;
913 ConstIterator(const ConstIterator
&) = delete;
914 ConstIterator(ConstIterator
&& aOther
) = delete;
915 ConstIterator
& operator=(const ConstIterator
&) = delete;
916 ConstIterator
& operator=(ConstIterator
&&) = delete;
919 PLDHashTable::Iterator mBaseIterator
;
922 class Iterator final
: public ConstIterator
{
924 using ConstIterator::ConstIterator
;
926 using ConstIterator::Get
;
928 EntryType
* Get() const {
929 return static_cast<EntryType
*>(this->mBaseIterator
.Get());
932 void Remove() { this->mBaseIterator
.Remove(); }
935 Iterator
Iter() { return Iterator(this); }
937 ConstIterator
ConstIter() const {
938 return ConstIterator(const_cast<nsTHashtable
*>(this));
941 using const_iterator
= ::detail::nsTHashtableEntryIterator
<const EntryType
>;
942 using iterator
= ::detail::nsTHashtableEntryIterator
<EntryType
>;
944 iterator
begin() { return iterator
{mTable
}; }
945 const_iterator
begin() const { return const_iterator
{mTable
}; }
946 const_iterator
cbegin() const { return begin(); }
948 return iterator
{mTable
, typename
iterator::EndIteratorTag
{}};
950 const_iterator
end() const {
951 return const_iterator
{mTable
, typename
const_iterator::EndIteratorTag
{}};
953 const_iterator
cend() const { return end(); }
956 return ::detail::nsTHashtableKeyRange
<nsPtrHashKey
<T
>>{mTable
};
959 void Remove(::detail::nsTHashtableKeyIterator
<EntryType
>& aIter
) {
960 aIter
.mIterator
.Remove();
963 void SwapElements(nsTHashtable
& aOther
) { Base::SwapElements(aOther
); }
966 #endif // nsTHashtable_h__