hashtable: add common hashtable hash/equals functions for pointer/string keys
[strongswan.git] / src / libstrongswan / collections / hashtable.c
1 /*
2 * Copyright (C) 2008-2012 Tobias Brunner
3 * 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 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(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(void *key)
157 {
158 return chunk_hash(chunk_from_thing(key));
159 }
160
161 /*
162 * See header.
163 */
164 u_int hashtable_hash_str(void *key)
165 {
166 return chunk_hash(chunk_from_str((char*)key));
167 }
168
169 /*
170 * See header.
171 */
172 bool hashtable_equals_ptr(void *key, void *other_key)
173 {
174 return key == other_key;
175 }
176
177 /*
178 * See header.
179 */
180 bool hashtable_equals_str(void *key, 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, 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, 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, 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, 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, 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, void **key, void **value)
383 {
384 while (this->count && this->row < this->table->capacity)
385 {
386 this->prev = this->current;
387 if (this->current)
388 {
389 this->current = this->current->next;
390 }
391 else
392 {
393 this->current = this->table->table[this->row];
394 }
395 if (this->current)
396 {
397 if (key)
398 {
399 *key = this->current->key;
400 }
401 if (value)
402 {
403 *value = this->current->value;
404 }
405 this->count--;
406 return TRUE;
407 }
408 this->row++;
409 }
410 return FALSE;
411 }
412
413 METHOD(hashtable_t, create_enumerator, enumerator_t*,
414 private_hashtable_t *this)
415 {
416 private_enumerator_t *enumerator;
417
418 INIT(enumerator,
419 .enumerator = {
420 .enumerate = (void*)_enumerate,
421 .destroy = (void*)free,
422 },
423 .table = this,
424 .count = this->count,
425 );
426
427 return &enumerator->enumerator;
428 }
429
430 METHOD(hashtable_t, destroy, void,
431 private_hashtable_t *this)
432 {
433 pair_t *pair, *next;
434 u_int row;
435
436 for (row = 0; row < this->capacity; row++)
437 {
438 pair = this->table[row];
439 while (pair)
440 {
441 next = pair->next;
442 free(pair);
443 pair = next;
444 }
445 }
446 free(this->table);
447 free(this);
448 }
449
450 /*
451 * Described in header.
452 */
453 hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
454 u_int capacity)
455 {
456 private_hashtable_t *this;
457
458 INIT(this,
459 .public = {
460 .put = _put,
461 .get = _get,
462 .get_match = _get_match,
463 .remove = _remove_,
464 .remove_at = (void*)_remove_at,
465 .get_count = _get_count,
466 .create_enumerator = _create_enumerator,
467 .destroy = _destroy,
468 },
469 .hash = hash,
470 .equals = equals,
471 );
472
473 init_hashtable(this, capacity);
474
475 return &this->public;
476 }