intmap: implement intmap_before()

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

diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c
index 3473ef3236159fc834aaffad1a4ba81977937ca1..341b8a92134981c9fd381149c71c7fd16d0325ef 100644 (file)
--- a/ccan/intmap/intmap.c
+++ b/ccan/intmap/intmap.c
@@ -231,6 +231,63 @@ none_left:
        return NULL;
 }
 
        return NULL;
 }
 

+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp)
+{
+       const struct intmap *n, *prev = NULL;
+       intmap_index_t index = (*indexp) - 1;
+
+       /* Special case of overflow */
+       if (index == (intmap_index_t)-1ULL)
+               goto none_left;
+
+       /* Special case of empty map */
+       if (intmap_empty_(map))
+               goto none_left;
+
+       /* Follow down, until prefix differs. */
+       n = map;
+       while (!n->v) {
+               int crit = critbit(n);
+               u8 direction;
+               intmap_index_t prefix, idx;
+
+               idx = (index >> crit);
+               direction = idx & 1;
+
+               /* Leave critbit in place: we can't shift by 64 anyway */
+               idx |= 1;
+               prefix = n->u.n->prefix_and_critbit >> crit;
+
+               /* If this entire tree is less than index, take last */
+               if (idx > prefix)
+                       return intmap_last_(n, indexp);
+               /* If this entire tree is greater than index, we're past it. */
+               else if (idx < prefix)
+                       goto try_lesser_tree;
+
+               /* Remember lesser tree for backtracking */
+               if (direction)
+                       prev = n;
+               n = &n->u.n->child[direction];
+       }
+
+       /* Found a predecessor? */
+       if (n->u.i <= index) {
+               errno = 0;
+               *indexp = n->u.i;
+               return n->v;
+       }
+
+try_lesser_tree:
+       /* If we ever took a lesser branch, go back to lesser branch */
+       if (prev)
+               return intmap_last_(&prev->u.n->child[0], indexp);
+
+none_left:
+       errno = ENOENT;
+       return NULL;
+}
+

 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
 {
        const struct intmap *n;
 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
 {
        const struct intmap *n;

diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h
index 207b7c9d2b18f993fd3a2a7692f8146391e3f864..834c969fa7c77e46dcc262b50b7b4c80b3c9b4d5 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)))
 
        tcon_cast((smap), sintmap_canary,                               \
                  sintmap_after_(sintmap_unwrap_(smap), (indexp)))
 

+/**
+ * uintmap_before - get the closest preceding index in an unsigned intmap
+ * @umap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define uintmap_before(umap, indexp)                                   \
+       tcon_cast((umap), uintmap_canary,                               \
+                 intmap_before_(uintmap_unwrap_(umap), (indexp)))
+
+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp);
+
+/**
+ * sintmap_before - get the closest preceding index in a signed intmap
+ * @smap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define sintmap_before(smap, indexp)                                   \
+       tcon_cast((smap), sintmap_canary,                               \
+                 sintmap_before_(sintmap_unwrap_(smap), (indexp)))
+

 /**
  * uintmap_last - get last value in an unsigned intmap
  * @umap: the typed intmap to iterate through.
 /**
  * uintmap_last - get last value in an unsigned intmap
  * @umap: the typed intmap to iterate through.


@@ -455,6 +481,15 @@ static inline void *sintmap_after_(const struct intmap *map,
        return ret;
 }
 
        return ret;
 }
 

+static inline void *sintmap_before_(const struct intmap *map,
+                                  sintmap_index_t *indexp)
+{
+       intmap_index_t i = SINTMAP_OFF(*indexp);
+       void *ret = intmap_before_(map, &i);
+       *indexp = SINTMAP_UNOFF(i);
+       return ret;
+}
+

 static inline void *sintmap_last_(const struct intmap *map,
                                  sintmap_index_t *indexp)
 {
 static inline void *sintmap_last_(const struct intmap *map,
                                  sintmap_index_t *indexp)
 {

diff --git a/ccan/intmap/test/run-order-smallsize.c b/ccan/intmap/test/run-order-smallsize.c
index 63c5b9c9f63514f7c58e857c2c992af11cf7c669..8121f27697fcda19ad617112070758169ce7643e 100644 (file)
--- a/ccan/intmap/test/run-order-smallsize.c
+++ b/ccan/intmap/test/run-order-smallsize.c
@@ -19,6 +19,15 @@ static bool check_umap(const umap *map)
        bool last = true;
 
        /* Must be in order, must contain value. */
        bool last = true;
 
        /* Must be in order, must contain value. */

+       prev = 256;
+       for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+               if (i >= prev)
+                       return false;
+               if (*v != i)
+                       return false;
+               prev = i;
+       }
+

        prev = -1;
        for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) {
                if (i <= prev)
        prev = -1;
        for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) {
                if (i <= prev)


@@ -40,6 +49,15 @@ static bool check_smap(const smap *map)
        bool last = true;
 
        /* Must be in order, must contain value. */
        bool last = true;
 
        /* Must be in order, must contain value. */

+       prev = 0x80000000ULL;
+       for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+               if (i >= prev)
+                       return false;
+               if (*v != i)
+                       return false;
+               prev = i;
+       }
+

        prev = -0x80000001ULL;
        for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) {
                if (i <= prev)
        prev = -0x80000001ULL;
        for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) {
                if (i <= prev)


@@ -52,7 +70,7 @@ static bool check_smap(const smap *map)
        return last;
 }
 
        return last;
 }
 

-int main(void)
+int main(int argc, char *argv[])

 {
        umap umap;
        smap smap;
 {
        umap umap;
        smap smap;


@@ -64,6 +82,9 @@ int main(void)
        uintmap_init(&umap);
        sintmap_init(&smap);
 
        uintmap_init(&umap);
        sintmap_init(&smap);
 

+       if (argc > 1)
+               srandom(atoi(argv[1]));
+

        for (i = 0; i < NUM; i++) {
                urandoms[i] = random();
                srandoms[i] = random();
        for (i = 0; i < NUM; i++) {
                urandoms[i] = random();
                srandoms[i] = random();

diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c
index f7e86692a83647bfaac224dd24495511b4880096..d945a4a86f5a6e35e5a6e5ad3c29956a9935b3fa 100644 (file)
--- a/ccan/intmap/test/run-order.c
+++ b/ccan/intmap/test/run-order.c
@@ -36,6 +36,19 @@ static bool check_umap(const umap *map)
                last = (uintmap_last(map, &last_idx) == v);
        }
 
                last = (uintmap_last(map, &last_idx) == v);
        }
 

+       if (!last)
+               return false;
+
+       prev = INT_MAX;
+       for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+               if ((int64_t)i >= prev)
+                       return false;
+               if (*v != i)
+                       return false;
+               prev = i;
+               last = (uintmap_first(map, &last_idx) == v);
+       }
+

        if (!last)
                return false;
 
        if (!last)
                return false;
 


@@ -71,6 +84,18 @@ static bool check_smap(const smap *map)
                prev = i;
        }
 
                prev = i;
        }
 

+       if (!last)
+               return false;
+
+       prev = 0x80000001ULL;
+       for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+               if (i >= prev)
+                       return false;
+               if (*v != i)
+                       return false;
+               prev = i;
+               last = (sintmap_first(map, &last_idx) == v);
+       }

        if (!last)
                return false;
 
        if (!last)
                return false;