Reimplement Symbols using hash table template.

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 60 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;
   explicit HashTable(Array& data) : data_(data) {}
 
   RawArray* Release() {
     ASSERT(!data_.IsNull());
     RawArray* array = data_.raw();
     data_ = Array::null();
     return array;
   }
 
   ~HashTable() {
@@ skipping 285 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) {
+  static RawArray* New(intptr_t initial_capacity,
+                       Heap::Space space = Heap::kNew) {
     Table table(Array::Handle(Array::New(
-        Table::ArrayLengthForNumOccupied(initial_capacity))));
+        Table::ArrayLengthForNumOccupied(initial_capacity), space)));
     table.Initialize();
     return table.Release();
   }
 
   // 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 17 matching lines @@
 
   template<typename Table>
   static void EnsureLoadFactor(double low, double high, const Table& table) {
     double current = (1 + table.NumOccupied() + table.NumDeleted()) /
         static_cast<double>(table.NumEntries());
     if (low <= current && current < high) {
       return;
     }
     double target = (low + high) / 2.0;
     intptr_t new_capacity = (1 + table.NumOccupied()) / target;
-    Table new_table(Array::Handle(New<Table>(new_capacity)));
+    Table new_table(Array::Handle(New<Table>(
+        new_capacity,
+        table.data_.IsOld() ? Heap::kOld : Heap::kNew)));
     Copy(table, new_table);
     table.data_ = new_table.Release();
   }
 
   // Serializes a table by concatenating its entries as an array.
   template<typename Table>
   static RawArray* ToArray(const Table& table, bool include_payload) {
     const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1;
     Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size));
     typename Table::Iterator it(&table);
@@ skipping 21 matching lines @@
   explicit HashMap(Array& data) : BaseIterTable(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 {
-    HashTables::EnsureLoadFactor(0.0, 0.75, *this);
+    EnsureCapacity();
     intptr_t entry = -1;
     bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
     if (!present) {
       BaseIterTable::InsertKey(entry, key);
     }
     BaseIterTable::UpdatePayload(entry, 0, value);
     return present;
   }
   // Update the value of an existing key. Note that 'key' need not be an Object.
   template<typename Key>
   void UpdateValue(const Key& key, const Object& value) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     ASSERT(entry != -1);
     BaseIterTable::UpdatePayload(entry, 0, value);
   }
+  // If 'key' is not present, maps it to 'value_if_absent'. Returns the final
+  // value in the map.
+  RawObject* InsertOrGetValue(const Object& key,
+                              const Object& value_if_absent) const {
+    EnsureCapacity();
+    intptr_t entry = -1;
+    if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
+      BaseIterTable::InsertKey(entry, key);
+      BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
+      return value_if_absent.raw();
+    } else {
+      return BaseIterTable::GetPayload(entry, 0);
+    }
+  }
+  // Like InsertOrGetValue, but calls NewKey to allocate a key object if needed.
+  template<typename Key>
+  RawObject* InsertNewOrGetValue(const Key& key,
+                                 const Object& value_if_absent) const {
+    EnsureCapacity();
+    intptr_t entry = -1;
+    if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
+      Object& new_key = Object::Handle(
+          BaseIterTable::BaseTable::Traits::NewKey(key));
+      BaseIterTable::InsertKey(entry, new_key);
+      BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
+      return value_if_absent.raw();
+    } else {
+      return BaseIterTable::GetPayload(entry, 0);
+    }
+  }
 
   template<typename Key>
   bool Remove(const Key& key) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (entry == -1) {
       return false;
     } else {
       BaseIterTable::DeleteEntry(entry);
       return true;
     }
   }
+
+ protected:
+  void EnsureCapacity() const {
+    static const double kMaxLoadFactor = 0.75;
+    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(Array& data) : BaseMap(data) {}
 };
 
 
 template<typename KeyTraits>
 class EnumIndexHashMap : public HashMap<EnumIndexHashTable<KeyTraits, 1> > {
  public:
   typedef HashMap<EnumIndexHashTable<KeyTraits, 1> > BaseMap;
   explicit EnumIndexHashMap(Array& data) : BaseMap(data) {}
 };
 
 
 template<typename BaseIterTable>
 class HashSet : public BaseIterTable {
  public:
   explicit HashSet(Array& data) : BaseIterTable(data) {}
   bool Insert(const Object& key) {
-    HashTables::EnsureLoadFactor(0.0, 0.75, *this);
+    EnsureCapacity();
     intptr_t entry = -1;
     bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
     if (!present) {
       BaseIterTable::InsertKey(entry, key);
     }
     return present;
   }
+
+  // If 'key' is not present, insert and return it. Else, return the existing
+  // key in the set (useful for canonicalization).
+  RawObject* InsertOrGet(const Object& key) const {
+    EnsureCapacity();
+    intptr_t entry = -1;
+    if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
+      BaseIterTable::InsertKey(entry, key);
+      return key.raw();
+    } else {
+      return BaseIterTable::GetPayload(entry, 0);
+    }
+  }
+
+  // Like InsertOrGet, but calls NewKey to allocate a key object if needed.
+  template<typename Key>
+  RawObject* InsertNewOrGet(const Key& key) const {
+    EnsureCapacity();
+    intptr_t entry = -1;
+    if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
+      Object& new_key = Object::Handle(
+          BaseIterTable::BaseTable::Traits::NewKey(key));
+      BaseIterTable::InsertKey(entry, new_key);
+      return new_key.raw();
+    } else {
+      return BaseIterTable::GetKey(entry);
+    }
+  }
+
+  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::GetKey(entry);
+  }
+
   template<typename Key>
   bool Remove(const Key& key) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (entry == -1) {
       return false;
     } else {
       BaseIterTable::DeleteEntry(entry);
       return true;
     }
   }
+
+ protected:
+  void EnsureCapacity() const {
+    static const double kMaxLoadFactor = 0.75;
+    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(Array& data) : BaseSet(data) {}
 };
 
 
 template<typename KeyTraits>
 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet;
   explicit EnumIndexHashSet(Array& data) : BaseSet(data) {}
 };
 
 }  // namespace dart
 
 #endif  // VM_HASH_TABLE_H_