- Add a new constructor to the hash table classes that allow handles to be passed in instead of cre…

runtime/vm/hash_table.h

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_HASH_TABLE_H_
 #define VM_HASH_TABLE_H_
 
 // Temporarily used when sorting the indices in EnumIndexHashTable.
 // TODO(koda): Remove these dependencies before using in production.
 #include <map>
@@ skipping 67 matching lines @@
 // Parameters
 //  KeyTraits: defines static methods
 //    bool IsMatch(const Key& key, const Object& obj) and
 //    uword Hash(const Key& key) for any number of desired lookup key types.
 //  kPayloadSize: number of components of the payload in each entry.
 //  kMetaDataSize: number of elements reserved (e.g., for iteration order data).
 template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize>
 class HashTable : public ValueObject {
  public:
   typedef KeyTraits Traits;
+  // Uses the passed in handles for all handle operations.
+  // 'Release' must be called at the end to obtain the final table
+  // after potential growth/shrinkage.
+  HashTable(Object* key, Smi* index, Array* data)
+      : key_handle_(key),
+        smi_handle_(index),
+        data_(data),
+        released_data_(NULL) {}
   // Uses 'zone' for handle allocation. 'Release' must be called at the end
   // to obtain the final table after potential growth/shrinkage.
   HashTable(Zone* zone, RawArray* data)
-      : zone_(zone),
-        key_handle_(Object::Handle(zone_)),
-        smi_handle_(Smi::Handle(zone_)),
-        data_(&Array::Handle(zone_, data)),
+      : key_handle_(&Object::Handle(zone)),
+        smi_handle_(&Smi::Handle(zone)),
+        data_(&Array::Handle(zone, data)),
         released_data_(NULL) {}
-  // Like above, except uses current zone.
-  explicit HashTable(RawArray* data)
-      : zone_(Thread::Current()->zone()),
-        key_handle_(Object::Handle(zone_)),
-        smi_handle_(Smi::Handle(zone_)),
-        data_(&Array::Handle(zone_, data)),
-        released_data_(NULL) {
-    ASSERT(!data_->IsNull());
-  }
 
   // Returns the final table. The handle is cleared when this HashTable is
   // destroyed.
   Array& Release() {
     ASSERT(data_ != NULL);
     ASSERT(released_data_ == NULL);
     // Ensure that no methods are called after 'Release'.
     released_data_ = data_;
     data_ = NULL;
     return *released_data_;
@@ skipping 12 matching lines @@
   static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) {
     // The current invariant requires at least one unoccupied entry.
     // TODO(koda): Adjust if moving to quadratic probing.
     intptr_t num_entries = num_occupied + 1;
     return kFirstKeyIndex + (kEntrySize * num_entries);
   }
 
   // Initializes an empty table.
   void Initialize() const {
     ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
-    smi_handle_ = Smi::New(0);
-    data_->SetAt(kOccupiedEntriesIndex, smi_handle_);
-    data_->SetAt(kDeletedEntriesIndex, smi_handle_);
+    *smi_handle_ = Smi::New(0);
+    data_->SetAt(kOccupiedEntriesIndex, *smi_handle_);
+    data_->SetAt(kDeletedEntriesIndex, *smi_handle_);
 
 NOT_IN_PRODUCT(
-    data_->SetAt(kNumGrowsIndex, smi_handle_);
-    data_->SetAt(kNumLT5LookupsIndex, smi_handle_);
-    data_->SetAt(kNumLT25LookupsIndex, smi_handle_);
-    data_->SetAt(kNumGT25LookupsIndex, smi_handle_);
+    data_->SetAt(kNumGrowsIndex, *smi_handle_);
+    data_->SetAt(kNumLT5LookupsIndex, *smi_handle_);
+    data_->SetAt(kNumLT25LookupsIndex, *smi_handle_);
+    data_->SetAt(kNumGT25LookupsIndex, *smi_handle_);
 )  // !PRODUCT
 
     for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
       data_->SetAt(i, Object::sentinel());
     }
   }
 
   // Returns whether 'key' matches any key in the table.
   template<typename Key>
   bool ContainsKey(const Key& key) const {
     return FindKey(key) != -1;
   }
 
   // Returns the entry that matches 'key', or -1 if none exists.
   template<typename Key>
   intptr_t FindKey(const Key& key) const {
     const intptr_t num_entries = NumEntries();
     ASSERT(NumOccupied() < num_entries);
     // TODO(koda): Add salt.
     NOT_IN_PRODUCT(intptr_t collisions = 0;)
     uword hash = KeyTraits::Hash(key);
     intptr_t probe = hash % num_entries;
     // TODO(koda): Consider quadratic probing.
     while (true) {
       if (IsUnused(probe)) {
         NOT_IN_PRODUCT(UpdateCollisions(collisions);)
         return -1;
       } else if (!IsDeleted(probe)) {
-        key_handle_ = GetKey(probe);
-        if (KeyTraits::IsMatch(key, key_handle_)) {
+        *key_handle_ = GetKey(probe);
+        if (KeyTraits::IsMatch(key, *key_handle_)) {
           NOT_IN_PRODUCT(UpdateCollisions(collisions);)
           return probe;
         }
         NOT_IN_PRODUCT(collisions += 1;)
       }
       // Advance probe.
       probe++;
       probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
@@ skipping 17 matching lines @@
     while (true) {
       if (IsUnused(probe)) {
         *entry = (deleted != -1) ? deleted : probe;
         NOT_IN_PRODUCT(UpdateCollisions(collisions);)
         return false;
       } else if (IsDeleted(probe)) {
         if (deleted == -1) {
           deleted = probe;
         }
       } else {
-        key_handle_ = GetKey(probe);
-        if (KeyTraits::IsMatch(key, key_handle_)) {
+        *key_handle_ = GetKey(probe);
+        if (KeyTraits::IsMatch(key, *key_handle_)) {
           *entry = probe;
           NOT_IN_PRODUCT(UpdateCollisions(collisions);)
           return true;
         }
         NOT_IN_PRODUCT(collisions += 1;)
       }
       // Advance probe.
       probe++;
       probe = (probe == num_entries) ? 0 : probe;
     }
@@ skipping 57 matching lines @@
   intptr_t NumUnused() const {
     return NumEntries() - NumOccupied() - NumDeleted();
   }
   intptr_t NumOccupied() const {
     return GetSmiValueAt(kOccupiedEntriesIndex);
   }
   intptr_t NumDeleted() const {
     return GetSmiValueAt(kDeletedEntriesIndex);
   }
   Object& KeyHandle() const {
-    return key_handle_;
+    return *key_handle_;
   }
   Smi& SmiHandle() const {
-    return smi_handle_;
+    return *smi_handle_;
   }
 
 NOT_IN_PRODUCT(
   intptr_t NumGrows() const {
     return GetSmiValueAt(kNumGrowsIndex);
   }
   intptr_t NumLT5Collisions() const {
     return GetSmiValueAt(kNumLT5LookupsIndex);
   }
   intptr_t NumLT25Collisions() const {
@@ skipping 63 matching lines @@
   RawObject* InternalGetKey(intptr_t entry) const {
     return data_->At(KeyIndex(entry));
   }
 
   void InternalSetKey(intptr_t entry, const Object& key) const {
     data_->SetAt(KeyIndex(entry), key);
   }
 
   intptr_t GetSmiValueAt(intptr_t index) const {
     ASSERT(!data_->IsNull());
-    ASSERT(Object::Handle(zone(), data_->At(index)).IsSmi());
+    ASSERT(!data_->At(index)->IsHeapObject());
     return Smi::Value(Smi::RawCast(data_->At(index)));
   }
 
   void SetSmiValueAt(intptr_t index, intptr_t value) const {
-    smi_handle_ = Smi::New(value);
-    data_->SetAt(index, smi_handle_);
+    *smi_handle_ = Smi::New(value);
+    data_->SetAt(index, *smi_handle_);
   }
 
   void AdjustSmiValueAt(intptr_t index, intptr_t delta) const {
     SetSmiValueAt(index, (GetSmiValueAt(index) + delta));
   }
 
-  Zone* zone() const { return zone_; }
-
-  Zone* zone_;
-  Object& key_handle_;
-  Smi& smi_handle_;
+  Object* key_handle_;
+  Smi* smi_handle_;
   // Exactly one of these is non-NULL, depending on whether Release was called.
   Array* data_;
   Array* released_data_;
 
   friend class HashTables;
 };
 
 
 // Table with unspecified iteration order. No payload overhead or metadata.
 template<typename KeyTraits, intptr_t kUserPayloadSize>
 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> {
  public:
   typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable;
   static const intptr_t kPayloadSize = kUserPayloadSize;
-  explicit UnorderedHashTable(RawArray* data) : BaseTable(data) {}
-  UnorderedHashTable(Zone* zone, RawArray* data)
-      : BaseTable(zone, data) {}
+  explicit UnorderedHashTable(RawArray* data)
+      : BaseTable(Thread::Current()->zone(), data) {}
+  UnorderedHashTable(Zone* zone, RawArray* data) : BaseTable(zone, data) {}
+  UnorderedHashTable(Object* key, Smi* value, Array* data)
+      : BaseTable(key, value, data) {}
   // Note: Does not check for concurrent modification.
   class Iterator {
    public:
     explicit Iterator(const UnorderedHashTable* table)
         : table_(table), entry_(-1) {}
     bool MoveNext() {
       while (entry_ < (table_->NumEntries() - 1)) {
         ++entry_;
         if (table_->IsOccupied(entry_)) {
           return true;
@@ skipping 16 matching lines @@
 
 // Table with insertion order, using one payload component for the enumeration
 // index, and one metadata element for the next enumeration index.
 template<typename KeyTraits, intptr_t kUserPayloadSize>
 class EnumIndexHashTable
     : public HashTable<KeyTraits, kUserPayloadSize + 1, 1> {
  public:
   typedef HashTable<KeyTraits, kUserPayloadSize + 1, 1> BaseTable;
   static const intptr_t kPayloadSize = kUserPayloadSize;
   static const intptr_t kNextEnumIndex = BaseTable::kMetaDataIndex;
+  EnumIndexHashTable(Object* key, Smi* value, Array* data)
+      : BaseTable(key, value, data) {}
   EnumIndexHashTable(Zone* zone, RawArray* data)
       : BaseTable(zone, data) {}
-  explicit EnumIndexHashTable(RawArray* data) : BaseTable(data) {}
+  explicit EnumIndexHashTable(RawArray* data)
+      : BaseTable(Thread::Current()->zone(), data) {}
   // Note: Does not check for concurrent modification.
   class Iterator {
    public:
     explicit Iterator(const EnumIndexHashTable* table) : index_(-1) {
       // TODO(koda): Use GrowableArray after adding stateful comparator support.
       std::map<intptr_t, intptr_t> enum_to_entry;
       for (intptr_t i = 0; i < table->NumEntries(); ++i) {
         if (table->IsOccupied(i)) {
           intptr_t enum_index =
               table->GetSmiValueAt(table->PayloadIndex(i, kPayloadSize));
@@ skipping 39 matching lines @@
   // No extra book-keeping needed for DeleteEntry.
 };
 
 
 class HashTables : public AllStatic {
  public:
   // Allocates and initializes a table.
   template<typename Table>
   static RawArray* New(intptr_t initial_capacity,
                        Heap::Space space = Heap::kNew) {
-    Table table(Array::New(
+    Table table(Thread::Current()->zone(), Array::New(
         Table::ArrayLengthForNumOccupied(initial_capacity), space));
     table.Initialize();
     return table.Release().raw();
   }
 
   template<typename Table>
   static RawArray* New(const Array& array) {
-    Table table(array.raw());
+    Table table(Thread::Current()->zone(), array.raw());
     table.Initialize();
     return table.Release().raw();
   }
 
   // Clears 'to' and inserts all elements from 'from', in iteration order.
   // The tables must have the same user payload size.
   template<typename From, typename To>
   static void Copy(const From& from, const To& to) {
     COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize);
     to.Initialize();
@@ skipping 52 matching lines @@
       }
     }
     return result.raw();
   }
 };
 
 
 template<typename BaseIterTable>
 class HashMap : public BaseIterTable {
  public:
-  explicit HashMap(RawArray* data) : BaseIterTable(data) {}
+  explicit HashMap(RawArray* data)
+      : BaseIterTable(Thread::Current()->zone(), data) {}
   HashMap(Zone* zone, RawArray* data) : BaseIterTable(zone, data) {}
+  HashMap(Object* key, Smi* value, Array* data)
+      : BaseIterTable(key, value, data) {}
   template<typename Key>
   RawObject* GetOrNull(const Key& key, bool* present = NULL) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (present != NULL) {
       *present = (entry != -1);
     }
     return (entry == -1) ? Object::null() : BaseIterTable::GetPayload(entry, 0);
   }
   bool UpdateOrInsert(const Object& key, const Object& value) const {
     EnsureCapacity();
@@ skipping 64 matching lines @@
     // We currently never shrink.
     HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this);
   }
 };
 
 
 template<typename KeyTraits>
 class UnorderedHashMap : public HashMap<UnorderedHashTable<KeyTraits, 1> > {
  public:
   typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap;
-  explicit UnorderedHashMap(RawArray* data) : BaseMap(data) {}
+  explicit UnorderedHashMap(RawArray* data)
+      : BaseMap(Thread::Current()->zone(), data) {}
   UnorderedHashMap(Zone* zone, RawArray* data) : BaseMap(zone, data) {}
+  UnorderedHashMap(Object* key, Smi* value, Array* data)
+      : BaseMap(key, value, data) {}
 };
 
 
 template<typename KeyTraits>
 class EnumIndexHashMap : public HashMap<EnumIndexHashTable<KeyTraits, 1> > {
  public:
   typedef HashMap<EnumIndexHashTable<KeyTraits, 1> > BaseMap;
-  explicit EnumIndexHashMap(RawArray* data) : BaseMap(data) {}
+  explicit EnumIndexHashMap(RawArray* data)
+      : BaseMap(Thread::Current()->zone(), data) {}
   EnumIndexHashMap(Zone* zone, RawArray* data) : BaseMap(zone, data) {}
+  EnumIndexHashMap(Object* key, Smi* value, Array* data)
+      : BaseMap(key, value, data) {}
 };
 
 
 template<typename BaseIterTable>
 class HashSet : public BaseIterTable {
  public:
-  explicit HashSet(RawArray* data) : BaseIterTable(data) {}
+  explicit HashSet(RawArray* data)
+      : BaseIterTable(Thread::Current()->zone(), data) {}
   HashSet(Zone* zone, RawArray* data) : BaseIterTable(zone, data) {}
+  HashSet(Object* key, Smi* value, Array* data)
+      : BaseIterTable(key, value, data) {}
   bool Insert(const Object& key) {
     EnsureCapacity();
     intptr_t entry = -1;
     bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
     if (!present) {
       BaseIterTable::InsertKey(entry, key);
     }
     return present;
   }
 
@@ skipping 55 matching lines @@
     // We currently never shrink.
     HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this);
   }
 };
 
 
 template<typename KeyTraits>
 class UnorderedHashSet : public HashSet<UnorderedHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<UnorderedHashTable<KeyTraits, 0> > BaseSet;
-  explicit UnorderedHashSet(RawArray* data) : BaseSet(data) {
+  explicit UnorderedHashSet(RawArray* data)
+      : BaseSet(Thread::Current()->zone(), data) {
     ASSERT(data != Array::null());
   }
   UnorderedHashSet(Zone* zone, RawArray* data) : BaseSet(zone, data) {}
+  UnorderedHashSet(Object* key, Smi* value, Array* data)
+      : BaseSet(key, value, data) {}
 };
 
 
 template<typename KeyTraits>
 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet;
-  explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {}
+  explicit EnumIndexHashSet(RawArray* data)
+      : BaseSet(Thread::Current()->zone(), data) {}
   EnumIndexHashSet(Zone* zone, RawArray* data) : BaseSet(zone, data) {}
+  EnumIndexHashSet(Object* key, Smi* value, Array* data)
+      : BaseSet(key, value, data) {}
 };
 
 }  // namespace dart
 
 #endif  // VM_HASH_TABLE_H_