Add lower/upper bound test ; fix id_key_cmp_fun.

3 files changed, 21 insertions, 1 deletions

diff --git a/src/common/libalgo/btree.c b/src/common/libalgo/btree.c
index 08a43ef..20323aa 100644
--- a/src/common/libalgo/btree.c
+++ b/src/common/libalgo/btree.c
@@ -261,6 +261,7 @@ void* btree_upper(btree_t *t, const void* key) {
 	return i->val;
 }
 
+
 void btree_iter(btree_t *t, kv_iter_fun_t f) {
 	void iter_aux(btree_item_t *i, kv_iter_fun_t f) {
 		if (i == 0) return;
diff --git a/src/common/libalgo/keyval.c b/src/common/libalgo/keyval.c
index 0368aed..528fa90 100644
--- a/src/common/libalgo/keyval.c
+++ b/src/common/libalgo/keyval.c
@@ -26,7 +26,7 @@ bool str_key_eq_fun(const void* a, const void* b) {
 }
 
 int id_key_cmp_fun(const void* a, const void* b) {
-	return (b == a ? 0 : (b > a ? 1 : -1));
+	return (a == b ? 0 : (a < b ? -1 : 1));
 }
 
 int str_key_cmp_fun(const void* a, const void* b) {
diff --git a/src/tests/ktests/btree2/test.c b/src/tests/ktests/btree2/test.c
index eb76dba..9e105a9 100644
--- a/src/tests/ktests/btree2/test.c
+++ b/src/tests/ktests/btree2/test.c
@@ -24,6 +24,25 @@ void test_btree_2() {
 
 	for (int i = 0; i < n; i++) {
 		ASSERT(btree_find(ht, (void*)k[i]) == (void*)v[i]);
+		ASSERT(btree_lower(ht, (void*)k[i]) == (void*)v[i]);
+		ASSERT(btree_upper(ht, (void*)k[i]) == (void*)v[i]);
+	}
+
+	// random lower bound/upper bound tests
+	for (int t = 0; t < 100; t++) {
+		const uint32_t xk = prng();
+		int ilower = -1, iupper = -1;
+		for (int i = 1; i < n; i++) {
+			if (k[i] <= xk && (ilower == -1 || k[i] > k[ilower])) ilower = i;
+			if (k[i] >= xk && (iupper == -1 || k[i] < k[iupper])) iupper = i;
+		}
+		dbg_printf("random %d : lower %d (= %d), upper %d (= %d) ; ",
+			xk, k[ilower], v[ilower], k[iupper], v[iupper]);
+		const uint32_t bt_lower = (uint32_t)btree_lower(ht, (void*)xk);
+		const uint32_t bt_upper = (uint32_t)btree_upper(ht, (void*)xk);
+		dbg_printf("got lower %d, upper %d\n", bt_lower, bt_upper);
+		ASSERT(bt_lower == (ilower == -1 ? 0 : v[ilower]));;
+		ASSERT(bt_upper == (iupper == -1 ? 0 : v[iupper]));;
 	}
 
 	for (int i = 0; i < n/2; i++) {