}
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);
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 */
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 */
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)
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)