Function btree_insert

src/btree.cc:909–1131

}

btree_result btree_insert(struct btree *btree, void *key, void *value)
{
    void *addr;
    size_t nsplitnode = 1;
    uint8_t *k = alca(uint8_t, btree->ksize);
    uint8_t *v = alca(uint8_t, btree->vsize);
    // index# and block ID for each level
    idx_t *idx = alca(idx_t, btree->height);
    bid_t *bid = alca(bid_t, btree->height);
    bid_t _bid;
    // flags
    int8_t *modified = alca(int8_t, btree->height);
    int8_t *moved = alca(int8_t, btree->height);
    int8_t *ins = alca(int8_t, btree->height);
    int8_t *minkey_replace = alca(int8_t, btree->height);
    int8_t height_growup;

    // key, value to be inserted
    struct list *kv_ins_list = alca(struct list, btree->height);
    struct kv_ins_item *kv_item;
    struct list_elem *e;

    // index# where kv is inserted
    idx_t *idx_ins = alca(idx_t, btree->height);
    struct bnode **node = alca(struct bnode *, btree->height);
    int i, j, _is_update = 0;

    // initialize flags
    for (i=0;i<btree->height;++i) {
        moved[i] = modified[i] = ins[i] = minkey_replace[i] = 0;
    }
    height_growup = 0;

    // initialize temporary variables
    if (btree->kv_ops->init_kv_var) {
        btree->kv_ops->init_kv_var(btree, k, v);
        for (i=0;i<btree->height;++i){
            list_init(&kv_ins_list[i]);
        }
    }

    // copy key-value pair to be inserted into leaf node
    kv_item = _kv_ins_item_create(btree, key, value);
    list_push_back(&kv_ins_list[0], &kv_item->le);

    ins[0] = 1;

    // set root node
    bid[btree->height-1] = btree->root_bid;

    // find path from root to leaf
    for (i=btree->height-1; i>=0; --i){
        // read block using bid
        addr = btree->blk_ops->blk_read(btree->blk_handle, bid[i]);
        // fetch node structure from block
        node[i] = _fetch_bnode(btree, addr, i+1);

        // lookup key in current node