botan: Add support for Ed25519 keys
[strongswan.git] / src / libstrongswan / collections / hashtable.c
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 }