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;
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)
/* 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
*
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))
#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 */
#define intmap_index_t uint8_t
+#define sintmap_index_t int8_t
#include <ccan/intmap/intmap.c>
#include <ccan/tap/tap.h>
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;
}
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;
}
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;
}
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;
}
{
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);
/* 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));
projects / ccan / commitdiff