Reland "HashTable::Shrink() handlified and derived template parameter added to HashTable hierarchy."

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 3638 matching lines @@
     ASSERT(UsesSeed);
     return Hash(key);
   }
   static uint32_t HashForObject(Key key, Object* object) { return 0; }
   static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) {
     ASSERT(UsesSeed);
     return HashForObject(key, object);
   }
 };
 
-template<typename Shape, typename Key>
+template<typename Derived, typename Shape, typename Key>
 class HashTable: public FixedArray {
  public:
   // Wrapper methods
   inline uint32_t Hash(Key key) {
     if (Shape::UsesSeed) {
       return Shape::SeededHash(key,
           GetHeap()->HashSeed());
     } else {
       return Shape::Hash(key);
     }
@@ skipping 32 matching lines @@
   void ElementRemoved() {
     SetNumberOfElements(NumberOfElements() - 1);
     SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
   }
   void ElementsRemoved(int n) {
     SetNumberOfElements(NumberOfElements() - n);
     SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
   }
 
   // Returns a new HashTable object. Might return Failure.
+  // TODO(ishell): this will be eventually replaced by New().
   MUST_USE_RESULT static MaybeObject* Allocate(
       Heap* heap,
       int at_least_space_for,
       MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY,
       PretenureFlag pretenure = NOT_TENURED);
 
+  // Returns a new HashTable object.
+  static Handle<Derived> New(
+      Isolate* isolate,
+      int at_least_space_for,
+      MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY,
+      PretenureFlag pretenure = NOT_TENURED);
+
   // Computes the required capacity for a table holding the given
   // number of elements. May be more than HashTable::kMaxCapacity.
   static int ComputeCapacity(int at_least_space_for);
 
   // Returns the key at entry.
   Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
 
   // Tells whether k is a real key.  The hole and undefined are not allowed
   // as keys and can be used to indicate missing or deleted elements.
   bool IsKey(Object* k) {
@@ skipping 89 matching lines @@
   }
 
   // Returns _expected_ if one of entries given by the first _probe_ probes is
   // equal to  _expected_. Otherwise, returns the entry given by the probe
   // number _probe_.
   uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected);
 
   void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
 
   // Rehashes this hash-table into the new table.
-  MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key);
+  void Rehash(Derived* new_table, Key key);
 
   // Attempt to shrink hash table after removal of key.
-  MUST_USE_RESULT MaybeObject* Shrink(Key key);
+  static Handle<Derived> Shrink(Handle<Derived> table, Key key);
 
   // Ensure enough space for n additional elements.
   MUST_USE_RESULT MaybeObject* EnsureCapacity(
       int n,
       Key key,
       PretenureFlag pretenure = NOT_TENURED);
 };
 
 
 // HashTableKey is an abstract superclass for virtual key behavior.
@@ skipping 32 matching lines @@
   static const int kPrefixSize = 0;
   static const int kEntrySize = 1;
 };
 
 class SeqOneByteString;
 
 // StringTable.
 //
 // No special elements in the prefix and the element size is 1
 // because only the string itself (the key) needs to be stored.
-class StringTable: public HashTable<StringTableShape, HashTableKey*> {
+// TODO(ishell): Make StringTable a singleton class and move
+//   Heap::InternalizeStringXX() methods here.
+class StringTable: public HashTable<StringTable,
+                                    StringTableShape,
+                                    HashTableKey*> {
  public:
   // Find string in the string table.  If it is not there yet, it is
   // added.  The return value is the string table which might have
   // been enlarged.  If the return value is not a failure, the string
   // pointer *s is set to the string found.
   MUST_USE_RESULT MaybeObject* LookupString(String* key, Object** s);
   MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s);
 
   // Looks up a string that is equal to the given string and returns
   // true if it is found, assigning the string to the given output
@@ skipping 31 matching lines @@
 
   static const int kPrefixSize = 0;
   static const int kEntrySize = 2;
 };
 
 
 // MapCache.
 //
 // Maps keys that are a fixed array of unique names to a map.
 // Used for canonicalize maps for object literals.
-class MapCache: public HashTable<MapCacheShape, HashTableKey*> {
+class MapCache: public HashTable<MapCache, MapCacheShape, HashTableKey*> {
  public:
   // Find cached value for a name key, otherwise return null.
   Object* Lookup(FixedArray* key);
   MUST_USE_RESULT MaybeObject* Put(FixedArray* key, Map* value);
   static inline MapCache* cast(Object* obj);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(MapCache);
 };
 
 
-template <typename Shape, typename Key>
-class Dictionary: public HashTable<Shape, Key> {
+template <typename Derived, typename Shape, typename Key>
+class Dictionary: public HashTable<Derived, Shape, Key> {
+ protected:
+  typedef HashTable<Derived, Shape, Key> DerivedHashTable;
+
  public:
-  static inline Dictionary<Shape, Key>* cast(Object* obj) {
-    return reinterpret_cast<Dictionary<Shape, Key>*>(obj);
+  static inline Dictionary* cast(Object* obj) {
+    return reinterpret_cast<Dictionary*>(obj);
   }
 
   // Returns the value at entry.
   Object* ValueAt(int entry) {
-    return this->get(HashTable<Shape, Key>::EntryToIndex(entry) + 1);
+    return this->get(DerivedHashTable::EntryToIndex(entry) + 1);
   }
 
   // Set the value for entry.
   void ValueAtPut(int entry, Object* value) {
-    this->set(HashTable<Shape, Key>::EntryToIndex(entry) + 1, value);
+    this->set(DerivedHashTable::EntryToIndex(entry) + 1, value);
   }
 
   // Returns the property details for the property at entry.
   PropertyDetails DetailsAt(int entry) {
     ASSERT(entry >= 0);  // Not found is -1, which is not caught by get().
     return PropertyDetails(
-        Smi::cast(this->get(HashTable<Shape, Key>::EntryToIndex(entry) + 2)));
+        Smi::cast(this->get(DerivedHashTable::EntryToIndex(entry) + 2)));
   }
 
   // Set the details for entry.
   void DetailsAtPut(int entry, PropertyDetails value) {
-    this->set(HashTable<Shape, Key>::EntryToIndex(entry) + 2, value.AsSmi());
+    this->set(DerivedHashTable::EntryToIndex(entry) + 2, value.AsSmi());
   }
 
   // Sorting support
   void CopyValuesTo(FixedArray* elements);
 
   // Delete a property from the dictionary.
   Object* DeleteProperty(int entry, JSObject::DeleteMode mode);
   // TODO(ishell): Temporary wrapper until handlified.
   static Handle<Object> DeleteProperty(
-      Handle<Dictionary<Shape, Key> > dictionary,
+      Handle<Dictionary> dictionary,
       int entry,
       JSObject::DeleteMode mode);
 
   // Attempt to shrink the dictionary after deletion of key.
-  MUST_USE_RESULT MaybeObject* Shrink(Key key);
-  // TODO(ishell): Temporary wrapper until handlified.
-  MUST_USE_RESULT static Handle<FixedArray> Shrink(
-      Handle<Dictionary<Shape, Key> > dictionary,
-      Key key);
+  static inline Handle<Derived> Shrink(Handle<Derived> dictionary, Key key) {
+    return DerivedHashTable::Shrink(dictionary, key);
+  }
 
   // Returns the number of elements in the dictionary filtering out properties
   // with the specified attributes.
   int NumberOfElementsFilterAttributes(PropertyAttributes filter);
 
   // Returns the number of enumerable elements in the dictionary.
   int NumberOfEnumElements();
 
   enum SortMode { UNSORTED, SORTED };
   // Copies keys to preallocated fixed array.
@@ skipping 49 matching lines @@
   MUST_USE_RESULT MaybeObject* AtPut(Key key, Object* value);
 
   // Add entry to dictionary.
   MUST_USE_RESULT MaybeObject* AddEntry(Key key,
                                         Object* value,
                                         PropertyDetails details,
                                         uint32_t hash);
 
   // Generate new enumeration indices to avoid enumeration index overflow.
   MUST_USE_RESULT MaybeObject* GenerateNewEnumerationIndices();
-  static const int kMaxNumberKeyIndex =
-      HashTable<Shape, Key>::kPrefixStartIndex;
+  static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex;
   static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1;
 };
 
 
 class NameDictionaryShape : public BaseShape<Name*> {
  public:
   static inline bool IsMatch(Name* key, Object* other);
   static inline uint32_t Hash(Name* key);
   static inline uint32_t HashForObject(Name* key, Object* object);
   MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap,
                                                       Name* key);
   static const int kPrefixSize = 2;
   static const int kEntrySize = 3;
   static const bool kIsEnumerable = true;
 };
 
 
-class NameDictionary: public Dictionary<NameDictionaryShape, Name*> {
+class NameDictionary: public Dictionary<NameDictionary,
+                                        NameDictionaryShape,
+                                        Name*> {
  public:
   static inline NameDictionary* cast(Object* obj) {
     ASSERT(obj->IsDictionary());
     return reinterpret_cast<NameDictionary*>(obj);
   }
 
   // Copies enumerable keys to preallocated fixed array.
   void CopyEnumKeysTo(FixedArray* storage);
   static void DoGenerateNewEnumerationIndices(
       Handle<NameDictionary> dictionary);
@@ skipping 29 matching lines @@
 class UnseededNumberDictionaryShape : public NumberDictionaryShape {
  public:
   static const int kPrefixSize = 0;
 
   static inline uint32_t Hash(uint32_t key);
   static inline uint32_t HashForObject(uint32_t key, Object* object);
 };
 
 
 class SeededNumberDictionary
-    : public Dictionary<SeededNumberDictionaryShape, uint32_t> {
+    : public Dictionary<SeededNumberDictionary,
+                        SeededNumberDictionaryShape,
+                        uint32_t> {
  public:
   static SeededNumberDictionary* cast(Object* obj) {
     ASSERT(obj->IsDictionary());
     return reinterpret_cast<SeededNumberDictionary*>(obj);
   }
 
   // Type specific at put (default NONE attributes is used when adding).
   MUST_USE_RESULT MaybeObject* AtNumberPut(uint32_t key, Object* value);
   MUST_USE_RESULT static Handle<SeededNumberDictionary> AddNumberEntry(
       Handle<SeededNumberDictionary> dictionary,
@@ skipping 32 matching lines @@
   inline uint32_t max_number_key();
 
   // Bit masks.
   static const int kRequiresSlowElementsMask = 1;
   static const int kRequiresSlowElementsTagSize = 1;
   static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1;
 };
 
 
 class UnseededNumberDictionary
-    : public Dictionary<UnseededNumberDictionaryShape, uint32_t> {
+    : public Dictionary<UnseededNumberDictionary,
+                        UnseededNumberDictionaryShape,
+                        uint32_t> {
  public:
   static UnseededNumberDictionary* cast(Object* obj) {
     ASSERT(obj->IsDictionary());
     return reinterpret_cast<UnseededNumberDictionary*>(obj);
   }
 
   // Type specific at put (default NONE attributes is used when adding).
   MUST_USE_RESULT MaybeObject* AtNumberPut(uint32_t key, Object* value);
   MUST_USE_RESULT MaybeObject* AddNumberEntry(uint32_t key, Object* value);
 
@@ skipping 15 matching lines @@
   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 = 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, Object*> {
+class ObjectHashTable: public HashTable<ObjectHashTable,
+                                        ObjectHashTableShape,
+                                        Object*> {
+  typedef HashTable<ObjectHashTable, ObjectHashTableShape, Object*> HashTable_;
  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,
       PretenureFlag pretenure = NOT_TENURED);
 
   // Attempt to shrink hash table after removal of key.
-  static Handle<ObjectHashTable> Shrink(Handle<ObjectHashTable> table,
-                                        Handle<Object> key);
+  static inline Handle<ObjectHashTable> Shrink(Handle<ObjectHashTable> table,
+                                               Handle<Object> key);
 
   // Looks up the value associated with the given key. The hole value is
   // returned in case the key is not present.
   Object* Lookup(Object* key);
 
   // Adds (or overwrites) the value associated with the given key. Mapping a
   // key to the hole value causes removal of the whole entry.
   static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
                                      Handle<Object> key,
                                      Handle<Object> value);
@@ skipping 177 matching lines @@
   MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap,
                                                       Object* key);
   static const int kPrefixSize = 0;
   static const int kEntrySize = entrysize;
 };
 
 
 // WeakHashTable maps keys that are arbitrary objects to object values.
 // It is used for the global weak hash table that maps objects
 // embedded in optimized code to dependent code lists.
-class WeakHashTable: public HashTable<WeakHashTableShape<2>, Object*> {
+class WeakHashTable: public HashTable<WeakHashTable,
+                                      WeakHashTableShape<2>,
+                                      Object*> {
  public:
   static inline WeakHashTable* cast(Object* obj) {
     ASSERT(obj->IsHashTable());
     return reinterpret_cast<WeakHashTable*>(obj);
   }
 
   // Looks up the value associated with the given key. The hole value is
   // returned in case the key is not present.
   Object* Lookup(Object* key);
 
@@ skipping 3749 matching lines @@
   MUST_USE_RESULT static MaybeObject* AsObject(Heap* heap,
                                                HashTableKey* key) {
     return key->AsObject(heap);
   }
 
   static const int kPrefixSize = 0;
   static const int kEntrySize = 2;
 };
 
 
-class CompilationCacheTable: public HashTable<CompilationCacheShape,
+class CompilationCacheTable: public HashTable<CompilationCacheTable,
+                                              CompilationCacheShape,
                                               HashTableKey*> {
  public:
   // Find cached value for a string key, otherwise return null.
   Handle<Object> Lookup(Handle<String> src, Handle<Context> context);
   Handle<Object> LookupEval(Handle<String> src, Handle<Context> context,
                      StrictMode strict_mode, int scope_position);
   Handle<Object> LookupRegExp(Handle<String> source, JSRegExp::Flags flags);
   static Handle<CompilationCacheTable> Put(
       Handle<CompilationCacheTable> cache, Handle<String> src,
       Handle<Context> context, Handle<Object> value);
@@ skipping 80 matching lines @@
   MUST_USE_RESULT static MaybeObject* AsObject(Heap* heap,
                                                HashTableKey* key) {
     return key->AsObject(heap);
   }
 
   static const int kPrefixSize = 0;
   static const int kEntrySize = 2;
 };
 
 
-class CodeCacheHashTable: public HashTable<CodeCacheHashTableShape,
+class CodeCacheHashTable: public HashTable<CodeCacheHashTable,
+                                           CodeCacheHashTableShape,
                                            HashTableKey*> {
  public:
   Object* Lookup(Name* name, Code::Flags flags);
   MUST_USE_RESULT MaybeObject* Put(Name* name, Code* code);
 
   int GetIndex(Name* name, Code::Flags flags);
   void RemoveByIndex(int index);
 
   static inline CodeCacheHashTable* cast(Object* obj);
 
@@ skipping 29 matching lines @@
 
   static const int kCacheOffset = HeapObject::kHeaderSize;
   static const int kSize = kCacheOffset + kPointerSize;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(PolymorphicCodeCache);
 };
 
 
 class PolymorphicCodeCacheHashTable
-    : public HashTable<CodeCacheHashTableShape, HashTableKey*> {
+    : public HashTable<PolymorphicCodeCacheHashTable,
+                       CodeCacheHashTableShape,
+                       HashTableKey*> {
  public:
   Object* Lookup(MapHandleList* maps, int code_kind);
 
   MUST_USE_RESULT MaybeObject* Put(MapHandleList* maps,
                                    int code_kind,
                                    Code* code);
 
   static inline PolymorphicCodeCacheHashTable* cast(Object* obj);
 
   static const int kInitialSize = 64;
@@ skipping 2659 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_