OrderedHashTable implementation with Set and Map interfaces

src/objects.h

Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index c4d3f251c318173946ab614ff661c3da679eb6fa..febf67a3f5a0cee3a8f064852f9d0448ff163505 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -4249,6 +4249,163 @@ class ObjectHashTable: public HashTable<ObjectHashTableShape<2>, Object*> {
 };
 
 
+// OrderedHashTable is a HashTable with Object keys that preserves
+// insertion order. There are Map and Set interfaces (OrderedHashMap
+// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
+//
+// Only Object* keys are supported, with Object::SameValue() used as the
+// equality operator and Object::GetHash() for the hash function.
+//
+// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
+// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
+// Originally attributed to Tyler Close.
+//
+// Memory layout:
+//   [0]: bucket count
+//   [1]: element count
+//   [2]: deleted element count
+//   [3]: "hash table", an array of length NumberOfBuckets() entry numbers

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

nit: Can we somehow visually note that the "hash table" is actually at [3..n],
because currently it looks like there is an indirection at [3] that points to
the "hash table".

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

Explained more. This could probably use some more explanation, though, I'll see
if I can figure a better way to lay it out.

+//        followed by "data table", an array of length NumberOfBuckets() *
+//        kLoadFactor entries
+template<int entrysize>
+class OrderedHashTable: public FixedArray {
+ public:
+  // Returns an OrderedHashTable with a capacity of at least |capacity|,
+  // or returns a Failure if a GC occurs.
+  MUST_USE_RESULT static MaybeObject* Allocate(Heap* heap, int capacity);
+
+  // Returns an OrderedHashTable (possibly |this|) with enough space
+  // to add at least one new element, or returns a Failure if a GC occurs.
+  MUST_USE_RESULT MaybeObject* EnsureGrowable();
+
+  static OrderedHashTable* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<OrderedHashTable*>(obj);
+  }
+
+  // Returns kNotFound if the key isn't present.
+  int FindEntry(Object* key);
+
+  int NumberOfElements() {
+    return Smi::cast(get(kNumberOfElementsIndex))->value();
+  }
+
+  int NumberOfDeletedElements() {
+    return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
+  }
+
+  int NumberOfBuckets() {
+    return Smi::cast(get(kNumberOfBucketsIndex))->value();
+  }
+
+  // Returns the index into the data table where the new entry
+  // should be placed. The table is assumed to have enough space
+  // for a new entry.
+  int AddEntry(int hash);
+
+  // Removes the entry, and puts the_hole in entrysize pointers
+  // (leaving the hash table chain intact).
+  void RemoveEntry(int entry);
+
+  // Returns an index into |this| for the given entry.
+  int EntryToIndex(int entry) {
+    return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
+  }
+
+  MUST_USE_RESULT MaybeObject* Shrink();
+  MUST_USE_RESULT MaybeObject* Rehash(OrderedHashTable* new_table);
+
+  static const int kNotFound = -1;
+
+ private:
+  void SetNumberOfBuckets(int num) {
+    set(kNumberOfBucketsIndex, Smi::FromInt(num));
+  }
+
+  void SetNumberOfElements(int num) {
+    set(kNumberOfElementsIndex, Smi::FromInt(num));
+  }
+
+  void SetNumberOfDeletedElements(int num) {
+    set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
+  }
+
+  int Capacity() {
+    return NumberOfBuckets() * kLoadFactor;
+  }
+
+  Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
+
+  // Returns the next entry for the given entry.
+  int ChainAt(int entry) {
+    return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value();
+  }
+
+  int HashToBucket(int hash) {
+    return hash & (NumberOfBuckets() - 1);
+  }
+
+  int HashToEntry(int hash) {
+    int bucket = HashToBucket(hash);
+    return Smi::cast(get(kHashTableStartIndex + bucket))->value();
+  }
+
+  static const int kNumberOfBucketsIndex = 0;
+  static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1;
+  static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
+  static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1;
+
+  static const int kEntrySize = entrysize + 1;
+  static const int kChainOffset = entrysize;
+
+  static const int kLoadFactor = 2;
+  static const int kMaxCapacity =
+      (FixedArray::kMaxLength - kHashTableStartIndex)
+      / (1 + (kEntrySize * kLoadFactor));
+};
+
+
+class OrderedHashSet: public OrderedHashTable<1> {
+ public:
+  static OrderedHashSet* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<OrderedHashSet*>(obj);
+  }
+
+  bool Contains(Object* key);
+  static Handle<OrderedHashSet> Add(
+      Handle<OrderedHashSet> table, Handle<Object> key);
+  static Handle<OrderedHashSet> Remove(
+      Handle<OrderedHashSet> table, Handle<Object> key);
+  static Handle<OrderedHashSet> EnsureGrowable(Handle<OrderedHashSet> table);
+  static Handle<OrderedHashSet> Shrink(Handle<OrderedHashSet> table);
+};
+
+
+class OrderedHashMap: public OrderedHashTable<2> {
+ public:
+  static OrderedHashMap* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<OrderedHashMap*>(obj);
+  }
+
+  Object* Lookup(Object* key);
+  static Handle<OrderedHashMap> Put(
+      Handle<OrderedHashMap> table,
+      Handle<Object> key,
+      Handle<Object> value);
+  static Handle<OrderedHashMap> EnsureGrowable(Handle<OrderedHashMap> table);
+  static Handle<OrderedHashMap> Shrink(Handle<OrderedHashMap> table);
+
+ private:
+  Object* ValueAt(int entry) {
+    return get(EntryToIndex(entry) + kValueOffset);
+  }
+
+  static const int kValueOffset = 1;
+};
+
+
 template <int entrysize>
 class WeakHashTableShape : public BaseShape<Object*> {
  public: