Lines Matching refs:table
5 #include "src/objects/ordered-hash-table.h"
12 #include "src/objects/ordered-hash-table-inl.h"
37 Handle<Derived> table = Handle<Derived>::cast(backing_store);
39 table->set(HashTableStartIndex() + i, Smi::FromInt(kNotFound));
41 table->SetNumberOfBuckets(num_buckets);
42 table->SetNumberOfElements(0);
43 table->SetNumberOfDeletedElements(0);
44 return table;
52 // Requires that the map has already been set up in the roots table.
58 Handle<Derived> table = Handle<Derived>::cast(backing_store);
59 table->SetNumberOfBuckets(0);
60 table->SetNumberOfElements(0);
61 table->SetNumberOfDeletedElements(0);
62 return table;
68 IsolateT* isolate, Handle<Derived> table) {
69 DCHECK(!table->IsObsolete());
71 int nof = table->NumberOfElements();
72 int nod = table->NumberOfDeletedElements();
73 int capacity = table->Capacity();
74 if ((nof + nod) < capacity) return table;
83 // a new table.
89 return Derived::Rehash(isolate, table, new_capacity);
94 Isolate* isolate, Handle<Derived> table) {
95 DCHECK(!table->IsObsolete());
97 int nof = table->NumberOfElements();
98 int capacity = table->Capacity();
99 if (nof >= (capacity >> 2)) return table;
100 return Derived::Rehash(isolate, table, capacity / 2).ToHandleChecked();
105 Isolate* isolate, Handle<Derived> table) {
106 DCHECK(!table->IsObsolete());
108 AllocationType allocation_type = Heap::InYoungGeneration(*table)
115 if (table->NumberOfBuckets() > 0) {
116 // Don't try to modify the empty canonical table which lives in RO space.
117 table->SetNextTable(*new_table);
118 table->SetNumberOfDeletedElements(kClearedTableSentinel);
126 Derived table, Object key) {
127 DCHECK_IMPLIES(entrysize == 1, table.IsOrderedHashSet());
128 DCHECK_IMPLIES(entrysize == 2, table.IsOrderedHashMap());
130 InternalIndex entry = table.FindEntry(isolate, key);
168 Handle<OrderedHashSet> table,
171 if (table->NumberOfElements() > 0) {
172 int raw_entry = table->HashToEntryRaw(hash);
175 Object candidate_key = table->KeyAt(InternalIndex(raw_entry));
177 if (candidate_key.SameValueZero(*key)) return table;
178 raw_entry = table->NextChainEntryRaw(raw_entry);
183 OrderedHashSet::EnsureGrowable(isolate, table);
184 if (!table_candidate.ToHandle(&table)) {
188 int bucket = table->HashToBucket(hash);
189 int previous_entry = table->HashToEntryRaw(hash);
190 int nof = table->NumberOfElements();
192 int new_entry = nof + table->NumberOfDeletedElements();
193 int new_index = table->EntryToIndexRaw(new_entry);
194 table->set(new_index, *key);
195 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
197 table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
198 table->SetNumberOfElements(nof + 1);
199 return table;
203 Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) {
204 int length = table->NumberOfElements();
205 int nof_buckets = table->NumberOfBuckets();
207 Handle<FixedArray> result = Handle<FixedArray>::cast(table);
208 // From this point on table is no longer a valid OrderedHashSet.
214 Object key = table->get(index);
243 IsolateT* isolate, Handle<Derived> table) {
244 return OrderedHashTable<Derived, entrysize>::Rehash(isolate, table,
245 table->Capacity());
251 IsolateT* isolate, Handle<Derived> table, int new_capacity) {
252 DCHECK(!table->IsObsolete());
256 Heap::InYoungGeneration(*table) ? AllocationType::kYoung
268 for (InternalIndex old_entry : table->IterateEntries()) {
270 Object key = table->KeyAt(old_entry);
272 table->SetRemovedIndexAt(removed_holes_index++, old_entry_raw);
281 int old_index = table->EntryToIndexRaw(old_entry_raw);
283 Object value = table->get(old_index + i);
290 DCHECK_EQ(table->NumberOfDeletedElements(), removed_holes_index);
292 new_table->SetNumberOfElements(table->NumberOfElements());
293 if (table->NumberOfBuckets() > 0) {
294 // Don't try to modify the empty canonical table which lives in RO space.
295 table->SetNextTable(*new_table);
302 Handle<OrderedHashSet> table,
304 return Base::Rehash(isolate, table, new_capacity);
308 Isolate* isolate, Handle<OrderedHashSet> table) {
309 return Base::Rehash(isolate, table);
313 Isolate* isolate, Handle<OrderedHashMap> table) {
314 return Base::Rehash(isolate, table);
318 Handle<OrderedHashMap> table,
320 return Base::Rehash(isolate, table, new_capacity);
325 IsolateT* isolate, Handle<OrderedNameDictionary> table, int new_capacity) {
327 Base::Rehash(isolate, table, new_capacity);
330 new_table->SetHash(table->Hash());
337 Derived table, Object key) {
339 InternalIndex entry = table.FindEntry(isolate, key);
342 int nof = table.NumberOfElements();
343 int nod = table.NumberOfDeletedElements();
344 int index = table.EntryToIndex(entry);
348 table.set(index + i, hole);
351 table.SetNumberOfElements(nof - 1);
352 table.SetNumberOfDeletedElements(nod + 1);
369 Handle<OrderedHashMap> table,
373 if (table->NumberOfElements() > 0) {
374 int raw_entry = table->HashToEntryRaw(hash);
380 Object candidate_key = table->KeyAt(InternalIndex(raw_entry));
382 if (candidate_key.SameValueZero(raw_key)) return table;
383 raw_entry = table->NextChainEntryRaw(raw_entry);
389 OrderedHashMap::EnsureGrowable(isolate, table);
390 if (!table_candidate.ToHandle(&table)) {
394 int bucket = table->HashToBucket(hash);
395 int previous_entry = table->HashToEntryRaw(hash);
396 int nof = table->NumberOfElements();
398 int new_entry = nof + table->NumberOfDeletedElements();
399 int new_index = table->EntryToIndexRaw(new_entry);
400 table->set(new_index, *key);
401 table->set(new_index + kValueOffset, *value);
402 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
404 table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
405 table->SetNumberOfElements(nof + 1);
406 return table;
438 // table for every iteration. This should be peeled out of the
448 IsolateT* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
451 DCHECK(table->FindEntry(isolate, *key).is_not_found());
454 OrderedNameDictionary::EnsureGrowable(isolate, table);
455 if (!table_candidate.ToHandle(&table)) {
460 int bucket = table->HashToBucket(hash);
461 int previous_entry = table->HashToEntryRaw(hash);
462 int nof = table->NumberOfElements();
464 int new_entry = nof + table->NumberOfDeletedElements();
465 int new_index = table->EntryToIndexRaw(new_entry);
466 table->set(new_index, *key);
467 table->set(new_index + kValueOffset, *value);
472 table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
474 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
476 table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
477 table->SetNumberOfElements(nof + 1);
478 return table;
497 Isolate* isolate, Handle<OrderedNameDictionary> table,
503 table->SetEntry(entry, hole, hole, details);
505 int nof = table->NumberOfElements();
506 table->SetNumberOfElements(nof - 1);
507 int nod = table->NumberOfDeletedElements();
508 table->SetNumberOfDeletedElements(nod + 1);
510 return Shrink(isolate, table);
530 Handle<OrderedNameDictionary> table;
531 if (table_candidate.ToHandle(&table)) {
532 table->SetHash(PropertyArray::kNoHashSentinel);
554 Handle<OrderedNameDictionary> table;
555 if (table_candidate.ToHandle(&table)) {
556 table->SetHash(PropertyArray::kNoHashSentinel);
564 Isolate* isolate, Handle<OrderedHashSet> table);
568 Handle<OrderedHashSet> table);
572 Handle<OrderedHashSet> table);
578 Isolate* isolate, OrderedHashSet table, Object key);
581 Isolate* isolate, OrderedHashSet table, Object key);
588 Isolate* isolate, Handle<OrderedHashMap> table);
592 Handle<OrderedHashMap> table);
596 Handle<OrderedHashMap> table);
602 Isolate* isolate, OrderedHashMap table, Object key);
605 Isolate* isolate, OrderedHashMap table, Object key);
612 Isolate* isolate, Handle<OrderedNameDictionary> table);
616 Isolate* isolate, Handle<OrderedNameDictionary> table);
628 Handle<OrderedNameDictionary> table,
639 Handle<OrderedNameDictionary> table,
645 Handle<OrderedNameDictionary> table,
710 Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) {
711 if (table->HasKey(isolate, key)) return table;
713 if (table->UsedCapacity() >= table->Capacity()) {
715 SmallOrderedHashSet::Grow(isolate, table);
716 if (!new_table.ToHandle(&table)) {
722 int nof = table->NumberOfElements();
725 int bucket = table->HashToBucket(hash);
726 int previous_entry = table->HashToFirstEntry(hash);
729 int new_entry = nof + table->NumberOfDeletedElements();
731 table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key);
732 table->SetFirstEntry(bucket, new_entry);
733 table->SetNextEntry(new_entry, previous_entry);
736 table->SetNumberOfElements(nof + 1);
738 return table;
741 bool SmallOrderedHashSet::Delete(Isolate* isolate, SmallOrderedHashSet table,
743 return SmallOrderedHashTable<SmallOrderedHashSet>::Delete(isolate, table,
752 Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
754 if (table->HasKey(isolate, key)) return table;
756 if (table->UsedCapacity() >= table->Capacity()) {
758 SmallOrderedHashMap::Grow(isolate, table);
759 if (!new_table.ToHandle(&table)) {
765 int nof = table->NumberOfElements();
768 int bucket = table->HashToBucket(hash);
769 int previous_entry = table->HashToFirstEntry(hash);
772 int new_entry = nof + table->NumberOfDeletedElements();
774 table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value);
775 table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
776 table->SetFirstEntry(bucket, new_entry);
777 table->SetNextEntry(new_entry, previous_entry);
780 table->SetNumberOfElements(nof + 1);
782 return table;
785 bool SmallOrderedHashMap::Delete(Isolate* isolate, SmallOrderedHashMap table,
787 return SmallOrderedHashTable<SmallOrderedHashMap>::Delete(isolate, table,
817 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
820 DCHECK(table->FindEntry(isolate, *key).is_not_found());
822 if (table->UsedCapacity() >= table->Capacity()) {
824 SmallOrderedNameDictionary::Grow(isolate, table);
825 if (!new_table.ToHandle(&table)) {
830 int nof = table->NumberOfElements();
834 int bucket = table->HashToBucket(hash);
835 int previous_entry = table->HashToFirstEntry(hash);
838 int new_entry = nof + table->NumberOfDeletedElements();
840 table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
842 table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
845 // data table to save more memory.
846 table->SetDataEntry(new_entry,
849 table->SetFirstEntry(bucket, new_entry);
850 table->SetNextEntry(new_entry, previous_entry);
853 table->SetNumberOfElements(nof + 1);
855 return table;
867 // data table to save more memory.
880 bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
883 InternalIndex entry = table.FindEntry(isolate, key);
886 int nof = table.NumberOfElements();
887 int nod = table.NumberOfDeletedElements();
891 table.SetDataEntry(entry.as_int(), j, hole);
894 table.SetNumberOfElements(nof - 1);
895 table.SetNumberOfDeletedElements(nod + 1);
901 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
908 table->SetEntry(entry, hole, hole, details);
910 int nof = table->NumberOfElements();
911 table->SetNumberOfElements(nof - 1);
912 int nod = table->NumberOfDeletedElements();
913 table->SetNumberOfDeletedElements(nod + 1);
915 return Shrink(isolate, table);
920 Handle<Derived> table,
926 Heap::InYoungGeneration(*table) ? AllocationType::kYoung
932 for (InternalIndex old_entry : table->IterateEntries()) {
933 Object key = table->KeyAt(old_entry);
944 Object value = table->GetDataEntry(old_entry.as_int(), i);
951 new_table->SetNumberOfElements(table->NumberOfElements());
957 Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity) {
958 return SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(isolate, table,
963 Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity) {
964 return SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(isolate, table,
969 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
972 SmallOrderedHashTable<SmallOrderedNameDictionary>::Rehash(isolate, table,
974 new_table->SetHash(table->Hash());
980 Handle<Derived> table) {
981 int nof = table->NumberOfElements();
982 int capacity = table->Capacity();
983 if (nof >= (capacity >> 2)) return table;
984 return Derived::Rehash(isolate, table, capacity / 2);
989 Isolate* isolate, Handle<Derived> table) {
990 int capacity = table->Capacity();
994 // TODO(gsathya): Compact in place, instead of allocating a new table.
995 if (table->NumberOfDeletedElements() < (capacity >> 1)) {
998 // The max capacity of our table is 254. We special case for 256 to
1000 // to 128 entries in our table.
1005 // We need to migrate to a bigger hash table.
1011 return Derived::Rehash(isolate, table, new_capacity);
1038 Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
1041 Isolate* isolate, Handle<SmallOrderedHashSet> table);
1044 Isolate* isolate, Handle<SmallOrderedHashSet> table);
1050 SmallOrderedHashSet table,
1057 Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
1060 Isolate* isolate, Handle<SmallOrderedHashMap> table);
1063 Isolate* isolate, Handle<SmallOrderedHashMap> table);
1070 SmallOrderedHashMap table,
1078 Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
1104 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
1105 if (SmallTable::Is(table)) {
1106 return SmallTable::Delete(isolate, *Handle<SmallTable>::cast(table), *key);
1109 DCHECK(LargeTable::Is(table));
1110 // Note: Once we migrate to the a big hash table, we never migrate
1111 // down to a smaller hash table.
1112 return LargeTable::Delete(isolate, *Handle<LargeTable>::cast(table), *key);
1117 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
1118 if (SmallTable::Is(table)) {
1119 return Handle<SmallTable>::cast(table)->HasKey(isolate, key);
1122 DCHECK(LargeTable::Is(table));
1123 return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key);
1128 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
1131 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
1135 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
1138 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
1142 Handle<HeapObject> table,
1146 Isolate* isolate, Handle<SmallOrderedHashMap> table) {
1157 for (InternalIndex entry : table->IterateEntries()) {
1158 Handle<Object> key = handle(table->KeyAt(entry), isolate);
1161 table->GetDataEntry(entry.as_int(), SmallOrderedHashMap::kValueIndex),
1173 Isolate* isolate, Handle<SmallOrderedHashSet> table) {
1184 for (InternalIndex entry : table->IterateEntries()) {
1185 Handle<Object> key = handle(table->KeyAt(entry), isolate);
1198 Isolate* isolate, Handle<SmallOrderedNameDictionary> table) {
1209 for (InternalIndex entry : table->IterateEntries()) {
1210 Handle<Name> key(Name::cast(table->KeyAt(entry)), isolate);
1212 Handle<Object> value(table->ValueAt(entry), isolate);
1213 PropertyDetails details = table->DetailsAt(entry);
1225 Handle<HeapObject> table,
1228 if (table->IsSmallOrderedHashMap()) {
1230 Handle<SmallOrderedHashMap>::cast(table);
1235 // We couldn't add to the small table, let's migrate to the
1236 // big table.
1239 if (!table_candidate.ToHandle(&table)) {
1244 DCHECK(table->IsOrderedHashMap());
1245 return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
1250 Handle<HeapObject> table,
1252 if (table->IsSmallOrderedHashSet()) {
1254 Handle<SmallOrderedHashSet>::cast(table);
1259 // We couldn't add to the small table, let's migrate to the
1260 // big table.
1263 if (!table_candidate.ToHandle(&table)) {
1268 DCHECK(table->IsOrderedHashSet());
1269 return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
1273 Isolate* isolate, Handle<HeapObject> table, Handle<Name> key,
1275 if (table->IsSmallOrderedNameDictionary()) {
1277 Handle<SmallOrderedNameDictionary>::cast(table);
1283 // We couldn't add to the small table, let's migrate to the
1284 // big table.
1287 if (!table_candidate.ToHandle(&table)) {
1292 DCHECK(table->IsOrderedNameDictionary());
1294 isolate, Handle<OrderedNameDictionary>::cast(table), key, value, details);
1297 void OrderedNameDictionaryHandler::SetEntry(HeapObject table,
1302 if (table.IsSmallOrderedNameDictionary()) {
1303 return SmallOrderedNameDictionary::cast(table).SetEntry(entry, key, value,
1307 DCHECK(table.IsOrderedNameDictionary());
1308 return OrderedNameDictionary::cast(table).SetEntry(InternalIndex(entry), key,
1313 HeapObject table,
1316 if (table.IsSmallOrderedNameDictionary()) {
1317 return SmallOrderedNameDictionary::cast(table).FindEntry(isolate, key);
1320 DCHECK(table.IsOrderedNameDictionary());
1321 return OrderedNameDictionary::cast(table).FindEntry(isolate, key);
1324 Object OrderedNameDictionaryHandler::ValueAt(HeapObject table,
1326 if (table.IsSmallOrderedNameDictionary()) {
1327 return SmallOrderedNameDictionary::cast(table).ValueAt(entry);
1330 DCHECK(table.IsOrderedNameDictionary());
1331 return OrderedNameDictionary::cast(table).ValueAt(entry);
1334 void OrderedNameDictionaryHandler::ValueAtPut(HeapObject table,
1337 if (table.IsSmallOrderedNameDictionary()) {
1338 return SmallOrderedNameDictionary::cast(table).ValueAtPut(entry, value);
1341 DCHECK(table.IsOrderedNameDictionary());
1342 OrderedNameDictionary::cast(table).ValueAtPut(entry, value);
1345 PropertyDetails OrderedNameDictionaryHandler::DetailsAt(HeapObject table,
1347 if (table.IsSmallOrderedNameDictionary()) {
1348 return SmallOrderedNameDictionary::cast(table).DetailsAt(entry);
1351 DCHECK(table.IsOrderedNameDictionary());
1352 return OrderedNameDictionary::cast(table).DetailsAt(entry);
1355 void OrderedNameDictionaryHandler::DetailsAtPut(HeapObject table,
1358 if (table.IsSmallOrderedNameDictionary()) {
1359 return SmallOrderedNameDictionary::cast(table).DetailsAtPut(entry, details);
1362 DCHECK(table.IsOrderedNameDictionary());
1363 OrderedNameDictionary::cast(table).DetailsAtPut(entry, details);
1366 int OrderedNameDictionaryHandler::Hash(HeapObject table) {
1367 if (table.IsSmallOrderedNameDictionary()) {
1368 return SmallOrderedNameDictionary::cast(table).Hash();
1371 DCHECK(table.IsOrderedNameDictionary());
1372 return OrderedNameDictionary::cast(table).Hash();
1375 void OrderedNameDictionaryHandler::SetHash(HeapObject table, int hash) {
1376 if (table.IsSmallOrderedNameDictionary()) {
1377 return SmallOrderedNameDictionary::cast(table).SetHash(hash);
1380 DCHECK(table.IsOrderedNameDictionary());
1381 OrderedNameDictionary::cast(table).SetHash(hash);
1384 Name OrderedNameDictionaryHandler::KeyAt(HeapObject table,
1386 if (table.IsSmallOrderedNameDictionary()) {
1387 return Name::cast(SmallOrderedNameDictionary::cast(table).KeyAt(entry));
1391 OrderedNameDictionary::cast(table).KeyAt(InternalIndex(entry)));
1394 int OrderedNameDictionaryHandler::NumberOfElements(HeapObject table) {
1395 if (table.IsSmallOrderedNameDictionary()) {
1396 return SmallOrderedNameDictionary::cast(table).NumberOfElements();
1399 return OrderedNameDictionary::cast(table).NumberOfElements();
1402 int OrderedNameDictionaryHandler::Capacity(HeapObject table) {
1403 if (table.IsSmallOrderedNameDictionary()) {
1404 return SmallOrderedNameDictionary::cast(table).Capacity();
1407 return OrderedNameDictionary::cast(table).Capacity();
1411 Isolate* isolate, Handle<HeapObject> table) {
1412 if (table->IsSmallOrderedNameDictionary()) {
1414 Handle<SmallOrderedNameDictionary>::cast(table);
1419 Handle<OrderedNameDictionary>::cast(table);
1424 Isolate* isolate, Handle<HeapObject> table, InternalIndex entry) {
1426 if (table->IsSmallOrderedNameDictionary()) {
1428 Handle<SmallOrderedNameDictionary>::cast(table);
1433 Handle<OrderedNameDictionary>::cast(table);
1441 TableType table = TableType::cast(this->table());
1442 if (!table.IsObsolete()) return;
1446 while (table.IsObsolete()) {
1447 TableType next_table = table.NextTable();
1450 int nod = table.NumberOfDeletedElements();
1457 int removed_index = table.RemovedIndexAt(i);
1464 table = next_table;
1467 set_table(table);
1478 TableType table = TableType::cast(this->table());
1480 int used_capacity = table.UsedCapacity();
1483 table.KeyAt(InternalIndex(index)).IsTheHole(ro_roots)) {