Line data Source code
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_H_
6 : #define V8_OBJECTS_HASH_TABLE_H_
7 :
8 : #include "src/base/compiler-specific.h"
9 : #include "src/base/export-template.h"
10 : #include "src/base/macros.h"
11 : #include "src/globals.h"
12 : #include "src/objects/fixed-array.h"
13 : #include "src/objects/smi.h"
14 : #include "src/roots.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 :
22 : // HashTable is a subclass of FixedArray that implements a hash table
23 : // that uses open addressing and quadratic probing.
24 : //
25 : // In order for the quadratic probing to work, elements that have not
26 : // yet been used and elements that have been deleted are
27 : // distinguished. Probing continues when deleted elements are
28 : // encountered and stops when unused elements are encountered.
29 : //
30 : // - Elements with key == undefined have not been used yet.
31 : // - Elements with key == the_hole have been deleted.
32 : //
33 : // The hash table class is parameterized with a Shape.
34 : // Shape must be a class with the following interface:
35 : // class ExampleShape {
36 : // public:
37 : // // Tells whether key matches other.
38 : // static bool IsMatch(Key key, Object other);
39 : // // Returns the hash value for key.
40 : // static uint32_t Hash(Isolate* isolate, Key key);
41 : // // Returns the hash value for object.
42 : // static uint32_t HashForObject(ReadOnlyRoots roots, Object object);
43 : // // Convert key to an object.
44 : // static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
45 : // // The prefix size indicates number of elements in the beginning
46 : // // of the backing storage.
47 : // static const int kPrefixSize = ..;
48 : // // The Element size indicates number of elements per entry.
49 : // static const int kEntrySize = ..;
50 : // // Indicates whether IsMatch can deal with other being the_hole (a
51 : // // deleted entry).
52 : // static const bool kNeedsHoleCheck = ..;
53 : // };
54 : // The prefix size indicates an amount of memory in the
55 : // beginning of the backing storage that can be used for non-element
56 : // information by subclasses.
57 :
58 : template <typename KeyT>
59 : class BaseShape {
60 : public:
61 : using Key = KeyT;
62 : static inline RootIndex GetMapRootIndex();
63 : static const bool kNeedsHoleCheck = true;
64 : static Object Unwrap(Object key) { return key; }
65 : static inline bool IsKey(ReadOnlyRoots roots, Object key);
66 : static inline bool IsLive(ReadOnlyRoots roots, Object key);
67 : };
68 :
69 : class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) {
70 : public:
71 : // Returns the number of elements in the hash table.
72 : inline int NumberOfElements() const;
73 :
74 : // Returns the number of deleted elements in the hash table.
75 : inline int NumberOfDeletedElements() const;
76 :
77 : // Returns the capacity of the hash table.
78 : inline int Capacity() const;
79 :
80 : // ElementAdded should be called whenever an element is added to a
81 : // hash table.
82 : inline void ElementAdded();
83 :
84 : // ElementRemoved should be called whenever an element is removed from
85 : // a hash table.
86 : inline void ElementRemoved();
87 : inline void ElementsRemoved(int n);
88 :
89 : // Computes the required capacity for a table holding the given
90 : // number of elements. May be more than HashTable::kMaxCapacity.
91 : static inline int ComputeCapacity(int at_least_space_for);
92 :
93 : // Compute the probe offset (quadratic probing).
94 : V8_INLINE static uint32_t GetProbeOffset(uint32_t n) {
95 : return (n + n * n) >> 1;
96 : }
97 :
98 : static const int kNumberOfElementsIndex = 0;
99 : static const int kNumberOfDeletedElementsIndex = 1;
100 : static const int kCapacityIndex = 2;
101 : static const int kPrefixStartIndex = 3;
102 :
103 : // Constant used for denoting a absent entry.
104 : static const int kNotFound = -1;
105 :
106 : // Minimum capacity for newly created hash tables.
107 : static const int kMinCapacity = 4;
108 :
109 : protected:
110 : // Update the number of elements in the hash table.
111 : inline void SetNumberOfElements(int nof);
112 :
113 : // Update the number of deleted elements in the hash table.
114 : inline void SetNumberOfDeletedElements(int nod);
115 :
116 : // Returns probe entry.
117 : static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) {
118 : DCHECK(base::bits::IsPowerOfTwo(size));
119 : return (hash + GetProbeOffset(number)) & (size - 1);
120 : }
121 :
122 : inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
123 894626599 : return hash & (size - 1);
124 : }
125 :
126 : inline static uint32_t NextProbe(uint32_t last, uint32_t number,
127 : uint32_t size) {
128 446602913 : return (last + number) & (size - 1);
129 : }
130 :
131 : OBJECT_CONSTRUCTORS(HashTableBase, FixedArray);
132 : };
133 :
134 : template <typename Derived, typename Shape>
135 : class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) HashTable
136 : : public HashTableBase {
137 : public:
138 : using ShapeT = Shape;
139 : using Key = typename Shape::Key;
140 :
141 : // Returns a new HashTable object.
142 : V8_WARN_UNUSED_RESULT static Handle<Derived> New(
143 : Isolate* isolate, int at_least_space_for,
144 : AllocationType allocation = AllocationType::kYoung,
145 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
146 :
147 : // Garbage collection support.
148 : void IteratePrefix(ObjectVisitor* visitor);
149 : void IterateElements(ObjectVisitor* visitor);
150 :
151 : // Find entry for key otherwise return kNotFound.
152 : inline int FindEntry(ReadOnlyRoots roots, Key key, int32_t hash);
153 : int FindEntry(Isolate* isolate, Key key);
154 :
155 : // Rehashes the table in-place.
156 : void Rehash(ReadOnlyRoots roots);
157 :
158 : // Tells whether k is a real key. The hole and undefined are not allowed
159 : // as keys and can be used to indicate missing or deleted elements.
160 : static bool IsKey(ReadOnlyRoots roots, Object k);
161 :
162 : inline bool ToKey(ReadOnlyRoots roots, int entry, Object* out_k);
163 :
164 : // Returns the key at entry.
165 0 : Object KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); }
166 :
167 : static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
168 : static const int kEntrySize = Shape::kEntrySize;
169 : STATIC_ASSERT(kEntrySize > 0);
170 : static const int kEntryKeyIndex = 0;
171 : static const int kElementsStartOffset =
172 : kHeaderSize + kElementsStartIndex * kTaggedSize;
173 : // Maximal capacity of HashTable. Based on maximal length of underlying
174 : // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
175 : // cannot overflow.
176 : static const int kMaxCapacity =
177 : (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
178 :
179 : // Don't shrink a HashTable below this capacity.
180 : static const int kMinShrinkCapacity = 16;
181 :
182 : static const int kMaxRegularCapacity = kMaxRegularHeapObjectSize / 32;
183 :
184 : // Returns the index for an entry (of the key)
185 0 : static constexpr inline int EntryToIndex(int entry) {
186 2864903405 : return (entry * kEntrySize) + kElementsStartIndex;
187 : }
188 :
189 : // Returns the index for an entry (of the key)
190 0 : static constexpr inline int IndexToEntry(int index) {
191 2 : return (index - kElementsStartIndex) / kEntrySize;
192 : }
193 :
194 : // Returns the index for a slot address in the object.
195 0 : static constexpr inline int SlotToIndex(Address object, Address slot) {
196 2 : return static_cast<int>((slot - object - kHeaderSize) / kTaggedSize);
197 : }
198 :
199 : // Ensure enough space for n additional elements.
200 : V8_WARN_UNUSED_RESULT static Handle<Derived> EnsureCapacity(
201 : Isolate* isolate, Handle<Derived> table, int n,
202 : AllocationType allocation = AllocationType::kYoung);
203 :
204 : // Returns true if this table has sufficient capacity for adding n elements.
205 : bool HasSufficientCapacityToAdd(int number_of_additional_elements);
206 :
207 : protected:
208 : friend class ObjectHashTable;
209 :
210 : V8_WARN_UNUSED_RESULT static Handle<Derived> NewInternal(
211 : Isolate* isolate, int capacity, AllocationType allocation);
212 :
213 : // Find the entry at which to insert element with the given key that
214 : // has the given hash value.
215 : uint32_t FindInsertionEntry(uint32_t hash);
216 :
217 : // Attempt to shrink hash table after removal of key.
218 : V8_WARN_UNUSED_RESULT static Handle<Derived> Shrink(
219 : Isolate* isolate, Handle<Derived> table, int additionalCapacity = 0);
220 :
221 : inline void set_key(int index, Object value);
222 : inline void set_key(int index, Object value, WriteBarrierMode mode);
223 :
224 : private:
225 : // Ensure that kMaxRegularCapacity yields a non-large object dictionary.
226 : STATIC_ASSERT(EntryToIndex(kMaxRegularCapacity) < kMaxRegularLength);
227 : STATIC_ASSERT(v8::base::bits::IsPowerOfTwo(kMaxRegularCapacity));
228 : static const int kMaxRegularEntry = kMaxRegularCapacity / kEntrySize;
229 : static const int kMaxRegularIndex = EntryToIndex(kMaxRegularEntry);
230 : STATIC_ASSERT(OffsetOfElementAt(kMaxRegularIndex) <
231 : kMaxRegularHeapObjectSize);
232 :
233 : // Sets the capacity of the hash table.
234 0 : void SetCapacity(int capacity) {
235 : // To scale a computed hash code to fit within the hash table, we
236 : // use bit-wise AND with a mask, so the capacity must be positive
237 : // and non-zero.
238 : DCHECK_GT(capacity, 0);
239 : DCHECK_LE(capacity, kMaxCapacity);
240 : set(kCapacityIndex, Smi::FromInt(capacity));
241 0 : }
242 :
243 : // Returns _expected_ if one of entries given by the first _probe_ probes is
244 : // equal to _expected_. Otherwise, returns the entry given by the probe
245 : // number _probe_.
246 : uint32_t EntryForProbe(ReadOnlyRoots roots, Object k, int probe,
247 : uint32_t expected);
248 :
249 : void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
250 :
251 : // Rehashes this hash-table into the new table.
252 : void Rehash(ReadOnlyRoots roots, Derived new_table);
253 :
254 0 : OBJECT_CONSTRUCTORS(HashTable, HashTableBase);
255 : };
256 :
257 : // HashTableKey is an abstract superclass for virtual key behavior.
258 : class HashTableKey {
259 : public:
260 60554152 : explicit HashTableKey(uint32_t hash) : hash_(hash) {}
261 :
262 : // Returns whether the other object matches this key.
263 : virtual bool IsMatch(Object other) = 0;
264 : // Returns the hash value for this key.
265 : // Required.
266 60554191 : virtual ~HashTableKey() = default;
267 :
268 : uint32_t Hash() const { return hash_; }
269 :
270 : protected:
271 : void set_hash(uint32_t hash) {
272 : DCHECK_EQ(0, hash_);
273 13075525 : hash_ = hash;
274 : }
275 :
276 : private:
277 : uint32_t hash_ = 0;
278 : };
279 :
280 : class ObjectHashTableShape : public BaseShape<Handle<Object>> {
281 : public:
282 : static inline bool IsMatch(Handle<Object> key, Object other);
283 : static inline uint32_t Hash(Isolate* isolate, Handle<Object> key);
284 : static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
285 : static inline Handle<Object> AsHandle(Handle<Object> key);
286 : static const int kPrefixSize = 0;
287 : static const int kEntryValueIndex = 1;
288 : static const int kEntrySize = 2;
289 : static const bool kNeedsHoleCheck = false;
290 : };
291 :
292 : template <typename Derived, typename Shape>
293 : class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) ObjectHashTableBase
294 : : public HashTable<Derived, Shape> {
295 : public:
296 : // Looks up the value associated with the given key. The hole value is
297 : // returned in case the key is not present.
298 : Object Lookup(Handle<Object> key);
299 : Object Lookup(Handle<Object> key, int32_t hash);
300 : Object Lookup(ReadOnlyRoots roots, Handle<Object> key, int32_t hash);
301 :
302 : // Returns the value at entry.
303 : Object ValueAt(int entry);
304 :
305 : // Overwrite all keys and values with the hole value.
306 : static void FillEntriesWithHoles(Handle<Derived>);
307 :
308 : // Adds (or overwrites) the value associated with the given key.
309 : static Handle<Derived> Put(Handle<Derived> table, Handle<Object> key,
310 : Handle<Object> value);
311 : static Handle<Derived> Put(Isolate* isolate, Handle<Derived> table,
312 : Handle<Object> key, Handle<Object> value,
313 : int32_t hash);
314 :
315 : // Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
316 : static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
317 : Handle<Object> key, bool* was_present);
318 : static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
319 : Handle<Object> key, bool* was_present,
320 : int32_t hash);
321 :
322 : // Returns the index to the value of an entry.
323 0 : static inline int EntryToValueIndex(int entry) {
324 : return HashTable<Derived, Shape>::EntryToIndex(entry) +
325 131460 : Shape::kEntryValueIndex;
326 : }
327 :
328 : protected:
329 : void AddEntry(int entry, Object key, Object value);
330 : void RemoveEntry(int entry);
331 :
332 0 : OBJECT_CONSTRUCTORS(ObjectHashTableBase, HashTable<Derived, Shape>);
333 : };
334 :
335 : class ObjectHashTable;
336 :
337 : extern template class EXPORT_TEMPLATE_DECLARE(
338 : V8_EXPORT_PRIVATE) HashTable<ObjectHashTable, ObjectHashTableShape>;
339 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
340 : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>;
341 :
342 : // ObjectHashTable maps keys that are arbitrary objects to object values by
343 : // using the identity hash of the key for hashing purposes.
344 : class V8_EXPORT_PRIVATE ObjectHashTable
345 : : public ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape> {
346 : public:
347 : DECL_CAST(ObjectHashTable)
348 : DECL_PRINTER(ObjectHashTable)
349 :
350 : OBJECT_CONSTRUCTORS(
351 : ObjectHashTable,
352 : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>);
353 : };
354 :
355 : class EphemeronHashTableShape : public ObjectHashTableShape {
356 : public:
357 : static inline RootIndex GetMapRootIndex();
358 : };
359 :
360 : class EphemeronHashTable;
361 :
362 : extern template class EXPORT_TEMPLATE_DECLARE(
363 : V8_EXPORT_PRIVATE) HashTable<EphemeronHashTable, EphemeronHashTableShape>;
364 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
365 : ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>;
366 :
367 : // EphemeronHashTable is similar to ObjectHashTable but gets special treatment
368 : // by the GC. The GC treats its entries as ephemerons: both key and value are
369 : // weak references, however if the key is strongly reachable its corresponding
370 : // value is also kept alive.
371 : class V8_EXPORT_PRIVATE EphemeronHashTable
372 : : public ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape> {
373 : public:
374 : DECL_CAST(EphemeronHashTable)
375 : DECL_PRINTER(EphemeronHashTable)
376 : class BodyDescriptor;
377 :
378 : protected:
379 : friend class MarkCompactCollector;
380 : friend class ScavengerCollector;
381 : friend class HashTable<EphemeronHashTable, EphemeronHashTableShape>;
382 : friend class ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>;
383 : inline void set_key(int index, Object value);
384 : inline void set_key(int index, Object value, WriteBarrierMode mode);
385 :
386 : OBJECT_CONSTRUCTORS(
387 : EphemeronHashTable,
388 : ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>);
389 : };
390 :
391 : class ObjectHashSetShape : public ObjectHashTableShape {
392 : public:
393 : static const int kPrefixSize = 0;
394 : static const int kEntrySize = 1;
395 : };
396 :
397 : class ObjectHashSet;
398 : extern template class EXPORT_TEMPLATE_DECLARE(
399 : V8_EXPORT_PRIVATE) HashTable<ObjectHashSet, ObjectHashSetShape>;
400 :
401 : class V8_EXPORT_PRIVATE ObjectHashSet
402 : : public HashTable<ObjectHashSet, ObjectHashSetShape> {
403 : public:
404 : static Handle<ObjectHashSet> Add(Isolate* isolate, Handle<ObjectHashSet> set,
405 : Handle<Object> key);
406 :
407 : inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
408 : inline bool Has(Isolate* isolate, Handle<Object> key);
409 :
410 : DECL_CAST(ObjectHashSet)
411 :
412 : OBJECT_CONSTRUCTORS(ObjectHashSet,
413 : HashTable<ObjectHashSet, ObjectHashSetShape>);
414 : };
415 :
416 : } // namespace internal
417 : } // namespace v8
418 :
419 : #include "src/objects/object-macros-undef.h"
420 :
421 : #endif // V8_OBJECTS_HASH_TABLE_H_
|
