From: Rusty Russell Date: Mon, 26 Mar 2018 10:42:39 +0000 (+1030) Subject: intmap: add iterator-by-callback. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=1e888a93a79132f28f59319558187278badbe418;hp=a241664cddd9c1a9a66064171f871ae52598b82b intmap: add iterator-by-callback. It's significantly faster because it assumes no deletion: 10000000,critbit iteration (nsec),316 10000000,critbit callback iteration (nsec),90 ... 10000000,critbit consecutive iteration (nsec),308 10000000,critbit consecutive callback iteration (nsec),78 Signed-off-by: Rusty Russell --- diff --git a/ccan/intmap/benchmark/speed.c b/ccan/intmap/benchmark/speed.c index e74b12aa..16eb40f3 100644 --- a/ccan/intmap/benchmark/speed.c +++ b/ccan/intmap/benchmark/speed.c @@ -61,6 +61,13 @@ static bool eqfn(const struct htable_elem *elem, const uint64_t index) } 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; @@ -127,6 +134,12 @@ int main(int argc, char *argv[]) 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); @@ -157,6 +170,12 @@ int main(int argc, char *argv[]) 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); diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c index ab6ddc9d..3473ef32 100644 --- a/ccan/intmap/intmap.c +++ b/ccan/intmap/intmap.c @@ -264,3 +264,19 @@ void intmap_clear_(struct intmap *map) clear(*map); intmap_init_(map); } + +bool intmap_iterate_(const struct intmap *n, + bool (*handle)(intmap_index_t, void *, void *), + void *data, + intmap_index_t offset) +{ + /* Can only happen at root */ + if (intmap_empty_(n)) + return true; + + if (n->v) + return handle(n->u.i - offset, n->v, data); + + return intmap_iterate_(&n->u.n->child[0], handle, data, offset) + && intmap_iterate_(&n->u.n->child[1], handle, data, offset); +} diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h index 07a86351..7724ea25 100644 --- a/ccan/intmap/intmap.h +++ b/ccan/intmap/intmap.h @@ -335,6 +335,95 @@ void *intmap_last_(const struct intmap *map, intmap_index_t *indexp); tcon_cast((smap), sintmap_canary, \ sintmap_last_(sintmap_unwrap_(smap), (indexp))) +/** + * uintmap_iterate - ordered iteration over an unsigned intmap + * @umap: the typed intmap to iterate through. + * @handle: the function to call. + * @arg: the argument for the function (types should match). + * + * @handle's prototype should be: + * bool @handle(intmap_index_t index, type value, typeof(arg) arg) + * + * If @handle returns false, the iteration will stop and uintmap_iterate will + * return false, otherwise uintmap_iterate will return true. + * You should not alter the map within the @handle function! + * + * Example: + * typedef UINTMAP(int *) umap_intp; + * static bool dump_some(intmap_index_t index, int *value, int *num) + * { + * // Only dump out num nodes. + * if (*(num--) == 0) + * return false; + * printf("%lu=>%i\n", (unsigned long)index, *value); + * return true; + * } + * + * static void dump_map(const umap_intp *map) + * { + * int max = 100; + * uintmap_iterate(map, dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +#define uintmap_iterate(map, handle, arg) \ + intmap_iterate_(tcon_unwrap(map), \ + typesafe_cb_cast(bool (*)(intmap_index_t, \ + void *, void *), \ + bool (*)(intmap_index_t, \ + tcon_type((map), \ + uintmap_canary), \ + __typeof__(arg)), (handle)), \ + (arg), 0) + +/** + * sintmap_iterate - ordered iteration over a signed intmap + * @smap: the typed intmap to iterate through. + * @handle: the function to call. + * @arg: the argument for the function (types should match). + * + * @handle's prototype should be: + * bool @handle(sintmap_index_t index, type value, typeof(arg) arg) + * + * If @handle returns false, the iteration will stop and sintmap_iterate will + * return false, otherwise sintmap_iterate will return true. + * You should not alter the map within the @handle function! + * + * Example: + * typedef SINTMAP(int *) smap_intp; + * static bool dump_some(sintmap_index_t index, int *value, int *num) + * { + * // Only dump out num nodes. + * if (*(num--) == 0) + * return false; + * printf("%li=>%i\n", (long)index, *value); + * return true; + * } + * + * static void dump_map(const smap_intp *map) + * { + * int max = 100; + * sintmap_iterate(map, dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +#define sintmap_iterate(map, handle, arg) \ + intmap_iterate_(tcon_unwrap(map), \ + typesafe_cb_cast(bool (*)(intmap_index_t, \ + void *, void *), \ + bool (*)(sintmap_index_t, \ + tcon_type((map), \ + sintmap_canary), \ + __typeof__(arg)), (handle)), \ + (arg), SINTMAP_OFFSET) + +bool intmap_iterate_(const struct intmap *map, + bool (*handle)(intmap_index_t, void *, void *), + void *data, + intmap_index_t offset); + /* TODO: We could implement intmap_prefix. */ /* These make sure it really is a uintmap/sintmap */ diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c index 0f8168d7..f7e86692 100644 --- a/ccan/intmap/test/run-order.c +++ b/ccan/intmap/test/run-order.c @@ -7,6 +7,16 @@ typedef UINTMAP(unsigned int *) umap; typedef SINTMAP(int *) smap; +static bool uint_iterate_check(intmap_index_t i, unsigned int *v, int64_t *prev) +{ + if ((int64_t)i <= *prev) + return false; + if (*v != i) + return false; + *prev = i; + return true; +} + static bool check_umap(const umap *map) { /* This is a larger type than unsigned, and allows negative */ @@ -25,7 +35,22 @@ static bool check_umap(const umap *map) prev = i; last = (uintmap_last(map, &last_idx) == v); } - return last; + + if (!last) + return false; + + prev = -1; + return uintmap_iterate(map, uint_iterate_check, &prev); +} + +static bool sint_iterate_check(sintmap_index_t i, int *v, int64_t *prev) +{ + if (i <= *prev) + return false; + if (*v != i) + return false; + *prev = i; + return true; } static bool check_smap(const smap *map) @@ -45,7 +70,12 @@ static bool check_smap(const smap *map) last = (sintmap_last(map, &last_idx) == v); prev = i; } - return last; + + if (!last) + return false; + + prev = -1; + return sintmap_iterate(map, sint_iterate_check, &prev); } int main(void)