htable: clean up interface, document htable_type better.
authorRusty Russell <rusty@rustcorp.com.au>
Tue, 27 Sep 2011 05:07:01 +0000 (14:37 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 27 Sep 2011 05:07:01 +0000 (14:37 +0930)
We change from htable_new()/htable_free() to htable_init/htable_clear.
We also change HTABLE_DEFINE_TYPE() to be the full name, without automatically
prepending htable_.

ccan/htable/_info
ccan/htable/htable.c
ccan/htable/htable.h
ccan/htable/htable_type.h
ccan/htable/test/run-size.c
ccan/htable/test/run-type.c
ccan/htable/test/run.c
ccan/htable/tools/speed.c
ccan/htable/tools/stringspeed.c
tools/ccanlint/file_analysis.c
tools/ccanlint/tests/reduce_features.c

index ed9a8a5dac60ef9657bb84839feeba25323f1ae3..1553da2b0e85e7df8378da6e6e4cf2f9b8464dd8 100644 (file)
@@ -62,7 +62,7 @@
  *
  *     int main(int argc, char *argv[])
  *     {
- *             struct htable *ht;
+ *             struct htable ht;
  *             unsigned int i;
  *             unsigned long val;
  *
  *                          argv[0]);
  *
  *             // Create and populate hash table.
- *             ht = htable_new(rehash, NULL);
+ *             htable_init(&ht, rehash, NULL);
  *             for (i = 0; i < sizeof(map)/sizeof(map[0]); i++)
- *                     htable_add(ht, hash_string(map[i].name), &map[i]);
+ *                     htable_add(&ht, hash_string(map[i].name), &map[i]);
  *
  *             // Add any aliases to the hash table.
  *             for (i = 1; i < argc; i++) {
  *                     if (!strncmp(argv[i], "--alias=", strlen("--alias=")))
- *                             add_alias(ht, argv[i] + strlen("--alias="));
+ *                             add_alias(&ht, argv[i] + strlen("--alias="));
  *                     else
  *                             break;
  *             }
@@ -86,7 +86,7 @@
  *             // Find the other args in the hash table.
  *             for (val = 0; i < argc; i++) {
  *                     struct name_to_digit *n;
- *                     n = htable_get(ht, hash_string(argv[i]),
+ *                     n = htable_get(&ht, hash_string(argv[i]),
  *                                    streq, argv[i]);
  *                     if (!n)
  *                             errx(1, "Invalid digit name %s", argv[i]);
index ba5f0de530a1a68d7acd5649cfeca6a67e64142b..f3e529211d5b2456bad5165d3baa848de4314d3d 100644 (file)
@@ -1,7 +1,6 @@
 /* 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>
@@ -10,17 +9,6 @@
 /* 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)
@@ -54,33 +42,29 @@ 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 = 0;
-               ht->rehash = rehash;
-               ht->priv = priv;
-               ht->elems = 0;
-               ht->deleted = 0;
-               ht->max = 0;
-               ht->max_with_deleted = 0;
-               /* This guarantees we enter update_common first add. */
-               ht->common_mask = -1;
-               ht->common_bits = 0;
-               ht->perfect_bit = 0;
-               /* Dummy table until first insert. */
-               ht->table = &ht->perfect_bit;
-       }
-       return ht;
+       ht->bits = 0;
+       ht->rehash = rehash;
+       ht->priv = priv;
+       ht->elems = 0;
+       ht->deleted = 0;
+       ht->max = 0;
+       ht->max_with_deleted = 0;
+       /* This guarantees we enter update_common first add. */
+       ht->common_mask = -1;
+       ht->common_bits = 0;
+       ht->perfect_bit = 0;
+       /* Dummy table until first insert. */
+       ht->table = &ht->perfect_bit;
 }
 
-void htable_free(const struct htable *ht)
+void htable_clear(struct htable *ht)
 {
        if (ht->table != &ht->perfect_bit)
                free((void *)ht->table);
-       free((void *)ht);
+       htable_init(ht, ht->rehash, ht->priv);
 }
 
 static size_t hash_bucket(const struct htable *ht, size_t h)
index 73f4da847a0864cd8912d5e8a624f7d4bb8a5a50..b3962ac050251747706c3de25259b781e3b026ca 100644 (file)
@@ -2,25 +2,43 @@
 #ifndef CCAN_HTABLE_H
 #define CCAN_HTABLE_H
 #include "config.h"
+#include <stdint.h>
 #include <stdbool.h>
 #include <stdlib.h>
 
-struct htable;
+/**
+ * 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_new - allocate a hash tree.
+ * htable_init - initialize an empty hash tree.
+ * @ht: the hash table to initialize
  * @rehash: hash function to use for rehashing.
  * @priv: private argument to @rehash function.
  */
-struct htable *htable_new(size_t (*hash)(const void *elem, void *priv),
-                         void *priv);
+void htable_init(struct htable *ht,
+                size_t (*rehash)(const void *elem, void *priv), void *priv);
 
 /**
- * htable_free - dellocate a hash tree.
+ * htable_clear - empty a hash tree.
+ * @ht: the hash table to clear
  *
  * This doesn't do anything to any pointers left in it.
  */
-void htable_free(const struct htable *);
+void htable_clear(struct htable *ht);
 
 /**
  * htable_rehash - use a hashtree's rehash function
index af9da1b22692baa0331241a0bde56a84899a6165..3b555cde4aaadd183d6e196ac50986d11fdc58d7 100644 (file)
@@ -7,88 +7,90 @@
 /**
  * HTABLE_DEFINE_TYPE - create a set of htable ops for a type
  * @type: a type whose pointers will be values in the hash.
- * @keyof: a function/macro to extract a key from a @type element.
- * @hashfn: a hash function for a @key
- * @cmpfn: a comparison function for two keyof()s.
- * @name: a name for all the functions to define (of form htable_<name>_*)
+ * @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem)
+ * @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *)
+ * @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *)
+ * @prefix: a prefix for all the functions to define (of form <name>_*)
  *
  * NULL values may not be placed into the hash table.
  *
- * The following wrapper functions are defined; each one is a
- * simplified version of the htable.h equivalent:
+ * This defines the type hashtable type and an iterator type:
+ *     struct <name>;
+ *     struct <name>_iter;
  *
- *     // Creating and freeing.
- *     struct htable_@name *htable_@name_new(void);
- *     void htable_@name_free(const struct htable_@name *ht);
+ * It also defines initialization and freeing functions:
+ *     void <name>_init(struct <name> *);
+ *     void <name>_clear(struct <name> *);
  *
- *     // Add, delete and find.
- *     bool htable_@name_add(struct htable_@name *ht, const type *e);
- *     bool htable_@name_del(struct htable_@name *ht, const type *e);
- *     bool htable_@name_delkey(struct htable_@name *ht, const ktype *k);
- *     type *htable_@name_get(const struct htable_@name *ht, const ktype *k);
+ * Add function only fails if we run out of memory:
+ *     bool <name>_add(struct <name> *ht, const <type> *e);
  *
- *     // Iteration.
- *     struct htable_@name_iter;
- *     type *htable_@name_first(const struct htable_@name *ht,
- *                              struct htable_@name_iter *i);
- *     type *htable_@name_next(const struct htable_@name *ht,
- *                             struct htable_@name_iter *i);
+ * Delete and delete-by key return true if it was in the set:
+ *     bool <name>_del(struct <name> *ht, const <type> *e);
+ *     bool <name>_delkey(struct <name> *ht, const <keytype> *k);
+ *
+ * Find function return the matching element, or NULL:
+ *     type *<name>_get(const struct @name *ht, const <keytype> *k);
+ *
+ * Iteration over hashtable is also supported:
+ *     type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
+ *     type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
+ *
+ * It's currently safe to iterate over a changing hashtable, but you might
+ * miss an element.  Iteration isn't very efficient, either.
  */
-#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, cmpfn, name)           \
-struct htable_##name;                                                  \
-struct htable_##name##_iter { struct htable_iter i; };                 \
-static inline size_t htable_##name##_hash(const void *elem, void *priv)        \
-{                                                                      \
-       return hashfn(keyof((const type *)elem));                       \
-}                                                                      \
-static inline struct htable_##name *htable_##name##_new(void)          \
-{                                                                      \
-       return (struct htable_##name *)htable_new(htable_##name##_hash, \
-                                                 NULL);                \
-}                                                                      \
-static inline void htable_##name##_free(const struct htable_##name *ht)        \
-{                                                                      \
-       htable_free((const struct htable *)ht);                         \
-}                                                                      \
-static inline bool htable_##name##_add(struct htable_##name *ht,       \
-                                      const type *elem)                \
-{                                                                      \
-       return htable_add((struct htable *)ht, hashfn(keyof(elem)), elem); \
-}                                                                      \
-static inline bool htable_##name##_del(const struct htable_##name *ht, \
-                                      const type *elem)                \
-{                                                                      \
-       return htable_del((struct htable *)ht, hashfn(keyof(elem)), elem); \
-}                                                                      \
-static inline type *htable_##name##_get(const struct htable_##name *ht,        \
-                                       const HTABLE_KTYPE(keyof) k)    \
-{                                                                      \
-       /* Typecheck for cmpfn */                                       \
-       (void)sizeof(cmpfn((const type *)NULL,                          \
-                          keyof((const type *)NULL)));                 \
-       return (type *)htable_get((const struct htable *)ht,            \
+#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name)            \
+       struct name { struct htable raw; };                             \
+       struct name##_iter { struct htable_iter i; };                   \
+       static inline size_t name##_hash(const void *elem, void *priv)  \
+       {                                                               \
+               return hashfn(keyof((const type *)elem));               \
+       }                                                               \
+       static inline void name##_init(struct name *ht)                 \
+       {                                                               \
+               htable_init(&ht->raw, name##_hash, NULL);               \
+       }                                                               \
+       static inline void name##_clear(struct name *ht)                \
+       {                                                               \
+               htable_clear(&ht->raw);                                 \
+       }                                                               \
+       static inline bool name##_add(struct name *ht, const type *elem) \
+       {                                                               \
+               return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \
+       }                                                               \
+       static inline bool name##_del(struct name *ht, const type *elem) \
+       {                                                               \
+               return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \
+       }                                                               \
+       static inline type *name##_get(const struct name *ht,           \
+                                      const HTABLE_KTYPE(keyof) k)     \
+       {                                                               \
+               /* Typecheck for eqfn */                                \
+               (void)sizeof(eqfn((const type *)NULL,                   \
+                                 keyof((const type *)NULL)));          \
+               return htable_get(&ht->raw,                             \
                                  hashfn(k),                            \
-                                 (bool (*)(const void *, void *))(cmpfn), \
+                                 (bool (*)(const void *, void *))(eqfn), \
                                  k);                                   \
-}                                                                      \
-static inline bool htable_##name##_delkey(struct htable_##name *ht,    \
-                                         const HTABLE_KTYPE(keyof) k) \
-{                                                                      \
-       type *elem = htable_##name##_get(ht, k);                        \
-       if (elem)                                                       \
-               return htable_##name##_del(ht, elem);                   \
-       return false;                                                   \
-}                                                                      \
-static inline type *htable_##name##_first(const struct htable_##name *ht, \
-                                         struct htable_##name##_iter *iter) \
-{                                                                      \
-       return htable_first((const struct htable *)ht, &iter->i);       \
-}                                                                      \
-static inline type *htable_##name##_next(const struct htable_##name *ht, \
-                                        struct htable_##name##_iter *iter) \
-{                                                                      \
-       return htable_next((const struct htable *)ht, &iter->i);        \
-}
+       }                                                               \
+       static inline bool name##_delkey(struct name *ht,               \
+                                        const HTABLE_KTYPE(keyof) k)   \
+       {                                                               \
+               type *elem = name##_get(ht, k);                         \
+               if (elem)                                               \
+                       return name##_del(ht, elem);                    \
+               return false;                                           \
+       }                                                               \
+       static inline type *name##_first(const struct name *ht,         \
+                                        struct name##_iter *iter)      \
+       {                                                               \
+               return htable_first(&ht->raw, &iter->i);                \
+       }                                                               \
+       static inline type *name##_next(const struct name *ht,          \
+                                       struct name##_iter *iter)       \
+       {                                                               \
+               return htable_next(&ht->raw, &iter->i);                 \
+       }
 
 #if HAVE_TYPEOF
 #define HTABLE_KTYPE(keyof) typeof(keyof(NULL))
index 01e4bb41acf7ad526dde9e5d3f1fa726ddc84f70..c92401c3c67d0d1d525c33f33f58d055512ee35f 100644 (file)
@@ -16,7 +16,7 @@ static size_t hash(const void *elem, void *unused)
 
 int main(int argc, char *argv[])
 {
-       struct htable *ht;
+       struct htable ht;
        uint64_t val[NUM_VALS];
        unsigned int i;
 
@@ -24,13 +24,13 @@ int main(int argc, char *argv[])
        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
 
-       ht = htable_new(hash, NULL);
+       htable_init(&ht, hash, NULL);
        for (i = 0; i < NUM_VALS; i++) {
-               ok1(ht->max >= i);
-               ok1(ht->max <= i * 2);
-               htable_add(ht, hash(&val[i], NULL), &val[i]);
+               ok1(ht.max >= i);
+               ok1(ht.max <= i * 2);
+               htable_add(&ht, hash(&val[i], NULL), &val[i]);
        }
-       htable_free(ht);
+       htable_clear(&ht);
 
        return exit_status();
 }
index aca9c59488240f7e3b9e0090ac15256120c7a59f..f97e7270b2fa65afd83e75cc9fcf33220d06d357 100644 (file)
@@ -33,7 +33,7 @@ static bool cmp(const struct obj *obj, const unsigned int *key)
        return obj->key == *key;
 }
 
-HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, obj);
+HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
 
 static void add_vals(struct htable_obj *ht,
                     struct obj val[], unsigned int num)
@@ -110,7 +110,7 @@ static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
 int main(int argc, char *argv[])
 {
        unsigned int i;
-       struct htable_obj *ht;
+       struct htable_obj ht;
        struct obj val[NUM_VALS];
        unsigned int dne;
        void *p;
@@ -121,57 +121,55 @@ int main(int argc, char *argv[])
                val[i].key = i;
        dne = i;
 
-       ht = htable_obj_new();
-       ok1(((struct htable *)ht)->max == 0);
-       ok1(((struct htable *)ht)->bits == 0);
+       htable_obj_init(&ht);
+       ok1(ht.raw.max == 0);
+       ok1(ht.raw.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
-       ok1(!htable_obj_get(ht, &dne));
+       ok1(!htable_obj_get(&ht, &dne));
 
        /* Fill it, it should increase in size. */
-       add_vals(ht, val, NUM_VALS);
-       ok1(((struct htable *)ht)->bits == NUM_BITS + 1);
-       ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
+       add_vals(&ht, val, NUM_VALS);
+       ok1(ht.raw.bits == NUM_BITS + 1);
+       ok1(ht.raw.max < (1 << ht.raw.bits));
 
        /* Mask should be set. */
-       ok1(((struct htable *)ht)->common_mask != 0);
-       ok1(((struct htable *)ht)->common_mask != -1);
-       ok1(check_mask((struct htable *)ht, val, NUM_VALS));
+       ok1(ht.raw.common_mask != 0);
+       ok1(ht.raw.common_mask != -1);
+       ok1(check_mask(&ht.raw, val, NUM_VALS));
 
        /* Find all. */
-       find_vals(ht, val, NUM_VALS);
-       ok1(!htable_obj_get(ht, &dne));
+       find_vals(&ht, val, NUM_VALS);
+       ok1(!htable_obj_get(&ht, &dne));
 
        /* Walk once, should get them all. */
        i = 0;
-       for (p = htable_obj_first(ht,&iter); p; p = htable_obj_next(ht, &iter))
+       for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
                i++;
        ok1(i == NUM_VALS);
 
        /* Delete all. */
-       del_vals(ht, val, NUM_VALS);
-       ok1(!htable_obj_get(ht, &val[0].key));
+       del_vals(&ht, val, NUM_VALS);
+       ok1(!htable_obj_get(&ht, &val[0].key));
 
        /* Worst case, a "pointer" which doesn't have any matching bits. */
-       htable_add((struct htable *)ht, 0,
-                  (void *)~(uintptr_t)&val[NUM_VALS-1]);
-       htable_obj_add(ht, &val[NUM_VALS-1]);
-       ok1(((struct htable *)ht)->common_mask == 0);
-       ok1(((struct htable *)ht)->common_bits == 0);
+       htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+       htable_obj_add(&ht, &val[NUM_VALS-1]);
+       ok1(ht.raw.common_mask == 0);
+       ok1(ht.raw.common_bits == 0);
        /* Delete the bogus one before we trip over it. */
-       htable_del((struct htable *)ht, 0,
-                  (void *)~(uintptr_t)&val[NUM_VALS-1]);
+       htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 
        /* Add the rest. */
-       add_vals(ht, val, NUM_VALS-1);
+       add_vals(&ht, val, NUM_VALS-1);
 
        /* Check we can find them all. */
-       find_vals(ht, val, NUM_VALS);
-       ok1(!htable_obj_get(ht, &dne));
+       find_vals(&ht, val, NUM_VALS);
+       ok1(!htable_obj_get(&ht, &dne));
 
        /* Delete them all by key. */
-       del_vals_bykey(ht, val, NUM_VALS);
-       htable_obj_free(ht);
+       del_vals_bykey(&ht, val, NUM_VALS);
+       htable_obj_clear(&ht);
 
        return exit_status();
 }
index 5e9d23ee30e07b55f7c6249ec798360653bc56ac..1a9e2de4cb6e7f98fe5e75485e06b37c73de26d5 100644 (file)
@@ -99,7 +99,7 @@ int main(int argc, char *argv[])
 {
        unsigned int i;
        uintptr_t perfect_bit;
-       struct htable *ht;
+       struct htable ht;
        uint64_t val[NUM_VALS];
        uint64_t dne;
        void *p;
@@ -110,81 +110,79 @@ int main(int argc, char *argv[])
                val[i] = i;
        dne = i;
 
-       ht = htable_new(hash, NULL);
-       ok1(ht->max == 0);
-       ok1(ht->bits == 0);
+       htable_init(&ht, hash, NULL);
+       ok1(ht.max == 0);
+       ok1(ht.bits == 0);
 
        /* We cannot find an entry which doesn't exist. */
-       ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
+       ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
 
        /* This should increase it once. */
-       add_vals(ht, val, 0, 1);
-       ok1(ht->bits == 1);
-       ok1(ht->max == 1);
-       ok1(ht->common_mask == -1);
+       add_vals(&ht, val, 0, 1);
+       ok1(ht.bits == 1);
+       ok1(ht.max == 1);
+       ok1(ht.common_mask == -1);
 
        /* Mask should be set. */
-       ok1(check_mask(ht, val, 1));
+       ok1(check_mask(&ht, val, 1));
 
        /* This should increase it again. */
-       add_vals(ht, val, 1, 1);
-       ok1(ht->bits == 2);
-       ok1(ht->max == 3);
+       add_vals(&ht, val, 1, 1);
+       ok1(ht.bits == 2);
+       ok1(ht.max == 3);
 
        /* Mask should be set. */
-       ok1(ht->common_mask != 0);
-       ok1(ht->common_mask != -1);
-       ok1(check_mask(ht, val, 2));
+       ok1(ht.common_mask != 0);
+       ok1(ht.common_mask != -1);
+       ok1(check_mask(&ht, val, 2));
 
        /* Now do the rest. */
-       add_vals(ht, val, 2, NUM_VALS - 2);
+       add_vals(&ht, val, 2, NUM_VALS - 2);
 
        /* Find all. */
-       find_vals(ht, val, NUM_VALS);
-       ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
+       find_vals(&ht, val, NUM_VALS);
+       ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
 
        /* Walk once, should get them all. */
        i = 0;
-       for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
+       for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
                i++;
        ok1(i == NUM_VALS);
 
        /* Delete all. */
-       del_vals(ht, val, NUM_VALS);
-       ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
+       del_vals(&ht, val, NUM_VALS);
+       ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
 
        /* Worst case, a "pointer" which doesn't have any matching bits. */
-       htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
-       htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
-       ok1(ht->common_mask == 0);
-       ok1(ht->common_bits == 0);
+       htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+       htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
+       ok1(ht.common_mask == 0);
+       ok1(ht.common_bits == 0);
        /* Get rid of bogus pointer before we trip over it! */
-       htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
+       htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 
        /* Add the rest. */
-       add_vals(ht, val, 0, NUM_VALS-1);
+       add_vals(&ht, val, 0, NUM_VALS-1);
 
        /* Check we can find them all. */
-       find_vals(ht, val, NUM_VALS);
-       ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
-
-       htable_free(ht);
+       find_vals(&ht, val, NUM_VALS);
+       ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
 
        /* Corner cases: wipe out the perfect bit using bogus pointer. */
-       ht = htable_new(hash, NULL);
-       htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
-       ok1(ht->perfect_bit);
-       perfect_bit = ht->perfect_bit;
-       htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
+       htable_clear(&ht);
+       htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
+       ok1(ht.perfect_bit);
+       perfect_bit = ht.perfect_bit;
+       htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
                                   | perfect_bit));
-       ok1(ht->perfect_bit == 0);
-       htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
+       ok1(ht.perfect_bit == 0);
+       htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
 
        /* Enlarging should restore it... */
-       add_vals(ht, val, 0, NUM_VALS-1);
+       add_vals(&ht, val, 0, NUM_VALS-1);
 
-       ok1(ht->perfect_bit != 0);
-       htable_free(ht);
+       ok1(ht.perfect_bit != 0);
+       htable_clear(&ht);
 
        return exit_status();
 }
index 194f11201f01c9d08aa5647f4a8436c1175a03de..0b4e43448e6a9b530d1d768a149d5c43000ea629 100644 (file)
@@ -34,7 +34,7 @@ static bool cmp(const struct object *object, const unsigned int *key)
        return object->key == *key;
 }
 
-HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj);
+HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj);
 
 static unsigned int popcount(unsigned long val)
 {
@@ -136,8 +136,7 @@ int main(int argc, char *argv[])
        struct object *objs;
        size_t i, j, num, deleted;
        struct timeval start, stop;
-       struct htable_obj *ht;
-       struct htable *htr;
+       struct htable_obj ht;
        bool make_dumb = false;
 
        if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
@@ -152,32 +151,31 @@ int main(int argc, char *argv[])
                objs[i].self = &objs[i];
        }
 
-       ht = htable_obj_new();
-       htr = (void *)ht;
+       htable_obj_init(&ht);
 
        printf("Initial insert: ");
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++)
-               htable_obj_add(ht, objs[i].self);
+               htable_obj_add(&ht, objs[i].self);
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
        printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
-              1U << htr->bits, popcount(htr->common_mask),
-              perfect(htr) * 100.0 / htr->elems);
+              1U << ht.raw.bits, popcount(ht.raw.common_mask),
+              perfect(&ht.raw) * 100.0 / ht.raw.elems);
 
        if (make_dumb) {
                /* Screw with mask, to hobble us. */
-               update_common(htr, (void *)~htr->common_bits);
+               update_common(&ht.raw, (void *)~ht.raw.common_bits);
                printf("Details: DUMB MODE: mask bits %u\n",
-                      popcount(htr->common_mask));
+                      popcount(ht.raw.common_mask));
        }
 
        printf("Initial lookup (match): ");
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++)
-               if (htable_obj_get(ht, &i)->self != objs[i].self)
+               if (htable_obj_get(&ht, &i)->self != objs[i].self)
                        abort();
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -187,7 +185,7 @@ int main(int argc, char *argv[])
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++) {
                unsigned int n = i + num;
-               if (htable_obj_get(ht, &n))
+               if (htable_obj_get(&ht, &n))
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -198,7 +196,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
-               if (htable_obj_get(ht, &j)->self != &objs[j])
+               if (htable_obj_get(&ht, &j)->self != &objs[j])
                        abort();
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -208,7 +206,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++)
-               if (!htable_obj_del(ht, objs[i].self))
+               if (!htable_obj_del(&ht, objs[i].self))
                        abort();
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -218,7 +216,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++)
-               htable_obj_add(ht, objs[i].self);
+               htable_obj_add(&ht, objs[i].self);
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
@@ -227,13 +225,13 @@ int main(int argc, char *argv[])
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i+=2)
-               if (!htable_obj_del(ht, objs[i].self))
+               if (!htable_obj_del(&ht, objs[i].self))
                        abort();
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
        printf("Details: rehashes %zu, delete markers %zu\n",
-              hashcount, count_deleted(htr));
+              hashcount, count_deleted(&ht.raw));
 
        printf("Adding (a different) half: ");
        fflush(stdout);
@@ -243,22 +241,22 @@ int main(int argc, char *argv[])
 
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i+=2)
-               htable_obj_add(ht, objs[i].self);
+               htable_obj_add(&ht, objs[i].self);
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
        printf("Details: delete markers %zu, perfect %.0f%%\n",
-              count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
+              count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
 
        printf("Lookup after half-change (match): ");
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 1; i < num; i+=2)
-               if (htable_obj_get(ht, &i)->self != objs[i].self)
+               if (htable_obj_get(&ht, &i)->self != objs[i].self)
                        abort();
        for (i = 0; i < num; i+=2) {
                unsigned int n = i + num;
-               if (htable_obj_get(ht, &n)->self != objs[i].self)
+               if (htable_obj_get(&ht, &n)->self != objs[i].self)
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -269,7 +267,7 @@ int main(int argc, char *argv[])
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++) {
                unsigned int n = i + num * 2;
-               if (htable_obj_get(ht, &n))
+               if (htable_obj_get(&ht, &n))
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -291,10 +289,10 @@ int main(int argc, char *argv[])
                }
                gettimeofday(&start, NULL);
                for (j = 0; j < num; j++) {
-                       if (!htable_obj_del(ht, &objs[j]))
+                       if (!htable_obj_del(&ht, &objs[j]))
                                abort();
                        objs[j].key = num*i+j;
-                       if (!htable_obj_add(ht, &objs[j]))
+                       if (!htable_obj_add(&ht, &objs[j]))
                                abort();
                }
                gettimeofday(&stop, NULL);
@@ -305,15 +303,15 @@ int main(int argc, char *argv[])
        /* Spread out the keys more to try to make it harder. */
        printf("Details: reinserting with spread\n");
        for (i = 0; i < num; i++) {
-               if (!htable_obj_del(ht, objs[i].self))
+               if (!htable_obj_del(&ht, objs[i].self))
                        abort();
                objs[i].key = num * 5 + i * 9;
-               if (!htable_obj_add(ht, objs[i].self))
+               if (!htable_obj_add(&ht, objs[i].self))
                        abort();
        }
        printf("Details: delete markers %zu, perfect %.0f%%\n",
-              count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
-       i = worst_run(htr, &deleted);
+              count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
+       i = worst_run(&ht.raw, &deleted);
        printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
 
        printf("Lookup after churn & spread (match): ");
@@ -321,7 +319,7 @@ int main(int argc, char *argv[])
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++) {
                unsigned int n = num * 5 + i * 9;
-               if (htable_obj_get(ht, &n)->self != objs[i].self)
+               if (htable_obj_get(&ht, &n)->self != objs[i].self)
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -332,7 +330,7 @@ int main(int argc, char *argv[])
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i++) {
                unsigned int n = num * (5 + 9) + i * 9;
-               if (htable_obj_get(ht, &n))
+               if (htable_obj_get(&ht, &n))
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -343,7 +341,7 @@ int main(int argc, char *argv[])
        gettimeofday(&start, NULL);
        for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
                unsigned int n = num * 5 + j * 9;
-               if (htable_obj_get(ht, &n)->self != &objs[j])
+               if (htable_obj_get(&ht, &n)->self != &objs[j])
                        abort();
        }
        gettimeofday(&stop, NULL);
@@ -354,7 +352,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i+=2)
-               if (!htable_obj_del(ht, objs[i].self))
+               if (!htable_obj_del(&ht, objs[i].self))
                        abort();
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -367,12 +365,12 @@ int main(int argc, char *argv[])
 
        gettimeofday(&start, NULL);
        for (i = 0; i < num; i+=2)
-               htable_obj_add(ht, objs[i].self);
+               htable_obj_add(&ht, objs[i].self);
        gettimeofday(&stop, NULL);
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
        printf("Details: delete markers %zu, perfect %.0f%%\n",
-              count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
+              count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
 
        return 0;
 }
index 00ad2790cd4cc13e7c58d9ea86f4152d47f7d89d..2bc1524ea09d040b8786b14f0c37ea8f64079eec 100644 (file)
@@ -31,7 +31,7 @@ static bool cmp(const char *obj, const char *key)
        return strcmp(obj, key) == 0;
 }
 
-HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, str);
+HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str);
 
 /* Nanoseconds per operation */
 static size_t normalize(const struct timeval *start,
@@ -51,13 +51,13 @@ int main(int argc, char *argv[])
 {
        size_t i, j, num;
        struct timeval start, stop;
-       struct htable_str *ht;
+       struct htable_str ht;
        char **words, **misswords;
 
        words = strsplit(NULL, grab_file(NULL,
                                         argv[1] ? argv[1] : "/usr/share/dict/words",
                                         NULL), "\n");
-       ht = htable_str_new();
+       htable_str_init(&ht);
        num = talloc_array_length(words) - 1;
        printf("%zu words\n", num);
 
@@ -77,19 +77,18 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++)
-               htable_str_add(ht, words[i]);
+               htable_str_add(&ht, words[i]);
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
        printf("Bytes allocated: %zu\n",
-              sizeof(((struct htable *)ht)->table[0])
-              << ((struct htable *)ht)->bits);
+              sizeof(ht.raw.table[0]) << ht.raw.bits);
 
        printf("#02: Initial lookup (match): ");
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++)
-               if (htable_str_get(ht, words[i]) != words[i])
+               if (htable_str_get(&ht, words[i]) != words[i])
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -98,7 +97,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++) {
-               if (htable_str_get(ht, misswords[i]))
+               if (htable_str_get(&ht, misswords[i]))
                        abort();
        }
        stop = time_now();
@@ -109,7 +108,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
-               if (htable_str_get(ht, words[j]) != words[j])
+               if (htable_str_get(&ht, words[j]) != words[j])
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -119,7 +118,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++)
-               if (!htable_str_del(ht, words[i]))
+               if (!htable_str_del(&ht, words[i]))
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -128,7 +127,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++)
-               htable_str_add(ht, words[i]);
+               htable_str_add(&ht, words[i]);
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
@@ -137,7 +136,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i+=2)
-               if (!htable_str_del(ht, words[i]))
+               if (!htable_str_del(&ht, words[i]))
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -147,7 +146,7 @@ int main(int argc, char *argv[])
 
        start = time_now();
        for (i = 0; i < num; i+=2)
-               htable_str_add(ht, misswords[i]);
+               htable_str_add(&ht, misswords[i]);
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
 
@@ -155,10 +154,10 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 1; i < num; i+=2)
-               if (htable_str_get(ht, words[i]) != words[i])
+               if (htable_str_get(&ht, words[i]) != words[i])
                        abort();
        for (i = 0; i < num; i+=2) {
-               if (htable_str_get(ht, misswords[i]) != misswords[i])
+               if (htable_str_get(&ht, misswords[i]) != misswords[i])
                        abort();
        }
        stop = time_now();
@@ -168,10 +167,10 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i+=2)
-               if (htable_str_get(ht, words[i]))
+               if (htable_str_get(&ht, words[i]))
                        abort();
        for (i = 1; i < num; i+=2) {
-               if (htable_str_get(ht, misswords[i]))
+               if (htable_str_get(&ht, misswords[i]))
                        abort();
        }
        stop = time_now();
@@ -182,9 +181,9 @@ int main(int argc, char *argv[])
        printf("#11: Churn 1: ");
        start = time_now();
        for (j = 0; j < num; j+=2) {
-               if (!htable_str_del(ht, misswords[j]))
+               if (!htable_str_del(&ht, misswords[j]))
                        abort();
-               if (!htable_str_add(ht, words[j]))
+               if (!htable_str_add(&ht, words[j]))
                        abort();
        }
        stop = time_now();
@@ -193,9 +192,9 @@ int main(int argc, char *argv[])
        printf("#12: Churn 2: ");
        start = time_now();
        for (j = 1; j < num; j+=2) {
-               if (!htable_str_del(ht, words[j]))
+               if (!htable_str_del(&ht, words[j]))
                        abort();
-               if (!htable_str_add(ht, misswords[j]))
+               if (!htable_str_add(&ht, misswords[j]))
                        abort();
        }
        stop = time_now();
@@ -204,9 +203,9 @@ int main(int argc, char *argv[])
        printf("#13: Churn 3: ");
        start = time_now();
        for (j = 1; j < num; j+=2) {
-               if (!htable_str_del(ht, misswords[j]))
+               if (!htable_str_del(&ht, misswords[j]))
                        abort();
-               if (!htable_str_add(ht, words[j]))
+               if (!htable_str_add(&ht, words[j]))
                        abort();
        }
        stop = time_now();
@@ -217,7 +216,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++)
-               if (htable_str_get(ht, words[i]) != words[i])
+               if (htable_str_get(&ht, words[i]) != words[i])
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
@@ -226,7 +225,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0; i < num; i++) {
-               if (htable_str_get(ht, misswords[i]))
+               if (htable_str_get(&ht, misswords[i]))
                        abort();
        }
        stop = time_now();
@@ -237,7 +236,7 @@ int main(int argc, char *argv[])
        fflush(stdout);
        start = time_now();
        for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
-               if (htable_str_get(ht, words[j]) != words[j])
+               if (htable_str_get(&ht, words[j]) != words[j])
                        abort();
        stop = time_now();
        printf(" %zu ns\n", normalize(&start, &stop, num));
index a4282a96c75b06a68d7a895346c3650747a7a8aa..63d22b8f129513420101f618f459ed4878a34c54 100644 (file)
@@ -40,7 +40,8 @@ static bool dir_cmp(const struct manifest *m, const char *dir)
        return strcmp(m->dir, dir) == 0;
 }
 
-HTABLE_DEFINE_TYPE(struct manifest, manifest_name, dir_hash, dir_cmp, manifest);
+HTABLE_DEFINE_TYPE(struct manifest, manifest_name, dir_hash, dir_cmp,
+                  htable_manifest);
 static struct htable_manifest *manifests;
 
 const char *get_ccan_file_contents(struct ccan_file *f)
@@ -211,8 +212,10 @@ struct manifest *get_manifest(const void *ctx, const char *dir)
        unsigned int len;
        struct list_head *list;
 
-       if (!manifests)
-               manifests = htable_manifest_new();
+       if (!manifests) {
+               manifests = talloc(NULL, struct htable_manifest);
+               htable_manifest_init(manifests);
+       }
 
        olddir = talloc_getcwd(NULL);
        if (!olddir)
index 39a2bde067a96dbc0072514f5633eebff39974aa..de817d655aa1342da22c2228ba55ac138cd58ba8 100644 (file)
@@ -40,7 +40,20 @@ static bool option_cmp(const char *name1, const char *name2)
        return streq(name1, name2);
 }
 
-HTABLE_DEFINE_TYPE(char, option_name, option_hash, option_cmp, option);
+HTABLE_DEFINE_TYPE(char, option_name, option_hash, option_cmp, htable_option);
+
+static struct htable_option *htable_option_new(void)
+{
+       struct htable_option *opts = malloc(sizeof(*opts));
+       htable_option_init(opts);
+       return opts;
+}
+
+static void htable_option_free(struct htable_option *opts)
+{
+       htable_option_clear(opts);
+       free(opts);
+}
 
 static unsigned int add_options(struct htable_option *opts,
                                struct pp_conditions *cond)