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