Allow bound check elimination to eliminate checks when both array length and index boundaries are e…

runtime/vm/hash_map.h

Index: runtime/vm/hash_map.h
diff --git a/runtime/vm/hash_map.h b/runtime/vm/hash_map.h
index 0c41f1221c8873d3f5d8269a113f53e769587e92..420c05d26f604793840755f47c50ef28c8f30355 100644
--- a/runtime/vm/hash_map.h
+++ b/runtime/vm/hash_map.h
@@ -7,7 +7,7 @@
 
 namespace dart {
 
-template <typename T>
+template <typename KeyValueTrait>
 class DirectChainedHashMap: public ValueObject {
  public:
   DirectChainedHashMap() : array_size_(0),
@@ -22,16 +22,16 @@ class DirectChainedHashMap: public ValueObject {
 
   DirectChainedHashMap(const DirectChainedHashMap& other);
 
-  void Insert(T value);
+  void Insert(typename KeyValueTrait::Pair kv);
 
-  T Lookup(T value) const;
+  typename KeyValueTrait::Value Lookup(typename KeyValueTrait::Key key) const;
 
   bool IsEmpty() const { return count_ == 0; }
 
  private:
   // A linked list of T values.  Stored in arrays.
   struct HashMapListElement {
-    T value;
+    typename KeyValueTrait::Pair kv;
     intptr_t next;  // Index in the array of the next list element.
   };
   static const intptr_t kNil = -1;  // The end of a linked list
@@ -53,15 +53,22 @@ class DirectChainedHashMap: public ValueObject {
 };
 
 
-template <typename T>
-T DirectChainedHashMap<T>::Lookup(T value) const {
-  uword hash = static_cast<uword>(value->Hashcode());
+template <typename KeyValueTrait>
+typename KeyValueTrait::Value
+    DirectChainedHashMap<KeyValueTrait>::
+        Lookup(typename KeyValueTrait::Key key) const {
+  uword hash = static_cast<uword>(KeyValueTrait::Hashcode(key));
   uword pos = Bound(hash);
-  if (array_[pos].value != NULL) {
-    if (array_[pos].value->Equals(value)) return array_[pos].value;
+  if (KeyValueTrait::ValueOf(array_[pos].kv) != NULL) {
+    if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) {
+      return KeyValueTrait::ValueOf(array_[pos].kv);
+    }
+
     intptr_t next = array_[pos].next;
     while (next != kNil) {
-      if (lists_[next].value->Equals(value)) return lists_[next].value;
+      if (KeyValueTrait::IsKeyEqual(lists_[next].kv, key)) {
+        return KeyValueTrait::ValueOf(lists_[next].kv);
+      }
       next = lists_[next].next;
     }
   }
@@ -85,8 +92,8 @@ DirectChainedHashMap<T>::DirectChainedHashMap(const DirectChainedHashMap& other)
 }
 
 
-template <typename T>
-void DirectChainedHashMap<T>::Resize(intptr_t new_size) {
+template <typename KeyValueTrait>
+void DirectChainedHashMap<KeyValueTrait>::Resize(intptr_t new_size) {
   ASSERT(new_size > count_);
   // Hashing the values into the new array has no more collisions than in the
   // old hash map, so we can use the existing lists_ array, if we are careful.
@@ -111,17 +118,17 @@ void DirectChainedHashMap<T>::Resize(intptr_t new_size) {
   if (old_array != NULL) {
     // Iterate over all the elements in lists, rehashing them.
     for (intptr_t i = 0; i < old_size; ++i) {
-      if (old_array[i].value != NULL) {
+      if (KeyValueTrait::ValueOf(old_array[i].kv) != NULL) {
         intptr_t current = old_array[i].next;
         while (current != kNil) {
-          Insert(lists_[current].value);
+          Insert(lists_[current].kv);
           intptr_t next = lists_[current].next;
           lists_[current].next = free_list_head_;
           free_list_head_ = current;
           current = next;
         }
         // Rehash the directly stored value.
-        Insert(old_array[i].value);
+        Insert(old_array[i].kv);
       }
     }
   }
@@ -155,16 +162,18 @@ void DirectChainedHashMap<T>::ResizeLists(intptr_t new_size) {
 }
 
 
-template <typename T>
-void DirectChainedHashMap<T>::Insert(T value) {
-  ASSERT(value != NULL);
+template <typename KeyValueTrait>
+void DirectChainedHashMap<KeyValueTrait>::
+    Insert(typename KeyValueTrait::Pair kv) {
+  ASSERT(KeyValueTrait::ValueOf(kv) != NULL);
   // Resizing when half of the hashtable is filled up.
   if (count_ >= array_size_ >> 1) Resize(array_size_ << 1);
   ASSERT(count_ < array_size_);
   count_++;
-  uword pos = Bound(static_cast<uword>(value->Hashcode()));
-  if (array_[pos].value == NULL) {
-    array_[pos].value = value;
+  uword pos = Bound(
+      static_cast<uword>(KeyValueTrait::Hashcode(KeyValueTrait::KeyOf(kv))));
+  if (KeyValueTrait::ValueOf(array_[pos].kv) == NULL) {
+    array_[pos].kv = kv;
     array_[pos].next = kNil;
   } else {
     if (free_list_head_ == kNil) {
@@ -173,13 +182,39 @@ void DirectChainedHashMap<T>::Insert(T value) {
     intptr_t new_element_pos = free_list_head_;
     ASSERT(new_element_pos != kNil);
     free_list_head_ = lists_[free_list_head_].next;
-    lists_[new_element_pos].value = value;
+    lists_[new_element_pos].kv = kv;
     lists_[new_element_pos].next = array_[pos].next;
-    ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
+    ASSERT(array_[pos].next == kNil ||
+           KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != NULL);
     array_[pos].next = new_element_pos;
   }
 }
 
+
+template<typename T>
+class PointerKeyValueTrait {
+ public:
+  typedef T* Value;
+  typedef T* Key;
+  typedef T* Pair;
+
+  static Key KeyOf(Pair p) {
+    return p;
+  }
+
+  static Value ValueOf(Pair p) {

[Florian Schneider, 2012/10/30 15:31:39]

for naming consistency use either "Pair kv" or "Pair p" in all places.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+    return p;
+  }
+
+  static inline intptr_t Hashcode(Key key) {
+    return key->Hashcode();
+  }
+
+  static inline intptr_t IsKeyEqual(Pair kv, Key key) {

[Florian Schneider, 2012/10/30 15:31:39]

bool IsKeyEqual?

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+    return kv->Equals(key);
+  }
+};
+
 }  // namespace dart
 
 #endif  // VM_HASH_MAP_H_