Implement in-place rehashing of HashTable.

src/objects.cc

 // Copyright 2013 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 13748 matching lines @@
       }
     }
   }
   new_table->SetNumberOfElements(NumberOfElements());
   new_table->SetNumberOfDeletedElements(0);
   return new_table;
 }
 
 
 template<typename Shape, typename Key>
+uint32_t HashTable<Shape, Key>::EntryForProbe(Key key,
+                                              Object* k,
+                                              int probe,
+                                              uint32_t expected) {
+  uint32_t hash = HashTable<Shape, Key>::HashForObject(key, k);
+  uint32_t capacity = Capacity();
+  uint32_t entry = FirstProbe(hash, capacity);
+  for (int i = 1; i < probe; i++) {
+    if (entry == expected) return expected;
+    entry = NextProbe(entry, i, capacity);
+  }
+  return entry;
+}
+
+
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::Swap(uint32_t entry1,
+                                 uint32_t entry2,
+                                 WriteBarrierMode mode) {
+  int index1 = EntryToIndex(entry1);
+  int index2 = EntryToIndex(entry2);
+  Object* temp[Shape::kEntrySize];
+  for (int j = 0; j < Shape::kEntrySize; j++) {
+    temp[j] = get(index1 + j);
+  }
+  for (int j = 0; j < Shape::kEntrySize; j++) {
+    set(index1 + j, get(index2 + j), mode);
+  }
+  for (int j = 0; j < Shape::kEntrySize; j++) {
+    set(index2 + j, temp[j], mode);
+  }
+}
+
+
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::Rehash(Key key) {
+  DisallowHeapAllocation no_gc;
+  WriteBarrierMode mode = GetWriteBarrierMode(no_gc);
+  uint32_t capacity = Capacity();
+  bool done = false;
+  for (int probe = 1; !done; probe++) {
+    // All elements at entries given by one of the first _probe_ probes
+    // are placed correctly. Other elements might need to be moved.
+    done = true;
+    for (uint32_t current = 0; current < capacity; current++) {
+      Object* current_key = get(EntryToIndex(current));
+      if (IsKey(current_key)) {
+        uint32_t target = EntryForProbe(key, current_key, probe, current);
+        if (current == target) continue;
+        Object* target_key = get(EntryToIndex(target));
+        if (!IsKey(target_key) ||
+            EntryForProbe(key, target_key, probe, target) != target) {
+          // Put the current element into the correct position.
+          Swap(current, target, mode);
+          // The other element will be processed on the next iteration.
+          current--;
+        } else {
+          // The place for the current element is occupied. Leave the element
+          // for the next probe.
+          done = false;
+        }
+      }
+    }
+  }
+}
+
+
+template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
   int nod = NumberOfDeletedElements();
   // Return if:
   //   50% is still free after adding n elements and
   //   at most 50% of the free elements are deleted elements.
   if (nod <= (capacity - nof) >> 1) {
     int needed_free = nof >> 1;
     if (nof + needed_free <= capacity) return this;
@@ skipping 2269 matching lines @@
 #define ERROR_MESSAGES_TEXTS(C, T) T,
   static const char* error_messages_[] = {
       ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS)
   };
 #undef ERROR_MESSAGES_TEXTS
   return error_messages_[reason];
 }
 
 
 } }  // namespace v8::internal