Method split_and_insert

cranelift/bforest/src/path.rs:291–374

Split the current leaf node and then insert `key, value`. This should only be used if `try_leaf_insert()` fails.

(
        &mut self,
        mut key: F::Key,
        value: F::Value,
        pool: &mut NodePool<F>,
    )

    /// Split the current leaf node and then insert `key, value`.
    /// This should only be used if `try_leaf_insert()` fails.
    fn split_and_insert(
        &mut self,
        mut key: F::Key,
        value: F::Value,
        pool: &mut NodePool<F>,
    ) -> Result<(), OutOfMemory> {
        let orig_root = self.node[0];

        // Loop invariant: We need to split the node at `level` and then retry a failed insertion.
        // The items to insert are either `(key, ins_node)` or `(key, value)`.
        let mut ins_node = None;
        let mut split;
        for level in (0..self.size).rev() {
            // Split the current node.
            let mut node = self.node[level];
            let mut entry = self.entry[level].into();
            split = pool[node].split(entry);
            let rhs_node = pool.alloc_node(split.rhs_data)?;

            // Should the path be moved to the new RHS node?
            // Prefer the smaller node if we're right in the middle.
            // Prefer to append to LHS all other things being equal.
            //
            // When inserting into an inner node (`ins_node.is_some()`), we must point to a valid
            // entry in the current node since the new entry is inserted *after* the insert
            // location.
            if entry > split.lhs_entries
                || (entry == split.lhs_entries
                    && (split.lhs_entries > split.rhs_entries || ins_node.is_some()))
            {
                node = rhs_node;
                entry -= split.lhs_entries;
                self.node[level] = node;
                self.entry[level] = entry as u8;
            }

            // Now that we have a not-full node, it must be possible to insert.
            match ins_node {
                None => {
                    let inserted = pool[node].try_leaf_insert(entry, key, value);
                    debug_assert!(inserted);
                    // If we inserted at the front of the new rhs_node leaf, we need to propagate
                    // the inserted key as the critical key instead of the previous front key.
                    if entry == 0 && node == rhs_node {
                        split.crit_key = key;
                    }
                }
                Some(n) => {
                    let inserted = pool[node].try_inner_insert(entry, key, n);
                    debug_assert!(inserted);
                    // The lower level was moved to the new RHS node, so make sure that is
                    // reflected here.
                    if n == self.node[level + 1] {
                        self.entry[level] += 1;
                    }
                }
            }