OLD | NEW |
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 #include "platform/hashmap.h" | 5 #include "platform/hashmap.h" |
6 | 6 |
7 #include "platform/utils.h" | 7 #include "platform/utils.h" |
8 | 8 |
9 namespace dart { | 9 namespace dart { |
10 | 10 |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
99 // candidate entry for clearing. | 99 // candidate entry for clearing. |
100 if ((next > candidate && (start <= candidate || start > next)) || | 100 if ((next > candidate && (start <= candidate || start > next)) || |
101 (next < candidate && (start <= candidate && start > next))) { | 101 (next < candidate && (start <= candidate && start > next))) { |
102 *candidate = *next; | 102 *candidate = *next; |
103 candidate = next; | 103 candidate = next; |
104 } | 104 } |
105 } | 105 } |
106 | 106 |
107 // Clear the candidate which will not break searching the hash table. | 107 // Clear the candidate which will not break searching the hash table. |
108 candidate->key = NULL; | 108 candidate->key = NULL; |
109 candidate->value = NULL; | |
110 occupancy_--; | 109 occupancy_--; |
111 } | 110 } |
112 | 111 |
113 | 112 |
| 113 HashMap::Entry* HashMap::Remove(Entry* entry) { |
| 114 Remove(entry->key, entry->hash); |
| 115 |
| 116 // A key can only exist once in the map and we just removed `key`. This means |
| 117 // that either a left-rotation has happened (in which case `entry` points |
| 118 // already to the next element (in terms of iteration order)) or alternatively |
| 119 // we can use the normal `Next()` call to move in iteration order. |
| 120 if (entry->key != NULL) { |
| 121 // A left-rotation happened. `entry` points already to the next element in |
| 122 // iteration order. |
| 123 return entry; |
| 124 } else { |
| 125 return Next(entry); |
| 126 } |
| 127 } |
| 128 |
| 129 |
114 void HashMap::Clear(ClearFun clear) { | 130 void HashMap::Clear(ClearFun clear) { |
115 // Mark all entries as empty. | 131 // Mark all entries as empty. |
116 const Entry* end = map_end(); | 132 const Entry* end = map_end(); |
117 for (Entry* p = map_; p < end; p++) { | 133 for (Entry* p = map_; p < end; p++) { |
118 if ((clear != NULL) && (p->key != NULL)) { | 134 if ((clear != NULL) && (p->key != NULL)) { |
119 clear(p->value); | 135 clear(p->value); |
120 } | 136 } |
121 p->value = NULL; | |
122 p->key = NULL; | 137 p->key = NULL; |
123 } | 138 } |
124 occupancy_ = 0; | 139 occupancy_ = 0; |
125 } | 140 } |
126 | 141 |
127 | 142 |
128 HashMap::Entry* HashMap::Start() const { | 143 HashMap::Entry* HashMap::Start() const { |
129 return Next(map_ - 1); | 144 return Next(map_ - 1); |
130 } | 145 } |
131 | 146 |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
186 Lookup(p->key, p->hash, true)->value = p->value; | 201 Lookup(p->key, p->hash, true)->value = p->value; |
187 n--; | 202 n--; |
188 } | 203 } |
189 } | 204 } |
190 | 205 |
191 // Delete old map. | 206 // Delete old map. |
192 delete[] map; | 207 delete[] map; |
193 } | 208 } |
194 | 209 |
195 } // namespace dart | 210 } // namespace dart |
OLD | NEW |