X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fintmap%2Fintmap.c;h=341b8a92134981c9fd381149c71c7fd16d0325ef;hp=ab6ddc9d87dd0763025a80912f2e049dfc96c01b;hb=HEAD;hpb=e59acd521d11c1f392264762d79195fd6cc2b992

diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c
index ab6ddc9d..341b8a92 100644
--- a/ccan/intmap/intmap.c
+++ b/ccan/intmap/intmap.c
@@ -231,6 +231,63 @@ none_left:
 	return NULL;
 }
 
+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp)
+{
+	const struct intmap *n, *prev = NULL;
+	intmap_index_t index = (*indexp) - 1;
+
+	/* Special case of overflow */
+	if (index == (intmap_index_t)-1ULL)
+		goto none_left;
+
+	/* Special case of empty map */
+	if (intmap_empty_(map))
+		goto none_left;
+
+	/* Follow down, until prefix differs. */
+	n = map;
+	while (!n->v) {
+		int crit = critbit(n);
+		u8 direction;
+		intmap_index_t prefix, idx;
+
+		idx = (index >> crit);
+		direction = idx & 1;
+
+		/* Leave critbit in place: we can't shift by 64 anyway */
+		idx |= 1;
+		prefix = n->u.n->prefix_and_critbit >> crit;
+
+		/* If this entire tree is less than index, take last */
+		if (idx > prefix)
+			return intmap_last_(n, indexp);
+		/* If this entire tree is greater than index, we're past it. */
+		else if (idx < prefix)
+			goto try_lesser_tree;
+
+		/* Remember lesser tree for backtracking */
+		if (direction)
+			prev = n;
+		n = &n->u.n->child[direction];
+	}
+
+	/* Found a predecessor? */
+	if (n->u.i <= index) {
+		errno = 0;
+		*indexp = n->u.i;
+		return n->v;
+	}
+
+try_lesser_tree:
+	/* If we ever took a lesser branch, go back to lesser branch */
+	if (prev)
+		return intmap_last_(&prev->u.n->child[0], indexp);
+
+none_left:
+	errno = ENOENT;
+	return NULL;
+}
+
 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
 {
 	const struct intmap *n;
@@ -264,3 +321,19 @@ void intmap_clear_(struct intmap *map)
 		clear(*map);
 	intmap_init_(map);
 }
+
+bool intmap_iterate_(const struct intmap *n,
+		     bool (*handle)(intmap_index_t, void *, void *),
+		     void *data,
+		     intmap_index_t offset)
+{
+	/* Can only happen at root */
+	if (intmap_empty_(n))
+		return true;
+
+	if (n->v)
+		return handle(n->u.i - offset, n->v, data);
+
+	return intmap_iterate_(&n->u.n->child[0], handle, data, offset)
+		&& intmap_iterate_(&n->u.n->child[1], handle, data, offset);
+}