diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/libalgo/btree.c | 1 | ||||
| -rw-r--r-- | src/common/libalgo/keyval.c | 2 | ||||
| -rw-r--r-- | src/tests/ktests/btree2/test.c | 19 |
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++) { |