1 /*
2 * Copyright (c) 2009, 2010 Petri Lehtinen <petri@digip.org>
3 *
4 * This library is free software; you can redistribute it and/or modify
5 * it under the terms of the MIT license. See LICENSE for details.
6 */
7
8 #include <config.h>
9
10 #include <stdlib.h>
11 #include "hashtable.h"
12
13 typedef struct hashtable_list list_t;
14 typedef struct hashtable_pair pair_t;
15 typedef struct hashtable_bucket bucket_t;
16
17 #define container_of(ptr_, type_, member_) \
18 ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
19
20 #define list_to_pair(list_) container_of(list_, pair_t, list)
21
list_init(list_t * list)22 static inline void list_init(list_t *list)
23 {
24 list->next = list;
25 list->prev = list;
26 }
27
list_insert(list_t * list,list_t * node)28 static inline void list_insert(list_t *list, list_t *node)
29 {
30 node->next = list;
31 node->prev = list->prev;
32 list->prev->next = node;
33 list->prev = node;
34 }
35
list_remove(list_t * list)36 static inline void list_remove(list_t *list)
37 {
38 list->prev->next = list->next;
39 list->next->prev = list->prev;
40 }
41
bucket_is_empty(hashtable_t * hashtable,bucket_t * bucket)42 static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
43 {
44 return bucket->first == &hashtable->list && bucket->first == bucket->last;
45 }
46
insert_to_bucket(hashtable_t * hashtable,bucket_t * bucket,list_t * list)47 static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,
48 list_t *list)
49 {
50 if(bucket_is_empty(hashtable, bucket))
51 {
52 list_insert(&hashtable->list, list);
53 bucket->first = bucket->last = list;
54 }
55 else
56 {
57 list_insert(bucket->first, list);
58 bucket->first = list;
59 }
60 }
61
62 static unsigned int primes[] = {
63 5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
64 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
65 12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
66 805306457, 1610612741
67 };
68 static const unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
69
num_buckets(hashtable_t * hashtable)70 static inline unsigned int num_buckets(hashtable_t *hashtable)
71 {
72 return primes[hashtable->num_buckets];
73 }
74
75
hashtable_find_pair(hashtable_t * hashtable,bucket_t * bucket,const void * key,unsigned int hash)76 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
77 const void *key, unsigned int hash)
78 {
79 list_t *list;
80 pair_t *pair;
81
82 if(bucket_is_empty(hashtable, bucket))
83 return NULL;
84
85 list = bucket->first;
86 while(1)
87 {
88 pair = list_to_pair(list);
89 if(pair->hash == hash && hashtable->cmp_keys(pair->key, key))
90 return pair;
91
92 if(list == bucket->last)
93 break;
94
95 list = list->next;
96 }
97
98 return NULL;
99 }
100
101 /* returns 0 on success, -1 if key was not found */
hashtable_do_del(hashtable_t * hashtable,const void * key,unsigned int hash)102 static int hashtable_do_del(hashtable_t *hashtable,
103 const void *key, unsigned int hash)
104 {
105 pair_t *pair;
106 bucket_t *bucket;
107 unsigned int index;
108
109 index = hash % num_buckets(hashtable);
110 bucket = &hashtable->buckets[index];
111
112 pair = hashtable_find_pair(hashtable, bucket, key, hash);
113 if(!pair)
114 return -1;
115
116 if(&pair->list == bucket->first && &pair->list == bucket->last)
117 bucket->first = bucket->last = &hashtable->list;
118
119 else if(&pair->list == bucket->first)
120 bucket->first = pair->list.next;
121
122 else if(&pair->list == bucket->last)
123 bucket->last = pair->list.prev;
124
125 list_remove(&pair->list);
126
127 if(hashtable->free_key)
128 hashtable->free_key(pair->key);
129 if(hashtable->free_value)
130 hashtable->free_value(pair->value);
131
132 free(pair);
133 hashtable->size--;
134
135 return 0;
136 }
137
hashtable_do_clear(hashtable_t * hashtable)138 static void hashtable_do_clear(hashtable_t *hashtable)
139 {
140 list_t *list, *next;
141 pair_t *pair;
142
143 for(list = hashtable->list.next; list != &hashtable->list; list = next)
144 {
145 next = list->next;
146 pair = list_to_pair(list);
147 if(hashtable->free_key)
148 hashtable->free_key(pair->key);
149 if(hashtable->free_value)
150 hashtable->free_value(pair->value);
151 free(pair);
152 }
153 }
154
hashtable_do_rehash(hashtable_t * hashtable)155 static int hashtable_do_rehash(hashtable_t *hashtable)
156 {
157 list_t *list, *next;
158 pair_t *pair;
159 unsigned int i, index, new_size;
160
161 free(hashtable->buckets);
162
163 hashtable->num_buckets++;
164 new_size = num_buckets(hashtable);
165
166 hashtable->buckets = malloc(new_size * sizeof(bucket_t));
167 if(!hashtable->buckets)
168 return -1;
169
170 for(i = 0; i < num_buckets(hashtable); i++)
171 {
172 hashtable->buckets[i].first = hashtable->buckets[i].last =
173 &hashtable->list;
174 }
175
176 list = hashtable->list.next;
177 list_init(&hashtable->list);
178
179 for(; list != &hashtable->list; list = next) {
180 next = list->next;
181 pair = list_to_pair(list);
182 index = pair->hash % new_size;
183 insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
184 }
185
186 return 0;
187 }
188
189
hashtable_create(key_hash_fn hash_key,key_cmp_fn cmp_keys,free_fn free_key,free_fn free_value)190 hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
191 free_fn free_key, free_fn free_value)
192 {
193 hashtable_t *hashtable = malloc(sizeof(hashtable_t));
194 if(!hashtable)
195 return NULL;
196
197 if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value))
198 {
199 free(hashtable);
200 return NULL;
201 }
202
203 return hashtable;
204 }
205
hashtable_destroy(hashtable_t * hashtable)206 void hashtable_destroy(hashtable_t *hashtable)
207 {
208 hashtable_close(hashtable);
209 free(hashtable);
210 }
211
hashtable_init(hashtable_t * hashtable,key_hash_fn hash_key,key_cmp_fn cmp_keys,free_fn free_key,free_fn free_value)212 int hashtable_init(hashtable_t *hashtable,
213 key_hash_fn hash_key, key_cmp_fn cmp_keys,
214 free_fn free_key, free_fn free_value)
215 {
216 unsigned int i;
217
218 hashtable->size = 0;
219 hashtable->num_buckets = 0; /* index to primes[] */
220 hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t));
221 if(!hashtable->buckets)
222 return -1;
223
224 list_init(&hashtable->list);
225
226 hashtable->hash_key = hash_key;
227 hashtable->cmp_keys = cmp_keys;
228 hashtable->free_key = free_key;
229 hashtable->free_value = free_value;
230
231 for(i = 0; i < num_buckets(hashtable); i++)
232 {
233 hashtable->buckets[i].first = hashtable->buckets[i].last =
234 &hashtable->list;
235 }
236
237 return 0;
238 }
239
hashtable_close(hashtable_t * hashtable)240 void hashtable_close(hashtable_t *hashtable)
241 {
242 hashtable_do_clear(hashtable);
243 free(hashtable->buckets);
244 }
245
hashtable_set(hashtable_t * hashtable,void * key,void * value)246 int hashtable_set(hashtable_t *hashtable, void *key, void *value)
247 {
248 pair_t *pair;
249 bucket_t *bucket;
250 unsigned int hash, index;
251
252 /* rehash if the load ratio exceeds 1 */
253 if(hashtable->size >= num_buckets(hashtable))
254 if(hashtable_do_rehash(hashtable))
255 return -1;
256
257 hash = hashtable->hash_key(key);
258 index = hash % num_buckets(hashtable);
259 bucket = &hashtable->buckets[index];
260 pair = hashtable_find_pair(hashtable, bucket, key, hash);
261
262 if(pair)
263 {
264 if(hashtable->free_key)
265 hashtable->free_key(key);
266 if(hashtable->free_value)
267 hashtable->free_value(pair->value);
268 pair->value = value;
269 }
270 else
271 {
272 pair = malloc(sizeof(pair_t));
273 if(!pair)
274 return -1;
275
276 pair->key = key;
277 pair->value = value;
278 pair->hash = hash;
279 list_init(&pair->list);
280
281 insert_to_bucket(hashtable, bucket, &pair->list);
282
283 hashtable->size++;
284 }
285 return 0;
286 }
287
hashtable_get(hashtable_t * hashtable,const void * key)288 void *hashtable_get(hashtable_t *hashtable, const void *key)
289 {
290 pair_t *pair;
291 unsigned int hash;
292 bucket_t *bucket;
293
294 hash = hashtable->hash_key(key);
295 bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
296
297 pair = hashtable_find_pair(hashtable, bucket, key, hash);
298 if(!pair)
299 return NULL;
300
301 return pair->value;
302 }
303
hashtable_del(hashtable_t * hashtable,const void * key)304 int hashtable_del(hashtable_t *hashtable, const void *key)
305 {
306 unsigned int hash = hashtable->hash_key(key);
307 return hashtable_do_del(hashtable, key, hash);
308 }
309
hashtable_clear(hashtable_t * hashtable)310 void hashtable_clear(hashtable_t *hashtable)
311 {
312 unsigned int i;
313
314 hashtable_do_clear(hashtable);
315
316 for(i = 0; i < num_buckets(hashtable); i++)
317 {
318 hashtable->buckets[i].first = hashtable->buckets[i].last =
319 &hashtable->list;
320 }
321
322 list_init(&hashtable->list);
323 hashtable->size = 0;
324 }
325
hashtable_iter(hashtable_t * hashtable)326 void *hashtable_iter(hashtable_t *hashtable)
327 {
328 return hashtable_iter_next(hashtable, &hashtable->list);
329 }
330
hashtable_iter_at(hashtable_t * hashtable,const void * key)331 void *hashtable_iter_at(hashtable_t *hashtable, const void *key)
332 {
333 pair_t *pair;
334 unsigned int hash;
335 bucket_t *bucket;
336
337 hash = hashtable->hash_key(key);
338 bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
339
340 pair = hashtable_find_pair(hashtable, bucket, key, hash);
341 if(!pair)
342 return NULL;
343
344 return &pair->list;
345 }
346
hashtable_iter_next(hashtable_t * hashtable,void * iter)347 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
348 {
349 list_t *list = (list_t *)iter;
350 if(list->next == &hashtable->list)
351 return NULL;
352 return list->next;
353 }
354
hashtable_iter_key(void * iter)355 void *hashtable_iter_key(void *iter)
356 {
357 pair_t *pair = list_to_pair((list_t *)iter);
358 return pair->key;
359 }
360
hashtable_iter_value(void * iter)361 void *hashtable_iter_value(void *iter)
362 {
363 pair_t *pair = list_to_pair((list_t *)iter);
364 return pair->value;
365 }
366
hashtable_iter_set(hashtable_t * hashtable,void * iter,void * value)367 void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value)
368 {
369 pair_t *pair = list_to_pair((list_t *)iter);
370
371 if(hashtable->free_value)
372 hashtable->free_value(pair->value);
373
374 pair->value = value;
375 }
376