1 /* Density measurements for hashtables. */
2 #include <ccan/err/err.h>
3 #include <ccan/htable/htable_type.h>
4 #include <ccan/htable/htable.c>
5 #include <ccan/hash/hash.h>
6 #include <ccan/ptrint/ptrint.h>
7 #include <ccan/time/time.h>
13 /* We don't actually hash objects: we put values in as if they were ptrs */
14 static uintptr_t key(const ptrint_t *obj)
19 static size_t hash_uintptr(uintptr_t key)
21 return hashl(&key, 1, 0);
24 static bool cmp(const ptrint_t *p, uintptr_t k)
29 HTABLE_DEFINE_TYPE(ptrint_t, key, hash_uintptr, cmp, htable_ptrint);
31 /* Nanoseconds per operation */
32 static size_t normalize(const struct timeabs *start,
33 const struct timeabs *stop,
36 return time_to_nsec(time_divide(time_between(*stop, *start), num));
39 static size_t average_run(const struct htable_ptrint *ht, size_t count, size_t *longest)
44 for (i = 0; i < count; i++) {
45 size_t h = hash_uintptr(i + 2);
48 while (get_raw_ptr(&ht->raw, ht->raw.table[h % ((size_t)1 << ht->raw.bits)]) != int2ptr(i + 2)) {
59 int main(int argc, char *argv[])
63 struct timeabs start, stop;
64 struct htable_ptrint ht;
67 errx(1, "Usage: density <power-of-2-tablesize>");
71 printf("Total buckets, buckets used, nanoseconds search time per element, avg run, longest run\n");
72 for (i = 1; i <= 99; i++) {
74 struct htable_ptrint_iter it;
75 size_t count, avg_run, longest_run;
78 htable_ptrint_init_sized(&ht, num * 3 / 4);
79 assert((1 << ht.raw.bits) == num);
81 /* Can't put 0 or 1 in the hash table: multiply by a prime. */
82 for (j = 0; j < num * i / 100; j++) {
83 htable_ptrint_add(&ht, int2ptr(j + 2));
84 /* stop it from doubling! */
85 ht.raw.elems = num / 2;
87 /* Must not have changed! */
88 assert((1 << ht.raw.bits) == num);
92 for (p = htable_ptrint_first(&ht, &it); p; p = htable_ptrint_next(&ht, &it))
94 assert(count == num * i / 100);
96 for (j = 0; j < count; j++)
97 assert(htable_ptrint_get(&ht, j + 2));
99 avg_run = average_run(&ht, count, &longest_run);
100 printf("%zu,%zu,%zu,%zu,%zu\n",
101 num, count, normalize(&start, &stop, count), avg_run, longest_run);
103 htable_ptrint_clear(&ht);