Revision: 20522
Author: [email protected]
Date: Fri Apr 4 20:41:57 2014 UTC
Log: OrderedHashTable implementation with Set and Map interfaces
OrderedHashTable is an insertion-ordered HashTable based on
Jason Orendorff's writeup of a data structure attributed to Tyler Close:
https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
It is intended as the new backing store for JSSet/JSMap, as ES6 requires
insertion-order-based iteration. Note, however, that in the interest of
keeping the initial check-in small this patch does not yet include any
iteration support.
This change also doesn't yet touch any existing behavior, but in
a branch I've verified that these structures pass the existing
JSSet/JSMap mjsunit tests.
BUG=v8:1793
LOG=N
[email protected]
Review URL: https://codereview.chromium.org/220293002
http://code.google.com/p/v8/source/detail?r=20522
Added:
/branches/bleeding_edge/test/cctest/test-ordered-hash-table.cc
Modified:
/branches/bleeding_edge/src/factory.cc
/branches/bleeding_edge/src/factory.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/test/cctest/cctest.gyp
/branches/bleeding_edge/test/cctest/test-dictionary.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/cctest/test-ordered-hash-table.cc Fri Apr
4 20:41:57 2014 UTC
@@ -0,0 +1,158 @@
+// 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:
+//
+// * 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
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (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 "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());
+}
+
+
+}
=======================================
--- /branches/bleeding_edge/src/factory.cc Fri Apr 4 12:06:11 2014 UTC
+++ /branches/bleeding_edge/src/factory.cc Fri Apr 4 20:41:57 2014 UTC
@@ -107,6 +107,16 @@
at_least_space_for),
ObjectHashSet);
}
+
+
+Handle<OrderedHashSet> Factory::NewOrderedHashSet() {
+ return OrderedHashSet::Allocate(isolate(), 4);
+}
+
+
+Handle<OrderedHashMap> Factory::NewOrderedHashMap() {
+ return OrderedHashMap::Allocate(isolate(), 4);
+}
Handle<ObjectHashTable> Factory::NewObjectHashTable(
=======================================
--- /branches/bleeding_edge/src/factory.h Fri Apr 4 12:06:11 2014 UTC
+++ /branches/bleeding_edge/src/factory.h Fri Apr 4 20:41:57 2014 UTC
@@ -57,6 +57,9 @@
int at_least_space_for,
MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
+ Handle<OrderedHashSet> NewOrderedHashSet();
+ Handle<OrderedHashMap> NewOrderedHashMap();
+
Handle<WeakHashTable> NewWeakHashTable(int at_least_space_for);
Handle<DescriptorArray> NewDescriptorArray(int number_of_descriptors,
=======================================
--- /branches/bleeding_edge/src/objects.cc Fri Apr 4 16:18:59 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Fri Apr 4 20:41:57 2014 UTC
@@ -15900,6 +15900,197 @@
set(EntryToValueIndex(entry), value);
ElementAdded();
}
+
+
+template<class Derived, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
+ Isolate* isolate, int capacity, PretenureFlag pretenure) {
+ // Capacity must be a power of two, since we depend on being able
+ // to divide and multiple by 2 (kLoadFactor) to derive capacity
+ // from number of buckets. If we decide to change kLoadFactor
+ // to something other than 2, capacity should be stored as another
+ // field of this object.
+ const int kMinCapacity = 4;
+ capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity));
+ if (capacity > kMaxCapacity) {
+ v8::internal::Heap::FatalProcessOutOfMemory("invalid table size",
true);
+ }
+ int num_buckets = capacity / kLoadFactor;
+ Handle<Derived> table =
+ Handle<Derived>::cast(
+ isolate->factory()->NewFixedArray(
+ kHashTableStartIndex + num_buckets + (capacity * kEntrySize),
+ pretenure));
+ for (int i = 0; i < num_buckets; ++i) {
+ table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound));
+ }
+ table->SetNumberOfBuckets(num_buckets);
+ table->SetNumberOfElements(0);
+ table->SetNumberOfDeletedElements(0);
+ return table;
+}
+
+
+template<class Derived, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
+ Handle<Derived> table) {
+ int nof = table->NumberOfElements();
+ int nod = table->NumberOfDeletedElements();
+ int capacity = table->Capacity();
+ if ((nof + nod) < capacity) return table;
+ // Don't need to grow if we can simply clear out deleted entries instead.
+ // Note that we can't compact in place, though, so we always allocate
+ // a new table.
+ return Rehash(table, (nod < (capacity >> 1)) ? capacity << 1 : capacity);
+}
+
+
+template<class Derived, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
+ Handle<Derived> table) {
+ int nof = table->NumberOfElements();
+ int capacity = table->Capacity();
+ if (nof > (capacity >> 2)) return table;
+ return Rehash(table, capacity / 2);
+}
+
+
+template<class Derived, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
+ Handle<Derived> table, int new_capacity) {
+ Handle<Derived> new_table =
+ Allocate(table->GetIsolate(),
+ new_capacity,
+ table->GetHeap()->InNewSpace(*table) ? NOT_TENURED :
TENURED);
+ int nof = table->NumberOfElements();
+ int nod = table->NumberOfDeletedElements();
+ int new_buckets = new_table->NumberOfBuckets();
+ int new_entry = 0;
+ for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
+ Object* key = table->KeyAt(old_entry);
+ if (key->IsTheHole()) continue;
+ Object* hash = key->GetHash();
+ int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
+ Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
+ new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
+ int new_index = new_table->EntryToIndex(new_entry);
+ int old_index = table->EntryToIndex(old_entry);
+ for (int i = 0; i < entrysize; ++i) {
+ Object* value = table->get(old_index + i);
+ new_table->set(new_index + i, value);
+ }
+ new_table->set(new_index + kChainOffset, chain_entry);
+ ++new_entry;
+ }
+ new_table->SetNumberOfElements(nof);
+ return new_table;
+}
+
+
+template<class Derived, int entrysize>
+int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) {
+ ASSERT(!key->IsTheHole());
+ Object* hash = key->GetHash();
+ if (hash->IsUndefined()) return kNotFound;
+ for (int entry = HashToEntry(Smi::cast(hash)->value());
+ entry != kNotFound;
+ entry = ChainAt(entry)) {
+ Object* candidate = KeyAt(entry);
+ if (candidate->SameValue(key))
+ return entry;
+ }
+ return kNotFound;
+}
+
+
+template<class Derived, int entrysize>
+int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) {
+ int entry = NumberOfElements() + NumberOfDeletedElements();
+ int bucket = HashToBucket(hash);
+ int index = EntryToIndex(entry);
+ Object* chain_entry = get(kHashTableStartIndex + bucket);
+ set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
+ set(index + kChainOffset, chain_entry);
+ SetNumberOfElements(NumberOfElements() + 1);
+ return index;
+}
+
+
+template<class Derived, int entrysize>
+void OrderedHashTable<Derived, entrysize>::RemoveEntry(int entry) {
+ int index = EntryToIndex(entry);
+ for (int i = 0; i < entrysize; ++i) {
+ set_the_hole(index + i);
+ }
+ SetNumberOfElements(NumberOfElements() - 1);
+ SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
+}
+
+
+template class OrderedHashTable<OrderedHashSet, 1>;
+template class OrderedHashTable<OrderedHashMap, 2>;
+
+
+bool OrderedHashSet::Contains(Object* key) {
+ return FindEntry(key) != kNotFound;
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table,
+ Handle<Object> key) {
+ if (table->FindEntry(*key) != kNotFound) return table;
+
+ table = EnsureGrowable(table);
+
+ Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+ int index = table->AddEntry(Smi::cast(*hash)->value());
+ table->set(index, *key);
+ return table;
+}
+
+
+Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table,
+ Handle<Object> key) {
+ int entry = table->FindEntry(*key);
+ if (entry == kNotFound) return table;
+ table->RemoveEntry(entry);
+ // TODO(adamk): Don't shrink if we're being iterated over
+ return Shrink(table);
+}
+
+
+Object* OrderedHashMap::Lookup(Object* key) {
+ int entry = FindEntry(key);
+ if (entry == kNotFound) return GetHeap()->the_hole_value();
+ return ValueAt(entry);
+}
+
+
+Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
+ Handle<Object> key,
+ Handle<Object> value) {
+ int entry = table->FindEntry(*key);
+
+ if (value->IsTheHole()) {
+ if (entry == kNotFound) return table;
+ table->RemoveEntry(entry);
+ // TODO(adamk): Only shrink if not iterating
+ return Shrink(table);
+ }
+
+ if (entry != kNotFound) {
+ table->set(table->EntryToIndex(entry) + kValueOffset, *value);
+ return table;
+ }
+
+ table = EnsureGrowable(table);
+
+ Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
+ int index = table->AddEntry(Smi::cast(*hash)->value());
+ table->set(index, *key);
+ table->set(index + kValueOffset, *value);
+ return table;
+}
DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
=======================================
--- /branches/bleeding_edge/src/objects.h Fri Apr 4 16:18:59 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Fri Apr 4 20:41:57 2014 UTC
@@ -92,6 +92,9 @@
// - CompilationCacheTable
// - CodeCacheHashTable
// - MapCache
+// - OrderedHashTable
+// - OrderedHashSet
+// - OrderedHashMap
// - Context
// - JSFunctionResultCache
// - ScopeInfo
@@ -4266,6 +4269,163 @@
};
+// OrderedHashTable is a HashTable with Object keys that preserves
+// insertion order. There are Map and Set interfaces (OrderedHashMap
+// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
+//
+// Only Object* keys are supported, with Object::SameValue() used as the
+// equality operator and Object::GetHash() for the hash function.
+//
+// Based on the "Deterministic Hash Table" as described by Jason Orendorff
at
+// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
+// Originally attributed to Tyler Close.
+//
+// Memory layout:
+// [0]: bucket count
+// [1]: element count
+// [2]: deleted element count
+// [3..(NumberOfBuckets() - 1)]: "hash table", where each item is an
offset
+// into the data table (see below) where
the
+// first item in this bucket is stored.
+// [3 + NumberOfBuckets()..length]: "data table", an array of length
+// Capacity() * kEntrySize, where the first
entrysize
+// items are handled by the derived class and
the
+// item at kChainOffset is another entry into
the
+// data table indicating the next entry in this
hash
+// bucket.
+template<class Derived, int entrysize>
+class OrderedHashTable: public FixedArray {
+ public:
+ // Returns an OrderedHashTable with a capacity of at least |capacity|.
+ static Handle<Derived> Allocate(
+ Isolate* isolate, int capacity, PretenureFlag pretenure =
NOT_TENURED);
+
+ // Returns an OrderedHashTable (possibly |table|) with enough space
+ // to add at least one new element, or returns a Failure if a GC occurs.
+ static Handle<Derived> EnsureGrowable(Handle<Derived> table);
+
+ // Returns an OrderedHashTable (possibly |table|) that's shrunken
+ // if possible.
+ static Handle<Derived> Shrink(Handle<Derived> table);
+
+ // Returns kNotFound if the key isn't present.
+ int FindEntry(Object* key);
+
+ int NumberOfElements() {
+ return Smi::cast(get(kNumberOfElementsIndex))->value();
+ }
+
+ int NumberOfDeletedElements() {
+ return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
+ }
+
+ int NumberOfBuckets() {
+ return Smi::cast(get(kNumberOfBucketsIndex))->value();
+ }
+
+ // Returns the index into the data table where the new entry
+ // should be placed. The table is assumed to have enough space
+ // for a new entry.
+ int AddEntry(int hash);
+
+ // Removes the entry, and puts the_hole in entrysize pointers
+ // (leaving the hash table chain intact).
+ void RemoveEntry(int entry);
+
+ // Returns an index into |this| for the given entry.
+ int EntryToIndex(int entry) {
+ return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
+ }
+
+ static const int kNotFound = -1;
+
+ private:
+ static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
+
+ void SetNumberOfBuckets(int num) {
+ set(kNumberOfBucketsIndex, Smi::FromInt(num));
+ }
+
+ void SetNumberOfElements(int num) {
+ set(kNumberOfElementsIndex, Smi::FromInt(num));
+ }
+
+ void SetNumberOfDeletedElements(int num) {
+ set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
+ }
+
+ int Capacity() {
+ return NumberOfBuckets() * kLoadFactor;
+ }
+
+ Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
+
+ // Returns the next entry for the given entry.
+ int ChainAt(int entry) {
+ return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value();
+ }
+
+ int HashToBucket(int hash) {
+ return hash & (NumberOfBuckets() - 1);
+ }
+
+ int HashToEntry(int hash) {
+ int bucket = HashToBucket(hash);
+ return Smi::cast(get(kHashTableStartIndex + bucket))->value();
+ }
+
+ static const int kNumberOfBucketsIndex = 0;
+ static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1;
+ static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex
+ 1;
+ static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex +
1;
+
+ static const int kEntrySize = entrysize + 1;
+ static const int kChainOffset = entrysize;
+
+ static const int kLoadFactor = 2;
+ static const int kMaxCapacity =
+ (FixedArray::kMaxLength - kHashTableStartIndex)
+ / (1 + (kEntrySize * kLoadFactor));
+};
+
+
+class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
+ public:
+ static OrderedHashSet* cast(Object* obj) {
+ ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this
+ return reinterpret_cast<OrderedHashSet*>(obj);
+ }
+
+ bool Contains(Object* key);
+ static Handle<OrderedHashSet> Add(
+ Handle<OrderedHashSet> table, Handle<Object> key);
+ static Handle<OrderedHashSet> Remove(
+ Handle<OrderedHashSet> table, Handle<Object> key);
+};
+
+
+class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> {
+ public:
+ static OrderedHashMap* cast(Object* obj) {
+ ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this
+ return reinterpret_cast<OrderedHashMap*>(obj);
+ }
+
+ Object* Lookup(Object* key);
+ static Handle<OrderedHashMap> Put(
+ Handle<OrderedHashMap> table,
+ Handle<Object> key,
+ Handle<Object> value);
+
+ private:
+ Object* ValueAt(int entry) {
+ return get(EntryToIndex(entry) + kValueOffset);
+ }
+
+ static const int kValueOffset = 1;
+};
+
+
template <int entrysize>
class WeakHashTableShape : public BaseShape<Object*> {
public:
=======================================
--- /branches/bleeding_edge/test/cctest/cctest.gyp Fri Mar 21 09:28:26 2014
UTC
+++ /branches/bleeding_edge/test/cctest/cctest.gyp Fri Apr 4 20:41:57 2014
UTC
@@ -94,6 +94,7 @@
'test-mementos.cc',
'test-mutex.cc',
'test-object-observe.cc',
+ 'test-ordered-hash-table.cc',
'test-parsing.cc',
'test-platform.cc',
'test-platform-tls.cc',
=======================================
--- /branches/bleeding_edge/test/cctest/test-dictionary.cc Tue Nov 5
11:47:11 2013 UTC
+++ /branches/bleeding_edge/test/cctest/test-dictionary.cc Fri Apr 4
20:41:57 2014 UTC
@@ -38,16 +38,17 @@
using namespace v8::internal;
+namespace {
-TEST(ObjectHashTable) {
- LocalContext context;
+
+template<typename HashMap>
+static void TestHashMap(Handle<HashMap> table) {
Isolate* isolate = CcTest::i_isolate();
Factory* factory = isolate->factory();
- v8::HandleScope scope(context->GetIsolate());
- Handle<ObjectHashTable> table = factory->NewObjectHashTable(23);
+
Handle<JSObject> a = factory->NewJSArray(7);
Handle<JSObject> b = factory->NewJSArray(11);
- table = ObjectHashTable::Put(table, a, b);
+ table = HashMap::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 +60,13 @@
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 = HashMap::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 = HashMap::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 +74,9 @@
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 = HashMap::Put(table, key, value);
CHECK_EQ(table->NumberOfElements(), i + 1);
- CHECK_NE(table->FindEntry(*key), ObjectHashTable::kNotFound);
+ CHECK_NE(table->FindEntry(*key), HashMap::kNotFound);
CHECK_EQ(table->Lookup(*key), *value);
CHECK(key->GetIdentityHash()->IsSmi());
}
@@ -86,7 +86,7 @@
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), HashMap::kNotFound);
CHECK_EQ(table->Lookup(*key), CcTest::heap()->the_hole_value());
CHECK(key->GetIdentityHash()->IsSmi());
}
@@ -100,6 +100,15 @@
CcTest::heap()->undefined_value());
}
}
+
+
+TEST(HashMap) {
+ LocalContext context;
+ v8::HandleScope scope(context->GetIsolate());
+ Isolate* isolate = CcTest::i_isolate();
+ TestHashMap(isolate->factory()->NewObjectHashTable(23));
+ TestHashMap(isolate->factory()->NewOrderedHashMap());
+}
class ObjectHashTableTest: public ObjectHashTable {
@@ -154,13 +163,11 @@
#ifdef DEBUG
-TEST(ObjectHashSetCausesGC) {
- i::FLAG_stress_compaction = false;
- LocalContext context;
+template<class HashSet>
+static void TestHashSetCausesGC(Handle<HashSet> table) {
Isolate* isolate = CcTest::i_isolate();
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);
@@ -180,24 +187,32 @@
CHECK(gc_count == isolate->heap()->gc_count());
// Calling Remove() will not cause GC in this case.
- table = ObjectHashSet::Remove(table, key);
+ table = HashSet::Remove(table, key);
CHECK(gc_count == isolate->heap()->gc_count());
// Calling Add() should cause GC.
- table = ObjectHashSet::Add(table, key);
+ table = HashSet::Add(table, key);
CHECK(gc_count < isolate->heap()->gc_count());
}
+
+
+TEST(ObjectHashSetCausesGC) {
+ i::FLAG_stress_compaction = false;
+ LocalContext context;
+ v8::HandleScope scope(context->GetIsolate());
+ Isolate* isolate = CcTest::i_isolate();
+ TestHashSetCausesGC(isolate->factory()->NewObjectHashSet(1));
+ TestHashSetCausesGC(isolate->factory()->NewOrderedHashSet());
+}
#endif
#ifdef DEBUG
-TEST(ObjectHashTableCausesGC) {
- i::FLAG_stress_compaction = false;
- LocalContext context;
+template<class HashMap>
+static void TestHashMapCausesGC(Handle<HashMap> table) {
Isolate* isolate = CcTest::i_isolate();
Factory* factory = isolate->factory();
- v8::HandleScope scope(context->GetIsolate());
- Handle<ObjectHashTable> table = factory->NewObjectHashTable(1);
+
Handle<JSObject> key = factory->NewJSArray(0);
v8::Handle<v8::Object> key_obj = v8::Utils::ToLocal(key);
@@ -216,7 +231,20 @@
// Calling Put() should request GC by returning a failure.
int gc_count = isolate->heap()->gc_count();
- ObjectHashTable::Put(table, key, key);
+ HashMap::Put(table, key, key);
CHECK(gc_count < isolate->heap()->gc_count());
}
+
+
+TEST(ObjectHashTableCausesGC) {
+ i::FLAG_stress_compaction = false;
+ LocalContext context;
+ v8::HandleScope scope(context->GetIsolate());
+ Isolate* isolate = CcTest::i_isolate();
+ TestHashMapCausesGC(isolate->factory()->NewObjectHashTable(1));
+ TestHashMapCausesGC(isolate->factory()->NewOrderedHashMap());
+}
#endif
+
+
+}
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
