intmap: implement uintmap_last/sintmap_last.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c
index bfaa2fe9d90bc50a3e079f9990a36928d5b97693..447f8eec40bec49ceab42e8ddf88f412ac8aebb2 100644 (file)
--- 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 be3dbc0936b40f9133b4caad30b4a49c62c1bd42..07a86351597dadb6f367b570ee132eab10733d33 100644 (file)
--- 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 3633180ea93880b337016582277aaf8af2f8ab85..63c5b9c9f63514f7c58e857c2c992af11cf7c669 100644 (file)
--- 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 1b2fdffdfadcb68eeadebe547ae5c9510bebcc11..0f8168d7fde54b3a0c3ec64cf790a162dadb148d 100644 (file)
--- 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 7c86a940c8538ef9a28e66099ed4e1fe57c473cb..14e5a2e568515b27afd82c9c91647120b57dd7d7 100644 (file)
--- 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 41efc442d88aaade56eb3996bc8a85ea60fe9235..86f09af47e0f4f2ced43d782b79c185d174bbb4d 100644 (file)
--- 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);