htable: add pre-sized option.

I thought this was slowing down my program; it turned out they were
all hashing to the same value.  But it might be useful.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index b7e65d11966acc96be83dffbb25a273fec153145..59048dc0ada0df95b23583e0dfbba65d3c96768c 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -52,6 +52,29 @@ void htable_init(struct htable *ht,
        ht->table = &ht->perfect_bit;
 }
 
        ht->table = &ht->perfect_bit;
 }
 

+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)
 {
        if (ht->table != &ht->perfect_bit)
 void htable_clear(struct htable *ht)
 {
        if (ht->table != &ht->perfect_bit)

diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h
index ed668e7405ed84e819cec49b85f8186b85287933..03193567d847a5512b31d173bcb8a21a6d54d09e 100644 (file)
--- a/ccan/htable/htable.h
+++ b/ccan/htable/htable.h
@@ -51,6 +51,21 @@ struct htable {
 void htable_init(struct htable *ht,
                 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);
 

+/**
+ * htable_init_sized - initialize an empty hash table of given size.
+ * @ht: the hash table to initialize
+ * @rehash: hash function to use for rehashing.
+ * @priv: private argument to @rehash function.
+ * @size: the number of element.
+ *
+ * If this returns false, @ht is still usable, but may need to do reallocation
+ * upon an add.  If this returns true, it will not need to reallocate within
+ * @size htable_adds.
+ */
+bool htable_init_sized(struct htable *ht,
+                      size_t (*rehash)(const void *elem, void *priv),
+                      void *priv, size_t size);
+

 /**
  * htable_clear - empty a hash table.
  * @ht: the hash table to clear
 /**
  * htable_clear - empty a hash table.
  * @ht: the hash table to clear

diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h
index 03cc46fc5836c8003e2c1e325c13a5ec6df5db47..ad3974c5e446dc74be147371d74dafb09feea631 100644 (file)
--- a/ccan/htable/htable_type.h
+++ b/ccan/htable/htable_type.h
@@ -20,6 +20,7 @@
  *
  * It also defines initialization and freeing functions:
  *     void <name>_init(struct <name> *);
  *
  * It also defines initialization and freeing functions:
  *     void <name>_init(struct <name> *);

+ *     void <name>_init_sized(struct <name> *, size_t);

  *     void <name>_clear(struct <name> *);
  *
  * Add function only fails if we run out of memory:
  *     void <name>_clear(struct <name> *);
  *
  * Add function only fails if we run out of memory:


@@ -53,6 +54,10 @@
        {                                                               \
                htable_init(&ht->raw, name##_hash, NULL);               \
        }                                                               \
        {                                                               \
                htable_init(&ht->raw, name##_hash, NULL);               \
        }                                                               \

+       static inline void name##_init_sized(struct name *ht, size_t s) \
+       {                                                               \
+               htable_init_sized(&ht->raw, name##_hash, NULL, s);      \
+       }                                                               \

        static inline void name##_clear(struct name *ht)                \
        {                                                               \
                htable_clear(&ht->raw);                                 \
        static inline void name##_clear(struct name *ht)                \
        {                                                               \
                htable_clear(&ht->raw);                                 \

diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c
index 7fc05e24f6bfac4b38748491911c6741d0b841a8..c5272c151df43686fbae208004d2a51ed951875c 100644 (file)
--- a/ccan/htable/test/run.c
+++ b/ccan/htable/test/run.c
@@ -105,7 +105,7 @@ int main(int argc, char *argv[])
        void *p;
        struct htable_iter iter;
 
        void *p;
        struct htable_iter iter;
 

-       plan_tests(29);
+       plan_tests(35);

        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;
        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;


@@ -191,5 +191,17 @@ int main(int argc, char *argv[])
        ok1(ht.perfect_bit != 0);
        htable_clear(&ht);
 
        ok1(ht.perfect_bit != 0);
        htable_clear(&ht);
 

+       ok1(htable_init_sized(&ht, hash, NULL, 1024));
+       ok1(ht.max >= 1024);
+       htable_clear(&ht);
+
+       ok1(htable_init_sized(&ht, hash, NULL, 1023));
+       ok1(ht.max >= 1023);
+       htable_clear(&ht);
+
+       ok1(htable_init_sized(&ht, hash, NULL, 1025));
+       ok1(ht.max >= 1025);
+       htable_clear(&ht);
+       

        return exit_status();
 }
        return exit_status();
 }