| // 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/base/export-template.h" |
| #include "src/base/macros.h" |
| #include "src/globals.h" |
| #include "src/objects/fixed-array.h" |
| #include "src/objects/smi.h" |
| #include "src/roots.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(ReadOnlyRoots roots, 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: |
| using Key = KeyT; |
| static inline RootIndex 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); |
| } |
| |
| OBJECT_CONSTRUCTORS(HashTableBase, FixedArray); |
| }; |
| |
| template <typename Derived, typename Shape> |
| class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) HashTable |
| : public HashTableBase { |
| public: |
| using ShapeT = Shape; |
| using Key = typename Shape::Key; |
| |
| // Returns a new HashTable object. |
| V8_WARN_UNUSED_RESULT static Handle<Derived> New( |
| Isolate* isolate, int at_least_space_for, |
| AllocationType allocation = AllocationType::kYoung, |
| MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY); |
| |
| // 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); |
| inline int FindEntry(Isolate* isolate, Key key); |
| |
| // Rehashes the table in-place. |
| void Rehash(ReadOnlyRoots roots); |
| |
| // 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 * kTaggedSize; |
| // 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; |
| |
| static const int kMaxRegularCapacity = kMaxRegularHeapObjectSize / 32; |
| |
| // Returns the index for an entry (of the key) |
| static constexpr inline int EntryToIndex(int entry) { |
| return (entry * kEntrySize) + kElementsStartIndex; |
| } |
| |
| // Returns the index for an entry (of the key) |
| static constexpr inline int IndexToEntry(int index) { |
| return (index - kElementsStartIndex) / kEntrySize; |
| } |
| |
| // Returns the index for a slot address in the object. |
| static constexpr inline int SlotToIndex(Address object, Address slot) { |
| return static_cast<int>((slot - object - kHeaderSize) / kTaggedSize); |
| } |
| |
| // Ensure enough space for n additional elements. |
| V8_WARN_UNUSED_RESULT static Handle<Derived> EnsureCapacity( |
| Isolate* isolate, Handle<Derived> table, int n, |
| AllocationType allocation = AllocationType::kYoung); |
| |
| // 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, AllocationType allocation); |
| |
| // 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); |
| |
| inline void set_key(int index, Object value); |
| inline void set_key(int index, Object value, WriteBarrierMode mode); |
| |
| 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(ReadOnlyRoots roots, 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(ReadOnlyRoots roots, Derived new_table); |
| |
| OBJECT_CONSTRUCTORS(HashTable, HashTableBase); |
| }; |
| |
| // 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() = default; |
| |
| 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(ReadOnlyRoots roots, 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 EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) 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); |
| |
| OBJECT_CONSTRUCTORS(ObjectHashTableBase, HashTable<Derived, Shape>); |
| }; |
| |
| class ObjectHashTable; |
| |
| extern template class EXPORT_TEMPLATE_DECLARE( |
| V8_EXPORT_PRIVATE) HashTable<ObjectHashTable, ObjectHashTableShape>; |
| extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) |
| ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>; |
| |
| // ObjectHashTable maps keys that are arbitrary objects to object values by |
| // using the identity hash of the key for hashing purposes. |
| class V8_EXPORT_PRIVATE ObjectHashTable |
| : public ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape> { |
| public: |
| DECL_CAST(ObjectHashTable) |
| DECL_PRINTER(ObjectHashTable) |
| |
| OBJECT_CONSTRUCTORS( |
| ObjectHashTable, |
| ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>); |
| }; |
| |
| class EphemeronHashTableShape : public ObjectHashTableShape { |
| public: |
| static inline RootIndex GetMapRootIndex(); |
| }; |
| |
| class EphemeronHashTable; |
| |
| extern template class EXPORT_TEMPLATE_DECLARE( |
| V8_EXPORT_PRIVATE) HashTable<EphemeronHashTable, EphemeronHashTableShape>; |
| extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) |
| ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>; |
| |
| // 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 V8_EXPORT_PRIVATE EphemeronHashTable |
| : public ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape> { |
| public: |
| DECL_CAST(EphemeronHashTable) |
| DECL_PRINTER(EphemeronHashTable) |
| class BodyDescriptor; |
| |
| protected: |
| friend class MarkCompactCollector; |
| friend class ScavengerCollector; |
| friend class HashTable<EphemeronHashTable, EphemeronHashTableShape>; |
| friend class ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>; |
| inline void set_key(int index, Object value); |
| inline void set_key(int index, Object value, WriteBarrierMode mode); |
| |
| OBJECT_CONSTRUCTORS( |
| EphemeronHashTable, |
| ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>); |
| }; |
| |
| class ObjectHashSetShape : public ObjectHashTableShape { |
| public: |
| static const int kPrefixSize = 0; |
| static const int kEntrySize = 1; |
| }; |
| |
| class ObjectHashSet; |
| extern template class EXPORT_TEMPLATE_DECLARE( |
| V8_EXPORT_PRIVATE) HashTable<ObjectHashSet, ObjectHashSetShape>; |
| |
| class V8_EXPORT_PRIVATE 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) |
| |
| OBJECT_CONSTRUCTORS(ObjectHashSet, |
| HashTable<ObjectHashSet, ObjectHashSetShape>); |
| }; |
| |
| } // namespace internal |
| } // namespace v8 |
| |
| #include "src/objects/object-macros-undef.h" |
| |
| #endif // V8_OBJECTS_HASH_TABLE_H_ |