Method check_node_invariants

rust/src/validation.rs:150–276

Recursively check invariants for a node and its children.

(
        &self,
        node: &NodeRef<K, V>,
        min_key: Option<&K>,
        max_key: Option<&K>,
        _is_root: bool,
    )

    /// Recursively check invariants for a node and its children.
    fn check_node_invariants(
        &self,
        node: &NodeRef<K, V>,
        min_key: Option<&K>,
        max_key: Option<&K>,
        _is_root: bool,
    ) -> bool {
        match node {
            NodeRef::Leaf(id, _) => {
                if let Some(leaf) = self.get_leaf(*id) {
                    // Check leaf invariants
                    if leaf.keys_len() != leaf.values_len() {
                        return false; // Keys and values must have same length
                    }

                    // Check that keys are sorted
                    for i in 1..leaf.keys_len() {
                        if let (Some(prev_key), Some(curr_key)) =
                            (leaf.get_key(i - 1), leaf.get_key(i))
                        {
                            if prev_key >= curr_key {
                                return false; // Keys must be in ascending order
                            }
                        }
                    }

                    // Check capacity constraints
                    if leaf.keys_len() > self.capacity {
                        return false; // Node exceeds capacity
                    }

                    // Check minimum occupancy
                    if !leaf.keys_is_empty() && leaf.is_underfull() {
                        // For root nodes, allow fewer keys only if it's the only node
                        if _is_root {
                            // Root leaf can have any number of keys >= 1
                            // (This is fine for leaf roots)
                        } else {
                            return false; // Non-root leaf is underfull
                        }
                    }

                    // Check key bounds
                    if let Some(min) = min_key {
                        if !leaf.keys_is_empty() {
                            if let Some(first_key) = leaf.first_key() {
                                if first_key < min {
                                    return false; // First key must be >= min_key
                                }
                            }
                        }
                    }
                    if let Some(max) = max_key {
                        if !leaf.keys_is_empty() {
                            if let Some(last_key) = leaf.last_key() {
                                if last_key >= max {
                                    return false; // Last key must be < max_key
                                }