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