From b796c0318151ce34b56d2973f567335fbf20aae7 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 13 Jan 2017 13:25:14 +1030 Subject: [PATCH 1/1] intmap: clean up iterators. By returning the value, we have a nice sentinal and we save a second lookup if they want it. Signed-off-by: Rusty Russell --- ccan/intmap/intmap.c | 26 +++++---- ccan/intmap/intmap.h | 80 ++++++++++++++++---------- ccan/intmap/test/run-order-smallsize.c | 21 +++---- ccan/intmap/test/run-order.c | 19 +++--- ccan/intmap/test/run-signed-int.c | 32 +++++++---- 5 files changed, 106 insertions(+), 72 deletions(-) diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c index d27b6456..bfaa2fe9 100644 --- a/ccan/intmap/intmap.c +++ b/ccan/intmap/intmap.c @@ -142,13 +142,13 @@ void *intmap_del_(struct intmap *map, intmap_index_t index) return value; } -intmap_index_t intmap_first_(const struct intmap *map) +void *intmap_first_(const struct intmap *map, intmap_index_t *indexp) { const struct intmap *n; if (intmap_empty_(map)) { errno = ENOENT; - return UINTMAP_NONE; + return NULL; } n = map; @@ -156,43 +156,45 @@ intmap_index_t intmap_first_(const struct intmap *map) while (!n->v) n = &n->u.n->child[0]; errno = 0; - return n->u.i; + *indexp = n->u.i; + return n->v; } -intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t index) +void *intmap_after_(const struct intmap *map, intmap_index_t *indexp) { const struct intmap *n, *prev = NULL; - /* Special case of unincrementable value, or empty map */ - if (index == UINTMAP_NONE || intmap_empty_(map)) { + /* Special case of empty map */ + if (intmap_empty_(map)) { errno = ENOENT; - return UINTMAP_NONE; + return NULL; } /* Follow down, track the last place where we could have set a bit * instead of clearing it: this is the higher alternative tree. */ n = map; while (!n->v) { - u8 direction = (index >> n->u.n->bit_num) & 1; + u8 direction = (*indexp >> n->u.n->bit_num) & 1; if (!direction) prev = n; n = &n->u.n->child[direction]; } /* Found a successor? */ - if (n->u.i > index) { + if (n->u.i > *indexp) { errno = 0; - return n->u.i; + *indexp = n->u.i; + return n->v; } /* Nowhere to go back up to? */ if (!prev) { errno = ENOENT; - return UINTMAP_NONE; + return NULL; } /* Get first one from that other branch. */ - return intmap_first_(&prev->u.n->child[1]); + return intmap_first_(&prev->u.n->child[1], indexp); } static void clear(struct intmap n) diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h index f06f02d0..be3dbc09 100644 --- a/ccan/intmap/intmap.h +++ b/ccan/intmap/intmap.h @@ -11,12 +11,9 @@ /* Must be an unsigned type. */ #ifndef intmap_index_t #define intmap_index_t uint64_t +#define sintmap_index_t int64_t #endif -/* Maximum possible values of each type */ -#define UINTMAP_NONE ((intmap_index_t)-1) -#define SINTMAP_NONE (((intmap_index_t)1 << (sizeof(intmap_index_t)*8))-1) - /** * struct intmap - representation of an integer map * @@ -261,52 +258,58 @@ void *intmap_del_(struct intmap *map, intmap_index_t index); void intmap_clear_(struct intmap *map); /** - * uintmap_first - get first index in an unsigned intmap + * uintmap_first - get first value in an unsigned intmap * @umap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. * - * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty. - * Otherwise errno is set to 0. + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the lowest entry. */ -#define uintmap_first(umap) \ - intmap_first_(uintmap_unwrap_(umap)) +#define uintmap_first(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_first_(uintmap_unwrap_(umap), (indexp))) + +void *intmap_first_(const struct intmap *map, intmap_index_t *indexp); /** - * sintmap_first - get first index in a signed intmap + * sintmap_first - get first value in a signed intmap * @smap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. * - * Returns SINTMAP_NONE and sets errno to ENOENT if it's - * empty. Otherwise errno is set to 0. + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the lowest entry. */ -#define sintmap_first(smap) \ - SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap))) - -intmap_index_t intmap_first_(const struct intmap *map); +#define sintmap_first(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_first_(sintmap_unwrap_(smap), (indexp))) /** * uintmap_after - get the closest following index in an unsigned intmap * @umap: the typed intmap to iterate through. - * @i: the preceeding index (may not exist) + * @indexp: the preceeding index (may not exist) * - * Returns UINTMAP_NONE and sets errno to ENOENT if there are no - * others. Otherwise errno is set to 0. + * Returns NULL if the there is no entry > @indexp, otherwise + * populates *@indexp and returns the lowest entry > @indexp. */ -#define uintmap_after(umap, i) \ - intmap_after_(uintmap_unwrap_(umap), (i)) +#define uintmap_after(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_after_(uintmap_unwrap_(umap), (indexp))) + +void *intmap_after_(const struct intmap *map, intmap_index_t *indexp); /** * sintmap_after - get the closest following index in a signed intmap * @smap: the typed intmap to iterate through. - * @i: the preceeding index. + * @indexp: the preceeding index (may not exist) * - * Returns SINTMAP_NONE and sets errno to ENOENT if there are no - * others. Otherwise errno is set to 0. + * Returns NULL if the there is no entry > @indexp, otherwise + * populates *@indexp and returns the lowest entry > @indexp. */ -#define sintmap_after(smap, i) \ - SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i)))) - -intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i); +#define sintmap_after(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_after_(sintmap_unwrap_(smap), (indexp))) -/* TODO: We could implement intmap_prefix, intmap_iterate... */ +/* TODO: We could implement intmap_prefix. */ /* These make sure it really is a uintmap/sintmap */ #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary)) @@ -317,4 +320,23 @@ intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i); #define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET) #define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET) +/* Due to multi-evaluation, these can't be macros */ +static inline void *sintmap_first_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i; + void *ret = intmap_first_(map, &i); + *indexp = SINTMAP_UNOFF(i); + return ret; + +} + +static inline void *sintmap_after_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i = SINTMAP_OFF(*indexp); + void *ret = intmap_after_(map, &i); + *indexp = SINTMAP_UNOFF(i); + return ret; +} #endif /* CCAN_INTMAP_H */ diff --git a/ccan/intmap/test/run-order-smallsize.c b/ccan/intmap/test/run-order-smallsize.c index e9164413..3633180e 100644 --- a/ccan/intmap/test/run-order-smallsize.c +++ b/ccan/intmap/test/run-order-smallsize.c @@ -1,4 +1,5 @@ #define intmap_index_t uint8_t +#define sintmap_index_t int8_t #include #include @@ -12,16 +13,16 @@ typedef SINTMAP(int8_t *) smap; static bool check_umap(const umap *map) { /* This is a larger type than unsigned, and allows negative */ - int64_t i, prev; + int64_t prev; + intmap_index_t i; + uint8_t *v; /* Must be in order, must contain value. */ prev = -1; - for (i = uintmap_first(map); - i != UINTMAP_NONE || errno == 0; - i = uintmap_after(map, i)) { + for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) { if (i <= prev) return false; - if (*(uint8_t *)uintmap_get(map, i) != i) + if (*v != i) return false; prev = i; } @@ -31,16 +32,16 @@ static bool check_umap(const umap *map) static bool check_smap(const smap *map) { /* This is a larger type than int, and allows negative */ - int64_t i, prev; + int64_t prev; + sintmap_index_t i; + int8_t *v; /* Must be in order, must contain value. */ prev = -0x80000001ULL; - for (i = sintmap_first(map); - i != 127 || errno == 0; - i = sintmap_after(map, i)) { + for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) { if (i <= prev) return false; - if (*(int8_t *)sintmap_get(map, i) != i) + if (*v != i) return false; prev = i; } diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c index c44d2ba3..1b2fdffd 100644 --- a/ccan/intmap/test/run-order.c +++ b/ccan/intmap/test/run-order.c @@ -10,14 +10,16 @@ typedef SINTMAP(int *) smap; static bool check_umap(const umap *map) { /* This is a larger type than unsigned, and allows negative */ - int64_t i, prev; + int64_t prev; + uint64_t i; + unsigned int *v; /* Must be in order, must contain value. */ prev = -1; - for (i = uintmap_first(map); i != -1ULL; i = uintmap_after(map, i)) { - if (i <= prev) + for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) { + if ((int64_t)i <= prev) return false; - if (*(unsigned int *)uintmap_get(map, i) != i) + if (*v != i) return false; prev = i; } @@ -27,16 +29,15 @@ static bool check_umap(const umap *map) static bool check_smap(const smap *map) { /* This is a larger type than int, and allows negative */ - int64_t i, prev; + int64_t prev, i; + int *v; /* Must be in order, must contain value. */ prev = -0x80000001ULL; - for (i = sintmap_first(map); - i != 0x7FFFFFFFFFFFFFFFLL; - i = sintmap_after(map, i)) { + for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) { if (i <= prev) return false; - if (*(int *)sintmap_get(map, i) != i) + if (*v != i) return false; prev = i; } diff --git a/ccan/intmap/test/run-signed-int.c b/ccan/intmap/test/run-signed-int.c index 8e95e8f4..7c86a940 100644 --- a/ccan/intmap/test/run-signed-int.c +++ b/ccan/intmap/test/run-signed-int.c @@ -6,6 +6,7 @@ int main(void) { SINTMAP(const char *) map; const char *first = "first", *second = "second"; + int64_t s; /* This is how many tests you plan to run */ plan_tests(35); @@ -14,36 +15,43 @@ int main(void) /* Test boundaries. */ ok1(!sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL)); ok1(!sintmap_get(&map, -0x8000000000000000LL)); - ok1(sintmap_first(&map) == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_first(&map, &s) == NULL); ok1(errno == ENOENT); - ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL); + s = 0x7FFFFFFFFFFFFFFFLL; + ok1(sintmap_after(&map, &s) == NULL); ok1(errno == ENOENT); - ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL); + s = -0x8000000000000000LL; + ok1(sintmap_after(&map, &s) == NULL); ok1(errno == ENOENT); - ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFELL) == 0x7FFFFFFFFFFFFFFFLL); + s = 0x7FFFFFFFFFFFFFFELL; + ok1(sintmap_after(&map, &s) == NULL); ok1(errno == ENOENT); ok1(sintmap_add(&map, 0x7FFFFFFFFFFFFFFFLL, first)); ok1(sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL) == first); - ok1(sintmap_first(&map) == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_first(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); ok1(sintmap_add(&map, -0x8000000000000000LL, second)); ok1(sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL) == first); ok1(sintmap_get(&map, -0x8000000000000000LL) == second); - ok1(sintmap_first(&map) == -0x8000000000000000LL); - ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_first(&map, &s) == second && s == -0x8000000000000000LL); + ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); - ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFELL) == 0x7FFFFFFFFFFFFFFFLL); + s = 0x7FFFFFFFFFFFFFFELL; + ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); - ok1(sintmap_after(&map, -0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL); + s = -0x7FFFFFFFFFFFFFFFLL; + ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); - ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_after(&map, &s) == NULL); ok1(errno == ENOENT); ok1(sintmap_del(&map, 0x7FFFFFFFFFFFFFFFLL) == first); - ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL); + s = -0x8000000000000000LL; + ok1(sintmap_after(&map, &s) == NULL); ok1(errno == ENOENT); ok1(sintmap_add(&map, 0x7FFFFFFFFFFFFFFFLL, first)); ok1(sintmap_del(&map, 0x8000000000000000LL) == second); - ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL); + s = -0x8000000000000000LL; + ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); ok1(sintmap_del(&map, 0x7FFFFFFFFFFFFFFFLL) == first); ok1(sintmap_empty(&map)); -- 2.39.2