X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=5a773cd8876d2f36b53733c659757213811651ff;hp=20b6f5ae2dc964c521aa7f517912cd3d4ab9aa6c;hb=7b56762984ce66f38728b542ca347bcb6fe3e981;hpb=74257cee33ae3033f961d5f22a0313b8cb1b18d4

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 20b6f5ae..5a773cd8 100644
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -1,29 +1,14 @@
 /* Licensed under LGPLv2+ - see LICENSE file for details */
 #include <ccan/htable/htable.h>
 #include <ccan/compiler/compiler.h>
-#include <stdint.h>
 #include <stdlib.h>
 #include <limits.h>
 #include <stdbool.h>
 #include <assert.h>
 
-/* This means a struct htable takes at least 512 bytes / 1k (32/64 bits). */
-#define HTABLE_BASE_BITS 7
-
 /* We use 0x1 as deleted marker. */
 #define HTABLE_DELETED (0x1)
 
-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;
-};
-
 /* 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)
@@ -57,35 +42,44 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
 		& ht->common_mask & ~ht->perfect_bit;
 }
 
-struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
-			  void *priv)
+void htable_init(struct htable *ht,
+		 size_t (*rehash)(const void *elem, void *priv), void *priv)
 {
-	struct htable *ht = malloc(sizeof(struct htable));
-	if (ht) {
-		ht->bits = HTABLE_BASE_BITS;
-		ht->rehash = rehash;
-		ht->priv = priv;
-		ht->elems = 0;
-		ht->deleted = 0;
-		ht->max = ((size_t)1 << ht->bits) * 3 / 4;
-		ht->max_with_deleted = ((size_t)1 << ht->bits) * 9 / 10;
-		/* This guarantees we enter update_common first add. */
-		ht->common_mask = -1;
-		ht->common_bits = 0;
-		ht->perfect_bit = 0;
-		ht->table = calloc(1 << ht->bits, sizeof(uintptr_t));
-		if (!ht->table) {
-			free(ht);
-			ht = NULL;
-		}
-	}
-	return ht;
+	struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL);
+	*ht = empty;
+	ht->rehash = rehash;
+	ht->priv = priv;
+	ht->table = &ht->perfect_bit;
 }
 
-void htable_free(const struct htable *ht)
+bool htable_init_sized(struct htable *ht,
+		       size_t (*rehash)(const void *, void *),
+		       void *priv, size_t expect)
+{
+	htable_init(ht, rehash, priv);
+
+	/* Don't go insane with sizing. */
+	for (ht->bits = 1; ((size_t)3 << ht->bits) / 4 < expect; ht->bits++) {
+		if (ht->bits == 30)
+			break;
+	}
+
+	ht->table = calloc(1 << ht->bits, sizeof(size_t));
+	if (!ht->table) {
+		ht->table = &ht->perfect_bit;
+		return false;
+	}
+	ht->max = ((size_t)3 << ht->bits) / 4;
+	ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+
+	return true;
+}
+	
+void htable_clear(struct htable *ht)
 {
-	free((void *)ht->table);
-	free((void *)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)
@@ -141,6 +135,17 @@ void *htable_next(const struct htable *ht, struct htable_iter *i)
 	return NULL;
 }
 
+void *htable_prev(const struct htable *ht, struct htable_iter *i)
+{
+	for (;;) {
+		if (!i->off)
+			return NULL;
+		i->off --;
+		if (entry_is_valid(ht->table[i->off]))
+			return get_raw_ptr(ht, ht->table[i->off]);
+	}
+}
+
 /* 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)
 {
@@ -169,8 +174,8 @@ static COLD bool double_table(struct htable *ht)
 		return false;
 	}
 	ht->bits++;
-	ht->max *= 2;
-	ht->max_with_deleted *= 2;
+	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) {
@@ -182,14 +187,16 @@ static COLD bool double_table(struct htable *ht)
 		}
 	}
 
-	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));
+	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;
-	free(oldtable);
 	return true;
 }
 
@@ -224,8 +231,17 @@ static COLD void update_common(struct htable *ht, const void *p)
 	uintptr_t maskdiff, bitsdiff;
 
 	if (ht->elems == 0) {
-		ht->common_mask = -1;
-		ht->common_bits = (uintptr_t)p;
+		/* 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;
 	}