Bug 722946 - Add method to HashTable::Enum for inline rekeying; r=luke
authorTerrence Cole <terrence@mozilla.com>
Wed, 14 Mar 2012 13:48:59 -0700
changeset 89496 c9024bcb8da0f79cfcefa887df1c52f37865f922
parent 89495 895c2f5035539931d4279cf88a7d326f87e21b51
child 89497 2d19579ec69b6aa95d2d2633a2bc10a2fdc623d2
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewersluke
bugs722946
milestone14.0a1
Bug 722946 - Add method to HashTable::Enum for inline rekeying; r=luke It is possible in several places to have unconstrained client objects as the key of a HashMap/HashSet. For generational and compacting GC, we will need to move these objects in memory. This means we will need to remove and re-insert these keys in a new location, during GC. Because we cannot safely allocate memory for this, we need a specialized algorithm inside the HashTable itself.
js/public/HashTable.h
js/src/jsapi-tests/Makefile.in
js/src/jsapi-tests/testHashTable.cpp
js/src/jsopcode.cpp
js/src/jsutil.h
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -91,17 +91,17 @@ class HashTableEntry {
     void setRemoved()             { keyHash = sRemovedKey; t = T(); }
     bool isLive() const           { return isLiveHash(keyHash); }
     void setLive(HashNumber hn)   { JS_ASSERT(isLiveHash(hn)); keyHash = hn; }
 
     void setCollision()           { JS_ASSERT(isLive()); keyHash |= sCollisionBit; }
     void setCollision(HashNumber collisionBit) {
         JS_ASSERT(isLive()); keyHash |= collisionBit;
     }
-    void unsetCollision()         { JS_ASSERT(isLive()); keyHash &= ~sCollisionBit; }
+    void unsetCollision()         { keyHash &= ~sCollisionBit; }
     bool hasCollision() const     { JS_ASSERT(isLive()); return keyHash & sCollisionBit; }
     bool matchHash(HashNumber hn) { return (keyHash & ~sCollisionBit) == hn; }
     HashNumber getKeyHash() const { JS_ASSERT(!hasCollision()); return keyHash; }
 };
 
 /*
  * js::detail::HashTable is an implementation detail of the js::HashMap and
  * js::HashSet templates. For js::Hash{Map,Set} API documentation and examples,
@@ -153,24 +153,19 @@ class HashTable : private AllocPolicy
         T *operator->() const                 { return &entry->t; }
     };
 
     /* A Ptr that can be used to add a key after a failed lookup. */
     class AddPtr : public Ptr
     {
         friend class HashTable;
         HashNumber keyHash;
-#ifdef DEBUG
-        uint64_t mutationCount;
+        DebugOnly<uint64_t> mutationCount;
 
-        AddPtr(Entry &entry, HashNumber hn, uint64_t mutationCount)
-            : Ptr(entry), keyHash(hn), mutationCount(mutationCount) {}
-#else
         AddPtr(Entry &entry, HashNumber hn) : Ptr(entry), keyHash(hn) {}
-#endif
       public:
         /* Leaves AddPtr uninitialized. */
         AddPtr() {}
     };
 
     /*
      * A collection of hash table entries. The collection is enumerated by
      * calling |front()| followed by |popFront()| as long as |!empty()|. As
@@ -217,48 +212,70 @@ class HashTable : private AllocPolicy
      * table, the user must ensure that the hash table is still alive when this
      * happens.
      */
     class Enum : public Range
     {
         friend class HashTable;
 
         HashTable &table;
+        bool added;
         bool removed;
 
         /* Not copyable. */
         Enum(const Enum &);
         void operator=(const Enum &);
 
       public:
         template<class Map> explicit
-        Enum(Map &map) : Range(map.all()), table(map.impl), removed(false) {}
+        Enum(Map &map) : Range(map.all()), table(map.impl), added(false), removed(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() {
             table.remove(*this->cur);
             removed = true;
         }
 
+        /*
+         * 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(Key &k) {
+            JS_ASSERT(&k != &HashPolicy::getKey(this->cur->t));
+            JS_ASSERT(!table.match(*this->cur, k));
+            Entry e = *this->cur;
+            HashPolicy::setKey(e.t, k);
+            table.remove(*this->cur);
+            table.add(k, e);
+            added = true;
+        }
+
         /* Potentially rehashes the table. */
         ~Enum() {
+            if (added)
+                table.checkOverloaded();
             if (removed)
                 table.checkUnderloaded();
         }
 
         /* Can be used to end the enumeration before the destructor. */
         void endEnumeration() {
+            if (added) {
+                table.checkOverloaded();
+                added = false;
+            }
             if (removed) {
                 table.checkUnderloaded();
                 removed = false;
             }
         }
     };
 
   private:
@@ -285,21 +302,19 @@ class HashTable : private AllocPolicy
         uint32_t        shrinks;        /* table contractions */
         uint32_t        compresses;     /* table compressions */
     } stats;
 #   define METER(x) x
 #else
 #   define METER(x)
 #endif
 
-#ifdef DEBUG
     friend class js::ReentrancyGuard;
-    mutable bool entered;
-    uint64_t     mutationCount;
-#endif
+    mutable DebugOnly<bool> entered;
+    DebugOnly<uint64_t>     mutationCount;
 
     /* The default initial capacity is 16, but you can ask for as small as 4. */
     static const unsigned sMinSizeLog2  = 2;
     static const unsigned sMinSize      = 1 << sMinSizeLog2;
     static const unsigned sDefaultInitSizeLog2 = 4;
   public:
     static const unsigned sDefaultInitSize = 1 << sDefaultInitSizeLog2;
   private:
@@ -359,21 +374,19 @@ class HashTable : private AllocPolicy
 
   public:
     HashTable(AllocPolicy ap)
       : AllocPolicy(ap),
         hashShift(sHashBits),
         entryCount(0),
         gen(0),
         removedCount(0),
-        table(NULL)
-#ifdef DEBUG
-        , entered(false),
+        table(NULL),
+        entered(false),
         mutationCount(0)
-#endif
     {}
 
     bool init(uint32_t length)
     {
         /* Make sure that init isn't called twice. */
         JS_ASSERT(table == NULL);
 
         /*
@@ -419,18 +432,32 @@ class HashTable : private AllocPolicy
             destroyTable(*this, table, capacity());
     }
 
   private:
     static HashNumber hash1(HashNumber hash0, uint32_t shift) {
         return hash0 >> shift;
     }
 
-    static HashNumber hash2(HashNumber hash0, uint32_t log2, uint32_t shift) {
-        return ((hash0 << log2) >> shift) | 1;
+    struct DoubleHash {
+        HashNumber h2;
+        HashNumber sizeMask;
+    };
+
+    DoubleHash hash2(HashNumber curKeyHash, uint32_t hashShift) const {
+        unsigned sizeLog2 = sHashBits - hashShift;
+        DoubleHash dh = {
+            ((curKeyHash << sizeLog2) >> hashShift) | 1,
+            (HashNumber(1) << sizeLog2) - 1
+        };
+        return dh;
+    }
+
+    static HashNumber applyDoubleHash(HashNumber h1, const DoubleHash &dh) {
+        return (h1 - dh.h2) & dh.sizeMask;
     }
 
     bool overloaded() {
         return entryCount + removedCount >= ((sMaxAlphaFrac * capacity()) >> 8);
     }
 
     bool underloaded() {
         uint32_t tableCapacity = capacity();
@@ -462,34 +489,31 @@ class HashTable : private AllocPolicy
 
         /* Hit: return entry. */
         if (entry->matchHash(keyHash) && match(*entry, l)) {
             METER(stats.hits++);
             return *entry;
         }
 
         /* Collision: double hash. */
-        unsigned sizeLog2 = sHashBits - hashShift;
-        HashNumber h2 = hash2(keyHash, sizeLog2, hashShift);
-        HashNumber sizeMask = (HashNumber(1) << sizeLog2) - 1;
+        DoubleHash dh = hash2(keyHash, hashShift);
 
         /* Save the first removed entry pointer so we can recycle later. */
         Entry *firstRemoved = NULL;
 
         while(true) {
             if (JS_UNLIKELY(entry->isRemoved())) {
                 if (!firstRemoved)
                     firstRemoved = entry;
             } else {
                 entry->setCollision(collisionBit);
             }
 
             METER(stats.steps++);
-            h1 -= h2;
-            h1 &= sizeMask;
+            h1 = applyDoubleHash(h1, dh);
 
             entry = &table[h1];
             if (entry->isFree()) {
                 METER(stats.misses++);
                 return firstRemoved ? *firstRemoved : *entry;
             }
 
             if (entry->matchHash(keyHash) && match(*entry, l)) {
@@ -520,27 +544,24 @@ class HashTable : private AllocPolicy
 
         /* Miss: return space for a new entry. */
         if (entry->isFree()) {
             METER(stats.misses++);
             return *entry;
         }
 
         /* Collision: double hash. */
-        unsigned sizeLog2 = sHashBits - hashShift;
-        HashNumber h2 = hash2(keyHash, sizeLog2, hashShift);
-        HashNumber sizeMask = (HashNumber(1) << sizeLog2) - 1;
+        DoubleHash dh = hash2(keyHash, hashShift);
 
         while(true) {
             JS_ASSERT(!entry->isRemoved());
             entry->setCollision();
 
             METER(stats.steps++);
-            h1 -= h2;
-            h1 &= sizeMask;
+            h1 = applyDoubleHash(h1, dh);
 
             entry = &table[h1];
             if (entry->isFree()) {
                 METER(stats.misses++);
                 return *entry;
             }
         }
     }
@@ -574,30 +595,66 @@ class HashTable : private AllocPolicy
                 findFreeEntry(src->getKeyHash()) = Move(*src);
             }
         }
 
         destroyTable(*this, oldTable, oldCap);
         return true;
     }
 
+    void add(const Lookup &l, const Entry &e)
+    {
+        HashNumber keyHash = prepareHash(l);
+        Entry &entry = lookup(l, keyHash, sCollisionBit);
+
+        if (entry.isRemoved()) {
+            METER(stats.addOverRemoved++);
+            removedCount--;
+            keyHash |= sCollisionBit;
+        }
+
+        entry.t = e.t;
+        entry.setLive(keyHash);
+        entryCount++;
+        mutationCount++;
+    }
+
+    bool checkOverloaded()
+    {
+        if (overloaded()) {
+            /* Compress if a quarter or more of all entries are removed. */
+            int deltaLog2;
+            if (removedCount >= (capacity() >> 2)) {
+                METER(stats.compresses++);
+                deltaLog2 = 0;
+            } else {
+                METER(stats.grows++);
+                deltaLog2 = 1;
+            }
+
+            (void) changeTableSize(deltaLog2);
+
+            return true;
+        }
+
+        return false;
+    }
+
     void remove(Entry &e)
     {
         METER(stats.removes++);
         if (e.hasCollision()) {
             e.setRemoved();
             removedCount++;
         } else {
             METER(stats.removeFrees++);
             e.setFree();
         }
         entryCount--;
-#ifdef DEBUG
         mutationCount++;
-#endif
     }
 
     void checkUnderloaded()
     {
         if (underloaded()) {
             METER(stats.shrinks++);
             (void) changeTableSize(-1);
         }
@@ -610,36 +667,32 @@ class HashTable : private AllocPolicy
             memset(table, 0, sizeof(*table) * capacity());
         } else {
             uint32_t tableCapacity = capacity();
             for (Entry *e = table, *end = table + tableCapacity; e < end; ++e)
                 *e = Move(Entry());
         }
         removedCount = 0;
         entryCount = 0;
-#ifdef DEBUG
         mutationCount++;
-#endif
     }
 
     void finish()
     {
         JS_ASSERT(!entered);
 
         if (!table)
             return;
-        
+
         destroyTable(*this, table, capacity());
         table = NULL;
         gen++;
         entryCount = 0;
         removedCount = 0;
-#ifdef DEBUG
         mutationCount++;
-#endif
     }
 
     Range all() const {
         return Range(table, table + capacity());
     }
 
     bool empty() const {
         return !entryCount;
@@ -670,21 +723,19 @@ class HashTable : private AllocPolicy
         HashNumber keyHash = prepareHash(l);
         return Ptr(lookup(l, keyHash, 0));
     }
 
     AddPtr lookupForAdd(const Lookup &l) const {
         ReentrancyGuard g(*this);
         HashNumber keyHash = prepareHash(l);
         Entry &entry = lookup(l, keyHash, sCollisionBit);
-#ifdef DEBUG
-        return AddPtr(entry, keyHash, mutationCount);
-#else
-        return AddPtr(entry, keyHash);
-#endif
+        AddPtr p(entry, keyHash);
+        p.mutationCount = mutationCount;
+        return p;
     }
 
     bool add(AddPtr &p)
     {
         ReentrancyGuard g(*this);
         JS_ASSERT(mutationCount == p.mutationCount);
         JS_ASSERT(table);
         JS_ASSERT(!p.found());
@@ -694,41 +745,24 @@ class HashTable : private AllocPolicy
          * Changing an entry from removed to live does not affect whether we
          * are overloaded and can be handled separately.
          */
         if (p.entry->isRemoved()) {
             METER(stats.addOverRemoved++);
             removedCount--;
             p.keyHash |= sCollisionBit;
         } else {
-            /* If alpha is >= .75, grow or compress the table. */
-            if (overloaded()) {
-                /* Compress if a quarter or more of all entries are removed. */
-                int deltaLog2;
-                if (removedCount >= (capacity() >> 2)) {
-                    METER(stats.compresses++);
-                    deltaLog2 = 0;
-                } else {
-                    METER(stats.grows++);
-                    deltaLog2 = 1;
-                }
-
-                if (!changeTableSize(deltaLog2))
-                    return false;
-
+            if (checkOverloaded())
                 /* Preserve the validity of |p.entry|. */
                 p.entry = &findFreeEntry(p.keyHash);
-            }
         }
 
         p.entry->setLive(p.keyHash);
         entryCount++;
-#ifdef DEBUG
         mutationCount++;
-#endif
         return true;
     }
 
     /*
      * There is an important contract between the caller and callee for this
      * function: if add() returns true, the caller must assign the T value
      * which produced p before using the hashtable again.
      */
@@ -745,33 +779,32 @@ class HashTable : private AllocPolicy
         if (!add(p))
             return false;
         p.entry->t = t;
         return true;
     }
 
     bool relookupOrAdd(AddPtr& p, const Lookup &l, const T& t)
     {
-#ifdef DEBUG
         p.mutationCount = mutationCount;
-#endif
         {
             ReentrancyGuard g(*this);
             p.entry = &lookup(l, p.keyHash, sCollisionBit);
         }
         return p.found() || add(p, t);
     }
 
     void remove(Ptr p)
     {
         ReentrancyGuard g(*this);
         JS_ASSERT(p.found());
         remove(*p.entry);
         checkUnderloaded();
     }
+
 #undef METER
 };
 
 }  /* namespace detail */
 
 /*****************************************************************************/
 
 /*
@@ -875,17 +908,17 @@ class HashMapEntry
     }
 
   public:
     HashMapEntry() : key(), value() {}
 
     template<typename KeyInput, typename ValueInput>
     HashMapEntry(const KeyInput &k, const ValueInput &v) : key(k), value(v) {}
 
-    HashMapEntry(MoveRef<HashMapEntry> rhs) 
+    HashMapEntry(MoveRef<HashMapEntry> rhs)
       : key(Move(rhs->key)), value(Move(rhs->value)) { }
     void operator=(MoveRef<HashMapEntry> rhs) {
         const_cast<Key &>(key) = Move(rhs->key);
         value = Move(rhs->value);
     }
 
     const Key key;
     Value value;
@@ -934,16 +967,17 @@ class HashMap
     typedef HashMapEntry<Key, Value> Entry;
 
   private:
     /* Implement HashMap using HashTable. Lift |Key| operations to |Entry|. */
     struct MapHashPolicy : HashPolicy
     {
         typedef Key KeyType;
         static const Key &getKey(Entry &e) { return e.key; }
+        static void setKey(Entry &e, Key &k) { const_cast<Key &>(e.key) = k; }
     };
     typedef detail::HashTable<Entry, MapHashPolicy, AllocPolicy> Impl;
 
     friend class Impl::Enum;
 
     /* Not implicitly copyable (expensive). May add explicit |clone| later. */
     HashMap(const HashMap &);
     HashMap &operator=(const HashMap &);
@@ -1063,17 +1097,17 @@ class HashMap
     typedef typename Impl::Range Range;
     Range all() const                                 { return impl.all(); }
     uint32_t count() const                            { return impl.count(); }
     size_t capacity() const                           { return impl.capacity(); }
     size_t sizeOfExcludingThis(JSMallocSizeOfFun mallocSizeOf) const {
         return impl.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(JSMallocSizeOfFun mallocSizeOf) const {
-        /* 
+        /*
          * Don't just call |impl.sizeOfExcludingThis()| because there's no
          * guarantee that |impl| is the first field in HashMap.
          */
         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
     }
 
     /*
      * Typedef for the enumeration class. An Enum may be used to examine and
@@ -1171,16 +1205,17 @@ template <class T, class HashPolicy = De
 class HashSet
 {
     typedef typename HashPolicy::Lookup Lookup;
 
     /* Implement HashSet in terms of HashTable. */
     struct SetOps : HashPolicy {
         typedef T KeyType;
         static const KeyType &getKey(const T &t) { return t; }
+        static void setKey(T &t, KeyType &k) { t = k; }
     };
     typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl;
 
     friend class Impl::Enum;
 
     /* Not implicitly copyable (expensive). May add explicit |clone| later. */
     HashSet(const HashSet &);
     HashSet &operator=(const HashSet &);
@@ -1273,17 +1308,17 @@ class HashSet
     typedef typename Impl::Range Range;
     Range all() const                                 { return impl.all(); }
     uint32_t count() const                            { return impl.count(); }
     size_t capacity() const                           { return impl.capacity(); }
     size_t sizeOfExcludingThis(JSMallocSizeOfFun mallocSizeOf) const {
         return impl.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(JSMallocSizeOfFun mallocSizeOf) const {
-        /* 
+        /*
          * Don't just call |impl.sizeOfExcludingThis()| because there's no
          * guarantee that |impl| is the first field in HashSet.
          */
         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
     }
 
     /*
      * Typedef for the enumeration class. An Enum may be used to examine and
--- a/js/src/jsapi-tests/Makefile.in
+++ b/js/src/jsapi-tests/Makefile.in
@@ -64,16 +64,17 @@ CPPSRCS = \
   testDefineProperty.cpp \
   testExtendedEq.cpp \
   testExternalStrings.cpp \
   testFuncCallback.cpp \
   testFunctionProperties.cpp \
   testGCOutOfMemory.cpp \
   testOOM.cpp \
   testGetPropertyDefault.cpp \
+  testHashTable.cpp \
   testIndexToString.cpp \
   testIntString.cpp \
   testIntTypesABI.cpp \
   testIntern.cpp \
   testLookup.cpp \
   testLooselyEqual.cpp \
   testNewObject.cpp \
   testOps.cpp \
new file mode 100644
--- /dev/null
+++ b/js/src/jsapi-tests/testHashTable.cpp
@@ -0,0 +1,287 @@
+#include "tests.h"
+
+#include "js/HashTable.h"
+
+//#define FUZZ
+
+typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;
+typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;
+
+/*
+ * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
+ * that are unique. We rekey by shifting left 16 bits.
+ */
+#ifdef FUZZ
+const size_t TestSize = 0x0000FFFF / 2;
+const size_t TestIterations = SIZE_MAX;
+#else
+const size_t TestSize = 10000;
+const size_t TestIterations = 10;
+#endif
+
+JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);
+
+struct LowToHigh
+{
+    static uint32_t rekey(uint32_t initial) {
+        if (initial > uint32_t(0x0000FFFF))
+            return initial;
+        return initial << 16;
+    }
+
+    static bool shouldBeRemoved(uint32_t initial) {
+        return false;
+    }
+};
+
+struct LowToHighWithRemoval
+{
+    static uint32_t rekey(uint32_t initial) {
+        if (initial > uint32_t(0x0000FFFF))
+            return initial;
+        return initial << 16;
+    }
+
+    static bool shouldBeRemoved(uint32_t initial) {
+        if (initial >= 0x00010000)
+            return (initial >> 16) % 2 == 0;
+        return initial % 2 == 0;
+    }
+};
+
+static bool
+MapsAreEqual(IntMap &am, IntMap &bm)
+{
+    bool equal = true;
+    if (am.count() != bm.count()) {
+        equal = false;
+        fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
+    }
+    for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {
+        if (!bm.has(r.front().key)) {
+            equal = false;
+            fprintf(stderr, "B does not have %x which is in A\n", r.front().key);
+        }
+    }
+    for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {
+        if (!am.has(r.front().key)) {
+            equal = false;
+            fprintf(stderr, "A does not have %x which is in B\n", r.front().key);
+        }
+    }
+    return equal;
+}
+
+static bool
+SetsAreEqual(IntSet &am, IntSet &bm)
+{
+    bool equal = true;
+    if (am.count() != bm.count()) {
+        equal = false;
+        fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
+    }
+    for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {
+        if (!bm.has(r.front())) {
+            equal = false;
+            fprintf(stderr, "B does not have %x which is in A\n", r.front());
+        }
+    }
+    for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {
+        if (!am.has(r.front())) {
+            equal = false;
+            fprintf(stderr, "A does not have %x which is in B\n", r.front());
+        }
+    }
+    return equal;
+}
+
+static bool
+AddLowKeys(IntMap *am, IntMap *bm, int seed)
+{
+    size_t i = 0;
+    srand(seed);
+    while (i < TestSize) {
+        uint32_t n = rand() & 0x0000FFFF;
+        if (!am->has(n)) {
+            if (bm->has(n))
+                return false;
+            am->putNew(n, n);
+            bm->putNew(n, n);
+            i++;
+        }
+    }
+    return true;
+}
+
+static bool
+AddLowKeys(IntSet *as, IntSet *bs, int seed)
+{
+    size_t i = 0;
+    srand(seed);
+    while (i < TestSize) {
+        uint32_t n = rand() & 0x0000FFFF;
+        if (!as->has(n)) {
+            if (bs->has(n))
+                return false;
+            as->putNew(n);
+            bs->putNew(n);
+            i++;
+        }
+    }
+    return true;
+}
+
+template <class NewKeyFunction>
+static bool
+SlowRekey(IntMap *m) {
+    IntMap tmp;
+    tmp.init();
+
+    for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {
+        if (NewKeyFunction::shouldBeRemoved(r.front().key))
+            continue;
+        uint32_t hi = NewKeyFunction::rekey(r.front().key);
+        if (tmp.has(hi))
+            return false;
+        tmp.putNew(hi, r.front().value);
+    }
+
+    m->clear();
+    for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {
+        m->putNew(r.front().key, r.front().value);
+    }
+
+    return true;
+}
+
+template <class NewKeyFunction>
+static bool
+SlowRekey(IntSet *s) {
+    IntSet tmp;
+    tmp.init();
+
+    for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {
+        if (NewKeyFunction::shouldBeRemoved(r.front()))
+            continue;
+        uint32_t hi = NewKeyFunction::rekey(r.front());
+        if (tmp.has(hi))
+            return false;
+        tmp.putNew(hi);
+    }
+
+    s->clear();
+    for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {
+        s->putNew(r.front());
+    }
+
+    return true;
+}
+
+BEGIN_TEST(testHashRekeyManual)
+{
+    IntMap am, bm;
+    am.init();
+    bm.init();
+    for (size_t i = 0; i < TestIterations; ++i) {
+#ifdef FUZZ
+        fprintf(stderr, "map1: %lu\n", i);
+#endif
+        CHECK(AddLowKeys(&am, &bm, i));
+        CHECK(MapsAreEqual(am, bm));
+
+        for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
+            uint32_t tmp = LowToHigh::rekey(e.front().key);
+            if (tmp != e.front().key)
+                e.rekeyFront(tmp);
+        }
+        CHECK(SlowRekey<LowToHigh>(&bm));
+
+        CHECK(MapsAreEqual(am, bm));
+        am.clear();
+        bm.clear();
+    }
+
+    IntSet as, bs;
+    as.init();
+    bs.init();
+    for (size_t i = 0; i < TestIterations; ++i) {
+#ifdef FUZZ
+        fprintf(stderr, "set1: %lu\n", i);
+#endif
+        CHECK(AddLowKeys(&as, &bs, i));
+        CHECK(SetsAreEqual(as, bs));
+
+        for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
+            uint32_t tmp = LowToHigh::rekey(e.front());
+            if (tmp != e.front())
+                e.rekeyFront(tmp);
+        }
+        CHECK(SlowRekey<LowToHigh>(&bs));
+
+        CHECK(SetsAreEqual(as, bs));
+        as.clear();
+        bs.clear();
+    }
+
+    return true;
+}
+END_TEST(testHashRekeyManual)
+
+BEGIN_TEST(testHashRekeyManualRemoval)
+{
+    IntMap am, bm;
+    am.init();
+    bm.init();
+    for (size_t i = 0; i < TestIterations; ++i) {
+#ifdef FUZZ
+        fprintf(stderr, "map2: %lu\n", i);
+#endif
+        CHECK(AddLowKeys(&am, &bm, i));
+        CHECK(MapsAreEqual(am, bm));
+
+        for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
+            if (LowToHighWithRemoval::shouldBeRemoved(e.front().key)) {
+                e.removeFront();
+            } else {
+                uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key);
+                if (tmp != e.front().key)
+                    e.rekeyFront(tmp);
+            }
+        }
+        CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
+
+        CHECK(MapsAreEqual(am, bm));
+        am.clear();
+        bm.clear();
+    }
+
+    IntSet as, bs;
+    as.init();
+    bs.init();
+    for (size_t i = 0; i < TestIterations; ++i) {
+#ifdef FUZZ
+        fprintf(stderr, "set1: %lu\n", i);
+#endif
+        CHECK(AddLowKeys(&as, &bs, i));
+        CHECK(SetsAreEqual(as, bs));
+
+        for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
+            if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {
+                e.removeFront();
+            } else {
+                uint32_t tmp = LowToHighWithRemoval::rekey(e.front());
+                if (tmp != e.front())
+                    e.rekeyFront(tmp);
+            }
+        }
+        CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
+
+        CHECK(SetsAreEqual(as, bs));
+        as.clear();
+        bs.clear();
+    }
+
+    return true;
+}
+END_TEST(testHashRekeyManualRemoval)
+
--- a/js/src/jsopcode.cpp
+++ b/js/src/jsopcode.cpp
@@ -2525,25 +2525,16 @@ InitSprintStack(JSContext *cx, SprintSta
     ss->bytecodes = (jsbytecode **) ((char *)space + offsetsz + opcodesz);
 
     ss->top = ss->inArrayInit = 0;
     ss->inGenExp = JS_FALSE;
     ss->printer = jp;
     return JS_TRUE;
 }
 
-template <typename T>
-void
-Swap(T &a, T &b)
-{
-    T tmp = a;
-    a = b;
-    b = tmp;
-}
-
 /*
  * If nb is non-negative, decompile nb bytecodes starting at pc.  Otherwise
  * the decompiler starts at pc and continues until it reaches an opcode for
  * which decompiling would result in the stack depth equaling -(nb + 1).
  */
 static jsbytecode *
 Decompile(SprintStack *ss, jsbytecode *pc, int nb)
 {
--- a/js/src/jsutil.h
+++ b/js/src/jsutil.h
@@ -268,16 +268,25 @@ PodEqual(T *one, T *two, size_t len)
                 return false;
         }
         return true;
     }
 
     return !memcmp(one, two, len * sizeof(T));
 }
 
+template <class T>
+JS_ALWAYS_INLINE static void
+Swap(T &t, T &u)
+{
+    T tmp(Move(t));
+    t = Move(u);
+    u = Move(tmp);
+}
+
 JS_ALWAYS_INLINE static size_t
 UnsignedPtrDiff(const void *bigger, const void *smaller)
 {
     return size_t(bigger) - size_t(smaller);
 }
 
 /*
  * Ordinarily, a function taking a JSContext* 'cx' parameter reports errors on