From 2317fdc124c61eeba5c4d0c2f6fd1690c887dc5a Mon Sep 17 00:00:00 2001 From: Mohamed Aslan Date: Thu, 14 Jan 2016 01:09:09 -0500 Subject: [PATCH] import hashtab --- .indent.pro | 22 ++++++ Makefile | 28 +++++++ Makefile.generic | 7 ++ example.c | 75 +++++++++++++++++++ hashtab.c | 218 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ hashtab.h | 48 ++++++++++++ 6 files changed, 398 insertions(+) create mode 100644 .indent.pro create mode 100644 Makefile create mode 100644 Makefile.generic create mode 100644 example.c create mode 100644 hashtab.c create mode 100644 hashtab.h diff --git a/.indent.pro b/.indent.pro new file mode 100644 index 0000000..fd7b500 --- /dev/null +++ b/.indent.pro @@ -0,0 +1,22 @@ +-bad +-br +-ce +-ci4 +-d0 +-di1 +-ei +-i8 +-l80 +-ncdb +-nlp +-npcs +-psl +-sc +-ut +-Tsize_t +-Ttime_t +-Tuint8_t +-Tuint32_t +-Thashtab +-Thashtab_options +-Thashtab_kv diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..ab6dacf --- /dev/null +++ b/Makefile @@ -0,0 +1,28 @@ +LIB= hashtab +SRCS= hashtab.c +HDRS= hashtab.h +SHLIB_MAJOR= 0 +SHLIB_MINOR= 1 +#MAN= hashtab.3 +#MLINKS= hashtab.3 hashtab_init.3 \ +# hashtab.3 hashtab_put.3 \ +# hashtab.3 hashtab_get.3 \ +# hashtab.3 hashtab_del.3 \ +# hashtab.3 hashtab_first.3 \ +# hashtab.3 hashtab_next.3 \ +# hashtab.3 hashtab_at.3 + +CFLAGS+= -Wall -Werror +COPTS+= -g + + +includes: + @cd ${.CURDIR}; for i in $(HDRS); do \ + j="cmp -s $$i ${DESTDIR}/usr/include/$$i || \ + ${INSTALL} ${INSTALL_COPY} -o ${BINOWN} -g ${BINGRP} \ + -m 444 $$i ${DESTDIR}/usr/include"; \ + echo $$j; \ + eval "$$j"; \ + done + +.include diff --git a/Makefile.generic b/Makefile.generic new file mode 100644 index 0000000..f85bdbe --- /dev/null +++ b/Makefile.generic @@ -0,0 +1,7 @@ +CFLAGS+=-I. -Wall +all: + cc -o hashtab.o -c hashtab.c $(CFLAGS) + cc -o example.o -c example.c $(CFLAGS) + cc -o example example.o hashtab.o $(CFLAGS) +clean: + rm -f *.o example diff --git a/example.c b/example.c new file mode 100644 index 0000000..4a34ce1 --- /dev/null +++ b/example.c @@ -0,0 +1,75 @@ +/* + * Copyright (c) 2015 Mohamed Aslan + * + * 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 + +int +main(int argc, char **argv) +{ + int i; + struct hashtab ht; + char *key, *val; + size_t key_size, val_size; + size_t iter; + char *keys[] = {"hi", "hello", "world", "hello world", "open", "source", "kernel", "hack"}; + char *values[] = {"1", "2", "3", "4", "5", "6", "7", "8"}; + + if (!hashtab_init(&ht, 4, NULL)) + errx(1, "hashtab_init"); + for (i = 0; i < 8; i++) { + hashtab_put(&ht, keys[i], strlen(keys[i]), values[i], strlen(values[i]) + 1); + printf("%s -> %s\n", keys[i], values[i]); + } + printf("\n"); + for (i = 0; i < 8; i++) { + hashtab_get(&ht, keys[i], strlen(keys[i]), (void **) &val, &val_size); + printf("%s -> %s\n", keys[i], val); + } + + printf("\nloop 1\n"); + if (hashtab_first(&ht, &iter)) { + do { + hashtab_at(&ht, iter, (void *) &key, &key_size, (void **) &val, &val_size); + printf("%s -> %s\n", key, val); + } while (hashtab_next(&ht, &iter)); + } + printf("done\n"); + + printf("loop 2\n"); + HASHTAB_FOREACH(ht, iter, key, key_size, val, val_size) { + hashtab_at(&ht, iter, (void *) &key, &key_size, (void **) &val, &val_size); + printf("%s -> %s\n", key, val); + } + printf("done\n"); + + + printf("\n"); + hashtab_put(&ht, "world", strlen("world"), "10", strlen("10") + 1); + hashtab_get(&ht, "world", strlen("world"), (void **) &val, &val_size); + printf("world -> %s\n", val); + printf("\n"); + hashtab_del(&ht, "world", strlen("world")); + if (hashtab_get(&ht, "world", strlen("world"), (void **) &val, &val_size)) + printf("world -> %s\n", val); + else + printf("world not found\n"); + return 0; +} diff --git a/hashtab.c b/hashtab.c new file mode 100644 index 0000000..d043ed8 --- /dev/null +++ b/hashtab.c @@ -0,0 +1,218 @@ +/* + * Copyright (c) 2015 Mohamed Aslan + * + * 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 "hashtab.h" + + +#define KV_USED (1 << 0) + + +struct hashtab_kv { + void *key; + void *val; + size_t key_size; + size_t val_size; + uint8_t flags; +}; + +static uint32_t +pjw_hash(void *key, size_t size) +{ + int i; + uint8_t *ptr = (uint8_t *) key; + uint32_t h = 0, hi; + + for (i = 0; i < size; i++) { + h = (h << 4) + ptr[i]; + if ((hi = h & 0xf0000000)) + h ^= hi >> 24; + hi &= ~hi; + } + return h; +} + +static int +alloc(struct hashtab *ht, void *key, size_t size, size_t *idx) +{ + size_t i = 0; + size_t h; + + h = ht->hash(key, size) % ht->size; + while (i++ < ht->size) { + if (!(ht->kv[h].flags & KV_USED)) { /* 1. empty slot */ + *idx = h; + return 1; + } + if (ht->kv[h].key_size == size) { /* 2. used by the same + * key */ + if (!(memcmp(ht->kv[h].key, key, size))) { + *idx = h; + return 1; + } + } + h = (h + 1) % ht->size; /* 3. used by a different key */ + } + return 0; +} + +static int +lookup(struct hashtab *ht, void *key, size_t size, size_t *idx) +{ + size_t i = 0; + size_t h; + + h = ht->hash(key, size) % ht->size; + while (i++ < ht->size) { + if (ht->kv[h].key_size == size) { + if (!(memcmp(ht->kv[h].key, key, size))) { + *idx = h; + return 1; + } + } + h = (h + 1) % ht->size; + } + return 0; +} + +static void +put(struct hashtab *ht, size_t idx, void *key, size_t ksize, void *val, + size_t vsize) +{ + ht->kv[idx].key = malloc(ksize); + ht->kv[idx].key_size = ksize; + ht->kv[idx].val = malloc(vsize); + ht->kv[idx].val_size = vsize; + memcpy(ht->kv[idx].key, key, ksize); + memcpy(ht->kv[idx].val, val, vsize); + ht->kv[idx].flags |= KV_USED; +} + +static void +get(struct hashtab *ht, size_t idx, void **val, size_t *size) +{ + *val = ht->kv[idx].val; + *size = ht->kv[idx].val_size; +} + +static void +del(struct hashtab *ht, size_t idx) +{ + free(ht->kv[idx].key); + free(ht->kv[idx].val); + memset(ht->kv, 0, sizeof(struct hashtab_kv)); +} + +int +hashtab_init(struct hashtab *ht, uint8_t size, struct hashtab_options *opts) +{ + if (ht == NULL) + return 0; + if (size < HTMIN || size > HTMAX) + return 0; + ht->size = 1UL << size; + ht->kv = (struct hashtab_kv *) calloc(ht->size, + sizeof(struct hashtab_kv)); + ht->hash = pjw_hash; + return 1; +} + +int +hashtab_first(struct hashtab *ht, size_t *iter) +{ + if (ht == NULL || iter == NULL) + return 0; + for (*iter = 0; *iter < ht->size; (*iter)++) { + if (!(ht->kv[*iter].flags & KV_USED)) + continue; + return 1; + } + return 0; +} + +int +hashtab_next(struct hashtab *ht, size_t *iter) +{ + if (ht == NULL || iter == NULL) + return 0; + for ((*iter)++; *iter < ht->size; (*iter)++) { + if (!(ht->kv[*iter].flags & KV_USED)) + continue; + return 1; + } + return 0; +} + +int +hashtab_at(struct hashtab *ht, size_t iter, void **key, size_t *ksize, + void **val, size_t *vsize) +{ + if (ht == NULL || key == NULL || ksize == NULL || val == NULL || + vsize == NULL) + return 0; + if (!(ht->kv[iter].flags & KV_USED)) + return 0; + *key = ht->kv[iter].key; + *ksize = ht->kv[iter].key_size; + *val = ht->kv[iter].val; + *vsize = ht->kv[iter].val_size; + return 1; +} + +int +hashtab_put(struct hashtab *ht, void *key, size_t ksize, void *val, + size_t vsize) +{ + size_t idx; + + if (ht == NULL) + return 0; + if (!alloc(ht, key, ksize, &idx)) + return 0; + put(ht, idx, key, ksize, val, vsize); + return 1; +} + +int +hashtab_get(struct hashtab *ht, void *key, size_t ksize, void **val, + size_t *vsize) +{ + size_t idx; + + if (ht == NULL || val == NULL || vsize == NULL) + return 0; + if (!lookup(ht, key, ksize, &idx)) + return 0; + get(ht, idx, val, vsize); + return 1; +} + +int +hashtab_del(struct hashtab *ht, void *key, size_t size) +{ + size_t idx; + + if (ht == NULL) + return 0; + if (!lookup(ht, key, size, &idx)) + return 0; + del(ht, idx); + return 1; +} diff --git a/hashtab.h b/hashtab.h new file mode 100644 index 0000000..6397d7e --- /dev/null +++ b/hashtab.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2015 Mohamed Aslan + * + * 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. + */ + +#ifndef HASHTAB_H +#define HASHTAB_H + +#include + +#define HTMIN 4 +#define HTMAX 24 + +struct hashtab { + struct hashtab_kv *kv; + size_t size; + uint32_t (*hash) (void *, size_t); +}; + +struct hashtab_options; + +int hashtab_init(struct hashtab *, uint8_t, struct hashtab_options *); +int hashtab_put(struct hashtab *, void *, size_t, void *, size_t); +int hashtab_get(struct hashtab *, void *, size_t, void **, size_t *); +int hashtab_del(struct hashtab *, void *, size_t); +int hashtab_first(struct hashtab *, size_t *); +int hashtab_next(struct hashtab *, size_t *); +int hashtab_at(struct hashtab *, size_t, void **, size_t *, void **, size_t *); + +#define HASHTAB_FOREACH(ht, itr, key, ksize, val, vsize) \ + for (hashtab_first(&(ht), &(itr)) ; \ + hashtab_at(&(ht), (itr), (void *)&(key), &(ksize), \ + (void *)&(val), &(vsize)) ; \ + hashtab_next(&(ht), &(itr)) \ + ) + +#endif -- 2.11.4.GIT