intmap: clean up iterators.
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 13 Jan 2017 02:55:14 +0000 (13:25 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 13 Jan 2017 02:55:14 +0000 (13:25 +1030)
By returning the value, we have a nice sentinal and we save a second lookup
if they want it.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/intmap/intmap.c
ccan/intmap/intmap.h
ccan/intmap/test/run-order-smallsize.c
ccan/intmap/test/run-order.c
ccan/intmap/test/run-signed-int.c

index d27b645695c43d4c52d66ab37358f92f624c5d06..bfaa2fe9d90bc50a3e079f9990a36928d5b97693 100644 (file)
@@ -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)
index f06f02d0ee599c9045c496ba7ad979d83c8b0cf0..be3dbc0936b40f9133b4caad30b4a49c62c1bd42 100644 (file)
 /* 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 */
index e9164413bb8d9561e9a1f9c622ca314009246160..3633180ea93880b337016582277aaf8af2f8ab85 100644 (file)
@@ -1,4 +1,5 @@
 #define intmap_index_t uint8_t
+#define sintmap_index_t int8_t
 
 #include <ccan/intmap/intmap.c>
 #include <ccan/tap/tap.h>
@@ -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;
        }
index c44d2ba3b3bd02b50d3feb04b7e6a39a5ccf4f4f..1b2fdffdfadcb68eeadebe547ae5c9510bebcc11 100644 (file)
@@ -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;
        }
index 8e95e8f4f29f1ff78ee31c2a0409b98bc4450af6..7c86a940c8538ef9a28e66099ed4e1fe57c473cb 100644 (file)
@@ -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));