lsquic_hash.c revision 5392f7a3
1229fce07SDmitri Tikhonov/* Copyright (c) 2017 - 2019 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_hash.h"
1650aadb33SDmitri Tikhonov#include "lsquic_xxhash.h"
1750aadb33SDmitri Tikhonov
1850aadb33SDmitri TikhonovTAILQ_HEAD(hels_head, lsquic_hash_elem);
1950aadb33SDmitri Tikhonov
2050aadb33SDmitri Tikhonov#define N_BUCKETS(n_bits) (1U << (n_bits))
2150aadb33SDmitri Tikhonov#define BUCKNO(n_bits, hash) ((hash) & (N_BUCKETS(n_bits) - 1))
2250aadb33SDmitri Tikhonov
2350aadb33SDmitri Tikhonovstruct lsquic_hash
2450aadb33SDmitri Tikhonov{
2550aadb33SDmitri Tikhonov    struct hels_head        *qh_buckets,
2650aadb33SDmitri Tikhonov                             qh_all;
2750aadb33SDmitri Tikhonov    struct lsquic_hash_elem *qh_iter_next;
2850aadb33SDmitri Tikhonov    unsigned                 qh_count;
2950aadb33SDmitri Tikhonov    unsigned                 qh_nbits;
3050aadb33SDmitri Tikhonov};
3150aadb33SDmitri Tikhonov
3250aadb33SDmitri Tikhonov
3350aadb33SDmitri Tikhonovstruct lsquic_hash *
3450aadb33SDmitri Tikhonovlsquic_hash_create (void)
3550aadb33SDmitri Tikhonov{
3650aadb33SDmitri Tikhonov    struct hels_head *buckets;
3750aadb33SDmitri Tikhonov    struct lsquic_hash *hash;
3850aadb33SDmitri Tikhonov    unsigned nbits = 2;
3950aadb33SDmitri Tikhonov    unsigned i;
4050aadb33SDmitri Tikhonov
4150aadb33SDmitri Tikhonov    buckets = malloc(sizeof(buckets[0]) * N_BUCKETS(nbits));
4250aadb33SDmitri Tikhonov    if (!buckets)
4350aadb33SDmitri Tikhonov        return NULL;
4450aadb33SDmitri Tikhonov
4550aadb33SDmitri Tikhonov    hash = malloc(sizeof(*hash));
4650aadb33SDmitri Tikhonov    if (!hash)
4750aadb33SDmitri Tikhonov    {
4850aadb33SDmitri Tikhonov        free(buckets);
4950aadb33SDmitri Tikhonov        return NULL;
5050aadb33SDmitri Tikhonov    }
5150aadb33SDmitri Tikhonov
5250aadb33SDmitri Tikhonov    for (i = 0; i < N_BUCKETS(nbits); ++i)
5350aadb33SDmitri Tikhonov        TAILQ_INIT(&buckets[i]);
5450aadb33SDmitri Tikhonov
5550aadb33SDmitri Tikhonov    TAILQ_INIT(&hash->qh_all);
5650aadb33SDmitri Tikhonov    hash->qh_buckets   = buckets;
5750aadb33SDmitri Tikhonov    hash->qh_nbits     = nbits;
5850aadb33SDmitri Tikhonov    hash->qh_iter_next = NULL;
5950aadb33SDmitri Tikhonov    hash->qh_count     = 0;
6050aadb33SDmitri Tikhonov    return hash;
6150aadb33SDmitri Tikhonov}
6250aadb33SDmitri Tikhonov
6350aadb33SDmitri Tikhonov
6450aadb33SDmitri Tikhonovvoid
6550aadb33SDmitri Tikhonovlsquic_hash_destroy (struct lsquic_hash *hash)
6650aadb33SDmitri Tikhonov{
6750aadb33SDmitri Tikhonov    free(hash->qh_buckets);
6850aadb33SDmitri Tikhonov    free(hash);
6950aadb33SDmitri Tikhonov}
7050aadb33SDmitri Tikhonov
7150aadb33SDmitri Tikhonov
7250aadb33SDmitri Tikhonovstatic int
7350aadb33SDmitri Tikhonovlsquic_hash_grow (struct lsquic_hash *hash)
7450aadb33SDmitri Tikhonov{
7550aadb33SDmitri Tikhonov    struct hels_head *new_buckets, *new[2];
7650aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
7750aadb33SDmitri Tikhonov    unsigned n, old_nbits;
7850aadb33SDmitri Tikhonov    int idx;
7950aadb33SDmitri Tikhonov
8050aadb33SDmitri Tikhonov    old_nbits = hash->qh_nbits;
8150aadb33SDmitri Tikhonov    new_buckets = malloc(sizeof(hash->qh_buckets[0])
8250aadb33SDmitri Tikhonov                                                * N_BUCKETS(old_nbits + 1));
8350aadb33SDmitri Tikhonov    if (!new_buckets)
8450aadb33SDmitri Tikhonov        return -1;
8550aadb33SDmitri Tikhonov
8650aadb33SDmitri Tikhonov    for (n = 0; n < N_BUCKETS(old_nbits); ++n)
8750aadb33SDmitri Tikhonov    {
8850aadb33SDmitri Tikhonov        new[0] = &new_buckets[n];
8950aadb33SDmitri Tikhonov        new[1] = &new_buckets[n + N_BUCKETS(old_nbits)];
9050aadb33SDmitri Tikhonov        TAILQ_INIT(new[0]);
9150aadb33SDmitri Tikhonov        TAILQ_INIT(new[1]);
9250aadb33SDmitri Tikhonov        while ((el = TAILQ_FIRST(&hash->qh_buckets[n])))
9350aadb33SDmitri Tikhonov        {
9450aadb33SDmitri Tikhonov            TAILQ_REMOVE(&hash->qh_buckets[n], el, qhe_next_bucket);
9550aadb33SDmitri Tikhonov            idx = (BUCKNO(old_nbits + 1, el->qhe_hash_val) >> old_nbits) & 1;
9650aadb33SDmitri Tikhonov            TAILQ_INSERT_TAIL(new[idx], el, qhe_next_bucket);
9750aadb33SDmitri Tikhonov        }
9850aadb33SDmitri Tikhonov    }
9950aadb33SDmitri Tikhonov    free(hash->qh_buckets);
10050aadb33SDmitri Tikhonov    hash->qh_nbits   = old_nbits + 1;
10150aadb33SDmitri Tikhonov    hash->qh_buckets = new_buckets;
10250aadb33SDmitri Tikhonov    return 0;
10350aadb33SDmitri Tikhonov}
10450aadb33SDmitri Tikhonov
10550aadb33SDmitri Tikhonov
10650aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
10750aadb33SDmitri Tikhonovlsquic_hash_insert (struct lsquic_hash *hash, const void *key,
1085392f7a3SLiteSpeed Tech                    unsigned key_sz, void *value, struct lsquic_hash_elem *el)
10950aadb33SDmitri Tikhonov{
11050aadb33SDmitri Tikhonov    unsigned buckno, hash_val;
11150aadb33SDmitri Tikhonov
1125392f7a3SLiteSpeed Tech    if (el->qhe_flags & QHE_HASHED)
11350aadb33SDmitri Tikhonov        return NULL;
11450aadb33SDmitri Tikhonov
11550aadb33SDmitri Tikhonov    if (hash->qh_count >= N_BUCKETS(hash->qh_nbits) / 2 &&
11650aadb33SDmitri Tikhonov                                            0 != lsquic_hash_grow(hash))
11750aadb33SDmitri Tikhonov        return NULL;
11850aadb33SDmitri Tikhonov
11950aadb33SDmitri Tikhonov    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
12050aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, hash_val);
12150aadb33SDmitri Tikhonov    TAILQ_INSERT_TAIL(&hash->qh_all, el, qhe_next_all);
12250aadb33SDmitri Tikhonov    TAILQ_INSERT_TAIL(&hash->qh_buckets[buckno], el, qhe_next_bucket);
12350aadb33SDmitri Tikhonov    el->qhe_key_data = key;
12450aadb33SDmitri Tikhonov    el->qhe_key_len  = key_sz;
1255392f7a3SLiteSpeed Tech    el->qhe_value    = value;
12650aadb33SDmitri Tikhonov    el->qhe_hash_val = hash_val;
1275392f7a3SLiteSpeed Tech    el->qhe_flags |= QHE_HASHED;
12850aadb33SDmitri Tikhonov    ++hash->qh_count;
12950aadb33SDmitri Tikhonov    return el;
13050aadb33SDmitri Tikhonov}
13150aadb33SDmitri Tikhonov
13250aadb33SDmitri Tikhonov
13350aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
13450aadb33SDmitri Tikhonovlsquic_hash_find (struct lsquic_hash *hash, const void *key, unsigned key_sz)
13550aadb33SDmitri Tikhonov{
13650aadb33SDmitri Tikhonov    unsigned buckno, hash_val;
13750aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
13850aadb33SDmitri Tikhonov
13950aadb33SDmitri Tikhonov    hash_val = XXH64(key, key_sz, (uintptr_t) hash);
14050aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, hash_val);
14150aadb33SDmitri Tikhonov    TAILQ_FOREACH(el, &hash->qh_buckets[buckno], qhe_next_bucket)
14250aadb33SDmitri Tikhonov        if (hash_val == el->qhe_hash_val &&
14350aadb33SDmitri Tikhonov            key_sz   == el->qhe_key_len &&
14450aadb33SDmitri Tikhonov            0 == memcmp(key, el->qhe_key_data, key_sz))
14550aadb33SDmitri Tikhonov        {
14650aadb33SDmitri Tikhonov            return el;
14750aadb33SDmitri Tikhonov        }
14850aadb33SDmitri Tikhonov
14950aadb33SDmitri Tikhonov    return NULL;
15050aadb33SDmitri Tikhonov}
15150aadb33SDmitri Tikhonov
15250aadb33SDmitri Tikhonov
15350aadb33SDmitri Tikhonovvoid
15450aadb33SDmitri Tikhonovlsquic_hash_erase (struct lsquic_hash *hash, struct lsquic_hash_elem *el)
15550aadb33SDmitri Tikhonov{
15650aadb33SDmitri Tikhonov    unsigned buckno;
15750aadb33SDmitri Tikhonov
1585392f7a3SLiteSpeed Tech    assert(el->qhe_flags & QHE_HASHED);
15950aadb33SDmitri Tikhonov    buckno = BUCKNO(hash->qh_nbits, el->qhe_hash_val);
1605392f7a3SLiteSpeed Tech    if (hash->qh_iter_next == el)
1615392f7a3SLiteSpeed Tech        hash->qh_iter_next = TAILQ_NEXT(el, qhe_next_all);
16250aadb33SDmitri Tikhonov    TAILQ_REMOVE(&hash->qh_buckets[buckno], el, qhe_next_bucket);
16350aadb33SDmitri Tikhonov    TAILQ_REMOVE(&hash->qh_all, el, qhe_next_all);
1645392f7a3SLiteSpeed Tech    el->qhe_flags &= ~QHE_HASHED;
16550aadb33SDmitri Tikhonov    --hash->qh_count;
16650aadb33SDmitri Tikhonov}
16750aadb33SDmitri Tikhonov
16850aadb33SDmitri Tikhonov
16950aadb33SDmitri Tikhonovvoid
17050aadb33SDmitri Tikhonovlsquic_hash_reset_iter (struct lsquic_hash *hash)
17150aadb33SDmitri Tikhonov{
17250aadb33SDmitri Tikhonov    hash->qh_iter_next = TAILQ_FIRST(&hash->qh_all);
17350aadb33SDmitri Tikhonov}
17450aadb33SDmitri Tikhonov
17550aadb33SDmitri Tikhonov
17650aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
17750aadb33SDmitri Tikhonovlsquic_hash_first (struct lsquic_hash *hash)
17850aadb33SDmitri Tikhonov{
17950aadb33SDmitri Tikhonov    lsquic_hash_reset_iter(hash);
18050aadb33SDmitri Tikhonov    return lsquic_hash_next(hash);
18150aadb33SDmitri Tikhonov}
18250aadb33SDmitri Tikhonov
18350aadb33SDmitri Tikhonov
18450aadb33SDmitri Tikhonovstruct lsquic_hash_elem *
18550aadb33SDmitri Tikhonovlsquic_hash_next (struct lsquic_hash *hash)
18650aadb33SDmitri Tikhonov{
18750aadb33SDmitri Tikhonov    struct lsquic_hash_elem *el;
18850aadb33SDmitri Tikhonov    el = hash->qh_iter_next;
18950aadb33SDmitri Tikhonov    if (el)
19050aadb33SDmitri Tikhonov        hash->qh_iter_next = TAILQ_NEXT(el, qhe_next_all);
19150aadb33SDmitri Tikhonov    return el;
19250aadb33SDmitri Tikhonov}
19350aadb33SDmitri Tikhonov
19450aadb33SDmitri Tikhonov
19550aadb33SDmitri Tikhonovunsigned
19650aadb33SDmitri Tikhonovlsquic_hash_count (struct lsquic_hash *hash)
19750aadb33SDmitri Tikhonov{
19850aadb33SDmitri Tikhonov    return hash->qh_count;
19950aadb33SDmitri Tikhonov}
200c51ce338SDmitri Tikhonov
201c51ce338SDmitri Tikhonov
202c51ce338SDmitri Tikhonovsize_t
203c51ce338SDmitri Tikhonovlsquic_hash_mem_used (const struct lsquic_hash *hash)
204c51ce338SDmitri Tikhonov{
205c51ce338SDmitri Tikhonov    return sizeof(*hash)
2065392f7a3SLiteSpeed Tech         + N_BUCKETS(hash->qh_nbits) * sizeof(hash->qh_buckets[0]);
207c51ce338SDmitri Tikhonov}
208