From d9e93014a999102aa1cc9979e041cd58e6aca724 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Wed, 11 Jan 2017 13:55:54 +1030 Subject: [PATCH] intmap: new module. Critbit tree to map ints/uints to pointers. Signed-off-by: Rusty Russell --- ccan/intmap/LICENSE | 1 + ccan/intmap/_info | 34 +++ ccan/intmap/intmap.c | 212 ++++++++++++++++ ccan/intmap/intmap.h | 320 +++++++++++++++++++++++++ ccan/intmap/test/run-order-smallsize.c | 92 +++++++ ccan/intmap/test/run-order.c | 88 +++++++ ccan/intmap/test/run-signed-int.c | 53 ++++ ccan/intmap/test/run.c | 55 +++++ 8 files changed, 855 insertions(+) create mode 120000 ccan/intmap/LICENSE create mode 100644 ccan/intmap/_info create mode 100644 ccan/intmap/intmap.c create mode 100644 ccan/intmap/intmap.h create mode 100644 ccan/intmap/test/run-order-smallsize.c create mode 100644 ccan/intmap/test/run-order.c create mode 100644 ccan/intmap/test/run-signed-int.c create mode 100644 ccan/intmap/test/run.c diff --git a/ccan/intmap/LICENSE b/ccan/intmap/LICENSE new file mode 120000 index 00000000..b7951dab --- /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 index 00000000..d9ba4622 --- /dev/null +++ b/ccan/intmap/_info @@ -0,0 +1,34 @@ +#include "config.h" +#include +#include + +/** + * 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 + */ +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 index 00000000..d27b6456 --- /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 +#include +#include +#include +#include +#include +#include + +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 index 00000000..f06f02d0 --- /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 +#include +#include +#include +#include + +/* 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 index 00000000..e9164413 --- /dev/null +++ b/ccan/intmap/test/run-order-smallsize.c @@ -0,0 +1,92 @@ +#define intmap_index_t uint8_t + +#include +#include +#include + +#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 index 00000000..c44d2ba3 --- /dev/null +++ b/ccan/intmap/test/run-order.c @@ -0,0 +1,88 @@ +#include +#include +#include + +#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 index 00000000..8e95e8f4 --- /dev/null +++ b/ccan/intmap/test/run-signed-int.c @@ -0,0 +1,53 @@ +#include +#include +#include + +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 index 00000000..41efc442 --- /dev/null +++ b/ccan/intmap/test/run.c @@ -0,0 +1,55 @@ +#include +#include +#include + +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(); +} -- 2.39.2