5 #ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_ 6 #define V8_OBJECTS_ORDERED_HASH_TABLE_H_ 8 #include "src/globals.h" 9 #include "src/objects/fixed-array.h" 10 #include "src/objects/js-objects.h" 11 #include "src/objects/smi.h" 14 #include "src/objects/object-macros.h" 55 template <
class Derived,
int entrysize>
60 PretenureFlag pretenure = NOT_TENURED);
76 static bool HasKey(
Isolate* isolate, Derived table,
Object* key);
80 static bool Delete(
Isolate* isolate, Derived table,
Object* key);
84 int NumberOfElements()
const {
85 return Smi::ToInt(
get(kNumberOfElementsIndex));
88 int NumberOfDeletedElements()
const {
89 return Smi::ToInt(
get(kNumberOfDeletedElementsIndex));
94 int UsedCapacity()
const {
95 return NumberOfElements() + NumberOfDeletedElements();
98 int NumberOfBuckets()
const {
return Smi::ToInt(
get(kNumberOfBucketsIndex)); }
101 int EntryToIndex(
int entry) {
102 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
105 int HashToBucket(
int hash) {
return hash & (NumberOfBuckets() - 1); }
107 int HashToEntry(
int hash) {
108 int bucket = HashToBucket(hash);
109 Object* entry = this->
get(kHashTableStartIndex + bucket);
110 return Smi::ToInt(entry);
113 int NextChainEntry(
int entry) {
114 Object* next_entry =
get(EntryToIndex(entry) + kChainOffset);
115 return Smi::ToInt(next_entry);
119 Object* KeyAt(
int entry) {
120 DCHECK_LT(entry, this->UsedCapacity());
121 return get(EntryToIndex(entry));
124 bool IsObsolete() {
return !
get(kNextTableIndex)->IsSmi(); }
127 Derived NextTable() {
return Derived::cast(
get(kNextTableIndex)); }
130 int RemovedIndexAt(
int index) {
131 return Smi::ToInt(
get(kRemovedHolesIndex + index));
134 static const int kEntrySize = entrysize + 1;
135 static const int kChainOffset = entrysize;
137 static const int kNotFound = -1;
138 static const int kMinCapacity = 4;
140 static const int kNumberOfElementsIndex = 0;
142 static const int kNextTableIndex = kNumberOfElementsIndex;
143 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
144 static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1;
145 static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1;
146 static const int kRemovedHolesIndex = kHashTableStartIndex;
148 static constexpr
const int kNumberOfElementsOffset =
149 FixedArray::OffsetOfElementAt(kNumberOfElementsIndex);
150 static constexpr
const int kNextTableOffset =
151 FixedArray::OffsetOfElementAt(kNextTableIndex);
152 static constexpr
const int kNumberOfDeletedElementsOffset =
153 FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex);
154 static constexpr
const int kNumberOfBucketsOffset =
155 FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex);
156 static constexpr
const int kHashTableStartOffset =
157 FixedArray::OffsetOfElementAt(kHashTableStartIndex);
159 static const int kLoadFactor = 2;
164 static const int kClearedTableSentinel = -1;
165 static const int kMaxCapacity =
166 (FixedArray::kMaxLength - kHashTableStartIndex) /
167 (1 + (kEntrySize * kLoadFactor));
173 void SetNumberOfBuckets(
int num) {
174 set(kNumberOfBucketsIndex, Smi::FromInt(num));
177 void SetNumberOfElements(
int num) {
178 set(kNumberOfElementsIndex, Smi::FromInt(num));
181 void SetNumberOfDeletedElements(
int num) {
182 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
186 int Capacity() {
return NumberOfBuckets() * kLoadFactor; }
188 void SetNextTable(Derived next_table) {
set(kNextTableIndex, next_table); }
190 void SetRemovedIndexAt(
int index,
int removed_index) {
191 return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
206 GetKeysConversion convert);
208 static inline RootIndex GetMapRootIndex();
223 Object* ValueAt(
int entry);
228 static inline RootIndex GetMapRootIndex();
231 static const int kValueOffset = 1;
274 template <
class Derived>
284 void Initialize(
Isolate* isolate,
int capacity);
287 PretenureFlag pretenure = NOT_TENURED);
294 static bool Delete(
Isolate* isolate, Derived table,
Object* key);
311 static int SizeFor(
int capacity) {
312 DCHECK_GE(capacity, kMinCapacity);
313 DCHECK_LE(capacity, kMaxCapacity);
315 int data_table_size = DataTableSizeFor(capacity);
316 int hash_table_size = capacity / kLoadFactor;
317 int chain_table_size = capacity;
318 int total_size = kDataTableStartOffset + data_table_size + hash_table_size +
321 return RoundUp(total_size, kPointerSize);
325 int Capacity()
const {
326 int capacity = NumberOfBuckets() * kLoadFactor;
327 DCHECK_GE(capacity, kMinCapacity);
328 DCHECK_LE(capacity, kMaxCapacity);
334 int NumberOfElements()
const {
335 int nof_elements = getByte(kNumberOfElementsOffset, 0);
336 DCHECK_LE(nof_elements, Capacity());
341 int NumberOfDeletedElements()
const {
342 int nof_deleted_elements = getByte(kNumberOfDeletedElementsOffset, 0);
343 DCHECK_LE(nof_deleted_elements, Capacity());
345 return nof_deleted_elements;
348 int NumberOfBuckets()
const {
return getByte(kNumberOfBucketsOffset, 0); }
352 static const int kMinCapacity = 4;
353 static const byte kNotFound = 0xFF;
358 static const int kMaxCapacity = 254;
359 STATIC_ASSERT(kMaxCapacity < kNotFound);
366 static const int kLoadFactor = 2;
373 static const int kGrowthHack = 256;
376 void SetDataEntry(
int entry,
int relative_index,
Object* value);
380 Offset GetBucketsStartOffset()
const {
381 int capacity = Capacity();
382 int data_table_size = DataTableSizeFor(capacity);
383 return kDataTableStartOffset + data_table_size;
386 Address GetHashTableStartAddress(
int capacity)
const {
387 return FIELD_ADDR(
this, kDataTableStartOffset + DataTableSizeFor(capacity));
390 void SetFirstEntry(
int bucket, byte value) {
391 DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
392 setByte(GetBucketsStartOffset(), bucket, value);
395 int GetFirstEntry(
int bucket)
const {
396 DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
397 return getByte(GetBucketsStartOffset(), bucket);
402 Offset GetChainTableOffset()
const {
403 int nof_buckets = NumberOfBuckets();
404 int capacity = nof_buckets * kLoadFactor;
405 DCHECK_EQ(Capacity(), capacity);
407 int data_table_size = DataTableSizeFor(capacity);
408 int hash_table_size = nof_buckets;
409 return kDataTableStartOffset + data_table_size + hash_table_size;
412 void SetNextEntry(
int entry,
int next_entry) {
413 DCHECK_LT(static_cast<unsigned>(entry), Capacity());
414 DCHECK_GE(static_cast<unsigned>(next_entry), 0);
415 DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
416 setByte(GetChainTableOffset(), entry, next_entry);
419 int GetNextEntry(
int entry)
const {
420 DCHECK_LT(entry, Capacity());
421 return getByte(GetChainTableOffset(), entry);
424 Object* GetDataEntry(
int entry,
int relative_index) {
425 DCHECK_LT(entry, Capacity());
426 DCHECK_LE(static_cast<unsigned>(relative_index), Derived::kEntrySize);
427 Offset entry_offset = GetDataEntryOffset(entry, relative_index);
428 return READ_FIELD(
this, entry_offset);
431 Object* KeyAt(
int entry)
const {
432 DCHECK_LT(entry, Capacity());
433 Offset entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex);
434 return READ_FIELD(
this, entry_offset);
437 int HashToBucket(
int hash)
const {
return hash & (NumberOfBuckets() - 1); }
439 int HashToFirstEntry(
int hash)
const {
440 int bucket = HashToBucket(hash);
441 int entry = GetFirstEntry(bucket);
442 DCHECK(entry < Capacity() || entry == kNotFound);
446 void SetNumberOfBuckets(
int num) { setByte(kNumberOfBucketsOffset, 0, num); }
448 void SetNumberOfElements(
int num) {
449 DCHECK_LE(static_cast<unsigned>(num), Capacity());
450 setByte(kNumberOfElementsOffset, 0, num);
453 void SetNumberOfDeletedElements(
int num) {
454 DCHECK_LE(static_cast<unsigned>(num), Capacity());
455 setByte(kNumberOfDeletedElementsOffset, 0, num);
458 static const Offset kNumberOfElementsOffset = kHeaderSize;
459 static const Offset kNumberOfDeletedElementsOffset =
460 kNumberOfElementsOffset + kOneByteSize;
461 static const Offset kNumberOfBucketsOffset =
462 kNumberOfDeletedElementsOffset + kOneByteSize;
463 static const constexpr
Offset kDataTableStartOffset =
464 RoundUp<kPointerSize>(kNumberOfBucketsOffset);
466 static constexpr
int DataTableSizeFor(
int capacity) {
467 return capacity * Derived::kEntrySize * kPointerSize;
473 DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset());
474 return READ_BYTE_FIELD(
this, offset + (index * kOneByteSize));
478 DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset());
479 WRITE_BYTE_FIELD(
this, offset + (index * kOneByteSize), value);
482 Offset GetDataEntryOffset(
int entry,
int relative_index)
const {
483 DCHECK_LT(entry, Capacity());
484 int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize;
485 int offset_in_entry = relative_index * kPointerSize;
486 return kDataTableStartOffset + offset_in_datatable + offset_in_entry;
489 int UsedCapacity()
const {
490 int used = NumberOfElements() + NumberOfDeletedElements();
491 DCHECK_LE(used, Capacity());
510 static const int kKeyIndex = 0;
511 static const int kEntrySize = 1;
520 static inline RootIndex GetMapRootIndex();
532 static const int kKeyIndex = 0;
533 static const int kValueIndex = 1;
534 static const int kEntrySize = 2;
544 static inline RootIndex GetMapRootIndex();
554 template <
class SmallTable,
class LargeTable>
565 static const int OrderedHashTableMinSize =
599 inline Object* ValueAt(
int entry);
602 inline void ValueAtPut(
int entry,
Object* value);
611 static inline RootIndex GetMapRootIndex();
613 static const int kValueOffset = 1;
614 static const int kPropertyDetailsOffset = 2;
628 inline Object* ValueAt(
int entry);
631 inline void ValueAtPut(
int entry,
Object* value);
639 static const int kKeyIndex = 0;
640 static const int kValueIndex = 1;
641 static const int kPropertyDetailsIndex = 2;
642 static const int kEntrySize = 3;
650 static inline RootIndex GetMapRootIndex();
659 DECL_ACCESSORS(table,
Object)
662 DECL_ACCESSORS(index,
Object)
664 void JSCollectionIteratorPrint(std::ostream& os,
const char* name);
666 static const int kTableOffset = JSObject::kHeaderSize;
667 static const int kIndexOffset = kTableOffset + kPointerSize;
668 static const int kSize = kIndexOffset + kPointerSize;
686 template <
class Derived,
class TableType>
694 void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); }
698 inline Object* CurrentKey();
711 #include "src/objects/object-macros-undef.h" 713 #endif // V8_OBJECTS_ORDERED_HASH_TABLE_H_