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