Function tree_insert_recursive

python/bplustree_c_src/tree_ops.c:43–75

Recursive insert helper */

/* Recursive insert helper */
static int tree_insert_recursive(BPlusNode *node, PyObject *key, PyObject *value,
                                BPlusNode **new_node, PyObject **split_key) {
    if (node->type == NODE_LEAF) {
        return node_insert_leaf(node, key, value, new_node, split_key);
    }
    
    /* Find child to insert into */
    int child_pos = node_find_position(node, key);
    if (child_pos < 0) {
        return -1;
    }
    /* bisect_right semantics: advance past equal keys */
    if (child_pos < node->num_keys) {
        PyObject *node_key = node_get_key(node, child_pos);
        int eq = fast_compare_eq(node_key, key);
        if (eq < 0) {
            return -1;
        }
        if (eq) {
            child_pos++;
        }
    }
    BPlusNode *child = node_get_child(node, child_pos);
    BPlusNode *new_child = NULL;
    PyObject *new_key = NULL;
    
    int result = tree_insert_recursive(child, key, value, &new_child, &new_key);
    if (result < 0) return result;  /* Error or update - propagate as-is */
    if (result == 0) return 0;      /* No split */
    
    /* Child was split, need to insert new_key and new_child into this node */
    return node_insert_branch(node, new_key, new_child, new_node, split_key);
}

/* Insert key-value pair into tree */
int tree_insert(BPlusTree *tree, PyObject *key, PyObject *value) {