// Copyright 2017 the V8 project authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style license that can be
|
// found in the LICENSE file.
|
|
#ifndef V8_OBJECTS_HASH_TABLE_H_
|
#define V8_OBJECTS_HASH_TABLE_H_
|
|
#include "src/base/compiler-specific.h"
|
#include "src/globals.h"
|
#include "src/objects/fixed-array.h"
|
|
// Has to be the last include (doesn't have include guards):
|
#include "src/objects/object-macros.h"
|
|
namespace v8 {
|
namespace internal {
|
|
// HashTable is a subclass of FixedArray that implements a hash table
|
// that uses open addressing and quadratic probing.
|
//
|
// In order for the quadratic probing to work, elements that have not
|
// yet been used and elements that have been deleted are
|
// distinguished. Probing continues when deleted elements are
|
// encountered and stops when unused elements are encountered.
|
//
|
// - Elements with key == undefined have not been used yet.
|
// - Elements with key == the_hole have been deleted.
|
//
|
// The hash table class is parameterized with a Shape.
|
// Shape must be a class with the following interface:
|
// class ExampleShape {
|
// public:
|
// // Tells whether key matches other.
|
// static bool IsMatch(Key key, Object* other);
|
// // Returns the hash value for key.
|
// static uint32_t Hash(Isolate* isolate, Key key);
|
// // Returns the hash value for object.
|
// static uint32_t HashForObject(Isolate* isolate, Object* object);
|
// // Convert key to an object.
|
// static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
|
// // The prefix size indicates number of elements in the beginning
|
// // of the backing storage.
|
// static const int kPrefixSize = ..;
|
// // The Element size indicates number of elements per entry.
|
// static const int kEntrySize = ..;
|
// // Indicates whether IsMatch can deal with other being the_hole (a
|
// // deleted entry).
|
// static const bool kNeedsHoleCheck = ..;
|
// };
|
// The prefix size indicates an amount of memory in the
|
// beginning of the backing storage that can be used for non-element
|
// information by subclasses.
|
|
template <typename KeyT>
|
class BaseShape {
|
public:
|
typedef KeyT Key;
|
static inline int GetMapRootIndex();
|
static const bool kNeedsHoleCheck = true;
|
static Object* Unwrap(Object* key) { return key; }
|
static inline bool IsKey(ReadOnlyRoots roots, Object* key);
|
static inline bool IsLive(ReadOnlyRoots roots, Object* key);
|
};
|
|
class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) {
|
public:
|
// Returns the number of elements in the hash table.
|
inline int NumberOfElements() const;
|
|
// Returns the number of deleted elements in the hash table.
|
inline int NumberOfDeletedElements() const;
|
|
// Returns the capacity of the hash table.
|
inline int Capacity() const;
|
|
// ElementAdded should be called whenever an element is added to a
|
// hash table.
|
inline void ElementAdded();
|
|
// ElementRemoved should be called whenever an element is removed from
|
// a hash table.
|
inline void ElementRemoved();
|
inline void ElementsRemoved(int n);
|
|
// Computes the required capacity for a table holding the given
|
// number of elements. May be more than HashTable::kMaxCapacity.
|
static inline int ComputeCapacity(int at_least_space_for);
|
|
// Compute the probe offset (quadratic probing).
|
V8_INLINE static uint32_t GetProbeOffset(uint32_t n) {
|
return (n + n * n) >> 1;
|
}
|
|
static const int kNumberOfElementsIndex = 0;
|
static const int kNumberOfDeletedElementsIndex = 1;
|
static const int kCapacityIndex = 2;
|
static const int kPrefixStartIndex = 3;
|
|
// Constant used for denoting a absent entry.
|
static const int kNotFound = -1;
|
|
// Minimum capacity for newly created hash tables.
|
static const int kMinCapacity = 4;
|
|
protected:
|
// Update the number of elements in the hash table.
|
inline void SetNumberOfElements(int nof);
|
|
// Update the number of deleted elements in the hash table.
|
inline void SetNumberOfDeletedElements(int nod);
|
|
// Returns probe entry.
|
static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) {
|
DCHECK(base::bits::IsPowerOfTwo(size));
|
return (hash + GetProbeOffset(number)) & (size - 1);
|
}
|
|
inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
|
return hash & (size - 1);
|
}
|
|
inline static uint32_t NextProbe(uint32_t last, uint32_t number,
|
uint32_t size) {
|
return (last + number) & (size - 1);
|
}
|
};
|
|
template <typename Derived, typename Shape>
|
class HashTable : public HashTableBase {
|
public:
|
typedef Shape ShapeT;
|
typedef typename Shape::Key Key;
|
|
// Returns a new HashTable object.
|
V8_WARN_UNUSED_RESULT static Handle<Derived> New(
|
Isolate* isolate, int at_least_space_for,
|
PretenureFlag pretenure = NOT_TENURED,
|
MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
|
|
DECL_CAST(HashTable)
|
|
// Garbage collection support.
|
void IteratePrefix(ObjectVisitor* visitor);
|
void IterateElements(ObjectVisitor* visitor);
|
|
// Find entry for key otherwise return kNotFound.
|
inline int FindEntry(ReadOnlyRoots roots, Key key, int32_t hash);
|
int FindEntry(Isolate* isolate, Key key);
|
|
// Rehashes the table in-place.
|
void Rehash(Isolate* isolate);
|
|
// Tells whether k is a real key. The hole and undefined are not allowed
|
// as keys and can be used to indicate missing or deleted elements.
|
static bool IsKey(ReadOnlyRoots roots, Object* k);
|
|
inline bool ToKey(ReadOnlyRoots roots, int entry, Object** out_k);
|
|
// Returns the key at entry.
|
Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); }
|
|
static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
|
static const int kEntrySize = Shape::kEntrySize;
|
STATIC_ASSERT(kEntrySize > 0);
|
static const int kEntryKeyIndex = 0;
|
static const int kElementsStartOffset =
|
kHeaderSize + kElementsStartIndex * kPointerSize;
|
// Maximal capacity of HashTable. Based on maximal length of underlying
|
// FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
|
// cannot overflow.
|
static const int kMaxCapacity =
|
(FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
|
|
// Don't shrink a HashTable below this capacity.
|
static const int kMinShrinkCapacity = 16;
|
|
// Maximum length to create a regular HashTable (aka. non large object).
|
static const int kMaxRegularCapacity = 16384;
|
|
// Returns the index for an entry (of the key)
|
static constexpr inline int EntryToIndex(int entry) {
|
return (entry * kEntrySize) + kElementsStartIndex;
|
}
|
|
// Ensure enough space for n additional elements.
|
V8_WARN_UNUSED_RESULT static Handle<Derived> EnsureCapacity(
|
Isolate* isolate, Handle<Derived> table, int n,
|
PretenureFlag pretenure = NOT_TENURED);
|
|
// Returns true if this table has sufficient capacity for adding n elements.
|
bool HasSufficientCapacityToAdd(int number_of_additional_elements);
|
|
protected:
|
friend class ObjectHashTable;
|
|
V8_WARN_UNUSED_RESULT static Handle<Derived> NewInternal(
|
Isolate* isolate, int capacity, PretenureFlag pretenure);
|
|
// Find the entry at which to insert element with the given key that
|
// has the given hash value.
|
uint32_t FindInsertionEntry(uint32_t hash);
|
|
// Attempt to shrink hash table after removal of key.
|
V8_WARN_UNUSED_RESULT static Handle<Derived> Shrink(
|
Isolate* isolate, Handle<Derived> table, int additionalCapacity = 0);
|
|
private:
|
// Ensure that kMaxRegularCapacity yields a non-large object dictionary.
|
STATIC_ASSERT(EntryToIndex(kMaxRegularCapacity) < kMaxRegularLength);
|
STATIC_ASSERT(v8::base::bits::IsPowerOfTwo(kMaxRegularCapacity));
|
static const int kMaxRegularEntry = kMaxRegularCapacity / kEntrySize;
|
static const int kMaxRegularIndex = EntryToIndex(kMaxRegularEntry);
|
STATIC_ASSERT(OffsetOfElementAt(kMaxRegularIndex) <
|
kMaxRegularHeapObjectSize);
|
|
// Sets the capacity of the hash table.
|
void SetCapacity(int capacity) {
|
// To scale a computed hash code to fit within the hash table, we
|
// use bit-wise AND with a mask, so the capacity must be positive
|
// and non-zero.
|
DCHECK_GT(capacity, 0);
|
DCHECK_LE(capacity, kMaxCapacity);
|
set(kCapacityIndex, Smi::FromInt(capacity));
|
}
|
|
// Returns _expected_ if one of entries given by the first _probe_ probes is
|
// equal to _expected_. Otherwise, returns the entry given by the probe
|
// number _probe_.
|
uint32_t EntryForProbe(Isolate* isolate, Object* k, int probe,
|
uint32_t expected);
|
|
void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
|
|
// Rehashes this hash-table into the new table.
|
void Rehash(Isolate* isolate, Derived* new_table);
|
};
|
|
// HashTableKey is an abstract superclass for virtual key behavior.
|
class HashTableKey {
|
public:
|
explicit HashTableKey(uint32_t hash) : hash_(hash) {}
|
|
// Returns whether the other object matches this key.
|
virtual bool IsMatch(Object* other) = 0;
|
// Returns the hash value for this key.
|
// Required.
|
virtual ~HashTableKey() {}
|
|
uint32_t Hash() const { return hash_; }
|
|
protected:
|
void set_hash(uint32_t hash) {
|
DCHECK_EQ(0, hash_);
|
hash_ = hash;
|
}
|
|
private:
|
uint32_t hash_ = 0;
|
};
|
|
class ObjectHashTableShape : public BaseShape<Handle<Object>> {
|
public:
|
static inline bool IsMatch(Handle<Object> key, Object* other);
|
static inline uint32_t Hash(Isolate* isolate, Handle<Object> key);
|
static inline uint32_t HashForObject(Isolate* isolate, Object* object);
|
static inline Handle<Object> AsHandle(Handle<Object> key);
|
static const int kPrefixSize = 0;
|
static const int kEntryValueIndex = 1;
|
static const int kEntrySize = 2;
|
static const bool kNeedsHoleCheck = false;
|
};
|
|
template <typename Derived, typename Shape>
|
class ObjectHashTableBase : public HashTable<Derived, Shape> {
|
public:
|
// Looks up the value associated with the given key. The hole value is
|
// returned in case the key is not present.
|
Object* Lookup(Handle<Object> key);
|
Object* Lookup(Handle<Object> key, int32_t hash);
|
Object* Lookup(ReadOnlyRoots roots, Handle<Object> key, int32_t hash);
|
|
// Returns the value at entry.
|
Object* ValueAt(int entry);
|
|
// Overwrite all keys and values with the hole value.
|
static void FillEntriesWithHoles(Handle<Derived>);
|
|
// Adds (or overwrites) the value associated with the given key.
|
static Handle<Derived> Put(Handle<Derived> table, Handle<Object> key,
|
Handle<Object> value);
|
static Handle<Derived> Put(Isolate* isolate, Handle<Derived> table,
|
Handle<Object> key, Handle<Object> value,
|
int32_t hash);
|
|
// Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
|
static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
|
Handle<Object> key, bool* was_present);
|
static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
|
Handle<Object> key, bool* was_present,
|
int32_t hash);
|
|
// Returns the index to the value of an entry.
|
static inline int EntryToValueIndex(int entry) {
|
return HashTable<Derived, Shape>::EntryToIndex(entry) +
|
Shape::kEntryValueIndex;
|
}
|
|
protected:
|
void AddEntry(int entry, Object* key, Object* value);
|
void RemoveEntry(int entry);
|
};
|
|
// ObjectHashTable maps keys that are arbitrary objects to object values by
|
// using the identity hash of the key for hashing purposes.
|
class ObjectHashTable
|
: public ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape> {
|
public:
|
DECL_CAST(ObjectHashTable)
|
DECL_PRINTER(ObjectHashTable)
|
};
|
|
class EphemeronHashTableShape : public ObjectHashTableShape {
|
public:
|
static inline int GetMapRootIndex();
|
};
|
|
// EphemeronHashTable is similar to ObjectHashTable but gets special treatment
|
// by the GC. The GC treats its entries as ephemerons: both key and value are
|
// weak references, however if the key is strongly reachable its corresponding
|
// value is also kept alive.
|
class EphemeronHashTable
|
: public ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape> {
|
public:
|
DECL_CAST(EphemeronHashTable)
|
DECL_PRINTER(EphemeronHashTable)
|
|
protected:
|
friend class MarkCompactCollector;
|
};
|
|
class ObjectHashSetShape : public ObjectHashTableShape {
|
public:
|
static const int kPrefixSize = 0;
|
static const int kEntrySize = 1;
|
};
|
|
class ObjectHashSet : public HashTable<ObjectHashSet, ObjectHashSetShape> {
|
public:
|
static Handle<ObjectHashSet> Add(Isolate* isolate, Handle<ObjectHashSet> set,
|
Handle<Object> key);
|
|
inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
|
inline bool Has(Isolate* isolate, Handle<Object> key);
|
|
DECL_CAST(ObjectHashSet)
|
};
|
|
} // namespace internal
|
} // namespace v8
|
|
#include "src/objects/object-macros-undef.h"
|
|
#endif // V8_OBJECTS_HASH_TABLE_H_
|
