Work in progress: ES6 Maps and Sets with deterministic iteration support

src/objects.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 34 matching lines @@
 #include "isolate-inl.h"
 #include "log.h"
 #include "objects-inl.h"
 #include "objects-visiting-inl.h"
 #include "macro-assembler.h"
 #include "mark-compact.h"
 #include "safepoint-table.h"
 #include "string-stream.h"
 #include "utils.h"
 
+#include "close-table.h"
+
 #ifdef ENABLE_DISASSEMBLER
 #include "disasm.h"
 #include "disassembler.h"
 #endif
 
 namespace v8 {
 namespace internal {
 
 
 MUST_USE_RESULT static MaybeObject* CreateJSValue(JSFunction* constructor,
@@ skipping 15822 matching lines @@
 }
 
 
 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) {
   set(EntryToIndex(entry), key);
   set(EntryToValueIndex(entry), value);
   ElementAdded();
 }
 
 
+template<int entrysize>
+MaybeObject* CloseTable<entrysize>::Allocate(Heap* heap, int capacity) {
+  // capacity must be a factor of two
+  const int kMinCapacity = 4;
+  capacity = Max(kMinCapacity, capacity);

[arv (Not doing code reviews), 2014/03/29 02:26:07]

Can be an assert instead? I don't think this needs to be a runtime check.

[adamk, 2014/03/31 15:36:39]

Something like that, yeah. I'm sort of waiting till the callers shake out to fix
the API of Allocate (and Factory::New*)

+  int num_buckets = capacity / kLoadFactor;
+  ASSERT(num_buckets * kLoadFactor == capacity);
+  CloseTable* table;
+  { MaybeObject* maybe_obj =
+        heap->AllocateFixedArray(
+            kHashTableStartIndex + num_buckets
+            + (capacity * kEntrySize));
+    if (!maybe_obj->To(&table)) return maybe_obj;
+  }
+  for (int i = 0; i < num_buckets; ++i) {
+    table->set(kHashTableStartIndex + i, heap->the_hole_value());
+  }
+  table->SetNumberOfBuckets(num_buckets);
+  table->SetNumberOfElements(0);
+  table->SetNumberOfDeletedElements(0);
+  return table;
+}
+
+
+template<int entrysize>
+MaybeObject* CloseTable<entrysize>::EnsureCapacity(int num_to_add) {
+  int nof = NumberOfElements();
+  int nod = NumberOfDeletedElements();
+  int capacity = Capacity();
+  if ((nof + nod + num_to_add) <= capacity) return this;
+  // Don't need to grow if we can simply clear out deleted entries instead.

[arv (Not doing code reviews), 2014/03/29 02:26:07]

This comment does not look accurate. We still call Allocate.

We should probably add a Compact function that does the in place cleanup.

[adamk, 2014/03/31 15:36:39]

The comment is confusing, I admit. It's trying to explain the ternary operator
on the next line, which doubles capacity unless keeping the same capacity (but a
new backing store) would work, due to deletions.

I don't believe this data structure supports in-place rehashing, since
collapsing chains can break the ordering. But perhaps you have something clever
in mind?

+  int new_capacity = (nod < (capacity >> 1)) ? capacity << 1 : capacity;
+  CloseTable* new_table;
+  { MaybeObject* maybe_obj = Allocate(GetHeap(), new_capacity);
+    if (!maybe_obj->To(&new_table)) return maybe_obj;
+  }
+  return Rehash(new_table);
+}
+
+
+template<int entrysize>
+MaybeObject* CloseTable<entrysize>::Shrink() {
+  int nof = NumberOfElements();
+  int capacity = Capacity();
+  if (nof > (capacity >> 2)) return this;
+  int new_capacity = capacity / 2;
+  CloseTable* new_table;
+  { MaybeObject* maybe_obj = Allocate(GetHeap(), new_capacity);
+    if (!maybe_obj->To(&new_table)) return maybe_obj;
+  }
+  return Rehash(new_table);
+}
+
+
+template<int entrysize>
+MaybeObject* CloseTable<entrysize>::Rehash(CloseTable* new_table) {
+  int nof = NumberOfElements();
+  int nod = NumberOfDeletedElements();
+  int new_buckets = new_table->NumberOfBuckets();
+  int new_entry = 0;
+  for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
+    Object* key = KeyAt(old_entry);
+    if (key->IsTheHole()) continue;
+    Object* hash = key->GetHash();
+    int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
+    Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
+    new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
+    for (int i = 0; i < kEntrySize; ++i) {
+      Object* value = get(EntryToIndex(old_entry) + i);
+      new_table->set(new_table->EntryToIndex(new_entry) + i, value);
+    }
+    new_table->set(new_table->EntryToIndex(new_entry) + kChainOffset, chain_entry);
+    ++new_entry;
+  }
+  new_table->SetNumberOfElements(nof);
+  return new_table;
+}
+
+
+template<int entrysize>
+int CloseTable<entrysize>::FindEntry(Object* key) {
+  ASSERT(!key->IsTheHole());
+  Object* hash = key->GetHash();
+  if (hash->IsUndefined()) return kNotFound;
+  int bucket = Smi::cast(hash)->value() & (NumberOfBuckets() - 1);
+  Object* bucket_entry = get(kHashTableStartIndex + bucket);
+  if (!bucket_entry->IsSmi()) return kNotFound;
+  int entry = Smi::cast(bucket_entry)->value();
+  while (true) {
+    Object* candidate = KeyAt(entry);
+    if (candidate->SameValue(key))
+      return entry;
+    Object* chain = ChainAt(entry);
+    if (!chain->IsSmi())
+      break;
+    entry = Smi::cast(chain)->value();
+  }
+  return kNotFound;
+}
+
+
+template class CloseTable<1>;
+template class CloseTable<2>;
+
+
+bool CloseTableSet::Contains(Object* key) {
+  return FindEntry(key) != kNotFound;
+}
+
+
+Handle<CloseTableSet> CloseTableSet::EnsureCapacity(
+    Handle<CloseTableSet> table,
+    int num_to_add) {
+  Handle<CloseTable<1> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->EnsureCapacity(num_to_add),
+                     CloseTableSet);
+}
+
+
+Handle<CloseTableSet> CloseTableSet::Shrink(Handle<CloseTableSet> table) {
+  Handle<CloseTable<1> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->Shrink(),
+                     CloseTableSet);
+}
+
+
+Handle<CloseTableSet> CloseTableSet::Add(Handle<CloseTableSet> table,
+                                         Handle<Object> key) {
+  if (table->FindEntry(*key) != kNotFound) return table;
+
+  table = EnsureCapacity(table, 1);
+
+  Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+  int bucket = Smi::cast(*hash)->value() & (table->NumberOfBuckets() - 1);
+  int nof = table->NumberOfElements();
+  int entry = nof + table->NumberOfDeletedElements();
+  int index = table->EntryToIndex(entry);
+  Object* chain_entry = table->get(kHashTableStartIndex + bucket);
+  table->set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+  table->set(index, *key);
+  table->set(index + kChainOffset, chain_entry);
+  table->ElementAdded();
+  return table;
+}
+
+
+Handle<CloseTableSet> CloseTableSet::Remove(Handle<CloseTableSet> table,
+                                            Handle<Object> key) {
+  int entry = table->FindEntry(*key);
+  if (entry == kNotFound) return table;
+
+  table->set_the_hole(table->EntryToIndex(entry));
+  table->ElementRemoved();
+
+  // TODO(adamk): Don't shrink if we're being iterated over
+  table = Shrink(table);
+
+  return table;
+}
+
+
+Object* CloseTableMap::Lookup(Object* key) {
+  int entry = FindEntry(key);
+  if (entry == kNotFound) return GetHeap()->the_hole_value();
+  return ValueAt(entry);
+}
+
+
+Handle<CloseTableMap> CloseTableMap::EnsureCapacity(
+    Handle<CloseTableMap> table,
+    int num_to_add) {
+  Handle<CloseTable<2> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->EnsureCapacity(num_to_add),
+                     CloseTableMap);
+}
+
+
+Handle<CloseTableMap> CloseTableMap::Shrink(Handle<CloseTableMap> table) {
+  Handle<CloseTable<2> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->Shrink(),
+                     CloseTableMap);
+}
+
+
+Handle<CloseTableMap> CloseTableMap::Put(Handle<CloseTableMap> table,
+                                         Handle<Object> key,
+                                         Handle<Object> value) {
+  int entry = table->FindEntry(*key);
+
+  if (value->IsTheHole()) {
+    if (entry == kNotFound) return table;
+    int index = table->EntryToIndex(entry);
+    table->set_the_hole(index);
+    table->set_the_hole(index + kValueOffset);
+    table->ElementRemoved();
+
+    // TODO(adamk): Only shrink if not iterating
+    table = Shrink(table);
+    return table;
+  }
+
+  if (entry != kNotFound) {
+    table->set(table->EntryToIndex(entry) + kValueOffset, *value);
+    return table;
+  }
+
+  table = EnsureCapacity(table, 1);
+
+  Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+  int bucket = Smi::cast(*hash)->value() & (table->NumberOfBuckets() - 1);
+  int nof = table->NumberOfElements();
+  entry = nof + table->NumberOfDeletedElements();
+  int index = table->EntryToIndex(entry);
+  Object* chain_entry = table->get(kHashTableStartIndex + bucket);
+  table->set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+  table->set(index, *key);
+  table->set(index + kValueOffset, *value);
+  table->set(index + kChainOffset, chain_entry);
+  table->ElementAdded();
+  return table;
+}
+
+
 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
     DeclaredAccessorDescriptor* descriptor)
     : array_(descriptor->serialized_data()->GetDataStartAddress()),
       length_(descriptor->serialized_data()->length()),
       offset_(0) {
 }
 
 
 const DeclaredAccessorDescriptorData*
   DeclaredAccessorDescriptorIterator::Next() {
@@ skipping 512 matching lines @@
 #define ERROR_MESSAGES_TEXTS(C, T) T,
   static const char* error_messages_[] = {
       ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS)
   };
 #undef ERROR_MESSAGES_TEXTS
   return error_messages_[reason];
 }
 
 
 } }  // namespace v8::internal