aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-11-11 22:53:21 +0100
committerDavid Robillard <d@drobilla.net>2018-12-31 11:37:48 -0500
commit03cc8153e49fcf3d075849d358e37bcd4d07446d (patch)
treec904ff0b2b7d601f070bd8251bf3141689c91340
parent7eecae6afb1184cfa4648ac6e16507ff23357cb4 (diff)
downloadserd-03cc8153e49fcf3d075849d358e37bcd4d07446d.tar.gz
serd-03cc8153e49fcf3d075849d358e37bcd4d07446d.tar.bz2
serd-03cc8153e49fcf3d075849d358e37bcd4d07446d.zip
Add debug check that BTree nodes are properly sorted
-rw-r--r--src/zix/btree.c26
1 files changed, 26 insertions, 0 deletions
diff --git a/src/zix/btree.c b/src/zix/btree.c
index f337f7df..7521086d 100644
--- a/src/zix/btree.c
+++ b/src/zix/btree.c
@@ -235,6 +235,30 @@ zix_btree_split_child(ZixBTreeNode* const n,
return rhs;
}
+#ifndef NDEBUG
+/** Check that `n` is sorted with respect to search key `e`. */
+ZIX_PRIVATE bool
+zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t,
+ const ZixBTreeNode* const n,
+ const void* const e)
+{
+ if (n->n_vals <= 1) {
+ return true;
+ }
+
+ int cmp = t->cmp(n->vals[0], e, t->cmp_data);
+ for (uint16_t i = 1; i < n->n_vals; ++i) {
+ const int next_cmp = t->cmp(n->vals[i], e, t->cmp_data);
+ if ((cmp >= 0 && next_cmp < 0)) {
+ return false;
+ }
+ cmp = next_cmp;
+ }
+
+ return true;
+}
+#endif
+
/** Find the first value in `n` that is not less than `e` (lower bound). */
ZIX_PRIVATE uint16_t
zix_btree_node_find(const ZixBTree* const t,
@@ -242,6 +266,8 @@ zix_btree_node_find(const ZixBTree* const t,
const void* const e,
bool* const equal)
{
+ assert(zix_btree_node_is_sorted_with_respect_to(t, n, e));
+
uint16_t first = 0;
uint16_t len = n->n_vals;
while (len > 0) {