X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fintmap%2Fintmap.c;h=341b8a92134981c9fd381149c71c7fd16d0325ef;hp=3473ef3236159fc834aaffad1a4ba81977937ca1;hb=7aac849abf06ef469c2aad9a0dd6e3bb82ef1f96;hpb=f7ead5da96bfb5ce3ebffe11256bbcb5f4b4f750

diff --git a/ccan/intmap/intmap.c b/ccan/intmap/intmap.c
index 3473ef32..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;