intmap: new module.

Critbit tree to map ints/uints to pointers.

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

diff --git a/ccan/intmap/LICENSE b/ccan/intmap/LICENSE
new file mode 120000 (symlink)
index 0000000..b7951da
--- /dev/null
+++ b/ccan/intmap/LICENSE
@@ -0,0 +1 @@
+../../licenses/CC0
\ No newline at end of file

diff --git a/ccan/intmap/_info b/ccan/intmap/_info
new file mode 100644 (file)
index 0000000..d9ba462
--- /dev/null
+++ b/ccan/intmap/_info
@@ -0,0 +1,34 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * intmap - ordered map integers to various types
+ *
+ * This code an ordered map of strings to values
+ *
+ * This code implements an ordered map of strings as a critbit tree. See:
+ *
+ *  http://cr.yp.to/critbit.html
+ *  http://github.com/agl/critbit (which this code is based on)
+ *
+ * License: CC0
+ * Author: Rusty Russell <rusty@rustcorp.com.au>
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/ilog\n"
+                      "ccan/short_types\n"
+                      "ccan/str\n"
+                      "ccan/tcon\n"
+                      "ccan/typesafe_cb\n");
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c
new file mode 100644 (file)
index 0000000..d27b645
--- /dev/null
+++ b/ccan/intmap/intmap.c
@@ -0,0 +1,212 @@
+/* CC0 license (public domain) - see LICENSE file for details */
+/* This code is based on ccan/strmap.c. */
+#include <ccan/intmap/intmap.h>
+#include <ccan/short_types/short_types.h>
+#include <ccan/str/str.h>
+#include <ccan/ilog/ilog.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <errno.h>
+
+struct node {
+       /* These point to strings or nodes. */
+       struct intmap child[2];
+       /* The bit where these children differ (0 == lsb) */
+       u8 bit_num;
+};
+
+/* Closest member to this in a non-empty map. */
+static struct intmap *closest(struct intmap *n, intmap_index_t index)
+{
+       /* Anything with NULL value is a node. */
+       while (!n->v) {
+               u8 direction = (index >> n->u.n->bit_num) & 1;
+               n = &n->u.n->child[direction];
+       }
+       return n;
+}
+
+void *intmap_get_(const struct intmap *map, intmap_index_t index)
+{
+       struct intmap *n;
+
+       /* Not empty map? */
+       if (!intmap_empty_(map)) {
+               n = closest((struct intmap *)map, index);
+               if (index == n->u.i)
+                       return n->v;
+       }
+       errno = ENOENT;
+       return NULL;
+}
+
+bool intmap_add_(struct intmap *map, intmap_index_t index, const void *value)
+{
+       struct intmap *n;
+       struct node *newn;
+       u8 bit_num, new_dir;
+
+       assert(value);
+
+       /* Empty map? */
+       if (intmap_empty_(map)) {
+               map->u.i = index;
+               map->v = (void *)value;
+               return true;
+       }
+
+       /* Find closest existing member. */
+       n = closest(map, index);
+
+       /* Find highest bit where they differ. */
+       bit_num = ilog64(n->u.i ^ index);
+       if (bit_num == 0) {
+               errno = EEXIST;
+               return false;
+       }
+       bit_num--;
+
+       assert(bit_num < CHAR_BIT*sizeof(index));
+
+       /* Which direction do we go at this bit? */
+       new_dir = (index >> bit_num) & 1;
+
+       /* Allocate new node. */
+       newn = malloc(sizeof(*newn));
+       if (!newn) {
+               errno = ENOMEM;
+               return false;
+       }
+       newn->bit_num = bit_num;
+       newn->child[new_dir].v = (void *)value;
+       newn->child[new_dir].u.i = index;
+
+       /* Find where to insert: not closest, but first which differs! */
+       n = map;
+       while (!n->v) {
+               u8 direction;
+
+               /* Subtle: bit numbers are "backwards" for comparison */
+               if (n->u.n->bit_num < bit_num)
+                       break;
+
+               direction = (index >> n->u.n->bit_num) & 1;
+               n = &n->u.n->child[direction];
+       }
+
+       newn->child[!new_dir] = *n;
+       n->u.n = newn;
+       n->v = NULL;
+       return true;
+}
+
+void *intmap_del_(struct intmap *map, intmap_index_t index)
+{
+       struct intmap *parent = NULL, *n;
+       u8 direction;
+       void *value;
+
+       /* Empty map? */
+       if (intmap_empty_(map)) {
+               errno = ENOENT;
+               return NULL;
+       }
+
+       /* Find closest, but keep track of parent. */
+       n = map;
+       /* Anything with NULL value is a node. */
+       while (!n->v) {
+               parent = n;
+               direction = (index >> n->u.n->bit_num) & 1;
+               n = &n->u.n->child[direction];
+       }
+
+       /* Did we find it? */
+       if (index != n->u.i) {
+               errno = ENOENT;
+               return NULL;
+       }
+
+       value = n->v;
+
+       if (!parent) {
+               /* We deleted last node. */
+               intmap_init_(map);
+       } else {
+               struct node *old = parent->u.n;
+               /* Raise other node to parent. */
+               *parent = old->child[!direction];
+               free(old);
+       }
+       errno = 0;
+       return value;
+}
+
+intmap_index_t intmap_first_(const struct intmap *map)
+{
+       const struct intmap *n;
+
+       if (intmap_empty_(map)) {
+               errno = ENOENT;
+               return UINTMAP_NONE;
+       }
+       
+       n = map;
+       /* Anything with NULL value is a node. */
+       while (!n->v)
+               n = &n->u.n->child[0];
+       errno = 0;
+       return n->u.i;
+}
+               
+intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t index)
+{
+       const struct intmap *n, *prev = NULL;
+
+       /* Special case of unincrementable value, or empty map */
+       if (index == UINTMAP_NONE || intmap_empty_(map)) {
+               errno = ENOENT;
+               return UINTMAP_NONE;
+       }
+
+       /* 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;
+               if (!direction)
+                       prev = n;
+               n = &n->u.n->child[direction];
+       }
+
+       /* Found a successor? */
+       if (n->u.i > index) {
+               errno = 0;
+               return n->u.i;
+       }
+
+       /* Nowhere to go back up to? */
+       if (!prev) {
+               errno = ENOENT;
+               return UINTMAP_NONE;
+       }
+
+       /* Get first one from that other branch. */
+       return intmap_first_(&prev->u.n->child[1]);
+}
+
+static void clear(struct intmap n)
+{
+       if (!n.v) {
+               clear(n.u.n->child[0]);
+               clear(n.u.n->child[1]);
+               free(n.u.n);
+       }
+}
+
+void intmap_clear_(struct intmap *map)
+{
+       if (!intmap_empty_(map))
+               clear(*map);
+       intmap_init_(map);
+}

diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h
new file mode 100644 (file)
index 0000000..f06f02d
--- /dev/null
+++ b/ccan/intmap/intmap.h
@@ -0,0 +1,320 @@
+/* CC0 license (public domain) - see LICENSE file for details */
+#ifndef CCAN_INTMAP_H
+#define CCAN_INTMAP_H
+#include "config.h"
+#include <ccan/tcon/tcon.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+/* Must be an unsigned type. */
+#ifndef intmap_index_t
+#define intmap_index_t uint64_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
+ *
+ * It's exposed here to allow you to embed it and so we can inline the
+ * trivial functions.
+ */
+struct intmap {
+       union {
+               struct node *n;
+               intmap_index_t i;
+       } u;
+       void *v;
+};
+
+/**
+ * UINTMAP - declare a type-specific intmap (for unsigned integers)
+ * @membertype: type for this map's values, or void * for any pointer.
+ *
+ * You use this to create your own typed intmap for a particular
+ * (non-NULL) pointer type.
+ *
+ * Example:
+ *     UINTMAP(int *) uint_intmap;
+ *     uintmap_init(&uint_intmap);
+ */
+#define UINTMAP(membertype)                                    \
+       TCON_WRAP(struct intmap, membertype uintmap_canary)
+
+/**
+ * SINTMAP - declare a type-specific intmap (for signed integers)
+ * @membertype: type for this map's values, or void * for any pointer.
+ *
+ * You use this to create your own typed intmap for a particular type.
+ * You can use an integer type as membertype, *but* remember you can't
+ * use "0" as a value!
+ *
+ * This is different from UINTMAP because we want it to sort into
+ * least (most negative) to largest order.
+ *
+ * Example:
+ *     SINTMAP(int *) sint_intmap;
+ *     sintmap_init(&sint_intmap);
+ */
+#define SINTMAP(membertype)                                    \
+       TCON_WRAP(struct intmap, membertype sintmap_canary)
+
+/**
+ * uintmap_init - initialize an unsigned integer map (empty)
+ * @umap: the typed intmap to initialize.
+ *
+ * For completeness; if you've arranged for it to be NULL already you don't
+ * need this.
+ *
+ * Example:
+ *     UINTMAP(int *) uint_intmap;
+ *
+ *     uintmap_init(&uint_intmap);
+ */
+#define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
+
+/**
+ * sintmap_init - initialize a signed integer map (empty)
+ * @smap: the typed intmap to initialize.
+ *
+ * For completeness; if you've arranged for it to be NULL already you don't
+ * need this.
+ *
+ * Example:
+ *     SINTMAP(int *) sint_intmap;
+ *
+ *     sintmap_init(&sint_intmap);
+ */
+#define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
+
+static inline void intmap_init_(struct intmap *map)
+{
+       map->u.n = NULL;
+       map->v = NULL;
+}
+
+/**
+ * uintmap_empty - is this unsigned integer map empty?
+ * @umap: the typed intmap to check.
+ *
+ * Example:
+ *     if (!uintmap_empty(&uint_intmap))
+ *             abort();
+ */
+#define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
+
+/**
+ * sintmap_empty - is this signed integer map empty?
+ * @smap: the typed intmap to check.
+ *
+ * Example:
+ *     if (!sintmap_empty(&sint_intmap))
+ *             abort();
+ */
+#define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
+
+static inline bool intmap_empty_(const struct intmap *map)
+{
+       return map->v == NULL && map->u.n == NULL;
+}
+
+/**
+ * uintmap_get - get a value from an unsigned integer map
+ * @umap: the typed intmap to search.
+ * @index: the unsigned index to search for.
+ *
+ * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
+ *
+ * Example:
+ *     int *val = uintmap_get(&uint_intmap, 100);
+ *     if (val)
+ *             printf("100 => %i\n", *val);
+ */
+#define uintmap_get(umap, index)                                       \
+       tcon_cast((umap), uintmap_canary,                               \
+                     intmap_get_(uintmap_unwrap_(umap), (index)))
+
+/**
+ * sintmap_get - get a value from a signed integer map
+ * @smap: the typed intmap to search.
+ * @index: the signed index to search for.
+ *
+ * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
+ *
+ * Example:
+ *     int *val2 = sintmap_get(&sint_intmap, -100);
+ *     if (val2)
+ *             printf("-100 => %i\n", *val2);
+ */
+#define sintmap_get(smap, index)                                       \
+       tcon_cast((smap), sintmap_canary,                               \
+                 intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
+
+void *intmap_get_(const struct intmap *map, intmap_index_t index);
+
+/**
+ * uintmap_add - place a member in an unsigned integer map.
+ * @umap: the typed intmap to add to.
+ * @index: the unsigned index to place in the map.
+ * @value: the (non-NULL) value.
+ *
+ * This returns false if we run out of memory (errno = ENOMEM), or
+ * (more normally) if that index already appears in the map (EEXIST).
+ *
+ * Note that the value is not copied, just the pointer.
+ *
+ * Example:
+ *     val = malloc(sizeof *val);
+ *     *val = 17;
+ *     if (!uintmap_add(&uint_intmap, 100, val))
+ *             printf("100 was already in the map\n");
+ */
+#define uintmap_add(umap, index, value)                                        \
+       intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary,  \
+                                              (value))),               \
+                   (index), (void *)(value))
+
+/**
+ * sintmap_add - place a member in a signed integer map.
+ * @smap: the typed intmap to add to.
+ * @index: the signed index to place in the map.
+ * @value: the (non-NULL) value.
+ *
+ * This returns false if we run out of memory (errno = ENOMEM), or
+ * (more normally) if that index already appears in the map (EEXIST).
+ *
+ * Note that the value is not copied, just the pointer.
+ *
+ * Example:
+ *     val = malloc(sizeof *val);
+ *     *val = 17;
+ *     if (!sintmap_add(&sint_intmap, -100, val))
+ *             printf("-100 was already in the map\n");
+ */
+#define sintmap_add(smap, index, value)                                        \
+       intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary,  \
+                                              (value))),               \
+                   SINTMAP_OFF(index), (void *)(value))
+
+bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
+
+/**
+ * uintmap_del - remove a member from an unsigned integer map.
+ * @umap: the typed intmap to delete from.
+ * @index: the unsigned index to remove from the map.
+ *
+ * This returns the value, or NULL if there was no value at that
+ * index.
+ *
+ * Example:
+ *     if (uintmap_del(&uint_intmap, 100) == NULL)
+ *             printf("100 was not in the map?\n");
+ */
+#define uintmap_del(umap, index)                                       \
+       tcon_cast((umap), uintmap_canary,                               \
+                 intmap_del_(uintmap_unwrap_(umap), (index)))
+
+/**
+ * sintmap_del - remove a member from a signed integer map.
+ * @smap: the typed intmap to delete from.
+ * @index: the signed index to remove from the map.
+ *
+ * This returns the value, or NULL if there was no value at that
+ * index.
+ *
+ * Example:
+ *     if (sintmap_del(&sint_intmap, -100) == NULL)
+ *             printf("-100 was not in the map?\n");
+ */
+#define sintmap_del(smap, index)                                       \
+       tcon_cast((smap), sintmap_canary,                               \
+                 intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
+
+void *intmap_del_(struct intmap *map, intmap_index_t index);
+
+/**
+ * uintmap_clear - remove every member from an unsigned integer map.
+ * @umap: the typed intmap to clear.
+ *
+ * The map will be empty after this.
+ *
+ * Example:
+ *     uintmap_clear(&uint_intmap);
+ */
+#define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
+
+/**
+ * sintmap_clear - remove every member from a signed integer map.
+ * @smap: the typed intmap to clear.
+ *
+ * The map will be empty after this.
+ *
+ * Example:
+ *     sintmap_clear(&sint_intmap);
+ */
+#define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
+
+void intmap_clear_(struct intmap *map);
+
+/**
+ * uintmap_first - get first index in an unsigned intmap
+ * @umap: the typed intmap to iterate through.
+ *
+ * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty.
+ * Otherwise errno is set to 0.
+ */
+#define uintmap_first(umap)                    \
+       intmap_first_(uintmap_unwrap_(umap))
+
+/**
+ * sintmap_first - get first index in a signed intmap
+ * @smap: the typed intmap to iterate through.
+ *
+ * Returns SINTMAP_NONE and sets errno to ENOENT if it's
+ * empty.  Otherwise errno is set to 0.
+ */
+#define sintmap_first(smap)                                    \
+       SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap)))
+
+intmap_index_t intmap_first_(const struct intmap *map);
+
+/**
+ * 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)
+ *
+ * Returns UINTMAP_NONE and sets errno to ENOENT if there are no
+ * others.  Otherwise errno is set to 0.
+ */
+#define uintmap_after(umap, i)                         \
+       intmap_after_(uintmap_unwrap_(umap), (i))
+
+/**
+ * sintmap_after - get the closest following index in a signed intmap
+ * @smap: the typed intmap to iterate through.
+ * @i: the preceeding index.
+ *
+ * Returns SINTMAP_NONE and sets errno to ENOENT if there are no
+ * others.  Otherwise errno is set to 0.
+ */
+#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);
+
+/* TODO: We could implement intmap_prefix, intmap_iterate... */
+
+/* These make sure it really is a uintmap/sintmap */
+#define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
+#define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
+
+/* We have to offset indices if they're signed, so ordering works. */
+#define SINTMAP_OFFSET         ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
+#define SINTMAP_OFF(index)     ((intmap_index_t)(index) + SINTMAP_OFFSET)
+#define SINTMAP_UNOFF(index)   ((intmap_index_t)(index) - SINTMAP_OFFSET)
+
+#endif /* CCAN_INTMAP_H */

diff --git a/ccan/intmap/test/run-order-smallsize.c b/ccan/intmap/test/run-order-smallsize.c
new file mode 100644 (file)
index 0000000..e916441
--- /dev/null
+++ b/ccan/intmap/test/run-order-smallsize.c
@@ -0,0 +1,92 @@
+#define intmap_index_t uint8_t
+
+#include <ccan/intmap/intmap.c>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+
+#define NUM 100
+
+typedef UINTMAP(uint8_t *) umap;
+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;
+
+       /* Must be in order, must contain value. */
+       prev = -1;
+       for (i = uintmap_first(map);
+            i != UINTMAP_NONE || errno == 0;
+            i = uintmap_after(map, i)) {
+               if (i <= prev)
+                       return false;
+               if (*(uint8_t *)uintmap_get(map, i) != i)
+                       return false;
+               prev = i;
+       }
+       return true;
+}
+
+static bool check_smap(const smap *map)
+{
+       /* This is a larger type than int, and allows negative */
+       int64_t i, prev;
+
+       /* Must be in order, must contain value. */
+       prev = -0x80000001ULL;
+       for (i = sintmap_first(map);
+            i != 127 || errno == 0;
+            i = sintmap_after(map, i)) {
+               if (i <= prev)
+                       return false;
+               if (*(int8_t *)sintmap_get(map, i) != i)
+                       return false;
+               prev = i;
+       }
+       return true;
+}
+
+int main(void)
+{
+       umap umap;
+       smap smap;
+       int i;
+       uint8_t urandoms[NUM];
+       int8_t srandoms[NUM];
+
+       plan_tests(6 * NUM + 2);
+       uintmap_init(&umap);
+       sintmap_init(&smap);
+
+       for (i = 0; i < NUM; i++) {
+               urandoms[i] = random();
+               srandoms[i] = random();
+       }
+       for (i = 0; i < NUM; i++) {
+               /* In case we have duplicates. */
+               while (!uintmap_add(&umap, urandoms[i], urandoms+i))
+                       urandoms[i] = random();
+               ok1(check_umap(&umap));
+       }
+       for (i = 0; i < NUM; i++) {
+               ok1(uintmap_del(&umap, urandoms[i]) == urandoms+i);
+               ok1(check_umap(&umap));
+       }
+       ok1(uintmap_empty(&umap));
+
+       for (i = 0; i < NUM; i++) {
+               /* In case we have duplicates. */
+               while (!sintmap_add(&smap, srandoms[i], srandoms+i))
+                       srandoms[i] = random();
+               ok1(check_smap(&smap));
+       }
+       for (i = 0; i < NUM; i++) {
+               ok1(sintmap_del(&smap, srandoms[i]) == srandoms+i);
+               ok1(check_smap(&smap));
+       }
+       ok1(sintmap_empty(&smap));
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}

diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c
new file mode 100644 (file)
index 0000000..c44d2ba
--- /dev/null
+++ b/ccan/intmap/test/run-order.c
@@ -0,0 +1,88 @@
+#include <ccan/intmap/intmap.c>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+
+#define NUM 1000
+
+typedef UINTMAP(unsigned int *) umap;
+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;
+
+       /* Must be in order, must contain value. */
+       prev = -1;
+       for (i = uintmap_first(map); i != -1ULL; i = uintmap_after(map, i)) {
+               if (i <= prev)
+                       return false;
+               if (*(unsigned int *)uintmap_get(map, i) != i)
+                       return false;
+               prev = i;
+       }
+       return true;
+}
+
+static bool check_smap(const smap *map)
+{
+       /* This is a larger type than int, and allows negative */
+       int64_t i, prev;
+
+       /* Must be in order, must contain value. */
+       prev = -0x80000001ULL;
+       for (i = sintmap_first(map);
+            i != 0x7FFFFFFFFFFFFFFFLL;
+            i = sintmap_after(map, i)) {
+               if (i <= prev)
+                       return false;
+               if (*(int *)sintmap_get(map, i) != i)
+                       return false;
+               prev = i;
+       }
+       return true;
+}
+
+int main(void)
+{
+       umap umap;
+       smap smap;
+       int i;
+       unsigned int urandoms[NUM];
+       int srandoms[NUM];
+
+       plan_tests(6 * NUM + 2);
+       uintmap_init(&umap);
+       sintmap_init(&smap);
+
+       for (i = 0; i < NUM; i++) {
+               urandoms[i] = random();
+               srandoms[i] = random();
+       }
+       for (i = 0; i < NUM; i++) {
+               /* In case we have duplicates. */
+               while (!uintmap_add(&umap, urandoms[i], urandoms+i))
+                       urandoms[i] = random();
+               ok1(check_umap(&umap));
+       }
+       for (i = 0; i < NUM; i++) {
+               ok1(uintmap_del(&umap, urandoms[i]) == urandoms+i);
+               ok1(check_umap(&umap));
+       }
+       ok1(uintmap_empty(&umap));
+
+       for (i = 0; i < NUM; i++) {
+               /* In case we have duplicates. */
+               while (!sintmap_add(&smap, srandoms[i], srandoms+i))
+                       srandoms[i] = random();
+               ok1(check_smap(&smap));
+       }
+       for (i = 0; i < NUM; i++) {
+               ok1(sintmap_del(&smap, srandoms[i]) == srandoms+i);
+               ok1(check_smap(&smap));
+       }
+       ok1(sintmap_empty(&smap));
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}

diff --git a/ccan/intmap/test/run-signed-int.c b/ccan/intmap/test/run-signed-int.c
new file mode 100644 (file)
index 0000000..8e95e8f
--- /dev/null
+++ b/ccan/intmap/test/run-signed-int.c
@@ -0,0 +1,53 @@
+#include <ccan/intmap/intmap.h>
+#include <ccan/intmap/intmap.c>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+       SINTMAP(const char *) map;
+       const char *first = "first", *second = "second";
+
+       /* This is how many tests you plan to run */
+       plan_tests(35);
+
+       sintmap_init(&map);
+       /* Test boundaries. */
+       ok1(!sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL));
+       ok1(!sintmap_get(&map, -0x8000000000000000LL));
+       ok1(sintmap_first(&map) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFELL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_add(&map, 0x7FFFFFFFFFFFFFFFLL, first));
+       ok1(sintmap_get(&map, 0x7FFFFFFFFFFFFFFFLL) == first);
+       ok1(sintmap_first(&map) == 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(errno == 0);
+       ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFELL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == 0);
+       ok1(sintmap_after(&map, -0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == 0);
+       ok1(sintmap_after(&map, 0x7FFFFFFFFFFFFFFFLL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_del(&map, 0x7FFFFFFFFFFFFFFFLL) == first);
+       ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == ENOENT);
+       ok1(sintmap_add(&map, 0x7FFFFFFFFFFFFFFFLL, first));
+       ok1(sintmap_del(&map, 0x8000000000000000LL) == second);
+       ok1(sintmap_after(&map, -0x8000000000000000LL) == 0x7FFFFFFFFFFFFFFFLL);
+       ok1(errno == 0);
+       ok1(sintmap_del(&map, 0x7FFFFFFFFFFFFFFFLL) == first);
+       ok1(sintmap_empty(&map));
+       
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}

diff --git a/ccan/intmap/test/run.c b/ccan/intmap/test/run.c
new file mode 100644 (file)
index 0000000..41efc44
--- /dev/null
+++ b/ccan/intmap/test/run.c
@@ -0,0 +1,55 @@
+#include <ccan/intmap/intmap.h>
+#include <ccan/intmap/intmap.c>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+       UINTMAP(char *) map;
+       const char val[] = "there";
+       const char none[] = "";
+
+       /* This is how many tests you plan to run */
+       plan_tests(28);
+
+       uintmap_init(&map);
+
+       ok1(!uintmap_get(&map, 1));
+       ok1(errno == ENOENT);
+       ok1(!uintmap_get(&map, 0));
+       ok1(errno == ENOENT);
+       ok1(!uintmap_del(&map, 1));
+       ok1(errno == ENOENT);
+       ok1(!uintmap_del(&map, 0));
+       ok1(errno == ENOENT);
+
+       ok1(uintmap_add(&map, 1, val));
+       ok1(uintmap_get(&map, 1) == val);
+       ok1(!uintmap_get(&map, 0));
+       ok1(errno == ENOENT);
+
+       /* Add a duplicate should fail. */
+       ok1(!uintmap_add(&map, 1, val));
+       ok1(errno == EEXIST);
+
+       /* Delete should succeed. */
+       ok1(uintmap_del(&map, 1) == val);
+       ok1(!uintmap_get(&map, 1));
+       ok1(errno == ENOENT);
+       ok1(!uintmap_get(&map, 0));
+       ok1(errno == ENOENT);
+
+       /* Both at once... */
+       ok1(uintmap_add(&map, 0, none));
+       ok1(uintmap_add(&map, 1, val));
+       ok1(uintmap_get(&map, 1) == val);
+       ok1(uintmap_get(&map, 0) == none);
+       ok1(!uintmap_del(&map, 2));
+       ok1(uintmap_del(&map, 0) == none);
+       ok1(uintmap_get(&map, 1) == val);
+       ok1(uintmap_del(&map, 1) == val);
+
+       ok1(uintmap_empty(&map));
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}