Version bump to 5.9.4
[strongswan.git] / src / libstrongswan / collections / hashtable.c
1 /*
2 * Copyright (C) 2008-2020 Tobias Brunner
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * for more details.
14 */
15
16 #include "hashtable.h"
17 #include "hashtable_profiler.h"
18
19 #include <utils/chunk.h>
20 #include <utils/debug.h>
21
22 /** The minimum size of the hash table (MUST be a power of 2) */
23 #define MIN_SIZE 8
24 /** The maximum size of the hash table (MUST be a power of 2) */
25 #define MAX_SIZE (1 << 30)
26
27 /** Determine the capacity/maximum load of the table (higher values cause
28 * more collisions, lower values increase the memory overhead) */
29 #define CAPACITY(size) (size / 3 * 2)
30 /** Factor for the new table size based on the number of items when resizing,
31 * with the above load factor this results in doubling the size when growing */
32 #define RESIZE_FACTOR 3
33
34 /**
35 * A note about these parameters:
36 *
37 * The maximum number of items that can be stored in this implementation
38 * is MAX_COUNT = CAPACITY(MAX_SIZE).
39 * Since we use u_int throughout, MAX_COUNT * RESIZE_FACTOR must not overflow
40 * this type.
41 */
42 #if (UINT_MAX / RESIZE_FACTOR < CAPACITY(MAX_SIZE))
43 #error Hahstable parameters invalid!
44 #endif
45
46 typedef struct pair_t pair_t;
47
48 /**
49 * This pair holds a pointer to the key and value it represents.
50 */
51 struct pair_t {
52
53 /**
54 * Key of a hash table item.
55 */
56 const void *key;
57
58 /**
59 * Value of a hash table item.
60 */
61 void *value;
62
63 /**
64 * Cached hash (used in case of a resize).
65 */
66 u_int hash;
67 };
68
69 typedef struct private_hashtable_t private_hashtable_t;
70
71 /**
72 * Private data of a hashtable_t object.
73 *
74 */
75 struct private_hashtable_t {
76
77 /**
78 * Public part of hash table.
79 */
80 hashtable_t public;
81
82 /**
83 * The number of items in the hash table.
84 */
85 u_int count;
86
87 /**
88 * The current size of the hash table (always a power of 2).
89 */
90 u_int size;
91
92 /**
93 * The current mask to calculate the row index (size - 1).
94 */
95 u_int mask;
96
97 /**
98 * All items in the order they were inserted (removed items are marked by
99 * setting the key to NULL until resized).
100 */
101 pair_t *items;
102
103 /**
104 * Number of available slots in the array above and the table in general,
105 * is set to CAPACITY(size) when the hash table is initialized.
106 */
107 u_int capacity;
108
109 /**
110 * Number of used slots in the array above.
111 */
112 u_int items_count;
113
114 /**
115 * Hash table with indices into the array above. The type depends on the
116 * current capacity.
117 */
118 void *table;
119
120 /**
121 * The hashing function.
122 */
123 hashtable_hash_t hash;
124
125 /**
126 * The equality function.
127 */
128 hashtable_equals_t equals;
129
130 /**
131 * Profiling data
132 */
133 hashtable_profile_t profile;
134 };
135
136 typedef struct private_enumerator_t private_enumerator_t;
137
138 /**
139 * Hash table enumerator implementation
140 */
141 struct private_enumerator_t {
142
143 /**
144 * Implements enumerator interface
145 */
146 enumerator_t enumerator;
147
148 /**
149 * Associated hash table
150 */
151 private_hashtable_t *table;
152
153 /**
154 * Current index
155 */
156 u_int index;
157 };
158
159 /*
160 * Described in header
161 */
162 u_int hashtable_hash_ptr(const void *key)
163 {
164 return chunk_hash(chunk_from_thing(key));
165 }
166
167 /*
168 * Described in header
169 */
170 u_int hashtable_hash_str(const void *key)
171 {
172 return chunk_hash(chunk_from_str((char*)key));
173 }
174
175 /*
176 * Described in header
177 */
178 bool hashtable_equals_ptr(const void *key, const void *other_key)
179 {
180 return key == other_key;
181 }
182
183 /*
184 * Described in header
185 */
186 bool hashtable_equals_str(const void *key, const void *other_key)
187 {
188 return streq(key, other_key);
189 }
190
191 /**
192 * Returns the index stored in the given bucket. If the bucket is empty,
193 * 0 is returned.
194 */
195 static inline u_int get_index(private_hashtable_t *this, u_int row)
196 {
197 if (this->capacity <= 0xff)
198 {
199 return ((uint8_t*)this->table)[row];
200 }
201 else if (this->capacity <= 0xffff)
202 {
203 return ((uint16_t*)this->table)[row];
204 }
205 return ((u_int*)this->table)[row];
206 }
207
208 /**
209 * Set the index stored in the given bucket. Set to 0 to clear a bucket.
210 */
211 static inline void set_index(private_hashtable_t *this, u_int row, u_int index)
212 {
213 if (this->capacity <= 0xff)
214 {
215 ((uint8_t*)this->table)[row] = index;
216 }
217 else if (this->capacity <= 0xffff)
218 {
219 ((uint16_t*)this->table)[row] = index;
220 }
221 else
222 {
223 ((u_int*)this->table)[row] = index;
224 }
225 }
226
227 /**
228 * This function returns the next-highest power of two for the given number.
229 * The algorithm works by setting all bits on the right-hand side of the most
230 * significant 1 to 1 and then increments the whole number so it rolls over
231 * to the nearest power of two. Note: returns 0 for n == 0
232 *
233 * Also used by hashlist_t.
234 */
235 u_int hashtable_get_nearest_powerof2(u_int n)
236 {
237 u_int i;
238
239 --n;
240 for (i = 1; i < sizeof(u_int) * 8; i <<= 1)
241 {
242 n |= n >> i;
243 }
244 return ++n;
245 }
246
247 /**
248 * Init hash table to the given size
249 */
250 static void init_hashtable(private_hashtable_t *this, u_int size)
251 {
252 u_int index_size = sizeof(u_int);
253
254 this->size = max(MIN_SIZE, min(size, MAX_SIZE));
255 this->size = hashtable_get_nearest_powerof2(this->size);
256 this->mask = this->size - 1;
257 profile_size(&this->profile, this->size);
258
259 this->capacity = CAPACITY(this->size);
260 this->items = calloc(this->capacity, sizeof(pair_t));
261 this->items_count = 0;
262
263 if (this->capacity <= 0xff)
264 {
265 index_size = sizeof(uint8_t);
266 }
267 else if (this->capacity <= 0xffff)
268 {
269 index_size = sizeof(uint16_t);
270 }
271 this->table = calloc(this->size, index_size);
272 }
273
274 /**
275 * Calculate the next bucket using quadratic probing (the sequence is h(k) + 1,
276 * h(k) + 3, h(k) + 6, h(k) + 10, ...).
277 */
278 static inline u_int get_next(private_hashtable_t *this, u_int row, u_int *p)
279 {
280 *p += 1;
281 return (row + *p) & this->mask;
282 }
283
284 /**
285 * Find the pair with the given key, optionally returns the hash and first empty
286 * or previously used row if the key is not found.
287 */
288 static inline pair_t *find_key(private_hashtable_t *this, const void *key,
289 u_int *out_hash, u_int *out_row)
290 {
291 pair_t *pair;
292 u_int hash, row, p = 0, removed, index;
293 bool found_removed = FALSE;
294
295 if (!this->count && !out_hash && !out_row)
296 {
297 return NULL;
298 }
299
300 lookup_start();
301
302 hash = this->hash(key);
303 row = hash & this->mask;
304 index = get_index(this, row);
305 while (index)
306 {
307 lookup_probing();
308 pair = &this->items[index-1];
309
310 if (!pair->key)
311 {
312 if (!found_removed && out_row)
313 {
314 removed = row;
315 found_removed = TRUE;
316 }
317 }
318 else if (pair->hash == hash && this->equals(key, pair->key))
319 {
320 lookup_success(&this->profile);
321 return pair;
322 }
323 row = get_next(this, row, &p);
324 index = get_index(this, row);
325 }
326 if (out_hash)
327 {
328 *out_hash = hash;
329 }
330 if (out_row)
331 {
332 *out_row = found_removed ? removed : row;
333 }
334 lookup_failure(&this->profile);
335 return NULL;
336 }
337
338 /**
339 * Helper to insert a new item into the table and items array,
340 * returns its new index into the latter.
341 */
342 static inline u_int insert_item(private_hashtable_t *this, u_int row)
343 {
344 u_int index = this->items_count++;
345
346 /* we use 0 to mark unused buckets, so increase the index */
347 set_index(this, row, index + 1);
348 return index;
349 }
350
351 /**
352 * Resize the hash table to the given size and rehash all the elements,
353 * size may be smaller or even the same (e.g. if it's necessary to clear
354 * previously used buckets).
355 */
356 static bool rehash(private_hashtable_t *this, u_int size)
357 {
358 pair_t *old_items, *pair;
359 u_int old_count, i, p, row, index;
360
361 if (size > MAX_SIZE)
362 {
363 return FALSE;
364 }
365
366 old_items = this->items;
367 old_count = this->items_count;
368 free(this->table);
369 init_hashtable(this, size);
370
371 /* no need to do anything if the table is empty and we are just cleaning
372 * up previously used items */
373 if (this->count)
374 {
375 for (i = 0; i < old_count; i++)
376 {
377 pair = &old_items[i];
378
379 if (pair->key)
380 {
381 row = pair->hash & this->mask;
382 index = get_index(this, row);
383 for (p = 0; index;)
384 {
385 row = get_next(this, row, &p);
386 index = get_index(this, row);
387 }
388 index = insert_item(this, row);
389 this->items[index] = *pair;
390 }
391 }
392 }
393 free(old_items);
394 return TRUE;
395 }
396
397 METHOD(hashtable_t, put, void*,
398 private_hashtable_t *this, const void *key, void *value)
399 {
400 void *old_value = NULL;
401 pair_t *pair;
402 u_int index, hash = 0, row = 0;
403
404 if (this->items_count >= this->capacity &&
405 !rehash(this, this->count * RESIZE_FACTOR))
406 {
407 DBG1(DBG_LIB, "!!! FAILED TO RESIZE HASHTABLE TO %u !!!",
408 this->count * RESIZE_FACTOR);
409 return NULL;
410 }
411 pair = find_key(this, key, &hash, &row);
412 if (pair)
413 {
414 old_value = pair->value;
415 pair->value = value;
416 pair->key = key;
417 return old_value;
418 }
419 index = insert_item(this, row);
420 this->items[index] = (pair_t){
421 .hash = hash,
422 .key = key,
423 .value = value,
424 };
425 this->count++;
426 profile_count(&this->profile, this->count);
427 return NULL;
428 }
429
430 METHOD(hashtable_t, get, void*,
431 private_hashtable_t *this, const void *key)
432 {
433 pair_t *pair = find_key(this, key, NULL, NULL);
434 return pair ? pair->value : NULL;
435 }
436
437 /**
438 * Remove the given item from the table, returns the currently stored value.
439 */
440 static void *remove_internal(private_hashtable_t *this, pair_t *pair)
441 {
442 void *value = NULL;
443
444 if (pair)
445 { /* this does not decrease the item count as we keep the previously
446 * used items until the table is rehashed/resized */
447 value = pair->value;
448 pair->key = NULL;
449 this->count--;
450 }
451 return value;
452 }
453
454 METHOD(hashtable_t, remove_, void*,
455 private_hashtable_t *this, const void *key)
456 {
457 pair_t *pair = find_key(this, key, NULL, NULL);
458 return remove_internal(this, pair);
459 }
460
461 METHOD(hashtable_t, remove_at, void,
462 private_hashtable_t *this, private_enumerator_t *enumerator)
463 {
464 if (enumerator->table == this && enumerator->index)
465 { /* the index is already advanced by one */
466 u_int index = enumerator->index - 1;
467 remove_internal(this, &this->items[index]);
468 }
469 }
470
471 METHOD(hashtable_t, get_count, u_int,
472 private_hashtable_t *this)
473 {
474 return this->count;
475 }
476
477 METHOD(enumerator_t, enumerate, bool,
478 private_enumerator_t *this, va_list args)
479 {
480 const void **key;
481 void **value;
482 pair_t *pair;
483
484 VA_ARGS_VGET(args, key, value);
485
486 while (this->index < this->table->items_count)
487 {
488 pair = &this->table->items[this->index++];
489 if (pair->key)
490 {
491 if (key)
492 {
493 *key = pair->key;
494 }
495 if (value)
496 {
497 *value = pair->value;
498 }
499 return TRUE;
500 }
501 }
502 return FALSE;
503 }
504
505 METHOD(hashtable_t, create_enumerator, enumerator_t*,
506 private_hashtable_t *this)
507 {
508 private_enumerator_t *enumerator;
509
510 INIT(enumerator,
511 .enumerator = {
512 .enumerate = enumerator_enumerate_default,
513 .venumerate = _enumerate,
514 .destroy = (void*)free,
515 },
516 .table = this,
517 );
518 return &enumerator->enumerator;
519 }
520
521 static void destroy_internal(private_hashtable_t *this,
522 void (*fn)(void*,const void*))
523 {
524 pair_t *pair;
525 u_int i;
526
527 profiler_cleanup(&this->profile, this->count, this->size);
528
529 if (fn)
530 {
531 for (i = 0; i < this->items_count; i++)
532 {
533 pair = &this->items[i];
534 if (pair->key)
535 {
536 fn(pair->value, pair->key);
537 }
538 }
539 }
540 free(this->items);
541 free(this->table);
542 free(this);
543 }
544
545 METHOD(hashtable_t, destroy, void,
546 private_hashtable_t *this)
547 {
548 destroy_internal(this, NULL);
549 }
550
551 METHOD(hashtable_t, destroy_function, void,
552 private_hashtable_t *this, void (*fn)(void*,const void*))
553 {
554 destroy_internal(this, fn);
555 }
556
557 /*
558 * Described in header.
559 */
560 hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
561 u_int size)
562 {
563 private_hashtable_t *this;
564
565 INIT(this,
566 .public = {
567 .put = _put,
568 .get = _get,
569 .remove = _remove_,
570 .remove_at = (void*)_remove_at,
571 .get_count = _get_count,
572 .create_enumerator = _create_enumerator,
573 .destroy = _destroy,
574 .destroy_function = _destroy_function,
575 },
576 .hash = hash,
577 .equals = equals,
578 );
579
580 init_hashtable(this, size);
581
582 profiler_init(&this->profile, 2);
583
584 return &this->public;
585 }