Remove some uses of STL map.

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>
-#include <vector>
-
 #include "platform/assert.h"
 #include "vm/object.h"
 
 namespace dart {
 
 // OVERVIEW:
 //
 // Hash maps and hash sets all use RawArray as backing storage. At the lowest
 // level is a generic open-addressing table that supports deletion.
 //  - HashTable
 // The next layer provides ordering and iteration functionality:
 //  - UnorderedHashTable
-//  - EnumIndexHashTable
 //  - LinkedListHashTable (TODO(koda): Implement.)
-// The utility class HashTables handles growth and conversion (e.g., converting
-// a compact EnumIndexHashTable to an iteration-efficient LinkedListHashTable).
+// The utility class HashTables handles growth and conversion.
 // The next layer fixes the payload size and provides a natural interface:
 //  - HashMap
 //  - HashSet
 // Combining either of these with an iteration strategy, we get the templates
 // intended for use outside this file:
 //  - UnorderedHashMap
-//  - EnumIndexHashMap
 //  - LinkedListHashMap
 //  - UnorderedHashSet
-//  - EnumIndexHashSet
 //  - LinkedListHashSet
 // Each of these can be finally specialized with KeyTraits to support any set of
 // lookup key types (e.g., look up a char* in a set of String objects), and
 // any equality and hash code computation.
 //
 // The classes all wrap an Array handle, and methods like HashSet::Insert can
 // trigger growth into a new RawArray, updating the handle. Debug mode asserts
 // that 'Release' was called once to access the final array before destruction.
 // NOTE: The handle returned by 'Release' is cleared by ~HashTable.
 //
@@ skipping 379 matching lines @@
 
    private:
     const UnorderedHashTable* table_;
     intptr_t entry_;
   };
 
   // No extra book-keeping needed for Initialize, InsertKey, DeleteEntry.
 };
 
 
-// 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(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));
-          enum_to_entry[enum_index] = i;
-        }
-      }
-      for (std::map<intptr_t, intptr_t>::iterator it = enum_to_entry.begin();
-           it != enum_to_entry.end();
-           ++it) {
-        entries_.push_back(it->second);
-      }
-    }
-    bool MoveNext() {
-      if (index_ < (static_cast<intptr_t>(entries_.size() - 1))) {
-        index_++;
-        return true;
-      }
-      return false;
-    }
-    intptr_t Current() {
-      return entries_[index_];
-    }
-
-   private:
-    intptr_t index_;
-    std::vector<intptr_t> entries_;
-  };
-
-  void Initialize() const {
-    BaseTable::Initialize();
-    BaseTable::SetSmiValueAt(kNextEnumIndex, 0);
-  }
-
-  void InsertKey(intptr_t entry, const Object& key) const {
-    BaseTable::InsertKey(entry, key);
-    BaseTable::SmiHandle() =
-        Smi::New(BaseTable::GetSmiValueAt(kNextEnumIndex));
-    BaseTable::UpdatePayload(entry, kPayloadSize, BaseTable::SmiHandle());
-    // TODO(koda): Handle possible Smi overflow from repeated insert/delete.
-    BaseTable::AdjustSmiValueAt(kNextEnumIndex, 1);
-  }
-
-  // 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(Thread::Current()->zone(), Array::New(
         Table::ArrayLengthForNumOccupied(initial_capacity), space));
     table.Initialize();
     return table.Release().raw();
@@ skipping 164 matching lines @@
  public:
   typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap;
   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(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(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();
@@ skipping 72 matching lines @@
   typedef HashSet<UnorderedHashTable<KeyTraits, 0> > BaseSet;
   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(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_