Branch data Line data Source code
1 : : /* The implementation of the hash table (_Py_hashtable_t) is based on the
2 : : cfuhash project:
3 : : http://sourceforge.net/projects/libcfu/
4 : :
5 : : Copyright of cfuhash:
6 : : ----------------------------------
7 : : Creation date: 2005-06-24 21:22:40
8 : : Authors: Don
9 : : Change log:
10 : :
11 : : Copyright (c) 2005 Don Owens
12 : : All rights reserved.
13 : :
14 : : This code is released under the BSD license:
15 : :
16 : : Redistribution and use in source and binary forms, with or without
17 : : modification, are permitted provided that the following conditions
18 : : are met:
19 : :
20 : : * Redistributions of source code must retain the above copyright
21 : : notice, this list of conditions and the following disclaimer.
22 : :
23 : : * Redistributions in binary form must reproduce the above
24 : : copyright notice, this list of conditions and the following
25 : : disclaimer in the documentation and/or other materials provided
26 : : with the distribution.
27 : :
28 : : * Neither the name of the author nor the names of its
29 : : contributors may be used to endorse or promote products derived
30 : : from this software without specific prior written permission.
31 : :
32 : : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
33 : : "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
34 : : LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
35 : : FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
36 : : COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
37 : : INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38 : : (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39 : : SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40 : : HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41 : : STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42 : : ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43 : : OF THE POSSIBILITY OF SUCH DAMAGE.
44 : : ----------------------------------
45 : : */
46 : :
47 : : #include "Python.h"
48 : : #include "pycore_hashtable.h"
49 : :
50 : : #define HASHTABLE_MIN_SIZE 16
51 : : #define HASHTABLE_HIGH 0.50
52 : : #define HASHTABLE_LOW 0.10
53 : : #define HASHTABLE_REHASH_FACTOR 2.0 / (HASHTABLE_LOW + HASHTABLE_HIGH)
54 : :
55 : : #define BUCKETS_HEAD(SLIST) \
56 : : ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(SLIST)))
57 : : #define TABLE_HEAD(HT, BUCKET) \
58 : : ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(HT)->buckets[BUCKET]))
59 : : #define ENTRY_NEXT(ENTRY) \
60 : : ((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY))
61 : :
62 : : /* Forward declaration */
63 : : static int hashtable_rehash(_Py_hashtable_t *ht);
64 : :
65 : : static void
66 : 383920 : _Py_slist_init(_Py_slist_t *list)
67 : : {
68 : 383920 : list->head = NULL;
69 : 383920 : }
70 : :
71 : :
72 : : static void
73 : 5569117 : _Py_slist_prepend(_Py_slist_t *list, _Py_slist_item_t *item)
74 : : {
75 : 5569117 : item->next = list->head;
76 : 5569117 : list->head = item;
77 : 5569117 : }
78 : :
79 : :
80 : : static void
81 : 1339083 : _Py_slist_remove(_Py_slist_t *list, _Py_slist_item_t *previous,
82 : : _Py_slist_item_t *item)
83 : : {
84 [ + + ]: 1339083 : if (previous != NULL)
85 : 43663 : previous->next = item->next;
86 : : else
87 : 1295420 : list->head = item->next;
88 : 1339083 : }
89 : :
90 : :
91 : : Py_uhash_t
92 : 10646375 : _Py_hashtable_hash_ptr(const void *key)
93 : : {
94 : 10646375 : return (Py_uhash_t)_Py_HashPointerRaw(key);
95 : : }
96 : :
97 : :
98 : : int
99 : 1339144 : _Py_hashtable_compare_direct(const void *key1, const void *key2)
100 : : {
101 : 1339144 : return (key1 == key2);
102 : : }
103 : :
104 : :
105 : : /* makes sure the real size of the buckets array is a power of 2 */
106 : : static size_t
107 : 30061 : round_size(size_t s)
108 : : {
109 : : size_t i;
110 [ + + ]: 30061 : if (s < HASHTABLE_MIN_SIZE)
111 : 298 : return HASHTABLE_MIN_SIZE;
112 : 29763 : i = 1;
113 [ + + ]: 237775 : while (i < s)
114 : 208012 : i <<= 1;
115 : 29763 : return i;
116 : : }
117 : :
118 : :
119 : : size_t
120 : 6 : _Py_hashtable_size(const _Py_hashtable_t *ht)
121 : : {
122 : 6 : size_t size = sizeof(_Py_hashtable_t);
123 : : /* buckets */
124 : 6 : size += ht->nbuckets * sizeof(_Py_hashtable_entry_t *);
125 : : /* entries */
126 : 6 : size += ht->nentries * sizeof(_Py_hashtable_entry_t);
127 : 6 : return size;
128 : : }
129 : :
130 : :
131 : : _Py_hashtable_entry_t *
132 : 7919983 : _Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key)
133 : : {
134 : 7919983 : Py_uhash_t key_hash = ht->hash_func(key);
135 : 7919983 : size_t index = key_hash & (ht->nbuckets - 1);
136 : 7919983 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
137 : : while (1) {
138 [ + + ]: 8565275 : if (entry == NULL) {
139 : 59727 : return NULL;
140 : : }
141 [ + + + - ]: 8505548 : if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {
142 : 7860256 : break;
143 : : }
144 : 645292 : entry = ENTRY_NEXT(entry);
145 : : }
146 : 7860256 : return entry;
147 : : }
148 : :
149 : :
150 : : // Specialized for:
151 : : // hash_func == _Py_hashtable_hash_ptr
152 : : // compare_func == _Py_hashtable_compare_direct
153 : : static _Py_hashtable_entry_t *
154 : 6498566 : _Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key)
155 : : {
156 : 6498566 : Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key);
157 : 6498566 : size_t index = key_hash & (ht->nbuckets - 1);
158 : 6498566 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
159 : : while (1) {
160 [ + + ]: 8049007 : if (entry == NULL) {
161 : 2773578 : return NULL;
162 : : }
163 : : // Compare directly keys (ignore entry->key_hash)
164 [ + + ]: 5275429 : if (entry->key == key) {
165 : 3724988 : break;
166 : : }
167 : 1550441 : entry = ENTRY_NEXT(entry);
168 : : }
169 : 3724988 : return entry;
170 : : }
171 : :
172 : :
173 : : void*
174 : 1395922 : _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key)
175 : : {
176 : 1395922 : Py_uhash_t key_hash = ht->hash_func(key);
177 : 1395922 : size_t index = key_hash & (ht->nbuckets - 1);
178 : :
179 : 1395922 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
180 : 1395922 : _Py_hashtable_entry_t *previous = NULL;
181 : : while (1) {
182 [ + + ]: 1458070 : if (entry == NULL) {
183 : : // not found
184 : 56839 : return NULL;
185 : : }
186 [ + + + - ]: 1401231 : if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {
187 : 1339083 : break;
188 : : }
189 : 62148 : previous = entry;
190 : 62148 : entry = ENTRY_NEXT(entry);
191 : : }
192 : :
193 : 1339083 : _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous,
194 : : (_Py_slist_item_t *)entry);
195 : 1339083 : ht->nentries--;
196 : :
197 : 1339083 : void *value = entry->value;
198 : 1339083 : ht->alloc.free(entry);
199 : :
200 [ + + ]: 1339083 : if ((float)ht->nentries / (float)ht->nbuckets < HASHTABLE_LOW) {
201 : : // Ignore failure: error cannot be reported to the caller
202 : 179 : hashtable_rehash(ht);
203 : : }
204 : 1339083 : return value;
205 : : }
206 : :
207 : :
208 : : int
209 : 2822610 : _Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value)
210 : : {
211 : : _Py_hashtable_entry_t *entry;
212 : :
213 : : #ifndef NDEBUG
214 : : /* Don't write the assertion on a single line because it is interesting
215 : : to know the duplicated entry if the assertion failed. The entry can
216 : : be read using a debugger. */
217 : : entry = ht->get_entry_func(ht, key);
218 : : assert(entry == NULL);
219 : : #endif
220 : :
221 : :
222 : 2822610 : entry = ht->alloc.malloc(sizeof(_Py_hashtable_entry_t));
223 [ - + ]: 2822610 : if (entry == NULL) {
224 : : /* memory allocation failed */
225 : 0 : return -1;
226 : : }
227 : :
228 : 2822610 : entry->key_hash = ht->hash_func(key);
229 : 2822610 : entry->key = (void *)key;
230 : 2822610 : entry->value = value;
231 : :
232 : 2822610 : ht->nentries++;
233 [ + + ]: 2822610 : if ((float)ht->nentries / (float)ht->nbuckets > HASHTABLE_HIGH) {
234 [ - + ]: 29709 : if (hashtable_rehash(ht) < 0) {
235 : 0 : ht->nentries--;
236 : 0 : ht->alloc.free(entry);
237 : 0 : return -1;
238 : : }
239 : : }
240 : :
241 : 2822610 : size_t index = entry->key_hash & (ht->nbuckets - 1);
242 : 2822610 : _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry);
243 : 2822610 : return 0;
244 : : }
245 : :
246 : :
247 : : void*
248 : 2409345 : _Py_hashtable_get(_Py_hashtable_t *ht, const void *key)
249 : : {
250 : 2409345 : _Py_hashtable_entry_t *entry = ht->get_entry_func(ht, key);
251 [ + + ]: 2409345 : if (entry != NULL) {
252 : 1017554 : return entry->value;
253 : : }
254 : : else {
255 : 1391791 : return NULL;
256 : : }
257 : : }
258 : :
259 : :
260 : : int
261 : 43 : _Py_hashtable_foreach(_Py_hashtable_t *ht,
262 : : _Py_hashtable_foreach_func func,
263 : : void *user_data)
264 : : {
265 [ + + ]: 955 : for (size_t hv = 0; hv < ht->nbuckets; hv++) {
266 : 912 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, hv);
267 [ + + ]: 1049 : while (entry != NULL) {
268 : 137 : int res = func(ht, entry->key, entry->value, user_data);
269 [ - + ]: 137 : if (res) {
270 : 0 : return res;
271 : : }
272 : 137 : entry = ENTRY_NEXT(entry);
273 : : }
274 : : }
275 : 43 : return 0;
276 : : }
277 : :
278 : :
279 : : static int
280 : 30061 : hashtable_rehash(_Py_hashtable_t *ht)
281 : : {
282 : 30061 : size_t new_size = round_size((size_t)(ht->nentries * HASHTABLE_REHASH_FACTOR));
283 [ + + ]: 30061 : if (new_size == ht->nbuckets) {
284 : 226 : return 0;
285 : : }
286 : :
287 : 29835 : size_t buckets_size = new_size * sizeof(ht->buckets[0]);
288 : 29835 : _Py_slist_t *new_buckets = ht->alloc.malloc(buckets_size);
289 [ - + ]: 29835 : if (new_buckets == NULL) {
290 : : /* memory allocation failed */
291 : 0 : return -1;
292 : : }
293 : 29835 : memset(new_buckets, 0, buckets_size);
294 : :
295 [ + + ]: 7347355 : for (size_t bucket = 0; bucket < ht->nbuckets; bucket++) {
296 : 7317520 : _Py_hashtable_entry_t *entry = BUCKETS_HEAD(ht->buckets[bucket]);
297 [ + + ]: 10064027 : while (entry != NULL) {
298 : : assert(ht->hash_func(entry->key) == entry->key_hash);
299 : 2746507 : _Py_hashtable_entry_t *next = ENTRY_NEXT(entry);
300 : 2746507 : size_t entry_index = entry->key_hash & (new_size - 1);
301 : :
302 : 2746507 : _Py_slist_prepend(&new_buckets[entry_index], (_Py_slist_item_t*)entry);
303 : :
304 : 2746507 : entry = next;
305 : : }
306 : : }
307 : :
308 : 29835 : ht->alloc.free(ht->buckets);
309 : 29835 : ht->nbuckets = new_size;
310 : 29835 : ht->buckets = new_buckets;
311 : 29835 : return 0;
312 : : }
313 : :
314 : :
315 : : _Py_hashtable_t *
316 : 15538 : _Py_hashtable_new_full(_Py_hashtable_hash_func hash_func,
317 : : _Py_hashtable_compare_func compare_func,
318 : : _Py_hashtable_destroy_func key_destroy_func,
319 : : _Py_hashtable_destroy_func value_destroy_func,
320 : : _Py_hashtable_allocator_t *allocator)
321 : : {
322 : : _Py_hashtable_allocator_t alloc;
323 [ + + ]: 15538 : if (allocator == NULL) {
324 : 15409 : alloc.malloc = PyMem_Malloc;
325 : 15409 : alloc.free = PyMem_Free;
326 : : }
327 : : else {
328 : 129 : alloc = *allocator;
329 : : }
330 : :
331 : 15538 : _Py_hashtable_t *ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t));
332 [ - + ]: 15538 : if (ht == NULL) {
333 : 0 : return ht;
334 : : }
335 : :
336 : 15538 : ht->nbuckets = HASHTABLE_MIN_SIZE;
337 : 15538 : ht->nentries = 0;
338 : :
339 : 15538 : size_t buckets_size = ht->nbuckets * sizeof(ht->buckets[0]);
340 : 15538 : ht->buckets = alloc.malloc(buckets_size);
341 [ - + ]: 15538 : if (ht->buckets == NULL) {
342 : 0 : alloc.free(ht);
343 : 0 : return NULL;
344 : : }
345 : 15538 : memset(ht->buckets, 0, buckets_size);
346 : :
347 : 15538 : ht->get_entry_func = _Py_hashtable_get_entry_generic;
348 : 15538 : ht->hash_func = hash_func;
349 : 15538 : ht->compare_func = compare_func;
350 : 15538 : ht->key_destroy_func = key_destroy_func;
351 : 15538 : ht->value_destroy_func = value_destroy_func;
352 : 15538 : ht->alloc = alloc;
353 [ + + ]: 15538 : if (ht->hash_func == _Py_hashtable_hash_ptr
354 [ + - ]: 15035 : && ht->compare_func == _Py_hashtable_compare_direct)
355 : : {
356 : 15035 : ht->get_entry_func = _Py_hashtable_get_entry_ptr;
357 : : }
358 : 15538 : return ht;
359 : : }
360 : :
361 : :
362 : : _Py_hashtable_t *
363 : 1 : _Py_hashtable_new(_Py_hashtable_hash_func hash_func,
364 : : _Py_hashtable_compare_func compare_func)
365 : : {
366 : 1 : return _Py_hashtable_new_full(hash_func, compare_func,
367 : : NULL, NULL, NULL);
368 : : }
369 : :
370 : :
371 : : static void
372 : 1483527 : _Py_hashtable_destroy_entry(_Py_hashtable_t *ht, _Py_hashtable_entry_t *entry)
373 : : {
374 [ + + ]: 1483527 : if (ht->key_destroy_func) {
375 : 1382350 : ht->key_destroy_func(entry->key);
376 : : }
377 [ + + ]: 1483527 : if (ht->value_destroy_func) {
378 : 101152 : ht->value_destroy_func(entry->value);
379 : : }
380 : 1483527 : ht->alloc.free(entry);
381 : 1483527 : }
382 : :
383 : :
384 : : void
385 : 173 : _Py_hashtable_clear(_Py_hashtable_t *ht)
386 : : {
387 [ + + ]: 384093 : for (size_t i=0; i < ht->nbuckets; i++) {
388 : 383920 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);
389 [ + + ]: 474590 : while (entry != NULL) {
390 : 90670 : _Py_hashtable_entry_t *next = ENTRY_NEXT(entry);
391 : 90670 : _Py_hashtable_destroy_entry(ht, entry);
392 : 90670 : entry = next;
393 : : }
394 : 383920 : _Py_slist_init(&ht->buckets[i]);
395 : : }
396 : 173 : ht->nentries = 0;
397 : : // Ignore failure: clear function is not expected to fail
398 : : // because of a memory allocation failure.
399 : 173 : (void)hashtable_rehash(ht);
400 : 173 : }
401 : :
402 : :
403 : : void
404 : 15538 : _Py_hashtable_destroy(_Py_hashtable_t *ht)
405 : : {
406 [ + + ]: 4114050 : for (size_t i = 0; i < ht->nbuckets; i++) {
407 : 4098512 : _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);
408 [ + + ]: 5491369 : while (entry) {
409 : 1392857 : _Py_hashtable_entry_t *entry_next = ENTRY_NEXT(entry);
410 : 1392857 : _Py_hashtable_destroy_entry(ht, entry);
411 : 1392857 : entry = entry_next;
412 : : }
413 : : }
414 : :
415 : 15538 : ht->alloc.free(ht->buckets);
416 : 15538 : ht->alloc.free(ht);
417 : 15538 : }
|
