summaryrefslogtreecommitdiffstats
path: root/js/public/HashTable.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/public/HashTable.h')
-rw-r--r--js/public/HashTable.h1880
1 files changed, 1880 insertions, 0 deletions
diff --git a/js/public/HashTable.h b/js/public/HashTable.h
new file mode 100644
index 000000000..5d4c0665d
--- /dev/null
+++ b/js/public/HashTable.h
@@ -0,0 +1,1880 @@
+/* -*- 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/HashFunctions.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/Move.h"
+#include "mozilla/Opaque.h"
+#include "mozilla/PodOperations.h"
+#include "mozilla/ReentrancyGuard.h"
+#include "mozilla/TemplateLib.h"
+#include "mozilla/TypeTraits.h"
+#include "mozilla/UniquePtr.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;
+} // namespace detail
+
+/*****************************************************************************/
+
+// The "generation" of a hash table is an opaque value indicating the state of
+// modification of the hash table through its lifetime. If the generation of
+// a hash table compares equal at times T1 and T2, then lookups in the hash
+// table, pointers to (or into) hash table entries, etc. at time T1 are valid
+// at time T2. If the generation compares unequal, these computations are all
+// invalid and must be performed again to be used.
+//
+// Generations are meaningfully comparable only with respect to a single hash
+// table. It's always nonsensical to compare the generation of distinct hash
+// tables H1 and H2.
+using Generation = mozilla::Opaque<uint64_t>;
+
+// 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
+ {
+ using Base = 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.
+ explicit HashMap(AllocPolicy a = AllocPolicy()) : impl(a) {}
+ MOZ_MUST_USE 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>
+ MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
+ return impl.add(p,
+ mozilla::Forward<KeyInput>(k),
+ mozilla::Forward<ValueInput>(v));
+ }
+
+ template<typename KeyInput>
+ MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k) {
+ return impl.add(p, mozilla::Forward<KeyInput>(k), Value());
+ }
+
+ template<typename KeyInput, typename ValueInput>
+ MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
+ return impl.relookupOrAdd(p, k,
+ mozilla::Forward<KeyInput>(k),
+ mozilla::Forward<ValueInput>(v));
+ }
+
+ // |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 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);
+ }
+
+ Generation generation() const {
+ return impl.generation();
+ }
+
+ /************************************************** Shorthand operations */
+
+ bool has(const Lookup& l) const {
+ return impl.lookup(l).found();
+ }
+
+ // Overwrite existing value with v. Return false on oom.
+ template<typename KeyInput, typename ValueInput>
+ MOZ_MUST_USE 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>
+ MOZ_MUST_USE bool putNew(KeyInput&& k, ValueInput&& v) {
+ return impl.putNew(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
+ }
+
+ // Only call this to populate an empty map after reserving space with init().
+ template<typename KeyInput, typename ValueInput>
+ void putNewInfallible(KeyInput&& k, ValueInput&& v) {
+ impl.putNewInfallible(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
+ }
+
+ // 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;
+ bool ok = add(p, k, defaultValue);
+ MOZ_ASSERT_IF(!ok, !p); // p is left false-y on oom.
+ (void)ok;
+ 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, and return whether that happened.
+ bool 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);
+ return true;
+ }
+ return false;
+ }
+
+ // 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) = delete;
+ HashMap& operator=(const HashMap& hm) = 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
+ {
+ using Base = 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.
+ explicit HashSet(AllocPolicy a = AllocPolicy()) : impl(a) {}
+ MOZ_MUST_USE 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>
+ MOZ_MUST_USE bool add(AddPtr& p, U&& u) {
+ return impl.add(p, mozilla::Forward<U>(u));
+ }
+
+ template <typename U>
+ MOZ_MUST_USE 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);
+ }
+
+ Generation generation() const {
+ return impl.generation();
+ }
+
+ /************************************************** Shorthand operations */
+
+ bool has(const Lookup& l) const {
+ return impl.lookup(l).found();
+ }
+
+ // Add |u| if it is not present already. Return false on oom.
+ template <typename U>
+ MOZ_MUST_USE 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>
+ MOZ_MUST_USE bool putNew(U&& u) {
+ return impl.putNew(u, mozilla::Forward<U>(u));
+ }
+
+ template <typename U>
+ MOZ_MUST_USE bool putNew(const Lookup& l, U&& u) {
+ return impl.putNew(l, mozilla::Forward<U>(u));
+ }
+
+ // Only call this to populate an empty set after reserving space with init().
+ template <typename U>
+ void putNewInfallible(const Lookup& l, U&& u) {
+ impl.putNewInfallible(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, and return whether that happened.
+ bool 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);
+ return true;
+ }
+ return false;
+ }
+
+ // Infallibly replace the current key at |p| with an equivalent key.
+ // Specifically, both HashPolicy::hash and HashPolicy::match must return
+ // identical results for the new and old key when applied against all
+ // possible matching values.
+ void replaceKey(Ptr p, const T& new_value) {
+ MOZ_ASSERT(p.found());
+ MOZ_ASSERT(*p != new_value);
+ MOZ_ASSERT(HashPolicy::hash(*p) == HashPolicy::hash(new_value));
+ MOZ_ASSERT(HashPolicy::match(*p, new_value));
+ const_cast<T&>(*p) = 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) = delete;
+ HashSet& operator=(const HashSet& hs) = 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) {
+ size_t word = reinterpret_cast<size_t>(l) >> zeroBits;
+ static_assert(sizeof(HashNumber) == 4,
+ "subsequent code assumes a four-byte hash");
+#if JS_BITS_PER_WORD == 32
+ return HashNumber(word);
+#else
+ static_assert(sizeof(word) == 8,
+ "unexpected word size, new hashing strategy required to "
+ "properly incorporate all bits");
+ return HashNumber((word >> 32) ^ word);
+#endif
+ }
+ static bool match(const Key& k, const Lookup& 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>
+{};
+
+// Specialize hashing policy for mozilla::UniquePtr to proxy the UniquePtr's
+// raw pointer to PointerHasher.
+template <class T, class D>
+struct DefaultHasher<mozilla::UniquePtr<T, D>>
+{
+ using Lookup = mozilla::UniquePtr<T, D>;
+ using PtrHasher = PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>;
+
+ static HashNumber hash(const Lookup& l) {
+ return PtrHasher::hash(l.get());
+ }
+ static bool match(const mozilla::UniquePtr<T, D>& k, const Lookup& l) {
+ return PtrHasher::match(k.get(), l.get());
+ }
+ static void rekey(mozilla::UniquePtr<T, D>& k, mozilla::UniquePtr<T, D>&& newKey) {
+ k = mozilla::Move(newKey);
+ }
+};
+
+// For doubles, we can xor the two uint32s.
+template <>
+struct DefaultHasher<double>
+{
+ typedef double Lookup;
+ static HashNumber hash(double d) {
+ static_assert(sizeof(HashNumber) == 4,
+ "subsequent code assumes a four-byte hash");
+ 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) {
+ static_assert(sizeof(HashNumber) == 4,
+ "subsequent code assumes a four-byte hash");
+ 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);
+ }
+};
+
+// A hash policy that compares C strings.
+struct CStringHasher
+{
+ typedef const char* Lookup;
+ static js::HashNumber hash(Lookup l) {
+ return mozilla::HashString(l);
+ }
+ static bool match(const char* key, Lookup lookup) {
+ return strcmp(key, lookup) == 0;
+ }
+};
+
+// Fallible hashing interface.
+//
+// Most of the time generating a hash code is infallible so this class provides
+// default methods that always succeed. Specialize this class for your own hash
+// policy to provide fallible hashing.
+//
+// This is used by MovableCellHasher to handle the fact that generating a unique
+// ID for cell pointer may fail due to OOM.
+template <typename HashPolicy>
+struct FallibleHashMethods
+{
+ // Return true if a hashcode is already available for its argument. Once
+ // this returns true for a specific argument it must continue to do so.
+ template <typename Lookup> static bool hasHash(Lookup&& l) { return true; }
+
+ // Fallible method to ensure a hashcode exists for its argument and create
+ // one if not. Returns false on error, e.g. out of memory.
+ template <typename Lookup> static bool ensureHash(Lookup&& l) { return true; }
+};
+
+template <typename HashPolicy, typename Lookup>
+static bool
+HasHash(Lookup&& l) {
+ return FallibleHashMethods<typename HashPolicy::Base>::hasHash(mozilla::Forward<Lookup>(l));
+}
+
+template <typename HashPolicy, typename Lookup>
+static bool
+EnsureHash(Lookup&& l) {
+ return FallibleHashMethods<typename HashPolicy::Base>::ensureHash(mozilla::Forward<Lookup>(l));
+}
+
+/*****************************************************************************/
+
+// 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;
+
+ 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_))
+ {}
+
+ void operator=(HashMapEntry&& rhs) {
+ key_ = mozilla::Move(rhs.key_);
+ value_ = mozilla::Move(rhs.value_);
+ }
+
+ typedef Key KeyType;
+ typedef Value ValueType;
+
+ const Key& key() const { return key_; }
+ Key& mutableKey() { return key_; }
+ const Value& value() const { return value_; }
+ Value& value() { return value_; }
+
+ private:
+ HashMapEntry(const HashMapEntry&) = delete;
+ void operator=(const HashMapEntry&) = 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&) = delete;
+ void operator=(const HashTableEntry&) = delete;
+ ~HashTableEntry() = 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) {
+ if (this == other)
+ return;
+ MOZ_ASSERT(isLive());
+ if (other->isLive()) {
+ mozilla::Swap(*mem.addr(), *other->mem.addr());
+ } else {
+ *other->mem.addr() = mozilla::Move(*mem.addr());
+ destroy();
+ }
+ mozilla::Swap(keyHash, other->keyHash);
+ }
+
+ T& get() { MOZ_ASSERT(isLive()); return *mem.addr(); }
+ NonConstT& getMutable() { 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 unsetCollision() { keyHash &= ~sCollisionBit; }
+ bool hasCollision() const { return keyHash & sCollisionBit; }
+ bool matchHash(HashNumber hn) { return (keyHash & ~sCollisionBit) == hn; }
+ HashNumber getKeyHash() const { return keyHash & ~sCollisionBit; }
+
+ template <typename... Args>
+ void setLive(HashNumber hn, Args&&... args)
+ {
+ MOZ_ASSERT(!isLive());
+ keyHash = hn;
+ new(mem.addr()) T(mozilla::Forward<Args>(args)...);
+ MOZ_ASSERT(isLive());
+ }
+};
+
+template <class T, class HashPolicy, class AllocPolicy>
+class HashTable : private AllocPolicy
+{
+ friend class mozilla::ReentrancyGuard;
+
+ 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;
+
+ Entry* entry_;
+#ifdef JS_DEBUG
+ const HashTable* table_;
+ Generation generation;
+#endif
+
+ protected:
+ Ptr(Entry& entry, const HashTable& tableArg)
+ : entry_(&entry)
+#ifdef JS_DEBUG
+ , table_(&tableArg)
+ , generation(tableArg.generation())
+#endif
+ {}
+
+ public:
+ Ptr()
+ : entry_(nullptr)
+#ifdef JS_DEBUG
+ , table_(nullptr)
+ , generation(0)
+#endif
+ {}
+
+ bool isValid() const {
+ return !entry_;
+ }
+
+ bool found() const {
+ if (isValid())
+ return false;
+#ifdef JS_DEBUG
+ MOZ_ASSERT(generation == table_->generation());
+#endif
+ return entry_->isLive();
+ }
+
+ explicit operator bool() const {
+ return found();
+ }
+
+ bool operator==(const Ptr& rhs) const {
+ MOZ_ASSERT(found() && rhs.found());
+ return entry_ == rhs.entry_;
+ }
+
+ bool operator!=(const Ptr& rhs) const {
+#ifdef JS_DEBUG
+ MOZ_ASSERT(generation == table_->generation());
+#endif
+ return !(*this == rhs);
+ }
+
+ T& operator*() const {
+#ifdef JS_DEBUG
+ MOZ_ASSERT(found());
+ MOZ_ASSERT(generation == table_->generation());
+#endif
+ return entry_->get();
+ }
+
+ T* operator->() const {
+#ifdef JS_DEBUG
+ MOZ_ASSERT(found());
+ MOZ_ASSERT(generation == table_->generation());
+#endif
+ 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;
+#ifdef JS_DEBUG
+ uint64_t mutationCount;
+#endif
+
+ AddPtr(Entry& entry, const HashTable& tableArg, HashNumber hn)
+ : Ptr(entry, tableArg)
+ , keyHash(hn)
+#ifdef JS_DEBUG
+ , mutationCount(tableArg.mutationCount)
+#endif
+ {}
+
+ public:
+ AddPtr() : keyHash(0) {}
+ };
+
+ // 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 JS_DEBUG
+ , table_(&tableArg)
+ , mutationCount(tableArg.mutationCount)
+ , generation(tableArg.generation())
+ , validEntry(true)
+#endif
+ {
+ while (cur < end && !cur->isLive())
+ ++cur;
+ }
+
+ Entry* cur;
+ Entry* end;
+#ifdef JS_DEBUG
+ const HashTable* table_;
+ uint64_t mutationCount;
+ Generation generation;
+ bool validEntry;
+#endif
+
+ public:
+ Range()
+ : cur(nullptr)
+ , end(nullptr)
+#ifdef JS_DEBUG
+ , table_(nullptr)
+ , mutationCount(0)
+ , generation(0)
+ , validEntry(false)
+#endif
+ {}
+
+ bool empty() const {
+#ifdef JS_DEBUG
+ MOZ_ASSERT(generation == table_->generation());
+ MOZ_ASSERT(mutationCount == table_->mutationCount);
+#endif
+ return cur == end;
+ }
+
+ T& front() const {
+ MOZ_ASSERT(!empty());
+#ifdef JS_DEBUG
+ MOZ_ASSERT(validEntry);
+ MOZ_ASSERT(generation == table_->generation());
+ MOZ_ASSERT(mutationCount == table_->mutationCount);
+#endif
+ return cur->get();
+ }
+
+ void popFront() {
+ MOZ_ASSERT(!empty());
+#ifdef JS_DEBUG
+ MOZ_ASSERT(generation == table_->generation());
+ MOZ_ASSERT(mutationCount == table_->mutationCount);
+#endif
+ while (++cur < end && !cur->isLive())
+ continue;
+#ifdef JS_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&) = delete;
+ void operator=(const Enum&) = 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 JS_DEBUG
+ this->validEntry = false;
+ this->mutationCount = table_.mutationCount;
+#endif
+ }
+
+ NonConstT& mutableFront() {
+ MOZ_ASSERT(!this->empty());
+#ifdef JS_DEBUG
+ MOZ_ASSERT(this->validEntry);
+ MOZ_ASSERT(this->generation == this->Range::table_->generation());
+ MOZ_ASSERT(this->mutationCount == this->Range::table_->mutationCount);
+#endif
+ return this->cur->getMutable();
+ }
+
+ // 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) {
+ MOZ_ASSERT(&k != &HashPolicy::getKey(this->cur->get()));
+ Ptr p(*this->cur, table_);
+ table_.rekeyWithoutRehash(p, l, k);
+ rekeyed = true;
+#ifdef JS_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&) = delete;
+ void operator=(const HashTable&) = delete;
+
+ private:
+ static const size_t CAP_BITS = 30;
+
+ public:
+ uint64_t gen:56; // entry storage generation number
+ uint64_t hashShift:8; // multiplicative hash shift
+ Entry* table; // entry storage
+ uint32_t entryCount; // number of entries in table
+ uint32_t removedCount; // removed entry sentinels in table
+
+#ifdef JS_DEBUG
+ uint64_t mutationCount;
+ mutable bool mEntered;
+ // Note that some updates to these stats are not thread-safe. See the
+ // comment on the three-argument overloading of HashTable::lookup().
+ 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
+
+ // 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(CAP_BITS - 1);
+ static const unsigned sMaxCapacity = JS_BIT(CAP_BITS);
+ 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;
+
+ void setTableSizeLog2(unsigned sizeLog2)
+ {
+ hashShift = sHashBits - sizeLog2;
+ }
+
+ 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;
+ }
+
+ enum FailureBehavior { DontReportFailure = false, ReportFailure = true };
+
+ static Entry* createTable(AllocPolicy& alloc, uint32_t capacity,
+ FailureBehavior reportFailure = ReportFailure)
+ {
+ static_assert(sFreeKey == 0,
+ "newly-calloc'd tables have to be considered empty");
+ if (reportFailure)
+ return alloc.template pod_calloc<Entry>(capacity);
+
+ return alloc.template maybe_pod_calloc<Entry>(capacity);
+ }
+
+ static Entry* maybeCreateTable(AllocPolicy& alloc, uint32_t capacity)
+ {
+ static_assert(sFreeKey == 0,
+ "newly-calloc'd tables have to be considered empty");
+ return alloc.template maybe_pod_calloc<Entry>(capacity);
+ }
+
+ static void destroyTable(AllocPolicy& alloc, Entry* oldTable, uint32_t capacity)
+ {
+ Entry* end = oldTable + capacity;
+ for (Entry* e = oldTable; e < end; ++e)
+ e->destroyIfLive();
+ alloc.free_(oldTable);
+ }
+
+ public:
+ explicit HashTable(AllocPolicy ap)
+ : AllocPolicy(ap)
+ , gen(0)
+ , hashShift(sHashBits)
+ , table(nullptr)
+ , entryCount(0)
+ , removedCount(0)
+#ifdef JS_DEBUG
+ , mutationCount(0)
+ , mEntered(false)
+#endif
+ {}
+
+ MOZ_MUST_USE 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 (MOZ_UNLIKELY(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);
+ }
+
+ // Warning: in order for readonlyThreadsafeLookup() to be safe this
+ // function must not modify the table in any way when |collisionBit| is 0.
+ // (The use of the METER() macro to increment stats violates this
+ // restriction but we will live with that for now because it's enabled so
+ // rarely.)
+ 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 {
+ if (collisionBit == sCollisionBit)
+ entry->setCollision();
+ }
+
+ 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, FailureBehavior reportFailure = ReportFailure)
+ {
+ // 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 (MOZ_UNLIKELY(newCapacity > sMaxCapacity)) {
+ if (reportFailure)
+ this->reportAllocOverflow();
+ return RehashFailed;
+ }
+
+ Entry* newTable = createTable(*this, newCapacity, reportFailure);
+ 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.
+ Entry* end = oldTable + oldCap;
+ for (Entry* src = oldTable; src < end; ++src) {
+ if (src->isLive()) {
+ HashNumber hn = src->getKeyHash();
+ findFreeEntry(hn).setLive(
+ hn, mozilla::Move(const_cast<typename Entry::NonConstT&>(src->get())));
+ src->destroy();
+ }
+ }
+
+ // All entries have been destroyed, no need to destroyTable.
+ this->free_(oldTable);
+ return Rehashed;
+ }
+
+ bool shouldCompressTable()
+ {
+ // Compress if a quarter or more of all entries are removed.
+ return removedCount >= (capacity() >> 2);
+ }
+
+ RebuildStatus checkOverloaded(FailureBehavior reportFailure = ReportFailure)
+ {
+ if (!overloaded())
+ return NotOverloaded;
+
+ int deltaLog2;
+ if (shouldCompressTable()) {
+ METER(stats.compresses++);
+ deltaLog2 = 0;
+ } else {
+ METER(stats.grows++);
+ deltaLog2 = 1;
+ }
+
+ return changeTableSize(deltaLog2, reportFailure);
+ }
+
+ // Infallibly rehash the table if we are overloaded with removals.
+ void checkOverRemoved()
+ {
+ if (overloaded()) {
+ if (checkOverloaded(DontReportFailure) == 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--;
+#ifdef JS_DEBUG
+ mutationCount++;
+#endif
+ }
+
+ void checkUnderloaded()
+ {
+ if (underloaded()) {
+ METER(stats.shrinks++);
+ (void) changeTableSize(-1, DontReportFailure);
+ }
+ }
+
+ // 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)
+ (void) changeTableSize(resizeLog2, DontReportFailure);
+ }
+
+ // 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.
+ }
+
+ // Note: |l| may be a reference to a piece of |u|, so this function
+ // must take care not to use |l| after moving |u|.
+ //
+ // Prefer to use putNewInfallible; this function does not check
+ // invariants.
+ template <typename... Args>
+ void putNewInfallibleInternal(const Lookup& l, Args&&... args)
+ {
+ MOZ_ASSERT(table);
+
+ HashNumber keyHash = prepareHash(l);
+ Entry* entry = &findFreeEntry(keyHash);
+ MOZ_ASSERT(entry);
+
+ if (entry->isRemoved()) {
+ METER(stats.addOverRemoved++);
+ removedCount--;
+ keyHash |= sCollisionBit;
+ }
+
+ entry->setLive(keyHash, mozilla::Forward<Args>(args)...);
+ entryCount++;
+#ifdef JS_DEBUG
+ mutationCount++;
+#endif
+ }
+
+ public:
+ void clear()
+ {
+ if (mozilla::IsPod<Entry>::value) {
+ memset(table, 0, sizeof(*table) * capacity());
+ } else {
+ uint32_t tableCapacity = capacity();
+ Entry* end = table + tableCapacity;
+ for (Entry* e = table; e < end; ++e)
+ e->clear();
+ }
+ removedCount = 0;
+ entryCount = 0;
+#ifdef JS_DEBUG
+ mutationCount++;
+#endif
+ }
+
+ void finish()
+ {
+#ifdef JS_DEBUG
+ MOZ_ASSERT(!mEntered);
+#endif
+ if (!table)
+ return;
+
+ destroyTable(*this, table, capacity());
+ table = nullptr;
+ gen++;
+ entryCount = 0;
+ removedCount = 0;
+#ifdef JS_DEBUG
+ mutationCount++;
+#endif
+ }
+
+ 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);
+ }
+
+ Generation generation() const
+ {
+ MOZ_ASSERT(table);
+ return Generation(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);
+ if (!HasHash<HashPolicy>(l))
+ return Ptr();
+ HashNumber keyHash = prepareHash(l);
+ return Ptr(lookup(l, keyHash, 0), *this);
+ }
+
+ Ptr readonlyThreadsafeLookup(const Lookup& l) const
+ {
+ if (!HasHash<HashPolicy>(l))
+ return Ptr();
+ HashNumber keyHash = prepareHash(l);
+ return Ptr(lookup(l, keyHash, 0), *this);
+ }
+
+ AddPtr lookupForAdd(const Lookup& l) const
+ {
+ mozilla::ReentrancyGuard g(*this);
+ if (!EnsureHash<HashPolicy>(l))
+ return AddPtr();
+ HashNumber keyHash = prepareHash(l);
+ Entry& entry = lookup(l, keyHash, sCollisionBit);
+ AddPtr p(entry, *this, keyHash);
+ return p;
+ }
+
+ template <typename... Args>
+ MOZ_MUST_USE bool add(AddPtr& p, Args&&... args)
+ {
+ mozilla::ReentrancyGuard g(*this);
+ MOZ_ASSERT(table);
+ MOZ_ASSERT(!p.found());
+ MOZ_ASSERT(!(p.keyHash & sCollisionBit));
+
+ // Check for error from ensureHash() here.
+ if (p.isValid())
+ return false;
+
+ // Changing an entry from removed to live does not affect whether we
+ // are overloaded and can be handled separately.
+ if (p.entry_->isRemoved()) {
+ if (!this->checkSimulatedOOM())
+ return false;
+ METER(stats.addOverRemoved++);
+ removedCount--;
+ p.keyHash |= sCollisionBit;
+ } else {
+ // Preserve the validity of |p.entry_|.
+ RebuildStatus status = checkOverloaded();
+ if (status == RehashFailed)
+ return false;
+ if (status == NotOverloaded && !this->checkSimulatedOOM())
+ return false;
+ if (status == Rehashed)
+ p.entry_ = &findFreeEntry(p.keyHash);
+ }
+
+ p.entry_->setLive(p.keyHash, mozilla::Forward<Args>(args)...);
+ entryCount++;
+#ifdef JS_DEBUG
+ mutationCount++;
+ 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 <typename... Args>
+ void putNewInfallible(const Lookup& l, Args&&... args)
+ {
+ MOZ_ASSERT(!lookup(l).found());
+ mozilla::ReentrancyGuard g(*this);
+ putNewInfallibleInternal(l, mozilla::Forward<Args>(args)...);
+ }
+
+ // Note: |l| may be alias arguments in |args|, so this function must take
+ // care not to use |l| after moving |args|.
+ template <typename... Args>
+ MOZ_MUST_USE bool putNew(const Lookup& l, Args&&... args)
+ {
+ if (!this->checkSimulatedOOM())
+ return false;
+
+ if (!EnsureHash<HashPolicy>(l))
+ return false;
+
+ if (checkOverloaded() == RehashFailed)
+ return false;
+
+ putNewInfallible(l, mozilla::Forward<Args>(args)...);
+ 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 <typename... Args>
+ MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, const Lookup& l, Args&&... args)
+ {
+ // Check for error from ensureHash() here.
+ if (p.isValid())
+ return false;
+
+#ifdef JS_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<Args>(args)...);
+ }
+
+ 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_);
+ putNewInfallibleInternal(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 */