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/objects.h"
9 :
10 : #include "src/base/compiler-specific.h"
11 : #include "src/globals.h"
12 :
13 : // Has to be the last include (doesn't have include guards):
14 : #include "src/objects/object-macros.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 : // HashTable is a subclass of FixedArray that implements a hash table
20 : // that uses open addressing and quadratic probing.
21 : //
22 : // In order for the quadratic probing to work, elements that have not
23 : // yet been used and elements that have been deleted are
24 : // distinguished. Probing continues when deleted elements are
25 : // encountered and stops when unused elements are encountered.
26 : //
27 : // - Elements with key == undefined have not been used yet.
28 : // - Elements with key == the_hole have been deleted.
29 : //
30 : // The hash table class is parameterized with a Shape.
31 : // Shape must be a class with the following interface:
32 : // class ExampleShape {
33 : // public:
34 : // // Tells whether key matches other.
35 : // static bool IsMatch(Key key, Object* other);
36 : // // Returns the hash value for key.
37 : // static uint32_t Hash(Isolate* isolate, Key key);
38 : // // Returns the hash value for object.
39 : // static uint32_t HashForObject(Isolate* isolate, Object* object);
40 : // // Convert key to an object.
41 : // static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
42 : // // The prefix size indicates number of elements in the beginning
43 : // // of the backing storage.
44 : // static const int kPrefixSize = ..;
45 : // // The Element size indicates number of elements per entry.
46 : // static const int kEntrySize = ..;
47 : // // Indicates whether IsMatch can deal with other being the_hole (a
48 : // // deleted entry).
49 : // static const bool kNeedsHoleCheck = ..;
50 : // };
51 : // The prefix size indicates an amount of memory in the
52 : // beginning of the backing storage that can be used for non-element
53 : // information by subclasses.
54 :
55 : template <typename KeyT>
56 : class BaseShape {
57 : public:
58 : typedef KeyT Key;
59 : static inline Map* GetMap(Isolate* isolate);
60 : static const bool kNeedsHoleCheck = true;
61 : static Object* Unwrap(Object* key) { return key; }
62 : static bool IsKey(Isolate* isolate, Object* key) {
63 : return IsLive(isolate, key);
64 : }
65 : static inline bool IsLive(Isolate* isolate, Object* key);
66 : };
67 :
68 : class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) {
69 : public:
70 : // Returns the number of elements in the hash table.
71 : inline int NumberOfElements() const;
72 :
73 : // Returns the number of deleted elements in the hash table.
74 : inline int NumberOfDeletedElements() const;
75 :
76 : // Returns the capacity of the hash table.
77 : inline int Capacity() const;
78 :
79 : // ElementAdded should be called whenever an element is added to a
80 : // hash table.
81 : inline void ElementAdded();
82 :
83 : // ElementRemoved should be called whenever an element is removed from
84 : // a hash table.
85 : inline void ElementRemoved();
86 : inline void ElementsRemoved(int n);
87 :
88 : // Computes the required capacity for a table holding the given
89 : // number of elements. May be more than HashTable::kMaxCapacity.
90 : static inline int ComputeCapacity(int at_least_space_for);
91 :
92 : // Compute the probe offset (quadratic probing).
93 : INLINE(static uint32_t GetProbeOffset(uint32_t n)) {
94 3876 : return (n + n * n) >> 1;
95 : }
96 :
97 : static const int kNumberOfElementsIndex = 0;
98 : static const int kNumberOfDeletedElementsIndex = 1;
99 : static const int kCapacityIndex = 2;
100 : static const int kPrefixStartIndex = 3;
101 :
102 : // Constant used for denoting a absent entry.
103 : static const int kNotFound = -1;
104 :
105 : // Minimum capacity for newly created hash tables.
106 : static const int kMinCapacity = 4;
107 :
108 : protected:
109 : // Update the number of elements in the hash table.
110 : inline void SetNumberOfElements(int nof);
111 :
112 : // Update the number of deleted elements in the hash table.
113 : inline void SetNumberOfDeletedElements(int nod);
114 :
115 : // Returns probe entry.
116 : static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) {
117 : DCHECK(base::bits::IsPowerOfTwo(size));
118 : return (hash + GetProbeOffset(number)) & (size - 1);
119 : }
120 :
121 : inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
122 621155370 : return hash & (size - 1);
123 : }
124 :
125 : inline static uint32_t NextProbe(uint32_t last, uint32_t number,
126 : uint32_t size) {
127 323790019 : return (last + number) & (size - 1);
128 : }
129 : };
130 :
131 : template <typename Derived, typename Shape>
132 : class HashTable : public HashTableBase {
133 : public:
134 : typedef Shape ShapeT;
135 : typedef typename Shape::Key Key;
136 :
137 : // Returns a new HashTable object.
138 : MUST_USE_RESULT static Handle<Derived> New(
139 : Isolate* isolate, int at_least_space_for,
140 : PretenureFlag pretenure = NOT_TENURED,
141 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
142 :
143 : DECL_CAST(HashTable)
144 :
145 : // Garbage collection support.
146 : void IteratePrefix(ObjectVisitor* visitor);
147 : void IterateElements(ObjectVisitor* visitor);
148 :
149 : // Find entry for key otherwise return kNotFound.
150 : inline int FindEntry(Key key);
151 : inline int FindEntry(Isolate* isolate, Key key, int32_t hash);
152 : int FindEntry(Isolate* isolate, Key key);
153 :
154 : // Rehashes the table in-place.
155 : void Rehash();
156 :
157 : // Tells whether k is a real key. The hole and undefined are not allowed
158 : // as keys and can be used to indicate missing or deleted elements.
159 1483 : static bool IsKey(Isolate* isolate, Object* k) {
160 30229349 : return Shape::IsKey(isolate, k);
161 : }
162 :
163 42697167 : inline bool ToKey(Isolate* isolate, int entry, Object** out_k) {
164 : Object* k = KeyAt(entry);
165 42697167 : if (!IsKey(isolate, k)) return false;
166 19566347 : *out_k = Shape::Unwrap(k);
167 19566347 : return true;
168 : }
169 :
170 : // Returns the key at entry.
171 0 : Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); }
172 :
173 : static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
174 : static const int kEntrySize = Shape::kEntrySize;
175 : STATIC_ASSERT(kEntrySize > 0);
176 : static const int kEntryKeyIndex = 0;
177 : static const int kElementsStartOffset =
178 : kHeaderSize + kElementsStartIndex * kPointerSize;
179 : // Maximal capacity of HashTable. Based on maximal length of underlying
180 : // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
181 : // cannot overflow.
182 : static const int kMaxCapacity =
183 : (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
184 :
185 : // Maximum length to create a regular HashTable (aka. non large object).
186 : static const int kMaxRegularCapacity = 16384;
187 :
188 : // Returns the index for an entry (of the key)
189 0 : static constexpr inline int EntryToIndex(int entry) {
190 2768926253 : return (entry * kEntrySize) + kElementsStartIndex;
191 : }
192 :
193 : // Ensure enough space for n additional elements.
194 : MUST_USE_RESULT static Handle<Derived> EnsureCapacity(
195 : Handle<Derived> table, int n, 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 : MUST_USE_RESULT static Handle<Derived> NewInternal(Isolate* isolate,
204 : int capacity,
205 : PretenureFlag pretenure);
206 :
207 : // Find the entry at which to insert element with the given key that
208 : // has the given hash value.
209 : uint32_t FindInsertionEntry(uint32_t hash);
210 :
211 : // Attempt to shrink hash table after removal of key.
212 : MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table);
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(Object* k, int probe, uint32_t expected);
237 :
238 : void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
239 :
240 : // Rehashes this hash-table into the new table.
241 : void Rehash(Derived* new_table);
242 : };
243 :
244 : // HashTableKey is an abstract superclass for virtual key behavior.
245 : class HashTableKey {
246 : public:
247 71252789 : explicit HashTableKey(uint32_t hash) : hash_(hash) {}
248 :
249 : // Returns whether the other object matches this key.
250 : virtual bool IsMatch(Object* other) = 0;
251 : // Returns the hash value for this key.
252 : // Required.
253 53400 : virtual ~HashTableKey() {}
254 :
255 : uint32_t Hash() const { return hash_; }
256 :
257 : protected:
258 : void set_hash(uint32_t hash) {
259 : DCHECK_EQ(0, hash_);
260 12049613 : hash_ = hash;
261 : }
262 :
263 : private:
264 : uint32_t hash_ = 0;
265 : };
266 :
267 : class ObjectHashTableShape : public BaseShape<Handle<Object>> {
268 : public:
269 : static inline bool IsMatch(Handle<Object> key, Object* other);
270 : static inline uint32_t Hash(Isolate* isolate, Handle<Object> key);
271 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
272 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
273 : static const int kPrefixSize = 0;
274 : static const int kEntryValueIndex = 1;
275 : static const int kEntrySize = 2;
276 : static const bool kNeedsHoleCheck = false;
277 : };
278 :
279 : // ObjectHashTable maps keys that are arbitrary objects to object values by
280 : // using the identity hash of the key for hashing purposes.
281 : class ObjectHashTable
282 : : public HashTable<ObjectHashTable, ObjectHashTableShape> {
283 : typedef HashTable<ObjectHashTable, ObjectHashTableShape> DerivedHashTable;
284 :
285 : public:
286 : DECL_CAST(ObjectHashTable)
287 :
288 : // Attempt to shrink hash table after removal of key.
289 : MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink(
290 : Handle<ObjectHashTable> table);
291 :
292 : // Looks up the value associated with the given key. The hole value is
293 : // returned in case the key is not present.
294 : Object* Lookup(Handle<Object> key);
295 : Object* Lookup(Handle<Object> key, int32_t hash);
296 : Object* Lookup(Isolate* isolate, Handle<Object> key, int32_t hash);
297 :
298 : // Returns the value at entry.
299 : Object* ValueAt(int entry);
300 :
301 : // Adds (or overwrites) the value associated with the given key.
302 : static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
303 : Handle<Object> key, Handle<Object> value);
304 : static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
305 : Handle<Object> key, Handle<Object> value,
306 : int32_t hash);
307 :
308 : // Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
309 : static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
310 : Handle<Object> key, bool* was_present);
311 : static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
312 : Handle<Object> key, bool* was_present,
313 : int32_t hash);
314 :
315 : // Returns the index to the value of an entry.
316 : static inline int EntryToValueIndex(int entry) {
317 100494 : return EntryToIndex(entry) + ObjectHashTableShape::kEntryValueIndex;
318 : }
319 :
320 : protected:
321 : friend class MarkCompactCollector;
322 :
323 : void AddEntry(int entry, Object* key, Object* value);
324 : void RemoveEntry(int entry);
325 : };
326 :
327 : class ObjectHashSetShape : public ObjectHashTableShape {
328 : public:
329 : static const int kPrefixSize = 0;
330 : static const int kEntrySize = 1;
331 : };
332 :
333 : class ObjectHashSet : public HashTable<ObjectHashSet, ObjectHashSetShape> {
334 : public:
335 : static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set,
336 : Handle<Object> key);
337 :
338 : inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
339 : inline bool Has(Isolate* isolate, Handle<Object> key);
340 :
341 : DECL_CAST(ObjectHashSet)
342 : };
343 :
344 : // Non-templatized base class for {OrderedHashTable}s.
345 : // TODO(hash): Unify this with the HashTableBase above.
346 : class OrderedHashTableBase : public FixedArray {
347 : public:
348 : static const int kNotFound = -1;
349 : static const int kMinCapacity = 4;
350 :
351 : static const int kNumberOfElementsIndex = 0;
352 : // The next table is stored at the same index as the nof elements.
353 : static const int kNextTableIndex = kNumberOfElementsIndex;
354 : static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
355 : static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1;
356 : static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1;
357 : static const int kRemovedHolesIndex = kHashTableStartIndex;
358 :
359 : static constexpr const int kNumberOfElementsOffset =
360 : FixedArray::OffsetOfElementAt(kNumberOfElementsIndex);
361 : static constexpr const int kNextTableOffset =
362 : FixedArray::OffsetOfElementAt(kNextTableIndex);
363 : static constexpr const int kNumberOfDeletedElementsOffset =
364 : FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex);
365 : static constexpr const int kNumberOfBucketsOffset =
366 : FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex);
367 : static constexpr const int kHashTableStartOffset =
368 : FixedArray::OffsetOfElementAt(kHashTableStartIndex);
369 :
370 : static const int kLoadFactor = 2;
371 :
372 : // NumberOfDeletedElements is set to kClearedTableSentinel when
373 : // the table is cleared, which allows iterator transitions to
374 : // optimize that case.
375 : static const int kClearedTableSentinel = -1;
376 : };
377 :
378 : // OrderedHashTable is a HashTable with Object keys that preserves
379 : // insertion order. There are Map and Set interfaces (OrderedHashMap
380 : // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
381 : //
382 : // Only Object* keys are supported, with Object::SameValueZero() used as the
383 : // equality operator and Object::GetHash() for the hash function.
384 : //
385 : // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
386 : // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
387 : // Originally attributed to Tyler Close.
388 : //
389 : // Memory layout:
390 : // [0]: element count
391 : // [1]: deleted element count
392 : // [2]: bucket count
393 : // [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an
394 : // offset into the data table (see below) where the
395 : // first item in this bucket is stored.
396 : // [3 + NumberOfBuckets()..length]: "data table", an array of length
397 : // Capacity() * kEntrySize, where the first entrysize
398 : // items are handled by the derived class and the
399 : // item at kChainOffset is another entry into the
400 : // data table indicating the next entry in this hash
401 : // bucket.
402 : //
403 : // When we transition the table to a new version we obsolete it and reuse parts
404 : // of the memory to store information how to transition an iterator to the new
405 : // table:
406 : //
407 : // Memory layout for obsolete table:
408 : // [0]: bucket count
409 : // [1]: Next newer table
410 : // [2]: Number of removed holes or -1 when the table was cleared.
411 : // [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes.
412 : // [3 + NumberOfRemovedHoles()..length]: Not used
413 : //
414 : template <class Derived, int entrysize>
415 : class OrderedHashTable : public OrderedHashTableBase {
416 : public:
417 : // Returns an OrderedHashTable with a capacity of at least |capacity|.
418 : static Handle<Derived> Allocate(Isolate* isolate, int capacity,
419 : PretenureFlag pretenure = NOT_TENURED);
420 :
421 : // Returns an OrderedHashTable (possibly |table|) with enough space
422 : // to add at least one new element.
423 : static Handle<Derived> EnsureGrowable(Handle<Derived> table);
424 :
425 : // Returns an OrderedHashTable (possibly |table|) that's shrunken
426 : // if possible.
427 : static Handle<Derived> Shrink(Handle<Derived> table);
428 :
429 : // Returns a new empty OrderedHashTable and records the clearing so that
430 : // existing iterators can be updated.
431 : static Handle<Derived> Clear(Handle<Derived> table);
432 :
433 : // Returns true if the OrderedHashTable contains the key
434 : static bool HasKey(Isolate* isolate, Derived* table, Object* key);
435 :
436 : // Returns a true value if the OrderedHashTable contains the key and
437 : // the key has been deleted. This does not shrink the table.
438 : static bool Delete(Isolate* isolate, Derived* table, Object* key);
439 :
440 : int NumberOfElements() { return Smi::ToInt(get(kNumberOfElementsIndex)); }
441 :
442 : int NumberOfDeletedElements() {
443 : return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
444 : }
445 :
446 : // Returns the number of contiguous entries in the data table, starting at 0,
447 : // that either are real entries or have been deleted.
448 1552 : int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
449 :
450 : int NumberOfBuckets() { return Smi::ToInt(get(kNumberOfBucketsIndex)); }
451 :
452 : // Returns an index into |this| for the given entry.
453 : int EntryToIndex(int entry) {
454 98187675 : return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
455 : }
456 :
457 140345248 : int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
458 :
459 93563903 : int HashToEntry(int hash) {
460 : int bucket = HashToBucket(hash);
461 93563903 : Object* entry = this->get(kHashTableStartIndex + bucket);
462 93563903 : return Smi::ToInt(entry);
463 : }
464 :
465 630 : int KeyToFirstEntry(Isolate* isolate, Object* key) {
466 : // This special cases for Smi, so that we avoid the HandleScope
467 : // creation below.
468 630 : if (key->IsSmi()) {
469 222 : uint32_t hash = ComputeIntegerHash(Smi::ToInt(key));
470 222 : return HashToEntry(hash & Smi::kMaxValue);
471 : }
472 : HandleScope scope(isolate);
473 408 : Object* hash = key->GetHash();
474 : // If the object does not have an identity hash, it was never used as a key
475 408 : if (hash->IsUndefined(isolate)) return kNotFound;
476 408 : return HashToEntry(Smi::ToInt(hash));
477 : }
478 :
479 630 : int FindEntry(Isolate* isolate, Object* key) {
480 630 : int entry = KeyToFirstEntry(isolate, key);
481 : // Walk the chain in the bucket to find the key.
482 1638 : while (entry != kNotFound) {
483 720 : Object* candidate_key = KeyAt(entry);
484 720 : if (candidate_key->SameValueZero(key)) break;
485 378 : entry = NextChainEntry(entry);
486 : }
487 :
488 630 : return entry;
489 : }
490 :
491 19168706 : int NextChainEntry(int entry) {
492 19168706 : Object* next_entry = get(EntryToIndex(entry) + kChainOffset);
493 19168706 : return Smi::ToInt(next_entry);
494 : }
495 :
496 : // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
497 23678076 : Object* KeyAt(int entry) {
498 : DCHECK_LT(entry, this->UsedCapacity());
499 23678076 : return get(EntryToIndex(entry));
500 : }
501 :
502 : bool IsObsolete() { return !get(kNextTableIndex)->IsSmi(); }
503 :
504 : // The next newer table. This is only valid if the table is obsolete.
505 : Derived* NextTable() { return Derived::cast(get(kNextTableIndex)); }
506 :
507 : // When the table is obsolete we store the indexes of the removed holes.
508 : int RemovedIndexAt(int index) {
509 0 : return Smi::ToInt(get(kRemovedHolesIndex + index));
510 : }
511 :
512 : static const int kEntrySize = entrysize + 1;
513 : static const int kChainOffset = entrysize;
514 :
515 : static const int kMaxCapacity =
516 : (FixedArray::kMaxLength - kHashTableStartIndex) /
517 : (1 + (kEntrySize * kLoadFactor));
518 :
519 : protected:
520 : static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
521 :
522 : void SetNumberOfBuckets(int num) {
523 : set(kNumberOfBucketsIndex, Smi::FromInt(num));
524 : }
525 :
526 : void SetNumberOfElements(int num) {
527 : set(kNumberOfElementsIndex, Smi::FromInt(num));
528 : }
529 :
530 : void SetNumberOfDeletedElements(int num) {
531 : set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
532 : }
533 :
534 : // Returns the number elements that can fit into the allocated buffer.
535 46928036 : int Capacity() { return NumberOfBuckets() * kLoadFactor; }
536 :
537 254676 : void SetNextTable(Derived* next_table) { set(kNextTableIndex, next_table); }
538 :
539 : void SetRemovedIndexAt(int index, int removed_index) {
540 : return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
541 : }
542 : };
543 :
544 : class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
545 : public:
546 : DECL_CAST(OrderedHashSet)
547 :
548 : static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table,
549 : Handle<Object> value);
550 : static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table,
551 : GetKeysConversion convert);
552 : };
553 :
554 : class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
555 : public:
556 : DECL_CAST(OrderedHashMap)
557 :
558 : // Returns a value if the OrderedHashMap contains the key, otherwise
559 : // returns undefined.
560 : static Handle<OrderedHashMap> Add(Handle<OrderedHashMap> table,
561 : Handle<Object> key, Handle<Object> value);
562 : Object* ValueAt(int entry);
563 :
564 : static Object* GetHash(Isolate* isolate, Object* key);
565 :
566 : static const int kValueOffset = 1;
567 : };
568 :
569 : template <int entrysize>
570 : class WeakHashTableShape : public BaseShape<Handle<Object>> {
571 : public:
572 : static inline bool IsMatch(Handle<Object> key, Object* other);
573 : static inline uint32_t Hash(Isolate* isolate, Handle<Object> key);
574 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
575 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
576 : static const int kPrefixSize = 0;
577 : static const int kEntrySize = entrysize;
578 : static const bool kNeedsHoleCheck = false;
579 : };
580 :
581 : // WeakHashTable maps keys that are arbitrary heap objects to heap object
582 : // values. The table wraps the keys in weak cells and store values directly.
583 : // Thus it references keys weakly and values strongly.
584 : class WeakHashTable : public HashTable<WeakHashTable, WeakHashTableShape<2>> {
585 : typedef HashTable<WeakHashTable, WeakHashTableShape<2>> DerivedHashTable;
586 :
587 : public:
588 : DECL_CAST(WeakHashTable)
589 :
590 : // Looks up the value associated with the given key. The hole value is
591 : // returned in case the key is not present.
592 : Object* Lookup(Handle<HeapObject> key);
593 :
594 : // Adds (or overwrites) the value associated with the given key. Mapping a
595 : // key to the hole value causes removal of the whole entry.
596 : MUST_USE_RESULT static Handle<WeakHashTable> Put(Handle<WeakHashTable> table,
597 : Handle<HeapObject> key,
598 : Handle<HeapObject> value);
599 :
600 : static Handle<FixedArray> GetValues(Handle<WeakHashTable> table);
601 :
602 : private:
603 : friend class MarkCompactCollector;
604 :
605 : void AddEntry(int entry, Handle<WeakCell> key, Handle<HeapObject> value);
606 :
607 : // Returns the index to the value of an entry.
608 : static inline int EntryToValueIndex(int entry) {
609 961304 : return EntryToIndex(entry) + 1;
610 : }
611 : };
612 :
613 : // This is similar to the OrderedHashTable, except for the memory
614 : // layout where we use byte instead of Smi. The max capacity of this
615 : // is only 254, we transition to an OrderedHashTable beyond that
616 : // limit.
617 : //
618 : // Each bucket and chain value is a byte long. The padding exists so
619 : // that the DataTable entries start aligned. A bucket or chain value
620 : // of 255 is used to denote an unknown entry.
621 : //
622 : // Memory layout: [ Header ] [ HashTable ] [ Chains ] [ Padding ] [ DataTable ]
623 : //
624 : // On a 64 bit machine with capacity = 4 and 2 entries,
625 : //
626 : // [ Header ] :
627 : // [0 .. 7] : Number of elements
628 : // [8 .. 15] : Number of deleted elements
629 : // [16 .. 23] : Number of buckets
630 : //
631 : // [ HashTable ] :
632 : // [24 .. 31] : First chain-link for bucket 1
633 : // [32 .. 40] : First chain-link for bucket 2
634 : //
635 : // [ Chains ] :
636 : // [40 .. 47] : Next chain link for entry 1
637 : // [48 .. 55] : Next chain link for entry 2
638 : // [56 .. 63] : Next chain link for entry 3
639 : // [64 .. 71] : Next chain link for entry 4
640 : //
641 : // [ Padding ] :
642 : // [72 .. 127] : Padding
643 : //
644 : // [ DataTable ] :
645 : // [128 .. 128 + kEntrySize - 1] : Entry 1
646 : // [128 + kEntrySize .. 128 + kEntrySize + kEntrySize - 1] : Entry 2
647 : //
648 : template <class Derived>
649 : class SmallOrderedHashTable : public HeapObject {
650 : public:
651 : void Initialize(Isolate* isolate, int capacity);
652 :
653 : static Handle<Derived> Allocate(Isolate* isolate, int capacity,
654 : PretenureFlag pretenure = NOT_TENURED);
655 :
656 : // Returns a true if the OrderedHashTable contains the key
657 : bool HasKey(Isolate* isolate, Handle<Object> key);
658 :
659 : // Iterates only fields in the DataTable.
660 : class BodyDescriptor;
661 :
662 : // No weak fields.
663 : typedef BodyDescriptor BodyDescriptorWeak;
664 :
665 : // Returns an SmallOrderedHashTable (possibly |table|) with enough
666 : // space to add at least one new element.
667 : static Handle<Derived> Grow(Handle<Derived> table);
668 :
669 : static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
670 :
671 : void SetDataEntry(int entry, int relative_index, Object* value);
672 :
673 : static int GetDataTableStartOffset(int capacity) {
674 108 : int nof_buckets = capacity / kLoadFactor;
675 : int nof_chain_entries = capacity;
676 :
677 38688 : int padding_index = kBucketsStartOffset + nof_buckets + nof_chain_entries;
678 38688 : int padding_offset = padding_index * kBitsPerByte;
679 :
680 38688 : return ((padding_offset + kPointerSize - 1) / kPointerSize) * kPointerSize;
681 : }
682 :
683 : int GetDataTableStartOffset() const {
684 : return GetDataTableStartOffset(Capacity());
685 : }
686 :
687 : static int Size(int capacity) {
688 : int data_table_start = GetDataTableStartOffset(capacity);
689 108 : int data_table_size = capacity * Derived::kEntrySize * kBitsPerPointer;
690 108 : return data_table_start + data_table_size;
691 : }
692 :
693 : int Size() const { return Size(Capacity()); }
694 :
695 : void SetFirstEntry(int bucket, byte value) {
696 : set(kBucketsStartOffset + bucket, value);
697 : }
698 :
699 : int GetFirstEntry(int bucket) const {
700 31392 : return get(kBucketsStartOffset + bucket);
701 : }
702 :
703 : void SetNextEntry(int entry, int next_entry) {
704 12288 : set(GetChainTableOffset() + entry, next_entry);
705 : }
706 :
707 : int GetNextEntry(int entry) const {
708 30600 : return get(GetChainTableOffset() + entry);
709 : }
710 :
711 : Object* GetDataEntry(int entry, int relative_index) {
712 : int entry_offset = GetDataEntryOffset(entry, relative_index);
713 4536 : return READ_FIELD(this, entry_offset);
714 : }
715 :
716 : Object* KeyAt(int entry) const {
717 : int entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex);
718 24720 : return READ_FIELD(this, entry_offset);
719 : }
720 :
721 15696 : int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }
722 :
723 : int HashToFirstEntry(int hash) const {
724 : int bucket = HashToBucket(hash);
725 : int entry = GetFirstEntry(bucket);
726 : return entry;
727 : }
728 :
729 : int GetChainTableOffset() const {
730 21444 : return kBucketsStartOffset + NumberOfBuckets();
731 : }
732 :
733 108 : void SetNumberOfBuckets(int num) { set(kNumberOfBucketsOffset, num); }
734 :
735 3192 : void SetNumberOfElements(int num) { set(kNumberOfElementsOffset, num); }
736 :
737 : void SetNumberOfDeletedElements(int num) {
738 : set(kNumberOfDeletedElementsOffset, num);
739 : }
740 :
741 6312 : int NumberOfElements() const { return get(kNumberOfElementsOffset); }
742 :
743 : int NumberOfDeletedElements() const {
744 6384 : return get(kNumberOfDeletedElementsOffset);
745 : }
746 :
747 78912 : int NumberOfBuckets() const { return get(kNumberOfBucketsOffset); }
748 :
749 : static const byte kNotFound = 0xFF;
750 : static const int kMinCapacity = 4;
751 :
752 : // We use the value 255 to indicate kNotFound for chain and bucket
753 : // values, which means that this value can't be used a valid
754 : // index.
755 : static const int kMaxCapacity = 254;
756 : STATIC_ASSERT(kMaxCapacity < kNotFound);
757 :
758 : static const int kNumberOfElementsOffset = 0;
759 : static const int kNumberOfDeletedElementsOffset = 1;
760 : static const int kNumberOfBucketsOffset = 2;
761 : static const int kBucketsStartOffset = 3;
762 :
763 : // The load factor is used to derive the number of buckets from
764 : // capacity during Allocation. We also depend on this to calaculate
765 : // the capacity from number of buckets after allocation. If we
766 : // decide to change kLoadFactor to something other than 2, capacity
767 : // should be stored as another field of this object.
768 : static const int kLoadFactor = 2;
769 : static const int kBitsPerPointer = kPointerSize * kBitsPerByte;
770 :
771 : // Our growth strategy involves doubling the capacity until we reach
772 : // kMaxCapacity, but since the kMaxCapacity is always less than 256,
773 : // we will never fully utilize this table. We special case for 256,
774 : // by changing the new capacity to be kMaxCapacity in
775 : // SmallOrderedHashTable::Grow.
776 : static const int kGrowthHack = 256;
777 :
778 : DECL_VERIFIER(SmallOrderedHashTable)
779 :
780 : protected:
781 : // This is used for accessing the non |DataTable| part of the
782 : // structure.
783 : byte get(int index) const {
784 123120 : return READ_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize));
785 : }
786 :
787 : void set(int index, byte value) {
788 15588 : WRITE_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize), value);
789 : }
790 :
791 : int GetDataEntryOffset(int entry, int relative_index) const {
792 : int datatable_start = GetDataTableStartOffset();
793 33936 : int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize;
794 13752 : int offset_in_entry = relative_index * kPointerSize;
795 38472 : return datatable_start + offset_in_datatable + offset_in_entry;
796 : }
797 :
798 : // Returns the number elements that can fit into the allocated buffer.
799 41772 : int Capacity() const { return NumberOfBuckets() * kLoadFactor; }
800 :
801 : int UsedCapacity() const {
802 3120 : return NumberOfElements() + NumberOfDeletedElements();
803 : }
804 : };
805 :
806 : class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
807 : public:
808 : DECL_CAST(SmallOrderedHashSet)
809 :
810 : DECL_PRINTER(SmallOrderedHashSet)
811 :
812 : static const int kKeyIndex = 0;
813 : static const int kEntrySize = 1;
814 :
815 : // Adds |value| to |table|, if the capacity isn't enough, a new
816 : // table is created. The original |table| is returned if there is
817 : // capacity to store |value| otherwise the new table is returned.
818 : static Handle<SmallOrderedHashSet> Add(Handle<SmallOrderedHashSet> table,
819 : Handle<Object> key);
820 : };
821 :
822 : class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
823 : public:
824 : DECL_CAST(SmallOrderedHashMap)
825 :
826 : DECL_PRINTER(SmallOrderedHashMap)
827 :
828 : static const int kKeyIndex = 0;
829 : static const int kValueIndex = 1;
830 : static const int kEntrySize = 2;
831 :
832 : // Adds |value| to |table|, if the capacity isn't enough, a new
833 : // table is created. The original |table| is returned if there is
834 : // capacity to store |value| otherwise the new table is returned.
835 : static Handle<SmallOrderedHashMap> Add(Handle<SmallOrderedHashMap> table,
836 : Handle<Object> key,
837 : Handle<Object> value);
838 : };
839 :
840 : class JSCollectionIterator : public JSObject {
841 : public:
842 : // [table]: the backing hash table mapping keys to values.
843 : DECL_ACCESSORS(table, Object)
844 :
845 : // [index]: The index into the data table.
846 : DECL_ACCESSORS(index, Object)
847 :
848 : // Dispatched behavior.
849 : DECL_PRINTER(JSCollectionIterator)
850 :
851 : static const int kTableOffset = JSObject::kHeaderSize;
852 : static const int kIndexOffset = kTableOffset + kPointerSize;
853 : static const int kSize = kIndexOffset + kPointerSize;
854 :
855 : private:
856 : DISALLOW_IMPLICIT_CONSTRUCTORS(JSCollectionIterator);
857 : };
858 :
859 : // OrderedHashTableIterator is an iterator that iterates over the keys and
860 : // values of an OrderedHashTable.
861 : //
862 : // The iterator has a reference to the underlying OrderedHashTable data,
863 : // [table], as well as the current [index] the iterator is at.
864 : //
865 : // When the OrderedHashTable is rehashed it adds a reference from the old table
866 : // to the new table as well as storing enough data about the changes so that the
867 : // iterator [index] can be adjusted accordingly.
868 : //
869 : // When the [Next] result from the iterator is requested, the iterator checks if
870 : // there is a newer table that it needs to transition to.
871 : template <class Derived, class TableType>
872 : class OrderedHashTableIterator : public JSCollectionIterator {
873 : public:
874 : // Whether the iterator has more elements. This needs to be called before
875 : // calling |CurrentKey| and/or |CurrentValue|.
876 : bool HasMore();
877 :
878 : // Move the index forward one.
879 0 : void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); }
880 :
881 : // Returns the current key of the iterator. This should only be called when
882 : // |HasMore| returns true.
883 : inline Object* CurrentKey();
884 :
885 : private:
886 : // Transitions the iterator to the non obsolete backing store. This is a NOP
887 : // if the [table] is not obsolete.
888 : void Transition();
889 :
890 : DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
891 : };
892 :
893 : class JSSetIterator
894 : : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> {
895 : public:
896 : // Dispatched behavior.
897 : DECL_PRINTER(JSSetIterator)
898 : DECL_VERIFIER(JSSetIterator)
899 :
900 : DECL_CAST(JSSetIterator)
901 :
902 : private:
903 : DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
904 : };
905 :
906 : class JSMapIterator
907 : : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> {
908 : public:
909 : // Dispatched behavior.
910 : DECL_PRINTER(JSMapIterator)
911 : DECL_VERIFIER(JSMapIterator)
912 :
913 : DECL_CAST(JSMapIterator)
914 :
915 : // Returns the current value of the iterator. This should only be called when
916 : // |HasMore| returns true.
917 : inline Object* CurrentValue();
918 :
919 : private:
920 : DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
921 : };
922 :
923 : } // namespace internal
924 : } // namespace v8
925 :
926 : #include "src/objects/object-macros-undef.h"
927 :
928 : #endif // V8_OBJECTS_HASH_TABLE_H_
|
