1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_OBJECTS_HASH_TABLE_INL_H_
6 #define V8_OBJECTS_HASH_TABLE_INL_H_
7
8 #include "src/objects/hash-table.h"
9
10 #include "src/execution/isolate-utils-inl.h"
11 #include "src/heap/heap.h"
12 #include "src/objects/fixed-array-inl.h"
13 #include "src/objects/heap-object-inl.h"
14 #include "src/objects/objects-inl.h"
15 #include "src/roots/roots-inl.h"
16
17 // Has to be the last include (doesn't have include guards):
18 #include "src/objects/object-macros.h"
19
20 namespace v8 {
21 namespace internal {
22
OBJECT_CONSTRUCTORS_IMPL(HashTableBase,FixedArray)23 OBJECT_CONSTRUCTORS_IMPL(HashTableBase, FixedArray)
24
25 template <typename Derived, typename Shape>
26 HashTable<Derived, Shape>::HashTable(Address ptr) : HashTableBase(ptr) {
27 SLOW_DCHECK(IsHashTable());
28 }
29
30 template <typename Derived, typename Shape>
ObjectHashTableBase(Address ptr)31 ObjectHashTableBase<Derived, Shape>::ObjectHashTableBase(Address ptr)
32 : HashTable<Derived, Shape>(ptr) {}
33
ObjectHashTable(Address ptr)34 ObjectHashTable::ObjectHashTable(Address ptr)
35 : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>(ptr) {
36 SLOW_DCHECK(IsObjectHashTable());
37 }
38
EphemeronHashTable(Address ptr)39 EphemeronHashTable::EphemeronHashTable(Address ptr)
40 : ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>(ptr) {
41 SLOW_DCHECK(IsEphemeronHashTable());
42 }
43
ObjectHashSet(Address ptr)44 ObjectHashSet::ObjectHashSet(Address ptr)
45 : HashTable<ObjectHashSet, ObjectHashSetShape>(ptr) {
46 SLOW_DCHECK(IsObjectHashSet());
47 }
48
49 CAST_ACCESSOR(ObjectHashTable)
CAST_ACCESSOR(EphemeronHashTable)50 CAST_ACCESSOR(EphemeronHashTable)
51 CAST_ACCESSOR(ObjectHashSet)
52
53 void EphemeronHashTable::set_key(int index, Object value) {
54 DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
55 DCHECK(IsEphemeronHashTable());
56 DCHECK_GE(index, 0);
57 DCHECK_LT(index, this->length());
58 int offset = kHeaderSize + index * kTaggedSize;
59 RELAXED_WRITE_FIELD(*this, offset, value);
60 EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value);
61 }
62
set_key(int index,Object value,WriteBarrierMode mode)63 void EphemeronHashTable::set_key(int index, Object value,
64 WriteBarrierMode mode) {
65 DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
66 DCHECK(IsEphemeronHashTable());
67 DCHECK_GE(index, 0);
68 DCHECK_LT(index, this->length());
69 int offset = kHeaderSize + index * kTaggedSize;
70 RELAXED_WRITE_FIELD(*this, offset, value);
71 CONDITIONAL_EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value, mode);
72 }
73
NumberOfElements()74 int HashTableBase::NumberOfElements() const {
75 int offset = OffsetOfElementAt(kNumberOfElementsIndex);
76 return TaggedField<Smi>::load(*this, offset).value();
77 }
78
NumberOfDeletedElements()79 int HashTableBase::NumberOfDeletedElements() const {
80 int offset = OffsetOfElementAt(kNumberOfDeletedElementsIndex);
81 return TaggedField<Smi>::load(*this, offset).value();
82 }
83
Capacity()84 int HashTableBase::Capacity() const {
85 int offset = OffsetOfElementAt(kCapacityIndex);
86 return TaggedField<Smi>::load(*this, offset).value();
87 }
88
IterateEntries()89 InternalIndex::Range HashTableBase::IterateEntries() const {
90 return InternalIndex::Range(Capacity());
91 }
92
ElementAdded()93 void HashTableBase::ElementAdded() {
94 SetNumberOfElements(NumberOfElements() + 1);
95 }
96
ElementRemoved()97 void HashTableBase::ElementRemoved() {
98 SetNumberOfElements(NumberOfElements() - 1);
99 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
100 }
101
ElementsRemoved(int n)102 void HashTableBase::ElementsRemoved(int n) {
103 SetNumberOfElements(NumberOfElements() - n);
104 SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
105 }
106
107 // static
ComputeCapacity(int at_least_space_for)108 int HashTableBase::ComputeCapacity(int at_least_space_for) {
109 // Add 50% slack to make slot collisions sufficiently unlikely.
110 // See matching computation in HashTable::HasSufficientCapacityToAdd().
111 // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
112 int raw_cap = at_least_space_for + (at_least_space_for >> 1);
113 int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
114 return Max(capacity, kMinCapacity);
115 }
116
SetNumberOfElements(int nof)117 void HashTableBase::SetNumberOfElements(int nof) {
118 set(kNumberOfElementsIndex, Smi::FromInt(nof));
119 }
120
SetNumberOfDeletedElements(int nod)121 void HashTableBase::SetNumberOfDeletedElements(int nod) {
122 set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
123 }
124
125 template <typename Key>
GetMap(ReadOnlyRoots roots)126 Handle<Map> BaseShape<Key>::GetMap(ReadOnlyRoots roots) {
127 return roots.hash_table_map_handle();
128 }
129
GetMap(ReadOnlyRoots roots)130 Handle<Map> EphemeronHashTableShape::GetMap(ReadOnlyRoots roots) {
131 return roots.ephemeron_hash_table_map_handle();
132 }
133
134 template <typename Derived, typename Shape>
FindEntry(Isolate * isolate,Key key)135 InternalIndex HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
136 return FindEntry(ReadOnlyRoots(isolate), key);
137 }
138
139 template <typename Derived, typename Shape>
FindEntry(ReadOnlyRoots roots,Key key)140 InternalIndex HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots,
141 Key key) {
142 return FindEntry(roots, key, Shape::Hash(roots, key));
143 }
144
145 // Find entry for key otherwise return kNotFound.
146 template <typename Derived, typename Shape>
FindEntry(ReadOnlyRoots roots,Key key,int32_t hash)147 InternalIndex HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
148 int32_t hash) {
149 uint32_t capacity = Capacity();
150 InternalIndex entry = FirstProbe(hash, capacity);
151 uint32_t count = 1;
152 // EnsureCapacity will guarantee the hash table is never full.
153 Object undefined = roots.undefined_value();
154 Object the_hole = roots.the_hole_value();
155 USE(the_hole);
156 while (true) {
157 Object element = KeyAt(entry);
158 // Empty entry. Uses raw unchecked accessors because it is called by the
159 // string table during bootstrapping.
160 if (element == undefined) break;
161 if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
162 if (Shape::IsMatch(key, element)) return entry;
163 }
164 entry = NextProbe(entry, count++, capacity);
165 }
166 return InternalIndex::NotFound();
167 }
168
169 template <typename Derived, typename Shape>
ToKey(ReadOnlyRoots roots,InternalIndex entry,Object * out_k)170 bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, InternalIndex entry,
171 Object* out_k) {
172 Object k = KeyAt(entry);
173 if (!IsKey(roots, k)) return false;
174 *out_k = Shape::Unwrap(k);
175 return true;
176 }
177
178 template <typename Derived, typename Shape>
ToKey(Isolate * isolate,InternalIndex entry,Object * out_k)179 bool HashTable<Derived, Shape>::ToKey(Isolate* isolate, InternalIndex entry,
180 Object* out_k) {
181 Object k = KeyAt(isolate, entry);
182 if (!IsKey(GetReadOnlyRoots(isolate), k)) return false;
183 *out_k = Shape::Unwrap(k);
184 return true;
185 }
186
187 template <typename Derived, typename Shape>
KeyAt(InternalIndex entry)188 Object HashTable<Derived, Shape>::KeyAt(InternalIndex entry) {
189 const Isolate* isolate = GetIsolateForPtrCompr(*this);
190 return KeyAt(isolate, entry);
191 }
192
193 template <typename Derived, typename Shape>
KeyAt(const Isolate * isolate,InternalIndex entry)194 Object HashTable<Derived, Shape>::KeyAt(const Isolate* isolate,
195 InternalIndex entry) {
196 return get(isolate, EntryToIndex(entry) + kEntryKeyIndex);
197 }
198
199 template <typename Derived, typename Shape>
set_key(int index,Object value)200 void HashTable<Derived, Shape>::set_key(int index, Object value) {
201 DCHECK(!IsEphemeronHashTable());
202 FixedArray::set(index, value);
203 }
204
205 template <typename Derived, typename Shape>
set_key(int index,Object value,WriteBarrierMode mode)206 void HashTable<Derived, Shape>::set_key(int index, Object value,
207 WriteBarrierMode mode) {
208 DCHECK(!IsEphemeronHashTable());
209 FixedArray::set(index, value, mode);
210 }
211
212 template <typename Derived, typename Shape>
SetCapacity(int capacity)213 void HashTable<Derived, Shape>::SetCapacity(int capacity) {
214 // To scale a computed hash code to fit within the hash table, we
215 // use bit-wise AND with a mask, so the capacity must be positive
216 // and non-zero.
217 DCHECK_GT(capacity, 0);
218 DCHECK_LE(capacity, kMaxCapacity);
219 set(kCapacityIndex, Smi::FromInt(capacity));
220 }
221
222 template <typename KeyT>
IsKey(ReadOnlyRoots roots,Object key)223 bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object key) {
224 return IsLive(roots, key);
225 }
226
227 template <typename KeyT>
IsLive(ReadOnlyRoots roots,Object k)228 bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object k) {
229 return k != roots.the_hole_value() && k != roots.undefined_value();
230 }
231
Has(Isolate * isolate,Handle<Object> key,int32_t hash)232 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
233 return FindEntry(ReadOnlyRoots(isolate), key, hash).is_found();
234 }
235
Has(Isolate * isolate,Handle<Object> key)236 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
237 Object hash = key->GetHash();
238 if (!hash.IsSmi()) return false;
239 return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)).is_found();
240 }
241
IsMatch(Handle<Object> key,Object other)242 bool ObjectHashTableShape::IsMatch(Handle<Object> key, Object other) {
243 return key->SameValue(other);
244 }
245
Hash(ReadOnlyRoots roots,Handle<Object> key)246 uint32_t ObjectHashTableShape::Hash(ReadOnlyRoots roots, Handle<Object> key) {
247 return Smi::ToInt(key->GetHash());
248 }
249
HashForObject(ReadOnlyRoots roots,Object other)250 uint32_t ObjectHashTableShape::HashForObject(ReadOnlyRoots roots,
251 Object other) {
252 return Smi::ToInt(other.GetHash());
253 }
254
255 } // namespace internal
256 } // namespace v8
257
258 #include "src/objects/object-macros-undef.h"
259
260 #endif // V8_OBJECTS_HASH_TABLE_INL_H_
261