struct node {
/* These point to strings or nodes. */
struct intmap child[2];
- /* The bit where these children differ (0 == lsb) */
- uint8_t bit_num;
+ /* Encoding both prefix and critbit: 1 is appended to prefix. */
+ intmap_index_t prefix_and_critbit;
};
static void update_span(const void *p, size_t s, uintptr_t *min, uintptr_t *max)
}
HTABLE_DEFINE_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash);
+static bool check_val(intmap_index_t i, uint64_t *v, uint64_t *expected)
+{
+ if (v != expected)
+ abort();
+ return true;
+}
+
int main(int argc, char *argv[])
{
uint64_t i, total = 0, seed, *v;
printf("%zu,critbit iteration (nsec),%"PRIu64"\n", max,
time_to_nsec(time_divide(time_between(end, start), max)));
+ start = time_now();
+ uintmap_iterate(&map, check_val, &i);
+ end = time_now();
+ printf("%zu,critbit callback iteration (nsec),%"PRIu64"\n", max,
+ time_to_nsec(time_divide(time_between(end, start), max)));
+
span_min = -1ULL;
span_max = 0;
getspan(uintmap_unwrap_(&map), &span_min, &span_max);
printf("%zu,critbit consecutive iteration (nsec),%"PRIu64"\n", max,
time_to_nsec(time_divide(time_between(end, start), max)));
+ start = time_now();
+ uintmap_iterate(&map, check_val, &i);
+ end = time_now();
+ printf("%zu,critbit consecutive callback iteration (nsec),%"PRIu64"\n", max,
+ time_to_nsec(time_divide(time_between(end, start), max)));
+
sipseed.u.u64[0] = isaac64_next_uint64(&isaac);
sipseed.u.u64[1] = isaac64_next_uint64(&isaac);