diff options
Diffstat (limited to 'ccan/htable')
| l--------- | ccan/htable/LICENSE | 1 | ||||
| -rw-r--r-- | ccan/htable/_info | 117 | ||||
| -rw-r--r-- | ccan/htable/htable.c | 325 | ||||
| -rw-r--r-- | ccan/htable/htable.h | 226 | ||||
| -rw-r--r-- | ccan/htable/htable_type.h | 166 | ||||
| -rw-r--r-- | ccan/htable/test/run-copy.c | 44 | ||||
| -rw-r--r-- | ccan/htable/test/run-size.c | 36 | ||||
| -rw-r--r-- | ccan/htable/test/run-type-int.c | 215 | ||||
| -rw-r--r-- | ccan/htable/test/run-type.c | 210 | ||||
| -rw-r--r-- | ccan/htable/test/run-zero-hash-first-entry.c | 61 | ||||
| -rw-r--r-- | ccan/htable/test/run.c | 212 | ||||
| -rw-r--r-- | ccan/htable/tools/Makefile | 40 | ||||
| -rw-r--r-- | ccan/htable/tools/hsearchspeed.c | 95 | ||||
| -rw-r--r-- | ccan/htable/tools/speed.c | 370 | ||||
| -rw-r--r-- | ccan/htable/tools/stringspeed.c | 240 |
15 files changed, 0 insertions, 2358 deletions
diff --git a/ccan/htable/LICENSE b/ccan/htable/LICENSE deleted file mode 120000 index dc314ec..0000000 --- a/ccan/htable/LICENSE +++ /dev/null @@ -1 +0,0 @@ -../../licenses/LGPL-2.1
\ No newline at end of file diff --git a/ccan/htable/_info b/ccan/htable/_info deleted file mode 100644 index a3bb76d..0000000 --- a/ccan/htable/_info +++ /dev/null @@ -1,117 +0,0 @@ -#include "config.h" -#include <string.h> -#include <stdio.h> - -/** - * 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 <ccan/htable/htable.h> - * #include <ccan/hash/hash.h> - * #include <stdio.h> - * #include <err.h> - * #include <string.h> - * - * 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=<name>=<value>"); - * *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=<name>=<val>]... <str>...", - * 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 <rusty@rustcorp.com.au> - */ -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 deleted file mode 100644 index e1d1369..0000000 --- a/ccan/htable/htable.c +++ /dev/null @@ -1,325 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#include <ccan/htable/htable.h> -#include <ccan/compiler/compiler.h> -#include <stdlib.h> -#include <limits.h> -#include <stdbool.h> -#include <assert.h> -#include <string.h> - -/* 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 deleted file mode 100644 index 9845388..0000000 --- a/ccan/htable/htable.h +++ /dev/null @@ -1,226 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#ifndef CCAN_HTABLE_H -#define CCAN_HTABLE_H -#include "config.h" -#include <stdint.h> -#include <stdbool.h> -#include <stdlib.h> - -/** - * 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 deleted file mode 100644 index 1401167..0000000 --- a/ccan/htable/htable_type.h +++ /dev/null @@ -1,166 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#ifndef CCAN_HTABLE_TYPE_H -#define CCAN_HTABLE_TYPE_H -#include <ccan/htable/htable.h> -#include <ccan/compiler/compiler.h> -#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: <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. - * - * This defines the type hashtable type and an iterator type: - * struct <name>; - * struct <name>_iter; - * - * It also defines initialization and freeing functions: - * void <name>_init(struct <name> *); - * bool <name>_init_sized(struct <name> *, size_t); - * void <name>_clear(struct <name> *); - * bool <name>_copy(struct <name> *dst, const struct <name> *src); - * - * Add function only fails if we run out of memory: - * bool <name>_add(struct <name> *ht, const <type> *e); - * - * 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 and return the (first) matching element, or NULL: - * type *<name>_get(const struct @name *ht, const <keytype> *k); - * - * Find and return all matching elements, or NULL: - * type *<name>_getfirst(const struct @name *ht, const <keytype> *k, - * struct <name>_iter *i); - * type *<name>_getnext(const struct @name *ht, const <keytype> *k, - * struct <name>_iter *i); - * - * 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); - * type *<name>_prev(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. - * - * You can use HTABLE_INITIALIZER like so: - * struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_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 deleted file mode 100644 index d111495..0000000 --- a/ccan/htable/test/run-copy.c +++ /dev/null @@ -1,44 +0,0 @@ -#include <ccan/htable/htable.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> -#include <string.h> - -#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 deleted file mode 100644 index 1a2f5cd..0000000 --- a/ccan/htable/test/run-size.c +++ /dev/null @@ -1,36 +0,0 @@ -#include <ccan/htable/htable.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> -#include <string.h> - -#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 deleted file mode 100644 index 7b71815..0000000 --- a/ccan/htable/test/run-type-int.c +++ /dev/null @@ -1,215 +0,0 @@ -/* 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 <ccan/htable/htable_type.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> -#include <string.h> - -#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 deleted file mode 100644 index a3616a5..0000000 --- a/ccan/htable/test/run-type.c +++ /dev/null @@ -1,210 +0,0 @@ -#include <ccan/htable/htable_type.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> -#include <string.h> - -#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 deleted file mode 100644 index 3a1a939..0000000 --- a/ccan/htable/test/run-zero-hash-first-entry.c +++ /dev/null @@ -1,61 +0,0 @@ -#include <ccan/htable/htable.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> - -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 deleted file mode 100644 index 46514c7..0000000 --- a/ccan/htable/test/run.c +++ /dev/null @@ -1,212 +0,0 @@ -#include <ccan/htable/htable.h> -#include <ccan/htable/htable.c> -#include <ccan/tap/tap.h> -#include <stdbool.h> -#include <string.h> - -#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 deleted file mode 100644 index a2cad59..0000000 --- a/ccan/htable/tools/Makefile +++ /dev/null @@ -1,40 +0,0 @@ -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 deleted file mode 100644 index 8828011..0000000 --- a/ccan/htable/tools/hsearchspeed.c +++ /dev/null @@ -1,95 +0,0 @@ -/* Simple speed tests for a hash of strings using hsearch */ -#include <ccan/htable/htable_type.h> -#include <ccan/htable/htable.c> -#include <ccan/tal/str/str.h> -#include <ccan/tal/grab_file/grab_file.h> -#include <ccan/tal/tal.h> -#include <ccan/hash/hash.h> -#include <ccan/time/time.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <time.h> -#include <unistd.h> -#include <sys/time.h> -#include <search.h> - -/* 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 deleted file mode 100644 index dce3fdf..0000000 --- a/ccan/htable/tools/speed.c +++ /dev/null @@ -1,370 +0,0 @@ -/* Simple speed tests for hashtables. */ -#include <ccan/htable/htable_type.h> -#include <ccan/htable/htable.c> -#include <ccan/hash/hash.h> -#include <ccan/time/time.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -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 deleted file mode 100644 index c6ca10f..0000000 --- a/ccan/htable/tools/stringspeed.c +++ /dev/null @@ -1,240 +0,0 @@ -/* Simple speed tests for a hash of strings. */ -#include <ccan/htable/htable_type.h> -#include <ccan/htable/htable.c> -#include <ccan/tal/str/str.h> -#include <ccan/tal/grab_file/grab_file.h> -#include <ccan/tal/tal.h> -#include <ccan/hash/hash.h> -#include <ccan/time/time.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <time.h> -#include <unistd.h> -#include <sys/time.h> - -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; -} |