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

src/close-table.h

+#ifndef CLOSE_TABLE_H
+#define CLOSE_TABLE_H
+
+#include "objects.h"
+
+namespace v8 {
+namespace internal {
+
+// TODO(adamk): Merge this into objects.h once development is done
+
+// Based on Tyler Close's "Deterministic Hash Table" as described
+// by Jason Orendorff at
+// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
+//
+// Memory layout:
+//   [0]: bucket count
+//   [1]: element count
+//   [2]: deleted element count
+//   [3]: "hash table", an array of length NumberOfBuckets() entry numbers
+//        followed by "data table", an array of length NumberOfBuckets() *
+//        kLoadFactor entries
+template<int entrysize>
+class CloseTable: public FixedArray {
+ public:
+  MUST_USE_RESULT static MaybeObject* Allocate(Heap* heap, int capacity);
+
+  MUST_USE_RESULT MaybeObject* EnsureCapacity(int num_to_add);
+
+  static CloseTable* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<CloseTable*>(obj);
+  }
+
+  int FindEntry(Object* key);
+
+  Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
+  Object* ChainAt(int entry) { return get(EntryToIndex(entry) + kChainOffset); }
+
+  int NumberOfElements() {
+    return Smi::cast(get(kNumberOfElementsIndex))->value();
+  }
+  void SetNumberOfElements(int num) {
+    set(kNumberOfElementsIndex, Smi::FromInt(num));
+  }
+  int NumberOfDeletedElements() {
+    return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
+  }
+  void SetNumberOfDeletedElements(int num) {
+    set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
+  }
+
+  int NumberOfBuckets() {
+    return Smi::cast(get(kNumberOfBucketsIndex))->value();
+  }
+
+  void SetNumberOfBuckets(int num) {
+    set(kNumberOfBucketsIndex, Smi::FromInt(num));
+  }
+
+  void ElementAdded() {
+    SetNumberOfElements(NumberOfElements() + 1);
+  }
+
+  void ElementRemoved() {
+    SetNumberOfElements(NumberOfElements() - 1);
+    SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
+  }
+
+  int Capacity() {
+    return NumberOfBuckets() * kLoadFactor;
+  }
+
+  int DataTableStartIndex() {
+    return kHashTableStartIndex + NumberOfBuckets();
+  }
+
+  int EntryToIndex(int entry) {
+    return DataTableStartIndex() + (entry * kEntrySize);
+  }
+
+  MUST_USE_RESULT MaybeObject* Shrink();
+  MUST_USE_RESULT MaybeObject* Rehash(CloseTable* new_table);
+
+  static const int kNotFound = -1;
+
+ private:
+  friend class CloseTableSet;
+  friend class CloseTableMap;
+
+  // Should be 8.0 / 3.0 but making it a double is complicated
+  static const int kLoadFactor = 2;
+
+  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;
+};
+
+
+class CloseTableSet: public CloseTable<1> {
+ public:
+  static CloseTableSet* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<CloseTableSet*>(obj);
+  }
+
+  bool Contains(Object* key);
+  static Handle<CloseTableSet> Add(Handle<CloseTableSet> table, Handle<Object> key);
+  static Handle<CloseTableSet> Remove(Handle<CloseTableSet> table, Handle<Object> key);
+  static Handle<CloseTableSet> EnsureCapacity(Handle<CloseTableSet> table, int num_to_add);
+  static Handle<CloseTableSet> Shrink(Handle<CloseTableSet>);
+};
+
+
+class CloseTableMap: public CloseTable<2> {
+ public:
+  static CloseTableMap* cast(Object* obj) {
+    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
+    return reinterpret_cast<CloseTableMap*>(obj);
+  }
+
+  Object* Lookup(Object* key);
+  static Handle<CloseTableMap> Put(Handle<CloseTableMap> table, Handle<Object> key, Handle<Object> value);
+  static Handle<CloseTableMap> EnsureCapacity(Handle<CloseTableMap> table, int num_to_add);
+  static Handle<CloseTableMap> Shrink(Handle<CloseTableMap>);
+
+ private:
+  Object* ValueAt(int entry) {
+    return get(EntryToIndex(entry) + kValueOffset);
+  }
+
+  static const int kValueOffset = 1;
+};
+
+
+} // namespace internal
+} // namespace v8
+
+#endif //CLOSE_TABLE_H