Function node_insert_branch

python/bplustree_c_src/tree_ops.c:135–220

Insert into branch node */

/* Insert into branch node */
int node_insert_branch(BPlusNode *node, PyObject *key, BPlusNode *right_child,
                       BPlusNode **new_node, PyObject **split_key) {
    int pos = node_find_position(node, key);
    if (pos < 0) return -1;
    
    /* Check if split is needed */
    if (node->num_keys >= node->capacity) {
        /* Create new node */
        *new_node = node_create(NODE_BRANCH, node->capacity);
        if (!*new_node) return -1;
        
        /* Temporary arrays for redistribution */
        PyObject **temp_keys = PyMem_Malloc((node->capacity + 1) * sizeof(PyObject*));
        BPlusNode **temp_children = PyMem_Malloc((node->capacity + 2) * sizeof(BPlusNode*));
        if (!temp_keys || !temp_children) {
            PyMem_Free(temp_keys);
            PyMem_Free(temp_children);
            node_destroy(*new_node);
            PyErr_NoMemory();
            return -1;
        }
        
        /* Copy existing + new into temp arrays */
        temp_children[0] = node_get_child(node, 0);
        
        int j = 0;
        for (int i = 0; i < pos; i++) {
            temp_keys[j] = node_get_key(node, i);
            temp_children[j + 1] = node_get_child(node, i + 1);
            j++;
        }
        temp_keys[j] = key;
        temp_children[j + 1] = right_child;
        j++;
        for (int i = pos; i < node->num_keys; i++) {
            temp_keys[j] = node_get_key(node, i);
            temp_children[j + 1] = node_get_child(node, i + 1);
            j++;
        }
        
        /* Split at midpoint */
        int mid = node->capacity / 2;
        *split_key = temp_keys[mid];
        Py_INCREF(*split_key);
        
        /* Keep first half in current node */
        node->num_keys = mid;
        for (int i = 0; i < mid; i++) {
            Py_INCREF(temp_keys[i]);
            node_set_key(node, i, temp_keys[i]);
        }
        for (int i = 0; i <= mid; i++) {
            node_set_child(node, i, temp_children[i]);
        }
        
        /* Move second half to new node */
        (*new_node)->num_keys = node->capacity - mid;
        for (int i = 0; i < (*new_node)->num_keys; i++) {