From 938910553edfd7c36de64e914b00caa2c9c72b98 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Wed, 23 Oct 2013 18:12:04 +0200 Subject: Remove old hashtable and replace tests shl_hashtable is no longer used. Remove it and replace the tests with shl_htable tests. Signed-off-by: David Herrmann --- .gitignore | 2 +- Makefile.am | 14 ++- external/htable.c | 273 -------------------------------------------- external/htable.h | 175 ---------------------------- src/shl_hashtable.h | 201 -------------------------------- test/test_common.h | 3 +- test/test_hashtable.c | 99 ---------------- test/test_htable.c | 311 ++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 322 insertions(+), 756 deletions(-) delete mode 100644 external/htable.c delete mode 100644 external/htable.h delete mode 100644 src/shl_hashtable.h delete mode 100644 test/test_hashtable.c create mode 100644 test/test_htable.c diff --git a/.gitignore b/.gitignore index 0c55793..00fe76c 100644 --- a/.gitignore +++ b/.gitignore @@ -23,4 +23,4 @@ libtool m4/ stamp-h1 test-suite.log -test_hashtable +test_htable diff --git a/Makefile.am b/Makefile.am index d480820..3fb5efb 100644 --- a/Makefile.am +++ b/Makefile.am @@ -146,8 +146,10 @@ endif # if BUILD_HAVE_CHECK -check_PROGRAMS += test_hashtable -TESTS += test_hashtable +check_PROGRAMS += \ + test_htable +TESTS += \ + test_htable endif test_sources = \ @@ -161,10 +163,10 @@ test_cflags = \ test_lflags = \ $(AM_LDFLAGS) -test_hashtable_SOURCES = test/test_hashtable.c $(test_sources) -test_hashtable_CPPFLAGS = $(test_cflags) -test_hashtable_LDADD = $(test_libs) -test_hashtable_LDFLAGS = $(test_lflags) +test_htable_SOURCES = test/test_htable.c $(test_sources) +test_htable_CPPFLAGS = $(test_cflags) +test_htable_LDADD = $(test_libs) +test_htable_LDFLAGS = $(test_lflags) # # Phony targets diff --git a/external/htable.c b/external/htable.c deleted file mode 100644 index be460c3..0000000 --- a/external/htable.c +++ /dev/null @@ -1,273 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#define COLD __attribute__((cold)) -#include "htable.h" -#include -#include -#include -#include - -/* We use 0x1 as deleted marker. */ -#define HTABLE_DELETED (0x1) - -/* We clear out the bits which are always the same, and put metadata there. */ -static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, - uintptr_t e) -{ - return e & ht->common_mask; -} - -static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e) -{ - return (void *)((e & ~ht->common_mask) | ht->common_bits); -} - -static inline uintptr_t make_hval(const struct htable *ht, - const void *p, uintptr_t bits) -{ - return ((uintptr_t)p & ~ht->common_mask) | bits; -} - -static inline bool entry_is_valid(uintptr_t e) -{ - return e > HTABLE_DELETED; -} - -static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, - size_t hash) -{ - /* Shuffling the extra bits (as specified in mask) down the - * end is quite expensive. But the lower bits are redundant, so - * we fold the value first. */ - return (hash ^ (hash >> ht->bits)) - & ht->common_mask & ~ht->perfect_bit; -} - -void htable_init(struct htable *ht, - size_t (*rehash)(const void *elem, void *priv), void *priv) -{ - struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); - *ht = empty; - ht->rehash = rehash; - ht->priv = priv; - ht->table = &ht->perfect_bit; -} - -void htable_clear(struct htable *ht) -{ - if (ht->table != &ht->perfect_bit) - free((void *)ht->table); - htable_init(ht, ht->rehash, ht->priv); -} - -static size_t hash_bucket(const struct htable *ht, size_t h) -{ - return h & ((1 << ht->bits)-1); -} - -static void *htable_val(const struct htable *ht, - struct htable_iter *i, size_t hash, uintptr_t perfect) -{ - uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; - - while (ht->table[i->off]) { - if (ht->table[i->off] != HTABLE_DELETED) { - if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) - return get_raw_ptr(ht, ht->table[i->off]); - } - i->off = (i->off + 1) & ((1 << ht->bits)-1); - h2 &= ~perfect; - } - return NULL; -} - -void *htable_firstval(const struct htable *ht, - struct htable_iter *i, size_t hash) -{ - i->off = hash_bucket(ht, hash); - return htable_val(ht, i, hash, ht->perfect_bit); -} - -void *htable_nextval(const struct htable *ht, - struct htable_iter *i, size_t hash) -{ - i->off = (i->off + 1) & ((1 << ht->bits)-1); - return htable_val(ht, i, hash, 0); -} - -void *htable_first(const struct htable *ht, struct htable_iter *i) -{ - for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) { - if (entry_is_valid(ht->table[i->off])) - return get_raw_ptr(ht, ht->table[i->off]); - } - return NULL; -} - -void *htable_next(const struct htable *ht, struct htable_iter *i) -{ - for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) { - if (entry_is_valid(ht->table[i->off])) - return get_raw_ptr(ht, ht->table[i->off]); - } - return NULL; -} - -/* This does not expand the hash table, that's up to caller. */ -static void ht_add(struct htable *ht, const void *new, size_t h) -{ - size_t i; - uintptr_t perfect = ht->perfect_bit; - - i = hash_bucket(ht, h); - - while (entry_is_valid(ht->table[i])) { - perfect = 0; - i = (i + 1) & ((1 << ht->bits)-1); - } - ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); -} - -static COLD bool double_table(struct htable *ht) -{ - unsigned int i; - size_t oldnum = (size_t)1 << ht->bits; - uintptr_t *oldtable, e; - - oldtable = ht->table; - ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); - if (!ht->table) { - ht->table = oldtable; - return false; - } - ht->bits++; - ht->max = ((size_t)3 << ht->bits) / 4; - ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; - - /* If we lost our "perfect bit", get it back now. */ - if (!ht->perfect_bit && ht->common_mask) { - for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) { - if (ht->common_mask & ((size_t)1 << i)) { - ht->perfect_bit = (size_t)1 << i; - break; - } - } - } - - if (oldtable != &ht->perfect_bit) { - for (i = 0; i < oldnum; i++) { - if (entry_is_valid(e = oldtable[i])) { - void *p = get_raw_ptr(ht, e); - ht_add(ht, p, ht->rehash(p, ht->priv)); - } - } - free(oldtable); - } - ht->deleted = 0; - return true; -} - -static COLD void rehash_table(struct htable *ht) -{ - size_t start, i; - uintptr_t e; - - /* Beware wrap cases: we need to start from first empty bucket. */ - for (start = 0; ht->table[start]; start++); - - for (i = 0; i < (size_t)1 << ht->bits; i++) { - size_t h = (i + start) & ((1 << ht->bits)-1); - e = ht->table[h]; - if (!e) - continue; - if (e == HTABLE_DELETED) - ht->table[h] = 0; - else if (!(e & ht->perfect_bit)) { - void *p = get_raw_ptr(ht, e); - ht->table[h] = 0; - ht_add(ht, p, ht->rehash(p, ht->priv)); - } - } - ht->deleted = 0; -} - -/* We stole some bits, now we need to put them back... */ -static COLD void update_common(struct htable *ht, const void *p) -{ - unsigned int i; - uintptr_t maskdiff, bitsdiff; - - if (ht->elems == 0) { - /* Always reveal one bit of the pointer in the bucket, - * so it's not zero or HTABLE_DELETED (1), even if - * hash happens to be 0. Assumes (void *)1 is not a - * valid pointer. */ - for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) { - if ((uintptr_t)p & ((uintptr_t)1 << i)) - break; - } - - ht->common_mask = ~((uintptr_t)1 << i); - ht->common_bits = ((uintptr_t)p & ht->common_mask); - ht->perfect_bit = 1; - return; - } - - /* Find bits which are unequal to old common set. */ - maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); - - /* These are the bits which go there in existing entries. */ - bitsdiff = ht->common_bits & maskdiff; - - for (i = 0; i < (size_t)1 << ht->bits; i++) { - if (!entry_is_valid(ht->table[i])) - continue; - /* Clear the bits no longer in the mask, set them as - * expected. */ - ht->table[i] &= ~maskdiff; - ht->table[i] |= bitsdiff; - } - - /* Take away those bits from our mask, bits and perfect bit. */ - ht->common_mask &= ~maskdiff; - ht->common_bits &= ~maskdiff; - ht->perfect_bit &= ~maskdiff; -} - -bool htable_add(struct htable *ht, size_t hash, const void *p) -{ - if (ht->elems+1 > ht->max && !double_table(ht)) - return false; - if (ht->elems+1 + ht->deleted > ht->max_with_deleted) - rehash_table(ht); - assert(p); - if (((uintptr_t)p & ht->common_mask) != ht->common_bits) - update_common(ht, p); - - ht_add(ht, p, hash); - ht->elems++; - return true; -} - -bool htable_del(struct htable *ht, size_t h, const void *p) -{ - struct htable_iter i; - void *c; - - for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { - if (c == p) { - htable_delval(ht, &i); - return true; - } - } - return false; -} - -void htable_delval(struct htable *ht, struct htable_iter *i) -{ - assert(i->off < (size_t)1 << ht->bits); - assert(entry_is_valid(ht->table[i->off])); - - ht->elems--; - ht->table[i->off] = HTABLE_DELETED; - ht->deleted++; -} diff --git a/external/htable.h b/external/htable.h deleted file mode 100644 index c555189..0000000 --- a/external/htable.h +++ /dev/null @@ -1,175 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#ifndef CCAN_HTABLE_H -#define CCAN_HTABLE_H -#include -#include -#include - -/** - * struct htable - private definition of a htable. - * - * It's exposed here so you can put it in your structures and so we can - * supply inline functions. - */ -struct htable { - size_t (*rehash)(const void *elem, void *priv); - void *priv; - unsigned int bits; - size_t elems, deleted, max, max_with_deleted; - /* These are the bits which are the same in all pointers. */ - uintptr_t common_mask, common_bits; - uintptr_t perfect_bit; - uintptr_t *table; -}; - -/** - * HTABLE_INITIALIZER - static initialization for a hash table. - * @name: name of this htable. - * @rehash: hash function to use for rehashing. - * @priv: private argument to @rehash function. - * - * This is useful for setting up static and global hash tables. - * - * Example: - * // For simplicity's sake, say hash value is contents of elem. - * static size_t rehash(const void *elem, void *unused) - * { - * return *(size_t *)elem; - * } - * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); - */ -#define HTABLE_INITIALIZER(name, rehash, priv) \ - { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit } - -/** - * htable_init - initialize an empty hash table. - * @ht: the hash table to initialize - * @rehash: hash function to use for rehashing. - * @priv: private argument to @rehash function. - */ -void htable_init(struct htable *ht, - size_t (*rehash)(const void *elem, void *priv), void *priv); - -/** - * htable_clear - empty a hash table. - * @ht: the hash table to clear - * - * This doesn't do anything to any pointers left in it. - */ -void htable_clear(struct htable *ht); - -/** - * htable_rehash - use a hashtree's rehash function - * @elem: the argument to rehash() - * - */ -size_t htable_rehash(const void *elem); - -/** - * htable_add - add a pointer into a hash table. - * @ht: the htable - * @hash: the hash value of the object - * @p: the non-NULL pointer - * - * Also note that this can only fail due to allocation failure. Otherwise, it - * returns true. - */ -bool htable_add(struct htable *ht, size_t hash, const void *p); - -/** - * htable_del - remove a pointer from a hash table - * @ht: the htable - * @hash: the hash value of the object - * @p: the pointer - * - * Returns true if the pointer was found (and deleted). - */ -bool htable_del(struct htable *ht, size_t hash, const void *p); - -/** - * struct htable_iter - iterator or htable_first or htable_firstval etc. - * - * This refers to a location inside the hashtable. - */ -struct htable_iter { - size_t off; -}; - -/** - * htable_firstval - find a candidate for a given hash value - * @htable: the hashtable - * @i: the struct htable_iter to initialize - * @hash: the hash value - * - * You'll need to check the value is what you want; returns NULL if none. - * See Also: - * htable_delval() - */ -void *htable_firstval(const struct htable *htable, - struct htable_iter *i, size_t hash); - -/** - * htable_nextval - find another candidate for a given hash value - * @htable: the hashtable - * @i: the struct htable_iter to initialize - * @hash: the hash value - * - * You'll need to check the value is what you want; returns NULL if no more. - */ -void *htable_nextval(const struct htable *htable, - struct htable_iter *i, size_t hash); - -/** - * htable_get - find an entry in the hash table - * @ht: the hashtable - * @h: the hash value of the entry - * @cmp: the comparison function - * @ptr: the pointer to hand to the comparison function. - * - * Convenient inline wrapper for htable_firstval/htable_nextval loop. - */ -static inline void *htable_get(const struct htable *ht, - size_t h, - bool (*cmp)(const void *candidate, void *ptr), - const void *ptr) -{ - struct htable_iter i; - void *c; - - for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { - if (cmp(c, (void *)ptr)) - return c; - } - return NULL; -} - -/** - * htable_first - find an entry in the hash table - * @ht: the hashtable - * @i: the struct htable_iter to initialize - * - * Get an entry in the hashtable; NULL if empty. - */ -void *htable_first(const struct htable *htable, struct htable_iter *i); - -/** - * htable_next - find another entry in the hash table - * @ht: the hashtable - * @i: the struct htable_iter to use - * - * Get another entry in the hashtable; NULL if all done. - * This is usually used after htable_first or prior non-NULL htable_next. - */ -void *htable_next(const struct htable *htable, struct htable_iter *i); - -/** - * htable_delval - remove an iterated pointer from a hash table - * @ht: the htable - * @i: the htable_iter - * - * Usually used to delete a hash entry after it has been found with - * htable_firstval etc. - */ -void htable_delval(struct htable *ht, struct htable_iter *i); - -#endif /* CCAN_HTABLE_H */ diff --git a/src/shl_hashtable.h b/src/shl_hashtable.h deleted file mode 100644 index 60ea7ca..0000000 --- a/src/shl_hashtable.h +++ /dev/null @@ -1,201 +0,0 @@ -/* - * shl - Dynamic Hashtable - * - * Copyright (c) 2011-2013 David Herrmann - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files - * (the "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be included - * in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -/* - * A dynamic hash table implementation - */ - -#ifndef SHL_HASHTABLE_H -#define SHL_HASHTABLE_H - -#include -#include -#include -#include -#include "external/htable.h" - -struct shl_hashtable; - -typedef unsigned int (*shl_hash_cb) (const void *data); -typedef bool (*shl_equal_cb) (const void *data1, const void *data2); -typedef void (*shl_free_cb) (void *data); - -struct shl_hashentry { - void *key; - void *value; -}; - -struct shl_hashtable { - struct htable tbl; - shl_hash_cb hash_cb; - shl_equal_cb equal_cb; - shl_free_cb free_key; - shl_free_cb free_value; -}; - -static inline unsigned int shl_direct_hash(const void *data) -{ - return (unsigned int)(unsigned long)data; -} - -static inline bool shl_direct_equal(const void *data1, const void *data2) -{ - return data1 == data2; -} - -static size_t shl_rehash(const void *ele, void *priv) -{ - struct shl_hashtable *tbl = priv; - const struct shl_hashentry *ent = ele; - - return tbl->hash_cb(ent->key); -} - -static inline int shl_hashtable_new(struct shl_hashtable **out, - shl_hash_cb hash_cb, - shl_equal_cb equal_cb, - shl_free_cb free_key, - shl_free_cb free_value) -{ - struct shl_hashtable *tbl; - - if (!out || !hash_cb || !equal_cb) - return -EINVAL; - - tbl = malloc(sizeof(*tbl)); - if (!tbl) - return -ENOMEM; - memset(tbl, 0, sizeof(*tbl)); - tbl->hash_cb = hash_cb; - tbl->equal_cb = equal_cb; - tbl->free_key = free_key; - tbl->free_value = free_value; - - htable_init(&tbl->tbl, shl_rehash, tbl); - - *out = tbl; - return 0; -} - -static inline void shl_hashtable_free(struct shl_hashtable *tbl) -{ - struct htable_iter i; - struct shl_hashentry *entry; - - if (!tbl) - return; - - for (entry = htable_first(&tbl->tbl, &i); - entry; - entry = htable_next(&tbl->tbl, &i)) { - htable_delval(&tbl->tbl, &i); - if (tbl->free_key) - tbl->free_key(entry->key); - if (tbl->free_value) - tbl->free_value(entry->value); - free(entry); - } - - htable_clear(&tbl->tbl); - free(tbl); -} - -static inline int shl_hashtable_insert(struct shl_hashtable *tbl, void *key, - void *value) -{ - struct shl_hashentry *entry; - size_t hash; - - if (!tbl) - return -EINVAL; - - entry = malloc(sizeof(*entry)); - if (!entry) - return -ENOMEM; - entry->key = key; - entry->value = value; - - hash = tbl->hash_cb(key); - - if (!htable_add(&tbl->tbl, hash, entry)) { - free(entry); - return -ENOMEM; - } - - return 0; -} - -static inline void shl_hashtable_remove(struct shl_hashtable *tbl, void *key) -{ - struct htable_iter i; - struct shl_hashentry *entry; - size_t hash; - - if (!tbl) - return; - - hash = tbl->hash_cb(key); - - for (entry = htable_firstval(&tbl->tbl, &i, hash); - entry; - entry = htable_nextval(&tbl->tbl, &i, hash)) { - if (tbl->equal_cb(key, entry->key)) { - htable_delval(&tbl->tbl, &i); - if (tbl->free_key) - tbl->free_key(entry->key); - if (tbl->free_value) - tbl->free_value(entry->value); - free(entry); - return; - } - } -} - -static inline bool shl_hashtable_find(struct shl_hashtable *tbl, void **out, - void *key) -{ - struct htable_iter i; - struct shl_hashentry *entry; - size_t hash; - - if (!tbl) - return false; - - hash = tbl->hash_cb(key); - - for (entry = htable_firstval(&tbl->tbl, &i, hash); - entry; - entry = htable_nextval(&tbl->tbl, &i, hash)) { - if (tbl->equal_cb(key, entry->key)) { - if (out) - *out = entry->value; - return true; - } - } - - return false; -} - -#endif /* SHL_HASHTABLE_H */ diff --git a/test/test_common.h b/test/test_common.h index c9939bb..75d5072 100644 --- a/test/test_common.h +++ b/test/test_common.h @@ -43,7 +43,8 @@ #include #include #include "libtsm.h" -#include "shl_hashtable.h" +#include "libtsm_int.h" +#include "shl_htable.h" /* lower address-space is protected from user-allocation, so this is invalid */ #define TEST_INVALID_PTR ((void*)0x10) diff --git a/test/test_hashtable.c b/test/test_hashtable.c deleted file mode 100644 index 83bf34f..0000000 --- a/test/test_hashtable.c +++ /dev/null @@ -1,99 +0,0 @@ -/* - * TSM - Hashtable Tests - * - * Copyright (c) 2012-2013 David Herrmann - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files - * (the "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be included - * in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -/* - * Hashtable Tests - * Stress tests for the internal hashtable implementation. - */ - -#include "test_common.h" - -START_TEST(test_hashtable_setup_valid) -{ - struct shl_hashtable *t = NULL; - int r; - - r = shl_hashtable_new(&t, shl_direct_hash, shl_direct_equal, - NULL, NULL); - ck_assert(r == 0); - ck_assert(t != NULL); - - shl_hashtable_free(t); -} -END_TEST - -START_TEST(test_hashtable_setup_invalid) -{ - struct shl_hashtable *t = TEST_INVALID_PTR; - int r; - - r = shl_hashtable_new(NULL, shl_direct_hash, shl_direct_equal, - NULL, NULL); - ck_assert(r != 0); - ck_assert(t == TEST_INVALID_PTR); - - r = shl_hashtable_new(&t, NULL, shl_direct_equal, - NULL, NULL); - ck_assert(r != 0); - ck_assert(t == TEST_INVALID_PTR); - - r = shl_hashtable_new(&t, shl_direct_hash, NULL, - NULL, NULL); - ck_assert(r != 0); - ck_assert(t == TEST_INVALID_PTR); - - r = shl_hashtable_new(&t, NULL, NULL, - NULL, NULL); - ck_assert(r != 0); - ck_assert(t == TEST_INVALID_PTR); - - r = shl_hashtable_new(NULL, NULL, NULL, - NULL, NULL); - ck_assert(r != 0); - ck_assert(t == TEST_INVALID_PTR); -} -END_TEST - -TEST_DEFINE_CASE(setup) - TEST(test_hashtable_setup_valid) - TEST(test_hashtable_setup_invalid) -TEST_END_CASE - -START_TEST(test_hashtable_add_1) -{ -} -END_TEST - -TEST_DEFINE_CASE(add) - TEST(test_hashtable_add_1) -TEST_END_CASE - -TEST_DEFINE( - TEST_SUITE(hashtable, - TEST_CASE(setup), - TEST_CASE(add), - TEST_END - ) -) diff --git a/test/test_htable.c b/test/test_htable.c new file mode 100644 index 0000000..74e5c2d --- /dev/null +++ b/test/test_htable.c @@ -0,0 +1,311 @@ +/* + * TSM - Hashtable Tests + * + * Copyright (c) 2012-2013 David Herrmann + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files + * (the "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + + +#include "test_common.h" + +static struct shl_htable ht = SHL_HTABLE_INIT_STR(ht); +static struct shl_htable uht = SHL_HTABLE_INIT_ULONG(uht); + +struct node { + char huge_padding[16384]; + uint8_t v; + char paaaaaadding[16384]; + char *key; + unsigned long ul; + char more_padding[32768]; + size_t hash; +}; + +#define to_node(_key) shl_htable_offsetof((_key), struct node, key) +#define ul_to_node(_key) shl_htable_offsetof((_key), struct node, ul) + +static struct node o[] = { + { .v = 0, .key = "o0", .ul = 0 }, + { .v = 1, .key = "o1", .ul = 1 }, + { .v = 2, .key = "o2", .ul = 2 }, + { .v = 3, .key = "o3", .ul = 3 }, + { .v = 4, .key = "o4", .ul = 4 }, + { .v = 5, .key = "o5", .ul = 5 }, + { .v = 6, .key = "o6", .ul = 6 }, + { .v = 7, .key = "o7", .ul = 7 }, +}; + +static void test_htable_str_cb(char **k, void *ctx) +{ + int *num = ctx; + + ck_assert(to_node(k)->v == to_node(k)->ul); + ++*num; +} + +START_TEST(test_htable_str) +{ + int r, i, num; + char **k; + bool b; + + /* insert once, remove once, try removing again */ + + ck_assert(!o[0].hash); + r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash); + ck_assert(!r); + ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL)); + + b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == 0); + + k = NULL; + b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k); + ck_assert(!b); + ck_assert(k == NULL); + + /* insert twice, remove twice, try removing again */ + + r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash); + ck_assert(!r); + ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL)); + + r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash); + ck_assert(!r); + ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL)); + + b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == 0); + + b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == 0); + + k = NULL; + b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k); + ck_assert(!b); + ck_assert(k == NULL); + + /* same as before but without hash-cache */ + + r = shl_htable_insert_str(&ht, &o[0].key, NULL); + ck_assert(!r); + + r = shl_htable_insert_str(&ht, &o[0].key, NULL); + ck_assert(!r); + + b = shl_htable_remove_str(&ht, o[0].key, NULL, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == 0); + + b = shl_htable_remove_str(&ht, o[0].key, NULL, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == 0); + + k = NULL; + b = shl_htable_remove_str(&ht, o[0].key, NULL, &k); + ck_assert(!b); + ck_assert(k == NULL); + + /* insert all elements and verify empty hash-caches */ + + o[0].hash = 0; + for (i = 0; i < 8; ++i) { + ck_assert(!o[i].hash); + r = shl_htable_insert_str(&ht, &o[i].key, &o[i].hash); + ck_assert(!r); + ck_assert(o[i].hash == shl_htable_rehash_str(&o[i].key, NULL)); + } + + /* verify */ + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_lookup_str(&ht, o[i].key, NULL, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == i); + } + + /* remove all elements again */ + + for (i = 0; i < 8; ++i) { + b = shl_htable_remove_str(&ht, o[i].key, NULL, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(to_node(k)->v == i); + } + + /* verify they're gone */ + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_remove_str(&ht, o[i].key, NULL, &k); + ck_assert(!b); + ck_assert(k == NULL); + } + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_lookup_str(&ht, o[i].key, NULL, &k); + ck_assert(!b); + ck_assert(k == NULL); + } + + num = 0; + shl_htable_visit_str(&ht, test_htable_str_cb, &num); + ck_assert(num == 0); + + num = 0; + shl_htable_clear_str(&ht, test_htable_str_cb, &num); + ck_assert(num == 0); + + /* test shl_htable_clear_str() */ + + for (i = 0; i < 8; ++i) { + r = shl_htable_insert_str(&ht, &o[i].key, &o[i].hash); + ck_assert(!r); + } + + num = 0; + shl_htable_visit_str(&ht, test_htable_str_cb, &num); + ck_assert(num == 8); + + num = 0; + shl_htable_clear_str(&ht, test_htable_str_cb, &num); + ck_assert(num == 8); +} +END_TEST + +static void test_htable_ulong_cb(unsigned long *k, void *ctx) +{ + int *num = ctx; + + ck_assert(ul_to_node(k)->v == ul_to_node(k)->ul); + ++*num; +} + +START_TEST(test_htable_ulong) +{ + int r, i, num; + unsigned long *k; + bool b; + + /* insert once, remove once, try removing again */ + + r = shl_htable_insert_ulong(&uht, &o[0].ul); + ck_assert(!r); + ck_assert(o[0].ul == shl_htable_rehash_ulong(&o[0].ul, NULL)); + + b = shl_htable_remove_ulong(&uht, o[0].ul, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(ul_to_node(k)->v == 0); + + k = NULL; + b = shl_htable_remove_ulong(&uht, o[0].ul, &k); + ck_assert(!b); + ck_assert(k == NULL); + + /* insert all */ + + for (i = 0; i < 8; ++i) { + r = shl_htable_insert_ulong(&uht, &o[i].ul); + ck_assert(!r); + } + + /* verify */ + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_lookup_ulong(&uht, o[i].ul, &k); + ck_assert(b); + ck_assert(k != NULL); + } + + /* remove all elements again */ + + for (i = 0; i < 8; ++i) { + b = shl_htable_remove_ulong(&uht, o[i].ul, &k); + ck_assert(b); + ck_assert(k != NULL); + ck_assert(ul_to_node(k)->v == i); + } + + /* verify they're gone */ + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_remove_ulong(&uht, o[i].ul, &k); + ck_assert(!b); + ck_assert(k == NULL); + } + + for (i = 0; i < 8; ++i) { + k = NULL; + b = shl_htable_lookup_ulong(&uht, o[i].ul, &k); + ck_assert(!b); + ck_assert(k == NULL); + } + + num = 0; + shl_htable_visit_ulong(&uht, test_htable_ulong_cb, &num); + ck_assert(num == 0); + + num = 0; + shl_htable_clear_ulong(&uht, test_htable_ulong_cb, &num); + ck_assert(num == 0); + + /* test shl_htable_clear_ulong() */ + + for (i = 0; i < 8; ++i) { + r = shl_htable_insert_ulong(&uht, &o[i].ul); + ck_assert(!r); + } + + num = 0; + shl_htable_visit_ulong(&uht, test_htable_ulong_cb, &num); + ck_assert(num == 8); + + num = 0; + shl_htable_clear_ulong(&uht, test_htable_ulong_cb, &num); + ck_assert(num == 8); +} +END_TEST + +TEST_DEFINE_CASE(misc) + TEST(test_htable_str) + TEST(test_htable_ulong) +TEST_END_CASE + +TEST_DEFINE( + TEST_SUITE(hashtable, + TEST_CASE(misc), + TEST_END + ) +) -- cgit v1.2.3