Annotation of embedaddon/strongswan/src/libstrongswan/collections/hashtable.c, revision 1.1.1.2
1.1 misho 1: /*
1.1.1.2 ! misho 2: * Copyright (C) 2008-2020 Tobias Brunner
1.1 misho 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"
1.1.1.2 ! misho 17: #include "hashtable_profiler.h"
1.1 misho 18:
19: #include <utils/chunk.h>
1.1.1.2 ! misho 20: #include <utils/debug.h>
1.1 misho 21:
1.1.1.2 ! misho 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
1.1 misho 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 {
1.1.1.2 ! misho 52:
1.1 misho 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 {
1.1.1.2 ! misho 76:
1.1 misho 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: /**
1.1.1.2 ! misho 88: * The current size of the hash table (always a power of 2).
1.1 misho 89: */
1.1.1.2 ! misho 90: u_int size;
1.1 misho 91:
92: /**
1.1.1.2 ! misho 93: * The current mask to calculate the row index (size - 1).
1.1 misho 94: */
95: u_int mask;
96:
97: /**
1.1.1.2 ! misho 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.
1.1 misho 106: */
1.1.1.2 ! misho 107: u_int capacity;
1.1 misho 108:
109: /**
1.1.1.2 ! misho 110: * Number of used slots in the array above.
1.1 misho 111: */
1.1.1.2 ! misho 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;
1.1 misho 119:
120: /**
121: * The hashing function.
122: */
123: hashtable_hash_t hash;
124:
125: /**
126: * The equality function.
127: */
128: hashtable_equals_t equals;
1.1.1.2 ! misho 129:
! 130: /**
! 131: * Profiling data
! 132: */
! 133: hashtable_profile_t profile;
1.1 misho 134: };
135:
136: typedef struct private_enumerator_t private_enumerator_t;
137:
138: /**
1.1.1.2 ! misho 139: * Hash table enumerator implementation
1.1 misho 140: */
141: struct private_enumerator_t {
142:
143: /**
1.1.1.2 ! misho 144: * Implements enumerator interface
1.1 misho 145: */
146: enumerator_t enumerator;
147:
148: /**
1.1.1.2 ! misho 149: * Associated hash table
1.1 misho 150: */
151: private_hashtable_t *table;
152:
153: /**
1.1.1.2 ! misho 154: * Current index
1.1 misho 155: */
1.1.1.2 ! misho 156: u_int index;
1.1 misho 157: };
158:
159: /*
1.1.1.2 ! misho 160: * Described in header
1.1 misho 161: */
162: u_int hashtable_hash_ptr(const void *key)
163: {
164: return chunk_hash(chunk_from_thing(key));
165: }
166:
167: /*
1.1.1.2 ! misho 168: * Described in header
1.1 misho 169: */
170: u_int hashtable_hash_str(const void *key)
171: {
172: return chunk_hash(chunk_from_str((char*)key));
173: }
174:
175: /*
1.1.1.2 ! misho 176: * Described in header
1.1 misho 177: */
178: bool hashtable_equals_ptr(const void *key, const void *other_key)
179: {
180: return key == other_key;
181: }
182:
183: /*
1.1.1.2 ! misho 184: * Described in header
1.1 misho 185: */
186: bool hashtable_equals_str(const void *key, const void *other_key)
187: {
188: return streq(key, other_key);
189: }
190:
191: /**
1.1.1.2 ! misho 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: /**
1.1 misho 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
1.1.1.2 ! misho 232: *
! 233: * Also used by hashlist_t.
1.1 misho 234: */
1.1.1.2 ! misho 235: u_int hashtable_get_nearest_powerof2(u_int n)
1.1 misho 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: /**
1.1.1.2 ! misho 248: * Init hash table to the given size
1.1 misho 249: */
1.1.1.2 ! misho 250: static void init_hashtable(private_hashtable_t *this, u_int size)
1.1 misho 251: {
1.1.1.2 ! misho 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: }
1.1 misho 273:
1.1.1.2 ! misho 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;
1.1 misho 282: }
283:
284: /**
1.1.1.2 ! misho 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.
1.1 misho 287: */
1.1.1.2 ! misho 288: static inline pair_t *find_key(private_hashtable_t *this, const void *key,
! 289: u_int *out_hash, u_int *out_row)
1.1 misho 290: {
1.1.1.2 ! misho 291: pair_t *pair;
! 292: u_int hash, row, p = 0, removed, index;
! 293: bool found_removed = FALSE;
1.1 misho 294:
1.1.1.2 ! misho 295: if (!this->count && !out_hash && !out_row)
1.1 misho 296: {
1.1.1.2 ! misho 297: return NULL;
1.1 misho 298: }
299:
1.1.1.2 ! misho 300: lookup_start();
1.1 misho 301:
1.1.1.2 ! misho 302: hash = this->hash(key);
! 303: row = hash & this->mask;
! 304: index = get_index(this, row);
! 305: while (index)
1.1 misho 306: {
1.1.1.2 ! misho 307: lookup_probing();
! 308: pair = &this->items[index-1];
1.1 misho 309:
1.1.1.2 ! misho 310: if (!pair->key)
! 311: {
! 312: if (!found_removed && out_row)
! 313: {
! 314: removed = row;
! 315: found_removed = TRUE;
! 316: }
1.1 misho 317: }
1.1.1.2 ! misho 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;
1.1 misho 333: }
1.1.1.2 ! misho 334: lookup_failure(&this->profile);
! 335: return NULL;
1.1 misho 336: }
337:
1.1.1.2 ! misho 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)
1.1 misho 343: {
1.1.1.2 ! misho 344: u_int index = this->items_count++;
1.1 misho 345:
1.1.1.2 ! misho 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;
1.1 misho 364: }
1.1.1.2 ! misho 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)
1.1 misho 374: {
1.1.1.2 ! misho 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: }
1.1 misho 392: }
1.1.1.2 ! misho 393: free(old_items);
! 394: return TRUE;
1.1 misho 395: }
396:
1.1.1.2 ! misho 397: METHOD(hashtable_t, put, void*,
! 398: private_hashtable_t *this, const void *key, void *value)
1.1 misho 399: {
1.1.1.2 ! misho 400: void *old_value = NULL;
1.1 misho 401: pair_t *pair;
1.1.1.2 ! misho 402: u_int index, hash = 0, row = 0;
1.1 misho 403:
1.1.1.2 ! misho 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);
1.1 misho 409: return NULL;
410: }
1.1.1.2 ! misho 411: pair = find_key(this, key, &hash, &row);
! 412: if (pair)
1.1 misho 413: {
1.1.1.2 ! misho 414: old_value = pair->value;
! 415: pair->value = value;
! 416: pair->key = key;
! 417: return old_value;
1.1 misho 418: }
1.1.1.2 ! misho 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;
1.1 misho 428: }
429:
430: METHOD(hashtable_t, get, void*,
431: private_hashtable_t *this, const void *key)
432: {
1.1.1.2 ! misho 433: pair_t *pair = find_key(this, key, NULL, NULL);
! 434: return pair ? pair->value : NULL;
1.1 misho 435: }
436:
1.1.1.2 ! misho 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)
1.1 misho 441: {
1.1.1.2 ! misho 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;
1.1 misho 452: }
453:
454: METHOD(hashtable_t, remove_, void*,
455: private_hashtable_t *this, const void *key)
456: {
1.1.1.2 ! misho 457: pair_t *pair = find_key(this, key, NULL, NULL);
! 458: return remove_internal(this, pair);
1.1 misho 459: }
460:
461: METHOD(hashtable_t, remove_at, void,
462: private_hashtable_t *this, private_enumerator_t *enumerator)
463: {
1.1.1.2 ! misho 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]);
1.1 misho 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;
1.1.1.2 ! misho 482: pair_t *pair;
1.1 misho 483:
484: VA_ARGS_VGET(args, key, value);
485:
1.1.1.2 ! misho 486: while (this->index < this->table->items_count)
1.1 misho 487: {
1.1.1.2 ! misho 488: pair = &this->table->items[this->index++];
! 489: if (pair->key)
1.1 misho 490: {
491: if (key)
492: {
1.1.1.2 ! misho 493: *key = pair->key;
1.1 misho 494: }
495: if (value)
496: {
1.1.1.2 ! misho 497: *value = pair->value;
1.1 misho 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: {
1.1.1.2 ! misho 524: pair_t *pair;
! 525: u_int i;
1.1 misho 526:
1.1.1.2 ! misho 527: profiler_cleanup(&this->profile, this->count, this->size);
! 528:
! 529: if (fn)
1.1 misho 530: {
1.1.1.2 ! misho 531: for (i = 0; i < this->items_count; i++)
1.1 misho 532: {
1.1.1.2 ! misho 533: pair = &this->items[i];
! 534: if (pair->key)
1.1 misho 535: {
536: fn(pair->value, pair->key);
537: }
538: }
539: }
1.1.1.2 ! misho 540: free(this->items);
1.1 misho 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,
1.1.1.2 ! misho 561: u_int size)
1.1 misho 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:
1.1.1.2 ! misho 580: init_hashtable(this, size);
! 581:
! 582: profiler_init(&this->profile, 2);
1.1 misho 583:
584: return &this->public;
585: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashtable.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections