Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2015 Andrew Kelley
3 : : *
4 : : * This file is part of zig, which is MIT licensed.
5 : : * See http://opensource.org/licenses/MIT
6 : : */
7 : :
8 : : #ifndef ZIG_HASH_MAP_HPP
9 : : #define ZIG_HASH_MAP_HPP
10 : :
11 : : #include "util.hpp"
12 : :
13 : : #include <stdint.h>
14 : :
15 : : template<typename K, typename V, uint32_t (*HashFunction)(K key), bool (*EqualFn)(K a, K b)>
16 : : class HashMap {
17 : : public:
18 : 38067 : void init(int capacity) {
19 : 38067 : init_capacity(capacity);
20 : 38067 : }
21 : 0 : void deinit(void) {
22 : 0 : free(_entries);
23 : 0 : }
24 : :
25 : : struct Entry {
26 : : bool used;
27 : : int distance_from_start_index;
28 : : K key;
29 : : V value;
30 : : };
31 : :
32 : 0 : void clear() {
33 [ # # ]: 0 : for (int i = 0; i < _capacity; i += 1) {
34 : 0 : _entries[i].used = false;
35 : : }
36 : 0 : _size = 0;
37 : 0 : _max_distance_from_start_index = 0;
38 : 0 : _modification_count += 1;
39 : 0 : }
40 : :
41 : 187623 : int size() const {
42 : 187623 : return _size;
43 : : }
44 : :
45 : 375074 : void put(const K &key, const V &value) {
46 : 375074 : _modification_count += 1;
47 : 375074 : internal_put(key, value);
48 : :
49 : : // if we get too full (60%), double the capacity
50 [ + + + + : 375074 : if (_size * 5 >= _capacity * 3) {
+ + + + +
+ + + + +
+ + + + ]
51 : 28086 : Entry *old_entries = _entries;
52 : 28086 : int old_capacity = _capacity;
53 : 28086 : init_capacity(_capacity * 2);
54 : : // dump all of the old elements into the new table
55 [ + + ][ + + ]: 682258 : for (int i = 0; i < old_capacity; i += 1) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
56 : 654172 : Entry *old_entry = &old_entries[i];
57 [ + + ][ + + ]: 654172 : if (old_entry->used)
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
58 : 410452 : internal_put(old_entry->key, old_entry->value);
59 : : }
60 : 28086 : free(old_entries);
61 : : }
62 : 375074 : }
63 : :
64 : 323767 : Entry *put_unique(const K &key, const V &value) {
65 : : // TODO make this more efficient
66 : 323767 : Entry *entry = internal_get(key);
67 [ - + + + : 323767 : if (entry)
+ + + + -
+ ]
68 : 21922 : return entry;
69 : 301845 : put(key, value);
70 : 301845 : return nullptr;
71 : : }
72 : :
73 : 19527 : const V &get(const K &key) const {
74 : 19527 : Entry *entry = internal_get(key);
75 [ - + ]: 19527 : if (!entry)
76 : 0 : zig_panic("key not found");
77 : 19527 : return entry->value;
78 : : }
79 : :
80 : 3664633 : Entry *maybe_get(const K &key) const {
81 : 3664633 : return internal_get(key);
82 : : }
83 : :
84 : 15661 : void maybe_remove(const K &key) {
85 [ + + ]: 15661 : if (maybe_get(key)) {
86 : 13434 : remove(key);
87 : : }
88 : 15661 : }
89 : :
90 : 13434 : void remove(const K &key) {
91 : 13434 : _modification_count += 1;
92 : 13434 : int start_index = key_to_index(key);
93 [ + - ]: 15883 : for (int roll_over = 0; roll_over <= _max_distance_from_start_index; roll_over += 1) {
94 : 15883 : int index = (start_index + roll_over) % _capacity;
95 : 15883 : Entry *entry = &_entries[index];
96 : :
97 [ - + ]: 15883 : if (!entry->used)
98 : 0 : zig_panic("key not found");
99 : :
100 [ + + ]: 15883 : if (!EqualFn(entry->key, key))
101 : 2449 : continue;
102 : :
103 [ + - ]: 17189 : for (; roll_over < _capacity; roll_over += 1) {
104 : 17189 : int next_index = (start_index + roll_over + 1) % _capacity;
105 : 17189 : Entry *next_entry = &_entries[next_index];
106 [ + + ][ + + ]: 17189 : if (!next_entry->used || next_entry->distance_from_start_index == 0) {
107 : 13434 : entry->used = false;
108 : 13434 : _size -= 1;
109 : 13434 : return;
110 : : }
111 : 3755 : *entry = *next_entry;
112 : 3755 : entry->distance_from_start_index -= 1;
113 : 3755 : entry = next_entry;
114 : : }
115 : 0 : zig_panic("shifting everything in the table");
116 : : }
117 : 0 : zig_panic("key not found");
118 : : }
119 : :
120 : : class Iterator {
121 : : public:
122 : 186005 : Entry *next() {
123 [ - + ][ # # ]: 186005 : if (_inital_modification_count != _table->_modification_count)
124 : 0 : zig_panic("concurrent modification");
125 [ + + ][ # # ]: 186005 : if (_count >= _table->size())
126 : 622 : return NULL;
127 [ + - ][ # # ]: 509983 : for (; _index < _table->_capacity; _index += 1) {
128 : 509983 : Entry *entry = &_table->_entries[_index];
129 [ + + ][ # # ]: 509983 : if (entry->used) {
130 : 185383 : _index += 1;
131 : 185383 : _count += 1;
132 : 185383 : return entry;
133 : : }
134 : : }
135 : 0 : zig_panic("no next item");
136 : : }
137 : : private:
138 : : const HashMap * _table;
139 : : // how many items have we returned
140 : : int _count = 0;
141 : : // iterator through the entry array
142 : : int _index = 0;
143 : : // used to detect concurrent modification
144 : : uint32_t _inital_modification_count;
145 : 622 : Iterator(const HashMap * table) :
146 : 622 : _table(table), _inital_modification_count(table->_modification_count) {
147 : 622 : }
148 : : friend HashMap;
149 : : };
150 : :
151 : : // you must not modify the underlying HashMap while this iterator is still in use
152 : 622 : Iterator entry_iterator() const {
153 : 622 : return Iterator(this);
154 : : }
155 : :
156 : : private:
157 : :
158 : : Entry *_entries;
159 : : int _capacity;
160 : : int _size;
161 : : int _max_distance_from_start_index;
162 : : // this is used to detect bugs where a hashtable is edited while an iterator is running.
163 : : uint32_t _modification_count;
164 : :
165 : 66153 : void init_capacity(int capacity) {
166 : 66153 : _capacity = capacity;
167 : 66153 : _entries = allocate<Entry>(_capacity);
168 : 66153 : _size = 0;
169 : 66153 : _max_distance_from_start_index = 0;
170 [ + + ][ + + ]: 1703320 : for (int i = 0; i < _capacity; i += 1) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ # # ]
171 : 1637167 : _entries[i].used = false;
172 : : }
173 : 66153 : }
174 : :
175 : 785526 : void internal_put(K key, V value) {
176 : 785526 : int start_index = key_to_index(key);
177 : 1872034 : for (int roll_over = 0, distance_from_start_index = 0;
178 [ + - ][ + - ]: 1872034 : roll_over < _capacity; roll_over += 1, distance_from_start_index += 1)
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
179 : : {
180 : 1872034 : int index = (start_index + roll_over) % _capacity;
181 : 1872034 : Entry *entry = &_entries[index];
182 : :
183 [ + + ][ + + ]: 1872034 : if (entry->used && !EqualFn(entry->key, key)) {
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + - ]
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + ]
184 [ + + ][ + + ]: 1086508 : if (entry->distance_from_start_index < distance_from_start_index) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
185 : : // robin hood to the rescue
186 : 188126 : Entry tmp = *entry;
187 [ + + ][ + + ]: 188126 : if (distance_from_start_index > _max_distance_from_start_index)
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
188 : 8908 : _max_distance_from_start_index = distance_from_start_index;
189 : 188126 : *entry = {
190 : : true,
191 : : distance_from_start_index,
192 : : key,
193 : : value,
194 : : };
195 : 188126 : key = tmp.key;
196 : 188126 : value = tmp.value;
197 : 188126 : distance_from_start_index = tmp.distance_from_start_index;
198 : : }
199 : 1086508 : continue;
200 : : }
201 : :
202 [ + + ][ + - ]: 785526 : if (!entry->used) {
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
203 : : // adding an entry. otherwise overwriting old value with
204 : : // same key
205 : 785493 : _size += 1;
206 : : }
207 : :
208 [ + + ][ + + ]: 785526 : if (distance_from_start_index > _max_distance_from_start_index)
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
209 : 20276 : _max_distance_from_start_index = distance_from_start_index;
210 : 785526 : *entry = {
211 : : true,
212 : : distance_from_start_index,
213 : : key,
214 : : value,
215 : : };
216 : 785526 : return;
217 : : }
218 : 0 : zig_panic("put into a full HashMap");
219 : : }
220 : :
221 : :
222 : 4007927 : Entry *internal_get(const K &key) const {
223 : 4007927 : int start_index = key_to_index(key);
224 [ + + ][ + + ]: 7102251 : for (int roll_over = 0; roll_over <= _max_distance_from_start_index; roll_over += 1) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
225 : 6871211 : int index = (start_index + roll_over) % _capacity;
226 : 6871211 : Entry *entry = &_entries[index];
227 : :
228 [ + + ][ + + ]: 6871211 : if (!entry->used)
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
229 : 2252760 : return NULL;
230 : :
231 [ + + ][ + + ]: 4618451 : if (EqualFn(entry->key, key))
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
232 : 1524127 : return entry;
233 : : }
234 : 231040 : return NULL;
235 : : }
236 : :
237 : 4806887 : int key_to_index(const K &key) const {
238 : 4806887 : return (int)(HashFunction(key) % ((uint32_t)_capacity));
239 : : }
240 : : };
241 : :
242 : : #endif
|
