From: Rusty Russell <rusty@rustcorp.com.au>
Date: Thu, 10 Oct 2019 05:06:00 +0000 (+1030)
Subject: intmap: implement intmap_before()
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=7aac849abf06ef469c2aad9a0dd6e3bb82ef1f96

intmap: implement intmap_before()

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

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;
diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h
index 207b7c9d..834c969f 100644
--- a/ccan/intmap/intmap.h
+++ b/ccan/intmap/intmap.h
@@ -309,6 +309,32 @@ void *intmap_after_(const struct intmap *map, intmap_index_t *indexp);
 	tcon_cast((smap), sintmap_canary,				\
 		  sintmap_after_(sintmap_unwrap_(smap), (indexp)))
 
+/**
+ * uintmap_before - get the closest preceding index in an unsigned intmap
+ * @umap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define uintmap_before(umap, indexp)					\
+	tcon_cast((umap), uintmap_canary,				\
+		  intmap_before_(uintmap_unwrap_(umap), (indexp)))
+
+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp);
+
+/**
+ * sintmap_before - get the closest preceding index in a signed intmap
+ * @smap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define sintmap_before(smap, indexp)					\
+	tcon_cast((smap), sintmap_canary,				\
+		  sintmap_before_(sintmap_unwrap_(smap), (indexp)))
+
 /**
  * uintmap_last - get last value in an unsigned intmap
  * @umap: the typed intmap to iterate through.
@@ -455,6 +481,15 @@ static inline void *sintmap_after_(const struct intmap *map,
 	return ret;
 }
 
+static inline void *sintmap_before_(const struct intmap *map,
+				   sintmap_index_t *indexp)
+{
+	intmap_index_t i = SINTMAP_OFF(*indexp);
+	void *ret = intmap_before_(map, &i);
+	*indexp = SINTMAP_UNOFF(i);
+	return ret;
+}
+
 static inline void *sintmap_last_(const struct intmap *map,
 				  sintmap_index_t *indexp)
 {
diff --git a/ccan/intmap/test/run-order-smallsize.c b/ccan/intmap/test/run-order-smallsize.c
index 63c5b9c9..8121f276 100644
--- a/ccan/intmap/test/run-order-smallsize.c
+++ b/ccan/intmap/test/run-order-smallsize.c
@@ -19,6 +19,15 @@ static bool check_umap(const umap *map)
 	bool last = true;
 
 	/* Must be in order, must contain value. */
+	prev = 256;
+	for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+		if (i >= prev)
+			return false;
+		if (*v != i)
+			return false;
+		prev = i;
+	}
+
 	prev = -1;
 	for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) {
 		if (i <= prev)
@@ -40,6 +49,15 @@ static bool check_smap(const smap *map)
 	bool last = true;
 
 	/* Must be in order, must contain value. */
+	prev = 0x80000000ULL;
+	for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+		if (i >= prev)
+			return false;
+		if (*v != i)
+			return false;
+		prev = i;
+	}
+
 	prev = -0x80000001ULL;
 	for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) {
 		if (i <= prev)
@@ -52,7 +70,7 @@ static bool check_smap(const smap *map)
 	return last;
 }
 
-int main(void)
+int main(int argc, char *argv[])
 {
 	umap umap;
 	smap smap;
@@ -64,6 +82,9 @@ int main(void)
 	uintmap_init(&umap);
 	sintmap_init(&smap);
 
+	if (argc > 1)
+		srandom(atoi(argv[1]));
+
 	for (i = 0; i < NUM; i++) {
 		urandoms[i] = random();
 		srandoms[i] = random();
diff --git a/ccan/intmap/test/run-order.c b/ccan/intmap/test/run-order.c
index f7e86692..d945a4a8 100644
--- a/ccan/intmap/test/run-order.c
+++ b/ccan/intmap/test/run-order.c
@@ -36,6 +36,19 @@ static bool check_umap(const umap *map)
 		last = (uintmap_last(map, &last_idx) == v);
 	}
 
+	if (!last)
+		return false;
+
+	prev = INT_MAX;
+	for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+		if ((int64_t)i >= prev)
+			return false;
+		if (*v != i)
+			return false;
+		prev = i;
+		last = (uintmap_first(map, &last_idx) == v);
+	}
+
 	if (!last)
 		return false;
 
@@ -71,6 +84,18 @@ static bool check_smap(const smap *map)
 		prev = i;
 	}
 
+	if (!last)
+		return false;
+
+	prev = 0x80000001ULL;
+	for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+		if (i >= prev)
+			return false;
+		if (*v != i)
+			return false;
+		prev = i;
+		last = (sintmap_first(map, &last_idx) == v);
+	}
 	if (!last)
 		return false;