Use OrderedHashTables as the backing store of JSSet and JSMap

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 1058 matching lines @@
   V(Primitive)                                 \
   V(GlobalObject)                              \
   V(JSGlobalObject)                            \
   V(JSBuiltinsObject)                          \
   V(JSGlobalProxy)                             \
   V(UndetectableObject)                        \
   V(AccessCheckNeeded)                         \
   V(Cell)                                      \
   V(PropertyCell)                              \
   V(ObjectHashTable)                           \
-  V(WeakHashTable)
+  V(WeakHashTable)                             \
+  V(OrderedHashTable)                          \

[Michael Starzinger, 2014/04/07 12:37:31]

Since the OrderedHashTable is just the abstract super-class of the
OrderedHashSet and OrderedHashMap, we really shouldn't have three instance types
here.

I am fine with sharing one map for both OrderedHashSet and OrderedHashMap as the
CL does right now. But then we should only add one new instance type for now and
drop the unused ones.

[adamk, 2014/04/07 23:50:02]

Okay, I switched back (only downside was that I have to keep my own custom
cast() methods).

+  V(OrderedHashSet)                            \
+  V(OrderedHashMap)
 
 
 #define ERROR_MESSAGES_LIST(V) \
   V(kNoReason, "no reason")                                                   \
                                                                               \
   V(k32BitValueInRegisterIsNotZeroExtended,                                   \
     "32 bit value in register is not zero-extended")                          \
   V(kAlignmentMarkerExpected, "Alignment marker expected")                    \
   V(kAllocationIsNotDoubleAligned, "Allocation is not double aligned")        \
   V(kAPICallReturnedInvalidObject, "API call returned invalid object")        \
@@ skipping 2654 matching lines @@
       (FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize;
 
   // Find entry for key otherwise return kNotFound.
   inline int FindEntry(Key key);
   int FindEntry(Isolate* isolate, Key key);
 
   // Rehashes the table in-place.
   void Rehash(Key key);
 
  protected:
-  friend class ObjectHashSet;
   friend class ObjectHashTable;
 
   // Find the entry at which to insert element with the given key that
   // has the given hash value.
   uint32_t FindInsertionEntry(uint32_t hash);
 
   // Returns the index for an entry (of the key)
   static inline int EntryToIndex(int entry) {
     return (entry * kEntrySize) + kElementsStartIndex;
   }
@@ skipping 410 matching lines @@
   // Return the updated dictionary.
   MUST_USE_RESULT static Handle<UnseededNumberDictionary> Set(
       Handle<UnseededNumberDictionary> dictionary,
       uint32_t index,
       Handle<Object> value);
 
   MUST_USE_RESULT MaybeObject* Set(uint32_t key, Object* value);
 };
 
 
-template <int entrysize>
 class ObjectHashTableShape : 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;
-};
-
-
-// ObjectHashSet holds keys that are arbitrary objects by using the identity
-// hash of the key for hashing purposes.
-class ObjectHashSet: public HashTable<ObjectHashTableShape<1>, Object*> {
- public:
-  static inline ObjectHashSet* cast(Object* obj) {
-    ASSERT(obj->IsHashTable());
-    return reinterpret_cast<ObjectHashSet*>(obj);
-  }
-
-  // Looks up whether the given key is part of this hash set.
-  bool Contains(Object* key);
-
-  static Handle<ObjectHashSet> EnsureCapacity(
-      Handle<ObjectHashSet> table,
-      int n,
-      Handle<Object> key,
-      PretenureFlag pretenure = NOT_TENURED);
-
-  // Attempt to shrink hash table after removal of key.
-  static Handle<ObjectHashSet> Shrink(Handle<ObjectHashSet> table,
-                                      Handle<Object> key);
-
-  // Adds the given key to this hash set.
-  static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> table,
-                                   Handle<Object> key);
-
-  // Removes the given key from this hash set.
-  static Handle<ObjectHashSet> Remove(Handle<ObjectHashSet> table,
-                                      Handle<Object> key);
+  static const int kEntrySize = 2;
 };
 
 
 // ObjectHashTable maps keys that are arbitrary objects to object values by
 // using the identity hash of the key for hashing purposes.
-class ObjectHashTable: public HashTable<ObjectHashTableShape<2>, Object*> {
+class ObjectHashTable: public HashTable<ObjectHashTableShape, Object*> {
  public:
   static inline ObjectHashTable* cast(Object* obj) {
     ASSERT(obj->IsHashTable());
     return reinterpret_cast<ObjectHashTable*>(obj);
   }
 
   static Handle<ObjectHashTable> EnsureCapacity(
       Handle<ObjectHashTable> table,
       int n,
       Handle<Object> key,
@@ skipping 51 matching lines @@
 //                            data table indicating the next entry in this hash
 //                            bucket.
 template<class Derived, int entrysize>
 class OrderedHashTable: public FixedArray {
  public:
   // Returns an OrderedHashTable with a capacity of at least |capacity|.
   static Handle<Derived> Allocate(
       Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED);
 
   // Returns an OrderedHashTable (possibly |table|) with enough space
-  // to add at least one new element, or returns a Failure if a GC occurs.
+  // to add at least one new element.
   static Handle<Derived> EnsureGrowable(Handle<Derived> table);
 
   // Returns an OrderedHashTable (possibly |table|) that's shrunken
   // if possible.
   static Handle<Derived> Shrink(Handle<Derived> table);
 
   // Returns kNotFound if the key isn't present.
   int FindEntry(Object* key);
 
   int NumberOfElements() {
@@ skipping 69 matching lines @@
 
   static const int kLoadFactor = 2;
   static const int kMaxCapacity =
       (FixedArray::kMaxLength - kHashTableStartIndex)
       / (1 + (kEntrySize * kLoadFactor));
 };
 
 
 class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
  public:
-  static OrderedHashSet* cast(Object* obj) {
-    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
-    return reinterpret_cast<OrderedHashSet*>(obj);
-  }
+  static inline OrderedHashSet* cast(Object* 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);
 };
 
 
 class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> {
  public:
-  static OrderedHashMap* cast(Object* obj) {
-    ASSERT(obj->IsFixedArray());  // TODO(adamk): Make a map for this
-    return reinterpret_cast<OrderedHashMap*>(obj);
-  }
+  static inline OrderedHashMap* cast(Object* obj);
 
   Object* Lookup(Object* key);
   static Handle<OrderedHashMap> Put(
       Handle<OrderedHashMap> table,
       Handle<Object> key,
       Handle<Object> value);
 
  private:
   Object* ValueAt(int entry) {
     return get(EntryToIndex(entry) + kValueOffset);
@@ skipping 6563 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_