michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef js_HashTable_h
michael@0: #define js_HashTable_h
michael@0: 
michael@0: #include "mozilla/Alignment.h"
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "mozilla/Casting.h"
michael@0: #include "mozilla/DebugOnly.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/Move.h"
michael@0: #include "mozilla/NullPtr.h"
michael@0: #include "mozilla/PodOperations.h"
michael@0: #include "mozilla/ReentrancyGuard.h"
michael@0: #include "mozilla/TemplateLib.h"
michael@0: #include "mozilla/TypeTraits.h"
michael@0: 
michael@0: #include "js/Utility.h"
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: class TempAllocPolicy;
michael@0: template <class> struct DefaultHasher;
michael@0: template <class, class> class HashMapEntry;
michael@0: namespace detail {
michael@0:     template <class T> class HashTableEntry;
michael@0:     template <class T, class HashPolicy, class AllocPolicy> class HashTable;
michael@0: }
michael@0: 
michael@0: /*****************************************************************************/
michael@0: 
michael@0: // A JS-friendly, STL-like container providing a hash-based map from keys to
michael@0: // values. In particular, HashMap calls constructors and destructors of all
michael@0: // objects added so non-PODs may be used safely.
michael@0: //
michael@0: // Key/Value requirements:
michael@0: //  - movable, destructible, assignable
michael@0: // HashPolicy requirements:
michael@0: //  - see Hash Policy section below
michael@0: // AllocPolicy:
michael@0: //  - see jsalloc.h
michael@0: //
michael@0: // Note:
michael@0: // - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
michael@0: //   called by HashMap must not call back into the same HashMap object.
michael@0: // - Due to the lack of exception handling, the user must call |init()|.
michael@0: template <class Key,
michael@0:           class Value,
michael@0:           class HashPolicy = DefaultHasher<Key>,
michael@0:           class AllocPolicy = TempAllocPolicy>
michael@0: class HashMap
michael@0: {
michael@0:     typedef HashMapEntry<Key, Value> TableEntry;
michael@0: 
michael@0:     struct MapHashPolicy : HashPolicy
michael@0:     {
michael@0:         typedef Key KeyType;
michael@0:         static const Key &getKey(TableEntry &e) { return e.key(); }
michael@0:         static void setKey(TableEntry &e, Key &k) { HashPolicy::rekey(e.mutableKey(), k); }
michael@0:     };
michael@0: 
michael@0:     typedef detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy> Impl;
michael@0:     Impl impl;
michael@0: 
michael@0:   public:
michael@0:     typedef typename HashPolicy::Lookup Lookup;
michael@0:     typedef TableEntry Entry;
michael@0: 
michael@0:     // HashMap construction is fallible (due to OOM); thus the user must call
michael@0:     // init after constructing a HashMap and check the return value.
michael@0:     HashMap(AllocPolicy a = AllocPolicy()) : impl(a)  {}
michael@0:     bool init(uint32_t len = 16)                      { return impl.init(len); }
michael@0:     bool initialized() const                          { return impl.initialized(); }
michael@0: 
michael@0:     // Return whether the given lookup value is present in the map. E.g.:
michael@0:     //
michael@0:     //   typedef HashMap<int,char> HM;
michael@0:     //   HM h;
michael@0:     //   if (HM::Ptr p = h.lookup(3)) {
michael@0:     //     const HM::Entry &e = *p; // p acts like a pointer to Entry
michael@0:     //     assert(p->key == 3);     // Entry contains the key
michael@0:     //     char val = p->value;     // and value
michael@0:     //   }
michael@0:     //
michael@0:     // Also see the definition of Ptr in HashTable above (with T = Entry).
michael@0:     typedef typename Impl::Ptr Ptr;
michael@0:     Ptr lookup(const Lookup &l) const                 { return impl.lookup(l); }
michael@0: 
michael@0:     // Like lookup, but does not assert if two threads call lookup at the same
michael@0:     // time. Only use this method when none of the threads will modify the map.
michael@0:     Ptr readonlyThreadsafeLookup(const Lookup &l) const { return impl.readonlyThreadsafeLookup(l); }
michael@0: 
michael@0:     // Assuming |p.found()|, remove |*p|.
michael@0:     void remove(Ptr p)                                { impl.remove(p); }
michael@0: 
michael@0:     // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
michael@0:     // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
michael@0:     // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new Entry. E.g.:
michael@0:     //
michael@0:     //   typedef HashMap<int,char> HM;
michael@0:     //   HM h;
michael@0:     //   HM::AddPtr p = h.lookupForAdd(3);
michael@0:     //   if (!p) {
michael@0:     //     if (!h.add(p, 3, 'a'))
michael@0:     //       return false;
michael@0:     //   }
michael@0:     //   const HM::Entry &e = *p;   // p acts like a pointer to Entry
michael@0:     //   assert(p->key == 3);       // Entry contains the key
michael@0:     //   char val = p->value;       // and value
michael@0:     //
michael@0:     // Also see the definition of AddPtr in HashTable above (with T = Entry).
michael@0:     //
michael@0:     // N.B. The caller must ensure that no mutating hash table operations
michael@0:     // occur between a pair of |lookupForAdd| and |add| calls. To avoid
michael@0:     // looking up the key a second time, the caller may use the more efficient
michael@0:     // relookupOrAdd method. This method reuses part of the hashing computation
michael@0:     // to more efficiently insert the key if it has not been added. For
michael@0:     // example, a mutation-handling version of the previous example:
michael@0:     //
michael@0:     //    HM::AddPtr p = h.lookupForAdd(3);
michael@0:     //    if (!p) {
michael@0:     //      call_that_may_mutate_h();
michael@0:     //      if (!h.relookupOrAdd(p, 3, 'a'))
michael@0:     //        return false;
michael@0:     //    }
michael@0:     //    const HM::Entry &e = *p;
michael@0:     //    assert(p->key == 3);
michael@0:     //    char val = p->value;
michael@0:     typedef typename Impl::AddPtr AddPtr;
michael@0:     AddPtr lookupForAdd(const Lookup &l) const {
michael@0:         return impl.lookupForAdd(l);
michael@0:     }
michael@0: 
michael@0:     template<typename KeyInput, typename ValueInput>
michael@0:     bool add(AddPtr &p, KeyInput &&k, ValueInput &&v) {
michael@0:         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
michael@0:         return impl.add(p, mozilla::Move(e));
michael@0:     }
michael@0: 
michael@0:     template<typename KeyInput>
michael@0:     bool add(AddPtr &p, KeyInput &&k) {
michael@0:         Entry e(mozilla::Forward<KeyInput>(k), Value());
michael@0:         return impl.add(p, mozilla::Move(e));
michael@0:     }
michael@0: 
michael@0:     template<typename KeyInput, typename ValueInput>
michael@0:     bool relookupOrAdd(AddPtr &p, KeyInput &&k, ValueInput &&v) {
michael@0:         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
michael@0:         return impl.relookupOrAdd(p, e.key(), mozilla::Move(e));
michael@0:     }
michael@0: 
michael@0:     // |all()| returns a Range containing |count()| elements. E.g.:
michael@0:     //
michael@0:     //   typedef HashMap<int,char> HM;
michael@0:     //   HM h;
michael@0:     //   for (HM::Range r = h.all(); !r.empty(); r.popFront())
michael@0:     //     char c = r.front().value();
michael@0:     //
michael@0:     // Also see the definition of Range in HashTable above (with T = Entry).
michael@0:     typedef typename Impl::Range Range;
michael@0:     Range all() const                                 { return impl.all(); }
michael@0: 
michael@0:     // Typedef for the enumeration class. An Enum may be used to examine and
michael@0:     // remove table entries:
michael@0:     //
michael@0:     //   typedef HashMap<int,char> HM;
michael@0:     //   HM s;
michael@0:     //   for (HM::Enum e(s); !e.empty(); e.popFront())
michael@0:     //     if (e.front().value() == 'l')
michael@0:     //       e.removeFront();
michael@0:     //
michael@0:     // Table resize may occur in Enum's destructor. Also see the definition of
michael@0:     // Enum in HashTable above (with T = Entry).
michael@0:     typedef typename Impl::Enum Enum;
michael@0: 
michael@0:     // Remove all entries. This does not shrink the table. For that consider
michael@0:     // using the finish() method.
michael@0:     void clear()                                      { impl.clear(); }
michael@0: 
michael@0:     // Remove all entries without triggering destructors. This method is unsafe.
michael@0:     void clearWithoutCallingDestructors()             { impl.clearWithoutCallingDestructors(); }
michael@0: 
michael@0:     // Remove all the entries and release all internal buffers. The map must
michael@0:     // be initialized again before any use.
michael@0:     void finish()                                     { impl.finish(); }
michael@0: 
michael@0:     // Does the table contain any entries?
michael@0:     bool empty() const                                { return impl.empty(); }
michael@0: 
michael@0:     // Number of live elements in the map.
michael@0:     uint32_t count() const                            { return impl.count(); }
michael@0: 
michael@0:     // Total number of allocation in the dynamic table. Note: resize will
michael@0:     // happen well before count() == capacity().
michael@0:     size_t capacity() const                           { return impl.capacity(); }
michael@0: 
michael@0:     // Don't just call |impl.sizeOfExcludingThis()| because there's no
michael@0:     // guarantee that |impl| is the first field in HashMap.
michael@0:     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
michael@0:         return impl.sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0:     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
michael@0:         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0: 
michael@0:     // If |generation()| is the same before and after a HashMap operation,
michael@0:     // pointers into the table remain valid.
michael@0:     unsigned generation() const                       { return impl.generation(); }
michael@0: 
michael@0:     /************************************************** Shorthand operations */
michael@0: 
michael@0:     bool has(const Lookup &l) const {
michael@0:         return impl.lookup(l) != nullptr;
michael@0:     }
michael@0: 
michael@0:     // Overwrite existing value with v. Return false on oom.
michael@0:     template<typename KeyInput, typename ValueInput>
michael@0:     bool put(KeyInput &&k, ValueInput &&v) {
michael@0:         AddPtr p = lookupForAdd(k);
michael@0:         if (p) {
michael@0:             p->value() = mozilla::Forward<ValueInput>(v);
michael@0:             return true;
michael@0:         }
michael@0:         return add(p, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
michael@0:     }
michael@0: 
michael@0:     // Like put, but assert that the given key is not already present.
michael@0:     template<typename KeyInput, typename ValueInput>
michael@0:     bool putNew(KeyInput &&k, ValueInput &&v) {
michael@0:         Entry e(mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
michael@0:         return impl.putNew(e.key(), mozilla::Move(e));
michael@0:     }
michael@0: 
michael@0:     // Add (k,defaultValue) if |k| is not found. Return a false-y Ptr on oom.
michael@0:     Ptr lookupWithDefault(const Key &k, const Value &defaultValue) {
michael@0:         AddPtr p = lookupForAdd(k);
michael@0:         if (p)
michael@0:             return p;
michael@0:         (void)add(p, k, defaultValue);  // p is left false-y on oom.
michael@0:         return p;
michael@0:     }
michael@0: 
michael@0:     // Remove if present.
michael@0:     void remove(const Lookup &l) {
michael@0:         if (Ptr p = lookup(l))
michael@0:             remove(p);
michael@0:     }
michael@0: 
michael@0:     // Infallibly rekey one entry, if necessary.
michael@0:     // Requires template parameters Key and HashPolicy::Lookup to be the same type.
michael@0:     void rekeyIfMoved(const Key &old_key, const Key &new_key) {
michael@0:         if (old_key != new_key)
michael@0:             rekeyAs(old_key, new_key, new_key);
michael@0:     }
michael@0: 
michael@0:     // Infallibly rekey one entry, if present.
michael@0:     void rekeyAs(const Lookup &old_lookup, const Lookup &new_lookup, const Key &new_key) {
michael@0:         if (Ptr p = lookup(old_lookup))
michael@0:             impl.rekeyAndMaybeRehash(p, new_lookup, new_key);
michael@0:     }
michael@0: 
michael@0:     // HashMap is movable
michael@0:     HashMap(HashMap &&rhs) : impl(mozilla::Move(rhs.impl)) {}
michael@0:     void operator=(HashMap &&rhs) {
michael@0:         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
michael@0:         impl = mozilla::Move(rhs.impl);
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     // HashMap is not copyable or assignable
michael@0:     HashMap(const HashMap &hm) MOZ_DELETE;
michael@0:     HashMap &operator=(const HashMap &hm) MOZ_DELETE;
michael@0: 
michael@0:     friend class Impl::Enum;
michael@0: };
michael@0: 
michael@0: /*****************************************************************************/
michael@0: 
michael@0: // A JS-friendly, STL-like container providing a hash-based set of values. In
michael@0: // particular, HashSet calls constructors and destructors of all objects added
michael@0: // so non-PODs may be used safely.
michael@0: //
michael@0: // T requirements:
michael@0: //  - movable, destructible, assignable
michael@0: // HashPolicy requirements:
michael@0: //  - see Hash Policy section below
michael@0: // AllocPolicy:
michael@0: //  - see jsalloc.h
michael@0: //
michael@0: // Note:
michael@0: // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
michael@0: //   HashSet must not call back into the same HashSet object.
michael@0: // - Due to the lack of exception handling, the user must call |init()|.
michael@0: template <class T,
michael@0:           class HashPolicy = DefaultHasher<T>,
michael@0:           class AllocPolicy = TempAllocPolicy>
michael@0: class HashSet
michael@0: {
michael@0:     struct SetOps : HashPolicy
michael@0:     {
michael@0:         typedef T KeyType;
michael@0:         static const KeyType &getKey(const T &t) { return t; }
michael@0:         static void setKey(T &t, KeyType &k) { HashPolicy::rekey(t, k); }
michael@0:     };
michael@0: 
michael@0:     typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl;
michael@0:     Impl impl;
michael@0: 
michael@0:   public:
michael@0:     typedef typename HashPolicy::Lookup Lookup;
michael@0:     typedef T Entry;
michael@0: 
michael@0:     // HashSet construction is fallible (due to OOM); thus the user must call
michael@0:     // init after constructing a HashSet and check the return value.
michael@0:     HashSet(AllocPolicy a = AllocPolicy()) : impl(a)  {}
michael@0:     bool init(uint32_t len = 16)                      { return impl.init(len); }
michael@0:     bool initialized() const                          { return impl.initialized(); }
michael@0: 
michael@0:     // Return whether the given lookup value is present in the map. E.g.:
michael@0:     //
michael@0:     //   typedef HashSet<int> HS;
michael@0:     //   HS h;
michael@0:     //   if (HS::Ptr p = h.lookup(3)) {
michael@0:     //     assert(*p == 3);   // p acts like a pointer to int
michael@0:     //   }
michael@0:     //
michael@0:     // Also see the definition of Ptr in HashTable above.
michael@0:     typedef typename Impl::Ptr Ptr;
michael@0:     Ptr lookup(const Lookup &l) const                 { return impl.lookup(l); }
michael@0: 
michael@0:     // Like lookup, but does not assert if two threads call lookup at the same
michael@0:     // time. Only use this method when none of the threads will modify the map.
michael@0:     Ptr readonlyThreadsafeLookup(const Lookup &l) const { return impl.readonlyThreadsafeLookup(l); }
michael@0: 
michael@0:     // Assuming |p.found()|, remove |*p|.
michael@0:     void remove(Ptr p)                                { impl.remove(p); }
michael@0: 
michael@0:     // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
michael@0:     // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
michael@0:     // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
michael@0:     //
michael@0:     //   typedef HashSet<int> HS;
michael@0:     //   HS h;
michael@0:     //   HS::AddPtr p = h.lookupForAdd(3);
michael@0:     //   if (!p) {
michael@0:     //     if (!h.add(p, 3))
michael@0:     //       return false;
michael@0:     //   }
michael@0:     //   assert(*p == 3);   // p acts like a pointer to int
michael@0:     //
michael@0:     // Also see the definition of AddPtr in HashTable above.
michael@0:     //
michael@0:     // N.B. The caller must ensure that no mutating hash table operations
michael@0:     // occur between a pair of |lookupForAdd| and |add| calls. To avoid
michael@0:     // looking up the key a second time, the caller may use the more efficient
michael@0:     // relookupOrAdd method. This method reuses part of the hashing computation
michael@0:     // to more efficiently insert the key if it has not been added. For
michael@0:     // example, a mutation-handling version of the previous example:
michael@0:     //
michael@0:     //    HS::AddPtr p = h.lookupForAdd(3);
michael@0:     //    if (!p) {
michael@0:     //      call_that_may_mutate_h();
michael@0:     //      if (!h.relookupOrAdd(p, 3, 3))
michael@0:     //        return false;
michael@0:     //    }
michael@0:     //    assert(*p == 3);
michael@0:     //
michael@0:     // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
michael@0:     // entry |t|, where the caller ensures match(l,t).
michael@0:     typedef typename Impl::AddPtr AddPtr;
michael@0:     AddPtr lookupForAdd(const Lookup &l) const        { return impl.lookupForAdd(l); }
michael@0: 
michael@0:     template <typename U>
michael@0:     bool add(AddPtr &p, U &&u) {
michael@0:         return impl.add(p, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     template <typename U>
michael@0:     bool relookupOrAdd(AddPtr &p, const Lookup &l, U &&u) {
michael@0:         return impl.relookupOrAdd(p, l, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     // |all()| returns a Range containing |count()| elements:
michael@0:     //
michael@0:     //   typedef HashSet<int> HS;
michael@0:     //   HS h;
michael@0:     //   for (HS::Range r = h.all(); !r.empty(); r.popFront())
michael@0:     //     int i = r.front();
michael@0:     //
michael@0:     // Also see the definition of Range in HashTable above.
michael@0:     typedef typename Impl::Range Range;
michael@0:     Range all() const                                 { return impl.all(); }
michael@0: 
michael@0:     // Typedef for the enumeration class. An Enum may be used to examine and
michael@0:     // remove table entries:
michael@0:     //
michael@0:     //   typedef HashSet<int> HS;
michael@0:     //   HS s;
michael@0:     //   for (HS::Enum e(s); !e.empty(); e.popFront())
michael@0:     //     if (e.front() == 42)
michael@0:     //       e.removeFront();
michael@0:     //
michael@0:     // Table resize may occur in Enum's destructor. Also see the definition of
michael@0:     // Enum in HashTable above.
michael@0:     typedef typename Impl::Enum Enum;
michael@0: 
michael@0:     // Remove all entries. This does not shrink the table. For that consider
michael@0:     // using the finish() method.
michael@0:     void clear()                                      { impl.clear(); }
michael@0: 
michael@0:     // Remove all the entries and release all internal buffers. The set must
michael@0:     // be initialized again before any use.
michael@0:     void finish()                                     { impl.finish(); }
michael@0: 
michael@0:     // Does the table contain any entries?
michael@0:     bool empty() const                                { return impl.empty(); }
michael@0: 
michael@0:     // Number of live elements in the map.
michael@0:     uint32_t count() const                            { return impl.count(); }
michael@0: 
michael@0:     // Total number of allocation in the dynamic table. Note: resize will
michael@0:     // happen well before count() == capacity().
michael@0:     size_t capacity() const                           { return impl.capacity(); }
michael@0: 
michael@0:     // Don't just call |impl.sizeOfExcludingThis()| because there's no
michael@0:     // guarantee that |impl| is the first field in HashSet.
michael@0:     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
michael@0:         return impl.sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0:     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
michael@0:         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0: 
michael@0:     // If |generation()| is the same before and after a HashSet operation,
michael@0:     // pointers into the table remain valid.
michael@0:     unsigned generation() const                       { return impl.generation(); }
michael@0: 
michael@0:     /************************************************** Shorthand operations */
michael@0: 
michael@0:     bool has(const Lookup &l) const {
michael@0:         return impl.lookup(l) != nullptr;
michael@0:     }
michael@0: 
michael@0:     // Add |u| if it is not present already. Return false on oom.
michael@0:     template <typename U>
michael@0:     bool put(U &&u) {
michael@0:         AddPtr p = lookupForAdd(u);
michael@0:         return p ? true : add(p, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     // Like put, but assert that the given key is not already present.
michael@0:     template <typename U>
michael@0:     bool putNew(U &&u) {
michael@0:         return impl.putNew(u, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     template <typename U>
michael@0:     bool putNew(const Lookup &l, U &&u) {
michael@0:         return impl.putNew(l, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     void remove(const Lookup &l) {
michael@0:         if (Ptr p = lookup(l))
michael@0:             remove(p);
michael@0:     }
michael@0: 
michael@0:     // Infallibly rekey one entry, if present.
michael@0:     // Requires template parameters T and HashPolicy::Lookup to be the same type.
michael@0:     void rekeyIfMoved(const Lookup &old_value, const T &new_value) {
michael@0:         if (old_value != new_value)
michael@0:             rekeyAs(old_value, new_value, new_value);
michael@0:     }
michael@0: 
michael@0:     // Infallibly rekey one entry, if present.
michael@0:     void rekeyAs(const Lookup &old_lookup, const Lookup &new_lookup, const T &new_value) {
michael@0:         if (Ptr p = lookup(old_lookup))
michael@0:             impl.rekeyAndMaybeRehash(p, new_lookup, new_value);
michael@0:     }
michael@0: 
michael@0:     // HashSet is movable
michael@0:     HashSet(HashSet &&rhs) : impl(mozilla::Move(rhs.impl)) {}
michael@0:     void operator=(HashSet &&rhs) {
michael@0:         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
michael@0:         impl = mozilla::Move(rhs.impl);
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     // HashSet is not copyable or assignable
michael@0:     HashSet(const HashSet &hs) MOZ_DELETE;
michael@0:     HashSet &operator=(const HashSet &hs) MOZ_DELETE;
michael@0: 
michael@0:     friend class Impl::Enum;
michael@0: };
michael@0: 
michael@0: /*****************************************************************************/
michael@0: 
michael@0: // Hash Policy
michael@0: //
michael@0: // A hash policy P for a hash table with key-type Key must provide:
michael@0: //  - a type |P::Lookup| to use to lookup table entries;
michael@0: //  - a static member function |P::hash| with signature
michael@0: //
michael@0: //      static js::HashNumber hash(Lookup)
michael@0: //
michael@0: //    to use to hash the lookup type; and
michael@0: //  - a static member function |P::match| with signature
michael@0: //
michael@0: //      static bool match(Key, Lookup)
michael@0: //
michael@0: //    to use to test equality of key and lookup values.
michael@0: //
michael@0: // Normally, Lookup = Key. In general, though, different values and types of
michael@0: // values can be used to lookup and store. If a Lookup value |l| is != to the
michael@0: // added Key value |k|, the user must ensure that |P::match(k,l)|. E.g.:
michael@0: //
michael@0: //   js::HashSet<Key, P>::AddPtr p = h.lookup(l);
michael@0: //   if (!p) {
michael@0: //     assert(P::match(k, l));  // must hold
michael@0: //     h.add(p, k);
michael@0: //   }
michael@0: 
michael@0: // Pointer hashing policy that strips the lowest zeroBits when calculating the
michael@0: // hash to improve key distribution.
michael@0: template <typename Key, size_t zeroBits>
michael@0: struct PointerHasher
michael@0: {
michael@0:     typedef Key Lookup;
michael@0:     static HashNumber hash(const Lookup &l) {
michael@0:         MOZ_ASSERT(!JS::IsPoisonedPtr(l));
michael@0:         size_t word = reinterpret_cast<size_t>(l) >> zeroBits;
michael@0:         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);
michael@0: #if JS_BITS_PER_WORD == 32
michael@0:         return HashNumber(word);
michael@0: #else
michael@0:         JS_STATIC_ASSERT(sizeof word == 8);
michael@0:         return HashNumber((word >> 32) ^ word);
michael@0: #endif
michael@0:     }
michael@0:     static bool match(const Key &k, const Lookup &l) {
michael@0:         MOZ_ASSERT(!JS::IsPoisonedPtr(k));
michael@0:         MOZ_ASSERT(!JS::IsPoisonedPtr(l));
michael@0:         return k == l;
michael@0:     }
michael@0:     static void rekey(Key &k, const Key& newKey) {
michael@0:         k = newKey;
michael@0:     }
michael@0: };
michael@0: 
michael@0: // Default hash policy: just use the 'lookup' value. This of course only
michael@0: // works if the lookup value is integral. HashTable applies ScrambleHashCode to
michael@0: // the result of the 'hash' which means that it is 'ok' if the lookup value is
michael@0: // not well distributed over the HashNumber domain.
michael@0: template <class Key>
michael@0: struct DefaultHasher
michael@0: {
michael@0:     typedef Key Lookup;
michael@0:     static HashNumber hash(const Lookup &l) {
michael@0:         // Hash if can implicitly cast to hash number type.
michael@0:         return l;
michael@0:     }
michael@0:     static bool match(const Key &k, const Lookup &l) {
michael@0:         // Use builtin or overloaded operator==.
michael@0:         return k == l;
michael@0:     }
michael@0:     static void rekey(Key &k, const Key& newKey) {
michael@0:         k = newKey;
michael@0:     }
michael@0: };
michael@0: 
michael@0: // Specialize hashing policy for pointer types. It assumes that the type is
michael@0: // at least word-aligned. For types with smaller size use PointerHasher.
michael@0: template <class T>
michael@0: struct DefaultHasher<T *> : PointerHasher<T *, mozilla::tl::FloorLog2<sizeof(void *)>::value>
michael@0: {};
michael@0: 
michael@0: // For doubles, we can xor the two uint32s.
michael@0: template <>
michael@0: struct DefaultHasher<double>
michael@0: {
michael@0:     typedef double Lookup;
michael@0:     static HashNumber hash(double d) {
michael@0:         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);
michael@0:         uint64_t u = mozilla::BitwiseCast<uint64_t>(d);
michael@0:         return HashNumber(u ^ (u >> 32));
michael@0:     }
michael@0:     static bool match(double lhs, double rhs) {
michael@0:         return mozilla::BitwiseCast<uint64_t>(lhs) == mozilla::BitwiseCast<uint64_t>(rhs);
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <>
michael@0: struct DefaultHasher<float>
michael@0: {
michael@0:     typedef float Lookup;
michael@0:     static HashNumber hash(float f) {
michael@0:         JS_STATIC_ASSERT(sizeof(HashNumber) == 4);
michael@0:         return HashNumber(mozilla::BitwiseCast<uint32_t>(f));
michael@0:     }
michael@0:     static bool match(float lhs, float rhs) {
michael@0:         return mozilla::BitwiseCast<uint32_t>(lhs) == mozilla::BitwiseCast<uint32_t>(rhs);
michael@0:     }
michael@0: };
michael@0: 
michael@0: /*****************************************************************************/
michael@0: 
michael@0: // Both HashMap and HashSet are implemented by a single HashTable that is even
michael@0: // more heavily parameterized than the other two. This leaves HashTable gnarly
michael@0: // and extremely coupled to HashMap and HashSet; thus code should not use
michael@0: // HashTable directly.
michael@0: 
michael@0: template <class Key, class Value>
michael@0: class HashMapEntry
michael@0: {
michael@0:     Key key_;
michael@0:     Value value_;
michael@0: 
michael@0:     template <class, class, class> friend class detail::HashTable;
michael@0:     template <class> friend class detail::HashTableEntry;
michael@0:     template <class, class, class, class> friend class HashMap;
michael@0: 
michael@0:     Key & mutableKey() { return key_; }
michael@0: 
michael@0:   public:
michael@0:     template<typename KeyInput, typename ValueInput>
michael@0:     HashMapEntry(KeyInput &&k, ValueInput &&v)
michael@0:       : key_(mozilla::Forward<KeyInput>(k)),
michael@0:         value_(mozilla::Forward<ValueInput>(v))
michael@0:     {}
michael@0: 
michael@0:     HashMapEntry(HashMapEntry &&rhs)
michael@0:       : key_(mozilla::Move(rhs.key_)),
michael@0:         value_(mozilla::Move(rhs.value_))
michael@0:     {}
michael@0: 
michael@0:     typedef Key KeyType;
michael@0:     typedef Value ValueType;
michael@0: 
michael@0:     const Key & key() const { return key_; }
michael@0:     const Value & value() const { return value_; }
michael@0:     Value & value() { return value_; }
michael@0: 
michael@0:   private:
michael@0:     HashMapEntry(const HashMapEntry &) MOZ_DELETE;
michael@0:     void operator=(const HashMapEntry &) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: } // namespace js
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: template <typename T>
michael@0: struct IsPod<js::detail::HashTableEntry<T> > : IsPod<T> {};
michael@0: 
michael@0: template <typename K, typename V>
michael@0: struct IsPod<js::HashMapEntry<K, V> >
michael@0:   : IntegralConstant<bool, IsPod<K>::value && IsPod<V>::value>
michael@0: {};
michael@0: 
michael@0: } // namespace mozilla
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: namespace detail {
michael@0: 
michael@0: template <class T, class HashPolicy, class AllocPolicy>
michael@0: class HashTable;
michael@0: 
michael@0: template <class T>
michael@0: class HashTableEntry
michael@0: {
michael@0:     template <class, class, class> friend class HashTable;
michael@0:     typedef typename mozilla::RemoveConst<T>::Type NonConstT;
michael@0: 
michael@0:     HashNumber keyHash;
michael@0:     mozilla::AlignedStorage2<NonConstT> mem;
michael@0: 
michael@0:     static const HashNumber sFreeKey = 0;
michael@0:     static const HashNumber sRemovedKey = 1;
michael@0:     static const HashNumber sCollisionBit = 1;
michael@0: 
michael@0:     static bool isLiveHash(HashNumber hash)
michael@0:     {
michael@0:         return hash > sRemovedKey;
michael@0:     }
michael@0: 
michael@0:     HashTableEntry(const HashTableEntry &) MOZ_DELETE;
michael@0:     void operator=(const HashTableEntry &) MOZ_DELETE;
michael@0:     ~HashTableEntry() MOZ_DELETE;
michael@0: 
michael@0:   public:
michael@0:     // NB: HashTableEntry is treated as a POD: no constructor or destructor calls.
michael@0: 
michael@0:     void destroyIfLive() {
michael@0:         if (isLive())
michael@0:             mem.addr()->~T();
michael@0:     }
michael@0: 
michael@0:     void destroy() {
michael@0:         MOZ_ASSERT(isLive());
michael@0:         mem.addr()->~T();
michael@0:     }
michael@0: 
michael@0:     void swap(HashTableEntry *other) {
michael@0:         mozilla::Swap(keyHash, other->keyHash);
michael@0:         mozilla::Swap(mem, other->mem);
michael@0:     }
michael@0: 
michael@0:     T &get() { MOZ_ASSERT(isLive()); return *mem.addr(); }
michael@0: 
michael@0:     bool isFree() const    { return keyHash == sFreeKey; }
michael@0:     void clearLive()       { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); }
michael@0:     void clear()           { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; }
michael@0:     bool isRemoved() const { return keyHash == sRemovedKey; }
michael@0:     void removeLive()      { MOZ_ASSERT(isLive()); keyHash = sRemovedKey; mem.addr()->~T(); }
michael@0:     bool isLive() const    { return isLiveHash(keyHash); }
michael@0:     void setCollision()               { MOZ_ASSERT(isLive()); keyHash |= sCollisionBit; }
michael@0:     void setCollision(HashNumber bit) { MOZ_ASSERT(isLive()); keyHash |= bit; }
michael@0:     void unsetCollision()             { keyHash &= ~sCollisionBit; }
michael@0:     bool hasCollision() const         { return keyHash & sCollisionBit; }
michael@0:     bool matchHash(HashNumber hn)     { return (keyHash & ~sCollisionBit) == hn; }
michael@0:     HashNumber getKeyHash() const     { return keyHash & ~sCollisionBit; }
michael@0: 
michael@0:     template <class U>
michael@0:     void setLive(HashNumber hn, U &&u)
michael@0:     {
michael@0:         MOZ_ASSERT(!isLive());
michael@0:         keyHash = hn;
michael@0:         new(mem.addr()) T(mozilla::Forward<U>(u));
michael@0:         MOZ_ASSERT(isLive());
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <class T, class HashPolicy, class AllocPolicy>
michael@0: class HashTable : private AllocPolicy
michael@0: {
michael@0:     typedef typename mozilla::RemoveConst<T>::Type NonConstT;
michael@0:     typedef typename HashPolicy::KeyType Key;
michael@0:     typedef typename HashPolicy::Lookup Lookup;
michael@0: 
michael@0:   public:
michael@0:     typedef HashTableEntry<T> Entry;
michael@0: 
michael@0:     // A nullable pointer to a hash table element. A Ptr |p| can be tested
michael@0:     // either explicitly |if (p.found()) p->...| or using boolean conversion
michael@0:     // |if (p) p->...|. Ptr objects must not be used after any mutating hash
michael@0:     // table operations unless |generation()| is tested.
michael@0:     class Ptr
michael@0:     {
michael@0:         friend class HashTable;
michael@0:         typedef void (Ptr::* ConvertibleToBool)();
michael@0:         void nonNull() {}
michael@0: 
michael@0:         Entry *entry_;
michael@0: #ifdef DEBUG
michael@0:         const HashTable *table_;
michael@0:         uint32_t generation;
michael@0: #endif
michael@0: 
michael@0:       protected:
michael@0:         Ptr(Entry &entry, const HashTable &tableArg)
michael@0:           : entry_(&entry)
michael@0: #ifdef DEBUG
michael@0:           , table_(&tableArg)
michael@0:           , generation(tableArg.generation())
michael@0: #endif
michael@0:         {}
michael@0: 
michael@0:       public:
michael@0:         // Leaves Ptr uninitialized.
michael@0:         Ptr() {
michael@0: #ifdef JS_DEBUG
michael@0:             entry_ = (Entry *)0xbad;
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         bool found() const {
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             return entry_->isLive();
michael@0:         }
michael@0: 
michael@0:         operator ConvertibleToBool() const {
michael@0:             return found() ? &Ptr::nonNull : 0;
michael@0:         }
michael@0: 
michael@0:         bool operator==(const Ptr &rhs) const {
michael@0:             MOZ_ASSERT(found() && rhs.found());
michael@0:             return entry_ == rhs.entry_;
michael@0:         }
michael@0: 
michael@0:         bool operator!=(const Ptr &rhs) const {
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             return !(*this == rhs);
michael@0:         }
michael@0: 
michael@0:         T &operator*() const {
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             return entry_->get();
michael@0:         }
michael@0: 
michael@0:         T *operator->() const {
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             return &entry_->get();
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     // A Ptr that can be used to add a key after a failed lookup.
michael@0:     class AddPtr : public Ptr
michael@0:     {
michael@0:         friend class HashTable;
michael@0:         HashNumber keyHash;
michael@0:         mozilla::DebugOnly<uint64_t> mutationCount;
michael@0: 
michael@0:         AddPtr(Entry &entry, const HashTable &tableArg, HashNumber hn)
michael@0:           : Ptr(entry, tableArg), keyHash(hn), mutationCount(tableArg.mutationCount)
michael@0:         {}
michael@0: 
michael@0:       public:
michael@0:         // Leaves AddPtr uninitialized.
michael@0:         AddPtr() {}
michael@0:     };
michael@0: 
michael@0:     // A collection of hash table entries. The collection is enumerated by
michael@0:     // calling |front()| followed by |popFront()| as long as |!empty()|. As
michael@0:     // with Ptr/AddPtr, Range objects must not be used after any mutating hash
michael@0:     // table operation unless the |generation()| is tested.
michael@0:     class Range
michael@0:     {
michael@0:       protected:
michael@0:         friend class HashTable;
michael@0: 
michael@0:         Range(const HashTable &tableArg, Entry *c, Entry *e)
michael@0:           : cur(c)
michael@0:           , end(e)
michael@0: #ifdef DEBUG
michael@0:           , table_(&tableArg)
michael@0:           , mutationCount(tableArg.mutationCount)
michael@0:           , generation(tableArg.generation())
michael@0:           , validEntry(true)
michael@0: #endif
michael@0:         {
michael@0:             while (cur < end && !cur->isLive())
michael@0:                 ++cur;
michael@0:         }
michael@0: 
michael@0:         Entry *cur, *end;
michael@0: #ifdef DEBUG
michael@0:         const HashTable *table_;
michael@0:         uint64_t mutationCount;
michael@0:         uint32_t generation;
michael@0:         bool validEntry;
michael@0: #endif
michael@0: 
michael@0:       public:
michael@0:         Range()
michael@0:           : cur(nullptr)
michael@0:           , end(nullptr)
michael@0: #ifdef DEBUG
michael@0:           , table_(nullptr)
michael@0:           , mutationCount(0)
michael@0:           , generation(0)
michael@0:           , validEntry(false)
michael@0: #endif
michael@0:         {}
michael@0: 
michael@0:         bool empty() const {
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             MOZ_ASSERT(mutationCount == table_->mutationCount);
michael@0:             return cur == end;
michael@0:         }
michael@0: 
michael@0:         T &front() const {
michael@0:             MOZ_ASSERT(validEntry);
michael@0:             MOZ_ASSERT(!empty());
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             MOZ_ASSERT(mutationCount == table_->mutationCount);
michael@0:             return cur->get();
michael@0:         }
michael@0: 
michael@0:         void popFront() {
michael@0:             MOZ_ASSERT(!empty());
michael@0:             MOZ_ASSERT(generation == table_->generation());
michael@0:             MOZ_ASSERT(mutationCount == table_->mutationCount);
michael@0:             while (++cur < end && !cur->isLive())
michael@0:                 continue;
michael@0: #ifdef DEBUG
michael@0:             validEntry = true;
michael@0: #endif
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     // A Range whose lifetime delimits a mutating enumeration of a hash table.
michael@0:     // Since rehashing when elements were removed during enumeration would be
michael@0:     // bad, it is postponed until the Enum is destructed.  Since the Enum's
michael@0:     // destructor touches the hash table, the user must ensure that the hash
michael@0:     // table is still alive when the destructor runs.
michael@0:     class Enum : public Range
michael@0:     {
michael@0:         friend class HashTable;
michael@0: 
michael@0:         HashTable &table_;
michael@0:         bool rekeyed;
michael@0:         bool removed;
michael@0: 
michael@0:         /* Not copyable. */
michael@0:         Enum(const Enum &) MOZ_DELETE;
michael@0:         void operator=(const Enum &) MOZ_DELETE;
michael@0: 
michael@0:       public:
michael@0:         template<class Map> explicit
michael@0:         Enum(Map &map) : Range(map.all()), table_(map.impl), rekeyed(false), removed(false) {}
michael@0: 
michael@0:         // Removes the |front()| element from the table, leaving |front()|
michael@0:         // invalid until the next call to |popFront()|. For example:
michael@0:         //
michael@0:         //   HashSet<int> s;
michael@0:         //   for (HashSet<int>::Enum e(s); !e.empty(); e.popFront())
michael@0:         //     if (e.front() == 42)
michael@0:         //       e.removeFront();
michael@0:         void removeFront() {
michael@0:             table_.remove(*this->cur);
michael@0:             removed = true;
michael@0: #ifdef DEBUG
michael@0:             this->validEntry = false;
michael@0:             this->mutationCount = table_.mutationCount;
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         // Removes the |front()| element and re-inserts it into the table with
michael@0:         // a new key at the new Lookup position.  |front()| is invalid after
michael@0:         // this operation until the next call to |popFront()|.
michael@0:         void rekeyFront(const Lookup &l, const Key &k) {
michael@0:             Ptr p(*this->cur, table_);
michael@0:             table_.rekeyWithoutRehash(p, l, k);
michael@0:             rekeyed = true;
michael@0: #ifdef DEBUG
michael@0:             this->validEntry = false;
michael@0:             this->mutationCount = table_.mutationCount;
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         void rekeyFront(const Key &k) {
michael@0:             rekeyFront(k, k);
michael@0:         }
michael@0: 
michael@0:         // Potentially rehashes the table.
michael@0:         ~Enum() {
michael@0:             if (rekeyed) {
michael@0:                 table_.gen++;
michael@0:                 table_.checkOverRemoved();
michael@0:             }
michael@0: 
michael@0:             if (removed)
michael@0:                 table_.compactIfUnderloaded();
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     // HashTable is movable
michael@0:     HashTable(HashTable &&rhs)
michael@0:       : AllocPolicy(rhs)
michael@0:     {
michael@0:         mozilla::PodAssign(this, &rhs);
michael@0:         rhs.table = nullptr;
michael@0:     }
michael@0:     void operator=(HashTable &&rhs) {
michael@0:         MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
michael@0:         if (table)
michael@0:             destroyTable(*this, table, capacity());
michael@0:         mozilla::PodAssign(this, &rhs);
michael@0:         rhs.table = nullptr;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     // HashTable is not copyable or assignable
michael@0:     HashTable(const HashTable &) MOZ_DELETE;
michael@0:     void operator=(const HashTable &) MOZ_DELETE;
michael@0: 
michael@0:   private:
michael@0:     uint32_t    hashShift;      // multiplicative hash shift
michael@0:     uint32_t    entryCount;     // number of entries in table
michael@0:     uint32_t    gen;            // entry storage generation number
michael@0:     uint32_t    removedCount;   // removed entry sentinels in table
michael@0:     Entry       *table;         // entry storage
michael@0: 
michael@0:     void setTableSizeLog2(unsigned sizeLog2)
michael@0:     {
michael@0:         hashShift = sHashBits - sizeLog2;
michael@0:     }
michael@0: 
michael@0: #ifdef JS_DEBUG
michael@0:     mutable struct Stats
michael@0:     {
michael@0:         uint32_t        searches;       // total number of table searches
michael@0:         uint32_t        steps;          // hash chain links traversed
michael@0:         uint32_t        hits;           // searches that found key
michael@0:         uint32_t        misses;         // searches that didn't find key
michael@0:         uint32_t        addOverRemoved; // adds that recycled a removed entry
michael@0:         uint32_t        removes;        // calls to remove
michael@0:         uint32_t        removeFrees;    // calls to remove that freed the entry
michael@0:         uint32_t        grows;          // table expansions
michael@0:         uint32_t        shrinks;        // table contractions
michael@0:         uint32_t        compresses;     // table compressions
michael@0:         uint32_t        rehashes;       // tombstone decontaminations
michael@0:     } stats;
michael@0: #   define METER(x) x
michael@0: #else
michael@0: #   define METER(x)
michael@0: #endif
michael@0: 
michael@0:     friend class mozilla::ReentrancyGuard;
michael@0:     mutable mozilla::DebugOnly<bool> entered;
michael@0:     mozilla::DebugOnly<uint64_t>     mutationCount;
michael@0: 
michael@0:     // The default initial capacity is 32 (enough to hold 16 elements), but it
michael@0:     // can be as low as 4.
michael@0:     static const unsigned sMinCapacityLog2 = 2;
michael@0:     static const unsigned sMinCapacity  = 1 << sMinCapacityLog2;
michael@0:     static const unsigned sMaxInit      = JS_BIT(23);
michael@0:     static const unsigned sMaxCapacity  = JS_BIT(24);
michael@0:     static const unsigned sHashBits     = mozilla::tl::BitSize<HashNumber>::value;
michael@0: 
michael@0:     // Hash-table alpha is conceptually a fraction, but to avoid floating-point
michael@0:     // math we implement it as a ratio of integers.
michael@0:     static const uint8_t sAlphaDenominator = 4;
michael@0:     static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
michael@0:     static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
michael@0: 
michael@0:     static const HashNumber sFreeKey = Entry::sFreeKey;
michael@0:     static const HashNumber sRemovedKey = Entry::sRemovedKey;
michael@0:     static const HashNumber sCollisionBit = Entry::sCollisionBit;
michael@0: 
michael@0:     static bool isLiveHash(HashNumber hash)
michael@0:     {
michael@0:         return Entry::isLiveHash(hash);
michael@0:     }
michael@0: 
michael@0:     static HashNumber prepareHash(const Lookup& l)
michael@0:     {
michael@0:         HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));
michael@0: 
michael@0:         // Avoid reserved hash codes.
michael@0:         if (!isLiveHash(keyHash))
michael@0:             keyHash -= (sRemovedKey + 1);
michael@0:         return keyHash & ~sCollisionBit;
michael@0:     }
michael@0: 
michael@0:     static Entry *createTable(AllocPolicy &alloc, uint32_t capacity)
michael@0:     {
michael@0:         static_assert(sFreeKey == 0,
michael@0:                       "newly-calloc'd tables have to be considered empty");
michael@0:         static_assert(sMaxCapacity <= SIZE_MAX / sizeof(Entry),
michael@0:                       "would overflow allocating max number of entries");
michael@0:         return static_cast<Entry*>(alloc.calloc_(capacity * sizeof(Entry)));
michael@0:     }
michael@0: 
michael@0:     static void destroyTable(AllocPolicy &alloc, Entry *oldTable, uint32_t capacity)
michael@0:     {
michael@0:         for (Entry *e = oldTable, *end = e + capacity; e < end; ++e)
michael@0:             e->destroyIfLive();
michael@0:         alloc.free_(oldTable);
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     HashTable(AllocPolicy ap)
michael@0:       : AllocPolicy(ap),
michael@0:         hashShift(sHashBits),
michael@0:         entryCount(0),
michael@0:         gen(0),
michael@0:         removedCount(0),
michael@0:         table(nullptr),
michael@0:         entered(false),
michael@0:         mutationCount(0)
michael@0:     {}
michael@0: 
michael@0:     MOZ_WARN_UNUSED_RESULT bool init(uint32_t length)
michael@0:     {
michael@0:         MOZ_ASSERT(!initialized());
michael@0: 
michael@0:         // Reject all lengths whose initial computed capacity would exceed
michael@0:         // sMaxCapacity.  Round that maximum length down to the nearest power
michael@0:         // of two for speedier code.
michael@0:         if (length > sMaxInit) {
michael@0:             this->reportAllocOverflow();
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         static_assert((sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,
michael@0:                       "multiplication in numerator below could overflow");
michael@0:         static_assert(sMaxInit * sAlphaDenominator <= UINT32_MAX - sMaxAlphaNumerator,
michael@0:                       "numerator calculation below could potentially overflow");
michael@0: 
michael@0:         // Compute the smallest capacity allowing |length| elements to be
michael@0:         // inserted without rehashing: ceil(length / max-alpha).  (Ceiling
michael@0:         // integral division: <http://stackoverflow.com/a/2745086>.)
michael@0:         uint32_t newCapacity =
michael@0:             (length * sAlphaDenominator + sMaxAlphaNumerator - 1) / sMaxAlphaNumerator;
michael@0:         if (newCapacity < sMinCapacity)
michael@0:             newCapacity = sMinCapacity;
michael@0: 
michael@0:         // FIXME: use JS_CEILING_LOG2 when PGO stops crashing (bug 543034).
michael@0:         uint32_t roundUp = sMinCapacity, roundUpLog2 = sMinCapacityLog2;
michael@0:         while (roundUp < newCapacity) {
michael@0:             roundUp <<= 1;
michael@0:             ++roundUpLog2;
michael@0:         }
michael@0: 
michael@0:         newCapacity = roundUp;
michael@0:         MOZ_ASSERT(newCapacity >= length);
michael@0:         MOZ_ASSERT(newCapacity <= sMaxCapacity);
michael@0: 
michael@0:         table = createTable(*this, newCapacity);
michael@0:         if (!table)
michael@0:             return false;
michael@0: 
michael@0:         setTableSizeLog2(roundUpLog2);
michael@0:         METER(memset(&stats, 0, sizeof(stats)));
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     bool initialized() const
michael@0:     {
michael@0:         return !!table;
michael@0:     }
michael@0: 
michael@0:     ~HashTable()
michael@0:     {
michael@0:         if (table)
michael@0:             destroyTable(*this, table, capacity());
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     HashNumber hash1(HashNumber hash0) const
michael@0:     {
michael@0:         return hash0 >> hashShift;
michael@0:     }
michael@0: 
michael@0:     struct DoubleHash
michael@0:     {
michael@0:         HashNumber h2;
michael@0:         HashNumber sizeMask;
michael@0:     };
michael@0: 
michael@0:     DoubleHash hash2(HashNumber curKeyHash) const
michael@0:     {
michael@0:         unsigned sizeLog2 = sHashBits - hashShift;
michael@0:         DoubleHash dh = {
michael@0:             ((curKeyHash << sizeLog2) >> hashShift) | 1,
michael@0:             (HashNumber(1) << sizeLog2) - 1
michael@0:         };
michael@0:         return dh;
michael@0:     }
michael@0: 
michael@0:     static HashNumber applyDoubleHash(HashNumber h1, const DoubleHash &dh)
michael@0:     {
michael@0:         return (h1 - dh.h2) & dh.sizeMask;
michael@0:     }
michael@0: 
michael@0:     bool overloaded()
michael@0:     {
michael@0:         static_assert(sMaxCapacity <= UINT32_MAX / sMaxAlphaNumerator,
michael@0:                       "multiplication below could overflow");
michael@0:         return entryCount + removedCount >=
michael@0:                capacity() * sMaxAlphaNumerator / sAlphaDenominator;
michael@0:     }
michael@0: 
michael@0:     // Would the table be underloaded if it had the given capacity and entryCount?
michael@0:     static bool wouldBeUnderloaded(uint32_t capacity, uint32_t entryCount)
michael@0:     {
michael@0:         static_assert(sMaxCapacity <= UINT32_MAX / sMinAlphaNumerator,
michael@0:                       "multiplication below could overflow");
michael@0:         return capacity > sMinCapacity &&
michael@0:                entryCount <= capacity * sMinAlphaNumerator / sAlphaDenominator;
michael@0:     }
michael@0: 
michael@0:     bool underloaded()
michael@0:     {
michael@0:         return wouldBeUnderloaded(capacity(), entryCount);
michael@0:     }
michael@0: 
michael@0:     static bool match(Entry &e, const Lookup &l)
michael@0:     {
michael@0:         return HashPolicy::match(HashPolicy::getKey(e.get()), l);
michael@0:     }
michael@0: 
michael@0:     Entry &lookup(const Lookup &l, HashNumber keyHash, unsigned collisionBit) const
michael@0:     {
michael@0:         MOZ_ASSERT(isLiveHash(keyHash));
michael@0:         MOZ_ASSERT(!(keyHash & sCollisionBit));
michael@0:         MOZ_ASSERT(collisionBit == 0 || collisionBit == sCollisionBit);
michael@0:         MOZ_ASSERT(table);
michael@0:         METER(stats.searches++);
michael@0: 
michael@0:         // Compute the primary hash address.
michael@0:         HashNumber h1 = hash1(keyHash);
michael@0:         Entry *entry = &table[h1];
michael@0: 
michael@0:         // Miss: return space for a new entry.
michael@0:         if (entry->isFree()) {
michael@0:             METER(stats.misses++);
michael@0:             return *entry;
michael@0:         }
michael@0: 
michael@0:         // Hit: return entry.
michael@0:         if (entry->matchHash(keyHash) && match(*entry, l)) {
michael@0:             METER(stats.hits++);
michael@0:             return *entry;
michael@0:         }
michael@0: 
michael@0:         // Collision: double hash.
michael@0:         DoubleHash dh = hash2(keyHash);
michael@0: 
michael@0:         // Save the first removed entry pointer so we can recycle later.
michael@0:         Entry *firstRemoved = nullptr;
michael@0: 
michael@0:         while(true) {
michael@0:             if (MOZ_UNLIKELY(entry->isRemoved())) {
michael@0:                 if (!firstRemoved)
michael@0:                     firstRemoved = entry;
michael@0:             } else {
michael@0:                 entry->setCollision(collisionBit);
michael@0:             }
michael@0: 
michael@0:             METER(stats.steps++);
michael@0:             h1 = applyDoubleHash(h1, dh);
michael@0: 
michael@0:             entry = &table[h1];
michael@0:             if (entry->isFree()) {
michael@0:                 METER(stats.misses++);
michael@0:                 return firstRemoved ? *firstRemoved : *entry;
michael@0:             }
michael@0: 
michael@0:             if (entry->matchHash(keyHash) && match(*entry, l)) {
michael@0:                 METER(stats.hits++);
michael@0:                 return *entry;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // This is a copy of lookup hardcoded to the assumptions:
michael@0:     //   1. the lookup is a lookupForAdd
michael@0:     //   2. the key, whose |keyHash| has been passed is not in the table,
michael@0:     //   3. no entries have been removed from the table.
michael@0:     // This specialized search avoids the need for recovering lookup values
michael@0:     // from entries, which allows more flexible Lookup/Key types.
michael@0:     Entry &findFreeEntry(HashNumber keyHash)
michael@0:     {
michael@0:         MOZ_ASSERT(!(keyHash & sCollisionBit));
michael@0:         MOZ_ASSERT(table);
michael@0:         METER(stats.searches++);
michael@0: 
michael@0:         // We assume 'keyHash' has already been distributed.
michael@0: 
michael@0:         // Compute the primary hash address.
michael@0:         HashNumber h1 = hash1(keyHash);
michael@0:         Entry *entry = &table[h1];
michael@0: 
michael@0:         // Miss: return space for a new entry.
michael@0:         if (!entry->isLive()) {
michael@0:             METER(stats.misses++);
michael@0:             return *entry;
michael@0:         }
michael@0: 
michael@0:         // Collision: double hash.
michael@0:         DoubleHash dh = hash2(keyHash);
michael@0: 
michael@0:         while(true) {
michael@0:             MOZ_ASSERT(!entry->isRemoved());
michael@0:             entry->setCollision();
michael@0: 
michael@0:             METER(stats.steps++);
michael@0:             h1 = applyDoubleHash(h1, dh);
michael@0: 
michael@0:             entry = &table[h1];
michael@0:             if (!entry->isLive()) {
michael@0:                 METER(stats.misses++);
michael@0:                 return *entry;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };
michael@0: 
michael@0:     RebuildStatus changeTableSize(int deltaLog2)
michael@0:     {
michael@0:         // Look, but don't touch, until we succeed in getting new entry store.
michael@0:         Entry *oldTable = table;
michael@0:         uint32_t oldCap = capacity();
michael@0:         uint32_t newLog2 = sHashBits - hashShift + deltaLog2;
michael@0:         uint32_t newCapacity = JS_BIT(newLog2);
michael@0:         if (newCapacity > sMaxCapacity) {
michael@0:             this->reportAllocOverflow();
michael@0:             return RehashFailed;
michael@0:         }
michael@0: 
michael@0:         Entry *newTable = createTable(*this, newCapacity);
michael@0:         if (!newTable)
michael@0:             return RehashFailed;
michael@0: 
michael@0:         // We can't fail from here on, so update table parameters.
michael@0:         setTableSizeLog2(newLog2);
michael@0:         removedCount = 0;
michael@0:         gen++;
michael@0:         table = newTable;
michael@0: 
michael@0:         // Copy only live entries, leaving removed ones behind.
michael@0:         for (Entry *src = oldTable, *end = src + oldCap; src < end; ++src) {
michael@0:             if (src->isLive()) {
michael@0:                 HashNumber hn = src->getKeyHash();
michael@0:                 findFreeEntry(hn).setLive(hn, mozilla::Move(src->get()));
michael@0:                 src->destroy();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // All entries have been destroyed, no need to destroyTable.
michael@0:         this->free_(oldTable);
michael@0:         return Rehashed;
michael@0:     }
michael@0: 
michael@0:     RebuildStatus checkOverloaded()
michael@0:     {
michael@0:         if (!overloaded())
michael@0:             return NotOverloaded;
michael@0: 
michael@0:         // Compress if a quarter or more of all entries are removed.
michael@0:         int deltaLog2;
michael@0:         if (removedCount >= (capacity() >> 2)) {
michael@0:             METER(stats.compresses++);
michael@0:             deltaLog2 = 0;
michael@0:         } else {
michael@0:             METER(stats.grows++);
michael@0:             deltaLog2 = 1;
michael@0:         }
michael@0: 
michael@0:         return changeTableSize(deltaLog2);
michael@0:     }
michael@0: 
michael@0:     // Infallibly rehash the table if we are overloaded with removals.
michael@0:     void checkOverRemoved()
michael@0:     {
michael@0:         if (overloaded()) {
michael@0:             if (checkOverloaded() == RehashFailed)
michael@0:                 rehashTableInPlace();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void remove(Entry &e)
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         METER(stats.removes++);
michael@0: 
michael@0:         if (e.hasCollision()) {
michael@0:             e.removeLive();
michael@0:             removedCount++;
michael@0:         } else {
michael@0:             METER(stats.removeFrees++);
michael@0:             e.clearLive();
michael@0:         }
michael@0:         entryCount--;
michael@0:         mutationCount++;
michael@0:     }
michael@0: 
michael@0:     void checkUnderloaded()
michael@0:     {
michael@0:         if (underloaded()) {
michael@0:             METER(stats.shrinks++);
michael@0:             (void) changeTableSize(-1);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Resize the table down to the largest capacity which doesn't underload the
michael@0:     // table.  Since we call checkUnderloaded() on every remove, you only need
michael@0:     // to call this after a bulk removal of items done without calling remove().
michael@0:     void compactIfUnderloaded()
michael@0:     {
michael@0:         int32_t resizeLog2 = 0;
michael@0:         uint32_t newCapacity = capacity();
michael@0:         while (wouldBeUnderloaded(newCapacity, entryCount)) {
michael@0:             newCapacity = newCapacity >> 1;
michael@0:             resizeLog2--;
michael@0:         }
michael@0: 
michael@0:         if (resizeLog2 != 0) {
michael@0:             changeTableSize(resizeLog2);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // This is identical to changeTableSize(currentSize), but without requiring
michael@0:     // a second table.  We do this by recycling the collision bits to tell us if
michael@0:     // the element is already inserted or still waiting to be inserted.  Since
michael@0:     // already-inserted elements win any conflicts, we get the same table as we
michael@0:     // would have gotten through random insertion order.
michael@0:     void rehashTableInPlace()
michael@0:     {
michael@0:         METER(stats.rehashes++);
michael@0:         removedCount = 0;
michael@0:         for (size_t i = 0; i < capacity(); ++i)
michael@0:             table[i].unsetCollision();
michael@0: 
michael@0:         for (size_t i = 0; i < capacity();) {
michael@0:             Entry *src = &table[i];
michael@0: 
michael@0:             if (!src->isLive() || src->hasCollision()) {
michael@0:                 ++i;
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             HashNumber keyHash = src->getKeyHash();
michael@0:             HashNumber h1 = hash1(keyHash);
michael@0:             DoubleHash dh = hash2(keyHash);
michael@0:             Entry *tgt = &table[h1];
michael@0:             while (true) {
michael@0:                 if (!tgt->hasCollision()) {
michael@0:                     src->swap(tgt);
michael@0:                     tgt->setCollision();
michael@0:                     break;
michael@0:                 }
michael@0: 
michael@0:                 h1 = applyDoubleHash(h1, dh);
michael@0:                 tgt = &table[h1];
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // TODO: this algorithm leaves collision bits on *all* elements, even if
michael@0:         // they are on no collision path. We have the option of setting the
michael@0:         // collision bits correctly on a subsequent pass or skipping the rehash
michael@0:         // unless we are totally filled with tombstones: benchmark to find out
michael@0:         // which approach is best.
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     void clear()
michael@0:     {
michael@0:         if (mozilla::IsPod<Entry>::value) {
michael@0:             memset(table, 0, sizeof(*table) * capacity());
michael@0:         } else {
michael@0:             uint32_t tableCapacity = capacity();
michael@0:             for (Entry *e = table, *end = table + tableCapacity; e < end; ++e)
michael@0:                 e->clear();
michael@0:         }
michael@0:         removedCount = 0;
michael@0:         entryCount = 0;
michael@0:         mutationCount++;
michael@0:     }
michael@0: 
michael@0:     void finish()
michael@0:     {
michael@0:         MOZ_ASSERT(!entered);
michael@0: 
michael@0:         if (!table)
michael@0:             return;
michael@0: 
michael@0:         destroyTable(*this, table, capacity());
michael@0:         table = nullptr;
michael@0:         gen++;
michael@0:         entryCount = 0;
michael@0:         removedCount = 0;
michael@0:         mutationCount++;
michael@0:     }
michael@0: 
michael@0:     Range all() const
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         return Range(*this, table, table + capacity());
michael@0:     }
michael@0: 
michael@0:     bool empty() const
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         return !entryCount;
michael@0:     }
michael@0: 
michael@0:     uint32_t count() const
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         return entryCount;
michael@0:     }
michael@0: 
michael@0:     uint32_t capacity() const
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         return JS_BIT(sHashBits - hashShift);
michael@0:     }
michael@0: 
michael@0:     uint32_t generation() const
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         return gen;
michael@0:     }
michael@0: 
michael@0:     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
michael@0:     {
michael@0:         return mallocSizeOf(table);
michael@0:     }
michael@0: 
michael@0:     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const
michael@0:     {
michael@0:         return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0: 
michael@0:     Ptr lookup(const Lookup &l) const
michael@0:     {
michael@0:         mozilla::ReentrancyGuard g(*this);
michael@0:         HashNumber keyHash = prepareHash(l);
michael@0:         return Ptr(lookup(l, keyHash, 0), *this);
michael@0:     }
michael@0: 
michael@0:     Ptr readonlyThreadsafeLookup(const Lookup &l) const
michael@0:     {
michael@0:         HashNumber keyHash = prepareHash(l);
michael@0:         return Ptr(lookup(l, keyHash, 0), *this);
michael@0:     }
michael@0: 
michael@0:     AddPtr lookupForAdd(const Lookup &l) const
michael@0:     {
michael@0:         mozilla::ReentrancyGuard g(*this);
michael@0:         HashNumber keyHash = prepareHash(l);
michael@0:         Entry &entry = lookup(l, keyHash, sCollisionBit);
michael@0:         AddPtr p(entry, *this, keyHash);
michael@0:         return p;
michael@0:     }
michael@0: 
michael@0:     template <class U>
michael@0:     bool add(AddPtr &p, U &&u)
michael@0:     {
michael@0:         mozilla::ReentrancyGuard g(*this);
michael@0:         MOZ_ASSERT(table);
michael@0:         MOZ_ASSERT(!p.found());
michael@0:         MOZ_ASSERT(!(p.keyHash & sCollisionBit));
michael@0: 
michael@0:         // Changing an entry from removed to live does not affect whether we
michael@0:         // are overloaded and can be handled separately.
michael@0:         if (p.entry_->isRemoved()) {
michael@0:             METER(stats.addOverRemoved++);
michael@0:             removedCount--;
michael@0:             p.keyHash |= sCollisionBit;
michael@0:         } else {
michael@0:             // Preserve the validity of |p.entry_|.
michael@0:             RebuildStatus status = checkOverloaded();
michael@0:             if (status == RehashFailed)
michael@0:                 return false;
michael@0:             if (status == Rehashed)
michael@0:                 p.entry_ = &findFreeEntry(p.keyHash);
michael@0:         }
michael@0: 
michael@0:         p.entry_->setLive(p.keyHash, mozilla::Forward<U>(u));
michael@0:         entryCount++;
michael@0:         mutationCount++;
michael@0: #ifdef DEBUG
michael@0:         p.generation = generation();
michael@0:         p.mutationCount = mutationCount;
michael@0: #endif
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Note: |l| may be a reference to a piece of |u|, so this function
michael@0:     // must take care not to use |l| after moving |u|.
michael@0:     template <class U>
michael@0:     void putNewInfallible(const Lookup &l, U &&u)
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0: 
michael@0:         HashNumber keyHash = prepareHash(l);
michael@0:         Entry *entry = &findFreeEntry(keyHash);
michael@0: 
michael@0:         if (entry->isRemoved()) {
michael@0:             METER(stats.addOverRemoved++);
michael@0:             removedCount--;
michael@0:             keyHash |= sCollisionBit;
michael@0:         }
michael@0: 
michael@0:         entry->setLive(keyHash, mozilla::Forward<U>(u));
michael@0:         entryCount++;
michael@0:         mutationCount++;
michael@0:     }
michael@0: 
michael@0:     // Note: |l| may be a reference to a piece of |u|, so this function
michael@0:     // must take care not to use |l| after moving |u|.
michael@0:     template <class U>
michael@0:     bool putNew(const Lookup &l, U &&u)
michael@0:     {
michael@0:         if (checkOverloaded() == RehashFailed)
michael@0:             return false;
michael@0: 
michael@0:         putNewInfallible(l, mozilla::Forward<U>(u));
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Note: |l| may be a reference to a piece of |u|, so this function
michael@0:     // must take care not to use |l| after moving |u|.
michael@0:     template <class U>
michael@0:     bool relookupOrAdd(AddPtr& p, const Lookup &l, U &&u)
michael@0:     {
michael@0: #ifdef DEBUG
michael@0:         p.generation = generation();
michael@0:         p.mutationCount = mutationCount;
michael@0: #endif
michael@0:         {
michael@0:             mozilla::ReentrancyGuard g(*this);
michael@0:             MOZ_ASSERT(prepareHash(l) == p.keyHash); // l has not been destroyed
michael@0:             p.entry_ = &lookup(l, p.keyHash, sCollisionBit);
michael@0:         }
michael@0:         return p.found() || add(p, mozilla::Forward<U>(u));
michael@0:     }
michael@0: 
michael@0:     void remove(Ptr p)
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         mozilla::ReentrancyGuard g(*this);
michael@0:         MOZ_ASSERT(p.found());
michael@0:         remove(*p.entry_);
michael@0:         checkUnderloaded();
michael@0:     }
michael@0: 
michael@0:     void rekeyWithoutRehash(Ptr p, const Lookup &l, const Key &k)
michael@0:     {
michael@0:         MOZ_ASSERT(table);
michael@0:         mozilla::ReentrancyGuard g(*this);
michael@0:         MOZ_ASSERT(p.found());
michael@0:         typename HashTableEntry<T>::NonConstT t(mozilla::Move(*p));
michael@0:         HashPolicy::setKey(t, const_cast<Key &>(k));
michael@0:         remove(*p.entry_);
michael@0:         putNewInfallible(l, mozilla::Move(t));
michael@0:     }
michael@0: 
michael@0:     void rekeyAndMaybeRehash(Ptr p, const Lookup &l, const Key &k)
michael@0:     {
michael@0:         rekeyWithoutRehash(p, l, k);
michael@0:         checkOverRemoved();
michael@0:     }
michael@0: 
michael@0: #undef METER
michael@0: };
michael@0: 
michael@0: }  // namespace detail
michael@0: }  // namespace js
michael@0: 
michael@0: #endif  /* js_HashTable_h */