diff options
| -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) { |