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 RUNTIME_VM_HASH_MAP_H_
6#define RUNTIME_VM_HASH_MAP_H_
7
8#include "vm/growable_array.h" // For Malloc, EmptyBase
9#include "vm/hash.h"
10#include "vm/zone.h"
11
12namespace dart {
13
14template <typename KeyValueTrait, typename B, typename Allocator = Zone>
15class BaseDirectChainedHashMap : public B {
16 public:
17 explicit BaseDirectChainedHashMap(Allocator* allocator)
18 : array_size_(0),
19 lists_size_(0),
20 count_(0),
21 array_(NULL),
22 lists_(NULL),
23 free_list_head_(kNil),
24 allocator_(allocator) {
25 ResizeLists(kInitialSize);
26 Resize(kInitialSize);
27 }
28
29 BaseDirectChainedHashMap(const BaseDirectChainedHashMap& other);
30
31 intptr_t Length() const { return count_; }
32
33 virtual ~BaseDirectChainedHashMap() {
34 allocator_->template Free<HashMapListElement>(array_, array_size_);
35 allocator_->template Free<HashMapListElement>(lists_, lists_size_);
36 }
37
38 // Assumes that no existing pair in the map has a key equal to [kv.key].
39 void Insert(typename KeyValueTrait::Pair kv);
40 bool Remove(typename KeyValueTrait::Key key);
41
42 // If a pair already exists in the map with an equal key, replace that pair
43 // with this one. Otherwise, insert the pair as a new entry.
44 //
45 // Note: Insert operates in constant time, while Update must walk the chained
46 // entries for a given hash value, checking keys for equality. However, if
47 // multiple value updates are needed for the same key, only using Update
48 // guarantees constant space usage whereas Insert does not.
49 void Update(typename KeyValueTrait::Pair kv);
50
51 typename KeyValueTrait::Value LookupValue(
52 typename KeyValueTrait::Key key) const;
53
54 typename KeyValueTrait::Pair* Lookup(typename KeyValueTrait::Key key) const;
55 bool HasKey(typename KeyValueTrait::Key key) const {
56 return Lookup(key) != NULL;
57 }
58
59 intptr_t Size() const { return count_; }
60 bool IsEmpty() const { return count_ == 0; }
61
62 virtual void Clear() {
63 if (!IsEmpty()) {
64 count_ = 0;
65 InitArray(array_, array_size_);
66 InitArray(lists_, lists_size_);
67 lists_[0].next = kNil;
68 for (intptr_t i = 1; i < lists_size_; ++i) {
69 lists_[i].next = i - 1;
70 }
71 free_list_head_ = lists_size_ - 1;
72 }
73 }
74
75 class Iterator {
76 public:
77 typename KeyValueTrait::Pair* Next();
78
79 void Reset() {
80 array_index_ = 0;
81 list_index_ = kNil;
82 }
83
84 private:
85 explicit Iterator(const BaseDirectChainedHashMap& map)
86 : map_(map), array_index_(0), list_index_(kNil) {}
87
88 const BaseDirectChainedHashMap& map_;
89 intptr_t array_index_;
90 intptr_t list_index_;
91
92 template <typename T, typename Bs, typename A>
93 friend class BaseDirectChainedHashMap;
94 };
95
96 Iterator GetIterator() const { return Iterator(*this); }
97
98 protected:
99 // A linked list of T values. Stored in arrays.
100 struct HashMapListElement {
101 HashMapListElement() : kv(), next(kNil) {}
102 typename KeyValueTrait::Pair kv;
103 intptr_t next; // Index in the array of the next list element.
104 };
105 static const intptr_t kNil = -1; // The end of a linked list
106
107 static void InitArray(HashMapListElement* array, intptr_t size) {
108 for (intptr_t i = 0; i < size; ++i) {
109 array[i] = HashMapListElement();
110 }
111 }
112
113 // Must be a power of 2.
114 static const intptr_t kInitialSize = 16;
115
116 void Resize(intptr_t new_size);
117 void ResizeLists(intptr_t new_size);
118 uword Bound(uword value) const { return value & (array_size_ - 1); }
119
120 intptr_t array_size_;
121 intptr_t lists_size_;
122 intptr_t count_; // The number of values stored in the HashMap.
123 HashMapListElement* array_; // Primary store - contains the first value
124 // with a given hash. Colliding elements are stored in linked lists.
125 HashMapListElement* lists_; // The linked lists containing hash collisions.
126 intptr_t free_list_head_; // Unused elements in lists_ are on the free list.
127 Allocator* allocator_;
128
129 private:
130 void operator=(const BaseDirectChainedHashMap& other) = delete;
131};
132
133template <typename KeyValueTrait, typename B, typename Allocator>
134BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::BaseDirectChainedHashMap(
135 const BaseDirectChainedHashMap& other)
136 : B(),
137 array_size_(other.array_size_),
138 lists_size_(other.lists_size_),
139 count_(other.count_),
140 array_(other.allocator_->template Alloc<HashMapListElement>(
141 other.array_size_)),
142 lists_(other.allocator_->template Alloc<HashMapListElement>(
143 other.lists_size_)),
144 free_list_head_(other.free_list_head_),
145 allocator_(other.allocator_) {
146 memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
147 memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
148}
149
150template <typename KeyValueTrait, typename B, typename Allocator>
151typename KeyValueTrait::Pair*
152BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Lookup(
153 typename KeyValueTrait::Key key) const {
154 const typename KeyValueTrait::Value kNoValue =
155 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
156
157 uword hash = static_cast<uword>(KeyValueTrait::Hashcode(key));
158 uword pos = Bound(hash);
159 if (KeyValueTrait::ValueOf(array_[pos].kv) != kNoValue) {
160 if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) {
161 return &array_[pos].kv;
162 }
163
164 intptr_t next = array_[pos].next;
165 while (next != kNil) {
166 if (KeyValueTrait::IsKeyEqual(lists_[next].kv, key)) {
167 return &lists_[next].kv;
168 }
169 next = lists_[next].next;
170 }
171 }
172 return NULL;
173}
174
175template <typename KeyValueTrait, typename B, typename Allocator>
176typename KeyValueTrait::Value
177BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::LookupValue(
178 typename KeyValueTrait::Key key) const {
179 const typename KeyValueTrait::Value kNoValue =
180 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
181 typename KeyValueTrait::Pair* pair = Lookup(key);
182 return (pair == NULL) ? kNoValue : KeyValueTrait::ValueOf(*pair);
183}
184
185template <typename KeyValueTrait, typename B, typename Allocator>
186typename KeyValueTrait::Pair*
187BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Iterator::Next() {
188 const typename KeyValueTrait::Value kNoValue =
189 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
190
191 // Return the current lists_ entry (if any), advancing list_index_.
192 if (list_index_ != kNil) {
193 intptr_t current = list_index_;
194 list_index_ = map_.lists_[current].next;
195 return &map_.lists_[current].kv;
196 }
197
198 // When we're done with the list, we'll continue with the next array
199 // slot.
200 while ((array_index_ < map_.array_size_) &&
201 KeyValueTrait::ValueOf(map_.array_[array_index_].kv) == kNoValue) {
202 ++array_index_;
203 }
204 if (array_index_ < map_.array_size_) {
205 const intptr_t old_array_index = array_index_;
206 ++array_index_;
207 list_index_ = map_.array_[old_array_index].next;
208 return &map_.array_[old_array_index].kv;
209 }
210
211 return nullptr;
212}
213
214template <typename KeyValueTrait, typename B, typename Allocator>
215void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Resize(
216 intptr_t new_size) {
217 const typename KeyValueTrait::Value kNoValue =
218 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
219
220 ASSERT(new_size > count_);
221 // Hashing the values into the new array has no more collisions than in the
222 // old hash map, so we can use the existing lists_ array, if we are careful.
223
224 // Make sure we have at least one free element.
225 if (free_list_head_ == kNil) {
226 ResizeLists(lists_size_ << 1);
227 }
228
229 HashMapListElement* new_array =
230 allocator_->template Alloc<HashMapListElement>(new_size);
231 InitArray(new_array, new_size);
232
233 HashMapListElement* old_array = array_;
234 intptr_t old_size = array_size_;
235
236 intptr_t old_count = count_;
237 count_ = 0;
238 array_size_ = new_size;
239 array_ = new_array;
240
241 if (old_array != NULL) {
242 // Iterate over all the elements in lists, rehashing them.
243 for (intptr_t i = 0; i < old_size; ++i) {
244 if (KeyValueTrait::ValueOf(old_array[i].kv) != kNoValue) {
245 intptr_t current = old_array[i].next;
246 while (current != kNil) {
247 Insert(lists_[current].kv);
248 intptr_t next = lists_[current].next;
249 lists_[current].next = free_list_head_;
250 free_list_head_ = current;
251 current = next;
252 }
253 // Rehash the directly stored value.
254 Insert(old_array[i].kv);
255 }
256 }
257 }
258 USE(old_count);
259 ASSERT(count_ == old_count);
260 allocator_->template Free<HashMapListElement>(old_array, old_size);
261}
262
263template <typename KeyValueTrait, typename B, typename Allocator>
264void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::ResizeLists(
265 intptr_t new_size) {
266 ASSERT(new_size > lists_size_);
267
268 HashMapListElement* new_lists =
269 allocator_->template Alloc<HashMapListElement>(new_size);
270 InitArray(new_lists, new_size);
271
272 HashMapListElement* old_lists = lists_;
273 intptr_t old_size = lists_size_;
274
275 lists_size_ = new_size;
276 lists_ = new_lists;
277
278 if (old_lists != NULL) {
279 for (intptr_t i = 0; i < old_size; i++) {
280 lists_[i] = old_lists[i];
281 }
282 }
283 for (intptr_t i = old_size; i < lists_size_; ++i) {
284 lists_[i].next = free_list_head_;
285 free_list_head_ = i;
286 }
287 allocator_->template Free<HashMapListElement>(old_lists, old_size);
288}
289
290template <typename KeyValueTrait, typename B, typename Allocator>
291void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Insert(
292 typename KeyValueTrait::Pair kv) {
293 const typename KeyValueTrait::Value kNoValue =
294 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
295
296 ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
297 // TODO(dartbug.com/38018): Add assert that Lookup returns nullptr for key.
298
299 // Resizing when half of the hashtable is filled up.
300 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1);
301 ASSERT(count_ < array_size_);
302 count_++;
303 uword pos = Bound(
304 static_cast<uword>(KeyValueTrait::Hashcode(KeyValueTrait::KeyOf(kv))));
305 if (KeyValueTrait::ValueOf(array_[pos].kv) == kNoValue) {
306 array_[pos].kv = kv;
307 array_[pos].next = kNil;
308 } else {
309 if (free_list_head_ == kNil) {
310 ResizeLists(lists_size_ << 1);
311 }
312 intptr_t new_element_pos = free_list_head_;
313 ASSERT(new_element_pos != kNil);
314 free_list_head_ = lists_[free_list_head_].next;
315 lists_[new_element_pos].kv = kv;
316 lists_[new_element_pos].next = array_[pos].next;
317 ASSERT(array_[pos].next == kNil ||
318 KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue);
319 array_[pos].next = new_element_pos;
320 }
321}
322
323template <typename KeyValueTrait, typename B, typename Allocator>
324void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Update(
325 typename KeyValueTrait::Pair kv) {
326 const typename KeyValueTrait::Value kNoValue =
327 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
328
329 ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
330 if (auto const old_kv = Lookup(KeyValueTrait::KeyOf(kv))) {
331 *old_kv = kv;
332 } else {
333 Insert(kv);
334 }
335}
336
337template <typename KeyValueTrait, typename B, typename Allocator>
338bool BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Remove(
339 typename KeyValueTrait::Key key) {
340 const typename KeyValueTrait::Value kNoValue =
341 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
342
343 uword pos = Bound(static_cast<uword>(KeyValueTrait::Hashcode(key)));
344
345 // Check to see if the first element in the bucket is the one we want to
346 // remove.
347 if (KeyValueTrait::ValueOf(array_[pos].kv) == kNoValue) return false;
348 if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) {
349 if (array_[pos].next == kNil) {
350 array_[pos] = HashMapListElement();
351 } else {
352 intptr_t next = array_[pos].next;
353 array_[pos] = lists_[next];
354 lists_[next] = HashMapListElement();
355 lists_[next].next = free_list_head_;
356 free_list_head_ = next;
357 }
358 count_--;
359 return true;
360 }
361
362 intptr_t current = array_[pos].next;
363
364 // If there's only the single element in the bucket and it does not match the
365 // key to be removed, just return.
366 if (current == kNil) {
367 return false;
368 }
369
370 // Check the case where the second element in the bucket is the one to be
371 // removed.
372 if (KeyValueTrait::IsKeyEqual(lists_[current].kv, key)) {
373 array_[pos].next = lists_[current].next;
374 lists_[current] = HashMapListElement();
375 lists_[current].next = free_list_head_;
376 free_list_head_ = current;
377 count_--;
378 return true;
379 }
380
381 // Finally, iterate through the rest of the bucket to see if we can find the
382 // entry that matches our key.
383 intptr_t previous = -1;
384 while (!KeyValueTrait::IsKeyEqual(lists_[current].kv, key)) {
385 previous = current;
386 current = lists_[current].next;
387
388 if (current == kNil) {
389 // Could not find entry with provided key to remove.
390 return false;
391 }
392 }
393
394 lists_[previous].next = lists_[current].next;
395 lists_[current] = HashMapListElement();
396 lists_[current].next = free_list_head_;
397 free_list_head_ = current;
398 count_--;
399 return true;
400}
401
402template <typename KeyValueTrait>
403class DirectChainedHashMap
404 : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> {
405 public:
406 DirectChainedHashMap()
407 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(
408 ASSERT_NOTNULL(ThreadState::Current()->zone())) {}
409
410 explicit DirectChainedHashMap(Zone* zone)
411 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(
412 ASSERT_NOTNULL(zone)) {}
413
414 // There is a current use of the copy constructor in CSEInstructionMap
415 // (compiler/backend/redundancy_elimination.cc), so work is needed if we
416 // want to disallow it.
417 DirectChainedHashMap(const DirectChainedHashMap& other)
418 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(other) {}
419
420 private:
421 void operator=(const DirectChainedHashMap& other) = delete;
422};
423
424template <typename KeyValueTrait>
425class MallocDirectChainedHashMap
426 : public BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc> {
427 public:
428 MallocDirectChainedHashMap()
429 : BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc>(NULL) {}
430
431 // The only use of the copy constructor seems to be in hash_map_test.cc.
432 // Not disallowing it for now just in case there are other users.
433 MallocDirectChainedHashMap(const MallocDirectChainedHashMap& other)
434 : BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc>(other) {}
435
436 private:
437 void operator=(const MallocDirectChainedHashMap& other) = delete;
438};
439
440template <typename T>
441class PointerKeyValueTrait {
442 public:
443 typedef T* Value;
444 typedef T* Key;
445 typedef T* Pair;
446
447 static Key KeyOf(Pair kv) { return kv; }
448
449 static Value ValueOf(Pair kv) { return kv; }
450
451 static inline intptr_t Hashcode(Key key) { return key->Hashcode(); }
452
453 static inline bool IsKeyEqual(Pair kv, Key key) { return kv->Equals(key); }
454};
455
456template <typename T>
457class NumbersKeyValueTrait {
458 public:
459 typedef T Value;
460 typedef intptr_t Key;
461 typedef T Pair;
462
463 static intptr_t KeyOf(Pair kv) { return kv.first(); }
464 static T ValueOf(Pair kv) { return kv; }
465 static inline intptr_t Hashcode(Key key) { return key; }
466 static inline bool IsKeyEqual(Pair kv, Key key) { return kv.first() == key; }
467};
468
469template <typename K, typename V>
470class RawPointerKeyValueTrait {
471 public:
472 typedef K* Key;
473 typedef V Value;
474
475 struct Pair {
476 Key key;
477 Value value;
478 Pair() : key(NULL), value() {}
479 Pair(const Key key, const Value& value) : key(key), value(value) {}
480 Pair(const Pair& other) : key(other.key), value(other.value) {}
481 Pair& operator=(const Pair&) = default;
482 };
483
484 static Key KeyOf(Pair kv) { return kv.key; }
485 static Value ValueOf(Pair kv) { return kv.value; }
486 static intptr_t Hashcode(Key key) { return reinterpret_cast<intptr_t>(key); }
487 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; }
488};
489
490template <typename V>
491class CStringKeyValueTrait : public RawPointerKeyValueTrait<const char, V> {
492 public:
493 typedef typename RawPointerKeyValueTrait<const char, V>::Key Key;
494 typedef typename RawPointerKeyValueTrait<const char, V>::Value Value;
495 typedef typename RawPointerKeyValueTrait<const char, V>::Pair Pair;
496
497 static intptr_t Hashcode(Key key) {
498 ASSERT(key != nullptr);
499 intptr_t hash = 0;
500 for (size_t i = 0; i < strlen(key); i++) {
501 hash = CombineHashes(hash, key[i]);
502 }
503 return FinalizeHash(hash, kBitsPerWord - 1);
504 }
505 static bool IsKeyEqual(Pair kv, Key key) {
506 ASSERT(kv.key != nullptr && key != nullptr);
507 return kv.key == key || strcmp(kv.key, key) == 0;
508 }
509};
510
511template <typename V>
512class CStringMap : public DirectChainedHashMap<CStringKeyValueTrait<V>> {
513 public:
514 CStringMap() : DirectChainedHashMap<CStringKeyValueTrait<V>>() {}
515 explicit CStringMap(Zone* zone)
516 : DirectChainedHashMap<CStringKeyValueTrait<V>>(zone) {}
517
518 private:
519 DISALLOW_COPY_AND_ASSIGN(CStringMap);
520};
521
522template <typename V>
523class IntKeyRawPointerValueTrait {
524 public:
525 typedef intptr_t Key;
526 typedef V Value;
527
528 struct Pair {
529 Key key;
530 Value value;
531 Pair() : key(0), value() {}
532 Pair(const Key key, const Value& value) : key(key), value(value) {}
533 Pair(const Pair& other) : key(other.key), value(other.value) {}
534 Pair& operator=(const Pair&) = default;
535 };
536
537 static Key KeyOf(Pair kv) { return kv.key; }
538 static Value ValueOf(Pair kv) { return kv.value; }
539 static intptr_t Hashcode(Key key) { return key; }
540 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; }
541};
542
543template <typename V>
544class IntMap : public DirectChainedHashMap<IntKeyRawPointerValueTrait<V> > {
545 public:
546 IntMap() : DirectChainedHashMap<IntKeyRawPointerValueTrait<V>>() {}
547 explicit IntMap(Zone* zone)
548 : DirectChainedHashMap<IntKeyRawPointerValueTrait<V>>(zone) {}
549
550 typedef typename IntKeyRawPointerValueTrait<V>::Key Key;
551 typedef typename IntKeyRawPointerValueTrait<V>::Value Value;
552 typedef typename IntKeyRawPointerValueTrait<V>::Pair Pair;
553
554 inline void Insert(const Key& key, const Value& value) {
555 Pair pair(key, value);
556 DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Insert(pair);
557 }
558
559 inline V Lookup(const Key& key) {
560 Pair* pair =
561 DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Lookup(key);
562 if (pair == NULL) {
563 return V();
564 } else {
565 return pair->value;
566 }
567 }
568
569 inline Pair* LookupPair(const Key& key) {
570 return DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Lookup(key);
571 }
572
573 private:
574 DISALLOW_COPY_AND_ASSIGN(IntMap);
575};
576
577template <typename V>
578class IdentitySetKeyValueTrait {
579 public:
580 // Typedefs needed for the DirectChainedHashMap template.
581 typedef V Key;
582 typedef V Value;
583 typedef V Pair;
584
585 static Key KeyOf(Pair kv) { return kv; }
586
587 static Value ValueOf(Pair kv) { return kv; }
588
589 static inline intptr_t Hashcode(Key key) {
590 return reinterpret_cast<intptr_t>(key);
591 }
592
593 static inline bool IsKeyEqual(Pair pair, Key key) { return pair == key; }
594};
595
596} // namespace dart
597
598#endif // RUNTIME_VM_HASH_MAP_H_
599