lsquic_hash.c revision 461e84d8
150aadb33SDmitri Tikhonov/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov/*
350aadb33SDmitri Tikhonov * lsquic_hash.c
450aadb33SDmitri Tikhonov */
550aadb33SDmitri Tikhonov
650aadb33SDmitri Tikhonov#include <assert.h>
750aadb33SDmitri Tikhonov#include <stdint.h>
850aadb33SDmitri Tikhonov#include <stdlib.h>
950aadb33SDmitri Tikhonov#include <string.h>
1050aadb33SDmitri Tikhonov#include <sys/queue.h>
11461e84d8SAmol Deshpande#ifdef WIN32
12461e84d8SAmol Deshpande#include <vc_compat.h>
13461e84d8SAmol Deshpande#endif
1450aadb33SDmitri Tikhonov
1550aadb33SDmitri Tikhonov#include "lsquic_malo.h"
1650aadb33SDmitri Tikhonov#include "lsquic_hash.h"
1750aadb33SDmitri Tikhonov#include "lsquic_xxhash.h"
1850aadb33SDmitri Tikhonov
1950aadb33SDmitri Tikhonovstruct lsquic_hash_elem
2050aadb33SDmitri Tikhonov{
2150aadb33SDmitri Tikhonov    TAILQ_ENTRY(lsquic_hash_elem)
2250aadb33SDmitri Tikhonov                    qhe_next_bucket,
2350aadb33SDmitri Tikhonov                    qhe_next_all;
2450aadb33SDmitri Tikhonov    const void     *qhe_key_data;
2550aadb33SDmitri Tikhonov    unsigned        qhe_key_len;
2650aadb33SDmitri Tikhonov    void           *qhe_value;
2750aadb33SDmitri Tikhonov    unsigned        qhe_hash_val;
2850aadb33SDmitri Tikhonov};
2950aadb33SDmitri Tikhonov
3050aadb33SDmitri TikhonovTAILQ_HEAD(hels_head, lsquic_hash_elem);
3150aadb33SDmitri Tikhonov
3250aadb33SDmitri Tikhonov#define N_BUCKETS(n_bits) (1U << (n_bits))
3350aadb33SDmitri Tikhonov#define BUCKNO(n_bits, hash) ((hash) & (N_BUCKETS(n_bits) - 1))
3450aadb33SDmitri Tikhonov
3550aadb33SDmitri Tikhonovstruct lsquic_hash
3650aadb33SDmitri Tikhonov{
3750aadb33SDmitri Tikhonov    struct hels_head        *qh_buckets,
3850aadb33SDmitri Tikhonov                             qh_all;
3950aadb33SDmitri Tikhonov    struct malo             *qh_malo_els;
4050aadb33SDmitri Tikhonov    struct lsquic_hash_elem *qh_iter_next;
4150aadb33SDmitri Tikhonov    unsigned                 qh_count;
4250aadb33SDmitri Tikhonov    unsigned                 qh_nbits;
4350aadb33SDmitri Tikhonov};
4450aadb33SDmitri Tikhonov
4550aadb33SDmitri Tikhonov
4650aadb33SDmitri Tikhonovstruct lsquic_hash *
4750aadb33SDmitri Tikhonovlsquic_hash_create (void)
4850aadb33SDmitri Tikhonov{
4950aadb33SDmitri Tikhonov    struct hels_head *buckets;
5050aadb33SDmitri Tikhonov    struct lsquic_hash *hash;
5150aadb33SDmitri Tikhonov    struct malo *malo;
5250aadb33SDmitri Tikhonov    unsigned nbits = 2;
5350aadb33SDmitri Tikhonov    unsigned i;
5450aadb33SDmitri Tikhonov
5550aadb33SDmitri Tikhonov    buckets = malloc(sizeof(buckets[0]) * N_BUCKETS(nbits));
5650aadb33SDmitri Tikhonov    if (!buckets)
5750aadb33SDmitri Tikhonov        return NULL;
5850aadb33SDmitri Tikhonov
5950aadb33SDmitri Tikhonov    hash = malloc(sizeof(*hash));
6050aadb33SDmitri Tikhonov    if (!hash)
6150aadb33SDmitri Tikhonov    {
6250aadb33SDmitri Tikhonov        free(buckets);
6350aadb33SDmitri Tikhonov        return NULL;
6450aadb33SDmitri Tikhonov    }
6550aadb33SDmitri Tikhonov
6650aadb33SDmitri Tikhonov    malo = lsquic_malo_create(sizeof(struct lsquic_hash_elem));
6750aadb33SDmitri Tikhonov    if (!malo)
6850aadb33SDmitri Tikhonov    {
6950aadb33SDmitri Tikhonov        free(hash);
7050aadb33SDmitri Tikhonov        free(buckets);
7150aadb33SDmitri Tikhonov        return NULL;
7250aadb33SDmitri Tikhonov    }
7350aadb33SDmitri Tikhonov
7450aadb33SDmitri Tikhonov    for (i = 0; i < N_BUCKETS(nbits); ++i)
7550aadb33SDmitri Tikhonov        TAILQ_INIT(&buckets[i]);
7650aadb33SDmitri Tikhonov
7750aadb33SDmitri Tikhonov    TAILQ_INIT(&hash->qh_all);
7850aadb33SDmitri Tikhonov    hash->qh_buckets   = buckets;
7950aadb33SDmitri Tikhonov    hash->qh_nbits     = nbits;
8050aadb33SDmitri Tikhonov    hash->qh_malo_els  = malo;
8150aadb33SDmitri Tikhonov    hash->qh_iter_next = NULL;
8250aadb33SDmitri Tikhonov    hash->qh_count     = 0;
8350aadb33SDmitri Tikhonov    return hash;
8450aadb33SDmitri Tikhonov}
8550aadb33SDmitri Tikhonov
8650aadb33SDmitri Tikhonov
8750aadb33SDmitri Tikhonovvoid
8850aadb33SDmitri Tikhonovlsquic_hash_destroy (struct lsquic_hash *hash)
8950aadb33SDmitri Tikhonov{
9050aadb33SDmitri Tikhonov    lsquic_malo_destroy(hash->qh_malo_els);
9150aadb33SDmitri Tikhonov    free(hash->qh_buckets);
9250aadb33SDmitri Tikhonov    free(hash);
9350aadb33SDmitri Tikhonov}
9450aadb33SDmitri Tikhonov
9550aadb33SDmitri Tikhonov
9650aadb33SDmitri Tikhonovstatic int
9750aadb33SDmitri Tikhonovlsquic_hash_grow (struct lsquic_hash *hash)
9850aadb33SDmitri Tikhonov{
9950aadb33SDmitri Tikhonov    struct hels_head *new_buckets, *new[2];
10050aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
10150aadb33SDmitri Tikhonov    unsigned n, old_nbits;
10250aadb33SDmitri Tikhonov    int idx;
10350aadb33SDmitri Tikhonov
10450aadb33SDmitri Tikhonov    old_nbits = hash->qh_nbits;
10550aadb33SDmitri Tikhonov    new_buckets = malloc(sizeof(hash->qh_buckets[0])
10650aadb33SDmitri Tikhonov                                                * N_BUCKETS(old_nbits + 1));
10750aadb33SDmitri Tikhonov    if (!new_buckets)
10850aadb33SDmitri Tikhonov        return -1;
10950aadb33SDmitri Tikhonov
11050aadb33SDmitri Tikhonov    for (n = 0; n < N_BUCKETS(old_nbits); ++n)
11150aadb33SDmitri Tikhonov    {
11250aadb33SDmitri Tikhonov        new[0] = &new_buckets[n];
11350aadb33SDmitri Tikhonov        new[1] = &new_buckets[n + N_BUCKETS(old_nbits)];
11450aadb33SDmitri Tikhonov        TAILQ_INIT(new[0]);
11550aadb33SDmitri Tikhonov        TAILQ_INIT(new[1]);
11650aadb33SDmitri Tikhonov        while ((el = TAILQ_FIRST(&hash->qh_buckets[n])))
11750aadb33SDmitri Tikhonov        {
11850aadb33SDmitri Tikhonov            TAILQ_REMOVE(&hash->qh_buckets[n], el, qhe_next_bucket);
11950aadb33SDmitri Tikhonov            idx = (BUCKNO(old_nbits + 1, el->qhe_hash_val) >> old_nbits) & 1;
12050aadb33SDmitri Tikhonov            TAILQ_INSERT_TAIL(new[idx], el, qhe_next_bucket);
12150aadb33SDmitri Tikhonov        }
12250aadb33SDmitri Tikhonov    }
12350aadb33SDmitri Tikhonov    free(hash->qh_buckets);
12450aadb33SDmitri Tikhonov    hash->qh_nbits   = old_nbits + 1;
12550aadb33SDmitri Tikhonov    hash->qh_buckets = new_buckets;
12650aadb33SDmitri Tikhonov    return 0;
12750aadb33SDmitri Tikhonov}
12850aadb33SDmitri Tikhonov
12950aadb33SDmitri Tikhonov
13050aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
13150aadb33SDmitri Tikhonovlsquic_hash_insert (struct lsquic_hash *hash, const void *key,
13250aadb33SDmitri Tikhonov                                            unsigned key_sz, void *data)
13350aadb33SDmitri Tikhonov{
13450aadb33SDmitri Tikhonov    unsigned buckno, hash_val;
13550aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
13650aadb33SDmitri Tikhonov
13750aadb33SDmitri Tikhonov    el = lsquic_malo_get(hash->qh_malo_els);
13850aadb33SDmitri Tikhonov    if (!el)
13950aadb33SDmitri Tikhonov        return NULL;
14050aadb33SDmitri Tikhonov
14150aadb33SDmitri Tikhonov    if (hash->qh_count >= N_BUCKETS(hash->qh_nbits) / 2 &&
14250aadb33SDmitri Tikhonov                                            0 != lsquic_hash_grow(hash))
14350aadb33SDmitri Tikhonov    {
14450aadb33SDmitri Tikhonov        lsquic_malo_put(el);
14550aadb33SDmitri Tikhonov        return NULL;
14650aadb33SDmitri Tikhonov    }
14750aadb33SDmitri Tikhonov
14850aadb33SDmitri Tikhonov    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
14950aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, hash_val);
15050aadb33SDmitri Tikhonov    TAILQ_INSERT_TAIL(&hash->qh_all, el, qhe_next_all);
15150aadb33SDmitri Tikhonov    TAILQ_INSERT_TAIL(&hash->qh_buckets[buckno], el, qhe_next_bucket);
15250aadb33SDmitri Tikhonov    el->qhe_key_data = key;
15350aadb33SDmitri Tikhonov    el->qhe_key_len  = key_sz;
15450aadb33SDmitri Tikhonov    el->qhe_value    = data;
15550aadb33SDmitri Tikhonov    el->qhe_hash_val = hash_val;
15650aadb33SDmitri Tikhonov    ++hash->qh_count;
15750aadb33SDmitri Tikhonov    return el;
15850aadb33SDmitri Tikhonov}
15950aadb33SDmitri Tikhonov
16050aadb33SDmitri Tikhonov
16150aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
16250aadb33SDmitri Tikhonovlsquic_hash_find (struct lsquic_hash *hash, const void *key, unsigned key_sz)
16350aadb33SDmitri Tikhonov{
16450aadb33SDmitri Tikhonov    unsigned buckno, hash_val;
16550aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
16650aadb33SDmitri Tikhonov
16750aadb33SDmitri Tikhonov    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
16850aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, hash_val);
16950aadb33SDmitri Tikhonov    TAILQ_FOREACH(el, &hash->qh_buckets[buckno], qhe_next_bucket)
17050aadb33SDmitri Tikhonov        if (hash_val == el->qhe_hash_val &&
17150aadb33SDmitri Tikhonov            key_sz   == el->qhe_key_len &&
17250aadb33SDmitri Tikhonov            0 == memcmp(key, el->qhe_key_data, key_sz))
17350aadb33SDmitri Tikhonov        {
17450aadb33SDmitri Tikhonov            return el;
17550aadb33SDmitri Tikhonov        }
17650aadb33SDmitri Tikhonov
17750aadb33SDmitri Tikhonov    return NULL;
17850aadb33SDmitri Tikhonov}
17950aadb33SDmitri Tikhonov
18050aadb33SDmitri Tikhonov
18150aadb33SDmitri Tikhonovvoid *
18250aadb33SDmitri Tikhonovlsquic_hashelem_getdata (const struct lsquic_hash_elem *el)
18350aadb33SDmitri Tikhonov{
18450aadb33SDmitri Tikhonov    return el->qhe_value;
18550aadb33SDmitri Tikhonov}
18650aadb33SDmitri Tikhonov
18750aadb33SDmitri Tikhonov
18850aadb33SDmitri Tikhonovvoid
18950aadb33SDmitri Tikhonovlsquic_hash_erase (struct lsquic_hash *hash, struct lsquic_hash_elem *el)
19050aadb33SDmitri Tikhonov{
19150aadb33SDmitri Tikhonov    unsigned buckno;
19250aadb33SDmitri Tikhonov
19350aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, el->qhe_hash_val);
19450aadb33SDmitri Tikhonov    TAILQ_REMOVE(&hash->qh_buckets[buckno], el, qhe_next_bucket);
19550aadb33SDmitri Tikhonov    TAILQ_REMOVE(&hash->qh_all, el, qhe_next_all);
19650aadb33SDmitri Tikhonov    lsquic_malo_put(el);
19750aadb33SDmitri Tikhonov    --hash->qh_count;
19850aadb33SDmitri Tikhonov}
19950aadb33SDmitri Tikhonov
20050aadb33SDmitri Tikhonov
20150aadb33SDmitri Tikhonovvoid
20250aadb33SDmitri Tikhonovlsquic_hash_reset_iter (struct lsquic_hash *hash)
20350aadb33SDmitri Tikhonov{
20450aadb33SDmitri Tikhonov    hash->qh_iter_next = TAILQ_FIRST(&hash->qh_all);
20550aadb33SDmitri Tikhonov}
20650aadb33SDmitri Tikhonov
20750aadb33SDmitri Tikhonov
20850aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
20950aadb33SDmitri Tikhonovlsquic_hash_first (struct lsquic_hash *hash)
21050aadb33SDmitri Tikhonov{
21150aadb33SDmitri Tikhonov    lsquic_hash_reset_iter(hash);
21250aadb33SDmitri Tikhonov    return lsquic_hash_next(hash);
21350aadb33SDmitri Tikhonov}
21450aadb33SDmitri Tikhonov
21550aadb33SDmitri Tikhonov
21650aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
21750aadb33SDmitri Tikhonovlsquic_hash_next (struct lsquic_hash *hash)
21850aadb33SDmitri Tikhonov{
21950aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
22050aadb33SDmitri Tikhonov    el = hash->qh_iter_next;
22150aadb33SDmitri Tikhonov    if (el)
22250aadb33SDmitri Tikhonov        hash->qh_iter_next = TAILQ_NEXT(el, qhe_next_all);
22350aadb33SDmitri Tikhonov    return el;
22450aadb33SDmitri Tikhonov}
22550aadb33SDmitri Tikhonov
22650aadb33SDmitri Tikhonov
22750aadb33SDmitri Tikhonovunsigned
22850aadb33SDmitri Tikhonovlsquic_hash_count (struct lsquic_hash *hash)
22950aadb33SDmitri Tikhonov{
23050aadb33SDmitri Tikhonov    return hash->qh_count;
23150aadb33SDmitri Tikhonov}
232c51ce338SDmitri Tikhonov
233c51ce338SDmitri Tikhonov
234c51ce338SDmitri Tikhonovsize_t
235c51ce338SDmitri Tikhonovlsquic_hash_mem_used (const struct lsquic_hash *hash)
236c51ce338SDmitri Tikhonov{
237c51ce338SDmitri Tikhonov    return sizeof(*hash)
238c51ce338SDmitri Tikhonov         + N_BUCKETS(hash->qh_nbits) * sizeof(hash->qh_buckets[0])
239c51ce338SDmitri Tikhonov         + lsquic_malo_mem_used(hash->qh_malo_els);
240c51ce338SDmitri Tikhonov}
241