keyfcns.c

db.* (pronounced dee-be star) is an advanced, high performance, small footprint embedded database fo

    /* copy keyno into current slot */
    memcpy(node_slot_ptr + sizeof(F_ADDR), &task->prefix, sizeof(short));

    node_slot_ptr += task->key_data;

    /* clear slot data area to zeros */
    memset(node_slot_ptr, 0, task->slot_len - task->key_data);

    /* copy keyval into current slot */
    if (task->cfld_ptr->fd_type == CHARACTER && task->cfld_ptr->fd_dim[1] == 0)
        strncpy(node_slot_ptr, key_val, task->key_len);
    else if (task->cfld_ptr->fd_type == WIDECHAR && task->cfld_ptr->fd_dim[1] == 0)
        vwcsncpy((wchar_t *)node_slot_ptr, (wchar_t *)key_val, task->key_len / sizeof(wchar_t));
    else
        memcpy(node_slot_ptr, key_val, task->key_len);

    /* copy database address into current slot */
    memcpy(node_slot_ptr + task->key_len, &dba, sizeof(DB_ADDR));

    if (node->used_slots == task->max_slots)
    {
        if (pg == ROOT_ADDR)
            split_root(node, task);
        else
            split_node(pg, node, task);
    }
    else
        dio_touch(task->keyfile, pg, PGFREE, task);

    return task->db_status;
}



/* ======================================================================
    Split node into two nodes
*/
static int INTERNAL_FCN split_node(
    F_ADDR   l_pg,                     /* left node's page number */
    NODE    *l_node,                   /* left node buffer */
    DB_TASK *task)
{
    F_ADDR        r_pg;
    DB_ADDR       dba;
    char         *key_val;
    NODE         *r_node;
    char         *l_node_slot_ptr;

    /* Save state of all global variables used in this (potentially) */
    /* recursively invoked procedure.                                */
    int           save_key_len;
    short         save_fldno;
    short         save_keyno;
    FIELD_ENTRY  *save_cfld_ptr;
    short         save_prefix;

    key_val = psp_getMemory(MAXKEYSIZE, 0);
    if (key_val == NULL)
        return (dberr(S_NOMEMORY));

    save_key_len = task->key_len;
    save_fldno = task->fldno;
    save_cfld_ptr = task->cfld_ptr;
    save_keyno = task->keyno;
    save_prefix = task->prefix;

    /* extract middle key */
    l_node_slot_ptr = &l_node->slots[task->mid_slot * task->slot_len];
    memcpy(&task->prefix, l_node_slot_ptr + sizeof(F_ADDR), sizeof(short));
    task->keyno = (short) (task->prefix + task->curr_db_table->key_offset);
    task->fldno = task->key_info[task->keyno].fldno;
    task->cfld_ptr = &task->field_table[task->fldno];
    task->key_len = task->cfld_ptr->fd_len;
    memcpy(key_val, l_node_slot_ptr + task->key_data, task->key_len);
    memcpy(&dba, l_node_slot_ptr + task->key_data + task->key_len, sizeof(DB_ADDR));

    /* divide left node */
    l_node->used_slots = task->mid_slot;

    /* allocate new right node */
    if ((dio_pzalloc(task->keyfile, &r_pg, task) == S_OKAY) &&
        (dio_get(task->keyfile, r_pg, (char **) &r_node, PGHOLD, task) == S_OKAY))
    {
        /* copy slots from left node at slot task->mid_slot+1 into right node */
        r_node->used_slots = (short) (task->max_slots - (task->mid_slot + 1));
        l_node_slot_ptr += task->slot_len;
        memcpy(r_node->slots, l_node_slot_ptr, NODE_WIDTH(r_node));

        dio_touch(task->keyfile, l_pg, PGFREE, task);
        dio_touch(task->keyfile, r_pg, PGFREE, task);

        --task->curkey->level;

        /* expand parent slot to include middle key and new right node ptr */
        expand(key_val, dba, r_pg, task);
    }
    
    psp_freeMemory(key_val, 0);
    task->key_len = save_key_len;
    task->fldno = save_fldno;
    task->cfld_ptr = save_cfld_ptr;
    task->keyno = save_keyno;
    task->prefix = save_prefix;

    return task->db_status;
}


/* ======================================================================
    Split root node
*/
static int INTERNAL_FCN split_root(NODE *node, DB_TASK *task)
{
    F_ADDR  l_pg, r_pg;
    NODE   *l_node,
           *r_node;
    int     slot_pos;
    char   *node_slot_ptr;

    /* allocate two new nodes */
    if ((dio_pzalloc(task->keyfile, &l_pg, task) != S_OKAY) ||
        (dio_get(task->keyfile, l_pg, (char **) &l_node, PGHOLD, task) != S_OKAY))
        return task->db_status;

    if ((dio_pzalloc(task->keyfile, &r_pg, task) != S_OKAY) ||
        (dio_get(task->keyfile, r_pg, (char **) &r_node, PGHOLD, task) != S_OKAY))
    {
        dio_unget(task->keyfile, l_pg, PGFREE, task);
        return task->db_status;
    }

    /* copy 0..task->max_slots/2-1 keys from root into left node */
    l_node->used_slots = task->mid_slot;
    slot_pos = task->mid_slot * task->slot_len;
    memcpy(l_node->slots, node->slots, NODE_WIDTH(l_node));

    /* copy task->max_slots/2+1..task->max_slots from root into right node */
    r_node->used_slots = (short) (task->max_slots - (task->mid_slot + 1));
    node_slot_ptr = &node->slots[slot_pos += task->slot_len];
    memcpy(r_node->slots, node_slot_ptr, NODE_WIDTH(r_node));

    /* copy task->mid_slot into slot[0] of root */
    memcpy(node->slots, node_slot_ptr - task->slot_len, task->slot_len);

    /* copy left page number into p[0] of root */
    memcpy(node->slots, &l_pg, sizeof(F_ADDR));

    /* copy right page number into p[1] of root */
    memcpy(&node->slots[task->slot_len], &r_pg, sizeof(F_ADDR));

    /* reset number of used slots in root */
    node->used_slots = 1;

    dio_touch(task->keyfile, l_pg, PGFREE, task);
    dio_touch(task->keyfile, r_pg, PGFREE, task);
    dio_touch(task->keyfile, ROOT_ADDR, PGFREE, task);

    return task->db_status;
}



/* ======================================================================
    Delete key from B-tree
*/
int INTERNAL_FCN key_delete(int fld, char const *key_val, DB_ADDR dba,
                                     DB_TASK *task)
{
    int stat;

    /* initialize key function operation */
    if (key_init(fld, task) != S_OKAY)
        return task->db_status;

    /* locate key to be deleted */
    if ((stat = key_locpos(key_val, &dba, task)) == S_OKAY)
    {
        if ((stat = delete(task)) == S_OKAY)
        {
            /* save key value and database address for possible repositioning */
            FIELD_ENTRY *kfld_ptr = &task->field_table[fld];
            if (kfld_ptr->fd_type == CHARACTER && kfld_ptr->fd_dim[1] == 0)
                strncpy(task->curkey->keyval, key_val, task->key_len);
            else if (kfld_ptr->fd_type == WIDECHAR && kfld_ptr->fd_dim[1] == 0)
                vwcsncpy((wchar_t *)task->curkey->keyval, (wchar_t *)key_val, task->key_len / sizeof(wchar_t));
            else
                memcpy(task->curkey->keyval, key_val, task->key_len);
            task->curkey->dba = dba;

            /* reset key position */
            key_reset(task->curkey->keyfile, task);
        }
    }

    return task->db_status = stat;
}



/* ======================================================================
    Delete key at current node_path position
*/
static int INTERNAL_FCN delete(DB_TASK *task)
{
    F_ADDR     pg, p_pg, l_pg, r_pg;
    F_ADDR     last_r_pg = 0L;
    int        amt, slot_pos, stat;
    NODE      *node;
    NODE      *p_node;
    NODE      *l_node;
    NODE      *r_node;
    NODE_PATH *np_ptr;
    char      *node_slot_ptr;
    char      *p_node_slot_ptr;
    char      *l_node_slot_ptr;
    char      *r_node_slot_ptr;

    np_ptr = &task->curkey->node_path[task->curkey->level];

    /* read node containing key to be deleted */
    if (dio_get(task->keyfile, pg = np_ptr->node,
                (char **) &node, PGHOLD, task) != S_OKAY)
        return task->db_status;

    /* copy pointer to right sub-tree */
    slot_pos = np_ptr->slot * task->slot_len;
    node_slot_ptr = &node->slots[slot_pos];
    memcpy(&r_pg, node_slot_ptr + task->slot_len, sizeof(F_ADDR));

    if (r_pg != NULL_NODE)
    {
        /* find leftmost descendent of right sub-tree */
        ++np_ptr->slot;
        do
        {
            if (last_r_pg)
                dio_unget(task->keyfile, last_r_pg, NOPGFREE, task);

            if ((stat = dio_get(task->keyfile, (last_r_pg = r_pg),
                                (char **) &r_node, NOPGHOLD, task)) != S_OKAY)
            {
                dio_unget(task->keyfile, pg, PGFREE, task);
                return task->db_status = stat;
            }

            ++task->curkey->level;
            ++np_ptr;
            np_ptr->node = r_pg;
            np_ptr->slot = 0;
            memcpy(&r_pg, r_node->slots, sizeof(F_ADDR));
        } while (r_pg != NULL_NODE);

        /* copy key from leaf into node */
        node_slot_ptr += sizeof(F_ADDR);
        r_node_slot_ptr = &r_node->slots[sizeof(F_ADDR)];
        memcpy(node_slot_ptr, r_node_slot_ptr, task->slot_len - sizeof(F_ADDR));
        dio_unget(task->keyfile, last_r_pg, NOPGFREE, task);
        dio_touch(task->keyfile, pg, PGFREE, task);

        /* set up to delete key from leaf */
        /* (this is more efficient than a recursive call) */
        slot_pos = 0;
        node_slot_ptr = node->slots;
        if (dio_get(task->keyfile, pg = np_ptr->node,
                    (char **) &node, PGHOLD, task) != S_OKAY)
            return task->db_status;
    }

shrink:                        /* delete key from leaf (shrink node ) */
    close_slots(node, slot_pos, 1, task);

    /* check if necessary to adjust nodes */
    if (task->curkey->level > 0 && node->used_slots < task->mid_slot)
    {
        /* read in parent node */
        if (dio_get(task->keyfile, p_pg = (np_ptr - 1)->node,
                    (char **) &p_node, PGHOLD, task) != S_OKAY)
            return task->db_status;

        slot_pos = (np_ptr - 1)->slot * task->slot_len;
        node_slot_ptr = &node->slots[slot_pos];
        if ((np_ptr - 1)->slot == p_node->used_slots)
        {
            /* pg is right node */
            r_pg = pg;
            r_node = node;

            /* parent slot position should bisect left & right nodes */
            --(np_ptr - 1)->slot;
            slot_pos -= task->slot_len;

            /* read left node */
            p_node_slot_ptr = &p_node->slots[slot_pos];
            memcpy(&l_pg, p_node_slot_ptr, sizeof(F_ADDR));
            if (dio_get(task->keyfile, l_pg, (char **) &l_node, PGHOLD, task) != S_OKAY)
                return task->db_status;
        }
        else
        {
            /* pg is left node */
            l_pg = pg;
            l_node = node;

            /* read right node */
            p_node_slot_ptr = &p_node->slots[slot_pos + task->slot_len];
            memcpy(&r_pg, p_node_slot_ptr, sizeof(F_ADDR));
            if (dio_get(task->keyfile, r_pg, (char **) &r_node, PGHOLD, task) != S_OKAY)
                return task->db_status;
        }

        if ((l_node->used_slots + r_node->used_slots + 1) < task->max_slots)
        {
            /* combine left and right nodes */
            if ((task->curkey->level == 1) && (p_node->used_slots == 1))
            {
                /* shrink down to root */
                /* copy right node data into root */
                p_node_slot_ptr = &p_node->slots[task->slot_len];
                memcpy(p_node_slot_ptr, r_node->slots, NODE_WIDTH(r_node));
                p_node->used_slots = (short) (r_node->used_slots + 1);
                r_node->used_slots = 0;
                dio_touch(task->keyfile, r_pg, PGFREE, task);

                /* copy left node data into root */
                open_slots(p_node, 0, l_node->used_slots, task);
                memcpy(p_node->slots, l_node->slots, NODE_WIDTH(l_node));
                l_node->used_slots = 0;
                dio_touch(task->keyfile, l_pg, PGFREE, task);

                dio_touch(task->keyfile, p_pg, PGFREE, task);

                /* free node pages */
                dio_pzdel(task->keyfile, r_pg, task);
                dio_pzdel(task->keyfile, l_pg, task);

                return task->db_status;
            }

            /* open space for l_node->used_slots+1 slots in right node */
            open_slots(r_node, 0, l_node->used_slots + 1, task);

            /* move left node slots into right node */
            amt = NODE_WIDTH(l_node);
            r_node_slot_ptr = r_node->slots;
            memcpy(r_node_slot_ptr, l_node->slots, amt);

            /* move parent slot data into right node */
            r_node_slot_ptr += amt;
            p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
            memcpy(r_node_slot_ptr, p_node_slot_ptr, task->slot_len - sizeof(F_ADDR));

            dio_touch(task->keyfile, r_pg, PGFREE, task);
            dio_touch(task->keyfile, l_pg, PGFREE, task);

            /* delete left node */
            l_node->used_slots = 0;
            if (dio_pzdel(task->keyfile, l_pg, task) != S_OKAY)
                return task->db_status;

            /* decrement level & make parent node current node */
            --task->curkey->level;
            --np_ptr;
            pg = p_pg;
            node = p_node;
            goto shrink;                  /* delete slot from parent */
        }

        /* acquire needed key from sibling */
        if ((l_node->used_slots + 1) < r_node->used_slots)
        {
            /* get key from right node */

            /* move parent slot to end of left node */
            l_node_slot_ptr = &l_node->slots[NODE_WIDTH(l_node)];
            p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
            memcpy(l_node_slot_ptr, p_node_slot_ptr, task->slot_len - sizeof(F_ADDR));

            ++l_node->used_slots;

            /* copy slot 0 child from right node to left node orphan */
            l_node_slot_ptr += task->slot_len - sizeof(F_ADDR);
            r_node_slot_ptr = r_node->slots;
            memcpy(l_node_slot_ptr, r_node_slot_ptr, sizeof(F_ADDR));

            /* move slot 0 of right node to parent */
            r_node_slot_ptr += sizeof(F_ADDR);
            memcpy(p_node_slot_ptr, r_node_slot_ptr, task->slot_len - sizeof(F_ADDR));

            /* delete slot 0 from right node */
            close_slots(r_node, 0, 1, task);
        }
        else if ((r_node->used_slots + 1) < l_node->used_slots)
        {
            /* get key from left node */

            /* open one slot at front of right node */
            open_slots(r_node, 0, 1, task);

            /* move parent slot to slot 0 of right node */
            r_node_slot_ptr = &r_node->slots[sizeof(F_ADDR)];
            p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
            memcpy(r_node_slot_ptr, p_node_slot_ptr, task->slot_len - sizeof(F_ADDR));

            /* move end slot of left node to parent */
            l_node_slot_ptr = &l_node->slots[NODE_WIDTH(l_node) - task->slot_len];
            memcpy(p_node_slot_ptr, l_node_slot_ptr, task->slot_len - sizeof(F_ADDR));