Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(169)

Side by Side Diff: runtime/vm/hash_map.h

Issue 10871040: Revert my last change r11227. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 8 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « runtime/vm/flow_graph_optimizer.cc ('k') | runtime/vm/hash_map_test.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 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 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. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 #ifndef VM_HASH_MAP_H_ 5 #ifndef VM_HASH_MAP_H_
6 #define VM_HASH_MAP_H_ 6 #define VM_HASH_MAP_H_
7 7
8 namespace dart { 8 namespace dart {
9 9
10 template <typename T> 10 template <typename T>
11 class DirectChainedHashMap: public ValueObject { 11 class DirectChainedHashMap: public ValueObject {
12 public: 12 public:
13 DirectChainedHashMap() : array_size_(0), 13 DirectChainedHashMap() : array_size_(0),
14 lists_size_(0), 14 lists_size_(0),
15 count_(0), 15 count_(0),
16 array_(NULL), 16 array_(NULL),
17 lists_(NULL), 17 lists_(NULL),
18 free_list_head_(kNil) { 18 free_list_head_(kNil) {
19 ResizeLists(kInitialSize); 19 ResizeLists(kInitialSize);
20 Resize(kInitialSize); 20 Resize(kInitialSize);
21 } 21 }
22 22
23 DirectChainedHashMap(const DirectChainedHashMap& other);
24
25 void Insert(T value); 23 void Insert(T value);
26 24
27 T Lookup(T value) const; 25 T Lookup(T value) const;
28 26
29 bool IsEmpty() const { return count_ == 0; } 27 bool IsEmpty() const { return count_ == 0; }
30 28
31 private: 29 private:
32 // A linked list of T values. Stored in arrays. 30 // A linked list of T values. Stored in arrays.
33 struct HashMapListElement { 31 struct HashMapListElement {
34 T value; 32 T value;
35 intptr_t next; // Index in the array of the next list element. 33 intptr_t next; // Index in the array of the next list element.
36 }; 34 };
37 static const intptr_t kNil = -1; // The end of a linked list 35 static const intptr_t kNil = -1; // The end of a linked list
38 36
39 // Must be a power of 2. 37 // Must be a power of 2.
40 static const intptr_t kInitialSize = 16; 38 static const intptr_t kInitialSize = 16;
41 39
42 void Resize(intptr_t new_size); 40 void Resize(intptr_t new_size);
43 void ResizeLists(intptr_t new_size); 41 void ResizeLists(intptr_t new_size);
44 uword Bound(uword value) const { return value & (array_size_ - 1); } 42 uword Bound(uword value) const { return value & (array_size_ - 1); }
45 43
46 intptr_t array_size_; 44 intptr_t array_size_;
47 intptr_t lists_size_; 45 intptr_t lists_size_;
48 intptr_t count_; // The number of values stored in the HashMap. 46 intptr_t count_; // The number of values stored in the HashMap.
49 HashMapListElement* array_; // Primary store - contains the first value 47 HashMapListElement* array_; // Primary store - contains the first value
50 // with a given hash. Colliding elements are stored in linked lists. 48 // with a given hash. Colliding elements are stored in linked lists.
51 HashMapListElement* lists_; // The linked lists containing hash collisions. 49 HashMapListElement* lists_; // The linked lists containing hash collisions.
52 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. 50 intptr_t free_list_head_; // Unused elements in lists_ are on the free list.
51
52 DISALLOW_COPY_AND_ASSIGN(DirectChainedHashMap);
53 }; 53 };
54 54
55 55
56 template <typename T> 56 template <typename T>
57 T DirectChainedHashMap<T>::Lookup(T value) const { 57 T DirectChainedHashMap<T>::Lookup(T value) const {
58 uword hash = static_cast<uword>(value->Hashcode()); 58 uword hash = static_cast<uword>(value->Hashcode());
59 uword pos = Bound(hash); 59 uword pos = Bound(hash);
60 if (array_[pos].value != NULL) { 60 if (array_[pos].value != NULL) {
61 if (array_[pos].value->Equals(value)) return array_[pos].value; 61 if (array_[pos].value->Equals(value)) return array_[pos].value;
62 intptr_t next = array_[pos].next; 62 intptr_t next = array_[pos].next;
63 while (next != kNil) { 63 while (next != kNil) {
64 if (lists_[next].value->Equals(value)) return lists_[next].value; 64 if (lists_[next].value->Equals(value)) return lists_[next].value;
65 next = lists_[next].next; 65 next = lists_[next].next;
66 } 66 }
67 } 67 }
68 return NULL; 68 return NULL;
69 } 69 }
70 70
71 71
72 template <typename T> 72 template <typename T>
73 DirectChainedHashMap<T>::DirectChainedHashMap(const DirectChainedHashMap& other)
74 : array_size_(other.array_size_),
75 lists_size_(other.lists_size_),
76 count_(other.count_),
77 array_(Isolate::Current()->current_zone()->
78 Alloc<HashMapListElement>(other.array_size_)),
79 lists_(Isolate::Current()->current_zone()->
80 Alloc<HashMapListElement>(other.lists_size_)),
81 free_list_head_(other.free_list_head_) {
82 memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
83 memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
84 }
85
86
87 template <typename T>
88 void DirectChainedHashMap<T>::Resize(intptr_t new_size) { 73 void DirectChainedHashMap<T>::Resize(intptr_t new_size) {
89 ASSERT(new_size > count_); 74 ASSERT(new_size > count_);
90 // Hashing the values into the new array has no more collisions than in the 75 // Hashing the values into the new array has no more collisions than in the
91 // old hash map, so we can use the existing lists_ array, if we are careful. 76 // old hash map, so we can use the existing lists_ array, if we are careful.
92 77
93 // Make sure we have at least one free element. 78 // Make sure we have at least one free element.
94 if (free_list_head_ == kNil) { 79 if (free_list_head_ == kNil) {
95 ResizeLists(lists_size_ << 1); 80 ResizeLists(lists_size_ << 1);
96 } 81 }
97 82
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after
175 lists_[new_element_pos].value = value; 160 lists_[new_element_pos].value = value;
176 lists_[new_element_pos].next = array_[pos].next; 161 lists_[new_element_pos].next = array_[pos].next;
177 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); 162 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
178 array_[pos].next = new_element_pos; 163 array_[pos].next = new_element_pos;
179 } 164 }
180 } 165 }
181 166
182 } // namespace dart 167 } // namespace dart
183 168
184 #endif // VM_HASH_MAP_H_ 169 #endif // VM_HASH_MAP_H_
OLDNEW
« no previous file with comments | « runtime/vm/flow_graph_optimizer.cc ('k') | runtime/vm/hash_map_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698