Annotation of embedaddon/strongswan/src/libstrongswan/collections/hashlist.c, revision 1.1
1.1 ! misho 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashlist.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