xpcom/ds/nsTHashtable.h

   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 // See the comment at the top of mfbt/HashTable.h for a comparison between
   8 // PLDHashTable and mozilla::HashTable.
   9
  10 #ifndef nsTHashtable_h__
  11 #define nsTHashtable_h__
  12
  13 #include <iterator>
  14 #include <new>
  15 #include <type_traits>
  16 #include <utility>
  17
  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"
  28
  29 template <class EntryType>
  30 class nsTHashtable;
  31
  32 namespace detail {
  33 class nsTHashtableIteratorBase {
  34  public:
  35   using EndIteratorTag = PLDHashTable::Iterator::EndIteratorTag;
  36
  37   nsTHashtableIteratorBase(nsTHashtableIteratorBase&& aOther) = default;
  38
  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));
  43   }
  44
  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());
  52     return *this;
  53   }
  54
  55   explicit nsTHashtableIteratorBase(PLDHashTable::Iterator aFrom)
  56       : mIterator{std::move(aFrom)} {}
  57
  58   explicit nsTHashtableIteratorBase(const PLDHashTable& aTable)
  59       : mIterator{&const_cast<PLDHashTable&>(aTable)} {}
  60
  61   nsTHashtableIteratorBase(const PLDHashTable& aTable, EndIteratorTag aTag)
  62       : mIterator{&const_cast<PLDHashTable&>(aTable), aTag} {}
  63
  64   bool operator==(const nsTHashtableIteratorBase& aRhs) const {
  65     return mIterator == aRhs.mIterator;
  66   }
  67   bool operator!=(const nsTHashtableIteratorBase& aRhs) const {
  68     return !(*this == aRhs);
  69   }
  70
  71  protected:
  72   PLDHashTable::Iterator mIterator;
  73 };
  74
  75 // STL-style iterators to allow the use in range-based for loops, e.g.
  76 template <typename T>
  77 class nsTHashtableEntryIterator : public nsTHashtableIteratorBase {
  78   friend class nsTHashtable<std::remove_const_t<T>>;
  79
  80  public:
  81   using iterator_category = std::forward_iterator_tag;
  82   using value_type = T;
  83   using difference_type = int32_t;
  84   using pointer = value_type*;
  85   using reference = value_type&;
  86
  87   using iterator_type = nsTHashtableEntryIterator;
  88   using const_iterator_type = nsTHashtableEntryIterator<const T>;
  89
  90   using nsTHashtableIteratorBase::nsTHashtableIteratorBase;
  91
  92   value_type* operator->() const {
  93     return static_cast<value_type*>(mIterator.Get());
  94   }
  95   value_type& operator*() const {
  96     return *static_cast<value_type*>(mIterator.Get());
  97   }
  98
  99   iterator_type& operator++() {
 100     mIterator.Next();
 101     return *this;
 102   }
 103   iterator_type operator++(int) {
 104     iterator_type it = *this;
 105     ++*this;
 106     return it;
 107   }
 108
 109   operator const_iterator_type() const {
 110     return const_iterator_type{mIterator.Clone()};
 111   }
 112 };
 113
 114 template <typename EntryType>
 115 class nsTHashtableKeyIterator : public nsTHashtableIteratorBase {
 116   friend class nsTHashtable<EntryType>;
 117
 118  public:
 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&;
 124
 125   using iterator_type = nsTHashtableKeyIterator;
 126   using const_iterator_type = nsTHashtableKeyIterator;
 127
 128   using nsTHashtableIteratorBase::nsTHashtableIteratorBase;
 129
 130   value_type* operator->() const {
 131     return &static_cast<const EntryType*>(mIterator.Get())->GetKey();
 132   }
 133   decltype(auto) operator*() const {
 134     return static_cast<const EntryType*>(mIterator.Get())->GetKey();
 135   }
 136
 137   iterator_type& operator++() {
 138     mIterator.Next();
 139     return *this;
 140   }
 141   iterator_type operator++(int) {
 142     iterator_type it = *this;
 143     ++*this;
 144     return it;
 145   }
 146 };
 147
 148 template <typename EntryType>
 149 class nsTHashtableKeyRange {
 150  public:
 151   using IteratorType = nsTHashtableKeyIterator<EntryType>;
 152   using iterator = IteratorType;
 153
 154   explicit nsTHashtableKeyRange(const PLDHashTable& aHashtable)
 155       : mHashtable{aHashtable} {}
 156
 157   auto begin() const { return IteratorType{mHashtable}; }
 158   auto end() const {
 159     return IteratorType{mHashtable, typename IteratorType::EndIteratorTag{}};
 160   }
 161   auto cbegin() const { return begin(); }
 162   auto cend() const { return end(); }
 163
 164   uint32_t Count() const { return mHashtable.EntryCount(); }
 165
 166  private:
 167   const PLDHashTable& mHashtable;
 168 };
 169
 170 template <typename EntryType>
 171 auto RangeSize(const ::detail::nsTHashtableKeyRange<EntryType>& aRange) {
 172   return aRange.Count();
 173 }
 174
 175 }  // namespace detail
 176
 177 /**
 178  * a base class for templated hashtables.
 179  *
 180  * Clients will rarely need to use this class directly. Check the derived
 181  * classes first, to see if they will meet your needs.
 182  *
 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
 187  *   PLDHashTable code.
 188  *<pre>   class EntryType : public PLDHashEntryHdr
 189  *   {
 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;
 198  *
 199  *     EntryType(KeyTypePointer aKey);
 200  *
 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
 205  *
 206  *     // the destructor must be defined... or you will cause link errors!
 207  *     ~EntryType();
 208  *
 209  *     // KeyEquals(): does this entry match this key?
 210  *     bool KeyEquals(KeyTypePointer aKey) const;
 211  *
 212  *     // KeyToPointer(): Convert KeyType to KeyTypePointer
 213  *     static KeyTypePointer KeyToPointer(KeyType aKey);
 214  *
 215  *     // HashKey(): calculate the hash number
 216  *     static PLDHashNumber HashKey(KeyTypePointer aKey);
 217  *
 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 };
 221  *   }</pre>
 222  *
 223  * @see nsInterfaceHashtable
 224  * @see nsClassHashtable
 225  * @see nsTHashMap
 226  * @author "Benjamin Smedberg <bsmedberg@covad.net>"
 227  */
 228
 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");
 234
 235  public:
 236   // Separate constructors instead of default aInitLength parameter since
 237   // otherwise the default no-arg constructor isn't found.
 238   nsTHashtable()
 239       : mTable(Ops(), sizeof(EntryType), PLDHashTable::kDefaultInitialLength) {}
 240   explicit nsTHashtable(uint32_t aInitLength)
 241       : mTable(Ops(), sizeof(EntryType), aInitLength) {}
 242
 243   /**
 244    * destructor, cleans up and deallocates
 245    */
 246   ~nsTHashtable() = default;
 247
 248   nsTHashtable(nsTHashtable<EntryType>&& aOther);
 249   nsTHashtable<EntryType>& operator=(nsTHashtable<EntryType>&& aOther);
 250
 251   nsTHashtable(const nsTHashtable<EntryType>&) = delete;
 252   nsTHashtable& operator=(const nsTHashtable<EntryType>&) = delete;
 253
 254   /**
 255    * Return the generation number for the table. This increments whenever
 256    * the table data items are moved.
 257    */
 258   uint32_t GetGeneration() const { return mTable.Generation(); }
 259
 260   /**
 261    * KeyType is typedef'ed for ease of use.
 262    */
 263   typedef typename EntryType::KeyType KeyType;
 264
 265   /**
 266    * KeyTypePointer is typedef'ed for ease of use.
 267    */
 268   typedef typename EntryType::KeyTypePointer KeyTypePointer;
 269
 270   /**
 271    * Return the number of entries in the table.
 272    * @return    number of entries
 273    */
 274   uint32_t Count() const { return mTable.EntryCount(); }
 275
 276   /**
 277    * Return true if the hashtable is empty.
 278    */
 279   bool IsEmpty() const { return Count() == 0; }
 280
 281   /**
 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
 285    *            key doesn't exist
 286    */
 287   EntryType* GetEntry(KeyType aKey) const {
 288     return static_cast<EntryType*>(
 289         mTable.Search(EntryType::KeyToPointer(aKey)));
 290   }
 291
 292   /**
 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
 296    */
 297   bool Contains(KeyType aKey) const { return !!GetEntry(aKey); }
 298
 299   /**
 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
 303    */
 304   EntryType* PutEntry(KeyType aKey) {
 305     // Infallible WithEntryHandle.
 306     return WithEntryHandle(
 307         aKey, [](auto entryHandle) { return entryHandle.OrInsert(); });
 308   }
 309
 310   /**
 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
 314    *            be allocated
 315    */
 316   [[nodiscard]] EntryType* PutEntry(KeyType aKey, const fallible_t& aFallible) {
 317     return WithEntryHandle(aKey, aFallible, [](auto maybeEntryHandle) {
 318       return maybeEntryHandle ? maybeEntryHandle->OrInsert() : nullptr;
 319     });
 320   }
 321
 322   /**
 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
 327    * found or created
 328    * @return    true if a new entry was created, or false if an existing entry
 329    *            was found
 330    */
 331   [[nodiscard]] bool EnsureInserted(KeyType aKey,
 332                                     EntryType** aEntry = nullptr) {
 333     auto oldCount = Count();
 334     EntryType* entry = PutEntry(aKey);
 335     if (aEntry) {
 336       *aEntry = entry;
 337     }
 338     return oldCount != Count();
 339   }
 340
 341   /**
 342    * Remove the entry associated with a key.
 343    * @param     aKey of the entry to remove
 344    */
 345   void RemoveEntry(KeyType aKey) {
 346     mTable.Remove(EntryType::KeyToPointer(aKey));
 347   }
 348
 349   /**
 350    * Lookup the entry associated with aKey and remove it if found, otherwise
 351    * do nothing.
 352    * @param     aKey of the entry to remove
 353    * @return    true if an entry was found and removed, or false if no entry
 354    *            was found for aKey
 355    */
 356   bool EnsureRemoved(KeyType aKey) {
 357     auto* entry = GetEntry(aKey);
 358     if (entry) {
 359       RemoveEntry(entry);
 360       return true;
 361     }
 362     return false;
 363   }
 364
 365   /**
 366    * Remove the entry associated with a key.
 367    * @param aEntry   the entry-pointer to remove (obtained from GetEntry)
 368    */
 369   void RemoveEntry(EntryType* aEntry) { mTable.RemoveEntry(aEntry); }
 370
 371   /**
 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)
 377    */
 378   void RawRemoveEntry(EntryType* aEntry) { mTable.RawRemove(aEntry); }
 379
 380  protected:
 381   class EntryHandle {
 382    public:
 383     EntryHandle(EntryHandle&& aOther) = default;
 384     ~EntryHandle() = default;
 385
 386     EntryHandle(const EntryHandle&) = delete;
 387     EntryHandle& operator=(const EntryHandle&) = delete;
 388     EntryHandle& operator=(const EntryHandle&&) = delete;
 389
 390     KeyType Key() const { return mKey; }
 391
 392     bool HasEntry() const { return mEntryHandle.HasEntry(); }
 393
 394     explicit operator bool() const { return mEntryHandle.operator bool(); }
 395
 396     EntryType* Entry() { return static_cast<EntryType*>(mEntryHandle.Entry()); }
 397
 398     void Insert() { InsertInternal(); }
 399
 400     EntryType* OrInsert() {
 401       if (!HasEntry()) {
 402         Insert();
 403       }
 404       return Entry();
 405     }
 406
 407     void Remove() { mEntryHandle.Remove(); }
 408
 409     void OrRemove() { mEntryHandle.OrRemove(); }
 410
 411    protected:
 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)...);
 418       });
 419     }
 420
 421    private:
 422     friend class nsTHashtable;
 423
 424     EntryHandle(KeyType aKey, PLDHashTable::EntryHandle&& aEntryHandle)
 425         : mKey(aKey), mEntryHandle(std::move(aEntryHandle)) {}
 426
 427     KeyType mKey;
 428     PLDHashTable::EntryHandle mEntryHandle;
 429   };
 430
 431   template <class F>
 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)});
 439         });
 440   }
 441
 442   template <class F>
 443   auto WithEntryHandle(KeyType aKey, const mozilla::fallible_t& aFallible,
 444                        F&& aFunc)
 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)(
 450               maybeEntryHandle
 451                   ? mozilla::Some(EntryHandle{aKey, maybeEntryHandle.extract()})
 452                   : mozilla::Nothing());
 453         });
 454   }
 455
 456  public:
 457   class ConstIterator {
 458    public:
 459     explicit ConstIterator(nsTHashtable* aTable)
 460         : mBaseIterator(&aTable->mTable) {}
 461     ~ConstIterator() = default;
 462
 463     KeyType Key() const { return Get()->GetKey(); }
 464
 465     const EntryType* Get() const {
 466       return static_cast<const EntryType*>(mBaseIterator.Get());
 467     }
 468
 469     bool Done() const { return mBaseIterator.Done(); }
 470     void Next() { mBaseIterator.Next(); }
 471
 472     ConstIterator() = delete;
 473     ConstIterator(const ConstIterator&) = delete;
 474     ConstIterator(ConstIterator&& aOther) = delete;
 475     ConstIterator& operator=(const ConstIterator&) = delete;
 476     ConstIterator& operator=(ConstIterator&&) = delete;
 477
 478    protected:
 479     PLDHashTable::Iterator mBaseIterator;
 480   };
 481
 482   // This is an iterator that also allows entry removal. Example usage:
 483   //
 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 ...
 488   //   }
 489   //
 490   class Iterator final : public ConstIterator {
 491    public:
 492     using ConstIterator::ConstIterator;
 493
 494     using ConstIterator::Get;
 495
 496     EntryType* Get() const {
 497       return static_cast<EntryType*>(this->mBaseIterator.Get());
 498     }
 499
 500     void Remove() { this->mBaseIterator.Remove(); }
 501   };
 502
 503   Iterator Iter() { return Iterator(this); }
 504
 505   ConstIterator ConstIter() const {
 506     return ConstIterator(const_cast<nsTHashtable*>(this));
 507   }
 508
 509   using const_iterator = ::detail::nsTHashtableEntryIterator<const EntryType>;
 510   using iterator = ::detail::nsTHashtableEntryIterator<EntryType>;
 511
 512   iterator begin() { return iterator{mTable}; }
 513   const_iterator begin() const { return const_iterator{mTable}; }
 514   const_iterator cbegin() const { return begin(); }
 515   iterator end() {
 516     return iterator{mTable, typename iterator::EndIteratorTag{}};
 517   }
 518   const_iterator end() const {
 519     return const_iterator{mTable, typename const_iterator::EndIteratorTag{}};
 520   }
 521   const_iterator cend() const { return end(); }
 522
 523   void Remove(const_iterator& aIter) { aIter.mIterator.Remove(); }
 524
 525   /**
 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.
 530    */
 531   auto Keys() const {
 532     return ::detail::nsTHashtableKeyRange<EntryType>{mTable};
 533   }
 534
 535   /**
 536    * Remove an entry from a key range, specified via a key iterator, e.g.
 537    *
 538    * for (auto it = hash.Keys().begin(), end = hash.Keys().end();
 539    *      it != end; * ++it) {
 540    *   if (*it > 42) { hash.Remove(it); }
 541    * }
 542    */
 543   void Remove(::detail::nsTHashtableKeyIterator<EntryType>& aIter) {
 544     aIter.mIterator.Remove();
 545   }
 546
 547   /**
 548    * Remove all entries, return hashtable to "pristine" state. It's
 549    * conceptually the same as calling the destructor and then re-calling the
 550    * constructor.
 551    */
 552   void Clear() { mTable.Clear(); }
 553
 554   /**
 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.
 559    *
 560    * @param     aMallocSizeOf the function used to measure heap-allocated blocks
 561    * @return    the measured shallow size of the table
 562    */
 563   size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const {
 564     return mTable.ShallowSizeOfExcludingThis(aMallocSizeOf);
 565   }
 566
 567   /**
 568    * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
 569    */
 570   size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const {
 571     return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
 572   }
 573
 574   /**
 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
 577    * entries.
 578    */
 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);
 583     }
 584     return n;
 585   }
 586
 587   /**
 588    * Like SizeOfExcludingThis, but includes sizeof(*this).
 589    */
 590   size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const {
 591     return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
 592   }
 593
 594   /**
 595    * Swap the elements in this hashtable with the elements in aOther.
 596    */
 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);
 601   }
 602
 603   /**
 604    * Mark the table as constant after initialization.
 605    *
 606    * This will prevent assertions when a read-only hash is accessed on multiple
 607    * threads without synchronization.
 608    */
 609   void MarkImmutable() { mTable.MarkImmutable(); }
 610
 611  protected:
 612   PLDHashTable mTable;
 613
 614   static PLDHashNumber s_HashKey(const void* aKey);
 615
 616   static bool s_MatchEntry(const PLDHashEntryHdr* aEntry, const void* aKey);
 617
 618   static void s_CopyEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom,
 619                           PLDHashEntryHdr* aTo);
 620
 621   static void s_ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
 622
 623  private:
 624   // copy constructor, not implemented
 625   nsTHashtable(nsTHashtable<EntryType>& aToCopy) = delete;
 626
 627   /**
 628    * Gets the table's ops.
 629    */
 630   static const PLDHashTableOps* Ops();
 631
 632   // assignment operator, not implemented
 633   nsTHashtable<EntryType>& operator=(nsTHashtable<EntryType>& aToEqual) =
 634       delete;
 635 };
 636
 637 namespace mozilla {
 638 namespace detail {
 639
 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.
 643 //
 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.
 646 template <size_t N>
 647 static void FixedSizeEntryMover(PLDHashTable*, const PLDHashEntryHdr* aFrom,
 648                                 PLDHashEntryHdr* aTo) {
 649   memcpy(aTo, aFrom, N);
 650 }
 651
 652 }  // namespace detail
 653 }  // namespace mozilla
 654
 655 //
 656 // template definitions
 657 //
 658
 659 template <class EntryType>
 660 nsTHashtable<EntryType>::nsTHashtable(nsTHashtable<EntryType>&& aOther)
 661     : mTable(std::move(aOther.mTable)) {}
 662
 663 template <class EntryType>
 664 nsTHashtable<EntryType>& nsTHashtable<EntryType>::operator=(
 665     nsTHashtable<EntryType>&& aOther) {
 666   mTable = std::move(aOther.mTable);
 667   return *this;
 668 }
 669
 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)>
 679           : s_CopyEntry,
 680       // Simplify hashtable clearing in case our entries are trivially
 681       // destructible.
 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
 686       // constructed).
 687       nullptr};
 688   return &sOps;
 689 }
 690
 691 // static definitions
 692
 693 template <class EntryType>
 694 PLDHashNumber nsTHashtable<EntryType>::s_HashKey(const void* aKey) {
 695   return EntryType::HashKey(static_cast<KeyTypePointer>(aKey));
 696 }
 697
 698 template <class EntryType>
 699 bool nsTHashtable<EntryType>::s_MatchEntry(const PLDHashEntryHdr* aEntry,
 700                                            const void* aKey) {
 701   return (static_cast<const EntryType*>(aEntry))
 702       ->KeyEquals(static_cast<KeyTypePointer>(aKey));
 703 }
 704
 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));
 711
 712   new (mozilla::KnownNotNull, aTo) EntryType(std::move(*fromEntry));
 713
 714   fromEntry->~EntryType();
 715 }
 716
 717 template <class EntryType>
 718 void nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable* aTable,
 719                                            PLDHashEntryHdr* aEntry) {
 720   static_cast<EntryType*>(aEntry)->~EntryType();
 721 }
 722
 723 class nsCycleCollectionTraversalCallback;
 724
 725 template <class EntryType>
 726 inline void ImplCycleCollectionUnlink(nsTHashtable<EntryType>& aField) {
 727   aField.Clear();
 728 }
 729
 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);
 737   }
 738 }
 739
 740 /**
 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.
 745  */
 746
 747 /**
 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:
 751  *
 752  * class nsTHashtable<nsPtrHashKey<T>> :
 753  *   protected nsTHashtable<nsPtrHashKey<const void>
 754  *
 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.
 757  */
 758 namespace detail {
 759
 760 class VoidPtrHashKey : public nsPtrHashKey<const void> {
 761   typedef nsPtrHashKey<const void> Base;
 762
 763  public:
 764   explicit VoidPtrHashKey(const void* aKey) : Base(aKey) {}
 765 };
 766
 767 }  // namespace detail
 768
 769 /**
 770  * See the main nsTHashtable documentation for descriptions of this class's
 771  * methods.
 772  */
 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;
 778
 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");
 783
 784   nsTHashtable(const nsTHashtable& aOther) = delete;
 785   nsTHashtable& operator=(const nsTHashtable& aOther) = delete;
 786
 787  public:
 788   nsTHashtable() = default;
 789   explicit nsTHashtable(uint32_t aInitLength) : Base(aInitLength) {}
 790
 791   ~nsTHashtable() = default;
 792
 793   nsTHashtable(nsTHashtable&&) = default;
 794
 795   using Base::Clear;
 796   using Base::Count;
 797   using Base::GetGeneration;
 798   using Base::IsEmpty;
 799
 800   using Base::MarkImmutable;
 801   using Base::ShallowSizeOfExcludingThis;
 802   using Base::ShallowSizeOfIncludingThis;
 803
 804   /* Wrapper functions */
 805   EntryType* GetEntry(T* aKey) const {
 806     return reinterpret_cast<EntryType*>(Base::GetEntry(aKey));
 807   }
 808
 809   bool Contains(T* aKey) const { return Base::Contains(aKey); }
 810
 811   EntryType* PutEntry(T* aKey) {
 812     return reinterpret_cast<EntryType*>(Base::PutEntry(aKey));
 813   }
 814
 815   [[nodiscard]] EntryType* PutEntry(T* aKey,
 816                                     const mozilla::fallible_t& aFallible) {
 817     return reinterpret_cast<EntryType*>(Base::PutEntry(aKey, aFallible));
 818   }
 819
 820   [[nodiscard]] bool EnsureInserted(T* aKey, EntryType** aEntry = nullptr) {
 821     return Base::EnsureInserted(
 822         aKey, reinterpret_cast<::detail::VoidPtrHashKey**>(aEntry));
 823   }
 824
 825   void RemoveEntry(T* aKey) { Base::RemoveEntry(aKey); }
 826
 827   bool EnsureRemoved(T* aKey) { return Base::EnsureRemoved(aKey); }
 828
 829   void RemoveEntry(EntryType* aEntry) {
 830     Base::RemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
 831   }
 832
 833   void RawRemoveEntry(EntryType* aEntry) {
 834     Base::RawRemoveEntry(reinterpret_cast<::detail::VoidPtrHashKey*>(aEntry));
 835   }
 836
 837  protected:
 838   class EntryHandle : protected Base::EntryHandle {
 839    public:
 840     using Base = nsTHashtable::Base::EntryHandle;
 841
 842     EntryHandle(EntryHandle&& aOther) = default;
 843     ~EntryHandle() = default;
 844
 845     EntryHandle(const EntryHandle&) = delete;
 846     EntryHandle& operator=(const EntryHandle&) = delete;
 847     EntryHandle& operator=(const EntryHandle&&) = delete;
 848
 849     using Base::Key;
 850
 851     using Base::HasEntry;
 852
 853     using Base::operator bool;
 854
 855     EntryType* Entry() { return reinterpret_cast<EntryType*>(Base::Entry()); }
 856
 857     using Base::Insert;
 858
 859     EntryType* OrInsert() {
 860       if (!HasEntry()) {
 861         Insert();
 862       }
 863       return Entry();
 864     }
 865
 866     using Base::Remove;
 867
 868     using Base::OrRemove;
 869
 870    private:
 871     friend class nsTHashtable;
 872
 873     explicit EntryHandle(Base&& aBase) : Base(std::move(aBase)) {}
 874   };
 875
 876   template <class F>
 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)});
 881     });
 882   }
 883
 884   template <class F>
 885   auto WithEntryHandle(KeyType aKey, const mozilla::fallible_t& aFallible,
 886                        F aFunc)
 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());
 893         });
 894   }
 895
 896  public:
 897   class ConstIterator {
 898    public:
 899     explicit ConstIterator(nsTHashtable* aTable)
 900         : mBaseIterator(&aTable->mTable) {}
 901     ~ConstIterator() = default;
 902
 903     KeyType Key() const { return Get()->GetKey(); }
 904
 905     const EntryType* Get() const {
 906       return static_cast<const EntryType*>(mBaseIterator.Get());
 907     }
 908
 909     bool Done() const { return mBaseIterator.Done(); }
 910     void Next() { mBaseIterator.Next(); }
 911
 912     ConstIterator() = delete;
 913     ConstIterator(const ConstIterator&) = delete;
 914     ConstIterator(ConstIterator&& aOther) = delete;
 915     ConstIterator& operator=(const ConstIterator&) = delete;
 916     ConstIterator& operator=(ConstIterator&&) = delete;
 917
 918    protected:
 919     PLDHashTable::Iterator mBaseIterator;
 920   };
 921
 922   class Iterator final : public ConstIterator {
 923    public:
 924     using ConstIterator::ConstIterator;
 925
 926     using ConstIterator::Get;
 927
 928     EntryType* Get() const {
 929       return static_cast<EntryType*>(this->mBaseIterator.Get());
 930     }
 931
 932     void Remove() { this->mBaseIterator.Remove(); }
 933   };
 934
 935   Iterator Iter() { return Iterator(this); }
 936
 937   ConstIterator ConstIter() const {
 938     return ConstIterator(const_cast<nsTHashtable*>(this));
 939   }
 940
 941   using const_iterator = ::detail::nsTHashtableEntryIterator<const EntryType>;
 942   using iterator = ::detail::nsTHashtableEntryIterator<EntryType>;
 943
 944   iterator begin() { return iterator{mTable}; }
 945   const_iterator begin() const { return const_iterator{mTable}; }
 946   const_iterator cbegin() const { return begin(); }
 947   iterator end() {
 948     return iterator{mTable, typename iterator::EndIteratorTag{}};
 949   }
 950   const_iterator end() const {
 951     return const_iterator{mTable, typename const_iterator::EndIteratorTag{}};
 952   }
 953   const_iterator cend() const { return end(); }
 954
 955   auto Keys() const {
 956     return ::detail::nsTHashtableKeyRange<nsPtrHashKey<T>>{mTable};
 957   }
 958
 959   void Remove(::detail::nsTHashtableKeyIterator<EntryType>& aIter) {
 960     aIter.mIterator.Remove();
 961   }
 962
 963   void SwapElements(nsTHashtable& aOther) { Base::SwapElements(aOther); }
 964 };
 965
 966 #endif  // nsTHashtable_h__