commit 79415f5117ea5fb311c4d57ddc43a317c9840b34 from: Stefan Sperling date: Fri Sep 01 14:06:22 2023 UTC add a hash table implementation ok tom commit - 444134c06cbc0ad8b7366aba187ea98566b758a5 commit + 79415f5117ea5fb311c4d57ddc43a317c9840b34 blob - d0ea33ff297130b499703d8f068c954783abcdb3 blob + 452d823c43405e462983e5c13eee67d7081cf956 --- Makefile +++ Makefile @@ -30,7 +30,7 @@ SRCS+=ctl.c show.c if.c version.c route.c conf.c compl SRCS+=bridge.c tunnel.c media.c sysctl.c passwd.c pfsync.c carp.c SRCS+=trunk.c who.c more.c stringlist.c utils.c sqlite3.c ppp.c prompt.c SRCS+=nopt.c pflow.c wg.c nameserver.c ndp.c umb.c utf8.c cmdargs.c ctlargs.c -SRCS+=helpcommands.c makeargv.c +SRCS+=helpcommands.c makeargv.c hashtable.c CLEANFILES+=compile.c LDADD=-lutil -ledit -ltermcap -lsqlite3 -L/usr/local/lib #-static blob - 98be4c1f2a50bf22257eacd7a22db984d21c26e7 blob + 0c4de9e47efee4ca545c7b35ce12c727c47e31e5 --- externs.h +++ externs.h @@ -564,3 +564,19 @@ int mbsavis(char**, int *, const char *); /* ctlargs.c */ int pr_prot1(int, char **); char **step_optreq(char **, char **, int, char **, int); + +/* hashtable.c */ +struct hashtable; +struct hashtable *hashtable_alloc(void); +void hashtable_free(struct hashtable *); +int hashtable_add(struct hashtable *, void *key, size_t keysize, + void *value, size_t valsize); +void *hashtable_get_keyptr(struct hashtable *, void *key, size_t keysize); +void *hashtable_get_value(struct hashtable *, void *key, size_t keysize); +int hashtable_remove(struct hashtable *, void **keyptr, void **value, + size_t *valsize, void *key, size_t keysize); +int hashtable_contains(struct hashtable *, void *key, size_t keysize); +int hashtable_foreach(struct hashtable *, + int (*cb)(void *, size_t, void *, size_t, void *), + void *cb_arg); +int hashtable_num_entries(struct hashtable *); blob - /dev/null blob + c9dd913ad5963e10318a72705c3dc7f25e00c8c3 (mode 644) --- /dev/null +++ hashtable.c @@ -0,0 +1,304 @@ +/* + * Copyright (c) 2023 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include +#include +#include +#include +#include +#include + +#include "externs.h" + +struct hashentry { + STAILQ_ENTRY(hashentry) entry; + void *key; + size_t keysize; + void *value; + size_t valsize; +}; + +STAILQ_HEAD(hashbucket, hashentry); + +#define HASHTABLE_MIN_BUCKETS 64 + +struct hashtable { + struct hashbucket *buckets; + size_t nbuckets; + unsigned int nentries; + unsigned int flags; +#define HASHTABLE_F_TRAVERSAL 0x01 +#define HASHTABLE_F_NOMEM 0x02 + SIPHASH_KEY siphash_key; +}; + +static uint64_t +entry_hash(struct hashtable *t, void *key, size_t keysize) +{ + return SipHash24(&t->siphash_key, key, keysize); +} + +struct hashtable * +hashtable_alloc(void) +{ + struct hashtable *t; + const size_t nbuckets = HASHTABLE_MIN_BUCKETS; + size_t i; + + t = calloc(1, sizeof(*t)); + if (t == NULL) + return NULL; + + t->buckets = calloc(nbuckets, sizeof(t->buckets[0])); + if (t->buckets == NULL) { + free(t); + return NULL; + } + + for (i = 0; i < nbuckets; i++) + STAILQ_INIT(&t->buckets[i]); + t->nbuckets = nbuckets; + arc4random_buf(&t->siphash_key, sizeof(t->siphash_key)); + + return t; +} + +void +hashtable_free(struct hashtable *t) +{ + size_t i; + struct hashentry *e; + + for (i = 0; i < t->nbuckets; i++) { + while (!STAILQ_EMPTY(&t->buckets[i])) { + e = STAILQ_FIRST(&t->buckets[i]); + STAILQ_REMOVE(&t->buckets[i], e, hashentry, entry); + free(e); + } + } + /* Storage for keys and values should be freed by caller. */ + free(t->buckets); + free(t); +} + +static int +table_resize(struct hashtable *t, size_t nbuckets) +{ + struct hashbucket *buckets; + size_t i; + + buckets = calloc(nbuckets, sizeof(buckets[0])); + if (buckets == NULL) { + if (errno != ENOMEM) + return -1; + /* Proceed with our current amount of hash buckets. */ + t->flags |= HASHTABLE_F_NOMEM; + return 0; + } + + for (i = 0; i < nbuckets; i++) + STAILQ_INIT(&buckets[i]); + + arc4random_buf(&t->siphash_key, sizeof(t->siphash_key)); + + for (i = 0; i < t->nbuckets; i++) { + while (!STAILQ_EMPTY(&t->buckets[i])) { + struct hashentry *e; + uint64_t idx; + e = STAILQ_FIRST(&t->buckets[i]); + STAILQ_REMOVE(&t->buckets[i], e, hashentry, entry); + idx = entry_hash(t, e->key, e->keysize) % nbuckets; + STAILQ_INSERT_HEAD(&buckets[idx], e, entry); + } + } + + free(t->buckets); + t->buckets = buckets; + t->nbuckets = nbuckets; + return 0; +} + +static int +table_grow(struct hashtable *t) +{ + size_t nbuckets; + + if (t->flags & HASHTABLE_F_NOMEM) + return 0; + + if (t->nbuckets >= UINT_MAX / 2) + nbuckets = UINT_MAX; + else + nbuckets = t->nbuckets * 2; + + return table_resize(t, nbuckets); +} + +int +hashtable_add(struct hashtable *t, void *key, size_t keysize, + void *value, size_t valsize) +{ + struct hashentry *e; + uint64_t idx; + struct hashbucket *bucket; + + /* + * Do not allow adding more entries during traversal. + * This function may resize the table. + */ + if (t->flags & HASHTABLE_F_TRAVERSAL) + return -1; + + if (t->nentries == UINT_MAX) + return -1; + + idx = entry_hash(t, key, keysize) % t->nbuckets; + bucket = &t->buckets[idx]; + + /* Require unique keys. */ + STAILQ_FOREACH(e, bucket, entry) { + if (e->keysize == keysize && memcmp(e->key, key, keysize) == 0) + return -1; + } + + e = calloc(1, sizeof(*e)); + if (e == NULL) + return -1; + + e->key = key; + e->keysize = keysize; + e->value = value; + e->valsize = valsize; + + STAILQ_INSERT_HEAD(bucket, e, entry); + t->nentries++; + + if (t->nbuckets < t->nentries) + if (table_grow(t) == -1) + return -1; + + return 0; +} + +static struct hashentry * +find_entry(struct hashtable *t, void *key, size_t keysize) +{ + uint64_t idx = entry_hash(t, key, keysize) % t->nbuckets; + struct hashbucket *bucket = &t->buckets[idx]; + struct hashentry *e; + + STAILQ_FOREACH(e, bucket, entry) { + if (e->keysize == keysize && memcmp(e->key, key, keysize) == 0) + return e; + } + + return NULL; +} + +void * +hashtable_get_keyptr(struct hashtable *t, void *key, size_t keysize) +{ + struct hashentry *e = find_entry(t, key, keysize); + return e ? e->key : NULL; +} + +void * +hashtable_get_value(struct hashtable *t, void *key, size_t keysize) +{ + struct hashentry *e = find_entry(t, key, keysize); + return e ? e->value : NULL; +} + +int +hashtable_remove(struct hashtable *t, void **keyptr, void **value, + size_t *valsize, void *key, size_t keysize) +{ + uint64_t idx; + struct hashbucket *bucket; + struct hashentry *e; + + if (keyptr) + *keyptr = NULL; + if (value) + *value = NULL; + if (valsize) + *valsize = 0; + + if (t->nentries == 0) + return -1; + + idx = entry_hash(t, key, keysize) % t->nbuckets; + bucket = &t->buckets[idx]; + STAILQ_FOREACH(e, bucket, entry) { + if (e->keysize == keysize && memcmp(e->key, key, keysize) == 0) + break; + } + if (e == NULL) + return -1; + + if (keyptr) + *keyptr = e->key; + if (value) + *value = e->value; + if (valsize) + *valsize = e->valsize; + + STAILQ_REMOVE(bucket, e, hashentry, entry); + free(e); + t->nentries--; + + return 0; +} + +int +hashtable_contains(struct hashtable *t, void *key, size_t keysize) +{ + struct hashentry *e = find_entry(t, key, keysize); + return e ? 1 : 0; +} + +int +hashtable_foreach(struct hashtable *t, + int (*cb)(void *, size_t, void *, size_t, void *), + void *cb_arg) +{ + struct hashbucket *bucket; + struct hashentry *e, *tmp; + size_t i; + int ret = 0; + + t->flags |= HASHTABLE_F_TRAVERSAL; + for (i = 0; i < t->nbuckets; i++) { + bucket = &t->buckets[i]; + STAILQ_FOREACH_SAFE(e, bucket, entry, tmp) { + ret = (*cb)(e->key, e->keysize, e->value, e->valsize, + cb_arg); + if (ret) + goto done; + } + } +done: + t->flags &= ~HASHTABLE_F_TRAVERSAL; + return ret; +} + +int +hashtable_num_entries(struct hashtable *t) +{ + return t->nentries; +}