correct use of calloc in hashtable_t
[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->capacity = get_nearest_powerof2(capacity);
169 this->mask = this->capacity - 1;
170 this->load_factor = 0.75;
171
172 this->table = calloc(this->capacity, sizeof(linked_list_t*));
173 }
174
175 /**
176 * Double the size of the hash table and rehash all the elements.
177 */
178 static void rehash(private_hashtable_t *this)
179 {
180 u_int row;
181 u_int old_capacity = this->capacity;
182 linked_list_t **old_table = this->table;
183
184 if (old_capacity >= MAX_CAPACITY)
185 {
186 return;
187 }
188
189 init_hashtable(this, old_capacity << 1);
190
191 for (row = 0; row < old_capacity; ++row)
192 {
193 linked_list_t *list;
194 if ((list = old_table[row]) != NULL)
195 {
196 pair_t *pair;
197 enumerator_t *enumerator = list->create_enumerator(list);
198 while (enumerator->enumerate(enumerator, &pair))
199 {
200 linked_list_t *new_list;
201 u_int new_row = pair->hash & this->mask;
202 list->remove_at(list, enumerator);
203 if ((new_list = this->table[new_row]) == NULL)
204 {
205 new_list = this->table[new_row] = linked_list_create();
206 }
207 new_list->insert_last(new_list, pair);
208 }
209 enumerator->destroy(enumerator);
210 list->destroy(list);
211 }
212 }
213 free(old_table);
214 }
215
216 /**
217 * Implementation of hashtable_t.put
218 */
219 static void *put(private_hashtable_t *this, void *key, void *value)
220 {
221 linked_list_t *list;
222 void *old_value = NULL;
223 u_int hash = this->hash(key);
224 u_int row = hash & this->mask;
225
226 if ((list = this->table[row]) != NULL)
227 {
228 pair_t *pair;
229 enumerator_t *enumerator = list->create_enumerator(list);
230 while (enumerator->enumerate(enumerator, &pair))
231 {
232 if (pair_equals(pair, this, key))
233 {
234 old_value = pair->value;
235 pair->value = value;
236 break;
237 }
238 }
239 enumerator->destroy(enumerator);
240 }
241 else
242 {
243 list = this->table[row] = linked_list_create();
244 }
245
246 if (!old_value)
247 {
248 list->insert_last(list, pair_create(key, value, hash));
249 this->count++;
250 }
251
252 if (this->count >= this->capacity * this->load_factor)
253 {
254 rehash(this);
255 }
256
257 return old_value;
258 }
259
260 /**
261 * Implementation of hashtable_t.get
262 */
263 static void *get(private_hashtable_t *this, void *key)
264 {
265 void *value = NULL;
266 linked_list_t *list;
267 u_int row = this->hash(key) & this->mask;
268
269 if ((list = this->table[row]) != NULL)
270 {
271 pair_t *pair;
272 if (list->find_first(list, (linked_list_match_t)pair_equals,
273 (void**)&pair, this, key) == SUCCESS)
274 {
275 value = pair->value;
276 }
277 }
278
279 return value;
280 }
281
282 /**
283 * Implementation of hashtable_t.remove
284 */
285 static void *remove(private_hashtable_t *this, void *key)
286 {
287 void *value = NULL;
288 linked_list_t *list;
289 u_int row = this->hash(key) & this->mask;
290
291 if ((list = this->table[row]) != NULL)
292 {
293 pair_t *pair;
294 enumerator_t *enumerator = list->create_enumerator(list);
295 while (enumerator->enumerate(enumerator, &pair))
296 {
297 if (pair_equals(pair, this, key))
298 {
299 list->remove_at(list, enumerator);
300 value = pair->value;
301 this->count--;
302 free(pair);
303 break;
304 }
305 }
306 enumerator->destroy(enumerator);
307 }
308
309 return value;
310 }
311
312 /**
313 * Implementation of hashtable_t.get_count
314 */
315 static u_int get_count(private_hashtable_t *this)
316 {
317 return this->count;
318 }
319
320 /**
321 * Implementation of private_enumerator_t.enumerator.enumerate.
322 */
323 static bool enumerate(private_enumerator_t *this, void **key, void **value)
324 {
325 while (this->row < this->table->capacity)
326 {
327 if (this->current)
328 {
329 pair_t *pair;
330
331 if (this->current->enumerate(this->current, &pair))
332 {
333 if (key)
334 {
335 *key = pair->key;
336 }
337 if (value)
338 {
339 *value = pair->value;
340 }
341 return TRUE;
342 }
343 this->current->destroy(this->current);
344 this->current = NULL;
345 }
346 else
347 {
348 linked_list_t *list;
349
350 if ((list = this->table->table[this->row]) != NULL)
351 {
352 this->current = list->create_enumerator(list);
353 continue;
354 }
355 }
356 this->row++;
357 }
358 return FALSE;
359 }
360
361 /**
362 * Implementation of private_enumerator_t.enumerator.destroy.
363 */
364 static void enumerator_destroy(private_enumerator_t *this)
365 {
366 if (this->current)
367 {
368 this->current->destroy(this->current);
369 }
370 free(this);
371 }
372
373 /**
374 * Implementation of hashtable_t.create_enumerator.
375 */
376 static enumerator_t* create_enumerator(private_hashtable_t *this)
377 {
378 private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
379
380 enumerator->enumerator.enumerate = (void*)enumerate;
381 enumerator->enumerator.destroy = (void*)enumerator_destroy;
382 enumerator->table = this;
383 enumerator->row = 0;
384 enumerator->current = NULL;
385
386 return &enumerator->enumerator;
387 }
388
389 /**
390 * Implementation of hashtable_t.destroy
391 */
392 static void destroy(private_hashtable_t *this)
393 {
394 u_int row;
395 for (row = 0; row < this->capacity; ++row)
396 {
397 linked_list_t *list;
398 if ((list = this->table[row]) != NULL)
399 {
400 list->destroy_function(list, free);
401 }
402 }
403 free(this->table);
404 free(this);
405 }
406
407 /*
408 * Described in header.
409 */
410 hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
411 u_int capacity)
412 {
413 private_hashtable_t *this = malloc_thing(private_hashtable_t);
414
415 this->public.put = (void*(*)(hashtable_t*,void*,void*))put;
416 this->public.get = (void*(*)(hashtable_t*,void*))get;
417 this->public.remove = (void*(*)(hashtable_t*,void*))remove;
418 this->public.get_count = (u_int(*)(hashtable_t*))get_count;
419 this->public.create_enumerator = (enumerator_t*(*)(hashtable_t*))create_enumerator;
420 this->public.destroy = (void(*)(hashtable_t*))destroy;
421
422 this->count = 0;
423 this->capacity = 0;
424 this->mask = 0;
425 this->load_factor = 0;
426 this->table = NULL;
427 this->hash = hash;
428 this->equals = equals;
429
430 init_hashtable(this, capacity);
431
432 return &this->public;
433 }