Function node_insert_leaf

python/bplustree_c_src/node_ops.c:172–287

Insert into leaf node */

/* Insert into leaf node */
int node_insert_leaf(BPlusNode *node, PyObject *key, PyObject *value, 
                     BPlusNode **new_node, PyObject **split_key) {
    int pos = node_find_position(node, key);
    if (pos < 0) return -1;  /* Comparison error */
    
    /* Check if key already exists */
    if (pos < node->num_keys) {
        PyObject *existing_key = node_get_key(node, pos);
        int cmp = fast_compare_eq(existing_key, key);
        if (cmp < 0) return -1;  /* Comparison error */
        
        if (cmp) {
            /* Update existing value */
            PyObject *old_value = node_get_value(node, pos);
            Py_INCREF(value);
            node_set_value(node, pos, value);
            Py_DECREF(old_value);
            return -2;  /* Special return code for update */
        }
    }
    
    /* Check if split is needed */
    if (node->num_keys >= node->capacity) {
        /* Create new node */
        *new_node = node_create(NODE_LEAF, node->capacity);
        if (!*new_node) return -1;
        
        /* Temporary arrays for redistribution */
        PyObject **temp_keys = PyMem_Malloc((node->capacity + 1) * sizeof(PyObject*));
        PyObject **temp_values = PyMem_Malloc((node->capacity + 1) * sizeof(PyObject*));
        if (!temp_keys || !temp_values) {
            PyMem_Free(temp_keys);
            PyMem_Free(temp_values);
            node_destroy(*new_node);
            PyErr_NoMemory();
            return -1;
        }
        
        /* Copy existing + new into temp arrays */
        int j = 0;
        for (int i = 0; i < pos; i++) {
            temp_keys[j] = node_get_key(node, i);
            temp_values[j] = node_get_value(node, i);
            j++;
        }
        temp_keys[j] = key;
        temp_values[j] = value;
        j++;
        for (int i = pos; i < node->num_keys; i++) {
            temp_keys[j] = node_get_key(node, i);
            temp_values[j] = node_get_value(node, i);
            j++;
        }
        
        /* Split at midpoint - exactly like Python code */
        int mid = node->capacity / 2;  /* Same as Python: self.capacity // 2 */

        /* Keep first half in current node */