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