Bug 775896 - OrderedHashTable should have a hashShift field like HashTable. r=luke.
authorJason Orendorff <jorendorff@mozilla.com>
Wed, 25 Jul 2012 12:43:29 -0500
changeset 105953 0610488a81c9bc7f6fa336169d669f31c306f1cf
parent 105952 e4fc754010f94ffacd6a78ec1e32f8805a6ec5b9
child 105954 aa8bab8cc31f909a26e8e1f4b85981d43fb71e50
push idunknown
push userunknown
push dateunknown
reviewersluke
bugs775896
milestone17.0a1
Bug 775896 - OrderedHashTable should have a hashShift field like HashTable. r=luke.
js/public/Utility.h
js/src/builtin/MapObject.cpp
--- a/js/public/Utility.h
+++ b/js/public/Utility.h
@@ -919,16 +919,17 @@ class ReentrancyGuard
 JS_ALWAYS_INLINE size_t
 RoundUpPow2(size_t x)
 {
     return size_t(1) << JS_CEILING_LOG2W(x);
 }
 
 /* Integral types for all hash functions. */
 typedef uint32_t HashNumber;
+const unsigned HashNumberSizeBits = 32;
 
 namespace detail {
 
 /*
  * Given a raw hash code, h, return a number that can be used to select a hash
  * bucket.
  *
  * This function aims to produce as uniform an output distribution as possible,
--- a/js/src/builtin/MapObject.cpp
+++ b/js/src/builtin/MapObject.cpp
@@ -75,23 +75,23 @@ class OrderedHashTable
         Data(const T &e, Data *c) : element(e), chain(c) {}
         Data(MoveRef<T> e, Data *c) : element(e), chain(c) {}
     };
 
     class Range;
     friend class Range;
 
   private:
-    Data **hashTable;           // power-of-2-sized hash table
+    Data **hashTable;           // hash table (has hashBuckets() elements)
     Data *data;                 // data vector, an array of Data objects
                                 // data[0:dataLength] are constructed
     uint32_t dataLength;        // number of constructed elements in data
     uint32_t dataCapacity;      // size of data, in elements
     uint32_t liveCount;         // dataLength less empty (removed) entries
-    uint32_t hashTableMask;     // size of hashTable, in elements, minus one
+    uint32_t hashShift;         // multiplicative hash shift
     Range *ranges;              // list of all live Ranges on this table
     AllocPolicy alloc;
 
   public:
     OrderedHashTable(AllocPolicy &ap)
         : hashTable(NULL), data(NULL), dataLength(0), ranges(NULL), alloc(ap) {}
 
     bool init() {
@@ -111,17 +111,18 @@ class OrderedHashTable
             return false;
         }
 
         hashTable = tableAlloc;
         data = dataAlloc;
         dataLength = 0;
         dataCapacity = capacity;
         liveCount = 0;
-        hashTableMask = buckets - 1;
+        hashShift = HashNumberSizeBits - initialBucketsLog2();
+        JS_ASSERT(hashBuckets() == buckets);
         return true;
     }
 
     ~OrderedHashTable() {
         alloc.free_(hashTable);
         freeData(data, dataLength);
     }
 
@@ -157,24 +158,22 @@ class OrderedHashTable
         if (Data *e = lookup(Ops::getKey(element), h)) {
             e->element = element;
             return true;
         }
 
         if (dataLength == dataCapacity) {
             // If the hashTable is more than 1/4 deleted data, simply rehash in
             // place to free up some space. Otherwise, grow the table.
-            uint32_t newMask = liveCount >= dataCapacity * 0.75
-                             ? (hashTableMask << 1) | 1
-                             : hashTableMask;
-            if (!rehash(newMask))
+            uint32_t newHashShift = liveCount >= dataCapacity * 0.75 ? hashShift - 1 : hashShift;
+            if (!rehash(newHashShift))
                 return false;
         }
 
-        h &= hashTableMask;
+        h >>= hashShift;
         liveCount++;
         Data *e = &data[dataLength++];
         new (e) Data(element, hashTable[h]);
         hashTable[h] = e;
         return true;
     }
 
     /*
@@ -203,18 +202,18 @@ class OrderedHashTable
         Ops::makeEmpty(&e->element);
 
         // Update active Ranges.
         uint32_t pos = e - data;
         for (Range *r = ranges; r; r = r->next)
             r->onRemove(pos);
 
         // If many entries have been removed, try to shrink the table.
-        if (hashTableMask > initialBuckets() && liveCount < dataLength * minDataFill()) {
-            if (!rehash(hashTableMask >> 1))
+        if (hashBuckets() > initialBuckets() && liveCount < dataLength * minDataFill()) {
+            if (!rehash(hashShift + 1))
                 return false;
         }
         return true;
     }
 
     /*
      * Ranges are used to iterate over OrderedHashTables.
      *
@@ -365,18 +364,18 @@ class OrderedHashTable
          * Change the key of the front entry.
          *
          * This calls Ops::hash on both the current key and the new key.
          * Ops::hash on the current key must return the same hash code as
          * when the entry was added to the table.
          */
         void rekeyFront(const Key &k) {
             Data &entry = ht.data[i];
-            HashNumber oldHash = prepareHash(Ops::getKey(entry.element)) & ht.hashTableMask;
-            HashNumber newHash = prepareHash(k) & ht.hashTableMask;
+            HashNumber oldHash = prepareHash(Ops::getKey(entry.element)) >> ht.hashShift;
+            HashNumber newHash = prepareHash(k) >> ht.hashShift;
             Ops::setKey(entry.element, k);
             if (newHash != oldHash) {
                 // Remove this entry from its old hash chain. (If this crashes
                 // reading NULL, it would mean we did not find this entry on
                 // the hash chain where we expected it. That probably means the
                 // key's hash code changed since it was inserted, breaking the
                 // hash code invariant.)
                 Data **ep = &ht.hashTable[oldHash];
@@ -401,39 +400,37 @@ class OrderedHashTable
         /*
          * Change the key of the front entry without calling Ops::hash on the
          * entry's current key. The caller must ensure that k has the same hash
          * code that the current key had when it was inserted.
          */
         void rekeyFrontWithSameHashCode(const Key &k) {
 #ifdef DEBUG
             // Assert that k falls in the same hash bucket as the old key.
-            HashNumber h = Ops::hash(k) & ht.hashTableMask;
+            HashNumber h = Ops::hash(k) >> ht.hashShift;
             Data *e = ht.hashTable[h];
             while (e && e != &ht.data[i])
                 e = e->chain;
             JS_ASSERT(e == &ht.data[i]);
 #endif
             Ops::setKey(ht.data[i].element, k);
         }
     };
 
     Range all() { return Range(*this); }
 
   private:
-    /*
-     * The number of buckets in the hash table initially.
-     * This must be a power of two.
-     */
-    static uint32_t initialBuckets() { return 2; }
+    /* Logarithm base 2 of the number of buckets in the hash table initially. */
+    static uint32_t initialBucketsLog2() { return 1; }
+    static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); }
 
     /*
      * The maximum load factor (mean number of entries per bucket).
      * It is an invariant that
-     *     dataCapacity == floor((hashTableMask + 1) * fillFactor()).
+     *     dataCapacity == floor(hashBuckets() * fillFactor()).
      *
      * The fill factor should be between 2 and 4, and it should be chosen so that
      * the fill factor times sizeof(Data) is close to but <= a power of 2.
      * This fixed fill factor was chosen to make the size of the data
      * array, in bytes, close to a power of two when sizeof(T) is 16.
      */
     static double fillFactor() { return 8.0 / 3.0; }
 
@@ -442,24 +439,29 @@ class OrderedHashTable
      * If that ratio drops below this value, we shrink the table.
      */
     static double minDataFill() { return 0.25; }
 
     static HashNumber prepareHash(const Lookup &l) {
         return ScrambleHashCode(Ops::hash(l));
     }
 
+    /* The size of hashTable, in elements. Always a power of two. */
+    uint32_t hashBuckets() const {
+        return 1 << (HashNumberSizeBits - hashShift);
+    }
+
     void freeData(Data *data, uint32_t length) {
         for (Data *p = data + length; p != data; )
             (--p)->~Data();
         alloc.free_(data);
     }
 
     Data *lookup(const Lookup &l, HashNumber h) {
-        for (Data *e = hashTable[h & hashTableMask]; e; e = e->chain) {
+        for (Data *e = hashTable[h >> hashShift]; e; e = e->chain) {
             if (Ops::match(Ops::getKey(e->element), l))
                 return e;
         }
         return NULL;
     }
 
     const Data *lookup(const Lookup &l) const {
         return const_cast<OrderedHashTable *>(this)->lookup(l, prepareHash(l));
@@ -470,22 +472,22 @@ class OrderedHashTable
         // If we had any empty entries, compacting may have moved live entries
         // to the left within |data|. Notify all live Ranges of the change.
         for (Range *r = ranges; r; r = r->next)
             r->onCompact();
     }
 
     /* Compact the entries in |data| and rehash them. */
     void rehashInPlace() {
-        for (uint32_t i = 0; i <= hashTableMask; i++)
+        for (uint32_t i = 0, N = hashBuckets(); i < N; i++)
             hashTable[i] = NULL;
         Data *wp = data, *end = data + dataLength;
         for (Data *rp = data; rp != end; rp++) {
             if (!Ops::isEmpty(Ops::getKey(rp->element))) {
-                HashNumber h = prepareHash(Ops::getKey(rp->element)) & hashTableMask;
+                HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift;
                 if (rp != wp)
                     wp->element = Move(rp->element);
                 wp->chain = hashTable[h];
                 hashTable[h] = wp;
                 wp++;
             }
         }
         MOZ_ASSERT(wp == data + liveCount);
@@ -498,56 +500,58 @@ class OrderedHashTable
 
     /*
      * Grow, shrink, or compact both |hashTable| and |data|.
      *
      * On success, this returns true, dataLength == liveCount, and there are no
      * empty elements in data[0:dataLength]. On allocation failure, this
      * leaves everything as it was and returns false.
      */
-    bool rehash(uint32_t newMask) {
+    bool rehash(uint32_t newHashShift) {
         // If the size of the table is not changing, rehash in place to avoid
         // allocating memory.
-        if (newMask == hashTableMask) {
+        if (newHashShift == hashShift) {
             rehashInPlace();
             return true;
         }
 
-        Data **newHashTable = static_cast<Data **>(alloc.malloc_((newMask + 1) * sizeof(Data *)));
+        size_t newHashBuckets = 1 << (HashNumberSizeBits - newHashShift);
+        Data **newHashTable = static_cast<Data **>(alloc.malloc_(newHashBuckets * sizeof(Data *)));
         if (!newHashTable)
             return false;
-        for (uint32_t i = 0; i <= newMask; i++)
+        for (uint32_t i = 0; i < newHashBuckets; i++)
             newHashTable[i] = NULL;
 
-        uint32_t newCapacity = uint32_t((newMask + 1) * fillFactor());
+        uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor());
         Data *newData = static_cast<Data *>(alloc.malloc_(newCapacity * sizeof(Data)));
         if (!newData) {
             alloc.free_(newHashTable);
             return false;
         }
 
         Data *wp = newData;
         for (Data *p = data, *end = data + dataLength; p != end; p++) {
             if (!Ops::isEmpty(Ops::getKey(p->element))) {
-                HashNumber h = prepareHash(Ops::getKey(p->element)) & newMask;
+                HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift;
                 new (wp) Data(Move(p->element), newHashTable[h]);
                 newHashTable[h] = wp;
                 wp++;
             }
         }
         MOZ_ASSERT(wp == newData + liveCount);
 
         alloc.free_(hashTable);
         freeData(data, dataLength);
 
         hashTable = newHashTable;
         data = newData;
         dataLength = liveCount;
         dataCapacity = newCapacity;
-        hashTableMask = newMask;
+        hashShift = newHashShift;
+        JS_ASSERT(hashBuckets() == newHashBuckets);
 
         compacted();
         return true;
     }
 
     // Not copyable.
     OrderedHashTable &operator=(const OrderedHashTable &) MOZ_DELETE;
     OrderedHashTable(const OrderedHashTable &) MOZ_DELETE;
@@ -678,17 +682,19 @@ HashableValue::hash() const
     // value.data.asBits, except for strings.
     if (value.isString()) {
         JSLinearString &s = value.toString()->asLinear();
         return HashChars(s.chars(), s.length());
     }
 
     // Having dispensed with strings, we can just hash asBits.
     uint64_t u = value.asRawBits();
-    return HashNumber((u >> 3) ^ (u >> (32 + 3)) ^ (u << (32 - 3)));
+    return HashNumber((u >> 3) ^
+                      (u >> (HashNumberSizeBits + 3)) ^
+                      (u << (HashNumberSizeBits - 3)));
 }
 
 bool
 HashableValue::equals(const HashableValue &other) const
 {
     // Two HashableValues are equal if they have equal bits or they're equal strings.
     bool b = (value.asRawBits() == other.value.asRawBits()) ||
               (value.isString() &&