![[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|
Return to hashtable.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections |
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: }