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