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 <dh.herrmann@gmail.com>

8 files changed, 322 insertions, 756 deletions

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 <stdlib.h>
-#include <limits.h>
-#include <stdbool.h>
-#include <assert.h>
-
-/* 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 <stdint.h>
-#include <stdbool.h>
-#include <stdlib.h>
-
-/**
- * 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 <dh.herrmann@gmail.com>
- *
- * 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 <errno.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdlib.h>
-#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 <stdbool.h>
 #include <stdlib.h>
 #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 <dh.herrmann@gmail.com>
- *
- * 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 <dh.herrmann@gmail.com>
+ *
+ * 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
+	)
+)