aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-11-11 22:53:21 +0100
committerDavid Robillard <d@drobilla.net>2019-04-13 19:15:32 +0200
commit2330ba6051f113fb47b124b3187d3e17be1fc969 (patch)
tree226401cc18c7b371056ed1923ce8383dfbd6a980
parent3d1d75d570579c402f9462f7b3048560651ac582 (diff)
downloadserd-2330ba6051f113fb47b124b3187d3e17be1fc969.tar.gz
serd-2330ba6051f113fb47b124b3187d3e17be1fc969.tar.bz2
serd-2330ba6051f113fb47b124b3187d3e17be1fc969.zip
Add debug check that BTree nodes are properly sorted
-rw-r--r--src/zix/btree.c28
1 files changed, 28 insertions, 0 deletions
diff --git a/src/zix/btree.c b/src/zix/btree.c
index 4c15e07c..ffc097ab 100644
--- a/src/zix/btree.c
+++ b/src/zix/btree.c
@@ -235,6 +235,30 @@ zix_btree_split_child(ZixBTreeNode* const n,
return rhs;
}
+#ifdef ZIX_BTREE_ULTRA_DEBUG
+/** 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 unsigned
zix_btree_node_find(const ZixBTree* const t,
@@ -242,6 +266,10 @@ zix_btree_node_find(const ZixBTree* const t,
const void* const e,
bool* const equal)
{
+#ifdef ZIX_BTREE_ULTRA_DEBUG
+ assert(zix_btree_node_is_sorted_with_respect_to(t, n, e));
+#endif
+
uint16_t first = 0;
uint16_t len = n->n_vals;
while (len > 0) {