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