OrderedHashTable implementation with Set and Map interfaces

test/cctest/test-ordered-hash-table.cc

Index: test/cctest/test-ordered-hash-table.cc
diff --git a/test/cctest/test-dictionary.cc b/test/cctest/test-ordered-hash-table.cc
similarity index 50%
copy from test/cctest/test-dictionary.cc
copy to test/cctest/test-ordered-hash-table.cc
index 6e62a2243c26eed0e00222abc2e44930be05a145..b5ce0140d06a2a7f3a68e89b117bfae17fa36991 100644
--- a/test/cctest/test-dictionary.cc
+++ b/test/cctest/test-ordered-hash-table.cc
@@ -1,4 +1,4 @@
-// Copyright 2011 the V8 project authors. All rights reserved.
+// Copyright 2014 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:
@@ -25,29 +25,148 @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+#include <stdlib.h>
+
 #include "v8.h"
 
-#include "api.h"
-#include "debug.h"
-#include "execution.h"
-#include "factory.h"
-#include "macro-assembler.h"
-#include "objects.h"
-#include "global-handles.h"
 #include "cctest.h"
+#include "factory.h"
+
+namespace {
 
 using namespace v8::internal;
 
+TEST(Set) {
+  LocalContext context;
+  Isolate* isolate = CcTest::i_isolate();
+  Factory* factory = isolate->factory();
+  HandleScope scope(isolate);
+  Handle<OrderedHashSet> ordered_set = factory->NewOrderedHashSet();
+  CHECK_EQ(2, ordered_set->NumberOfBuckets());
+  CHECK_EQ(0, ordered_set->NumberOfElements());
+  CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
+
+  Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
+  Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
+  CHECK(!ordered_set->Contains(*obj));
+  ordered_set = OrderedHashSet::Add(ordered_set, obj);
+  CHECK_EQ(1, ordered_set->NumberOfElements());
+  CHECK(ordered_set->Contains(*obj));
+  ordered_set = OrderedHashSet::Remove(ordered_set, obj);
+  CHECK_EQ(0, ordered_set->NumberOfElements());
+  CHECK(!ordered_set->Contains(*obj));
+
+  // Test for collisions/chaining
+  Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
+  ordered_set = OrderedHashSet::Add(ordered_set, obj1);
+  Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
+  ordered_set = OrderedHashSet::Add(ordered_set, obj2);
+  Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
+  ordered_set = OrderedHashSet::Add(ordered_set, obj3);
+  CHECK_EQ(3, ordered_set->NumberOfElements());
+  CHECK(ordered_set->Contains(*obj1));
+  CHECK(ordered_set->Contains(*obj2));
+  CHECK(ordered_set->Contains(*obj3));
+
+  // Test growth
+  ordered_set = OrderedHashSet::Add(ordered_set, obj);
+  Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
+  ordered_set = OrderedHashSet::Add(ordered_set, obj4);
+  CHECK(ordered_set->Contains(*obj));
+  CHECK(ordered_set->Contains(*obj1));
+  CHECK(ordered_set->Contains(*obj2));
+  CHECK(ordered_set->Contains(*obj3));
+  CHECK(ordered_set->Contains(*obj4));
+  CHECK_EQ(5, ordered_set->NumberOfElements());
+  CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
+  CHECK_EQ(4, ordered_set->NumberOfBuckets());
+
+  // Test shrinking
+  ordered_set = OrderedHashSet::Remove(ordered_set, obj);
+  ordered_set = OrderedHashSet::Remove(ordered_set, obj1);
+  ordered_set = OrderedHashSet::Remove(ordered_set, obj2);
+  ordered_set = OrderedHashSet::Remove(ordered_set, obj3);
+  CHECK_EQ(1, ordered_set->NumberOfElements());
+  CHECK_EQ(2, ordered_set->NumberOfBuckets());
+}
+
+
+TEST(Map) {
+  LocalContext context;
+  Isolate* isolate = CcTest::i_isolate();
+  Factory* factory = isolate->factory();
+  HandleScope scope(isolate);
+  Handle<OrderedHashMap> ordered_map = factory->NewOrderedHashMap();
+  CHECK_EQ(2, ordered_map->NumberOfBuckets());
+  CHECK_EQ(0, ordered_map->NumberOfElements());
+  CHECK_EQ(0, ordered_map->NumberOfDeletedElements());
+
+  Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
+  Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> val = factory->NewJSObjectFromMap(map);
+  CHECK(ordered_map->Lookup(*obj)->IsTheHole());
+  ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
+  CHECK_EQ(1, ordered_map->NumberOfElements());
+  CHECK(ordered_map->Lookup(*obj)->SameValue(*val));
+  ordered_map = OrderedHashMap::Put(
+      ordered_map, obj, factory->the_hole_value());
+  CHECK_EQ(0, ordered_map->NumberOfElements());
+  CHECK(ordered_map->Lookup(*obj)->IsTheHole());
+
+  // Test for collisions/chaining
+  Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> val1 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> val2 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> val3 = factory->NewJSObjectFromMap(map);
+  ordered_map = OrderedHashMap::Put(ordered_map, obj1, val1);
+  ordered_map = OrderedHashMap::Put(ordered_map, obj2, val2);
+  ordered_map = OrderedHashMap::Put(ordered_map, obj3, val3);
+  CHECK_EQ(3, ordered_map->NumberOfElements());
+  CHECK(ordered_map->Lookup(*obj1)->SameValue(*val1));
+  CHECK(ordered_map->Lookup(*obj2)->SameValue(*val2));
+  CHECK(ordered_map->Lookup(*obj3)->SameValue(*val3));
+
+  // Test growth
+  ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
+  Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
+  Handle<JSObject> val4 = factory->NewJSObjectFromMap(map);
+  ordered_map = OrderedHashMap::Put(ordered_map, obj4, val4);
+  CHECK(ordered_map->Lookup(*obj)->SameValue(*val));
+  CHECK(ordered_map->Lookup(*obj1)->SameValue(*val1));
+  CHECK(ordered_map->Lookup(*obj2)->SameValue(*val2));
+  CHECK(ordered_map->Lookup(*obj3)->SameValue(*val3));
+  CHECK(ordered_map->Lookup(*obj4)->SameValue(*val4));
+  CHECK_EQ(5, ordered_map->NumberOfElements());
+  CHECK_EQ(4, ordered_map->NumberOfBuckets());
+
+  // Test shrinking
+  ordered_map = OrderedHashMap::Put(
+      ordered_map, obj, factory->the_hole_value());
+  ordered_map = OrderedHashMap::Put(
+      ordered_map, obj1, factory->the_hole_value());
+  ordered_map = OrderedHashMap::Put(
+      ordered_map, obj2, factory->the_hole_value());
+  ordered_map = OrderedHashMap::Put(
+      ordered_map, obj3, factory->the_hole_value());
+  CHECK_EQ(1, ordered_map->NumberOfElements());
+  CHECK_EQ(2, ordered_map->NumberOfBuckets());
+}
+
+
+// BELOW THIS LINE TESTS WERE CONVERTED FROM test-dictionary.cc

[Michael Starzinger, 2014/04/02 12:09:37]

It would be nice if we could avoid duplicating the tests from test-dictionary.cc
here. Would it be possible to templatize the tests in test-dictionary.cc and
instantiate them there for both, ObjectHashTable and OrderedHashMap. At a first
glance this looks doable for all tests right after the call to
Factory::NewFoo().

[adamk, 2014/04/02 22:01:10]

Yeah, should be able to take care of this, will look into it next.

+
 
 TEST(ObjectHashTable) {
   LocalContext context;
   Isolate* isolate = CcTest::i_isolate();
   Factory* factory = isolate->factory();
   v8::HandleScope scope(context->GetIsolate());
-  Handle<ObjectHashTable> table = factory->NewObjectHashTable(23);
+  Handle<OrderedHashMap> table = factory->NewOrderedHashMap();
   Handle<JSObject> a = factory->NewJSArray(7);
   Handle<JSObject> b = factory->NewJSArray(11);
-  table = ObjectHashTable::Put(table, a, b);
+  table = OrderedHashMap::Put(table, a, b);
   CHECK_EQ(table->NumberOfElements(), 1);
   CHECK_EQ(table->Lookup(*a), *b);
   CHECK_EQ(table->Lookup(*b), CcTest::heap()->the_hole_value());
@@ -59,14 +178,13 @@ TEST(ObjectHashTable) {
   CHECK_EQ(table->Lookup(*b), CcTest::heap()->the_hole_value());
 
   // Keys that are overwritten should not change number of elements.
-  table = ObjectHashTable::Put(table, a, factory->NewJSArray(13));
+  table = OrderedHashMap::Put(table, a, factory->NewJSArray(13));
   CHECK_EQ(table->NumberOfElements(), 1);
   CHECK_NE(table->Lookup(*a), *b);
 
   // Keys mapped to the hole should be removed permanently.
-  table = ObjectHashTable::Put(table, a, factory->the_hole_value());
+  table = OrderedHashMap::Put(table, a, factory->the_hole_value());
   CHECK_EQ(table->NumberOfElements(), 0);
-  CHECK_EQ(table->NumberOfDeletedElements(), 1);
   CHECK_EQ(table->Lookup(*a), CcTest::heap()->the_hole_value());
 
   // Keys should map back to their respective values and also should get
@@ -74,9 +192,9 @@ TEST(ObjectHashTable) {
   for (int i = 0; i < 100; i++) {
     Handle<JSReceiver> key = factory->NewJSArray(7);
     Handle<JSObject> value = factory->NewJSArray(11);
-    table = ObjectHashTable::Put(table, key, value);
+    table = OrderedHashMap::Put(table, key, value);
     CHECK_EQ(table->NumberOfElements(), i + 1);
-    CHECK_NE(table->FindEntry(*key), ObjectHashTable::kNotFound);
+    CHECK_NE(table->FindEntry(*key), OrderedHashMap::kNotFound);
     CHECK_EQ(table->Lookup(*key), *value);
     CHECK(key->GetIdentityHash()->IsSmi());
   }
@@ -86,7 +204,7 @@ TEST(ObjectHashTable) {
   for (int i = 0; i < 100; i++) {
     Handle<JSReceiver> key = factory->NewJSArray(7);
     CHECK(JSReceiver::GetOrCreateIdentityHash(key)->IsSmi());
-    CHECK_EQ(table->FindEntry(*key), ObjectHashTable::kNotFound);
+    CHECK_EQ(table->FindEntry(*key), OrderedHashMap::kNotFound);
     CHECK_EQ(table->Lookup(*key), CcTest::heap()->the_hole_value());
     CHECK(key->GetIdentityHash()->IsSmi());
   }
@@ -102,65 +220,14 @@ TEST(ObjectHashTable) {
 }
 
 
-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 = CcTest::i_isolate();
-  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) {
+TEST(OrderedHashSetCausesGC) {
   i::FLAG_stress_compaction = false;
   LocalContext context;
   Isolate* isolate = CcTest::i_isolate();
   Factory* factory = isolate->factory();
   v8::HandleScope scope(context->GetIsolate());
-  Handle<ObjectHashSet> table = factory->NewObjectHashSet(1);
+  Handle<OrderedHashSet> table = factory->NewOrderedHashSet();
   Handle<JSObject> key = factory->NewJSArray(0);
   v8::Handle<v8::Object> key_obj = v8::Utils::ToLocal(key);
 
@@ -180,24 +247,24 @@ TEST(ObjectHashSetCausesGC) {
   CHECK(gc_count == isolate->heap()->gc_count());
 
   // Calling Remove() will not cause GC in this case.
-  table = ObjectHashSet::Remove(table, key);
+  table = OrderedHashSet::Remove(table, key);
   CHECK(gc_count == isolate->heap()->gc_count());
 
   // Calling Add() should cause GC.
-  table = ObjectHashSet::Add(table, key);
+  table = OrderedHashSet::Add(table, key);
   CHECK(gc_count < isolate->heap()->gc_count());
 }
 #endif
 
 
 #ifdef DEBUG
-TEST(ObjectHashTableCausesGC) {
+TEST(OrderedHashMapCausesGC) {
   i::FLAG_stress_compaction = false;
   LocalContext context;
   Isolate* isolate = CcTest::i_isolate();
   Factory* factory = isolate->factory();
   v8::HandleScope scope(context->GetIsolate());
-  Handle<ObjectHashTable> table = factory->NewObjectHashTable(1);
+  Handle<OrderedHashMap> table = factory->NewOrderedHashMap();
   Handle<JSObject> key = factory->NewJSArray(0);
   v8::Handle<v8::Object> key_obj = v8::Utils::ToLocal(key);
 
@@ -216,7 +283,9 @@ TEST(ObjectHashTableCausesGC) {
 
   // Calling Put() should request GC by returning a failure.
   int gc_count = isolate->heap()->gc_count();
-  ObjectHashTable::Put(table, key, key);
+  OrderedHashMap::Put(table, key, key);
   CHECK(gc_count < isolate->heap()->gc_count());
 }
 #endif
+
+}