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