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