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