Bug 1478879 - Introduce Iterator and ModIterator in HashTable.h. r=luke
authorNicholas Nethercote <nnethercote@mozilla.com>
Fri, 27 Jul 2018 12:17:37 +1000
changeset 484931 1e45ce266b665543f4388b96cd2a2ccc15359bda
parent 484930 591d08c5c22b1286579a216f0dc2c462cb5679fc
child 484932 2c3b5f4eda625adf917db7402bc1d655d1c1e3bc
push id9719
push userffxbld-merge
push dateFri, 24 Aug 2018 17:49:46 +0000
treeherdermozilla-beta@719ec98fba77 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs1478879
milestone63.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1478879 - Introduce Iterator and ModIterator in HashTable.h. r=luke These basically duplicate the existing Range and Enum classes, but use more familiar terminology, similar to the iterators we have for PLDHashTable/nsTHashtable: - Hash{Set,Map}::all() Hash{Set,Map}::iter() - Enum constructor Hash{Set,Map}::modIter() - Range::front() Iterator::get() - Range::popFront() Iterator::next() - Range::empty() Iterator::done() - Enum::mutableFront() ModIterator::getMutable() - Enum::removeFront() ModIterator::remove() - Enum::rekeyFront() ModIterator::rekey() The next patch will reduce the amount of code duplication.
mfbt/HashTable.h
--- a/mfbt/HashTable.h
+++ b/mfbt/HashTable.h
@@ -223,42 +223,46 @@ public:
                                   ValueInput&& aValue)
   {
     return mImpl.relookupOrAdd(aPtr,
                                aKey,
                                std::forward<KeyInput>(aKey),
                                std::forward<ValueInput>(aValue));
   }
 
-  // |all()| returns a Range containing |count()| elements. E.g.:
+  // |iter()| returns an Iterator:
   //
-  //   using HM = HashMap<int,char>;
-  //   HM h;
-  //   for (HM::Range r = h.all(); !r.empty(); r.popFront()) {
-  //     char c = r.front().value();
+  //   HashMap<int, char> h;
+  //   for (auto iter = h.iter(); !iter.done(); iter.next()) {
+  //     char c = iter.get().value();
   //   }
   //
-  // Also see the definition of Range in HashTable above (with T = Entry).
-  using Range = typename Impl::Range;
-  Range all() const { return mImpl.all(); }
+  // Also see the definition of Iterator in HashTable above (with T = Entry).
+  using Iterator = typename Impl::Iterator;
+  Iterator iter() const { return mImpl.iter(); }
 
-  // Typedef for the enumeration class. An Enum may be used to examine and
-  // remove table entries:
+  // |modIter()| returns a ModIterator:
   //
-  //   using HM = HashMap<int,char>;
-  //   HM s;
-  //   for (HM::Enum e(s); !e.empty(); e.popFront()) {
-  //     if (e.front().value() == 'l') {
-  //       e.removeFront();
+  //   HashMap<int, char> h;
+  //   for (auto iter = h.modIter(); !iter.done(); iter.next()) {
+  //     if (iter.get().value() == 'l') {
+  //       iter.remove();
   //     }
   //   }
   //
-  // Table resize may occur in Enum's destructor. Also see the definition of
-  // Enum in HashTable above (with T = Entry).
+  // Table resize may occur in ModIterator's destructor. Also see the
+  // definition of ModIterator in HashTable above (with T = Entry).
+  using ModIterator = typename Impl::ModIterator;
+  ModIterator modIter() { return mImpl.modIter(); }
+
+  // These are similar to Iterator/ModIterator/iter(), but use less common
+  // terminology.
+  using Range = typename Impl::Range;
   using Enum = typename Impl::Enum;
+  Range all() const { return mImpl.all(); }
 
   // Remove all entries. This does not shrink the table. For that consider
   // using the finish() method.
   void clear() { mImpl.clear(); }
 
   // Remove all entries. Unlike clear() this method tries to shrink the table.
   // Unlike finish() it does not require the map to be initialized again.
   void clearAndShrink() { mImpl.clearAndShrink(); }
@@ -512,42 +516,46 @@ public:
   }
 
   template<typename U>
   MOZ_MUST_USE bool relookupOrAdd(AddPtr& aPtr, const Lookup& aLookup, U&& aU)
   {
     return mImpl.relookupOrAdd(aPtr, aLookup, std::forward<U>(aU));
   }
 
-  // |all()| returns a Range containing |count()| elements:
+  // |iter()| returns an Iterator:
   //
-  //   using HS = HashSet<int>;
-  //   HS h;
-  //   for (HS::Range r = h.all(); !r.empty(); r.popFront()) {
-  //     int i = r.front();
+  //   HashSet<int> h;
+  //   for (auto iter = h.iter(); !iter.done(); iter.next()) {
+  //     int i = iter.get();
   //   }
   //
-  // Also see the definition of Range in HashTable above.
-  using Range = typename Impl::Range;
-  Range all() const { return mImpl.all(); }
+  // Also see the definition of Iterator in HashTable above.
+  typedef typename Impl::Iterator Iterator;
+  Iterator iter() const { return mImpl.iter(); }
 
-  // Typedef for the enumeration class. An Enum may be used to examine and
-  // remove table entries:
+  // |modIter()| returns a ModIterator:
   //
-  //   using HS = HashSet<int>;
-  //   HS s;
-  //   for (HS::Enum e(s); !e.empty(); e.popFront()) {
-  //     if (e.front() == 42) {
-  //       e.removeFront();
+  //   HashSet<int> h;
+  //   for (auto iter = h.modIter(); !iter.done(); iter.next()) {
+  //     if (iter.get() == 42) {
+  //       iter.remove();
   //     }
   //   }
   //
-  // Table resize may occur in Enum's destructor. Also see the definition of
-  // Enum in HashTable above.
+  // Table resize may occur in ModIterator's destructor. Also see the
+  // definition of ModIterator in HashTable above.
+  typedef typename Impl::ModIterator ModIterator;
+  ModIterator modIter() { return mImpl.modIter(); }
+
+  // These are similar to Iterator/ModIterator/iter(), but use different
+  // terminology.
+  using Range = typename Impl::Range;
   using Enum = typename Impl::Enum;
+  Range all() const { return mImpl.all(); }
 
   // Remove all entries. This does not shrink the table. For that consider
   // using the finish() method.
   void clear() { mImpl.clear(); }
 
   // Remove all entries. Unlike clear() this method tries to shrink the table.
   // Unlike finish() it does not require the set to be initialized again.
   void clearAndShrink() { mImpl.clearAndShrink(); }
@@ -1190,20 +1198,177 @@ public:
 
   public:
     AddPtr()
       : mKeyHash(0)
     {
     }
   };
 
-  // A collection of hash table entries. The collection is enumerated by
-  // calling |front()| followed by |popFront()| as long as |!empty()|. As
-  // with Ptr/AddPtr, Range objects must not be used after any mutating hash
-  // table operation unless the |generation()| is tested.
+  // A hash table iterator that (mostly) doesn't allow table modifications.
+  // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
+  // hash table operation unless the |generation()| is tested.
+  class Iterator
+  {
+  protected:
+    friend class HashTable;
+
+    explicit Iterator(const HashTable& aTable)
+      : mCur(aTable.mTable)
+      , mEnd(aTable.mTable + aTable.capacity())
+#ifdef DEBUG
+      , mTable(aTable)
+      , mMutationCount(aTable.mMutationCount)
+      , mGeneration(aTable.generation())
+      , mValidEntry(true)
+#endif
+    {
+      while (mCur < mEnd && !mCur->isLive()) {
+        ++mCur;
+      }
+    }
+
+    Entry* mCur;
+    Entry* mEnd;
+#ifdef DEBUG
+    const HashTable& mTable;
+    uint64_t mMutationCount;
+    Generation mGeneration;
+    bool mValidEntry;
+#endif
+
+  public:
+    bool done() const
+    {
+#ifdef DEBUG
+      MOZ_ASSERT(mGeneration == mTable.generation());
+      MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
+#endif
+      return mCur == mEnd;
+    }
+
+    T& get() const
+    {
+      MOZ_ASSERT(!done());
+#ifdef DEBUG
+      MOZ_ASSERT(mValidEntry);
+      MOZ_ASSERT(mGeneration == mTable.generation());
+      MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
+#endif
+      return mCur->get();
+    }
+
+    void next()
+    {
+      MOZ_ASSERT(!done());
+#ifdef DEBUG
+      MOZ_ASSERT(mGeneration == mTable.generation());
+      MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
+#endif
+      while (++mCur < mEnd && !mCur->isLive()) {
+        continue;
+      }
+#ifdef DEBUG
+      mValidEntry = true;
+#endif
+    }
+  };
+
+  // A hash table iterator that permits modification, removal and rekeying.
+  // Since rehashing when elements were removed during enumeration would be
+  // bad, it is postponed until the ModIterator is destructed. Since the
+  // ModIterator's destructor touches the hash table, the user must ensure
+  // that the hash table is still alive when the destructor runs.
+  class ModIterator : public Iterator
+  {
+    friend class HashTable;
+
+    HashTable& mTable;
+    bool mRekeyed;
+    bool mRemoved;
+
+    // ModIterator is movable but not copyable.
+    ModIterator(const ModIterator&) = delete;
+    void operator=(const ModIterator&) = delete;
+
+  protected:
+    explicit ModIterator(HashTable& aTable)
+      : Iterator(aTable)
+      , mTable(aTable)
+      , mRekeyed(false)
+      , mRemoved(false)
+    {
+    }
+
+  public:
+    MOZ_IMPLICIT ModIterator(ModIterator&& aOther)
+      : Iterator(aOther)
+      , mTable(aOther.mTable)
+      , mRekeyed(aOther.mRekeyed)
+      , mRemoved(aOther.mRemoved)
+    {
+      aOther.mRekeyed = false;
+      aOther.mRemoved = false;
+    }
+
+    // Removes the current element from the table, leaving |get()|
+    // invalid until the next call to |next()|.
+    void remove()
+    {
+      mTable.remove(*this->mCur);
+      mRemoved = true;
+#ifdef DEBUG
+      this->mValidEntry = false;
+      this->mMutationCount = mTable.mMutationCount;
+#endif
+    }
+
+    NonConstT& getMutable()
+    {
+      MOZ_ASSERT(!this->done());
+#ifdef DEBUG
+      MOZ_ASSERT(this->mValidEntry);
+      MOZ_ASSERT(this->mGeneration == this->Iterator::mTable.generation());
+      MOZ_ASSERT(this->mMutationCount == this->Iterator::mTable.mMutationCount);
+#endif
+      return this->mCur->getMutable();
+    }
+
+    // Removes the current element and re-inserts it into the table with
+    // a new key at the new Lookup position.  |get()| is invalid after
+    // this operation until the next call to |next()|.
+    void rekey(const Lookup& l, const Key& k)
+    {
+      MOZ_ASSERT(&k != &HashPolicy::getKey(this->mCur->get()));
+      Ptr p(*this->mCur, mTable);
+      mTable.rekeyWithoutRehash(p, l, k);
+      mRekeyed = true;
+#ifdef DEBUG
+      this->mValidEntry = false;
+      this->mMutationCount = mTable.mMutationCount;
+#endif
+    }
+
+    void rekey(const Key& k) { rekey(k, k); }
+
+    // Potentially rehashes the table.
+    ~ModIterator()
+    {
+      if (mRekeyed) {
+        mTable.mGen++;
+        mTable.checkOverRemoved();
+      }
+
+      if (mRemoved) {
+        mTable.compactIfUnderloaded();
+      }
+    }
+  };
+
+  // Range is similar to Iterator, but uses different terminology.
   class Range
   {
   protected:
     friend class HashTable;
 
     Range(const HashTable& aTable, Entry* aCur, Entry* aEnd)
       : mCur(aCur)
       , mEnd(aEnd)
@@ -1260,21 +1425,17 @@ public:
         continue;
       }
 #ifdef DEBUG
       mValidEntry = true;
 #endif
     }
   };
 
-  // A Range whose lifetime delimits a mutating enumeration of a hash table.
-  // Since rehashing when elements were removed during enumeration would be
-  // bad, it is postponed until the Enum is destructed.  Since the Enum's
-  // destructor touches the hash table, the user must ensure that the hash
-  // table is still alive when the destructor runs.
+  // Enum is similar to ModIterator, but uses different terminology.
   class Enum : public Range
   {
     friend class HashTable;
 
     HashTable& mTable;
     bool mRekeyed;
     bool mRemoved;
 
@@ -1297,25 +1458,16 @@ public:
       , mTable(aOther.mTable)
       , mRekeyed(aOther.mRekeyed)
       , mRemoved(aOther.mRemoved)
     {
       aOther.mRekeyed = false;
       aOther.mRemoved = false;
     }
 
-    // Removes the |front()| element from the table, leaving |front()|
-    // invalid until the next call to |popFront()|. For example:
-    //
-    //   HashSet<int> s;
-    //   for (HashSet<int>::Enum e(s); !e.empty(); e.popFront()) {
-    //     if (e.front() == 42) {
-    //       e.removeFront();
-    //     }
-    //   }
     void removeFront()
     {
       mTable.remove(*this->mCur);
       mRemoved = true;
 #ifdef DEBUG
       this->mValidEntry = false;
       this->mMutationCount = mTable.mMutationCount;
 #endif
@@ -1327,34 +1479,30 @@ public:
 #ifdef DEBUG
       MOZ_ASSERT(this->mValidEntry);
       MOZ_ASSERT(this->mGeneration == this->Range::mTable.generation());
       MOZ_ASSERT(this->mMutationCount == this->Range::mTable.mMutationCount);
 #endif
       return this->mCur->getMutable();
     }
 
-    // Removes the |front()| element and re-inserts it into the table with
-    // a new key at the new Lookup position.  |front()| is invalid after
-    // this operation until the next call to |popFront()|.
     void rekeyFront(const Lookup& aLookup, const Key& aKey)
     {
       MOZ_ASSERT(&aKey != &HashPolicy::getKey(this->mCur->get()));
       Ptr p(*this->mCur, mTable);
       mTable.rekeyWithoutRehash(p, aLookup, aKey);
       mRekeyed = true;
 #ifdef DEBUG
       this->mValidEntry = false;
       this->mMutationCount = mTable.mMutationCount;
 #endif
     }
 
     void rekeyFront(const Key& aKey) { rekeyFront(aKey, aKey); }
 
-    // Potentially rehashes the table.
     ~Enum()
     {
       if (mRekeyed) {
         mTable.mGen++;
         mTable.checkOverRemoved();
       }
 
       if (mRemoved) {
@@ -1949,16 +2097,28 @@ public:
     mGen++;
     mEntryCount = 0;
     mRemovedCount = 0;
 #ifdef DEBUG
     mMutationCount++;
 #endif
   }
 
+  Iterator iter() const
+  {
+    MOZ_ASSERT(mTable);
+    return Iterator(*this);
+  }
+
+  ModIterator modIter()
+  {
+    MOZ_ASSERT(mTable);
+    return ModIterator(*this);
+  }
+
   Range all() const
   {
     MOZ_ASSERT(mTable);
     return Range(*this, mTable, mTable + capacity());
   }
 
   bool empty() const
   {