Changeset View
Changeset View
Standalone View
Standalone View
libraries/source/spidermonkey/include-win32-debug/js/HashTable.h
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | ||||
* vim: set ts=8 sts=4 et sw=4 tw=99: | * vim: set ts=8 sts=4 et sw=4 tw=99: | ||||
* This Source Code Form is subject to the terms of the Mozilla Public | * 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 | * 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/. */ | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | ||||
#ifndef js_HashTable_h | #ifndef js_HashTable_h | ||||
#define js_HashTable_h | #define js_HashTable_h | ||||
#include "mozilla/Alignment.h" | #include "mozilla/Alignment.h" | ||||
#include "mozilla/Assertions.h" | #include "mozilla/Assertions.h" | ||||
#include "mozilla/Attributes.h" | #include "mozilla/Attributes.h" | ||||
#include "mozilla/Casting.h" | #include "mozilla/Casting.h" | ||||
#include "mozilla/HashFunctions.h" | |||||
#include "mozilla/MemoryReporting.h" | #include "mozilla/MemoryReporting.h" | ||||
#include "mozilla/Move.h" | #include "mozilla/Move.h" | ||||
#include "mozilla/Opaque.h" | #include "mozilla/Opaque.h" | ||||
#include "mozilla/PodOperations.h" | #include "mozilla/PodOperations.h" | ||||
#include "mozilla/ReentrancyGuard.h" | #include "mozilla/ReentrancyGuard.h" | ||||
#include "mozilla/TemplateLib.h" | #include "mozilla/TemplateLib.h" | ||||
#include "mozilla/TypeTraits.h" | #include "mozilla/TypeTraits.h" | ||||
#include "mozilla/UniquePtr.h" | #include "mozilla/UniquePtr.h" | ||||
#include "js/Utility.h" | #include "js/Utility.h" | ||||
namespace js { | namespace js { | ||||
class TempAllocPolicy; | class TempAllocPolicy; | ||||
template <class> struct DefaultHasher; | template <class> struct DefaultHasher; | ||||
template <class, class> class HashMapEntry; | template <class, class> class HashMapEntry; | ||||
namespace detail { | namespace detail { | ||||
template <class T> class HashTableEntry; | template <class T> class HashTableEntry; | ||||
template <class T, class HashPolicy, class AllocPolicy> class HashTable; | template <class T, class HashPolicy, class AllocPolicy> class HashTable; | ||||
} // namespace detail | } // 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>; | using Generation = mozilla::Opaque<uint64_t>; | ||||
// A JS-friendly, STL-like container providing a hash-based map from keys to | // A JS-friendly, STL-like container providing a hash-based map from keys to | ||||
// values. In particular, HashMap calls constructors and destructors of all | // values. In particular, HashMap calls constructors and destructors of all | ||||
// objects added so non-PODs may be used safely. | // objects added so non-PODs may be used safely. | ||||
// | // | ||||
// Key/Value requirements: | // Key/Value requirements: | ||||
// - movable, destructible, assignable | // - movable, destructible, assignable | ||||
Show All 11 Lines | template <class Key, | ||||
class HashPolicy = DefaultHasher<Key>, | class HashPolicy = DefaultHasher<Key>, | ||||
class AllocPolicy = TempAllocPolicy> | class AllocPolicy = TempAllocPolicy> | ||||
class HashMap | class HashMap | ||||
{ | { | ||||
typedef HashMapEntry<Key, Value> TableEntry; | typedef HashMapEntry<Key, Value> TableEntry; | ||||
struct MapHashPolicy : HashPolicy | struct MapHashPolicy : HashPolicy | ||||
{ | { | ||||
using Base = HashPolicy; | |||||
typedef Key KeyType; | typedef Key KeyType; | ||||
static const Key& getKey(TableEntry& e) { return e.key(); } | static const Key& getKey(TableEntry& e) { return e.key(); } | ||||
static void setKey(TableEntry& e, Key& k) { HashPolicy::rekey(e.mutableKey(), k); } | static void setKey(TableEntry& e, Key& k) { HashPolicy::rekey(e.mutableKey(), k); } | ||||
}; | }; | ||||
typedef detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy> Impl; | typedef detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy> Impl; | ||||
Impl impl; | Impl impl; | ||||
public: | public: | ||||
typedef typename HashPolicy::Lookup Lookup; | typedef typename HashPolicy::Lookup Lookup; | ||||
typedef TableEntry Entry; | typedef TableEntry Entry; | ||||
// HashMap construction is fallible (due to OOM); thus the user must call | // HashMap construction is fallible (due to OOM); thus the user must call | ||||
// init after constructing a HashMap and check the return value. | // init after constructing a HashMap and check the return value. | ||||
explicit HashMap(AllocPolicy a = AllocPolicy()) : impl(a) {} | explicit HashMap(AllocPolicy a = AllocPolicy()) : impl(a) {} | ||||
bool init(uint32_t len = 16) { return impl.init(len); } | MOZ_MUST_USE bool init(uint32_t len = 16) { return impl.init(len); } | ||||
bool initialized() const { return impl.initialized(); } | bool initialized() const { return impl.initialized(); } | ||||
// Return whether the given lookup value is present in the map. E.g.: | // Return whether the given lookup value is present in the map. E.g.: | ||||
// | // | ||||
// typedef HashMap<int,char> HM; | // typedef HashMap<int,char> HM; | ||||
// HM h; | // HM h; | ||||
// if (HM::Ptr p = h.lookup(3)) { | // if (HM::Ptr p = h.lookup(3)) { | ||||
// const HM::Entry& e = *p; // p acts like a pointer to Entry | // const HM::Entry& e = *p; // p acts like a pointer to Entry | ||||
// assert(p->key == 3); // Entry contains the key | // assert(p->key == 3); // Entry contains the key | ||||
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines | public: | ||||
// assert(p->key == 3); | // assert(p->key == 3); | ||||
// char val = p->value; | // char val = p->value; | ||||
typedef typename Impl::AddPtr AddPtr; | typedef typename Impl::AddPtr AddPtr; | ||||
AddPtr lookupForAdd(const Lookup& l) const { | AddPtr lookupForAdd(const Lookup& l) const { | ||||
return impl.lookupForAdd(l); | return impl.lookupForAdd(l); | ||||
} | } | ||||
template<typename KeyInput, typename ValueInput> | template<typename KeyInput, typename ValueInput> | ||||
bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) { | MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) { | ||||
return impl.add(p, | return impl.add(p, | ||||
mozilla::Forward<KeyInput>(k), | mozilla::Forward<KeyInput>(k), | ||||
mozilla::Forward<ValueInput>(v)); | mozilla::Forward<ValueInput>(v)); | ||||
} | } | ||||
template<typename KeyInput> | template<typename KeyInput> | ||||
bool add(AddPtr& p, KeyInput&& k) { | MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k) { | ||||
return impl.add(p, mozilla::Forward<KeyInput>(k), Value()); | return impl.add(p, mozilla::Forward<KeyInput>(k), Value()); | ||||
} | } | ||||
template<typename KeyInput, typename ValueInput> | template<typename KeyInput, typename ValueInput> | ||||
bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) { | MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) { | ||||
return impl.relookupOrAdd(p, k, | return impl.relookupOrAdd(p, k, | ||||
mozilla::Forward<KeyInput>(k), | mozilla::Forward<KeyInput>(k), | ||||
mozilla::Forward<ValueInput>(v)); | mozilla::Forward<ValueInput>(v)); | ||||
} | } | ||||
// |all()| returns a Range containing |count()| elements. E.g.: | // |all()| returns a Range containing |count()| elements. E.g.: | ||||
// | // | ||||
// typedef HashMap<int,char> HM; | // typedef HashMap<int,char> HM; | ||||
Show All 40 Lines | public: | ||||
// guarantee that |impl| is the first field in HashMap. | // guarantee that |impl| is the first field in HashMap. | ||||
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | ||||
return impl.sizeOfExcludingThis(mallocSizeOf); | return impl.sizeOfExcludingThis(mallocSizeOf); | ||||
} | } | ||||
size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | ||||
return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf); | return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf); | ||||
} | } | ||||
// If |generation()| is the same before and after a HashMap operation, | |||||
// pointers into the table remain valid. | |||||
Generation generation() const { | Generation generation() const { | ||||
return impl.generation(); | return impl.generation(); | ||||
} | } | ||||
/************************************************** Shorthand operations */ | /************************************************** Shorthand operations */ | ||||
bool has(const Lookup& l) const { | bool has(const Lookup& l) const { | ||||
return impl.lookup(l).found(); | return impl.lookup(l).found(); | ||||
} | } | ||||
// Overwrite existing value with v. Return false on oom. | // Overwrite existing value with v. Return false on oom. | ||||
template<typename KeyInput, typename ValueInput> | template<typename KeyInput, typename ValueInput> | ||||
bool put(KeyInput&& k, ValueInput&& v) { | MOZ_MUST_USE bool put(KeyInput&& k, ValueInput&& v) { | ||||
AddPtr p = lookupForAdd(k); | AddPtr p = lookupForAdd(k); | ||||
if (p) { | if (p) { | ||||
p->value() = mozilla::Forward<ValueInput>(v); | p->value() = mozilla::Forward<ValueInput>(v); | ||||
return true; | return true; | ||||
} | } | ||||
return add(p, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v)); | return add(p, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v)); | ||||
} | } | ||||
// Like put, but assert that the given key is not already present. | // Like put, but assert that the given key is not already present. | ||||
template<typename KeyInput, typename ValueInput> | template<typename KeyInput, typename ValueInput> | ||||
bool putNew(KeyInput&& k, ValueInput&& v) { | MOZ_MUST_USE bool putNew(KeyInput&& k, ValueInput&& v) { | ||||
return impl.putNew(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<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(). | // Only call this to populate an empty map after reserving space with init(). | ||||
template<typename KeyInput, typename ValueInput> | template<typename KeyInput, typename ValueInput> | ||||
void putNewInfallible(KeyInput&& k, ValueInput&& v) { | void putNewInfallible(KeyInput&& k, ValueInput&& v) { | ||||
impl.putNewInfallible(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<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. | // Add (k,defaultValue) if |k| is not found. Return a false-y Ptr on oom. | ||||
Ptr lookupWithDefault(const Key& k, const Value& defaultValue) { | Ptr lookupWithDefault(const Key& k, const Value& defaultValue) { | ||||
AddPtr p = lookupForAdd(k); | AddPtr p = lookupForAdd(k); | ||||
if (p) | if (p) | ||||
return p; | return p; | ||||
(void)add(p, k, defaultValue); // p is left false-y on oom. | bool ok = add(p, k, defaultValue); | ||||
MOZ_ASSERT_IF(!ok, !p); // p is left false-y on oom. | |||||
(void)ok; | |||||
return p; | return p; | ||||
} | } | ||||
// Remove if present. | // Remove if present. | ||||
void remove(const Lookup& l) { | void remove(const Lookup& l) { | ||||
if (Ptr p = lookup(l)) | if (Ptr p = lookup(l)) | ||||
remove(p); | remove(p); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 48 Lines • ▼ Show 20 Lines | |||||
// - Due to the lack of exception handling, the user must call |init()|. | // - Due to the lack of exception handling, the user must call |init()|. | ||||
template <class T, | template <class T, | ||||
class HashPolicy = DefaultHasher<T>, | class HashPolicy = DefaultHasher<T>, | ||||
class AllocPolicy = TempAllocPolicy> | class AllocPolicy = TempAllocPolicy> | ||||
class HashSet | class HashSet | ||||
{ | { | ||||
struct SetOps : HashPolicy | struct SetOps : HashPolicy | ||||
{ | { | ||||
using Base = HashPolicy; | |||||
typedef T KeyType; | typedef T KeyType; | ||||
static const KeyType& getKey(const T& t) { return t; } | static const KeyType& getKey(const T& t) { return t; } | ||||
static void setKey(T& t, KeyType& k) { HashPolicy::rekey(t, k); } | static void setKey(T& t, KeyType& k) { HashPolicy::rekey(t, k); } | ||||
}; | }; | ||||
typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl; | typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl; | ||||
Impl impl; | Impl impl; | ||||
public: | public: | ||||
typedef typename HashPolicy::Lookup Lookup; | typedef typename HashPolicy::Lookup Lookup; | ||||
typedef T Entry; | typedef T Entry; | ||||
// HashSet construction is fallible (due to OOM); thus the user must call | // HashSet construction is fallible (due to OOM); thus the user must call | ||||
// init after constructing a HashSet and check the return value. | // init after constructing a HashSet and check the return value. | ||||
explicit HashSet(AllocPolicy a = AllocPolicy()) : impl(a) {} | explicit HashSet(AllocPolicy a = AllocPolicy()) : impl(a) {} | ||||
bool init(uint32_t len = 16) { return impl.init(len); } | MOZ_MUST_USE bool init(uint32_t len = 16) { return impl.init(len); } | ||||
bool initialized() const { return impl.initialized(); } | bool initialized() const { return impl.initialized(); } | ||||
// Return whether the given lookup value is present in the map. E.g.: | // Return whether the given lookup value is present in the map. E.g.: | ||||
// | // | ||||
// typedef HashSet<int> HS; | // typedef HashSet<int> HS; | ||||
// HS h; | // HS h; | ||||
// if (HS::Ptr p = h.lookup(3)) { | // if (HS::Ptr p = h.lookup(3)) { | ||||
// assert(*p == 3); // p acts like a pointer to int | // assert(*p == 3); // p acts like a pointer to int | ||||
// } | // } | ||||
Show All 40 Lines | public: | ||||
// assert(*p == 3); | // assert(*p == 3); | ||||
// | // | ||||
// Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the | // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the | ||||
// entry |t|, where the caller ensures match(l,t). | // entry |t|, where the caller ensures match(l,t). | ||||
typedef typename Impl::AddPtr AddPtr; | typedef typename Impl::AddPtr AddPtr; | ||||
AddPtr lookupForAdd(const Lookup& l) const { return impl.lookupForAdd(l); } | AddPtr lookupForAdd(const Lookup& l) const { return impl.lookupForAdd(l); } | ||||
template <typename U> | template <typename U> | ||||
bool add(AddPtr& p, U&& u) { | MOZ_MUST_USE bool add(AddPtr& p, U&& u) { | ||||
return impl.add(p, mozilla::Forward<U>(u)); | return impl.add(p, mozilla::Forward<U>(u)); | ||||
} | } | ||||
template <typename U> | template <typename U> | ||||
bool relookupOrAdd(AddPtr& p, const Lookup& l, U&& u) { | MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, const Lookup& l, U&& u) { | ||||
return impl.relookupOrAdd(p, l, mozilla::Forward<U>(u)); | return impl.relookupOrAdd(p, l, mozilla::Forward<U>(u)); | ||||
} | } | ||||
// |all()| returns a Range containing |count()| elements: | // |all()| returns a Range containing |count()| elements: | ||||
// | // | ||||
// typedef HashSet<int> HS; | // typedef HashSet<int> HS; | ||||
// HS h; | // HS h; | ||||
// for (HS::Range r = h.all(); !r.empty(); r.popFront()) | // for (HS::Range r = h.all(); !r.empty(); r.popFront()) | ||||
Show All 38 Lines | public: | ||||
// guarantee that |impl| is the first field in HashSet. | // guarantee that |impl| is the first field in HashSet. | ||||
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | ||||
return impl.sizeOfExcludingThis(mallocSizeOf); | return impl.sizeOfExcludingThis(mallocSizeOf); | ||||
} | } | ||||
size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { | ||||
return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf); | return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf); | ||||
} | } | ||||
// If |generation()| is the same before and after a HashSet operation, | |||||
// pointers into the table remain valid. | |||||
Generation generation() const { | Generation generation() const { | ||||
return impl.generation(); | return impl.generation(); | ||||
} | } | ||||
/************************************************** Shorthand operations */ | /************************************************** Shorthand operations */ | ||||
bool has(const Lookup& l) const { | bool has(const Lookup& l) const { | ||||
return impl.lookup(l).found(); | return impl.lookup(l).found(); | ||||
} | } | ||||
// Add |u| if it is not present already. Return false on oom. | // Add |u| if it is not present already. Return false on oom. | ||||
template <typename U> | template <typename U> | ||||
bool put(U&& u) { | MOZ_MUST_USE bool put(U&& u) { | ||||
AddPtr p = lookupForAdd(u); | AddPtr p = lookupForAdd(u); | ||||
return p ? true : add(p, mozilla::Forward<U>(u)); | return p ? true : add(p, mozilla::Forward<U>(u)); | ||||
} | } | ||||
// Like put, but assert that the given key is not already present. | // Like put, but assert that the given key is not already present. | ||||
template <typename U> | template <typename U> | ||||
bool putNew(U&& u) { | MOZ_MUST_USE bool putNew(U&& u) { | ||||
return impl.putNew(u, mozilla::Forward<U>(u)); | return impl.putNew(u, mozilla::Forward<U>(u)); | ||||
} | } | ||||
template <typename U> | template <typename U> | ||||
bool putNew(const Lookup& l, U&& u) { | MOZ_MUST_USE bool putNew(const Lookup& l, U&& u) { | ||||
return impl.putNew(l, mozilla::Forward<U>(u)); | return impl.putNew(l, mozilla::Forward<U>(u)); | ||||
} | } | ||||
// Only call this to populate an empty set after reserving space with init(). | // Only call this to populate an empty set after reserving space with init(). | ||||
template <typename U> | template <typename U> | ||||
void putNewInfallible(const Lookup& l, U&& u) { | void putNewInfallible(const Lookup& l, U&& u) { | ||||
impl.putNewInfallible(l, mozilla::Forward<U>(u)); | impl.putNewInfallible(l, mozilla::Forward<U>(u)); | ||||
} | } | ||||
Show All 14 Lines | public: | ||||
bool rekeyAs(const Lookup& old_lookup, const Lookup& new_lookup, const T& new_value) { | bool rekeyAs(const Lookup& old_lookup, const Lookup& new_lookup, const T& new_value) { | ||||
if (Ptr p = lookup(old_lookup)) { | if (Ptr p = lookup(old_lookup)) { | ||||
impl.rekeyAndMaybeRehash(p, new_lookup, new_value); | impl.rekeyAndMaybeRehash(p, new_lookup, new_value); | ||||
return true; | return true; | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
// Infallibly rekey one entry with a new key that is equivalent. | // Infallibly replace the current key at |p| with an equivalent key. | ||||
void rekeyInPlace(Ptr p, const T& new_value) | // 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)); | MOZ_ASSERT(HashPolicy::match(*p, new_value)); | ||||
impl.rekeyInPlace(p, new_value); | const_cast<T&>(*p) = new_value; | ||||
} | } | ||||
// HashSet is movable | // HashSet is movable | ||||
HashSet(HashSet&& rhs) : impl(mozilla::Move(rhs.impl)) {} | HashSet(HashSet&& rhs) : impl(mozilla::Move(rhs.impl)) {} | ||||
void operator=(HashSet&& rhs) { | void operator=(HashSet&& rhs) { | ||||
MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); | MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); | ||||
impl = mozilla::Move(rhs.impl); | impl = mozilla::Move(rhs.impl); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 82 Lines • ▼ Show 20 Lines | |||||
}; | }; | ||||
// Specialize hashing policy for pointer types. It assumes that the type is | // Specialize hashing policy for pointer types. It assumes that the type is | ||||
// at least word-aligned. For types with smaller size use PointerHasher. | // at least word-aligned. For types with smaller size use PointerHasher. | ||||
template <class T> | template <class T> | ||||
struct DefaultHasher<T*> : PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value> | struct DefaultHasher<T*> : PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value> | ||||
{}; | {}; | ||||
// Specialize hashing policy for mozilla::UniquePtr<T> to proxy the UniquePtr's | // Specialize hashing policy for mozilla::UniquePtr to proxy the UniquePtr's | ||||
// raw pointer to PointerHasher. | // raw pointer to PointerHasher. | ||||
template <class T> | template <class T, class D> | ||||
struct DefaultHasher<mozilla::UniquePtr<T>> | struct DefaultHasher<mozilla::UniquePtr<T, D>> | ||||
{ | { | ||||
using Lookup = mozilla::UniquePtr<T>; | using Lookup = mozilla::UniquePtr<T, D>; | ||||
using PtrHasher = PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>; | using PtrHasher = PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>; | ||||
static HashNumber hash(const Lookup& l) { | static HashNumber hash(const Lookup& l) { | ||||
return PtrHasher::hash(l.get()); | return PtrHasher::hash(l.get()); | ||||
} | } | ||||
static bool match(const mozilla::UniquePtr<T>& k, const Lookup& l) { | static bool match(const mozilla::UniquePtr<T, D>& k, const Lookup& l) { | ||||
return PtrHasher::match(k.get(), l.get()); | return PtrHasher::match(k.get(), l.get()); | ||||
} | } | ||||
static void rekey(mozilla::UniquePtr<T>& k, mozilla::UniquePtr<T>&& newKey) { | static void rekey(mozilla::UniquePtr<T, D>& k, mozilla::UniquePtr<T, D>&& newKey) { | ||||
k = mozilla::Move(newKey); | k = mozilla::Move(newKey); | ||||
} | } | ||||
}; | }; | ||||
// For doubles, we can xor the two uint32s. | // For doubles, we can xor the two uint32s. | ||||
template <> | template <> | ||||
struct DefaultHasher<double> | struct DefaultHasher<double> | ||||
{ | { | ||||
Show All 18 Lines | static HashNumber hash(float f) { | ||||
"subsequent code assumes a four-byte hash"); | "subsequent code assumes a four-byte hash"); | ||||
return HashNumber(mozilla::BitwiseCast<uint32_t>(f)); | return HashNumber(mozilla::BitwiseCast<uint32_t>(f)); | ||||
} | } | ||||
static bool match(float lhs, float rhs) { | static bool match(float lhs, float rhs) { | ||||
return mozilla::BitwiseCast<uint32_t>(lhs) == mozilla::BitwiseCast<uint32_t>(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 | // Both HashMap and HashSet are implemented by a single HashTable that is even | ||||
// more heavily parameterized than the other two. This leaves HashTable gnarly | // more heavily parameterized than the other two. This leaves HashTable gnarly | ||||
// and extremely coupled to HashMap and HashSet; thus code should not use | // and extremely coupled to HashMap and HashSet; thus code should not use | ||||
// HashTable directly. | // HashTable directly. | ||||
template <class Key, class Value> | template <class Key, class Value> | ||||
Show All 13 Lines | HashMapEntry(KeyInput&& k, ValueInput&& v) | ||||
value_(mozilla::Forward<ValueInput>(v)) | value_(mozilla::Forward<ValueInput>(v)) | ||||
{} | {} | ||||
HashMapEntry(HashMapEntry&& rhs) | HashMapEntry(HashMapEntry&& rhs) | ||||
: key_(mozilla::Move(rhs.key_)), | : key_(mozilla::Move(rhs.key_)), | ||||
value_(mozilla::Move(rhs.value_)) | value_(mozilla::Move(rhs.value_)) | ||||
{} | {} | ||||
void operator=(HashMapEntry&& rhs) { | |||||
key_ = mozilla::Move(rhs.key_); | |||||
value_ = mozilla::Move(rhs.value_); | |||||
} | |||||
typedef Key KeyType; | typedef Key KeyType; | ||||
typedef Value ValueType; | typedef Value ValueType; | ||||
const Key& key() const { return key_; } | const Key& key() const { return key_; } | ||||
Key& mutableKey() { return key_; } | Key& mutableKey() { return key_; } | ||||
const Value& value() const { return value_; } | const Value& value() const { return value_; } | ||||
Value& value() { return value_; } | Value& value() { return value_; } | ||||
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines | public: | ||||
} | } | ||||
void destroy() { | void destroy() { | ||||
MOZ_ASSERT(isLive()); | MOZ_ASSERT(isLive()); | ||||
mem.addr()->~T(); | mem.addr()->~T(); | ||||
} | } | ||||
void swap(HashTableEntry* other) { | 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); | mozilla::Swap(keyHash, other->keyHash); | ||||
mozilla::Swap(mem, other->mem); | |||||
} | } | ||||
T& get() { MOZ_ASSERT(isLive()); return *mem.addr(); } | T& get() { MOZ_ASSERT(isLive()); return *mem.addr(); } | ||||
NonConstT& getMutable() { MOZ_ASSERT(isLive()); return *mem.addr(); } | NonConstT& getMutable() { MOZ_ASSERT(isLive()); return *mem.addr(); } | ||||
bool isFree() const { return keyHash == sFreeKey; } | bool isFree() const { return keyHash == sFreeKey; } | ||||
void clearLive() { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); } | void clearLive() { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); } | ||||
void clear() { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; } | void clear() { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; } | ||||
▲ Show 20 Lines • Show All 47 Lines • ▼ Show 20 Lines | #endif | ||||
: entry_(&entry) | : entry_(&entry) | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
, table_(&tableArg) | , table_(&tableArg) | ||||
, generation(tableArg.generation()) | , generation(tableArg.generation()) | ||||
#endif | #endif | ||||
{} | {} | ||||
public: | public: | ||||
// Leaves Ptr uninitialized. | Ptr() | ||||
Ptr() { | : entry_(nullptr) | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
entry_ = (Entry*)0xbad; | , table_(nullptr) | ||||
, generation(0) | |||||
#endif | #endif | ||||
{} | |||||
bool isValid() const { | |||||
return !entry_; | |||||
} | } | ||||
bool found() const { | bool found() const { | ||||
if (isValid()) | |||||
return false; | |||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
MOZ_ASSERT(generation == table_->generation()); | MOZ_ASSERT(generation == table_->generation()); | ||||
#endif | #endif | ||||
return entry_->isLive(); | return entry_->isLive(); | ||||
} | } | ||||
explicit operator bool() const { | explicit operator bool() const { | ||||
return found(); | return found(); | ||||
} | } | ||||
bool operator==(const Ptr& rhs) const { | bool operator==(const Ptr& rhs) const { | ||||
MOZ_ASSERT(found() && rhs.found()); | MOZ_ASSERT(found() && rhs.found()); | ||||
return entry_ == rhs.entry_; | return entry_ == rhs.entry_; | ||||
} | } | ||||
bool operator!=(const Ptr& rhs) const { | bool operator!=(const Ptr& rhs) const { | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
MOZ_ASSERT(generation == table_->generation()); | MOZ_ASSERT(generation == table_->generation()); | ||||
#endif | #endif | ||||
return !(*this == rhs); | return !(*this == rhs); | ||||
} | } | ||||
T& operator*() const { | T& operator*() const { | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
MOZ_ASSERT(found()); | |||||
MOZ_ASSERT(generation == table_->generation()); | MOZ_ASSERT(generation == table_->generation()); | ||||
#endif | #endif | ||||
return entry_->get(); | return entry_->get(); | ||||
} | } | ||||
T* operator->() const { | T* operator->() const { | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
MOZ_ASSERT(found()); | |||||
MOZ_ASSERT(generation == table_->generation()); | MOZ_ASSERT(generation == table_->generation()); | ||||
#endif | #endif | ||||
return &entry_->get(); | return &entry_->get(); | ||||
} | } | ||||
}; | }; | ||||
// A Ptr that can be used to add a key after a failed lookup. | // A Ptr that can be used to add a key after a failed lookup. | ||||
class AddPtr : public Ptr | class AddPtr : public Ptr | ||||
{ | { | ||||
friend class HashTable; | friend class HashTable; | ||||
HashNumber keyHash; | HashNumber keyHash; | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
uint64_t mutationCount; | uint64_t mutationCount; | ||||
#endif | #endif | ||||
AddPtr(Entry& entry, const HashTable& tableArg, HashNumber hn) | AddPtr(Entry& entry, const HashTable& tableArg, HashNumber hn) | ||||
: Ptr(entry, tableArg) | : Ptr(entry, tableArg) | ||||
, keyHash(hn) | , keyHash(hn) | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
, mutationCount(tableArg.mutationCount) | , mutationCount(tableArg.mutationCount) | ||||
#endif | #endif | ||||
{} | {} | ||||
public: | public: | ||||
// Leaves AddPtr uninitialized. | AddPtr() : keyHash(0) {} | ||||
AddPtr() {} | |||||
}; | }; | ||||
// A collection of hash table entries. The collection is enumerated by | // A collection of hash table entries. The collection is enumerated by | ||||
// calling |front()| followed by |popFront()| as long as |!empty()|. As | // calling |front()| followed by |popFront()| as long as |!empty()|. As | ||||
// with Ptr/AddPtr, Range objects must not be used after any mutating hash | // with Ptr/AddPtr, Range objects must not be used after any mutating hash | ||||
// table operation unless the |generation()| is tested. | // table operation unless the |generation()| is tested. | ||||
class Range | class Range | ||||
{ | { | ||||
▲ Show 20 Lines • Show All 273 Lines • ▼ Show 20 Lines | explicit HashTable(AllocPolicy ap) | ||||
, entryCount(0) | , entryCount(0) | ||||
, removedCount(0) | , removedCount(0) | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
, mutationCount(0) | , mutationCount(0) | ||||
, mEntered(false) | , mEntered(false) | ||||
#endif | #endif | ||||
{} | {} | ||||
MOZ_WARN_UNUSED_RESULT bool init(uint32_t length) | MOZ_MUST_USE bool init(uint32_t length) | ||||
{ | { | ||||
MOZ_ASSERT(!initialized()); | MOZ_ASSERT(!initialized()); | ||||
// Reject all lengths whose initial computed capacity would exceed | // Reject all lengths whose initial computed capacity would exceed | ||||
// sMaxCapacity. Round that maximum length down to the nearest power | // sMaxCapacity. Round that maximum length down to the nearest power | ||||
// of two for speedier code. | // of two for speedier code. | ||||
if (MOZ_UNLIKELY(length > sMaxInit)) { | if (MOZ_UNLIKELY(length > sMaxInit)) { | ||||
this->reportAllocOverflow(); | this->reportAllocOverflow(); | ||||
▲ Show 20 Lines • Show All 353 Lines • ▼ Show 20 Lines | void rehashTableInPlace() | ||||
// TODO: this algorithm leaves collision bits on *all* elements, even if | // TODO: this algorithm leaves collision bits on *all* elements, even if | ||||
// they are on no collision path. We have the option of setting the | // they are on no collision path. We have the option of setting the | ||||
// collision bits correctly on a subsequent pass or skipping the rehash | // collision bits correctly on a subsequent pass or skipping the rehash | ||||
// unless we are totally filled with tombstones: benchmark to find out | // unless we are totally filled with tombstones: benchmark to find out | ||||
// which approach is best. | // 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: | public: | ||||
void clear() | void clear() | ||||
{ | { | ||||
if (mozilla::IsPod<Entry>::value) { | if (mozilla::IsPod<Entry>::value) { | ||||
memset(table, 0, sizeof(*table) * capacity()); | memset(table, 0, sizeof(*table) * capacity()); | ||||
} else { | } else { | ||||
uint32_t tableCapacity = capacity(); | uint32_t tableCapacity = capacity(); | ||||
Entry* end = table + tableCapacity; | Entry* end = table + tableCapacity; | ||||
▲ Show 20 Lines • Show All 63 Lines • ▼ Show 20 Lines | #endif | ||||
size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const | size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const | ||||
{ | { | ||||
return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf); | return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf); | ||||
} | } | ||||
Ptr lookup(const Lookup& l) const | Ptr lookup(const Lookup& l) const | ||||
{ | { | ||||
mozilla::ReentrancyGuard g(*this); | mozilla::ReentrancyGuard g(*this); | ||||
if (!HasHash<HashPolicy>(l)) | |||||
return Ptr(); | |||||
HashNumber keyHash = prepareHash(l); | HashNumber keyHash = prepareHash(l); | ||||
return Ptr(lookup(l, keyHash, 0), *this); | return Ptr(lookup(l, keyHash, 0), *this); | ||||
} | } | ||||
Ptr readonlyThreadsafeLookup(const Lookup& l) const | Ptr readonlyThreadsafeLookup(const Lookup& l) const | ||||
{ | { | ||||
if (!HasHash<HashPolicy>(l)) | |||||
return Ptr(); | |||||
HashNumber keyHash = prepareHash(l); | HashNumber keyHash = prepareHash(l); | ||||
return Ptr(lookup(l, keyHash, 0), *this); | return Ptr(lookup(l, keyHash, 0), *this); | ||||
} | } | ||||
AddPtr lookupForAdd(const Lookup& l) const | AddPtr lookupForAdd(const Lookup& l) const | ||||
{ | { | ||||
mozilla::ReentrancyGuard g(*this); | mozilla::ReentrancyGuard g(*this); | ||||
if (!EnsureHash<HashPolicy>(l)) | |||||
return AddPtr(); | |||||
HashNumber keyHash = prepareHash(l); | HashNumber keyHash = prepareHash(l); | ||||
Entry& entry = lookup(l, keyHash, sCollisionBit); | Entry& entry = lookup(l, keyHash, sCollisionBit); | ||||
AddPtr p(entry, *this, keyHash); | AddPtr p(entry, *this, keyHash); | ||||
return p; | return p; | ||||
} | } | ||||
template <typename... Args> | template <typename... Args> | ||||
bool add(AddPtr& p, Args&&... args) | MOZ_MUST_USE bool add(AddPtr& p, Args&&... args) | ||||
{ | { | ||||
mozilla::ReentrancyGuard g(*this); | mozilla::ReentrancyGuard g(*this); | ||||
MOZ_ASSERT(table); | MOZ_ASSERT(table); | ||||
MOZ_ASSERT(!p.found()); | MOZ_ASSERT(!p.found()); | ||||
MOZ_ASSERT(!(p.keyHash & sCollisionBit)); | 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 | // Changing an entry from removed to live does not affect whether we | ||||
// are overloaded and can be handled separately. | // are overloaded and can be handled separately. | ||||
if (p.entry_->isRemoved()) { | if (p.entry_->isRemoved()) { | ||||
if (!this->checkSimulatedOOM()) | if (!this->checkSimulatedOOM()) | ||||
return false; | return false; | ||||
METER(stats.addOverRemoved++); | METER(stats.addOverRemoved++); | ||||
removedCount--; | removedCount--; | ||||
p.keyHash |= sCollisionBit; | p.keyHash |= sCollisionBit; | ||||
} else { | } else { | ||||
// Preserve the validity of |p.entry_|. | // Preserve the validity of |p.entry_|. | ||||
RebuildStatus status = checkOverloaded(); | RebuildStatus status = checkOverloaded(); | ||||
if (status == RehashFailed) | if (status == RehashFailed) | ||||
return false; | return false; | ||||
if (!this->checkSimulatedOOM()) | if (status == NotOverloaded && !this->checkSimulatedOOM()) | ||||
return false; | return false; | ||||
if (status == Rehashed) | if (status == Rehashed) | ||||
p.entry_ = &findFreeEntry(p.keyHash); | p.entry_ = &findFreeEntry(p.keyHash); | ||||
} | } | ||||
p.entry_->setLive(p.keyHash, mozilla::Forward<Args>(args)...); | p.entry_->setLive(p.keyHash, mozilla::Forward<Args>(args)...); | ||||
entryCount++; | entryCount++; | ||||
#ifdef JS_DEBUG | #ifdef JS_DEBUG | ||||
mutationCount++; | mutationCount++; | ||||
p.generation = generation(); | p.generation = generation(); | ||||
p.mutationCount = mutationCount; | p.mutationCount = mutationCount; | ||||
#endif | #endif | ||||
return true; | return true; | ||||
} | } | ||||
// Note: |l| may be a reference to a piece of |u|, so this function | // Note: |l| may be a reference to a piece of |u|, so this function | ||||
// must take care not to use |l| after moving |u|. | // must take care not to use |l| after moving |u|. | ||||
template <typename... Args> | template <typename... Args> | ||||
void putNewInfallible(const Lookup& l, Args&&... args) | void putNewInfallible(const Lookup& l, Args&&... args) | ||||
{ | { | ||||
MOZ_ASSERT(table); | MOZ_ASSERT(!lookup(l).found()); | ||||
mozilla::ReentrancyGuard g(*this); | |||||
HashNumber keyHash = prepareHash(l); | putNewInfallibleInternal(l, mozilla::Forward<Args>(args)...); | ||||
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 | |||||
} | } | ||||
// Note: |l| may be alias arguments in |args|, so this function must take | // Note: |l| may be alias arguments in |args|, so this function must take | ||||
// care not to use |l| after moving |args|. | // care not to use |l| after moving |args|. | ||||
template <typename... Args> | template <typename... Args> | ||||
bool putNew(const Lookup& l, Args&&... args) | MOZ_MUST_USE bool putNew(const Lookup& l, Args&&... args) | ||||
{ | { | ||||
if (!this->checkSimulatedOOM()) | if (!this->checkSimulatedOOM()) | ||||
return false; | return false; | ||||
if (!EnsureHash<HashPolicy>(l)) | |||||
return false; | |||||
if (checkOverloaded() == RehashFailed) | if (checkOverloaded() == RehashFailed) | ||||
return false; | return false; | ||||
putNewInfallible(l, mozilla::Forward<Args>(args)...); | putNewInfallible(l, mozilla::Forward<Args>(args)...); | ||||
return true; | return true; | ||||
} | } | ||||
// Note: |l| may be a reference to a piece of |u|, so this function | // Note: |l| may be a reference to a piece of |u|, so this function | ||||
// must take care not to use |l| after moving |u|. | // must take care not to use |l| after moving |u|. | ||||
template <typename... Args> | template <typename... Args> | ||||
bool relookupOrAdd(AddPtr& p, const Lookup& l, Args&&... 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 | #ifdef JS_DEBUG | ||||
p.generation = generation(); | p.generation = generation(); | ||||
p.mutationCount = mutationCount; | p.mutationCount = mutationCount; | ||||
#endif | #endif | ||||
{ | { | ||||
mozilla::ReentrancyGuard g(*this); | mozilla::ReentrancyGuard g(*this); | ||||
MOZ_ASSERT(prepareHash(l) == p.keyHash); // l has not been destroyed | MOZ_ASSERT(prepareHash(l) == p.keyHash); // l has not been destroyed | ||||
p.entry_ = &lookup(l, p.keyHash, sCollisionBit); | p.entry_ = &lookup(l, p.keyHash, sCollisionBit); | ||||
Show All 13 Lines | #endif | ||||
void rekeyWithoutRehash(Ptr p, const Lookup& l, const Key& k) | void rekeyWithoutRehash(Ptr p, const Lookup& l, const Key& k) | ||||
{ | { | ||||
MOZ_ASSERT(table); | MOZ_ASSERT(table); | ||||
mozilla::ReentrancyGuard g(*this); | mozilla::ReentrancyGuard g(*this); | ||||
MOZ_ASSERT(p.found()); | MOZ_ASSERT(p.found()); | ||||
typename HashTableEntry<T>::NonConstT t(mozilla::Move(*p)); | typename HashTableEntry<T>::NonConstT t(mozilla::Move(*p)); | ||||
HashPolicy::setKey(t, const_cast<Key&>(k)); | HashPolicy::setKey(t, const_cast<Key&>(k)); | ||||
remove(*p.entry_); | remove(*p.entry_); | ||||
putNewInfallible(l, mozilla::Move(t)); | putNewInfallibleInternal(l, mozilla::Move(t)); | ||||
} | } | ||||
void rekeyAndMaybeRehash(Ptr p, const Lookup& l, const Key& k) | void rekeyAndMaybeRehash(Ptr p, const Lookup& l, const Key& k) | ||||
{ | { | ||||
rekeyWithoutRehash(p, l, k); | rekeyWithoutRehash(p, l, k); | ||||
checkOverRemoved(); | checkOverRemoved(); | ||||
} | } | ||||
void rekeyInPlace(Ptr p, const Key& k) | |||||
{ | |||||
MOZ_ASSERT(table); | |||||
mozilla::ReentrancyGuard g(*this); | |||||
MOZ_ASSERT(p.found()); | |||||
HashPolicy::rekey(const_cast<Key&>(*p), const_cast<Key&>(k)); | |||||
} | |||||
#undef METER | #undef METER | ||||
}; | }; | ||||
} // namespace detail | } // namespace detail | ||||
} // namespace js | } // namespace js | ||||
#endif /* js_HashTable_h */ | #endif /* js_HashTable_h */ |
Wildfire Games · Phabricator