OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 #ifndef VM_HASH_MAP_H_ |
| 6 #define VM_HASH_MAP_H_ |
| 7 |
| 8 namespace dart { |
| 9 |
| 10 template <typename T> |
| 11 class DirectChainedHashMap: public ValueObject { |
| 12 public: |
| 13 DirectChainedHashMap() : array_size_(0), |
| 14 lists_size_(0), |
| 15 count_(0), |
| 16 array_(NULL), |
| 17 lists_(NULL), |
| 18 free_list_head_(kNil) { |
| 19 ResizeLists(kInitialSize); |
| 20 Resize(kInitialSize); |
| 21 } |
| 22 |
| 23 void Insert(T value); |
| 24 |
| 25 T Lookup(T value) const; |
| 26 |
| 27 bool IsEmpty() const { return count_ == 0; } |
| 28 |
| 29 private: |
| 30 // A linked list of T values. Stored in arrays. |
| 31 struct HashMapListElement { |
| 32 T value; |
| 33 intptr_t next; // Index in the array of the next list element. |
| 34 }; |
| 35 static const intptr_t kNil = -1; // The end of a linked list |
| 36 |
| 37 // Must be a power of 2. |
| 38 static const intptr_t kInitialSize = 16; |
| 39 |
| 40 void Resize(intptr_t new_size); |
| 41 void ResizeLists(intptr_t new_size); |
| 42 uword Bound(uword value) const { return value & (array_size_ - 1); } |
| 43 |
| 44 intptr_t array_size_; |
| 45 intptr_t lists_size_; |
| 46 intptr_t count_; // The number of values stored in the HashMap. |
| 47 HashMapListElement* array_; // Primary store - contains the first value |
| 48 // with a given hash. Colliding elements are stored in linked lists. |
| 49 HashMapListElement* lists_; // The linked lists containing hash collisions. |
| 50 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. |
| 51 |
| 52 DISALLOW_COPY_AND_ASSIGN(DirectChainedHashMap); |
| 53 }; |
| 54 |
| 55 |
| 56 template <typename T> |
| 57 T DirectChainedHashMap<T>::Lookup(T value) const { |
| 58 uword hash = static_cast<uword>(value->Hashcode()); |
| 59 uword pos = Bound(hash); |
| 60 if (array_[pos].value != NULL) { |
| 61 if (array_[pos].value->Equals(value)) return array_[pos].value; |
| 62 intptr_t next = array_[pos].next; |
| 63 while (next != kNil) { |
| 64 if (lists_[next].value->Equals(value)) return lists_[next].value; |
| 65 next = lists_[next].next; |
| 66 } |
| 67 } |
| 68 return NULL; |
| 69 } |
| 70 |
| 71 |
| 72 template <typename T> |
| 73 void DirectChainedHashMap<T>::Resize(intptr_t new_size) { |
| 74 ASSERT(new_size > count_); |
| 75 // Hashing the values into the new array has no more collisions than in the |
| 76 // old hash map, so we can use the existing lists_ array, if we are careful. |
| 77 |
| 78 // Make sure we have at least one free element. |
| 79 if (free_list_head_ == kNil) { |
| 80 ResizeLists(lists_size_ << 1); |
| 81 } |
| 82 |
| 83 HashMapListElement* new_array = |
| 84 Isolate::Current()->current_zone()->Alloc<HashMapListElement>(new_size); |
| 85 memset(new_array, 0, sizeof(HashMapListElement) * new_size); |
| 86 |
| 87 HashMapListElement* old_array = array_; |
| 88 intptr_t old_size = array_size_; |
| 89 |
| 90 intptr_t old_count = count_; |
| 91 count_ = 0; |
| 92 array_size_ = new_size; |
| 93 array_ = new_array; |
| 94 |
| 95 if (old_array != NULL) { |
| 96 // Iterate over all the elements in lists, rehashing them. |
| 97 for (intptr_t i = 0; i < old_size; ++i) { |
| 98 if (old_array[i].value != NULL) { |
| 99 intptr_t current = old_array[i].next; |
| 100 while (current != kNil) { |
| 101 Insert(lists_[current].value); |
| 102 intptr_t next = lists_[current].next; |
| 103 lists_[current].next = free_list_head_; |
| 104 free_list_head_ = current; |
| 105 current = next; |
| 106 } |
| 107 // Rehash the directly stored value. |
| 108 Insert(old_array[i].value); |
| 109 } |
| 110 } |
| 111 } |
| 112 USE(old_count); |
| 113 ASSERT(count_ == old_count); |
| 114 } |
| 115 |
| 116 |
| 117 template <typename T> |
| 118 void DirectChainedHashMap<T>::ResizeLists(intptr_t new_size) { |
| 119 ASSERT(new_size > lists_size_); |
| 120 |
| 121 HashMapListElement* new_lists = |
| 122 Isolate::Current()->current_zone()-> |
| 123 Alloc<HashMapListElement>(new_size); |
| 124 memset(new_lists, 0, sizeof(HashMapListElement) * new_size); |
| 125 |
| 126 HashMapListElement* old_lists = lists_; |
| 127 intptr_t old_size = lists_size_; |
| 128 |
| 129 lists_size_ = new_size; |
| 130 lists_ = new_lists; |
| 131 |
| 132 if (old_lists != NULL) { |
| 133 memmove(lists_, old_lists, old_size * sizeof(HashMapListElement)); |
| 134 } |
| 135 for (intptr_t i = old_size; i < lists_size_; ++i) { |
| 136 lists_[i].next = free_list_head_; |
| 137 free_list_head_ = i; |
| 138 } |
| 139 } |
| 140 |
| 141 |
| 142 template <typename T> |
| 143 void DirectChainedHashMap<T>::Insert(T value) { |
| 144 ASSERT(value != NULL); |
| 145 // Resizing when half of the hashtable is filled up. |
| 146 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1); |
| 147 ASSERT(count_ < array_size_); |
| 148 count_++; |
| 149 uword pos = Bound(static_cast<uword>(value->Hashcode())); |
| 150 if (array_[pos].value == NULL) { |
| 151 array_[pos].value = value; |
| 152 array_[pos].next = kNil; |
| 153 } else { |
| 154 if (free_list_head_ == kNil) { |
| 155 ResizeLists(lists_size_ << 1); |
| 156 } |
| 157 intptr_t new_element_pos = free_list_head_; |
| 158 ASSERT(new_element_pos != kNil); |
| 159 free_list_head_ = lists_[free_list_head_].next; |
| 160 lists_[new_element_pos].value = value; |
| 161 lists_[new_element_pos].next = array_[pos].next; |
| 162 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); |
| 163 array_[pos].next = new_element_pos; |
| 164 } |
| 165 } |
| 166 |
| 167 } // namespace dart |
| 168 |
| 169 #endif // VM_HASH_MAP_H_ |
OLD | NEW |