From 1b8fbbd843ddeb5fc81c9303db9c590a436d499b Mon Sep 17 00:00:00 2001 From: William Casarin Date: Mon, 9 Jul 2018 12:10:32 -0700 Subject: progress --- ccan/htable/LICENSE | 1 + ccan/htable/_info | 117 +++++++++ ccan/htable/htable.c | 325 +++++++++++++++++++++++ ccan/htable/htable.h | 226 ++++++++++++++++ ccan/htable/htable_type.h | 166 ++++++++++++ ccan/htable/test/run-copy.c | 44 ++++ ccan/htable/test/run-size.c | 36 +++ ccan/htable/test/run-type-int.c | 215 ++++++++++++++++ ccan/htable/test/run-type.c | 210 +++++++++++++++ ccan/htable/test/run-zero-hash-first-entry.c | 61 +++++ ccan/htable/test/run.c | 212 +++++++++++++++ ccan/htable/tools/Makefile | 40 +++ ccan/htable/tools/hsearchspeed.c | 95 +++++++ ccan/htable/tools/speed.c | 370 +++++++++++++++++++++++++++ ccan/htable/tools/stringspeed.c | 240 +++++++++++++++++ 15 files changed, 2358 insertions(+) create mode 120000 ccan/htable/LICENSE create mode 100644 ccan/htable/_info create mode 100644 ccan/htable/htable.c create mode 100644 ccan/htable/htable.h create mode 100644 ccan/htable/htable_type.h create mode 100644 ccan/htable/test/run-copy.c create mode 100644 ccan/htable/test/run-size.c create mode 100644 ccan/htable/test/run-type-int.c create mode 100644 ccan/htable/test/run-type.c create mode 100644 ccan/htable/test/run-zero-hash-first-entry.c create mode 100644 ccan/htable/test/run.c create mode 100644 ccan/htable/tools/Makefile create mode 100644 ccan/htable/tools/hsearchspeed.c create mode 100644 ccan/htable/tools/speed.c create mode 100644 ccan/htable/tools/stringspeed.c (limited to 'ccan/htable') diff --git a/ccan/htable/LICENSE b/ccan/htable/LICENSE new file mode 120000 index 0000000..dc314ec --- /dev/null +++ b/ccan/htable/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/htable/_info b/ccan/htable/_info new file mode 100644 index 0000000..a3bb76d --- /dev/null +++ b/ccan/htable/_info @@ -0,0 +1,117 @@ +#include "config.h" +#include +#include + +/** + * htable - hash table routines + * + * A hash table is an efficient structure for looking up keys. This version + * grows with usage and allows efficient deletion. + * + * Example: + * #include + * #include + * #include + * #include + * #include + * + * struct name_to_digit { + * const char *name; + * unsigned int val; + * }; + * + * static struct name_to_digit map[] = { + * { "zero", 0}, + * { "one", 1 }, + * { "two", 2 }, + * { "three", 3 }, + * { "four", 4 }, + * { "five", 5 }, + * { "six", 6 }, + * { "seven", 7 }, + * { "eight", 8 }, + * { "nine", 9 } + * }; + * + * // Wrapper for rehash function pointer. + * static size_t rehash(const void *e, void *unused) + * { + * (void)unused; + * return hash_string(((struct name_to_digit *)e)->name); + * } + * + * // Comparison function. + * static bool streq(const void *e, void *string) + * { + * return strcmp(((struct name_to_digit *)e)->name, string) == 0; + * } + * + * // We let them add their own aliases, eg. --alias=v=5 + * static void add_alias(struct htable *ht, const char *alias) + * { + * char *eq; + * struct name_to_digit *n; + * + * n = malloc(sizeof(*n)); + * n->name = strdup(alias); + * + * eq = strchr(n->name, '='); + * if (!eq || ((n->val = atoi(eq+1)) == 0 && !strcmp(eq+1, "0"))) + * errx(1, "Usage: --alias=="); + * *eq = '\0'; + * htable_add(ht, hash_string(n->name), n); + * } + * + * int main(int argc, char *argv[]) + * { + * struct htable ht; + * int i; + * unsigned long val; + * + * if (argc < 2) + * errx(1, "Usage: %s [--alias==]... ...", + * argv[0]); + * + * // Create and populate hash table. + * htable_init(&ht, rehash, NULL); + * for (i = 0; i < (int)(sizeof(map)/sizeof(map[0])); 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=")); + * else + * break; + * } + * + * // 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]), + * streq, argv[i]); + * if (!n) + * errx(1, "Invalid digit name %s", argv[i]); + * // Append it to the value we are building up. + * val *= 10; + * val += n->val; + * } + * printf("%lu\n", val); + * return 0; + * } + * + * License: LGPL (v2.1 or any later version) + * Author: Rusty Russell + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/compiler\n"); + return 0; + } + + return 1; +} diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c new file mode 100644 index 0000000..e1d1369 --- /dev/null +++ b/ccan/htable/htable.c @@ -0,0 +1,325 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include +#include +#include +#include +#include +#include +#include + +/* We use 0x1 as deleted marker. */ +#define HTABLE_DELETED (0x1) + +/* 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) +{ + return e & ht->common_mask; +} + +static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e) +{ + return (void *)((e & ~ht->common_mask) | ht->common_bits); +} + +static inline uintptr_t make_hval(const struct htable *ht, + const void *p, uintptr_t bits) +{ + return ((uintptr_t)p & ~ht->common_mask) | bits; +} + +static inline bool entry_is_valid(uintptr_t e) +{ + return e > HTABLE_DELETED; +} + +static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, + size_t hash) +{ + /* Shuffling the extra bits (as specified in mask) down the + * end is quite expensive. But the lower bits are redundant, so + * we fold the value first. */ + return (hash ^ (hash >> ht->bits)) + & ht->common_mask & ~ht->perfect_bit; +} + +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv) +{ + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->perfect_bit; +} + +/* We've changed ht->bits, update ht->max and ht->max_with_deleted */ +static void htable_adjust_capacity(struct htable *ht) +{ + ht->max = ((size_t)3 << ht->bits) / 4; + ht->max_with_deleted = ((size_t)9 << ht->bits) / 10; +} + +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; + } + htable_adjust_capacity(ht); + return true; +} + +void htable_clear(struct htable *ht) +{ + if (ht->table != &ht->perfect_bit) + free((void *)ht->table); + htable_init(ht, ht->rehash, ht->priv); +} + +bool htable_copy(struct htable *dst, const struct htable *src) +{ + uintptr_t *htable = malloc(sizeof(size_t) << src->bits); + + if (!htable) + return false; + + *dst = *src; + dst->table = htable; + memcpy(dst->table, src->table, sizeof(size_t) << src->bits); + return true; +} + +static size_t hash_bucket(const struct htable *ht, size_t h) +{ + return h & ((1 << ht->bits)-1); +} + +static void *htable_val(const struct htable *ht, + struct htable_iter *i, size_t hash, uintptr_t perfect) +{ + uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; + + while (ht->table[i->off]) { + if (ht->table[i->off] != HTABLE_DELETED) { + if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) + return get_raw_ptr(ht, ht->table[i->off]); + } + i->off = (i->off + 1) & ((1 << ht->bits)-1); + h2 &= ~perfect; + } + return NULL; +} + +void *htable_firstval(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = hash_bucket(ht, hash); + return htable_val(ht, i, hash, ht->perfect_bit); +} + +void *htable_nextval(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = (i->off + 1) & ((1 << ht->bits)-1); + return htable_val(ht, i, hash, 0); +} + +void *htable_first(const struct htable *ht, struct htable_iter *i) +{ + for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) { + if (entry_is_valid(ht->table[i->off])) + return get_raw_ptr(ht, ht->table[i->off]); + } + return NULL; +} + +void *htable_next(const struct htable *ht, struct htable_iter *i) +{ + for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) { + if (entry_is_valid(ht->table[i->off])) + return get_raw_ptr(ht, ht->table[i->off]); + } + 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) +{ + size_t i; + uintptr_t perfect = ht->perfect_bit; + + i = hash_bucket(ht, h); + + while (entry_is_valid(ht->table[i])) { + perfect = 0; + i = (i + 1) & ((1 << ht->bits)-1); + } + ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); +} + +static COLD bool double_table(struct htable *ht) +{ + unsigned int i; + size_t oldnum = (size_t)1 << ht->bits; + uintptr_t *oldtable, e; + + oldtable = ht->table; + ht->table = calloc(1 << (ht->bits+1), sizeof(size_t)); + if (!ht->table) { + ht->table = oldtable; + return false; + } + ht->bits++; + htable_adjust_capacity(ht); + + /* 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; + } + } + } + + 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; + return true; +} + +static COLD void rehash_table(struct htable *ht) +{ + size_t start, i; + uintptr_t e; + + /* Beware wrap cases: we need to start from first empty bucket. */ + for (start = 0; ht->table[start]; start++); + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + size_t h = (i + start) & ((1 << ht->bits)-1); + e = ht->table[h]; + if (!e) + continue; + if (e == HTABLE_DELETED) + ht->table[h] = 0; + else if (!(e & ht->perfect_bit)) { + void *p = get_raw_ptr(ht, e); + ht->table[h] = 0; + ht_add(ht, p, ht->rehash(p, ht->priv)); + } + } + ht->deleted = 0; +} + +/* We stole some bits, now we need to put them back... */ +static COLD void update_common(struct htable *ht, const void *p) +{ + unsigned int i; + uintptr_t maskdiff, bitsdiff; + + if (ht->elems == 0) { + /* 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; + } + + /* Find bits which are unequal to old common set. */ + maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); + + /* These are the bits which go there in existing entries. */ + bitsdiff = ht->common_bits & maskdiff; + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + if (!entry_is_valid(ht->table[i])) + continue; + /* Clear the bits no longer in the mask, set them as + * expected. */ + ht->table[i] &= ~maskdiff; + ht->table[i] |= bitsdiff; + } + + /* Take away those bits from our mask, bits and perfect bit. */ + ht->common_mask &= ~maskdiff; + ht->common_bits &= ~maskdiff; + ht->perfect_bit &= ~maskdiff; +} + +bool htable_add(struct htable *ht, size_t hash, const void *p) +{ + if (ht->elems+1 > ht->max && !double_table(ht)) + return false; + if (ht->elems+1 + ht->deleted > ht->max_with_deleted) + rehash_table(ht); + assert(p); + if (((uintptr_t)p & ht->common_mask) != ht->common_bits) + update_common(ht, p); + + ht_add(ht, p, hash); + ht->elems++; + return true; +} + +bool htable_del(struct htable *ht, size_t h, const void *p) +{ + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { + if (c == p) { + htable_delval(ht, &i); + return true; + } + } + return false; +} + +void htable_delval(struct htable *ht, struct htable_iter *i) +{ + assert(i->off < (size_t)1 << ht->bits); + assert(entry_is_valid(ht->table[i->off])); + + ht->elems--; + ht->table[i->off] = HTABLE_DELETED; + ht->deleted++; +} diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h new file mode 100644 index 0000000..9845388 --- /dev/null +++ b/ccan/htable/htable.h @@ -0,0 +1,226 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_HTABLE_H +#define CCAN_HTABLE_H +#include "config.h" +#include +#include +#include + +/** + * 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_INITIALIZER - static initialization for a hash table. + * @name: name of this htable. + * @rehash: hash function to use for rehashing. + * @priv: private argument to @rehash function. + * + * This is useful for setting up static and global hash tables. + * + * Example: + * // For simplicity's sake, say hash value is contents of elem. + * static size_t rehash(const void *elem, void *unused) + * { + * (void)unused; + * return *(size_t *)elem; + * } + * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); + */ +#define HTABLE_INITIALIZER(name, rehash, priv) \ + { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit } + +/** + * htable_init - initialize an empty hash table. + * @ht: the hash table to initialize + * @rehash: hash function to use for rehashing. + * @priv: private argument to @rehash function. + */ +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 + * + * This doesn't do anything to any pointers left in it. + */ +void htable_clear(struct htable *ht); + +/** + * htable_copy - duplicate a hash table. + * @dst: the hash table to overwrite + * @src: the hash table to copy + * + * Only fails on out-of-memory. + * + * Equivalent to (but faster than): + * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits)) + * return false; + * v = htable_first(src, &i); + * while (v) { + * htable_add(dst, v); + * v = htable_next(src, i); + * } + * return true; + */ +bool htable_copy(struct htable *dst, const struct htable *src); + +/** + * htable_rehash - use a hashtree's rehash function + * @elem: the argument to rehash() + * + */ +size_t htable_rehash(const void *elem); + +/** + * htable_add - add a pointer into a hash table. + * @ht: the htable + * @hash: the hash value of the object + * @p: the non-NULL pointer + * + * Also note that this can only fail due to allocation failure. Otherwise, it + * returns true. + */ +bool htable_add(struct htable *ht, size_t hash, const void *p); + +/** + * htable_del - remove a pointer from a hash table + * @ht: the htable + * @hash: the hash value of the object + * @p: the pointer + * + * Returns true if the pointer was found (and deleted). + */ +bool htable_del(struct htable *ht, size_t hash, const void *p); + +/** + * struct htable_iter - iterator or htable_first or htable_firstval etc. + * + * This refers to a location inside the hashtable. + */ +struct htable_iter { + size_t off; +}; + +/** + * htable_firstval - find a candidate for a given hash value + * @htable: the hashtable + * @i: the struct htable_iter to initialize + * @hash: the hash value + * + * You'll need to check the value is what you want; returns NULL if none. + * See Also: + * htable_delval() + */ +void *htable_firstval(const struct htable *htable, + struct htable_iter *i, size_t hash); + +/** + * htable_nextval - find another candidate for a given hash value + * @htable: the hashtable + * @i: the struct htable_iter to initialize + * @hash: the hash value + * + * You'll need to check the value is what you want; returns NULL if no more. + */ +void *htable_nextval(const struct htable *htable, + struct htable_iter *i, size_t hash); + +/** + * htable_get - find an entry in the hash table + * @ht: the hashtable + * @h: the hash value of the entry + * @cmp: the comparison function + * @ptr: the pointer to hand to the comparison function. + * + * Convenient inline wrapper for htable_firstval/htable_nextval loop. + */ +static inline void *htable_get(const struct htable *ht, + size_t h, + bool (*cmp)(const void *candidate, void *ptr), + const void *ptr) +{ + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { + if (cmp(c, (void *)ptr)) + return c; + } + return NULL; +} + +/** + * htable_first - find an entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to initialize + * + * Get an entry in the hashtable; NULL if empty. + */ +void *htable_first(const struct htable *htable, struct htable_iter *i); + +/** + * htable_next - find another entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to use + * + * Get another entry in the hashtable; NULL if all done. + * This is usually used after htable_first or prior non-NULL htable_next. + */ +void *htable_next(const struct htable *htable, struct htable_iter *i); + +/** + * htable_prev - find the previous entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to use + * + * Get previous entry in the hashtable; NULL if all done. + * + * "previous" here only means the item that would have been returned by + * htable_next() before the item it returned most recently. + * + * This is usually used in the middle of (or after) a htable_next iteration and + * to "unwind" actions taken. + */ +void *htable_prev(const struct htable *htable, struct htable_iter *i); + +/** + * htable_delval - remove an iterated pointer from a hash table + * @ht: the htable + * @i: the htable_iter + * + * Usually used to delete a hash entry after it has been found with + * htable_firstval etc. + */ +void htable_delval(struct htable *ht, struct htable_iter *i); + +#endif /* CCAN_HTABLE_H */ diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h new file mode 100644 index 0000000..1401167 --- /dev/null +++ b/ccan/htable/htable_type.h @@ -0,0 +1,166 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_HTABLE_TYPE_H +#define CCAN_HTABLE_TYPE_H +#include +#include +#include "config.h" + +/** + * 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: @keyof(const type *elem) + * @hashfn: a hash function for a @key: size_t @hashfn(const *) + * @eqfn: an equality function keys: bool @eqfn(const type *, const *) + * @prefix: a prefix for all the functions to define (of form _*) + * + * NULL values may not be placed into the hash table. + * + * This defines the type hashtable type and an iterator type: + * struct ; + * struct _iter; + * + * It also defines initialization and freeing functions: + * void _init(struct *); + * bool _init_sized(struct *, size_t); + * void _clear(struct *); + * bool _copy(struct *dst, const struct *src); + * + * Add function only fails if we run out of memory: + * bool _add(struct *ht, const *e); + * + * Delete and delete-by key return true if it was in the set: + * bool _del(struct *ht, const *e); + * bool _delkey(struct *ht, const *k); + * + * Find and return the (first) matching element, or NULL: + * type *_get(const struct @name *ht, const *k); + * + * Find and return all matching elements, or NULL: + * type *_getfirst(const struct @name *ht, const *k, + * struct _iter *i); + * type *_getnext(const struct @name *ht, const *k, + * struct _iter *i); + * + * Iteration over hashtable is also supported: + * type *_first(const struct *ht, struct _iter *i); + * type *_next(const struct *ht, struct _iter *i); + * type *_prev(const struct *ht, struct _iter *i); + * + * It's currently safe to iterate over a changing hashtable, but you might + * miss an element. Iteration isn't very efficient, either. + * + * You can use HTABLE_INITIALIZER like so: + * struct ht = { HTABLE_INITIALIZER(ht.raw, _hash, NULL) }; + */ +#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) \ + { \ + (void)priv; \ + return hashfn(keyof((const type *)elem)); \ + } \ + static inline UNNEEDED void name##_init(struct name *ht) \ + { \ + htable_init(&ht->raw, name##_hash, NULL); \ + } \ + static inline UNNEEDED bool name##_init_sized(struct name *ht, \ + size_t s) \ + { \ + return htable_init_sized(&ht->raw, name##_hash, NULL, s); \ + } \ + static inline UNNEEDED void name##_clear(struct name *ht) \ + { \ + htable_clear(&ht->raw); \ + } \ + static inline UNNEEDED bool name##_copy(struct name *dst, \ + const struct name *src) \ + { \ + return htable_copy(&dst->raw, &src->raw); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED bool name##_del(struct name *ht, \ + const type *elem) \ + { \ + return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED type *name##_get(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *c; \ + \ + for (c = htable_firstval(&ht->raw,&i,h); \ + c; \ + c = htable_nextval(&ht->raw,&i,h)) { \ + if (eqfn(c, k)) \ + return c; \ + } \ + return NULL; \ + } \ + static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + size_t h, \ + type *v, \ + struct name##_iter *iter) \ + { \ + while (v) { \ + if (eqfn(v, k)) \ + break; \ + v = htable_nextval(&ht->raw, &iter->i, h); \ + } \ + return v; \ + } \ + static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_firstval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED type *name##_getnext(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_nextval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED bool name##_delkey(struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + type *elem = name##_get(ht, k); \ + if (elem) \ + return name##_del(ht, elem); \ + return false; \ + } \ + static inline UNNEEDED type *name##_first(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_first(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_next(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_next(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_prev(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_prev(&ht->raw, &iter->i); \ + } + +#if HAVE_TYPEOF +#define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) +#else +/* Assumes keys are a pointer: if not, override. */ +#ifndef HTABLE_KTYPE +#define HTABLE_KTYPE(keyof, type) void * +#endif +#endif +#endif /* CCAN_HTABLE_TYPE_H */ diff --git a/ccan/htable/test/run-copy.c b/ccan/htable/test/run-copy.c new file mode 100644 index 0000000..d111495 --- /dev/null +++ b/ccan/htable/test/run-copy.c @@ -0,0 +1,44 @@ +#include +#include +#include +#include +#include + +#define NUM_VALS 512 + +static size_t hash(const void *elem, void *unused UNNEEDED) +{ + size_t h = *(uint64_t *)elem / 2; + return h; +} + +static bool cmp(const void *candidate, void *ptr) +{ + return *(const uint64_t *)candidate == *(const uint64_t *)ptr; +} + +int main(void) +{ + struct htable ht, ht2; + uint64_t val[NUM_VALS], i; + + plan_tests((NUM_VALS) * 3); + for (i = 0; i < NUM_VALS; i++) + val[i] = i; + + 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]); + } + + htable_copy(&ht2, &ht); + htable_clear(&ht); + + for (i = 0; i < NUM_VALS; i++) + ok1(htable_get(&ht2, hash(&i, NULL), cmp, &i) == &val[i]); + htable_clear(&ht2); + + return exit_status(); +} diff --git a/ccan/htable/test/run-size.c b/ccan/htable/test/run-size.c new file mode 100644 index 0000000..1a2f5cd --- /dev/null +++ b/ccan/htable/test/run-size.c @@ -0,0 +1,36 @@ +#include +#include +#include +#include +#include + +#define NUM_VALS 512 + +/* We use the number divided by two as the hash (for lots of + collisions). */ +static size_t hash(const void *elem, void *unused UNNEEDED) +{ + size_t h = *(uint64_t *)elem / 2; + return h; +} + +int main(void) +{ + struct htable ht; + uint64_t val[NUM_VALS]; + unsigned int i; + + plan_tests((NUM_VALS) * 2); + for (i = 0; i < NUM_VALS; i++) + val[i] = i; + + 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]); + } + htable_clear(&ht); + + return exit_status(); +} diff --git a/ccan/htable/test/run-type-int.c b/ccan/htable/test/run-type-int.c new file mode 100644 index 0000000..7b71815 --- /dev/null +++ b/ccan/htable/test/run-type-int.c @@ -0,0 +1,215 @@ +/* Key is an unsigned int, not a pointer. */ +#include "config.h" +#if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF +#define HTABLE_KTYPE(keyof, type) unsigned int +#endif +#include +#include +#include +#include +#include + +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) + +struct obj { + /* Makes sure we don't try to treat and obj as a key or vice versa */ + unsigned char unused; + unsigned int key; +}; + +static const unsigned int objkey(const struct obj *obj) +{ + return obj->key; +} + +/* We use the number divided by two as the hash (for lots of + collisions), plus set all the higher bits so we can detect if they + don't get masked out. */ +static size_t objhash(const unsigned int key) +{ + size_t h = key / 2; + h |= -1UL << NUM_BITS; + return h; +} + +static bool cmp(const struct obj *obj, const unsigned int key) +{ + return obj->key == key; +} + +HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj); + +static void add_vals(struct htable_obj *ht, + struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, i)) { + fail("%u already in hash", i); + return; + } + htable_obj_add(ht, &val[i]); + if (htable_obj_get(ht, i) != &val[i]) { + fail("%u not added to hash", i); + return; + } + } + pass("Added %u numbers to hash", i); +} + +static void find_vals(const struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, i) != &val[i]) { + fail("%u not found in hash", i); + return; + } + } + pass("Found %u numbers in hash", i); +} + +static void del_vals(struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, val[i].key)) { + fail("%u not deleted from hash", i); + return; + } + } + pass("Deleted %u numbers in hash", i); +} + +static void del_vals_bykey(struct htable_obj *ht, + const struct obj val[] UNNEEDED, unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, i)) { + fail("%u not deleted by key from hash", i); + return; + } + } + pass("Deleted %u numbers by key from hash", i); +} + +static bool check_mask(struct htable *ht, const struct obj val[], unsigned num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits) + return false; + } + return true; +} + +int main(void) +{ + unsigned int i; + struct htable_obj ht, ht2; + struct obj val[NUM_VALS], *result; + unsigned int dne; + void *p; + struct htable_obj_iter iter; + + plan_tests(29); + for (i = 0; i < NUM_VALS; i++) + val[i].key = i; + dne = i; + + 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)); + + /* Fill it, it should increase in size. */ + 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(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)); + + /* Walk once, should get them all. */ + i = 0; + for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + i = 0; + for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + + /* Delete all. */ + 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(&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(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + + /* Add the rest. */ + 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)); + + /* Check copy. */ + ok1(htable_obj_copy(&ht2, &ht)); + + /* Delete them all by key. */ + del_vals_bykey(&ht, val, NUM_VALS); + del_vals_bykey(&ht2, val, NUM_VALS); + + /* Write two of the same value. */ + val[1] = val[0]; + htable_obj_add(&ht, &val[0]); + htable_obj_add(&ht, &val[1]); + i = 0; + + result = htable_obj_getfirst(&ht, i, &iter); + ok1(result == &val[0] || result == &val[1]); + if (result == &val[0]) { + ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]); + ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + + /* Deleting first should make us iterate over the other. */ + ok1(htable_obj_del(&ht, &val[0])); + ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]); + ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + } else { + ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]); + ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + + /* Deleting first should make us iterate over the other. */ + ok1(htable_obj_del(&ht, &val[1])); + ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]); + ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + } + + htable_obj_clear(&ht); + htable_obj_clear(&ht2); + return exit_status(); +} diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c new file mode 100644 index 0000000..a3616a5 --- /dev/null +++ b/ccan/htable/test/run-type.c @@ -0,0 +1,210 @@ +#include +#include +#include +#include +#include + +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) + +struct obj { + /* Makes sure we don't try to treat and obj as a key or vice versa */ + unsigned char unused; + unsigned int key; +}; + +static const unsigned int *objkey(const struct obj *obj) +{ + return &obj->key; +} + +/* We use the number divided by two as the hash (for lots of + collisions), plus set all the higher bits so we can detect if they + don't get masked out. */ +static size_t objhash(const unsigned int *key) +{ + size_t h = *key / 2; + h |= -1UL << NUM_BITS; + return h; +} + +static bool cmp(const struct obj *obj, const unsigned int *key) +{ + return obj->key == *key; +} + +HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj); + +static void add_vals(struct htable_obj *ht, + struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, &i)) { + fail("%u already in hash", i); + return; + } + htable_obj_add(ht, &val[i]); + if (htable_obj_get(ht, &i) != &val[i]) { + fail("%u not added to hash", i); + return; + } + } + pass("Added %u numbers to hash", i); +} + +static void find_vals(const struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, &i) != &val[i]) { + fail("%u not found in hash", i); + return; + } + } + pass("Found %u numbers in hash", i); +} + +static void del_vals(struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, &val[i].key)) { + fail("%u not deleted from hash", i); + return; + } + } + pass("Deleted %u numbers in hash", i); +} + +static void del_vals_bykey(struct htable_obj *ht, + const struct obj val[] UNNEEDED, unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, &i)) { + fail("%u not deleted by key from hash", i); + return; + } + } + pass("Deleted %u numbers by key from hash", i); +} + +static bool check_mask(struct htable *ht, const struct obj val[], unsigned num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits) + return false; + } + return true; +} + +int main(void) +{ + unsigned int i; + struct htable_obj ht, ht2; + struct obj val[NUM_VALS], *result; + unsigned int dne; + void *p; + struct htable_obj_iter iter; + + plan_tests(29); + for (i = 0; i < NUM_VALS; i++) + val[i].key = i; + dne = i; + + 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)); + + /* Fill it, it should increase in size. */ + 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(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)); + + /* Walk once, should get them all. */ + i = 0; + for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + i = 0; + for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + + /* Delete all. */ + 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(&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(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + + /* Add the rest. */ + 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)); + + /* Check copy. */ + ok1(htable_obj_copy(&ht2, &ht)); + + /* Delete them all by key. */ + del_vals_bykey(&ht, val, NUM_VALS); + del_vals_bykey(&ht2, val, NUM_VALS); + + /* Write two of the same value. */ + val[1] = val[0]; + htable_obj_add(&ht, &val[0]); + htable_obj_add(&ht, &val[1]); + i = 0; + + result = htable_obj_getfirst(&ht, &i, &iter); + ok1(result == &val[0] || result == &val[1]); + if (result == &val[0]) { + ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]); + ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + + /* Deleting first should make us iterate over the other. */ + ok1(htable_obj_del(&ht, &val[0])); + ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]); + ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + } else { + ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]); + ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + + /* Deleting first should make us iterate over the other. */ + ok1(htable_obj_del(&ht, &val[1])); + ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]); + ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + } + + htable_obj_clear(&ht); + htable_obj_clear(&ht2); + return exit_status(); +} diff --git a/ccan/htable/test/run-zero-hash-first-entry.c b/ccan/htable/test/run-zero-hash-first-entry.c new file mode 100644 index 0000000..3a1a939 --- /dev/null +++ b/ccan/htable/test/run-zero-hash-first-entry.c @@ -0,0 +1,61 @@ +#include +#include +#include +#include + +struct data { + size_t key; +}; + +/* Hash is simply key itself. */ +static size_t hash(const void *e, void *unused UNNEEDED) +{ + struct data *d = (struct data *)e; + + return d->key; +} + +static bool eq(const void *e, void *k) +{ + struct data *d = (struct data *)e; + size_t *key = (size_t *)k; + + return (d->key == *key); +} + +int main(void) +{ + struct htable table; + struct data *d0, *d1; + + plan_tests(6); + + d1 = malloc(sizeof(struct data)); + d1->key = 1; + d0 = malloc(sizeof(struct data)); + d0->key = 0; + + htable_init(&table, hash, NULL); + + htable_add(&table, d0->key, d0); + htable_add(&table, d1->key, d1); + + ok1(table.elems == 2); + ok1(htable_get(&table, 1, eq, &d1->key) == d1); + ok1(htable_get(&table, 0, eq, &d0->key) == d0); + htable_clear(&table); + + /* Now add in reverse order, should still be OK. */ + htable_add(&table, d1->key, d1); + htable_add(&table, d0->key, d0); + + ok1(table.elems == 2); + ok1(htable_get(&table, 1, eq, &d1->key) == d1); + ok1(htable_get(&table, 0, eq, &d0->key) == d0); + htable_clear(&table); + + free(d0); + free(d1); + return exit_status(); +} + diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c new file mode 100644 index 0000000..46514c7 --- /dev/null +++ b/ccan/htable/test/run.c @@ -0,0 +1,212 @@ +#include +#include +#include +#include +#include + +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) + +/* We use the number divided by two as the hash (for lots of + collisions), plus set all the higher bits so we can detect if they + don't get masked out. */ +static size_t hash(const void *elem, void *unused UNNEEDED) +{ + size_t h = *(uint64_t *)elem / 2; + h |= -1UL << NUM_BITS; + return h; +} + +static bool objcmp(const void *htelem, void *cmpdata) +{ + return *(uint64_t *)htelem == *(uint64_t *)cmpdata; +} + +static void add_vals(struct htable *ht, + const uint64_t val[], + unsigned int off, unsigned int num) +{ + uint64_t i; + + for (i = off; i < off+num; i++) { + if (htable_get(ht, hash(&i, NULL), objcmp, &i)) { + fail("%llu already in hash", (long long)i); + return; + } + htable_add(ht, hash(&val[i], NULL), &val[i]); + if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) { + fail("%llu not added to hash", (long long)i); + return; + } + } + pass("Added %llu numbers to hash", (long long)i); +} + +#if 0 +static void refill_vals(struct htable *ht, + const uint64_t val[], unsigned int num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (htable_get(ht, hash(&i, NULL), objcmp, &i)) + continue; + htable_add(ht, hash(&val[i], NULL), &val[i]); + } +} +#endif + +static void find_vals(struct htable *ht, + const uint64_t val[], unsigned int num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) { + fail("%llu not found in hash", (long long)i); + return; + } + } + pass("Found %llu numbers in hash", (long long)i); +} + +static void del_vals(struct htable *ht, + const uint64_t val[], unsigned int num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (!htable_del(ht, hash(&val[i], NULL), &val[i])) { + fail("%llu not deleted from hash", (long long)i); + return; + } + } + pass("Deleted %llu numbers in hash", (long long)i); +} + +static bool check_mask(struct htable *ht, uint64_t val[], unsigned num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits) + return false; + } + return true; +} + +int main(void) +{ + unsigned int i, weight; + uintptr_t perfect_bit; + struct htable ht; + uint64_t val[NUM_VALS]; + uint64_t dne; + void *p; + struct htable_iter iter; + + plan_tests(36); + for (i = 0; i < NUM_VALS; i++) + val[i] = i; + dne = i; + + 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)); + + /* This should increase it once. */ + add_vals(&ht, val, 0, 1); + ok1(ht.bits == 1); + ok1(ht.max == 1); + weight = 0; + for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) { + if (ht.common_mask & ((uintptr_t)1 << i)) { + weight++; + } + } + /* Only one bit should be clear. */ + ok1(weight == i-1); + + /* Mask should be set. */ + 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); + + /* Mask should be set. */ + 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); + + /* Find all. */ + 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)) + i++; + ok1(i == NUM_VALS); + + i = 0; + for (p = htable_prev(&ht, &iter); p; p = htable_prev(&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])); + + /* 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); + /* Get rid of bogus pointer before we trip over it! */ + htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + + /* Add the rest. */ + 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)); + + /* Corner cases: wipe out the perfect bit using bogus pointer. */ + 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)); + + /* Enlarging should restore it... */ + add_vals(&ht, val, 0, NUM_VALS-1); + + 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(); +} diff --git a/ccan/htable/tools/Makefile b/ccan/htable/tools/Makefile new file mode 100644 index 0000000..a2cad59 --- /dev/null +++ b/ccan/htable/tools/Makefile @@ -0,0 +1,40 @@ +CCANDIR=../../.. +CFLAGS=-Wall -Werror -O3 -I$(CCANDIR) +#CFLAGS=-Wall -Werror -g -I$(CCANDIR) + +CCAN_OBJS:=ccan-tal.o ccan-tal-str.o ccan-tal-grab_file.o ccan-take.o ccan-time.o ccan-str.o ccan-noerr.o ccan-list.o + +all: speed stringspeed hsearchspeed + +speed: speed.o hash.o $(CCAN_OBJS) + +speed.o: speed.c ../htable.h ../htable.c + +hash.o: ../../hash/hash.c + $(CC) $(CFLAGS) -c -o $@ $< + +stringspeed: stringspeed.o hash.o $(CCAN_OBJS) + +stringspeed.o: speed.c ../htable.h ../htable.c + +hsearchspeed: hsearchspeed.o $(CCAN_OBJS) + +clean: + rm -f stringspeed speed hsearchspeed *.o + +ccan-tal.o: $(CCANDIR)/ccan/tal/tal.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-tal-str.o: $(CCANDIR)/ccan/tal/str/str.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-take.o: $(CCANDIR)/ccan/take/take.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-tal-grab_file.o: $(CCANDIR)/ccan/tal/grab_file/grab_file.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-time.o: $(CCANDIR)/ccan/time/time.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-list.o: $(CCANDIR)/ccan/list/list.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-str.o: $(CCANDIR)/ccan/str/str.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-noerr.o: $(CCANDIR)/ccan/noerr/noerr.c + $(CC) $(CFLAGS) -c -o $@ $< diff --git a/ccan/htable/tools/hsearchspeed.c b/ccan/htable/tools/hsearchspeed.c new file mode 100644 index 0000000..8828011 --- /dev/null +++ b/ccan/htable/tools/hsearchspeed.c @@ -0,0 +1,95 @@ +/* Simple speed tests for a hash of strings using hsearch */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* Nanoseconds per operation */ +static size_t normalize(const struct timeabs *start, + const struct timeabs *stop, + unsigned int num) +{ + return time_to_nsec(time_divide(time_between(*stop, *start), num)); +} + +int main(int argc, char *argv[]) +{ + size_t i, j, num; + struct timeabs start, stop; + char **w; + ENTRY *words, *misswords; + + w = tal_strsplit(NULL, grab_file(NULL, + argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", STR_NO_EMPTY); + num = tal_count(w) - 1; + printf("%zu words\n", num); + + hcreate(num+num/3); + + words = tal_arr(w, ENTRY, num); + for (i = 0; i < num; i++) { + words[i].key = w[i]; + words[i].data = words[i].key; + } + + /* Append and prepend last char for miss testing. */ + misswords = tal_arr(w, ENTRY, num); + for (i = 0; i < num; i++) { + char lastc; + if (strlen(w[i])) + lastc = w[i][strlen(w[i])-1]; + else + lastc = 'z'; + misswords[i].key = tal_fmt(misswords, "%c%s%c%c", + lastc, w[i], lastc, lastc); + } + + printf("#01: Initial insert: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + hsearch(words[i], ENTER); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#02: Initial lookup (match): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + if (hsearch(words[i], FIND)->data != words[i].data) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#03: Initial lookup (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + if (hsearch(misswords[i], FIND)) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Lookups in order are very cache-friendly for judy; try random */ + printf("#04: Initial lookup (random): "); + fflush(stdout); + start = time_now(); + for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) + if (hsearch(words[i], FIND)->data != words[i].data) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + return 0; +} diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c new file mode 100644 index 0000000..dce3fdf --- /dev/null +++ b/ccan/htable/tools/speed.c @@ -0,0 +1,370 @@ +/* Simple speed tests for hashtables. */ +#include +#include +#include +#include +#include +#include +#include +#include + +static size_t hashcount; +struct object { + /* The key. */ + unsigned int key; + + /* Some contents. Doubles as consistency check. */ + struct object *self; +}; + +static const unsigned int *objkey(const struct object *obj) +{ + return &obj->key; +} + +static size_t hash_obj(const unsigned int *key) +{ + hashcount++; + return hashl(key, 1, 0); +} + +static bool cmp(const struct object *object, const unsigned int *key) +{ + return object->key == *key; +} + +HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj); + +static unsigned int popcount(unsigned long val) +{ +#if HAVE_BUILTIN_POPCOUNTL + return __builtin_popcountl(val); +#else + if (sizeof(long) == sizeof(u64)) { + u64 v = val; + v = (v & 0x5555555555555555ULL) + + ((v >> 1) & 0x5555555555555555ULL); + v = (v & 0x3333333333333333ULL) + + ((v >> 1) & 0x3333333333333333ULL); + v = (v & 0x0F0F0F0F0F0F0F0FULL) + + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL); + v = (v & 0x00FF00FF00FF00FFULL) + + ((v >> 1) & 0x00FF00FF00FF00FFULL); + v = (v & 0x0000FFFF0000FFFFULL) + + ((v >> 1) & 0x0000FFFF0000FFFFULL); + v = (v & 0x00000000FFFFFFFFULL) + + ((v >> 1) & 0x00000000FFFFFFFFULL); + return v; + } + val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL); + val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL); + val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL); + val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL); + val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL); + return val; +#endif +} + +static size_t perfect(const struct htable *ht) +{ + size_t i, placed_perfect = 0; + + for (i = 0; i < ((size_t)1 << ht->bits); i++) { + if (!entry_is_valid(ht->table[i])) + continue; + if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]), + ht->priv)) == i) { + assert((ht->table[i] & ht->perfect_bit) + == ht->perfect_bit); + placed_perfect++; + } + } + return placed_perfect; +} + +static size_t count_deleted(const struct htable *ht) +{ + size_t i, delete_markers = 0; + + for (i = 0; i < ((size_t)1 << ht->bits); i++) { + if (ht->table[i] == HTABLE_DELETED) + delete_markers++; + } + return delete_markers; +} + +/* Nanoseconds per operation */ +static size_t normalize(const struct timeabs *start, + const struct timeabs *stop, + unsigned int num) +{ + return time_to_nsec(time_divide(time_between(*stop, *start), num)); +} + +static size_t worst_run(struct htable *ht, size_t *deleted) +{ + size_t longest = 0, len = 0, this_del = 0, i; + + *deleted = 0; + /* This doesn't take into account end-wrap, but gives an idea. */ + for (i = 0; i < ((size_t)1 << ht->bits); i++) { + if (ht->table[i]) { + len++; + if (ht->table[i] == HTABLE_DELETED) + this_del++; + } else { + if (len > longest) { + longest = len; + *deleted = this_del; + } + len = 0; + this_del = 0; + } + } + return longest; +} + +int main(int argc, char *argv[]) +{ + struct object *objs; + unsigned int i, j; + size_t num, deleted; + struct timeabs start, stop; + struct htable_obj ht; + bool make_dumb = false; + + if (argv[1] && strcmp(argv[1], "--dumb") == 0) { + argv++; + make_dumb = true; + } + num = argv[1] ? atoi(argv[1]) : 1000000; + objs = calloc(num, sizeof(objs[0])); + + for (i = 0; i < num; i++) { + objs[i].key = i; + objs[i].self = &objs[i]; + } + + htable_obj_init(&ht); + + printf("Initial insert: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + htable_obj_add(&ht, objs[i].self); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n", + 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(&ht.raw, (void *)~ht.raw.common_bits); + printf("Details: DUMB MODE: mask bits %u\n", + popcount(ht.raw.common_mask)); + } + + printf("Initial lookup (match): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + if (htable_obj_get(&ht, &i)->self != objs[i].self) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Initial lookup (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + unsigned int n = i + num; + if (htable_obj_get(&ht, &n)) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Lookups in order are very cache-friendly for judy; try random */ + printf("Initial lookup (random): "); + fflush(stdout); + start = time_now(); + for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) + if (htable_obj_get(&ht, &j)->self != &objs[j]) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + hashcount = 0; + printf("Initial delete all: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + if (!htable_obj_del(&ht, objs[i].self)) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + printf("Details: rehashes %zu\n", hashcount); + + printf("Initial re-inserting: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + htable_obj_add(&ht, objs[i].self); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + hashcount = 0; + printf("Deleting first half: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i+=2) + if (!htable_obj_del(&ht, objs[i].self)) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Details: rehashes %zu, delete markers %zu\n", + hashcount, count_deleted(&ht.raw)); + + printf("Adding (a different) half: "); + fflush(stdout); + + for (i = 0; i < num; i+=2) + objs[i].key = num+i; + + start = time_now(); + for (i = 0; i < num; i+=2) + htable_obj_add(&ht, objs[i].self); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Details: delete markers %zu, perfect %.0f%%\n", + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); + + printf("Lookup after half-change (match): "); + fflush(stdout); + start = time_now(); + for (i = 1; i < num; i+=2) + 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) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Lookup after half-change (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + unsigned int n = i + num * 2; + if (htable_obj_get(&ht, &n)) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Hashtables with delete markers can fill with markers over time. + * so do some changes to see how it operates in long-term. */ + for (i = 0; i < 5; i++) { + if (i == 0) { + /* We don't measure this: jmap is different. */ + printf("Details: initial churn\n"); + } else { + printf("Churning %s time: ", + i == 1 ? "second" + : i == 2 ? "third" + : i == 3 ? "fourth" + : "fifth"); + fflush(stdout); + } + start = time_now(); + for (j = 0; j < num; j++) { + if (!htable_obj_del(&ht, &objs[j])) + abort(); + objs[j].key = num*i+j; + if (!htable_obj_add(&ht, &objs[j])) + abort(); + } + stop = time_now(); + if (i != 0) + printf(" %zu ns\n", normalize(&start, &stop, num)); + } + + /* 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)) + abort(); + objs[i].key = num * 5 + i * 9; + if (!htable_obj_add(&ht, objs[i].self)) + abort(); + } + printf("Details: delete markers %zu, perfect %.0f%%\n", + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); + i = worst_run(&ht.raw, &deleted); + printf("Details: worst run %u (%zu deleted)\n", i, deleted); + + printf("Lookup after churn & spread (match): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + unsigned int n = num * 5 + i * 9; + if (htable_obj_get(&ht, &n)->self != objs[i].self) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Lookup after churn & spread (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + unsigned int n = num * (5 + 9) + i * 9; + if (htable_obj_get(&ht, &n)) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Lookup after churn & spread (random): "); + fflush(stdout); + start = time_now(); + 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]) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + hashcount = 0; + printf("Deleting half after churn & spread: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i+=2) + if (!htable_obj_del(&ht, objs[i].self)) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Adding (a different) half after churn & spread: "); + fflush(stdout); + + for (i = 0; i < num; i+=2) + objs[i].key = num*6+i*9; + + start = time_now(); + for (i = 0; i < num; i+=2) + htable_obj_add(&ht, objs[i].self); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Details: delete markers %zu, perfect %.0f%%\n", + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); + + return 0; +} diff --git a/ccan/htable/tools/stringspeed.c b/ccan/htable/tools/stringspeed.c new file mode 100644 index 0000000..c6ca10f --- /dev/null +++ b/ccan/htable/tools/stringspeed.c @@ -0,0 +1,240 @@ +/* Simple speed tests for a hash of strings. */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +static size_t hashcount; + +static const char *strkey(const char *str) +{ + return str; +} + +static size_t hash_str(const char *key) +{ + hashcount++; + return hash(key, strlen(key), 0); +} + +static bool cmp(const char *obj, const char *key) +{ + return strcmp(obj, key) == 0; +} + +HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str); + +/* Nanoseconds per operation */ +static size_t normalize(const struct timeabs *start, + const struct timeabs *stop, + unsigned int num) +{ + return time_to_nsec(time_divide(time_between(*stop, *start), num)); +} + +int main(int argc, char *argv[]) +{ + size_t i, j, num; + struct timeabs start, stop; + struct htable_str ht; + char **words, **misswords; + + words = tal_strsplit(NULL, grab_file(NULL, + argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", + STR_NO_EMPTY); + htable_str_init(&ht); + num = tal_count(words) - 1; + /* Note that on my system, num is just > 98304, where we double! */ + printf("%zu words\n", num); + + /* Append and prepend last char for miss testing. */ + misswords = tal_arr(words, char *, num); + for (i = 0; i < num; i++) { + char lastc; + if (strlen(words[i])) + lastc = words[i][strlen(words[i])-1]; + else + lastc = 'z'; + misswords[i] = tal_fmt(misswords, "%c%s%c%c", + lastc, words[i], lastc, lastc); + } + + printf("#01: Initial insert: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + htable_str_add(&ht, words[i]); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("Bytes allocated: %zu\n", + 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]) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#03: Initial lookup (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + if (htable_str_get(&ht, misswords[i])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Lookups in order are very cache-friendly for judy; try random */ + printf("#04: Initial lookup (random): "); + 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]) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + hashcount = 0; + printf("#05: Initial delete all: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + if (!htable_str_del(&ht, words[i])) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#06: Initial re-inserting: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + htable_str_add(&ht, words[i]); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + hashcount = 0; + printf("#07: Deleting first half: "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i+=2) + if (!htable_str_del(&ht, words[i])) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#08: Adding (a different) half: "); + fflush(stdout); + + start = time_now(); + for (i = 0; i < num; i+=2) + htable_str_add(&ht, misswords[i]); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#09: Lookup after half-change (match): "); + fflush(stdout); + start = time_now(); + for (i = 1; i < num; i+=2) + 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]) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#10: Lookup after half-change (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i+=2) + if (htable_str_get(&ht, words[i])) + abort(); + for (i = 1; i < num; i+=2) { + if (htable_str_get(&ht, misswords[i])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Hashtables with delete markers can fill with markers over time. + * so do some changes to see how it operates in long-term. */ + printf("#11: Churn 1: "); + start = time_now(); + for (j = 0; j < num; j+=2) { + if (!htable_str_del(&ht, misswords[j])) + abort(); + if (!htable_str_add(&ht, words[j])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#12: Churn 2: "); + start = time_now(); + for (j = 1; j < num; j+=2) { + if (!htable_str_del(&ht, words[j])) + abort(); + if (!htable_str_add(&ht, misswords[j])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#13: Churn 3: "); + start = time_now(); + for (j = 1; j < num; j+=2) { + if (!htable_str_del(&ht, misswords[j])) + abort(); + if (!htable_str_add(&ht, words[j])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Now it's back to normal... */ + printf("#14: Post-Churn lookup (match): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) + if (htable_str_get(&ht, words[i]) != words[i]) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + printf("#15: Post-Churn lookup (miss): "); + fflush(stdout); + start = time_now(); + for (i = 0; i < num; i++) { + if (htable_str_get(&ht, misswords[i])) + abort(); + } + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + /* Lookups in order are very cache-friendly for judy; try random */ + printf("#16: Post-Churn lookup (random): "); + 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]) + abort(); + stop = time_now(); + printf(" %zu ns\n", normalize(&start, &stop, num)); + + return 0; +} -- cgit v1.2.3