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