OrderedHashTable implementation with Set and Map interfaces

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 15876 matching lines @@
 }
 
 
 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) {
   set(EntryToIndex(entry), key);
   set(EntryToValueIndex(entry), value);
   ElementAdded();
 }
 
 
+template<int entrysize>
+MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap* heap, int capacity) {

[arv (Not doing code reviews), 2014/04/01 15:22:45]

We should probably have a pretenure flag here too. If the old table was in the
old space we should probably create the new table in the old space as well.

[adamk, 2014/04/03 22:53:38]

Added a PretenureFlag, though I wonder if I need to do something like what
HashTable does and have a minimum size I'll allocate in the old space.

+  // capacity must be a factor of two
+  const int kMinCapacity = 4;
+  capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity));
+  if (capacity > kMaxCapacity) {
+    v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true);
+  }
+  int num_buckets = capacity / kLoadFactor;
+  OrderedHashTable* 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, Smi::FromInt(kNotFound));
+  }
+  table->SetNumberOfBuckets(num_buckets);
+  table->SetNumberOfElements(0);
+  table->SetNumberOfDeletedElements(0);
+  return table;
+}
+
+
+template<int entrysize>
+MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() {

[Michael Starzinger, 2014/04/02 12:09:37]

Is there a particular reason why this implementation is unhandlified and the
sub-classes contain handle-wrappers? If not, I would vote for making this
implementation be handle-based. IIUC, this would alleviate the need to even
declare them explicitly.

Admittedly, doing that straight-forward would make the return type be
Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
(courtesy of Andreas) would be to add a second template parameter (in addition
to "entrysize") to declare to concrete type.

[Michael Starzinger, 2014/04/02 12:12:18]

... [to declare them explicitly] in the concrete subclasses again.
 

[rossberg, 2014/04/02 13:09:12]

More concretely, something like

template<class Derived, int entrysize> class OrderHashTable {
  // ..., e.g.:
  Handle<Derived> Rehash(Handle<Derived>);
};

class OrderedHashSet: OrderedHashTable<OrderedHashSet, 1> { ... };

should work (perhaps with some extra tweaks).

[adamk, 2014/04/02 22:01:10]

Done and done. This code was so-structured because it was based on
ObjectHashTable.

Note that in the current patch Allocate() is also handlified, but this seems to
go against the norms of objects.cc...let me know what's preferred here.

[Michael Starzinger, 2014/04/04 09:38:12]

I definitely prefer handlified as you did in your recent patch set.

+  int nof = NumberOfElements();
+  int nod = NumberOfDeletedElements();
+  int capacity = Capacity();
+  if ((nof + nod) < capacity) return this;
+  // Don't need to grow if we can simply clear out deleted entries instead.
+  // Note that we can't compact in place, though, so we always allocate
+  // a new table.
+  int new_capacity = (nod < (capacity >> 1)) ? capacity << 1 : capacity;
+  OrderedHashTable* 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* OrderedHashTable<entrysize>::Shrink() {

[Michael Starzinger, 2014/04/02 12:09:37]

Likewise.

+  int nof = NumberOfElements();
+  int capacity = Capacity();
+  if (nof > (capacity >> 2)) return this;
+  int new_capacity = capacity / 2;
+  OrderedHashTable* 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* OrderedHashTable<entrysize>::Rehash(OrderedHashTable* new_table) {

[Michael Starzinger, 2014/04/02 12:09:37]

AFAICT, addressing the above two comments would also allow us to implement this
one handle-based.

+  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));
+    int new_index = new_table->EntryToIndex(new_entry);
+    int old_index = EntryToIndex(old_entry);
+    for (int i = 0; i < entrysize; ++i) {
+      Object* value = get(old_index + i);
+      new_table->set(new_index + i, value);
+    }
+    new_table->set(new_index + kChainOffset, chain_entry);
+    ++new_entry;
+  }
+  new_table->SetNumberOfElements(nof);
+  return new_table;
+}
+
+
+template<int entrysize>
+int OrderedHashTable<entrysize>::FindEntry(Object* key) {
+  ASSERT(!key->IsTheHole());
+  Object* hash = key->GetHash();
+  if (hash->IsUndefined()) return kNotFound;
+  for (int entry = HashToEntry(Smi::cast(hash)->value());
+       entry != kNotFound;
+       entry = ChainAt(entry)) {
+    Object* candidate = KeyAt(entry);
+    if (candidate->SameValue(key))
+      return entry;
+  }
+  return kNotFound;
+}
+
+
+template<int entrysize>
+int OrderedHashTable<entrysize>::AddEntry(int hash) {
+  int entry = NumberOfElements() + NumberOfDeletedElements();
+  int bucket = HashToBucket(hash);
+  int index = EntryToIndex(entry);
+  Object* chain_entry = get(kHashTableStartIndex + bucket);
+  set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+  set(index + kChainOffset, chain_entry);
+  SetNumberOfElements(NumberOfElements() + 1);
+  return index;
+}
+
+
+template<int entrysize>
+void OrderedHashTable<entrysize>::RemoveEntry(int entry) {
+  int index = EntryToIndex(entry);
+  for (int i = 0; i < entrysize; ++i) {
+    set_the_hole(index + i);
+  }
+  SetNumberOfElements(NumberOfElements() - 1);
+  SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
+}
+
+
+template class OrderedHashTable<1>;
+template class OrderedHashTable<2>;
+
+
+bool OrderedHashSet::Contains(Object* key) {
+  return FindEntry(key) != kNotFound;
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::EnsureGrowable(

[Michael Starzinger, 2014/04/02 12:09:37]

Obsolete if above comments are addressed, I think.

+    Handle<OrderedHashSet> table) {
+  Handle<OrderedHashTable<1> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->EnsureGrowable(),
+                     OrderedHashSet);
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::Shrink(Handle<OrderedHashSet> table) {

[Michael Starzinger, 2014/04/02 12:09:37]

Likewise.

+  Handle<OrderedHashTable<1> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->Shrink(),
+                     OrderedHashSet);
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table,
+                                           Handle<Object> key) {
+  if (table->FindEntry(*key) != kNotFound) return table;
+
+  table = EnsureGrowable(table);
+
+  Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+  int index = table->AddEntry(Smi::cast(*hash)->value());
+  table->set(index, *key);
+  return table;
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table,
+                                              Handle<Object> key) {
+  int entry = table->FindEntry(*key);
+  if (entry == kNotFound) return table;
+  table->RemoveEntry(entry);
+  // TODO(adamk): Don't shrink if we're being iterated over
+  return Shrink(table);
+}
+
+
+Object* OrderedHashMap::Lookup(Object* key) {
+  int entry = FindEntry(key);
+  if (entry == kNotFound) return GetHeap()->the_hole_value();
+  return ValueAt(entry);
+}
+
+
+Handle<OrderedHashMap> OrderedHashMap::EnsureGrowable(

[Michael Starzinger, 2014/04/02 12:09:37]

Likewise.

+    Handle<OrderedHashMap> table) {
+  Handle<OrderedHashTable<2> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->EnsureGrowable(),
+                     OrderedHashMap);
+}
+
+
+Handle<OrderedHashMap> OrderedHashMap::Shrink(Handle<OrderedHashMap> table) {

[Michael Starzinger, 2014/04/02 12:09:37]

Likewise.

+  Handle<OrderedHashTable<2> > table_base = table;
+  CALL_HEAP_FUNCTION(table_base->GetIsolate(),
+                     table_base->Shrink(),
+                     OrderedHashMap);
+}
+
+
+Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
+                                           Handle<Object> key,
+                                           Handle<Object> value) {
+  int entry = table->FindEntry(*key);
+
+  if (value->IsTheHole()) {
+    if (entry == kNotFound) return table;
+    table->RemoveEntry(entry);
+    // TODO(adamk): Only shrink if not iterating
+    return Shrink(table);
+  }
+
+  if (entry != kNotFound) {
+    table->set(table->EntryToIndex(entry) + kValueOffset, *value);
+    return table;
+  }
+
+  table = EnsureGrowable(table);
+
+  Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+  int index = table->AddEntry(Smi::cast(*hash)->value());
+  table->set(index, *key);
+  table->set(index + kValueOffset, *value);
+  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