diff options
author | David Robillard <d@drobilla.net> | 2018-11-11 22:53:21 +0100 |
---|---|---|
committer | David Robillard <d@drobilla.net> | 2018-12-31 11:37:48 -0500 |
commit | 03cc8153e49fcf3d075849d358e37bcd4d07446d (patch) | |
tree | c904ff0b2b7d601f070bd8251bf3141689c91340 | |
parent | 7eecae6afb1184cfa4648ac6e16507ff23357cb4 (diff) | |
download | serd-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.c | 26 |
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) { |