From 09bb99b92546f3e8be6bb0f9218924b8491be461 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 26 Feb 2018 15:03:28 +1030 Subject: [PATCH 1/1] intmap: implement uintmap_last/sintmap_last. Signed-off-by: Rusty Russell --- ccan/intmap/intmap.c | 18 +++++++++++++ ccan/intmap/intmap.h | 36 ++++++++++++++++++++++++++ ccan/intmap/test/run-order-smallsize.c | 12 ++++++--- ccan/intmap/test/run-order.c | 12 ++++++--- ccan/intmap/test/run-signed-int.c | 5 +++- ccan/intmap/test/run.c | 15 ++++++++++- 6 files changed, 88 insertions(+), 10 deletions(-) diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c index bfaa2fe9..447f8eec 100644 --- a/ccan/intmap/intmap.c +++ b/ccan/intmap/intmap.c @@ -197,6 +197,24 @@ void *intmap_after_(const struct intmap *map, intmap_index_t *indexp) return intmap_first_(&prev->u.n->child[1], indexp); } +void *intmap_last_(const struct intmap *map, intmap_index_t *indexp) +{ + const struct intmap *n; + + if (intmap_empty_(map)) { + errno = ENOENT; + return NULL; + } + + n = map; + /* Anything with NULL value is a node. */ + while (!n->v) + n = &n->u.n->child[1]; + errno = 0; + *indexp = n->u.i; + return n->v; +} + static void clear(struct intmap n) { if (!n.v) { diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h index be3dbc09..07a86351 100644 --- a/ccan/intmap/intmap.h +++ b/ccan/intmap/intmap.h @@ -309,6 +309,32 @@ void *intmap_after_(const struct intmap *map, intmap_index_t *indexp); tcon_cast((smap), sintmap_canary, \ sintmap_after_(sintmap_unwrap_(smap), (indexp))) +/** + * uintmap_last - get last value in an unsigned intmap + * @umap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. + * + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the highest entry. + */ +#define uintmap_last(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_last_(uintmap_unwrap_(umap), (indexp))) + +void *intmap_last_(const struct intmap *map, intmap_index_t *indexp); + +/** + * sintmap_last - get last value in a signed intmap + * @smap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. + * + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the highest entry. + */ +#define sintmap_last(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_last_(sintmap_unwrap_(smap), (indexp))) + /* TODO: We could implement intmap_prefix. */ /* These make sure it really is a uintmap/sintmap */ @@ -339,4 +365,14 @@ static inline void *sintmap_after_(const struct intmap *map, *indexp = SINTMAP_UNOFF(i); return ret; } + +static inline void *sintmap_last_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i; + void *ret = intmap_last_(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 3633180e..63c5b9c9 100644 --- a/ccan/intmap/test/run-order-smallsize.c +++ b/ccan/intmap/test/run-order-smallsize.c @@ -14,8 +14,9 @@ static bool check_umap(const umap *map) { /* This is a larger type than unsigned, and allows negative */ int64_t prev; - intmap_index_t i; + intmap_index_t i, last_idx; uint8_t *v; + bool last = true; /* Must be in order, must contain value. */ prev = -1; @@ -25,16 +26,18 @@ static bool check_umap(const umap *map) if (*v != i) return false; prev = i; + last = (uintmap_last(map, &last_idx) == v); } - return true; + return last; } static bool check_smap(const smap *map) { /* This is a larger type than int, and allows negative */ int64_t prev; - sintmap_index_t i; + sintmap_index_t i, last_idx; int8_t *v; + bool last = true; /* Must be in order, must contain value. */ prev = -0x80000001ULL; @@ -44,8 +47,9 @@ static bool check_smap(const smap *map) if (*v != i) return false; prev = i; + last = (sintmap_last(map, &last_idx) == v); } - return true; + return last; } int main(void) diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c index 1b2fdffd..0f8168d7 100644 --- a/ccan/intmap/test/run-order.c +++ b/ccan/intmap/test/run-order.c @@ -11,8 +11,9 @@ static bool check_umap(const umap *map) { /* This is a larger type than unsigned, and allows negative */ int64_t prev; - uint64_t i; + uint64_t i, last_idx; unsigned int *v; + bool last = true; /* Must be in order, must contain value. */ prev = -1; @@ -22,15 +23,17 @@ static bool check_umap(const umap *map) if (*v != i) return false; prev = i; + last = (uintmap_last(map, &last_idx) == v); } - return true; + return last; } static bool check_smap(const smap *map) { /* This is a larger type than int, and allows negative */ - int64_t prev, i; + int64_t prev, i, last_idx; int *v; + bool last = true; /* Must be in order, must contain value. */ prev = -0x80000001ULL; @@ -39,9 +42,10 @@ static bool check_smap(const smap *map) return false; if (*v != i) return false; + last = (sintmap_last(map, &last_idx) == v); prev = i; } - return true; + return last; } int main(void) diff --git a/ccan/intmap/test/run-signed-int.c b/ccan/intmap/test/run-signed-int.c index 7c86a940..14e5a2e5 100644 --- a/ccan/intmap/test/run-signed-int.c +++ b/ccan/intmap/test/run-signed-int.c @@ -9,13 +9,14 @@ int main(void) int64_t s; /* This is how many tests you plan to run */ - plan_tests(35); + plan_tests(38); sintmap_init(&map); /* Test boundaries. */ ok1(!sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL)); ok1(!sintmap_get(&map, -0x8000000000000000LL)); ok1(sintmap_first(&map, &s) == NULL); + ok1(sintmap_last(&map, &s) == NULL); ok1(errno == ENOENT); s = 0x7FFFFFFFFFFFFFFFLL; ok1(sintmap_after(&map, &s) == NULL); @@ -29,12 +30,14 @@ int main(void) ok1(sintmap_add(&map, 0x7FFFFFFFFFFFFFFFLL, first)); ok1(sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL) == first); ok1(sintmap_first(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_last(&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, &s) == second && s == -0x8000000000000000LL); ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); + ok1(sintmap_last(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); ok1(errno == 0); s = 0x7FFFFFFFFFFFFFFELL; ok1(sintmap_after(&map, &s) == first && s == 0x7FFFFFFFFFFFFFFFLL); diff --git a/ccan/intmap/test/run.c b/ccan/intmap/test/run.c index 41efc442..86f09af4 100644 --- a/ccan/intmap/test/run.c +++ b/ccan/intmap/test/run.c @@ -7,9 +7,10 @@ int main(void) UINTMAP(char *) map; const char val[] = "there"; const char none[] = ""; + uint64_t idx; /* This is how many tests you plan to run */ - plan_tests(28); + plan_tests(40); uintmap_init(&map); @@ -21,11 +22,19 @@ int main(void) ok1(errno == ENOENT); ok1(!uintmap_del(&map, 0)); ok1(errno == ENOENT); + ok1(!uintmap_first(&map, &idx)); + ok1(errno == ENOENT); + ok1(!uintmap_last(&map, &idx)); + ok1(errno == ENOENT); ok1(uintmap_add(&map, 1, val)); ok1(uintmap_get(&map, 1) == val); ok1(!uintmap_get(&map, 0)); ok1(errno == ENOENT); + ok1(uintmap_first(&map, &idx) == val); + ok1(idx == 1); + ok1(uintmap_last(&map, &idx) == val); + ok1(idx == 1); /* Add a duplicate should fail. */ ok1(!uintmap_add(&map, 1, val)); @@ -43,6 +52,10 @@ int main(void) ok1(uintmap_add(&map, 1, val)); ok1(uintmap_get(&map, 1) == val); ok1(uintmap_get(&map, 0) == none); + ok1(uintmap_first(&map, &idx) == none); + ok1(idx == 0); + ok1(uintmap_last(&map, &idx) == val); + ok1(idx == 1); ok1(!uintmap_del(&map, 2)); ok1(uintmap_del(&map, 0) == none); ok1(uintmap_get(&map, 1) == val); -- 2.39.2