summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/ccan/htable/_info10
-rw-r--r--lib/ccan/htable/htable.c50
-rw-r--r--lib/ccan/htable/htable.h30
-rw-r--r--lib/ccan/htable/htable_type.h148
-rw-r--r--lib/ccan/htable/test/run-size.c12
-rw-r--r--lib/ccan/htable/test/run-type.c56
-rw-r--r--lib/ccan/htable/test/run.c82
-rw-r--r--lib/ccan/htable/tools/speed.c66
-rw-r--r--lib/ccan/htable/tools/stringspeed.c51
9 files changed, 251 insertions, 254 deletions
diff --git a/lib/ccan/htable/_info b/lib/ccan/htable/_info
index ed9a8a5dac..1553da2b0e 100644
--- a/lib/ccan/htable/_info
+++ b/lib/ccan/htable/_info
@@ -62,7 +62,7 @@
*
* int main(int argc, char *argv[])
* {
- * struct htable *ht;
+ * struct htable ht;
* unsigned int i;
* unsigned long val;
*
@@ -71,14 +71,14 @@
* 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]);
diff --git a/lib/ccan/htable/htable.c b/lib/ccan/htable/htable.c
index ba5f0de530..f3e529211d 100644
--- a/lib/ccan/htable/htable.c
+++ b/lib/ccan/htable/htable.c
@@ -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)
diff --git a/lib/ccan/htable/htable.h b/lib/ccan/htable/htable.h
index 73f4da847a..b3962ac050 100644
--- a/lib/ccan/htable/htable.h
+++ b/lib/ccan/htable/htable.h
@@ -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
diff --git a/lib/ccan/htable/htable_type.h b/lib/ccan/htable/htable_type.h
index af9da1b226..3b555cde4a 100644
--- a/lib/ccan/htable/htable_type.h
+++ b/lib/ccan/htable/htable_type.h
@@ -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))
diff --git a/lib/ccan/htable/test/run-size.c b/lib/ccan/htable/test/run-size.c
index 01e4bb41ac..c92401c3c6 100644
--- a/lib/ccan/htable/test/run-size.c
+++ b/lib/ccan/htable/test/run-size.c
@@ -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();
}
diff --git a/lib/ccan/htable/test/run-type.c b/lib/ccan/htable/test/run-type.c
index aca9c59488..f97e7270b2 100644
--- a/lib/ccan/htable/test/run-type.c
+++ b/lib/ccan/htable/test/run-type.c
@@ -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();
}
diff --git a/lib/ccan/htable/test/run.c b/lib/ccan/htable/test/run.c
index 5e9d23ee30..1a9e2de4cb 100644
--- a/lib/ccan/htable/test/run.c
+++ b/lib/ccan/htable/test/run.c
@@ -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();
}
diff --git a/lib/ccan/htable/tools/speed.c b/lib/ccan/htable/tools/speed.c
index 194f11201f..0b4e43448e 100644
--- a/lib/ccan/htable/tools/speed.c
+++ b/lib/ccan/htable/tools/speed.c
@@ -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;
}
diff --git a/lib/ccan/htable/tools/stringspeed.c b/lib/ccan/htable/tools/stringspeed.c
index 00ad2790cd..2bc1524ea0 100644
--- a/lib/ccan/htable/tools/stringspeed.c
+++ b/lib/ccan/htable/tools/stringspeed.c
@@ -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));
generated by cgit (git 2.34.1) at 2024-11-05 17:39:24 +0000