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