Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(847)

Unified Diff: src/objects.h

Issue 220293002: OrderedHashTable implementation with Set and Map interfaces (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Patch for landing Created 6 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/factory.cc ('k') | src/objects.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index c4d3f251c318173946ab614ff661c3da679eb6fa..33375763cb73a8e4d09a7096f3a761bd1d46fc1e 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -92,6 +92,9 @@
// - CompilationCacheTable
// - CodeCacheHashTable
// - MapCache
+// - OrderedHashTable
+// - OrderedHashSet
+// - OrderedHashMap
// - Context
// - JSFunctionResultCache
// - ScopeInfo
@@ -4249,6 +4252,163 @@ class ObjectHashTable: public HashTable<ObjectHashTableShape<2>, Object*> {
};
+// 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
arv (Not doing code reviews) 2014/04/07 00:01:21 ES6 Map/Set uses SameValueZero (which treats -0 an
+// 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:
« no previous file with comments | « src/factory.cc ('k') | src/objects.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698