The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

  * vim: set ts=8 sts=4 et sw=4 tw=99:

  * This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #ifndef js_HashTable_h

 #define js_HashTable_h

 #include "mozilla/Alignment.h"

 #include "mozilla/Assertions.h"

 #include "mozilla/Attributes.h"

 #include "mozilla/Casting.h"

 #include "mozilla/DebugOnly.h"

 #include "mozilla/MemoryReporting.h"

 #include "mozilla/Move.h"

 #include "mozilla/NullPtr.h"

 #include "mozilla/PodOperations.h"

 #include "mozilla/ReentrancyGuard.h"

 #include "mozilla/TemplateLib.h"

 #include "mozilla/TypeTraits.h"

 #include "js/Utility.h"

 namespace js {

 class TempAllocPolicy;

 template <class> struct DefaultHasher;

 template <class, class> class HashMapEntry;

 namespace detail {

     template <class T> class HashTableEntry;

     template <class T, class HashPolicy, class AllocPolicy> class HashTable;

 }

 /*****************************************************************************/

 // A JS-friendly, STL-like container providing a hash-based map from keys to

 // values. In particular, HashMap calls constructors and destructors of all

 // objects added so non-PODs may be used safely.

 //

 // Key/Value requirements:

 //  - movable, destructible, assignable

 // HashPolicy requirements:

 //  - see Hash Policy section below

 // AllocPolicy:

 //  - see jsalloc.h

 //

 // Note:

 // - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members

 //   called by HashMap must not call back into the same HashMap object.

 // - Due to the lack of exception handling, the user must call |init()|.

 template <class Key,

           class Value,

           class HashPolicy = DefaultHasher<Key>,

           class AllocPolicy = TempAllocPolicy>

 class HashMap

 {

     typedef HashMapEntry<Key, Value> TableEntry;

     struct MapHashPolicy : HashPolicy

     {

         typedef Key KeyType;

         static const Key &getKey(TableEntry &e) { return e.key(); }

         static void setKey(TableEntry &e, Key &k) { HashPolicy::rekey(e.mutableKey(), k); }

     };

     typedef detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy> Impl;

     Impl impl;

   public:

     typedef typename HashPolicy::Lookup Lookup;

     typedef TableEntry Entry;

     // HashMap construction is fallible (due to OOM); thus the user must call

     // init after constructing a HashMap and check the return value.

     HashMap(AllocPolicy a = AllocPolicy()) : impl(a)  {}

     bool init(uint32_t len = 16)                      { return impl.init(len); }

     bool initialized() const                          { return impl.initialized(); }

     // Return whether the given lookup value is present in the map. E.g.:

     //

     //   typedef HashMap<int,char> HM;

     //   HM h;

     //   if (HM::Ptr p = h.lookup(3)) {

     //     const HM::Entry &e = *p; // p acts like a pointer to Entry

     //     assert(p->key == 3);     // Entry contains the key

     //     char val = p->value;     // and value

     //   }

     //

     // Also see the definition of Ptr in HashTable above (with T = Entry).

     typedef typename Impl::Ptr Ptr;

     Ptr lookup(const Lookup &l) const                 { return impl.lookup(l); }

     // Like lookup, but does not assert if two threads call lookup at the same

     // time. Only use this method when none of the threads will modify the map.

     Ptr readonlyThreadsafeLookup(const Lookup &l) const { return impl.readonlyThreadsafeLookup(l); }

     // Assuming |p.found()|, remove |*p|.

     void remove(Ptr p)                                { impl.remove(p); }

     // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient

     // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using

     // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new Entry. E.g.:

     //

     //   typedef HashMap<int,char> HM;

     //   HM h;

     //   HM::AddPtr p = h.lookupForAdd(3);

     //   if (!p) {

     //     if (!h.add(p, 3, 'a'))

     //       return false;

     //   }

     //   const HM::Entry &e = *p;   // p acts like a pointer to Entry

     //   assert(p->key == 3);       // Entry contains the key

     //   char val = p->value;       // and value

     //

     // Also see the definition of AddPtr in HashTable above (with T = Entry).

     //

     // N.B. The caller must ensure that no mutating hash table operations

     // occur between a pair of |lookupForAdd| and |add| calls. To avoid

     // looking up the key a second time, the caller may use the more efficient

     // relookupOrAdd method. This method reuses part of the hashing computation

     // to more efficiently insert the key if it has not been added. For

     // example, a mutation-handling version of the previous example:

     //

     //    HM::AddPtr p = h.lookupForAdd(3);

     //    if (!p) {

     //      call_that_may_mutate_h();

     //      if (!h.relookupOrAdd(p, 3, 'a'))

     //        return false;

     //    }

     //    const HM::Entry &e = *p;

     //    assert(p->key == 3);

     //    char val = p->value;

     typedef typename Impl::AddPtr AddPtr;

     AddPtr lookupForAdd(const Lookup &l) const {

         return impl.lookupForAdd(l);

     }

     template<typename KeyInput, typename ValueInput>

     bool add(AddPtr &p, KeyInput &&k, ValueInput &&v) {

         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));

         return impl.add(p, mozilla::Move(e));

     }

     template<typename KeyInput>

     bool add(AddPtr &p, KeyInput &&k) {

         Entry e(mozilla::Forward<KeyInput>(k), Value());

         return impl.add(p, mozilla::Move(e));

     }

     template<typename KeyInput, typename ValueInput>

     bool relookupOrAdd(AddPtr &p, KeyInput &&k, ValueInput &&v) {

         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));

         return impl.relookupOrAdd(p, e.key(), mozilla::Move(e));

     }

     // |all()| returns a Range containing |count()| elements. E.g.:

     //

     //   typedef HashMap<int,char> HM;

     //   HM h;

     //   for (HM::Range r = h.all(); !r.empty(); r.popFront())

     //     char c = r.front().value();

     //

     // Also see the definition of Range in HashTable above (with T = Entry).

     typedef typename Impl::Range Range;

     Range all() const                                 { return impl.all(); }

     // Typedef for the enumeration class. An Enum may be used to examine and

     // remove table entries:

     //

     //   typedef HashMap<int,char> HM;

     //   HM s;

     //   for (HM::Enum e(s); !e.empty(); e.popFront())

     //     if (e.front().value() == 'l')

     //       e.removeFront();

     //

     // Table resize may occur in Enum's destructor. Also see the definition of

     // Enum in HashTable above (with T = Entry).

     typedef typename Impl::Enum Enum;

     // Remove all entries. This does not shrink the table. For that consider

     // using the finish() method.

     void clear()                                      { impl.clear(); }

     // Remove all entries without triggering destructors. This method is unsafe.

     void clearWithoutCallingDestructors()             { impl.clearWithoutCallingDestructors(); }

     // Remove all the entries and release all internal buffers. The map must

     // be initialized again before any use.

     void finish()                                     { impl.finish(); }

     // Does the table contain any entries?

     bool empty() const                                { return impl.empty(); }

     // Number of live elements in the map.

     uint32_t count() const                            { return impl.count(); }

     // Total number of allocation in the dynamic table. Note: resize will

     // happen well before count() == capacity().

     size_t capacity() const                           { return impl.capacity(); }

     // Don't just call |impl.sizeOfExcludingThis()| because there's no

     // guarantee that |impl| is the first field in HashMap.

     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

         return impl.sizeOfExcludingThis(mallocSizeOf);

     }

     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);

     }

     // If |generation()| is the same before and after a HashMap operation,

     // pointers into the table remain valid.

     unsigned generation() const                       { return impl.generation(); }

     /************************************************** Shorthand operations */

     bool has(const Lookup &l) const {

         return impl.lookup(l) != nullptr;

     }

     // Overwrite existing value with v. Return false on oom.

     template<typename KeyInput, typename ValueInput>

     bool put(KeyInput &&k, ValueInput &&v) {

         AddPtr p = lookupForAdd(k);

         if (p) {

             p->value() = mozilla::Forward<ValueInput>(v);

             return true;

         }

         return add(p, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));

     }

     // Like put, but assert that the given key is not already present.

     template<typename KeyInput, typename ValueInput>

     bool putNew(KeyInput &&k, ValueInput &&v) {

         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));

         return impl.putNew(e.key(), mozilla::Move(e));

     }

     // Add (k,defaultValue) if |k| is not found. Return a false-y Ptr on oom.

     Ptr lookupWithDefault(const Key &k, const Value &defaultValue) {

         AddPtr p = lookupForAdd(k);

         if (p)

             return p;

         (void)add(p, k, defaultValue);  // p is left false-y on oom.

         return p;

     }

     // Remove if present.

     void remove(const Lookup &l) {

         if (Ptr p = lookup(l))

             remove(p);

     }

     // Infallibly rekey one entry, if necessary.

     // Requires template parameters Key and HashPolicy::Lookup to be the same type.

     void rekeyIfMoved(const Key &old_key, const Key &new_key) {

         if (old_key != new_key)

             rekeyAs(old_key, new_key, new_key);

     }

     // Infallibly rekey one entry, if present.

     void rekeyAs(const Lookup &old_lookup, const Lookup &new_lookup, const Key &new_key) {

         if (Ptr p = lookup(old_lookup))

             impl.rekeyAndMaybeRehash(p, new_lookup, new_key);

     }

     // HashMap is movable

     HashMap(HashMap &&rhs) : impl(mozilla::Move(rhs.impl)) {}

     void operator=(HashMap &&rhs) {

         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");

         impl = mozilla::Move(rhs.impl);

     }

   private:

     // HashMap is not copyable or assignable

     HashMap(const HashMap &hm) MOZ_DELETE;

     HashMap &operator=(const HashMap &hm) MOZ_DELETE;

     friend class Impl::Enum;

 };

 /*****************************************************************************/

 // A JS-friendly, STL-like container providing a hash-based set of values. In

 // particular, HashSet calls constructors and destructors of all objects added

 // so non-PODs may be used safely.

 //

 // T requirements:

 //  - movable, destructible, assignable

 // HashPolicy requirements:

 //  - see Hash Policy section below

 // AllocPolicy:

 //  - see jsalloc.h

 //

 // Note:

 // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by

 //   HashSet must not call back into the same HashSet object.

 // - Due to the lack of exception handling, the user must call |init()|.

 template <class T,

           class HashPolicy = DefaultHasher<T>,

           class AllocPolicy = TempAllocPolicy>

 class HashSet

 {

     struct SetOps : HashPolicy

     {

         typedef T KeyType;

         static const KeyType &getKey(const T &t) { return t; }

         static void setKey(T &t, KeyType &k) { HashPolicy::rekey(t, k); }

     };

     typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl;

     Impl impl;

   public:

     typedef typename HashPolicy::Lookup Lookup;

     typedef T Entry;

     // HashSet construction is fallible (due to OOM); thus the user must call

     // init after constructing a HashSet and check the return value.

     HashSet(AllocPolicy a = AllocPolicy()) : impl(a)  {}

     bool init(uint32_t len = 16)                      { return impl.init(len); }

     bool initialized() const                          { return impl.initialized(); }

     // Return whether the given lookup value is present in the map. E.g.:

     //

     //   typedef HashSet<int> HS;

     //   HS h;

     //   if (HS::Ptr p = h.lookup(3)) {

     //     assert(*p == 3);   // p acts like a pointer to int

     //   }

     //

     // Also see the definition of Ptr in HashTable above.

     typedef typename Impl::Ptr Ptr;

     Ptr lookup(const Lookup &l) const                 { return impl.lookup(l); }

     // Like lookup, but does not assert if two threads call lookup at the same

     // time. Only use this method when none of the threads will modify the map.

     Ptr readonlyThreadsafeLookup(const Lookup &l) const { return impl.readonlyThreadsafeLookup(l); }

     // Assuming |p.found()|, remove |*p|.

     void remove(Ptr p)                                { impl.remove(p); }

     // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient

     // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using

     // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:

     //

     //   typedef HashSet<int> HS;

     //   HS h;

     //   HS::AddPtr p = h.lookupForAdd(3);

     //   if (!p) {

     //     if (!h.add(p, 3))

     //       return false;

     //   }

     //   assert(*p == 3);   // p acts like a pointer to int

     //

     // Also see the definition of AddPtr in HashTable above.

     //

     // N.B. The caller must ensure that no mutating hash table operations

     // occur between a pair of |lookupForAdd| and |add| calls. To avoid

     // looking up the key a second time, the caller may use the more efficient

     // relookupOrAdd method. This method reuses part of the hashing computation

     // to more efficiently insert the key if it has not been added. For

     // example, a mutation-handling version of the previous example:

     //

     //    HS::AddPtr p = h.lookupForAdd(3);

     //    if (!p) {

     //      call_that_may_mutate_h();

     //      if (!h.relookupOrAdd(p, 3, 3))

     //        return false;

     //    }

     //    assert(*p == 3);

     //

     // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the

     // entry |t|, where the caller ensures match(l,t).

     typedef typename Impl::AddPtr AddPtr;

     AddPtr lookupForAdd(const Lookup &l) const        { return impl.lookupForAdd(l); }

     template <typename U>

     bool add(AddPtr &p, U &&u) {

         return impl.add(p, mozilla::Forward<U>(u));

     }

     template <typename U>

     bool relookupOrAdd(AddPtr &p, const Lookup &l, U &&u) {

         return impl.relookupOrAdd(p, l, mozilla::Forward<U>(u));

     }

     // |all()| returns a Range containing |count()| elements:

     //

     //   typedef HashSet<int> HS;

     //   HS h;

     //   for (HS::Range r = h.all(); !r.empty(); r.popFront())

     //     int i = r.front();

     //

     // Also see the definition of Range in HashTable above.

     typedef typename Impl::Range Range;

     Range all() const                                 { return impl.all(); }

     // Typedef for the enumeration class. An Enum may be used to examine and

     // remove table entries:

     //

     //   typedef HashSet<int> HS;

     //   HS s;

     //   for (HS::Enum e(s); !e.empty(); e.popFront())

     //     if (e.front() == 42)

     //       e.removeFront();

     //

     // Table resize may occur in Enum's destructor. Also see the definition of

     // Enum in HashTable above.

     typedef typename Impl::Enum Enum;

     // Remove all entries. This does not shrink the table. For that consider

     // using the finish() method.

     void clear()                                      { impl.clear(); }

     // Remove all the entries and release all internal buffers. The set must

     // be initialized again before any use.

     void finish()                                     { impl.finish(); }

     // Does the table contain any entries?

     bool empty() const                                { return impl.empty(); }

     // Number of live elements in the map.

     uint32_t count() const                            { return impl.count(); }

     // Total number of allocation in the dynamic table. Note: resize will

     // happen well before count() == capacity().

     size_t capacity() const                           { return impl.capacity(); }

     // Don't just call |impl.sizeOfExcludingThis()| because there's no

     // guarantee that |impl| is the first field in HashSet.

     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

         return impl.sizeOfExcludingThis(mallocSizeOf);

     }

     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);

     }

     // If |generation()| is the same before and after a HashSet operation,

     // pointers into the table remain valid.

     unsigned generation() const                       { return impl.generation(); }

     /************************************************** Shorthand operations */

     bool has(const Lookup &l) const {

         return impl.lookup(l) != nullptr;

     }

     // Add |u| if it is not present already. Return false on oom.

     template <typename U>

     bool put(U &&u) {

         AddPtr p = lookupForAdd(u);

         return p ? true : add(p, mozilla::Forward<U>(u));

     }

     // Like put, but assert that the given key is not already present.

     template <typename U>

     bool putNew(U &&u) {

         return impl.putNew(u, mozilla::Forward<U>(u));

     }

     template <typename U>

     bool putNew(const Lookup &l, U &&u) {

         return impl.putNew(l, mozilla::Forward<U>(u));

     }

     void remove(const Lookup &l) {

         if (Ptr p = lookup(l))

             remove(p);

     }

     // Infallibly rekey one entry, if present.

     // Requires template parameters T and HashPolicy::Lookup to be the same type.

     void rekeyIfMoved(const Lookup &old_value, const T &new_value) {

         if (old_value != new_value)

             rekeyAs(old_value, new_value, new_value);

     }

     // Infallibly rekey one entry, if present.

     void rekeyAs(const Lookup &old_lookup, const Lookup &new_lookup, const T &new_value) {

         if (Ptr p = lookup(old_lookup))

             impl.rekeyAndMaybeRehash(p, new_lookup, new_value);

     }

     // HashSet is movable

     HashSet(HashSet &&rhs) : impl(mozilla::Move(rhs.impl)) {}

     void operator=(HashSet &&rhs) {

         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");

         impl = mozilla::Move(rhs.impl);

     }

   private:

     // HashSet is not copyable or assignable

     HashSet(const HashSet &hs) MOZ_DELETE;

     HashSet &operator=(const HashSet &hs) MOZ_DELETE;

     friend class Impl::Enum;

 };

 /*****************************************************************************/

 // Hash Policy

 //

 // A hash policy P for a hash table with key-type Key must provide:

 //  - a type |P::Lookup| to use to lookup table entries;

 //  - a static member function |P::hash| with signature

 //

 //      static js::HashNumber hash(Lookup)

 //

 //    to use to hash the lookup type; and

 //  - a static member function |P::match| with signature

 //

 //      static bool match(Key, Lookup)

 //

 //    to use to test equality of key and lookup values.

 //

 // Normally, Lookup = Key. In general, though, different values and types of

 // values can be used to lookup and store. If a Lookup value |l| is != to the

 // added Key value |k|, the user must ensure that |P::match(k,l)|. E.g.:

 //

 //   js::HashSet<Key, P>::AddPtr p = h.lookup(l);

 //   if (!p) {

 //     assert(P::match(k, l));  // must hold

 //     h.add(p, k);

 //   }

 // Pointer hashing policy that strips the lowest zeroBits when calculating the

 // hash to improve key distribution.

 template <typename Key, size_t zeroBits>

 struct PointerHasher

 {

     typedef Key Lookup;

     static HashNumber hash(const Lookup &l) {

         MOZ_ASSERT(!JS::IsPoisonedPtr(l));

         size_t word = reinterpret_cast<size_t>(l) >> zeroBits;

         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);

 #if JS_BITS_PER_WORD == 32

         return HashNumber(word);

 #else

         JS_STATIC_ASSERT(sizeof word == 8);

         return HashNumber((word >> 32) ^ word);

 #endif

     }

     static bool match(const Key &k, const Lookup &l) {

         MOZ_ASSERT(!JS::IsPoisonedPtr(k));

         MOZ_ASSERT(!JS::IsPoisonedPtr(l));

         return k == l;

     }

     static void rekey(Key &k, const Key& newKey) {

         k = newKey;

     }

 };

 // Default hash policy: just use the 'lookup' value. This of course only

 // works if the lookup value is integral. HashTable applies ScrambleHashCode to

 // the result of the 'hash' which means that it is 'ok' if the lookup value is

 // not well distributed over the HashNumber domain.

 template <class Key>

 struct DefaultHasher

 {

     typedef Key Lookup;

     static HashNumber hash(const Lookup &l) {

         // Hash if can implicitly cast to hash number type.

         return l;

     }

     static bool match(const Key &k, const Lookup &l) {

         // Use builtin or overloaded operator==.

         return k == l;

     }

     static void rekey(Key &k, const Key& newKey) {

         k = newKey;

     }

 };

 // Specialize hashing policy for pointer types. It assumes that the type is

 // at least word-aligned. For types with smaller size use PointerHasher.

 template <class T>

 struct DefaultHasher<T *> : PointerHasher<T *, mozilla::tl::FloorLog2<sizeof(void *)>::value>

 {};

 // For doubles, we can xor the two uint32s.

 template <>

 struct DefaultHasher<double>

 {

     typedef double Lookup;

     static HashNumber hash(double d) {

         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);

         uint64_t u = mozilla::BitwiseCast<uint64_t>(d);

         return HashNumber(u ^ (u >> 32));

     }

     static bool match(double lhs, double rhs) {

         return mozilla::BitwiseCast<uint64_t>(lhs) == mozilla::BitwiseCast<uint64_t>(rhs);

     }

 };

 template <>

 struct DefaultHasher<float>

 {

     typedef float Lookup;

     static HashNumber hash(float f) {

         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);

         return HashNumber(mozilla::BitwiseCast<uint32_t>(f));

     }

     static bool match(float lhs, float rhs) {

         return mozilla::BitwiseCast<uint32_t>(lhs) == mozilla::BitwiseCast<uint32_t>(rhs);

     }

 };

 /*****************************************************************************/

 // Both HashMap and HashSet are implemented by a single HashTable that is even

 // more heavily parameterized than the other two. This leaves HashTable gnarly

 // and extremely coupled to HashMap and HashSet; thus code should not use

 // HashTable directly.

 template <class Key, class Value>

 class HashMapEntry

 {

     Key key_;

     Value value_;

     template <class, class, class> friend class detail::HashTable;

     template <class> friend class detail::HashTableEntry;

     template <class, class, class, class> friend class HashMap;

     Key & mutableKey() { return key_; }

   public:

     template<typename KeyInput, typename ValueInput>

     HashMapEntry(KeyInput &&k, ValueInput &&v)

       : key_(mozilla::Forward<KeyInput>(k)),

         value_(mozilla::Forward<ValueInput>(v))

     {}

     HashMapEntry(HashMapEntry &&rhs)

       : key_(mozilla::Move(rhs.key_)),

         value_(mozilla::Move(rhs.value_))

     {}

     typedef Key KeyType;

     typedef Value ValueType;

     const Key & key() const { return key_; }

     const Value & value() const { return value_; }

     Value & value() { return value_; }

   private:

     HashMapEntry(const HashMapEntry &) MOZ_DELETE;

     void operator=(const HashMapEntry &) MOZ_DELETE;

 };

 } // namespace js

 namespace mozilla {

 template <typename T>

 struct IsPod<js::detail::HashTableEntry<T> > : IsPod<T> {};

 template <typename K, typename V>

 struct IsPod<js::HashMapEntry<K, V> >

   : IntegralConstant<bool, IsPod<K>::value && IsPod<V>::value>

 {};

 } // namespace mozilla

 namespace js {

 namespace detail {

 template <class T, class HashPolicy, class AllocPolicy>

 class HashTable;

 template <class T>

 class HashTableEntry

 {

     template <class, class, class> friend class HashTable;

     typedef typename mozilla::RemoveConst<T>::Type NonConstT;

     HashNumber keyHash;

     mozilla::AlignedStorage2<NonConstT> mem;

     static const HashNumber sFreeKey = 0;

     static const HashNumber sRemovedKey = 1;

     static const HashNumber sCollisionBit = 1;

     static bool isLiveHash(HashNumber hash)

     {

         return hash > sRemovedKey;

     }

     HashTableEntry(const HashTableEntry &) MOZ_DELETE;

     void operator=(const HashTableEntry &) MOZ_DELETE;

     ~HashTableEntry() MOZ_DELETE;

   public:

     // NB: HashTableEntry is treated as a POD: no constructor or destructor calls.

     void destroyIfLive() {

         if (isLive())

             mem.addr()->~T();

     }

     void destroy() {

         MOZ_ASSERT(isLive());

         mem.addr()->~T();

     }

     void swap(HashTableEntry *other) {

         mozilla::Swap(keyHash, other->keyHash);

         mozilla::Swap(mem, other->mem);

     }

     T &get() { MOZ_ASSERT(isLive()); return *mem.addr(); }

     bool isFree() const    { return keyHash == sFreeKey; }

     void clearLive()       { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); }

     void clear()           { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; }

     bool isRemoved() const { return keyHash == sRemovedKey; }

     void removeLive()      { MOZ_ASSERT(isLive()); keyHash = sRemovedKey; mem.addr()->~T(); }

     bool isLive() const    { return isLiveHash(keyHash); }

     void setCollision()               { MOZ_ASSERT(isLive()); keyHash |= sCollisionBit; }

     void setCollision(HashNumber bit) { MOZ_ASSERT(isLive()); keyHash |= bit; }

     void unsetCollision()             { keyHash &= ~sCollisionBit; }

     bool hasCollision() const         { return keyHash & sCollisionBit; }

     bool matchHash(HashNumber hn)     { return (keyHash & ~sCollisionBit) == hn; }

     HashNumber getKeyHash() const     { return keyHash & ~sCollisionBit; }

     template <class U>

     void setLive(HashNumber hn, U &&u)

     {

         MOZ_ASSERT(!isLive());

         keyHash = hn;

         new(mem.addr()) T(mozilla::Forward<U>(u));

         MOZ_ASSERT(isLive());

     }

 };

 template <class T, class HashPolicy, class AllocPolicy>

 class HashTable : private AllocPolicy

 {

     typedef typename mozilla::RemoveConst<T>::Type NonConstT;

     typedef typename HashPolicy::KeyType Key;

     typedef typename HashPolicy::Lookup Lookup;

   public:

     typedef HashTableEntry<T> Entry;

     // A nullable pointer to a hash table element. A Ptr |p| can be tested

     // either explicitly |if (p.found()) p->...| or using boolean conversion

     // |if (p) p->...|. Ptr objects must not be used after any mutating hash

     // table operations unless |generation()| is tested.

     class Ptr

     {

         friend class HashTable;

         typedef void (Ptr::* ConvertibleToBool)();

         void nonNull() {}

         Entry *entry_;

 #ifdef DEBUG

         const HashTable *table_;

         uint32_t generation;

 #endif

       protected:

         Ptr(Entry &entry, const HashTable &tableArg)

           : entry_(&entry)

 #ifdef DEBUG

           , table_(&tableArg)

           , generation(tableArg.generation())

 #endif

         {}

       public:

         // Leaves Ptr uninitialized.

         Ptr() {

 #ifdef JS_DEBUG

             entry_ = (Entry *)0xbad;

 #endif

         }

         bool found() const {

             MOZ_ASSERT(generation == table_->generation());

             return entry_->isLive();

         }

         operator ConvertibleToBool() const {

             return found() ? &Ptr::nonNull : 0;

         }

         bool operator==(const Ptr &rhs) const {

             MOZ_ASSERT(found() && rhs.found());

             return entry_ == rhs.entry_;

         }

         bool operator!=(const Ptr &rhs) const {

             MOZ_ASSERT(generation == table_->generation());

             return !(*this == rhs);

         }

         T &operator*() const {

             MOZ_ASSERT(generation == table_->generation());

             return entry_->get();

         }

         T *operator->() const {

             MOZ_ASSERT(generation == table_->generation());

             return &entry_->get();

         }

     };

     // A Ptr that can be used to add a key after a failed lookup.

     class AddPtr : public Ptr

     {

         friend class HashTable;

         HashNumber keyHash;

         mozilla::DebugOnly<uint64_t> mutationCount;

         AddPtr(Entry &entry, const HashTable &tableArg, HashNumber hn)

           : Ptr(entry, tableArg), keyHash(hn), mutationCount(tableArg.mutationCount)

         {}

       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

     // with Ptr/AddPtr, Range objects must not be used after any mutating hash

     // table operation unless the |generation()| is tested.

     class Range

     {

       protected:

         friend class HashTable;

         Range(const HashTable &tableArg, Entry *c, Entry *e)

           : cur(c)

           , end(e)

 #ifdef DEBUG

           , table_(&tableArg)

           , mutationCount(tableArg.mutationCount)

           , generation(tableArg.generation())

           , validEntry(true)

 #endif

         {

             while (cur < end && !cur->isLive())

                 ++cur;

         }

         Entry *cur, *end;

 #ifdef DEBUG

         const HashTable *table_;

         uint64_t mutationCount;

         uint32_t generation;

         bool validEntry;

 #endif

       public:

         Range()

           : cur(nullptr)

           , end(nullptr)

 #ifdef DEBUG

           , table_(nullptr)

           , mutationCount(0)

           , generation(0)

           , validEntry(false)

 #endif

         {}

         bool empty() const {

             MOZ_ASSERT(generation == table_->generation());

             MOZ_ASSERT(mutationCount == table_->mutationCount);

             return cur == end;

         }

         T &front() const {

             MOZ_ASSERT(validEntry);

             MOZ_ASSERT(!empty());

             MOZ_ASSERT(generation == table_->generation());

             MOZ_ASSERT(mutationCount == table_->mutationCount);

             return cur->get();

         }

         void popFront() {

             MOZ_ASSERT(!empty());

             MOZ_ASSERT(generation == table_->generation());

             MOZ_ASSERT(mutationCount == table_->mutationCount);

             while (++cur < end && !cur->isLive())

                 continue;

 #ifdef DEBUG

             validEntry = 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.

     class Enum : public Range

     {

         friend class HashTable;

         HashTable &table_;

         bool rekeyed;

         bool removed;

         /* Not copyable. */

         Enum(const Enum &) MOZ_DELETE;

         void operator=(const Enum &) MOZ_DELETE;

       public:

         template<class Map> explicit

         Enum(Map &map) : Range(map.all()), table_(map.impl), rekeyed(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;

 #ifdef DEBUG

             this->validEntry = false;

             this->mutationCount = table_.mutationCount;

 #endif

         }

         // 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 &l, const Key &k) {

             Ptr p(*this->cur, table_);

             table_.rekeyWithoutRehash(p, l, k);

             rekeyed = true;

 #ifdef DEBUG

             this->validEntry = false;

             this->mutationCount = table_.mutationCount;

 #endif

         }

         void rekeyFront(const Key &k) {

             rekeyFront(k, k);

         }

         // Potentially rehashes the table.

         ~Enum() {

             if (rekeyed) {

                 table_.gen++;

                 table_.checkOverRemoved();

             }

             if (removed)

                 table_.compactIfUnderloaded();

         }

     };

     // HashTable is movable

     HashTable(HashTable &&rhs)

       : AllocPolicy(rhs)

     {

         mozilla::PodAssign(this, &rhs);

         rhs.table = nullptr;

     }

     void operator=(HashTable &&rhs) {

         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");

         if (table)

             destroyTable(*this, table, capacity());

         mozilla::PodAssign(this, &rhs);

         rhs.table = nullptr;

     }

   private:

     // HashTable is not copyable or assignable

     HashTable(const HashTable &) MOZ_DELETE;

     void operator=(const HashTable &) MOZ_DELETE;

   private:

     uint32_t    hashShift;      // multiplicative hash shift

     uint32_t    entryCount;     // number of entries in table

     uint32_t    gen;            // entry storage generation number

     uint32_t    removedCount;   // removed entry sentinels in table

     Entry       *table;         // entry storage

     void setTableSizeLog2(unsigned sizeLog2)

     {

         hashShift = sHashBits - sizeLog2;

     }

 #ifdef JS_DEBUG

     mutable struct Stats

     {

         uint32_t        searches;       // total number of table searches

         uint32_t        steps;          // hash chain links traversed

         uint32_t        hits;           // searches that found key

         uint32_t        misses;         // searches that didn't find key

         uint32_t        addOverRemoved; // adds that recycled a removed entry

         uint32_t        removes;        // calls to remove

         uint32_t        removeFrees;    // calls to remove that freed the entry

         uint32_t        grows;          // table expansions

         uint32_t        shrinks;        // table contractions

         uint32_t        compresses;     // table compressions

         uint32_t        rehashes;       // tombstone decontaminations

     } stats;

 #   define METER(x) x

 #else

 #   define METER(x)

 #endif

     friend class mozilla::ReentrancyGuard;

     mutable mozilla::DebugOnly<bool> entered;

     mozilla::DebugOnly<uint64_t>     mutationCount;

     // The default initial capacity is 32 (enough to hold 16 elements), but it

     // can be as low as 4.

     static const unsigned sMinCapacityLog2 = 2;

     static const unsigned sMinCapacity  = 1 << sMinCapacityLog2;

     static const unsigned sMaxInit      = JS_BIT(23);

     static const unsigned sMaxCapacity  = JS_BIT(24);

     static const unsigned sHashBits     = mozilla::tl::BitSize<HashNumber>::value;

     // Hash-table alpha is conceptually a fraction, but to avoid floating-point

     // math we implement it as a ratio of integers.

     static const uint8_t sAlphaDenominator = 4;

     static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4

     static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4

     static const HashNumber sFreeKey = Entry::sFreeKey;

     static const HashNumber sRemovedKey = Entry::sRemovedKey;

     static const HashNumber sCollisionBit = Entry::sCollisionBit;

     static bool isLiveHash(HashNumber hash)

     {

         return Entry::isLiveHash(hash);

     }

     static HashNumber prepareHash(const Lookup& l)

     {

         HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));

         // Avoid reserved hash codes.

         if (!isLiveHash(keyHash))

             keyHash -= (sRemovedKey + 1);

         return keyHash & ~sCollisionBit;

     }

     static Entry *createTable(AllocPolicy &alloc, uint32_t capacity)

     {

         static_assert(sFreeKey == 0,

                       "newly-calloc'd tables have to be considered empty");

         static_assert(sMaxCapacity <= SIZE_MAX / sizeof(Entry),

                       "would overflow allocating max number of entries");

         return static_cast<Entry*>(alloc.calloc_(capacity * sizeof(Entry)));

     }

     static void destroyTable(AllocPolicy &alloc, Entry *oldTable, uint32_t capacity)

     {

         for (Entry *e = oldTable, *end = e + capacity; e < end; ++e)

             e->destroyIfLive();

         alloc.free_(oldTable);

     }

   public:

     HashTable(AllocPolicy ap)

       : AllocPolicy(ap),

         hashShift(sHashBits),

         entryCount(0),

         gen(0),

         removedCount(0),

         table(nullptr),

         entered(false),

         mutationCount(0)

     {}

     MOZ_WARN_UNUSED_RESULT bool init(uint32_t length)

     {

         MOZ_ASSERT(!initialized());

         // Reject all lengths whose initial computed capacity would exceed

         // sMaxCapacity.  Round that maximum length down to the nearest power

         // of two for speedier code.

         if (length > sMaxInit) {

             this->reportAllocOverflow();

             return false;

         }

         static_assert((sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,

                       "multiplication in numerator below could overflow");

         static_assert(sMaxInit * sAlphaDenominator <= UINT32_MAX - sMaxAlphaNumerator,

                       "numerator calculation below could potentially overflow");

         // Compute the smallest capacity allowing |length| elements to be

         // inserted without rehashing: ceil(length / max-alpha).  (Ceiling

         // integral division: <http://stackoverflow.com/a/2745086>.)

         uint32_t newCapacity =

             (length * sAlphaDenominator + sMaxAlphaNumerator - 1) / sMaxAlphaNumerator;

         if (newCapacity < sMinCapacity)

             newCapacity = sMinCapacity;

         // FIXME: use JS_CEILING_LOG2 when PGO stops crashing (bug 543034).

         uint32_t roundUp = sMinCapacity, roundUpLog2 = sMinCapacityLog2;

         while (roundUp < newCapacity) {

             roundUp <<= 1;

             ++roundUpLog2;

         }

         newCapacity = roundUp;

         MOZ_ASSERT(newCapacity >= length);

         MOZ_ASSERT(newCapacity <= sMaxCapacity);

         table = createTable(*this, newCapacity);

         if (!table)

             return false;

         setTableSizeLog2(roundUpLog2);

         METER(memset(&stats, 0, sizeof(stats)));

         return true;

     }

     bool initialized() const

     {

         return !!table;

     }

     ~HashTable()

     {

         if (table)

             destroyTable(*this, table, capacity());

     }

   private:

     HashNumber hash1(HashNumber hash0) const

     {

         return hash0 >> hashShift;

     }

     struct DoubleHash

     {

         HashNumber h2;

         HashNumber sizeMask;

     };

     DoubleHash hash2(HashNumber curKeyHash) 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()

     {

         static_assert(sMaxCapacity <= UINT32_MAX / sMaxAlphaNumerator,

                       "multiplication below could overflow");

         return entryCount + removedCount >=

                capacity() * sMaxAlphaNumerator / sAlphaDenominator;

     }

     // Would the table be underloaded if it had the given capacity and entryCount?

     static bool wouldBeUnderloaded(uint32_t capacity, uint32_t entryCount)

     {

         static_assert(sMaxCapacity <= UINT32_MAX / sMinAlphaNumerator,

                       "multiplication below could overflow");

         return capacity > sMinCapacity &&

                entryCount <= capacity * sMinAlphaNumerator / sAlphaDenominator;

     }

     bool underloaded()

     {

         return wouldBeUnderloaded(capacity(), entryCount);

     }

     static bool match(Entry &e, const Lookup &l)

     {

         return HashPolicy::match(HashPolicy::getKey(e.get()), l);

     }

     Entry &lookup(const Lookup &l, HashNumber keyHash, unsigned collisionBit) const

     {

         MOZ_ASSERT(isLiveHash(keyHash));

         MOZ_ASSERT(!(keyHash & sCollisionBit));

         MOZ_ASSERT(collisionBit == 0 || collisionBit == sCollisionBit);

         MOZ_ASSERT(table);

         METER(stats.searches++);

         // Compute the primary hash address.

         HashNumber h1 = hash1(keyHash);

         Entry *entry = &table[h1];

         // Miss: return space for a new entry.

         if (entry->isFree()) {

             METER(stats.misses++);

             return *entry;

         }

         // Hit: return entry.

         if (entry->matchHash(keyHash) && match(*entry, l)) {

             METER(stats.hits++);

             return *entry;

         }

         // Collision: double hash.

         DoubleHash dh = hash2(keyHash);

         // Save the first removed entry pointer so we can recycle later.

         Entry *firstRemoved = nullptr;

         while(true) {

             if (MOZ_UNLIKELY(entry->isRemoved())) {

                 if (!firstRemoved)

                     firstRemoved = entry;

             } else {

                 entry->setCollision(collisionBit);

             }

             METER(stats.steps++);

             h1 = applyDoubleHash(h1, dh);

             entry = &table[h1];

             if (entry->isFree()) {

                 METER(stats.misses++);

                 return firstRemoved ? *firstRemoved : *entry;

             }

             if (entry->matchHash(keyHash) && match(*entry, l)) {

                 METER(stats.hits++);

                 return *entry;

             }

         }

     }

     // This is a copy of lookup hardcoded to the assumptions:

     //   1. the lookup is a lookupForAdd

     //   2. the key, whose |keyHash| has been passed is not in the table,

     //   3. no entries have been removed from the table.

     // This specialized search avoids the need for recovering lookup values

     // from entries, which allows more flexible Lookup/Key types.

     Entry &findFreeEntry(HashNumber keyHash)

     {

         MOZ_ASSERT(!(keyHash & sCollisionBit));

         MOZ_ASSERT(table);

         METER(stats.searches++);

         // We assume 'keyHash' has already been distributed.

         // Compute the primary hash address.

         HashNumber h1 = hash1(keyHash);

         Entry *entry = &table[h1];

         // Miss: return space for a new entry.

         if (!entry->isLive()) {

             METER(stats.misses++);

             return *entry;

         }

         // Collision: double hash.

         DoubleHash dh = hash2(keyHash);

         while(true) {

             MOZ_ASSERT(!entry->isRemoved());

             entry->setCollision();

             METER(stats.steps++);

             h1 = applyDoubleHash(h1, dh);

             entry = &table[h1];

             if (!entry->isLive()) {

                 METER(stats.misses++);

                 return *entry;

             }

         }

     }

     enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };

     RebuildStatus changeTableSize(int deltaLog2)

     {

         // Look, but don't touch, until we succeed in getting new entry store.

         Entry *oldTable = table;

         uint32_t oldCap = capacity();

         uint32_t newLog2 = sHashBits - hashShift + deltaLog2;

         uint32_t newCapacity = JS_BIT(newLog2);

         if (newCapacity > sMaxCapacity) {

             this->reportAllocOverflow();

             return RehashFailed;

         }

         Entry *newTable = createTable(*this, newCapacity);

         if (!newTable)

             return RehashFailed;

         // We can't fail from here on, so update table parameters.

         setTableSizeLog2(newLog2);

         removedCount = 0;

         gen++;

         table = newTable;

         // Copy only live entries, leaving removed ones behind.

         for (Entry *src = oldTable, *end = src + oldCap; src < end; ++src) {

             if (src->isLive()) {

                 HashNumber hn = src->getKeyHash();

                 findFreeEntry(hn).setLive(hn, mozilla::Move(src->get()));

                 src->destroy();

             }

         }

         // All entries have been destroyed, no need to destroyTable.

         this->free_(oldTable);

         return Rehashed;

     }

     RebuildStatus checkOverloaded()

     {

         if (!overloaded())

             return NotOverloaded;

         // 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;

         }

         return changeTableSize(deltaLog2);

     }

     // Infallibly rehash the table if we are overloaded with removals.

     void checkOverRemoved()

     {

         if (overloaded()) {

             if (checkOverloaded() == RehashFailed)

                 rehashTableInPlace();

         }

     }

     void remove(Entry &e)

     {

         MOZ_ASSERT(table);

         METER(stats.removes++);

         if (e.hasCollision()) {

             e.removeLive();

             removedCount++;

         } else {

             METER(stats.removeFrees++);

             e.clearLive();

         }

         entryCount--;

         mutationCount++;

     }

     void checkUnderloaded()

     {

         if (underloaded()) {

             METER(stats.shrinks++);

             (void) changeTableSize(-1);

         }

     }

     // Resize the table down to the largest capacity which doesn't underload the

     // table.  Since we call checkUnderloaded() on every remove, you only need

     // to call this after a bulk removal of items done without calling remove().

     void compactIfUnderloaded()

     {

         int32_t resizeLog2 = 0;

         uint32_t newCapacity = capacity();

         while (wouldBeUnderloaded(newCapacity, entryCount)) {

             newCapacity = newCapacity >> 1;

             resizeLog2--;

         }

         if (resizeLog2 != 0) {

             changeTableSize(resizeLog2);

         }

     }

     // This is identical to changeTableSize(currentSize), but without requiring

     // a second table.  We do this by recycling the collision bits to tell us if

     // the element is already inserted or still waiting to be inserted.  Since

     // already-inserted elements win any conflicts, we get the same table as we

     // would have gotten through random insertion order.

     void rehashTableInPlace()

     {

         METER(stats.rehashes++);

         removedCount = 0;

         for (size_t i = 0; i < capacity(); ++i)

             table[i].unsetCollision();

         for (size_t i = 0; i < capacity();) {

             Entry *src = &table[i];

             if (!src->isLive() || src->hasCollision()) {

                 ++i;

                 continue;

             }

             HashNumber keyHash = src->getKeyHash();

             HashNumber h1 = hash1(keyHash);

             DoubleHash dh = hash2(keyHash);

             Entry *tgt = &table[h1];

             while (true) {

                 if (!tgt->hasCollision()) {

                     src->swap(tgt);

                     tgt->setCollision();

                     break;

                 }

                 h1 = applyDoubleHash(h1, dh);

                 tgt = &table[h1];

             }

         }

         // TODO: this algorithm leaves collision bits on *all* elements, even if

         // they are on no collision path. We have the option of setting the

         // collision bits correctly on a subsequent pass or skipping the rehash

         // unless we are totally filled with tombstones: benchmark to find out

         // which approach is best.

     }

   public:

     void clear()

     {

         if (mozilla::IsPod<Entry>::value) {

             memset(table, 0, sizeof(*table) * capacity());

         } else {

             uint32_t tableCapacity = capacity();

             for (Entry *e = table, *end = table + tableCapacity; e < end; ++e)

                 e->clear();

         }

         removedCount = 0;

         entryCount = 0;

         mutationCount++;

     }

     void finish()

     {

         MOZ_ASSERT(!entered);

         if (!table)

             return;

         destroyTable(*this, table, capacity());

         table = nullptr;

         gen++;

         entryCount = 0;

         removedCount = 0;

         mutationCount++;

     }

     Range all() const

     {

         MOZ_ASSERT(table);

         return Range(*this, table, table + capacity());

     }

     bool empty() const

     {

         MOZ_ASSERT(table);

         return !entryCount;

     }

     uint32_t count() const

     {

         MOZ_ASSERT(table);

         return entryCount;

     }

     uint32_t capacity() const

     {

         MOZ_ASSERT(table);

         return JS_BIT(sHashBits - hashShift);

     }

     uint32_t generation() const

     {

         MOZ_ASSERT(table);

         return gen;

     }

     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const

     {

         return mallocSizeOf(table);

     }

     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const

     {

         return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);

     }

     Ptr lookup(const Lookup &l) const

     {

         mozilla::ReentrancyGuard g(*this);

         HashNumber keyHash = prepareHash(l);

         return Ptr(lookup(l, keyHash, 0), *this);

     }

     Ptr readonlyThreadsafeLookup(const Lookup &l) const

     {

         HashNumber keyHash = prepareHash(l);

         return Ptr(lookup(l, keyHash, 0), *this);

     }

     AddPtr lookupForAdd(const Lookup &l) const

     {

         mozilla::ReentrancyGuard g(*this);

         HashNumber keyHash = prepareHash(l);

         Entry &entry = lookup(l, keyHash, sCollisionBit);

         AddPtr p(entry, *this, keyHash);

         return p;

     }

     template <class U>

     bool add(AddPtr &p, U &&u)

     {

         mozilla::ReentrancyGuard g(*this);

         MOZ_ASSERT(table);

         MOZ_ASSERT(!p.found());

         MOZ_ASSERT(!(p.keyHash & sCollisionBit));

         // 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 {

             // Preserve the validity of |p.entry_|.

             RebuildStatus status = checkOverloaded();

             if (status == RehashFailed)

                 return false;

             if (status == Rehashed)

                 p.entry_ = &findFreeEntry(p.keyHash);

         }

         p.entry_->setLive(p.keyHash, mozilla::Forward<U>(u));

         entryCount++;

         mutationCount++;

 #ifdef DEBUG

         p.generation = generation();

         p.mutationCount = mutationCount;

 #endif

         return true;

     }

     // Note: |l| may be a reference to a piece of |u|, so this function

     // must take care not to use |l| after moving |u|.

     template <class U>

     void putNewInfallible(const Lookup &l, U &&u)

     {

         MOZ_ASSERT(table);

         HashNumber keyHash = prepareHash(l);

         Entry *entry = &findFreeEntry(keyHash);

         if (entry->isRemoved()) {

             METER(stats.addOverRemoved++);

             removedCount--;

             keyHash |= sCollisionBit;

         }

         entry->setLive(keyHash, mozilla::Forward<U>(u));

         entryCount++;

         mutationCount++;

     }

     // Note: |l| may be a reference to a piece of |u|, so this function

     // must take care not to use |l| after moving |u|.

     template <class U>

     bool putNew(const Lookup &l, U &&u)

     {

         if (checkOverloaded() == RehashFailed)

             return false;

         putNewInfallible(l, mozilla::Forward<U>(u));

         return true;

     }

     // Note: |l| may be a reference to a piece of |u|, so this function

     // must take care not to use |l| after moving |u|.

     template <class U>

     bool relookupOrAdd(AddPtr& p, const Lookup &l, U &&u)

     {

 #ifdef DEBUG

         p.generation = generation();

         p.mutationCount = mutationCount;

 #endif

         {

             mozilla::ReentrancyGuard g(*this);

             MOZ_ASSERT(prepareHash(l) == p.keyHash); // l has not been destroyed

             p.entry_ = &lookup(l, p.keyHash, sCollisionBit);

         }

         return p.found() || add(p, mozilla::Forward<U>(u));

     }

     void remove(Ptr p)

     {

         MOZ_ASSERT(table);

         mozilla::ReentrancyGuard g(*this);

         MOZ_ASSERT(p.found());

         remove(*p.entry_);

         checkUnderloaded();

     }

     void rekeyWithoutRehash(Ptr p, const Lookup &l, const Key &k)

     {

         MOZ_ASSERT(table);

         mozilla::ReentrancyGuard g(*this);

         MOZ_ASSERT(p.found());

         typename HashTableEntry<T>::NonConstT t(mozilla::Move(*p));

         HashPolicy::setKey(t, const_cast<Key &>(k));

         remove(*p.entry_);

         putNewInfallible(l, mozilla::Move(t));

     }

     void rekeyAndMaybeRehash(Ptr p, const Lookup &l, const Key &k)

     {

         rekeyWithoutRehash(p, l, k);

         checkOverRemoved();

     }

 #undef METER

 };

 }  // namespace detail

 }  // namespace js

 #endif  /* js_HashTable_h */