Implement in-place rehashing of HashTable.

test/cctest/test-dictionary.cc

 // Copyright 2011 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 83 matching lines @@
   // Keys that don't have an identity hash should not be found and also
   // should not get an identity hash code generated.
   for (int i = 0; i < 100; i++) {
     Handle<JSReceiver> key = factory->NewJSArray(7);
     CHECK_EQ(table->Lookup(*key), HEAP->the_hole_value());
     CHECK_EQ(key->GetIdentityHash(OMIT_CREATION), HEAP->undefined_value());
   }
 }
 
 
+class ObjectHashTableTest: public ObjectHashTable {
+ public:
+  void insert(int entry, int key, int value) {
+    set(EntryToIndex(entry), Smi::FromInt(key));
+    set(EntryToIndex(entry) + 1, Smi::FromInt(value));
+  }
+
+  int lookup(int key) {
+    return Smi::cast(Lookup(Smi::FromInt(key)))->value();
+  }
+
+  int capacity() {
+    return Capacity();
+  }
+};
+
+
+TEST(HashTableRehash) {
+  LocalContext context;
+  Isolate* isolate = Isolate::Current();
+  Factory* factory = isolate->factory();
+  v8::HandleScope scope(context->GetIsolate());
+  // Test almost filled table.
+  {
+    Handle<ObjectHashTable> table = factory->NewObjectHashTable(100);
+    ObjectHashTableTest* t = reinterpret_cast<ObjectHashTableTest*>(*table);
+    int capacity = t->capacity();
+    for (int i = 0; i < capacity - 1; i++) {
+      t->insert(i, i * i, i);
+    }
+    t->Rehash(Smi::FromInt(0));
+    for (int i = 0; i < capacity - 1; i++) {
+      CHECK_EQ(i, t->lookup(i * i));
+    }
+  }
+  // Test half-filled table.
+  {
+    Handle<ObjectHashTable> table = factory->NewObjectHashTable(100);
+    ObjectHashTableTest* t = reinterpret_cast<ObjectHashTableTest*>(*table);
+    int capacity = t->capacity();
+    for (int i = 0; i < capacity / 2; i++) {
+      t->insert(i, i * i, i);
+    }
+    t->Rehash(Smi::FromInt(0));
+    for (int i = 0; i < capacity / 2; i++) {
+      CHECK_EQ(i, t->lookup(i * i));
+    }
+  }
+}
+
+
 #ifdef DEBUG
 TEST(ObjectHashSetCausesGC) {
   i::FLAG_stress_compaction = false;
   LocalContext context;
   Isolate* isolate = Isolate::Current();
   Factory* factory = isolate->factory();
   v8::HandleScope scope(context->GetIsolate());
   Handle<ObjectHashSet> table = factory->NewObjectHashSet(1);
   Handle<JSObject> key = factory->NewJSArray(0);
   v8::Handle<v8::Object> key_obj = v8::Utils::ToLocal(key);
@@ skipping 41 matching lines @@
   SimulateFullSpace(HEAP->new_space());
   SimulateFullSpace(HEAP->old_pointer_space());
 
   // Calling Lookup() should not cause GC ever.
   CHECK(table->Lookup(*key)->IsTheHole());
 
   // Calling Put() should request GC by returning a failure.
   CHECK(table->Put(*key, *key)->IsRetryAfterGC());
 }
 #endif