Revision: 20585
Author: [email protected]
Date: Tue Apr 8 20:06:35 2014 UTC
Log: Use OrderedHashTables as the backing store of JSSet and JSMap
This also deletes ObjectHashSet as it's no longer used.
BUG=v8:1793
LOG=N
[email protected]
Review URL: https://codereview.chromium.org/225183009
http://code.google.com/p/v8/source/detail?r=20585
Modified:
/branches/bleeding_edge/include/v8.h
/branches/bleeding_edge/src/factory.cc
/branches/bleeding_edge/src/factory.h
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/heap.h
/branches/bleeding_edge/src/objects-debug.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/test/cctest/test-dictionary.cc
=======================================
--- /branches/bleeding_edge/include/v8.h Mon Apr 7 11:11:25 2014 UTC
+++ /branches/bleeding_edge/include/v8.h Tue Apr 8 20:06:35 2014 UTC
@@ -5604,7 +5604,7 @@
static const int kNullValueRootIndex = 7;
static const int kTrueValueRootIndex = 8;
static const int kFalseValueRootIndex = 9;
- static const int kEmptyStringRootIndex = 159;
+ static const int kEmptyStringRootIndex = 160;
static const int kNodeClassIdOffset = 1 * kApiPointerSize;
static const int kNodeFlagsOffset = 1 * kApiPointerSize + 3;
=======================================
--- /branches/bleeding_edge/src/factory.cc Tue Apr 8 09:49:49 2014 UTC
+++ /branches/bleeding_edge/src/factory.cc Tue Apr 8 20:06:35 2014 UTC
@@ -97,15 +97,6 @@
at_least_space_for),
UnseededNumberDictionary);
}
-
-
-Handle<ObjectHashSet> Factory::NewObjectHashSet(int at_least_space_for) {
- ASSERT(0 <= at_least_space_for);
- CALL_HEAP_FUNCTION(isolate(),
- ObjectHashSet::Allocate(isolate()->heap(),
- at_least_space_for),
- ObjectHashSet);
-}
Handle<OrderedHashSet> Factory::NewOrderedHashSet() {
=======================================
--- /branches/bleeding_edge/src/factory.h Tue Apr 8 06:45:53 2014 UTC
+++ /branches/bleeding_edge/src/factory.h Tue Apr 8 20:06:35 2014 UTC
@@ -46,8 +46,6 @@
Handle<NameDictionary> NewNameDictionary(int at_least_space_for);
- Handle<ObjectHashSet> NewObjectHashSet(int at_least_space_for);
-
Handle<ObjectHashTable> NewObjectHashTable(
int at_least_space_for,
MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
=======================================
--- /branches/bleeding_edge/src/heap.cc Tue Apr 8 10:00:57 2014 UTC
+++ /branches/bleeding_edge/src/heap.cc Tue Apr 8 20:06:35 2014 UTC
@@ -2901,6 +2901,7 @@
}
ALLOCATE_VARSIZE_MAP(FIXED_ARRAY_TYPE, hash_table)
+ ALLOCATE_VARSIZE_MAP(FIXED_ARRAY_TYPE, ordered_hash_table)
ALLOCATE_VARSIZE_MAP(FIXED_ARRAY_TYPE, function_context)
ALLOCATE_VARSIZE_MAP(FIXED_ARRAY_TYPE, catch_context)
=======================================
--- /branches/bleeding_edge/src/heap.h Tue Apr 8 06:15:20 2014 UTC
+++ /branches/bleeding_edge/src/heap.h Tue Apr 8 20:06:35 2014 UTC
@@ -74,6 +74,7 @@
V(Map, constant_pool_array_map,
ConstantPoolArrayMap) \
V(Oddball, no_interceptor_result_sentinel,
NoInterceptorResultSentinel) \
V(Map, hash_table_map,
HashTableMap) \
+ V(Map, ordered_hash_table_map,
OrderedHashTableMap) \
V(FixedArray, empty_fixed_array,
EmptyFixedArray) \
V(ByteArray, empty_byte_array,
EmptyByteArray) \
V(DescriptorArray, empty_descriptor_array,
EmptyDescriptorArray) \
@@ -260,6 +261,7 @@
V(constant_pool_array_map) \
V(no_interceptor_result_sentinel) \
V(hash_table_map) \
+ V(ordered_hash_table_map) \
V(empty_fixed_array) \
V(empty_byte_array) \
V(empty_descriptor_array) \
=======================================
--- /branches/bleeding_edge/src/objects-debug.cc Tue Apr 8 09:49:49 2014
UTC
+++ /branches/bleeding_edge/src/objects-debug.cc Tue Apr 8 20:06:35 2014
UTC
@@ -699,7 +699,7 @@
CHECK(IsJSSet());
JSObjectVerify();
VerifyHeapPointer(table());
- CHECK(table()->IsHashTable() || table()->IsUndefined());
+ CHECK(table()->IsOrderedHashTable() || table()->IsUndefined());
}
@@ -707,7 +707,7 @@
CHECK(IsJSMap());
JSObjectVerify();
VerifyHeapPointer(table());
- CHECK(table()->IsHashTable() || table()->IsUndefined());
+ CHECK(table()->IsOrderedHashTable() || table()->IsUndefined());
}
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Tue Apr 8 16:31:57 2014 UTC
+++ /branches/bleeding_edge/src/objects-inl.h Tue Apr 8 20:06:35 2014 UTC
@@ -926,6 +926,13 @@
bool Object::IsObjectHashTable() {
return IsHashTable();
}
+
+
+bool Object::IsOrderedHashTable() {
+ return IsHeapObject() &&
+ HeapObject::cast(this)->map() ==
+ HeapObject::cast(this)->GetHeap()->ordered_hash_table_map();
+}
bool Object::IsPrimitive() {
@@ -6754,28 +6761,22 @@
}
-template <int entrysize>
-bool ObjectHashTableShape<entrysize>::IsMatch(Object* key, Object* other) {
+bool ObjectHashTableShape::IsMatch(Object* key, Object* other) {
return key->SameValue(other);
}
-template <int entrysize>
-uint32_t ObjectHashTableShape<entrysize>::Hash(Object* key) {
+uint32_t ObjectHashTableShape::Hash(Object* key) {
return Smi::cast(key->GetHash())->value();
}
-template <int entrysize>
-uint32_t ObjectHashTableShape<entrysize>::HashForObject(Object* key,
- Object* other) {
+uint32_t ObjectHashTableShape::HashForObject(Object* key, Object* other) {
return Smi::cast(other->GetHash())->value();
}
-template <int entrysize>
-MaybeObject* ObjectHashTableShape<entrysize>::AsObject(Heap* heap,
- Object* key) {
+MaybeObject* ObjectHashTableShape::AsObject(Heap* heap, Object* key) {
return key;
}
=======================================
--- /branches/bleeding_edge/src/objects.cc Tue Apr 8 14:20:29 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Tue Apr 8 20:06:35 2014 UTC
@@ -14251,9 +14251,7 @@
template class HashTable<MapCacheShape, HashTableKey*>;
-template class HashTable<ObjectHashTableShape<1>, Object*>;
-
-template class HashTable<ObjectHashTableShape<2>, Object*>;
+template class HashTable<ObjectHashTableShape, Object*>;
template class HashTable<WeakHashTableShape<2>, Object*>;
@@ -15774,88 +15772,13 @@
return obj;
}
-
-Handle<ObjectHashSet> ObjectHashSet::EnsureCapacity(
- Handle<ObjectHashSet> table,
- int n,
- Handle<Object> key,
- PretenureFlag pretenure) {
- Handle<HashTable<ObjectHashTableShape<1>, Object*> > table_base = table;
- CALL_HEAP_FUNCTION(table_base->GetIsolate(),
- table_base->EnsureCapacity(n, *key, pretenure),
- ObjectHashSet);
-}
-
-
-Handle<ObjectHashSet> ObjectHashSet::Shrink(Handle<ObjectHashSet> table,
- Handle<Object> key) {
- Handle<HashTable<ObjectHashTableShape<1>, Object*> > table_base = table;
- CALL_HEAP_FUNCTION(table_base->GetIsolate(),
- table_base->Shrink(*key),
- ObjectHashSet);
-}
-
-
-bool ObjectHashSet::Contains(Object* key) {
- ASSERT(IsKey(key));
-
- // If the object does not have an identity hash, it was never used as a
key.
- Object* hash = key->GetHash();
- if (hash->IsUndefined()) return false;
-
- return (FindEntry(key) != kNotFound);
-}
-
-
-Handle<ObjectHashSet> ObjectHashSet::Add(Handle<ObjectHashSet> table,
- Handle<Object> key) {
- ASSERT(table->IsKey(*key));
-
- // Make sure the key object has an identity hash code.
- Handle<Object> object_hash = Object::GetOrCreateHash(key,
-
table->GetIsolate());
-
- int entry = table->FindEntry(*key);
-
- // Check whether key is already present.
- if (entry != kNotFound) return table;
-
- // Check whether the hash set should be extended and add entry.
- Handle<ObjectHashSet> new_table =
- ObjectHashSet::EnsureCapacity(table, 1, key);
- entry = new_table->FindInsertionEntry(Smi::cast(*object_hash)->value());
- new_table->set(EntryToIndex(entry), *key);
- new_table->ElementAdded();
- return new_table;
-}
-
-
-Handle<ObjectHashSet> ObjectHashSet::Remove(Handle<ObjectHashSet> table,
- Handle<Object> key) {
- ASSERT(table->IsKey(*key));
-
- // If the object does not have an identity hash, it was never used as a
key.
- if (key->GetHash()->IsUndefined()) return table;
-
- int entry = table->FindEntry(*key);
-
- // Check whether key is actually present.
- if (entry == kNotFound) return table;
-
- // Remove entry and try to shrink this hash set.
- table->set_the_hole(EntryToIndex(entry));
- table->ElementRemoved();
-
- return ObjectHashSet::Shrink(table, key);
-}
-
Handle<ObjectHashTable> ObjectHashTable::EnsureCapacity(
Handle<ObjectHashTable> table,
int n,
Handle<Object> key,
PretenureFlag pretenure) {
- Handle<HashTable<ObjectHashTableShape<2>, Object*> > table_base = table;
+ Handle<HashTable<ObjectHashTableShape, Object*> > table_base = table;
CALL_HEAP_FUNCTION(table_base->GetIsolate(),
table_base->EnsureCapacity(n, *key, pretenure),
ObjectHashTable);
@@ -15864,7 +15787,7 @@
Handle<ObjectHashTable> ObjectHashTable::Shrink(
Handle<ObjectHashTable> table, Handle<Object> key) {
- Handle<HashTable<ObjectHashTableShape<2>, Object*> > table_base = table;
+ Handle<HashTable<ObjectHashTableShape, Object*> > table_base = table;
CALL_HEAP_FUNCTION(table_base->GetIsolate(),
table_base->Shrink(*key),
ObjectHashTable);
@@ -15982,11 +15905,11 @@
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));
+ Handle<FixedArray> backing_store = isolate->factory()->NewFixedArray(
+ kHashTableStartIndex + num_buckets + (capacity * kEntrySize),
pretenure);
+ backing_store->set_map_no_write_barrier(
+ isolate->heap()->ordered_hash_table_map());
+ Handle<Derived> table = Handle<Derived>::cast(backing_store);
for (int i = 0; i < num_buckets; ++i) {
table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound));
}
=======================================
--- /branches/bleeding_edge/src/objects.h Tue Apr 8 16:31:57 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Tue Apr 8 20:06:35 2014 UTC
@@ -1076,7 +1076,8 @@
V(Cell) \
V(PropertyCell) \
V(ObjectHashTable) \
- V(WeakHashTable)
+ V(WeakHashTable) \
+ V(OrderedHashTable)
#define ERROR_MESSAGES_LIST(V) \
@@ -3779,7 +3780,6 @@
void Rehash(Key key);
protected:
- friend class ObjectHashSet;
friend class ObjectHashTable;
// Find the entry at which to insert element with the given key that
@@ -4210,7 +4210,6 @@
};
-template <int entrysize>
class ObjectHashTableShape : public BaseShape<Object*> {
public:
static inline bool IsMatch(Object* key, Object* other);
@@ -4219,45 +4218,13 @@
MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap,
Object* key);
static const int kPrefixSize = 0;
- static const int kEntrySize = entrysize;
-};
-
-
-// ObjectHashSet holds keys that are arbitrary objects by using the
identity
-// hash of the key for hashing purposes.
-class ObjectHashSet: public HashTable<ObjectHashTableShape<1>, Object*> {
- public:
- static inline ObjectHashSet* cast(Object* obj) {
- ASSERT(obj->IsHashTable());
- return reinterpret_cast<ObjectHashSet*>(obj);
- }
-
- // Looks up whether the given key is part of this hash set.
- bool Contains(Object* key);
-
- static Handle<ObjectHashSet> EnsureCapacity(
- Handle<ObjectHashSet> table,
- int n,
- Handle<Object> key,
- PretenureFlag pretenure = NOT_TENURED);
-
- // Attempt to shrink hash table after removal of key.
- static Handle<ObjectHashSet> Shrink(Handle<ObjectHashSet> table,
- Handle<Object> key);
-
- // Adds the given key to this hash set.
- static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> table,
- Handle<Object> key);
-
- // Removes the given key from this hash set.
- static Handle<ObjectHashSet> Remove(Handle<ObjectHashSet> table,
- Handle<Object> key);
+ static const int kEntrySize = 2;
};
// ObjectHashTable maps keys that are arbitrary objects to object values by
// using the identity hash of the key for hashing purposes.
-class ObjectHashTable: public HashTable<ObjectHashTableShape<2>, Object*> {
+class ObjectHashTable: public HashTable<ObjectHashTableShape, Object*> {
public:
static inline ObjectHashTable* cast(Object* obj) {
ASSERT(obj->IsHashTable());
@@ -4329,7 +4296,7 @@
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.
+ // to add at least one new element.
static Handle<Derived> EnsureGrowable(Handle<Derived> table);
// Returns an OrderedHashTable (possibly |table|) that's shrunken
@@ -4420,7 +4387,7 @@
class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
public:
static OrderedHashSet* cast(Object* obj) {
- ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this
+ ASSERT(obj->IsOrderedHashTable());
return reinterpret_cast<OrderedHashSet*>(obj);
}
@@ -4435,7 +4402,7 @@
class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> {
public:
static OrderedHashMap* cast(Object* obj) {
- ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this
+ ASSERT(obj->IsOrderedHashTable());
return reinterpret_cast<OrderedHashMap*>(obj);
}
=======================================
--- /branches/bleeding_edge/src/runtime.cc Tue Apr 8 09:49:49 2014 UTC
+++ /branches/bleeding_edge/src/runtime.cc Tue Apr 8 20:06:35 2014 UTC
@@ -1507,7 +1507,7 @@
HandleScope scope(isolate);
ASSERT(args.length() == 1);
CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
- Handle<ObjectHashSet> table = isolate->factory()->NewObjectHashSet(0);
+ Handle<OrderedHashSet> table = isolate->factory()->NewOrderedHashSet();
holder->set_table(*table);
return *holder;
}
@@ -1518,8 +1518,8 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
Handle<Object> key(args[1], isolate);
- Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
- table = ObjectHashSet::Add(table, key);
+ Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
+ table = OrderedHashSet::Add(table, key);
holder->set_table(*table);
return isolate->heap()->undefined_value();
}
@@ -1530,7 +1530,7 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
Handle<Object> key(args[1], isolate);
- Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
+ Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
return isolate->heap()->ToBoolean(table->Contains(*key));
}
@@ -1540,8 +1540,8 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
Handle<Object> key(args[1], isolate);
- Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
- table = ObjectHashSet::Remove(table, key);
+ Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
+ table = OrderedHashSet::Remove(table, key);
holder->set_table(*table);
return isolate->heap()->undefined_value();
}
@@ -1551,7 +1551,7 @@
HandleScope scope(isolate);
ASSERT(args.length() == 1);
CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
- Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
+ Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
return Smi::FromInt(table->NumberOfElements());
}
@@ -1560,7 +1560,7 @@
HandleScope scope(isolate);
ASSERT(args.length() == 1);
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
- Handle<ObjectHashTable> table =
isolate->factory()->NewObjectHashTable(0);
+ Handle<OrderedHashMap> table = isolate->factory()->NewOrderedHashMap();
holder->set_table(*table);
return *holder;
}
@@ -1571,7 +1571,7 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
- Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
+ Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
Handle<Object> lookup(table->Lookup(*key), isolate);
return lookup->IsTheHole() ? isolate->heap()->undefined_value() :
*lookup;
}
@@ -1582,7 +1582,7 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
- Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
+ Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
Handle<Object> lookup(table->Lookup(*key), isolate);
return isolate->heap()->ToBoolean(!lookup->IsTheHole());
}
@@ -1593,10 +1593,10 @@
ASSERT(args.length() == 2);
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
- Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
+ Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
Handle<Object> lookup(table->Lookup(*key), isolate);
- Handle<ObjectHashTable> new_table =
- ObjectHashTable::Put(table, key,
isolate->factory()->the_hole_value());
+ Handle<OrderedHashMap> new_table =
+ OrderedHashMap::Put(table, key,
isolate->factory()->the_hole_value());
holder->set_table(*new_table);
return isolate->heap()->ToBoolean(!lookup->IsTheHole());
}
@@ -1608,8 +1608,8 @@
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
CONVERT_ARG_HANDLE_CHECKED(Object, value, 2);
- Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
- Handle<ObjectHashTable> new_table = ObjectHashTable::Put(table, key,
value);
+ Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
+ Handle<OrderedHashMap> new_table = OrderedHashMap::Put(table, key,
value);
holder->set_table(*new_table);
return isolate->heap()->undefined_value();
}
@@ -1619,7 +1619,7 @@
HandleScope scope(isolate);
ASSERT(args.length() == 1);
CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
- Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
+ Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
return Smi::FromInt(table->NumberOfElements());
}
=======================================
--- /branches/bleeding_edge/test/cctest/test-dictionary.cc Fri Apr 4
20:41:57 2014 UTC
+++ /branches/bleeding_edge/test/cctest/test-dictionary.cc Tue Apr 8
20:06:35 2014 UTC
@@ -201,7 +201,6 @@
LocalContext context;
v8::HandleScope scope(context->GetIsolate());
Isolate* isolate = CcTest::i_isolate();
- TestHashSetCausesGC(isolate->factory()->NewObjectHashSet(1));
TestHashSetCausesGC(isolate->factory()->NewOrderedHashSet());
}
#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.
