lsquic_hash.c revision 461e84d8 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_hash.c
4 */
5
6#include <assert.h>
7#include <stdint.h>
8#include <stdlib.h>
9#include <string.h>
10#include <sys/queue.h>
11#ifdef WIN32
12#include <vc_compat.h>
13#endif
14
15#include "lsquic_malo.h"
16#include "lsquic_hash.h"
17#include "lsquic_xxhash.h"
18
19struct lsquic_hash_elem
20{
21    TAILQ_ENTRY(lsquic_hash_elem)
22                    qhe_next_bucket,
23                    qhe_next_all;
24    const void     *qhe_key_data;
25    unsigned        qhe_key_len;
26    void           *qhe_value;
27    unsigned        qhe_hash_val;
28};
29
30TAILQ_HEAD(hels_head, lsquic_hash_elem);
31
32#define N_BUCKETS(n_bits) (1U << (n_bits))
33#define BUCKNO(n_bits, hash) ((hash) & (N_BUCKETS(n_bits) - 1))
34
35struct lsquic_hash
36{
37    struct hels_head        *qh_buckets,
38                             qh_all;
39    struct malo             *qh_malo_els;
40    struct lsquic_hash_elem *qh_iter_next;
41    unsigned                 qh_count;
42    unsigned                 qh_nbits;
43};
44
45
46struct lsquic_hash *
47lsquic_hash_create (void)
48{
49    struct hels_head *buckets;
50    struct lsquic_hash *hash;
51    struct malo *malo;
52    unsigned nbits = 2;
53    unsigned i;
54
55    buckets = malloc(sizeof(buckets[0]) * N_BUCKETS(nbits));
56    if (!buckets)
57        return NULL;
58
59    hash = malloc(sizeof(*hash));
60    if (!hash)
61    {
62        free(buckets);
63        return NULL;
64    }
65
66    malo = lsquic_malo_create(sizeof(struct lsquic_hash_elem));
67    if (!malo)
68    {
69        free(hash);
70        free(buckets);
71        return NULL;
72    }
73
74    for (i = 0; i < N_BUCKETS(nbits); ++i)
75        TAILQ_INIT(&buckets[i]);
76
77    TAILQ_INIT(&hash->qh_all);
78    hash->qh_buckets   = buckets;
79    hash->qh_nbits     = nbits;
80    hash->qh_malo_els  = malo;
81    hash->qh_iter_next = NULL;
82    hash->qh_count     = 0;
83    return hash;
84}
85
86
87void
88lsquic_hash_destroy (struct lsquic_hash *hash)
89{
90    lsquic_malo_destroy(hash->qh_malo_els);
91    free(hash->qh_buckets);
92    free(hash);
93}
94
95
96static int
97lsquic_hash_grow (struct lsquic_hash *hash)
98{
99    struct hels_head *new_buckets, *new[2];
100    struct lsquic_hash_elem *el;
101    unsigned n, old_nbits;
102    int idx;
103
104    old_nbits = hash->qh_nbits;
105    new_buckets = malloc(sizeof(hash->qh_buckets[0])
106                                                * N_BUCKETS(old_nbits + 1));
107    if (!new_buckets)
108        return -1;
109
110    for (n = 0; n < N_BUCKETS(old_nbits); ++n)
111    {
112        new[0] = &new_buckets[n];
113        new[1] = &new_buckets[n + N_BUCKETS(old_nbits)];
114        TAILQ_INIT(new[0]);
115        TAILQ_INIT(new[1]);
116        while ((el = TAILQ_FIRST(&hash->qh_buckets[n])))
117        {
118            TAILQ_REMOVE(&hash->qh_buckets[n], el, qhe_next_bucket);
119            idx = (BUCKNO(old_nbits + 1, el->qhe_hash_val) >> old_nbits) & 1;
120            TAILQ_INSERT_TAIL(new[idx], el, qhe_next_bucket);
121        }
122    }
123    free(hash->qh_buckets);
124    hash->qh_nbits   = old_nbits + 1;
125    hash->qh_buckets = new_buckets;
126    return 0;
127}
128
129
130struct lsquic_hash_elem *
131lsquic_hash_insert (struct lsquic_hash *hash, const void *key,
132                                            unsigned key_sz, void *data)
133{
134    unsigned buckno, hash_val;
135    struct lsquic_hash_elem *el;
136
137    el = lsquic_malo_get(hash->qh_malo_els);
138    if (!el)
139        return NULL;
140
141    if (hash->qh_count >= N_BUCKETS(hash->qh_nbits) / 2 &&
142                                            0 != lsquic_hash_grow(hash))
143    {
144        lsquic_malo_put(el);
145        return NULL;
146    }
147
148    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
149    buckno = BUCKNO(hash->qh_nbits, hash_val);
150    TAILQ_INSERT_TAIL(&hash->qh_all, el, qhe_next_all);
151    TAILQ_INSERT_TAIL(&hash->qh_buckets[buckno], el, qhe_next_bucket);
152    el->qhe_key_data = key;
153    el->qhe_key_len  = key_sz;
154    el->qhe_value    = data;
155    el->qhe_hash_val = hash_val;
156    ++hash->qh_count;
157    return el;
158}
159
160
161struct lsquic_hash_elem *
162lsquic_hash_find (struct lsquic_hash *hash, const void *key, unsigned key_sz)
163{
164    unsigned buckno, hash_val;
165    struct lsquic_hash_elem *el;
166
167    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
168    buckno = BUCKNO(hash->qh_nbits, hash_val);
169    TAILQ_FOREACH(el, &hash->qh_buckets[buckno], qhe_next_bucket)
170        if (hash_val == el->qhe_hash_val &&
171            key_sz   == el->qhe_key_len &&
172            0 == memcmp(key, el->qhe_key_data, key_sz))
173        {
174            return el;
175        }
176
177    return NULL;
178}
179
180
181void *
182lsquic_hashelem_getdata (const struct lsquic_hash_elem *el)
183{
184    return el->qhe_value;
185}
186
187
188void
189lsquic_hash_erase (struct lsquic_hash *hash, struct lsquic_hash_elem *el)
190{
191    unsigned buckno;
192
193    buckno = BUCKNO(hash->qh_nbits, el->qhe_hash_val);
194    TAILQ_REMOVE(&hash->qh_buckets[buckno], el, qhe_next_bucket);
195    TAILQ_REMOVE(&hash->qh_all, el, qhe_next_all);
196    lsquic_malo_put(el);
197    --hash->qh_count;
198}
199
200
201void
202lsquic_hash_reset_iter (struct lsquic_hash *hash)
203{
204    hash->qh_iter_next = TAILQ_FIRST(&hash->qh_all);
205}
206
207
208struct lsquic_hash_elem *
209lsquic_hash_first (struct lsquic_hash *hash)
210{
211    lsquic_hash_reset_iter(hash);
212    return lsquic_hash_next(hash);
213}
214
215
216struct lsquic_hash_elem *
217lsquic_hash_next (struct lsquic_hash *hash)
218{
219    struct lsquic_hash_elem *el;
220    el = hash->qh_iter_next;
221    if (el)
222        hash->qh_iter_next = TAILQ_NEXT(el, qhe_next_all);
223    return el;
224}
225
226
227unsigned
228lsquic_hash_count (struct lsquic_hash *hash)
229{
230    return hash->qh_count;
231}
232
233
234size_t
235lsquic_hash_mem_used (const struct lsquic_hash *hash)
236{
237    return sizeof(*hash)
238         + N_BUCKETS(hash->qh_nbits) * sizeof(hash->qh_buckets[0])
239         + lsquic_malo_mem_used(hash->qh_malo_els);
240}
241