2 * Copyright (c) 2009 Petri Lehtinen <petri@digip.org>
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.
11 typedef struct hashtable_list list_t;
12 typedef struct hashtable_pair pair_t;
13 typedef struct hashtable_bucket bucket_t;
15 #define container_of(ptr_, type_, member_) \
16 ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
18 #define list_to_pair(list_) container_of(list_, pair_t, list)
20 static inline void list_init(list_t *list)
26 static inline void list_insert(list_t *list, list_t *node)
29 node->prev = list->prev;
30 list->prev->next = node;
34 static inline void list_remove(list_t *list)
36 list->prev->next = list->next;
37 list->next->prev = list->prev;
40 static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
42 return bucket->first == &hashtable->list && bucket->first == bucket->last;
45 static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,
48 if(bucket_is_empty(hashtable, bucket))
50 list_insert(&hashtable->list, list);
51 bucket->first = bucket->last = list;
55 list_insert(bucket->first, list);
60 static unsigned int primes[] = {
61 5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
62 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
63 12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
66 static const unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
68 static inline unsigned int num_buckets(hashtable_t *hashtable)
70 return primes[hashtable->num_buckets];
74 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
75 const void *key, unsigned int hash)
80 if(bucket_is_empty(hashtable, bucket))
86 pair = list_to_pair(list);
87 if(pair->hash == hash && hashtable->cmp_keys(pair->key, key))
90 if(list == bucket->last)
99 /* returns 0 on success, -1 if key was not found */
100 static int hashtable_do_del(hashtable_t *hashtable,
101 const void *key, unsigned int hash)
107 index = hash % num_buckets(hashtable);
108 bucket = &hashtable->buckets[index];
110 pair = hashtable_find_pair(hashtable, bucket, key, hash);
114 if(&pair->list == bucket->first && &pair->list == bucket->last)
115 bucket->first = bucket->last = &hashtable->list;
117 else if(&pair->list == bucket->first)
118 bucket->first = pair->list.next;
120 else if(&pair->list == bucket->last)
121 bucket->last = pair->list.prev;
123 list_remove(&pair->list);
125 if(hashtable->free_key)
126 hashtable->free_key(pair->key);
127 if(hashtable->free_value)
128 hashtable->free_value(pair->value);
136 static void hashtable_do_clear(hashtable_t *hashtable)
141 for(list = hashtable->list.next; list != &hashtable->list; list = next)
144 pair = list_to_pair(list);
145 if(hashtable->free_key)
146 hashtable->free_key(pair->key);
147 if(hashtable->free_value)
148 hashtable->free_value(pair->value);
153 static int hashtable_do_rehash(hashtable_t *hashtable)
157 unsigned int i, index, new_size;
159 free(hashtable->buckets);
161 hashtable->num_buckets++;
162 new_size = num_buckets(hashtable);
164 hashtable->buckets = malloc(new_size * sizeof(bucket_t));
165 if(!hashtable->buckets)
168 for(i = 0; i < num_buckets(hashtable); i++)
170 hashtable->buckets[i].first = hashtable->buckets[i].last =
174 list = hashtable->list.next;
175 list_init(&hashtable->list);
177 for(; list != &hashtable->list; list = next) {
179 pair = list_to_pair(list);
180 index = pair->hash % new_size;
181 insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
188 hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
189 free_fn free_key, free_fn free_value)
191 hashtable_t *hashtable = malloc(sizeof(hashtable_t));
195 if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value))
204 void hashtable_destroy(hashtable_t *hashtable)
206 hashtable_close(hashtable);
210 int hashtable_init(hashtable_t *hashtable,
211 key_hash_fn hash_key, key_cmp_fn cmp_keys,
212 free_fn free_key, free_fn free_value)
217 hashtable->num_buckets = 0; /* index to primes[] */
218 hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t));
219 if(!hashtable->buckets)
222 list_init(&hashtable->list);
224 hashtable->hash_key = hash_key;
225 hashtable->cmp_keys = cmp_keys;
226 hashtable->free_key = free_key;
227 hashtable->free_value = free_value;
229 for(i = 0; i < num_buckets(hashtable); i++)
231 hashtable->buckets[i].first = hashtable->buckets[i].last =
238 void hashtable_close(hashtable_t *hashtable)
240 hashtable_do_clear(hashtable);
241 free(hashtable->buckets);
244 int hashtable_set(hashtable_t *hashtable, void *key, void *value)
248 unsigned int hash, index;
250 hash = hashtable->hash_key(key);
252 /* if the key already exists, delete it */
253 hashtable_do_del(hashtable, key, hash);
255 /* rehash if the load ratio exceeds 1 */
256 if(hashtable->size >= num_buckets(hashtable))
257 if(hashtable_do_rehash(hashtable))
260 pair = malloc(sizeof(pair_t));
267 list_init(&pair->list);
269 index = hash % num_buckets(hashtable);
270 bucket = &hashtable->buckets[index];
272 insert_to_bucket(hashtable, bucket, &pair->list);
278 void *hashtable_get(hashtable_t *hashtable, const void *key)
284 hash = hashtable->hash_key(key);
285 bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
287 pair = hashtable_find_pair(hashtable, bucket, key, hash);
294 int hashtable_del(hashtable_t *hashtable, const void *key)
296 unsigned int hash = hashtable->hash_key(key);
297 return hashtable_do_del(hashtable, key, hash);
300 void hashtable_clear(hashtable_t *hashtable)
304 hashtable_do_clear(hashtable);
306 for(i = 0; i < num_buckets(hashtable); i++)
308 hashtable->buckets[i].first = hashtable->buckets[i].last =
312 list_init(&hashtable->list);
316 void *hashtable_iter(hashtable_t *hashtable)
318 return hashtable_iter_next(hashtable, &hashtable->list);
321 void *hashtable_iter_at(hashtable_t *hashtable, const void *key)
327 hash = hashtable->hash_key(key);
328 bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
330 pair = hashtable_find_pair(hashtable, bucket, key, hash);
337 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
339 list_t *list = (list_t *)iter;
340 if(list->next == &hashtable->list)
345 void *hashtable_iter_key(void *iter)
347 pair_t *pair = list_to_pair((list_t *)iter);
351 void *hashtable_iter_value(void *iter)
353 pair_t *pair = list_to_pair((list_t *)iter);
357 void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value)
359 pair_t *pair = list_to_pair((list_t *)iter);
361 if(hashtable->free_value)
362 hashtable->free_value(pair->value);