/src/strongswan/src/libstrongswan/collections/hashlist.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright (C) 2008-2020 Tobias Brunner |
3 | | * |
4 | | * Copyright (C) secunet Security Networks AG |
5 | | * |
6 | | * This program is free software; you can redistribute it and/or modify it |
7 | | * under the terms of the GNU General Public License as published by the |
8 | | * Free Software Foundation; either version 2 of the License, or (at your |
9 | | * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. |
10 | | * |
11 | | * This program is distributed in the hope that it will be useful, but |
12 | | * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
13 | | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | | * for more details. |
15 | | */ |
16 | | |
17 | | #include "hashtable.h" |
18 | | #include "hashtable_profiler.h" |
19 | | |
20 | | #include <utils/chunk.h> |
21 | | #include <utils/debug.h> |
22 | | #ifdef HASHTABLE_PROFILER |
23 | | #include <utils/backtrace.h> |
24 | | #endif |
25 | | |
26 | | /** The minimum size of the hash table (MUST be a power of 2) */ |
27 | | #define MIN_SIZE 8 |
28 | | /** The maximum size of the hash table (MUST be a power of 2) */ |
29 | 3.51k | #define MAX_SIZE (1 << 30) |
30 | | |
31 | | /** Maximum load factor before the hash table is resized */ |
32 | 267k | #define LOAD_FACTOR 0.75f |
33 | | |
34 | | /** Provided by hashtable_t */ |
35 | | u_int hashtable_get_nearest_powerof2(u_int n); |
36 | | |
37 | | typedef struct pair_t pair_t; |
38 | | |
39 | | /** |
40 | | * This pair holds a pointer to the key and value it represents. |
41 | | */ |
42 | | struct pair_t { |
43 | | |
44 | | /** |
45 | | * Key of a hash table item. |
46 | | */ |
47 | | const void *key; |
48 | | |
49 | | /** |
50 | | * Value of a hash table item. |
51 | | */ |
52 | | void *value; |
53 | | |
54 | | /** |
55 | | * Cached hash (used in case of a resize). |
56 | | */ |
57 | | u_int hash; |
58 | | |
59 | | /** |
60 | | * Next pair in an overflow list. |
61 | | */ |
62 | | pair_t *next; |
63 | | }; |
64 | | |
65 | | typedef struct private_hashlist_t private_hashlist_t; |
66 | | |
67 | | /** |
68 | | * Private data of a hashlist_t object. |
69 | | */ |
70 | | struct private_hashlist_t { |
71 | | |
72 | | /** |
73 | | * Public interface. |
74 | | */ |
75 | | hashlist_t public; |
76 | | |
77 | | /** |
78 | | * The number of items in the hash table. |
79 | | */ |
80 | | u_int count; |
81 | | |
82 | | /** |
83 | | * The current size of the hash table (always a power of 2). |
84 | | */ |
85 | | u_int size; |
86 | | |
87 | | /** |
88 | | * The current mask to calculate the row index (size - 1). |
89 | | */ |
90 | | u_int mask; |
91 | | |
92 | | /** |
93 | | * The actual table. |
94 | | */ |
95 | | pair_t **table; |
96 | | |
97 | | /** |
98 | | * The hashing function. |
99 | | */ |
100 | | hashtable_hash_t hash; |
101 | | |
102 | | /** |
103 | | * The equality function. |
104 | | */ |
105 | | hashtable_equals_t equals; |
106 | | |
107 | | /** |
108 | | * Alternative comparison function. |
109 | | */ |
110 | | hashtable_cmp_t cmp; |
111 | | |
112 | | /** |
113 | | * Profiling information |
114 | | */ |
115 | | hashtable_profile_t profile; |
116 | | }; |
117 | | |
118 | | typedef struct private_enumerator_t private_enumerator_t; |
119 | | |
120 | | /** |
121 | | * Hash table enumerator implementation |
122 | | */ |
123 | | struct private_enumerator_t { |
124 | | |
125 | | /** |
126 | | * Implements enumerator interface. |
127 | | */ |
128 | | enumerator_t enumerator; |
129 | | |
130 | | /** |
131 | | * Associated hash table. |
132 | | */ |
133 | | private_hashlist_t *table; |
134 | | |
135 | | /** |
136 | | * Current row index. |
137 | | */ |
138 | | u_int row; |
139 | | |
140 | | /** |
141 | | * Number of remaining items to enumerate. |
142 | | */ |
143 | | u_int count; |
144 | | |
145 | | /** |
146 | | * Current pair. |
147 | | */ |
148 | | pair_t *current; |
149 | | |
150 | | /** |
151 | | * Previous pair (used by remove_at). |
152 | | */ |
153 | | pair_t *prev; |
154 | | }; |
155 | | |
156 | | /** |
157 | | * Init hash table parameters |
158 | | */ |
159 | | static void init_hashtable(private_hashlist_t *this, u_int size) |
160 | 7.03k | { |
161 | 7.03k | size = max(MIN_SIZE, min(size, MAX_SIZE)); |
162 | 7.03k | this->size = hashtable_get_nearest_powerof2(size); |
163 | 7.03k | this->mask = this->size - 1; |
164 | 7.03k | profile_size(&this->profile, this->size); |
165 | | |
166 | 7.03k | this->table = calloc(this->size, sizeof(pair_t*)); |
167 | 7.03k | } |
168 | | |
169 | | /** |
170 | | * Insert an item into a bucket. |
171 | | */ |
172 | | static inline void insert_pair(private_hashlist_t *this, pair_t *to_insert, |
173 | | pair_t *prev) |
174 | 435k | { |
175 | 435k | u_int row; |
176 | | |
177 | 435k | if (prev) |
178 | 119k | { |
179 | 119k | to_insert->next = prev->next; |
180 | 119k | prev->next = to_insert; |
181 | 119k | } |
182 | 316k | else |
183 | 316k | { |
184 | 316k | row = to_insert->hash & this->mask; |
185 | 316k | to_insert->next = this->table[row]; |
186 | 316k | this->table[row] = to_insert; |
187 | 316k | } |
188 | 435k | } |
189 | | |
190 | | /** |
191 | | * Double the size of the hash table and rehash all the elements. |
192 | | */ |
193 | | static void rehash(private_hashlist_t *this) |
194 | 3.51k | { |
195 | 3.51k | pair_t **old_table, *to_move, *pair, *next; |
196 | 3.51k | u_int row, old_size; |
197 | | |
198 | 3.51k | if (this->size >= MAX_SIZE) |
199 | 0 | { |
200 | 0 | return; |
201 | 0 | } |
202 | | |
203 | 3.51k | old_size = this->size; |
204 | 3.51k | old_table = this->table; |
205 | | |
206 | 3.51k | init_hashtable(this, old_size << 1); |
207 | | |
208 | 228k | for (row = 0; row < old_size; row++) |
209 | 224k | { |
210 | 224k | to_move = old_table[row]; |
211 | 393k | while (to_move) |
212 | 168k | { |
213 | 168k | pair_t *prev = NULL; |
214 | | |
215 | 168k | pair = this->table[to_move->hash & this->mask]; |
216 | 203k | while (pair) |
217 | 35.1k | { |
218 | 35.1k | if (this->cmp && this->cmp(to_move->key, pair->key) < 0) |
219 | 0 | { |
220 | 0 | break; |
221 | 0 | } |
222 | 35.1k | prev = pair; |
223 | 35.1k | pair = pair->next; |
224 | 35.1k | } |
225 | 168k | next = to_move->next; |
226 | 168k | insert_pair(this, to_move, prev); |
227 | 168k | to_move = next; |
228 | 168k | } |
229 | 224k | } |
230 | 3.51k | free(old_table); |
231 | 3.51k | } |
232 | | |
233 | | /** |
234 | | * Find the pair with the given key, optionally returning the hash and previous |
235 | | * (or last) pair in the bucket. |
236 | | */ |
237 | | static inline pair_t *find_key(private_hashlist_t *this, const void *key, |
238 | | hashtable_equals_t equals, u_int *out_hash, |
239 | | pair_t **out_prev) |
240 | 2.12M | { |
241 | 2.12M | pair_t *pair, *prev = NULL; |
242 | 2.12M | bool use_callback = equals != NULL; |
243 | 2.12M | u_int hash; |
244 | | |
245 | 2.12M | if (!this->count && !out_hash) |
246 | 3.51k | { /* no need to calculate the hash if not requested */ |
247 | 3.51k | return NULL; |
248 | 3.51k | } |
249 | | |
250 | 2.12M | equals = equals ?: this->equals; |
251 | 2.12M | hash = this->hash(key); |
252 | 2.12M | if (out_hash) |
253 | 267k | { |
254 | 267k | *out_hash = hash; |
255 | 267k | } |
256 | | |
257 | 2.12M | lookup_start(); |
258 | | |
259 | 2.12M | pair = this->table[hash & this->mask]; |
260 | 3.32M | while (pair) |
261 | 1.98M | { |
262 | 1.98M | lookup_probing(); |
263 | | /* when keys are sorted, we compare all items so we can abort earlier |
264 | | * even if the hash does not match, but only as long as we don't |
265 | | * have a callback */ |
266 | 1.98M | if (!use_callback && this->cmp) |
267 | 0 | { |
268 | 0 | int cmp = this->cmp(key, pair->key); |
269 | 0 | if (cmp == 0) |
270 | 0 | { |
271 | 0 | break; |
272 | 0 | } |
273 | 0 | else if (cmp < 0) |
274 | 0 | { /* no need to continue as the key we search is smaller */ |
275 | 0 | pair = NULL; |
276 | 0 | break; |
277 | 0 | } |
278 | 0 | } |
279 | 1.98M | else if (hash == pair->hash && equals(key, pair->key)) |
280 | 780k | { |
281 | 780k | break; |
282 | 780k | } |
283 | 1.20M | prev = pair; |
284 | 1.20M | pair = pair->next; |
285 | 1.20M | } |
286 | 2.12M | if (out_prev) |
287 | 534k | { |
288 | 534k | *out_prev = prev; |
289 | 534k | } |
290 | 2.12M | if (pair) |
291 | 780k | { |
292 | 780k | lookup_success(&this->profile); |
293 | 780k | } |
294 | 1.34M | else |
295 | 1.34M | { |
296 | 1.34M | lookup_failure(&this->profile); |
297 | 1.34M | } |
298 | 2.12M | return pair; |
299 | 2.12M | } |
300 | | |
301 | | METHOD(hashtable_t, put, void*, |
302 | | private_hashlist_t *this, const void *key, void *value) |
303 | 267k | { |
304 | 267k | void *old_value = NULL; |
305 | 267k | pair_t *pair, *prev = NULL; |
306 | 267k | u_int hash; |
307 | | |
308 | 267k | if (this->count >= this->size * LOAD_FACTOR) |
309 | 3.51k | { |
310 | 3.51k | rehash(this); |
311 | 3.51k | } |
312 | | |
313 | 267k | pair = find_key(this, key, NULL, &hash, &prev); |
314 | 267k | if (pair) |
315 | 0 | { |
316 | 0 | old_value = pair->value; |
317 | 0 | pair->value = value; |
318 | 0 | pair->key = key; |
319 | 0 | } |
320 | 267k | else |
321 | 267k | { |
322 | 267k | INIT(pair, |
323 | 267k | .key = key, |
324 | 267k | .value = value, |
325 | 267k | .hash = hash, |
326 | 267k | ); |
327 | 267k | insert_pair(this, pair, prev); |
328 | 267k | this->count++; |
329 | 267k | profile_count(&this->profile, this->count); |
330 | 267k | } |
331 | 267k | return old_value; |
332 | 267k | } |
333 | | |
334 | | |
335 | | METHOD(hashtable_t, get, void*, |
336 | | private_hashlist_t *this, const void *key) |
337 | 618k | { |
338 | 618k | pair_t *pair = find_key(this, key, NULL, NULL, NULL); |
339 | 618k | return pair ? pair->value : NULL; |
340 | 618k | } |
341 | | |
342 | | METHOD(hashlist_t, get_match, void*, |
343 | | private_hashlist_t *this, const void *key, hashtable_equals_t match) |
344 | 973k | { |
345 | 973k | pair_t *pair = find_key(this, key, match, NULL, NULL); |
346 | 973k | return pair ? pair->value : NULL; |
347 | 973k | } |
348 | | |
349 | | METHOD(hashtable_t, remove_, void*, |
350 | | private_hashlist_t *this, const void *key) |
351 | 267k | { |
352 | 267k | void *value = NULL; |
353 | 267k | pair_t *pair, *prev = NULL; |
354 | | |
355 | 267k | pair = find_key(this, key, NULL, NULL, &prev); |
356 | 267k | if (pair) |
357 | 267k | { |
358 | 267k | if (prev) |
359 | 28.1k | { |
360 | 28.1k | prev->next = pair->next; |
361 | 28.1k | } |
362 | 239k | else |
363 | 239k | { |
364 | 239k | this->table[pair->hash & this->mask] = pair->next; |
365 | 239k | } |
366 | 267k | value = pair->value; |
367 | 267k | free(pair); |
368 | 267k | this->count--; |
369 | 267k | } |
370 | 267k | return value; |
371 | 267k | } |
372 | | |
373 | | METHOD(hashtable_t, remove_at, void, |
374 | | private_hashlist_t *this, private_enumerator_t *enumerator) |
375 | 0 | { |
376 | 0 | if (enumerator->table == this && enumerator->current) |
377 | 0 | { |
378 | 0 | pair_t *current = enumerator->current; |
379 | 0 | if (enumerator->prev) |
380 | 0 | { |
381 | 0 | enumerator->prev->next = current->next; |
382 | 0 | } |
383 | 0 | else |
384 | 0 | { |
385 | 0 | this->table[enumerator->row] = current->next; |
386 | 0 | } |
387 | 0 | enumerator->current = enumerator->prev; |
388 | 0 | free(current); |
389 | 0 | this->count--; |
390 | 0 | } |
391 | 0 | } |
392 | | |
393 | | METHOD(hashtable_t, get_count, u_int, |
394 | | private_hashlist_t *this) |
395 | 0 | { |
396 | 0 | return this->count; |
397 | 0 | } |
398 | | |
399 | | METHOD(enumerator_t, enumerate, bool, |
400 | | private_enumerator_t *this, va_list args) |
401 | 0 | { |
402 | 0 | const void **key; |
403 | 0 | void **value; |
404 | |
|
405 | 0 | VA_ARGS_VGET(args, key, value); |
406 | |
|
407 | 0 | while (this->count && this->row < this->table->size) |
408 | 0 | { |
409 | 0 | this->prev = this->current; |
410 | 0 | if (this->current) |
411 | 0 | { |
412 | 0 | this->current = this->current->next; |
413 | 0 | } |
414 | 0 | else |
415 | 0 | { |
416 | 0 | this->current = this->table->table[this->row]; |
417 | 0 | } |
418 | 0 | if (this->current) |
419 | 0 | { |
420 | 0 | if (key) |
421 | 0 | { |
422 | 0 | *key = this->current->key; |
423 | 0 | } |
424 | 0 | if (value) |
425 | 0 | { |
426 | 0 | *value = this->current->value; |
427 | 0 | } |
428 | 0 | this->count--; |
429 | 0 | return TRUE; |
430 | 0 | } |
431 | 0 | this->row++; |
432 | 0 | } |
433 | 0 | return FALSE; |
434 | 0 | } |
435 | | |
436 | | METHOD(hashtable_t, create_enumerator, enumerator_t*, |
437 | | private_hashlist_t *this) |
438 | 0 | { |
439 | 0 | private_enumerator_t *enumerator; |
440 | |
|
441 | 0 | INIT(enumerator, |
442 | 0 | .enumerator = { |
443 | 0 | .enumerate = enumerator_enumerate_default, |
444 | 0 | .venumerate = _enumerate, |
445 | 0 | .destroy = (void*)free, |
446 | 0 | }, |
447 | 0 | .table = this, |
448 | 0 | .count = this->count, |
449 | 0 | ); |
450 | |
|
451 | 0 | return &enumerator->enumerator; |
452 | 0 | } |
453 | | |
454 | | static void destroy_internal(private_hashlist_t *this, |
455 | | void (*fn)(void*,const void*)) |
456 | 3.51k | { |
457 | 3.51k | pair_t *pair, *next; |
458 | 3.51k | u_int row; |
459 | | |
460 | 3.51k | profiler_cleanup(&this->profile, this->count, this->size); |
461 | | |
462 | 453k | for (row = 0; row < this->size; row++) |
463 | 449k | { |
464 | 449k | pair = this->table[row]; |
465 | 449k | while (pair) |
466 | 0 | { |
467 | 0 | if (fn) |
468 | 0 | { |
469 | 0 | fn(pair->value, pair->key); |
470 | 0 | } |
471 | 0 | next = pair->next; |
472 | 0 | free(pair); |
473 | 0 | pair = next; |
474 | 0 | } |
475 | 449k | } |
476 | 3.51k | free(this->table); |
477 | 3.51k | free(this); |
478 | 3.51k | } |
479 | | |
480 | | METHOD2(hashlist_t, hashtable_t, destroy, void, |
481 | | private_hashlist_t *this) |
482 | 3.51k | { |
483 | 3.51k | destroy_internal(this, NULL); |
484 | 3.51k | } |
485 | | |
486 | | METHOD(hashtable_t, destroy_function, void, |
487 | | private_hashlist_t *this, void (*fn)(void*,const void*)) |
488 | 0 | { |
489 | 0 | destroy_internal(this, fn); |
490 | 0 | } |
491 | | |
492 | | /** |
493 | | * Create a hash list |
494 | | */ |
495 | | static private_hashlist_t *hashlist_create_internal(hashtable_hash_t hash, |
496 | | u_int size) |
497 | 3.51k | { |
498 | 3.51k | private_hashlist_t *this; |
499 | | |
500 | 3.51k | INIT(this, |
501 | 3.51k | .public = { |
502 | 3.51k | .ht = { |
503 | 3.51k | .put = _put, |
504 | 3.51k | .get = _get, |
505 | 3.51k | .remove = _remove_, |
506 | 3.51k | .remove_at = (void*)_remove_at, |
507 | 3.51k | .get_count = _get_count, |
508 | 3.51k | .create_enumerator = _create_enumerator, |
509 | 3.51k | .destroy = _destroy, |
510 | 3.51k | .destroy_function = _destroy_function, |
511 | 3.51k | }, |
512 | 3.51k | .get_match = _get_match, |
513 | 3.51k | .destroy = _destroy, |
514 | 3.51k | }, |
515 | 3.51k | .hash = hash, |
516 | 3.51k | ); |
517 | | |
518 | 3.51k | init_hashtable(this, size); |
519 | | |
520 | 3.51k | profiler_init(&this->profile, 3); |
521 | | |
522 | 3.51k | return this; |
523 | 3.51k | } |
524 | | |
525 | | /* |
526 | | * Described in header |
527 | | */ |
528 | | hashlist_t *hashlist_create(hashtable_hash_t hash, hashtable_equals_t equals, |
529 | | u_int size) |
530 | 3.51k | { |
531 | 3.51k | private_hashlist_t *this = hashlist_create_internal(hash, size); |
532 | | |
533 | 3.51k | this->equals = equals; |
534 | | |
535 | 3.51k | return &this->public; |
536 | 3.51k | } |
537 | | |
538 | | /* |
539 | | * Described in header |
540 | | */ |
541 | | hashlist_t *hashlist_create_sorted(hashtable_hash_t hash, |
542 | | hashtable_cmp_t cmp, u_int size) |
543 | 0 | { |
544 | 0 | private_hashlist_t *this = hashlist_create_internal(hash, size); |
545 | |
|
546 | 0 | this->cmp = cmp; |
547 | |
|
548 | 0 | return &this->public; |
549 | 0 | } |