Added rehashing of hash tables when there are too many deleted elements.

src/objects.h

 // Copyright 2006-2009 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 1868 matching lines @@
 // information by subclasses.
 
 template<typename Shape, typename Key>
 class HashTable: public FixedArray {
  public:
   // Returns the number of elements in the hash table.
   int NumberOfElements() {
     return Smi::cast(get(kNumberOfElementsIndex))->value();
   }
 
+  // Returns the number of deleted elements in the hash table.
+  int NumberOfDeletedElements() {
+    return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
+  }
+
   // Returns the capacity of the hash table.
   int Capacity() {
     return Smi::cast(get(kCapacityIndex))->value();
   }
 
   // ElementAdded should be called whenever an element is added to a
   // hash table.
   void ElementAdded() { SetNumberOfElements(NumberOfElements() + 1); }
 
   // ElementRemoved should be called whenever an element is removed from
   // a hash table.
-  void ElementRemoved() { SetNumberOfElements(NumberOfElements() - 1); }
-  void ElementsRemoved(int n) { SetNumberOfElements(NumberOfElements() - n); }
+  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.
   static Object* Allocate(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.  Null and undefined are not allowed
   // as keys and can be used to indicate missing or deleted elements.
   bool IsKey(Object* k) {
     return !k->IsNull() && !k->IsUndefined();
   }
 
   // Garbage collection support.
   void IteratePrefix(ObjectVisitor* visitor);
   void IterateElements(ObjectVisitor* visitor);
 
   // Casting.
   static inline HashTable* cast(Object* obj);
 
   // Compute the probe offset (quadratic probing).
   INLINE(static uint32_t GetProbeOffset(uint32_t n)) {
     return (n + n * n) >> 1;
   }
 
   static const int kNumberOfElementsIndex = 0;
-  static const int kCapacityIndex         = 1;
-  static const int kPrefixStartIndex      = 2;
-  static const int kElementsStartIndex    =
+  static const int kNumberOfDeletedElementsIndex = 1;
+  static const int kCapacityIndex = 2;
+  static const int kPrefixStartIndex = 3;
+  static const int kElementsStartIndex =
       kPrefixStartIndex + Shape::kPrefixSize;
-  static const int kEntrySize             = Shape::kEntrySize;
-  static const int kElementsStartOffset   =
+  static const int kEntrySize = Shape::kEntrySize;
+  static const int kElementsStartOffset =
       kHeaderSize + kElementsStartIndex * kPointerSize;
 
   // Constant used for denoting a absent entry.
   static const int kNotFound = -1;
 
   // Find entry for key otherwise return -1.
   int FindEntry(Key key);
 
  protected:
 
   // 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;
   }
 
   // Update the number of elements in the hash table.
   void SetNumberOfElements(int nof) {
     fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof));
   }
 
+  // Update the number of deleted elements in the hash table.
+  void SetNumberOfDeletedElements(int nod) {
+    fast_set(this, kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
+  }
+
   // Sets the capacity of the hash table.
   void SetCapacity(int capacity) {
     // To scale a computed hash code to fit within the hash table, we
     // use bit-wise AND with a mask, so the capacity must be positive
     // and non-zero.
     ASSERT(capacity > 0);
     fast_set(this, kCapacityIndex, Smi::FromInt(capacity));
   }
 
 
@@ skipping 2915 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_