Lines Matching full:table
5 #include "src/objects/ordered-hash-table.h"
10 #include "src/objects/ordered-hash-table-inl.h"
25 isolate->heap()->FatalProcessOutOfMemory("invalid table size"); in Allocate()
31 Handle<Derived> table = Handle<Derived>::cast(backing_store); in Allocate() local
33 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); in Allocate()
35 table->SetNumberOfBuckets(num_buckets); in Allocate()
36 table->SetNumberOfElements(0); in Allocate()
37 table->SetNumberOfDeletedElements(0); in Allocate()
38 return table; in Allocate()
43 Isolate* isolate, Handle<Derived> table) { in EnsureGrowable() argument
44 DCHECK(!table->IsObsolete()); in EnsureGrowable()
46 int nof = table->NumberOfElements(); in EnsureGrowable()
47 int nod = table->NumberOfDeletedElements(); in EnsureGrowable()
48 int capacity = table->Capacity(); in EnsureGrowable()
49 if ((nof + nod) < capacity) return table; in EnsureGrowable()
52 // a new table. in EnsureGrowable()
53 return Rehash(isolate, table, in EnsureGrowable()
59 Isolate* isolate, Handle<Derived> table) { in Shrink() argument
60 DCHECK(!table->IsObsolete()); in Shrink()
62 int nof = table->NumberOfElements(); in Shrink()
63 int capacity = table->Capacity(); in Shrink()
64 if (nof >= (capacity >> 2)) return table; in Shrink()
65 return Rehash(isolate, table, capacity / 2); in Shrink()
70 Isolate* isolate, Handle<Derived> table) { in Clear() argument
71 DCHECK(!table->IsObsolete()); in Clear()
74 isolate, kMinCapacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); in Clear()
76 table->SetNextTable(*new_table); in Clear()
77 table->SetNumberOfDeletedElements(kClearedTableSentinel); in Clear()
84 Derived* table, Object* key) { in HasKey() argument
85 DCHECK((entrysize == 1 && table->IsOrderedHashSet()) || in HasKey()
86 (entrysize == 2 && table->IsOrderedHashMap())); in HasKey()
88 int entry = table->FindEntry(isolate, key); in HasKey()
93 Handle<OrderedHashSet> table, in Add() argument
96 int entry = table->HashToEntry(hash); in Add()
99 Object* candidate_key = table->KeyAt(entry); in Add()
101 if (candidate_key->SameValueZero(*key)) return table; in Add()
102 entry = table->NextChainEntry(entry); in Add()
105 table = OrderedHashSet::EnsureGrowable(isolate, table); in Add()
107 int bucket = table->HashToBucket(hash); in Add()
108 int previous_entry = table->HashToEntry(hash); in Add()
109 int nof = table->NumberOfElements(); in Add()
111 int new_entry = nof + table->NumberOfDeletedElements(); in Add()
112 int new_index = table->EntryToIndex(new_entry); in Add()
113 table->set(new_index, *key); in Add()
114 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry)); in Add()
116 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); in Add()
117 table->SetNumberOfElements(nof + 1); in Add()
118 return table; in Add()
122 Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) { in ConvertToKeysArray() argument
123 int length = table->NumberOfElements(); in ConvertToKeysArray()
124 int nof_buckets = table->NumberOfBuckets(); in ConvertToKeysArray()
126 Handle<FixedArray> result = Handle<FixedArray>::cast(table); in ConvertToKeysArray()
127 // From this point on table is no longer a valid OrderedHashSet. in ConvertToKeysArray()
133 Object* key = table->get(index); in ConvertToKeysArray()
159 Isolate* isolate, Handle<Derived> table, int new_capacity) { in Rehash() argument
160 DCHECK(!table->IsObsolete()); in Rehash()
163 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); in Rehash()
164 int nof = table->NumberOfElements(); in Rehash()
165 int nod = table->NumberOfDeletedElements(); in Rehash()
172 Object* key = table->KeyAt(old_entry); in Rehash()
174 table->SetRemovedIndexAt(removed_holes_index++, old_entry); in Rehash()
183 int old_index = table->EntryToIndex(old_entry); in Rehash()
185 Object* value = table->get(old_index + i); in Rehash()
195 table->SetNextTable(*new_table); in Rehash()
202 Derived* table, Object* key) { in Delete() argument
204 int entry = table->FindEntry(isolate, key); in Delete()
207 int nof = table->NumberOfElements(); in Delete()
208 int nod = table->NumberOfDeletedElements(); in Delete()
209 int index = table->EntryToIndex(entry); in Delete()
213 table->set(index + i, hole); in Delete()
216 table->SetNumberOfElements(nof - 1); in Delete()
217 table->SetNumberOfDeletedElements(nod + 1); in Delete()
234 Handle<OrderedHashMap> table, in Add() argument
238 int entry = table->HashToEntry(hash); in Add()
244 Object* candidate_key = table->KeyAt(entry); in Add()
246 if (candidate_key->SameValueZero(raw_key)) return table; in Add()
247 entry = table->NextChainEntry(entry); in Add()
251 table = OrderedHashMap::EnsureGrowable(isolate, table); in Add()
253 int bucket = table->HashToBucket(hash); in Add()
254 int previous_entry = table->HashToEntry(hash); in Add()
255 int nof = table->NumberOfElements(); in Add()
257 int new_entry = nof + table->NumberOfDeletedElements(); in Add()
258 int new_index = table->EntryToIndex(new_entry); in Add()
259 table->set(new_index, *key); in Add()
260 table->set(new_index + kValueOffset, *value); in Add()
261 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry)); in Add()
263 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); in Add()
264 table->SetNumberOfElements(nof + 1); in Add()
265 return table; in Add()
273 Isolate* isolate, Handle<OrderedHashSet> table);
276 Isolate* isolate, Handle<OrderedHashSet> table);
279 Isolate* isolate, Handle<OrderedHashSet> table);
282 OrderedHashSet* table,
286 OrderedHashSet* table,
294 Isolate* isolate, Handle<OrderedHashMap> table);
297 Isolate* isolate, Handle<OrderedHashMap> table);
300 Isolate* isolate, Handle<OrderedHashMap> table);
303 OrderedHashMap* table,
307 OrderedHashMap* table,
371 Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) { in Add() argument
372 if (table->HasKey(isolate, key)) return table; in Add()
374 if (table->UsedCapacity() >= table->Capacity()) { in Add()
376 SmallOrderedHashSet::Grow(isolate, table); in Add()
377 if (!new_table.ToHandle(&table)) { in Add()
383 int nof = table->NumberOfElements(); in Add()
386 int bucket = table->HashToBucket(hash); in Add()
387 int previous_entry = table->HashToFirstEntry(hash); in Add()
390 int new_entry = nof + table->NumberOfDeletedElements(); in Add()
392 table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key); in Add()
393 table->SetFirstEntry(bucket, new_entry); in Add()
394 table->SetNextEntry(new_entry, previous_entry); in Add()
397 table->SetNumberOfElements(nof + 1); in Add()
399 return table; in Add()
403 Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key, in Add() argument
405 if (table->HasKey(isolate, key)) return table; in Add()
407 if (table->UsedCapacity() >= table->Capacity()) { in Add()
409 SmallOrderedHashMap::Grow(isolate, table); in Add()
410 if (!new_table.ToHandle(&table)) { in Add()
416 int nof = table->NumberOfElements(); in Add()
419 int bucket = table->HashToBucket(hash); in Add()
420 int previous_entry = table->HashToFirstEntry(hash); in Add()
423 int new_entry = nof + table->NumberOfDeletedElements(); in Add()
425 table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value); in Add()
426 table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key); in Add()
427 table->SetFirstEntry(bucket, new_entry); in Add()
428 table->SetNextEntry(new_entry, previous_entry); in Add()
431 table->SetNumberOfElements(nof + 1); in Add()
433 return table; in Add()
444 bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived* table, in Delete() argument
447 int entry = table->FindEntry(isolate, key); in Delete()
450 int nof = table->NumberOfElements(); in Delete()
451 int nod = table->NumberOfDeletedElements(); in Delete()
455 table->SetDataEntry(entry, j, hole); in Delete()
458 table->SetNumberOfElements(nof - 1); in Delete()
459 table->SetNumberOfDeletedElements(nod + 1); in Delete()
466 Handle<Derived> table, in Rehash() argument
471 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); in Rehash()
472 int nof = table->NumberOfElements(); in Rehash()
473 int nod = table->NumberOfDeletedElements(); in Rehash()
479 Object* key = table->KeyAt(old_entry); in Rehash()
490 Object* value = table->GetDataEntry(old_entry, i); in Rehash()
504 Isolate* isolate, Handle<Derived> table) { in Grow() argument
505 int capacity = table->Capacity(); in Grow()
509 // TODO(gsathya): Compact in place, instead of allocating a new table. in Grow()
510 if (table->NumberOfDeletedElements() < (capacity >> 1)) { in Grow()
513 // The max capacity of our table is 254. We special case for 256 to in Grow()
515 // to 128 entries in our table. in Grow()
520 // We need to migrate to a bigger hash table. in Grow()
526 return Rehash(isolate, table, new_capacity); in Grow()
533 Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
536 Isolate* isolate, Handle<SmallOrderedHashSet> table);
544 Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
547 Isolate* isolate, Handle<SmallOrderedHashMap> table);
552 Isolate* isolate, SmallOrderedHashMap* table, Object* key);
554 Isolate* isolate, SmallOrderedHashSet* table, Object* key);
575 Handle<HeapObject> table, Handle<Object> key) { in Delete() argument
576 if (SmallTable::Is(table)) { in Delete()
577 return SmallTable::Delete(Handle<SmallTable>::cast(table), key); in Delete()
580 DCHECK(LargeTable::Is(table)); in Delete()
581 // Note: Once we migrate to the a big hash table, we never migrate in Delete()
582 // down to a smaller hash table. in Delete()
583 return LargeTable::Delete(Handle<LargeTable>::cast(table), key); in Delete()
588 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) { in HasKey() argument
589 if (SmallTable::Is(table)) { in HasKey()
590 return Handle<SmallTable>::cast(table)->HasKey(isolate, key); in HasKey()
593 DCHECK(LargeTable::Is(table)); in HasKey()
594 return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key); in HasKey()
599 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
602 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
605 Isolate* isolate, Handle<SmallOrderedHashMap> table) { in AdjustRepresentation() argument
608 int nof = table->NumberOfElements(); in AdjustRepresentation()
609 int nod = table->NumberOfDeletedElements(); in AdjustRepresentation()
615 Handle<Object> key = handle(table->KeyAt(entry), isolate); in AdjustRepresentation()
618 table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate); in AdjustRepresentation()
626 Isolate* isolate, Handle<SmallOrderedHashSet> table) { in AdjustRepresentation() argument
629 int nof = table->NumberOfElements(); in AdjustRepresentation()
630 int nod = table->NumberOfDeletedElements(); in AdjustRepresentation()
636 Handle<Object> key = handle(table->KeyAt(entry), isolate); in AdjustRepresentation()
645 Handle<HeapObject> table, in Add() argument
648 if (table->IsSmallOrderedHashMap()) { in Add()
650 Handle<SmallOrderedHashMap>::cast(table); in Add()
655 // We couldn't add to the small table, let's migrate to the in Add()
656 // big table. in Add()
657 table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map); in Add()
660 DCHECK(table->IsOrderedHashMap()); in Add()
661 return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key, in Add()
666 Handle<HeapObject> table, in Add() argument
668 if (table->IsSmallOrderedHashSet()) { in Add()
670 Handle<SmallOrderedHashSet>::cast(table); in Add()
675 // We couldn't add to the small table, let's migrate to the in Add()
676 // big table. in Add()
677 table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set); in Add()
680 DCHECK(table->IsOrderedHashSet()); in Add()
681 return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key); in Add()
687 TableType* table = TableType::cast(this->table()); in Transition() local
688 if (!table->IsObsolete()) return; in Transition()
691 while (table->IsObsolete()) { in Transition()
692 TableType* next_table = table->NextTable(); in Transition()
695 int nod = table->NumberOfDeletedElements(); in Transition()
702 int removed_index = table->RemovedIndexAt(i); in Transition()
709 table = next_table; in Transition()
712 set_table(table); in Transition()
723 TableType* table = TableType::cast(this->table()); in HasMore() local
725 int used_capacity = table->UsedCapacity(); in HasMore()
727 while (index < used_capacity && table->KeyAt(index)->IsTheHole(ro_roots)) { in HasMore()