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();
 }
 
 
+// TODO(adamk): Figure out where to put this, maybe we need some traits
+//const double CloseTable<entrysize>::kLoadFactor = 8.0 / 3.0;
+
+
+template<int entrysize>
+MaybeObject* CloseTable<entrysize>::Allocate(Heap* heap, int capacity) {
+  // capacity must be a factor of two
+  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->undefined_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();
+  // TODO(adamk): Allow possibility to compact instead of always
+  // increasing capacity if num deleted is big.
+  if ((nof + nod + num_to_add) <= Capacity()) 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;
+  }
+  int new_buckets = new_table->NumberOfBuckets();
+  for (int entry = 0; entry < (nof + nod); ++entry) {
+    Object* key = KeyAt(entry);
+    if (key->IsTheHole()) continue;
+    Object* hash = key->GetHash();
+    int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
+    Object* old_entry = new_table->get(kHashTableStartIndex + bucket);
+    new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+    int index = new_table->EntryToIndex(entry);
+    new_table->set(index, key);

[arv (Not doing code reviews), 2014/03/27 22:39:02]

For map, we probably need to store the value at index+1

The loop should probably be entry += entrysize and 

then an inner loop from entry to entry+entrysize to copy over key, values and
magical third item of a pair.

[adamk, 2014/03/27 22:43:13]

Oh, you're looking at an old one. This is now an inner for loop.

+    new_table->set(index + kChainOffset, old_entry);
+  }
+  new_table->SetNumberOfElements(nof);
+  return new_table;
+}
+
+
+template<int entrysize>
+int CloseTable<entrysize>::Lookup(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;

[arv (Not doing code reviews), 2014/03/27 22:39:02]

Maybe we should use -1 instead of undefined? Might be faster

[adamk, 2014/03/27 22:43:13]

Hmm, and I guess I can use -1 even in the chain...sounds like a reasonable plan.
I still need to add code to fill up the data table with the_hole_value, though,
since I'm using that as a sentinel now in my Rehash loop.

+  int entry = Smi::cast(bucket_entry)->value();
+  while (true) {
+    Object* candidate = KeyAt(entry);
+    if (candidate == key)
+      return entry;
+    Object* chain = ChainAt(entry);
+    if (!chain->IsSmi())
+      break;
+    entry = Smi::cast(chain)->value();
+  }
+  return kNotFound;
+}
+
+
+bool CloseTableSet::Contains(Object* key) {
+  return Lookup(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::Add(Handle<CloseTableSet> table,
+                                         Handle<Object> key) {
+  if (table->Lookup(*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* old_entry = table->get(kHashTableStartIndex + bucket);
+  table->set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+  table->set(index, *key);
+  table->set(index + kChainOffset, old_entry);
+  table->ElementAdded();
+  return table;
+}
+
+
+Handle<CloseTableSet> CloseTableSet::Remove(Handle<CloseTableSet> table,
+                                            Handle<Object> key) {
+  int entry = table->Lookup(*key);
+  if (entry == kNotFound) return table;
+
+  table->set_the_hole(table->EntryToIndex(entry));
+  table->ElementRemoved();
+
+  /* shrink if needed & not iterating */
+  return table;
+}
+
+
+template class CloseTable<1>;
+
+
 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