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