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>

2 files changed, 0 insertions, 448 deletions

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 */