The Tor Browser: js/public/HashTable.h@925c144e1f1f (annotated)

js/public/HashTable.h@925c144e1f1f (annotated)

js/public/HashTable.h

Fri, 16 Jan 2015 18:13:44 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Fri, 16 Jan 2015 18:13:44 +0100
branch: TOR_BUG_9701
changeset 14: 925c144e1f1f
permissions: -rw-r--r--

Integrate suggestion from review to improve consistency with existing code.

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

The Tor Browser / annotate

js/public/HashTable.h@925c144e1f1f (annotated)

js/public/HashTable.h