Add debug check that BTree nodes are properly sorted

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