X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Fhtable.c;h=20b6f5ae2dc964c521aa7f517912cd3d4ab9aa6c;hp=dec53127470a9f6b06a53555286a9fcbb153dbef;hb=4f844a85accfe7f00d19952e34c577766b05319c;hpb=78e983a7a6e5250ebf963d5d93fe34c1d27d5a39

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index dec53127..20b6f5ae 100644
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -1,7 +1,9 @@
+/* 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>
 
@@ -65,8 +67,8 @@ struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
 		ht->priv = priv;
 		ht->elems = 0;
 		ht->deleted = 0;
-		ht->max = (1 << ht->bits) * 2 / 3;
-		ht->max_with_deleted = (1 << ht->bits) * 4 / 5;
+		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;
@@ -154,7 +156,7 @@ static void ht_add(struct htable *ht, const void *new, size_t h)
 	ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
 }
 
-static COLD_ATTRIBUTE bool double_table(struct htable *ht)
+static COLD bool double_table(struct htable *ht)
 {
 	unsigned int i;
 	size_t oldnum = (size_t)1 << ht->bits;
@@ -170,7 +172,16 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht)
 	ht->max *= 2;
 	ht->max_with_deleted *= 2;
 
-	/* FIXME: If we lost our perfect bit, we could reclaim it here! */
+	/* 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;
+			}
+		}
+	}
+
 	for (i = 0; i < oldnum; i++) {
 		if (entry_is_valid(e = oldtable[i])) {
 			void *p = get_raw_ptr(ht, e);
@@ -182,7 +193,7 @@ static COLD_ATTRIBUTE bool double_table(struct htable *ht)
 	return true;
 }
 
-static COLD_ATTRIBUTE void rehash_table(struct htable *ht)
+static COLD void rehash_table(struct htable *ht)
 {
 	size_t start, i;
 	uintptr_t e;
@@ -207,7 +218,7 @@ static COLD_ATTRIBUTE void rehash_table(struct htable *ht)
 }
 
 /* We stole some bits, now we need to put them back... */
-static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
+static COLD void update_common(struct htable *ht, const void *p)
 {
 	unsigned int i;
 	uintptr_t maskdiff, bitsdiff;