OrderedHashTable implementation with Set and Map interfaces

src/objects.h

 // Copyright 2012 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 73 matching lines @@
 //           - JSFunctionProxy
 //       - FixedArrayBase
 //         - ByteArray
 //         - FixedArray
 //           - DescriptorArray
 //           - HashTable
 //             - Dictionary
 //             - StringTable
 //             - CompilationCacheTable
 //             - CodeCacheHashTable
 //             - MapCache

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

nit: Can we add the three new classes into the hierarchy here?

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

Done.

 //           - Context
 //           - JSFunctionResultCache
 //           - ScopeInfo
 //           - TransitionArray
 //         - FixedDoubleArray
 //         - ExternalArray
 //           - ExternalUint8ClampedArray
 //           - ExternalInt8Array
 //           - ExternalUint8Array
 //           - ExternalInt16Array
@@ skipping 4137 matching lines @@
   void AddEntry(int entry, Object* key, Object* value);
   void RemoveEntry(int entry);
 
   // Returns the index to the value of an entry.
   static inline int EntryToValueIndex(int entry) {
     return EntryToIndex(entry) + 1;
   }
 };
 
 
+// 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:
   static inline bool IsMatch(Object* key, Object* other);
   static inline uint32_t Hash(Object* key);
   static inline uint32_t HashForObject(Object* key, Object* object);
   MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap,
                                                       Object* key);
   static const int kPrefixSize = 0;
   static const int kEntrySize = entrysize;
@@ skipping 6524 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_