intmap: add test case which failed, extracted from real world usage.
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 26 Mar 2018 10:37:34 +0000 (21:07 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 26 Mar 2018 10:37:34 +0000 (21:07 +1030)
Because intmap_after_() would simply examine the critbits to walk the
tree, it wouldn't realize that it might be in the completely wrong tree.

In this case:

         Bit 4:
         0   1
        /     \
       /       \
  100000011  100001011

When we ask for intmap_after_(011111111) we would check the critbit, it's
a 1, so we end up on the right leaf instead of the left.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/intmap/test/run-after-fail.c [new file with mode: 0644]

diff --git a/ccan/intmap/test/run-after-fail.c b/ccan/intmap/test/run-after-fail.c
new file mode 100644 (file)
index 0000000..4105b12
--- /dev/null
@@ -0,0 +1,26 @@
+#include <ccan/intmap/intmap.h>
+#include <ccan/intmap/intmap.c>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+       UINTMAP(const char *) map;
+       u64 idx;
+
+       /* This is how many tests you plan to run */
+       plan_tests(2);
+
+       uintmap_init(&map);
+       assert(uintmap_add(&map, 0x103, "103"));
+       assert(uintmap_add(&map, 0x10b, "10b"));
+
+       uintmap_first(&map, &idx);
+       ok1(idx > 0xF);
+       idx = 0xF;
+       ok1(strcmp(uintmap_after(&map, &idx), "103") == 0);
+
+       uintmap_clear(&map);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}