Annotation of embedaddon/strongswan/src/libstrongswan/collections/hashtable.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Copyright (C) 2008-2014 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:
! 17: #include "hashtable.h"
! 18:
! 19: #include <utils/chunk.h>
! 20:
! 21: /** The maximum capacity of the hash table (MUST be a power of 2) */
! 22: #define MAX_CAPACITY (1 << 30)
! 23:
! 24: typedef struct pair_t pair_t;
! 25:
! 26: /**
! 27: * This pair holds a pointer to the key and value it represents.
! 28: */
! 29: struct pair_t {
! 30: /**
! 31: * Key of a hash table item.
! 32: */
! 33: const void *key;
! 34:
! 35: /**
! 36: * Value of a hash table item.
! 37: */
! 38: void *value;
! 39:
! 40: /**
! 41: * Cached hash (used in case of a resize).
! 42: */
! 43: u_int hash;
! 44:
! 45: /**
! 46: * Next pair in an overflow list.
! 47: */
! 48: pair_t *next;
! 49: };
! 50:
! 51: /**
! 52: * Creates an empty pair object.
! 53: */
! 54: static inline pair_t *pair_create(const void *key, void *value, u_int hash)
! 55: {
! 56: pair_t *this;
! 57:
! 58: INIT(this,
! 59: .key = key,
! 60: .value = value,
! 61: .hash = hash,
! 62: );
! 63:
! 64: return this;
! 65: }
! 66:
! 67: typedef struct private_hashtable_t private_hashtable_t;
! 68:
! 69: /**
! 70: * Private data of a hashtable_t object.
! 71: *
! 72: */
! 73: struct private_hashtable_t {
! 74: /**
! 75: * Public part of hash table.
! 76: */
! 77: hashtable_t public;
! 78:
! 79: /**
! 80: * The number of items in the hash table.
! 81: */
! 82: u_int count;
! 83:
! 84: /**
! 85: * The current capacity of the hash table (always a power of 2).
! 86: */
! 87: u_int capacity;
! 88:
! 89: /**
! 90: * The current mask to calculate the row index (capacity - 1).
! 91: */
! 92: u_int mask;
! 93:
! 94: /**
! 95: * The load factor.
! 96: */
! 97: float load_factor;
! 98:
! 99: /**
! 100: * The actual table.
! 101: */
! 102: pair_t **table;
! 103:
! 104: /**
! 105: * The hashing function.
! 106: */
! 107: hashtable_hash_t hash;
! 108:
! 109: /**
! 110: * The equality function.
! 111: */
! 112: hashtable_equals_t equals;
! 113: };
! 114:
! 115: typedef struct private_enumerator_t private_enumerator_t;
! 116:
! 117: /**
! 118: * hash table enumerator implementation
! 119: */
! 120: struct private_enumerator_t {
! 121:
! 122: /**
! 123: * implements enumerator interface
! 124: */
! 125: enumerator_t enumerator;
! 126:
! 127: /**
! 128: * associated hash table
! 129: */
! 130: private_hashtable_t *table;
! 131:
! 132: /**
! 133: * current row index
! 134: */
! 135: u_int row;
! 136:
! 137: /**
! 138: * number of remaining items in hashtable
! 139: */
! 140: u_int count;
! 141:
! 142: /**
! 143: * current pair
! 144: */
! 145: pair_t *current;
! 146:
! 147: /**
! 148: * previous pair (used by remove_at)
! 149: */
! 150: pair_t *prev;
! 151: };
! 152:
! 153: /*
! 154: * See header.
! 155: */
! 156: u_int hashtable_hash_ptr(const void *key)
! 157: {
! 158: return chunk_hash(chunk_from_thing(key));
! 159: }
! 160:
! 161: /*
! 162: * See header.
! 163: */
! 164: u_int hashtable_hash_str(const void *key)
! 165: {
! 166: return chunk_hash(chunk_from_str((char*)key));
! 167: }
! 168:
! 169: /*
! 170: * See header.
! 171: */
! 172: bool hashtable_equals_ptr(const void *key, const void *other_key)
! 173: {
! 174: return key == other_key;
! 175: }
! 176:
! 177: /*
! 178: * See header.
! 179: */
! 180: bool hashtable_equals_str(const void *key, const void *other_key)
! 181: {
! 182: return streq(key, other_key);
! 183: }
! 184:
! 185: /**
! 186: * This function returns the next-highest power of two for the given number.
! 187: * The algorithm works by setting all bits on the right-hand side of the most
! 188: * significant 1 to 1 and then increments the whole number so it rolls over
! 189: * to the nearest power of two. Note: returns 0 for n == 0
! 190: */
! 191: static u_int get_nearest_powerof2(u_int n)
! 192: {
! 193: u_int i;
! 194:
! 195: --n;
! 196: for (i = 1; i < sizeof(u_int) * 8; i <<= 1)
! 197: {
! 198: n |= n >> i;
! 199: }
! 200: return ++n;
! 201: }
! 202:
! 203: /**
! 204: * Init hash table parameters
! 205: */
! 206: static void init_hashtable(private_hashtable_t *this, u_int capacity)
! 207: {
! 208: capacity = max(1, min(capacity, MAX_CAPACITY));
! 209: this->capacity = get_nearest_powerof2(capacity);
! 210: this->mask = this->capacity - 1;
! 211: this->load_factor = 0.75;
! 212:
! 213: this->table = calloc(this->capacity, sizeof(pair_t*));
! 214: }
! 215:
! 216: /**
! 217: * Double the size of the hash table and rehash all the elements.
! 218: */
! 219: static void rehash(private_hashtable_t *this)
! 220: {
! 221: pair_t **old_table;
! 222: u_int row, old_capacity;
! 223:
! 224: if (this->capacity >= MAX_CAPACITY)
! 225: {
! 226: return;
! 227: }
! 228:
! 229: old_capacity = this->capacity;
! 230: old_table = this->table;
! 231:
! 232: init_hashtable(this, old_capacity << 1);
! 233:
! 234: for (row = 0; row < old_capacity; row++)
! 235: {
! 236: pair_t *pair, *next;
! 237: u_int new_row;
! 238:
! 239: pair = old_table[row];
! 240: while (pair)
! 241: { /* insert pair at the front of new bucket*/
! 242: next = pair->next;
! 243: new_row = pair->hash & this->mask;
! 244: pair->next = this->table[new_row];
! 245: this->table[new_row] = pair;
! 246: pair = next;
! 247: }
! 248: }
! 249: free(old_table);
! 250: }
! 251:
! 252: METHOD(hashtable_t, put, void*,
! 253: private_hashtable_t *this, const void *key, void *value)
! 254: {
! 255: void *old_value = NULL;
! 256: pair_t *pair;
! 257: u_int hash, row;
! 258:
! 259: hash = this->hash(key);
! 260: row = hash & this->mask;
! 261: pair = this->table[row];
! 262: while (pair)
! 263: { /* search existing bucket for key */
! 264: if (this->equals(key, pair->key))
! 265: {
! 266: old_value = pair->value;
! 267: pair->value = value;
! 268: pair->key = key;
! 269: break;
! 270: }
! 271: pair = pair->next;
! 272: }
! 273: if (!pair)
! 274: { /* insert at the front of bucket */
! 275: pair = pair_create(key, value, hash);
! 276: pair->next = this->table[row];
! 277: this->table[row] = pair;
! 278: this->count++;
! 279: }
! 280: if (this->count >= this->capacity * this->load_factor)
! 281: {
! 282: rehash(this);
! 283: }
! 284: return old_value;
! 285: }
! 286:
! 287: static void *get_internal(private_hashtable_t *this, const void *key,
! 288: hashtable_equals_t equals)
! 289: {
! 290: void *value = NULL;
! 291: pair_t *pair;
! 292:
! 293: if (!this->count)
! 294: { /* no need to calculate the hash */
! 295: return NULL;
! 296: }
! 297:
! 298: pair = this->table[this->hash(key) & this->mask];
! 299: while (pair)
! 300: {
! 301: if (equals(key, pair->key))
! 302: {
! 303: value = pair->value;
! 304: break;
! 305: }
! 306: pair = pair->next;
! 307: }
! 308: return value;
! 309: }
! 310:
! 311: METHOD(hashtable_t, get, void*,
! 312: private_hashtable_t *this, const void *key)
! 313: {
! 314: return get_internal(this, key, this->equals);
! 315: }
! 316:
! 317: METHOD(hashtable_t, get_match, void*,
! 318: private_hashtable_t *this, const void *key, hashtable_equals_t match)
! 319: {
! 320: return get_internal(this, key, match);
! 321: }
! 322:
! 323: METHOD(hashtable_t, remove_, void*,
! 324: private_hashtable_t *this, const void *key)
! 325: {
! 326: void *value = NULL;
! 327: pair_t *pair, *prev = NULL;
! 328: u_int row;
! 329:
! 330: row = this->hash(key) & this->mask;
! 331: pair = this->table[row];
! 332: while (pair)
! 333: {
! 334: if (this->equals(key, pair->key))
! 335: {
! 336: if (prev)
! 337: {
! 338: prev->next = pair->next;
! 339: }
! 340: else
! 341: {
! 342: this->table[row] = pair->next;
! 343: }
! 344: value = pair->value;
! 345: this->count--;
! 346: free(pair);
! 347: break;
! 348: }
! 349: prev = pair;
! 350: pair = pair->next;
! 351: }
! 352: return value;
! 353: }
! 354:
! 355: METHOD(hashtable_t, remove_at, void,
! 356: private_hashtable_t *this, private_enumerator_t *enumerator)
! 357: {
! 358: if (enumerator->table == this && enumerator->current)
! 359: {
! 360: pair_t *current = enumerator->current;
! 361: if (enumerator->prev)
! 362: {
! 363: enumerator->prev->next = current->next;
! 364: }
! 365: else
! 366: {
! 367: this->table[enumerator->row] = current->next;
! 368: }
! 369: enumerator->current = enumerator->prev;
! 370: free(current);
! 371: this->count--;
! 372: }
! 373: }
! 374:
! 375: METHOD(hashtable_t, get_count, u_int,
! 376: private_hashtable_t *this)
! 377: {
! 378: return this->count;
! 379: }
! 380:
! 381: METHOD(enumerator_t, enumerate, bool,
! 382: private_enumerator_t *this, va_list args)
! 383: {
! 384: const void **key;
! 385: void **value;
! 386:
! 387: VA_ARGS_VGET(args, key, value);
! 388:
! 389: while (this->count && this->row < this->table->capacity)
! 390: {
! 391: this->prev = this->current;
! 392: if (this->current)
! 393: {
! 394: this->current = this->current->next;
! 395: }
! 396: else
! 397: {
! 398: this->current = this->table->table[this->row];
! 399: }
! 400: if (this->current)
! 401: {
! 402: if (key)
! 403: {
! 404: *key = this->current->key;
! 405: }
! 406: if (value)
! 407: {
! 408: *value = this->current->value;
! 409: }
! 410: this->count--;
! 411: return TRUE;
! 412: }
! 413: this->row++;
! 414: }
! 415: return FALSE;
! 416: }
! 417:
! 418: METHOD(hashtable_t, create_enumerator, enumerator_t*,
! 419: private_hashtable_t *this)
! 420: {
! 421: private_enumerator_t *enumerator;
! 422:
! 423: INIT(enumerator,
! 424: .enumerator = {
! 425: .enumerate = enumerator_enumerate_default,
! 426: .venumerate = _enumerate,
! 427: .destroy = (void*)free,
! 428: },
! 429: .table = this,
! 430: .count = this->count,
! 431: );
! 432:
! 433: return &enumerator->enumerator;
! 434: }
! 435:
! 436: static void destroy_internal(private_hashtable_t *this,
! 437: void (*fn)(void*,const void*))
! 438: {
! 439: pair_t *pair, *next;
! 440: u_int row;
! 441:
! 442: for (row = 0; row < this->capacity; row++)
! 443: {
! 444: pair = this->table[row];
! 445: while (pair)
! 446: {
! 447: if (fn)
! 448: {
! 449: fn(pair->value, pair->key);
! 450: }
! 451: next = pair->next;
! 452: free(pair);
! 453: pair = next;
! 454: }
! 455: }
! 456: free(this->table);
! 457: free(this);
! 458: }
! 459:
! 460: METHOD(hashtable_t, destroy, void,
! 461: private_hashtable_t *this)
! 462: {
! 463: destroy_internal(this, NULL);
! 464: }
! 465:
! 466: METHOD(hashtable_t, destroy_function, void,
! 467: private_hashtable_t *this, void (*fn)(void*,const void*))
! 468: {
! 469: destroy_internal(this, fn);
! 470: }
! 471:
! 472: /*
! 473: * Described in header.
! 474: */
! 475: hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
! 476: u_int capacity)
! 477: {
! 478: private_hashtable_t *this;
! 479:
! 480: INIT(this,
! 481: .public = {
! 482: .put = _put,
! 483: .get = _get,
! 484: .get_match = _get_match,
! 485: .remove = _remove_,
! 486: .remove_at = (void*)_remove_at,
! 487: .get_count = _get_count,
! 488: .create_enumerator = _create_enumerator,
! 489: .destroy = _destroy,
! 490: .destroy_function = _destroy_function,
! 491: },
! 492: .hash = hash,
! 493: .equals = equals,
! 494: );
! 495:
! 496: init_hashtable(this, capacity);
! 497:
! 498: return &this->public;
! 499: }
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