keyfcns.c

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

    } while (u >= l);

have_slot:
    if (cmp > 0)
    {
        /* always return next higher slot when not found */
        ++i;
        node_slot_ptr += task->slot_len;
        slot_pos += task->slot_len;
    }

    /* return child pointer from located slot */
    memcpy(child, node_slot_ptr, sizeof(F_ADDR));

    /* return slot number */
    *slotno = i;
    *slot_offset = slot_pos;

    return task->db_status = (cmp == 0 ? S_OKAY : S_NOTFOUND);
}



/* ======================================================================
    Compare key value
*/
static int INTERNAL_FCN keycmp(
    const char *key_val, /* key value */
    KEY_SLOT *slot,      /* pointer to key slot to be compared */
    DB_ADDR *dba,        /* dbaddr included in comparison if not null */
    DB_TASK *task)
{
/*
    returns < 0 if key_val < slot
            > 0 if key_val > slot
            = 0 if key_val == slot
*/
    int cmp;

    if ((cmp = SHORTcmp((char *) &task->prefix, (char *) &slot->keyno)) == 0 &&
        (cmp = fldcmp(task->cfld_ptr, key_val, slot->data, task)) == 0 && dba)
        cmp = ADDRcmp(dba, (DB_ADDR *) &slot->data[task->key_len]);

    return cmp;
}


/* ======================================================================
    Scan thru key field
*/
int EXTERNAL_FCN key_scan(
    int fcn,                        /* next or prev */
    DB_ADDR *dba,                   /* db address of scanned record */
    DB_TASK *task)
{
    F_ADDR     child;
    F_ADDR     last_page;
    int        stat;
    NODE      *node;
    NODE_PATH *np_ptr;
    char      *node_slot_ptr;

    /* If the last d_keyfind() returned S_NOTFOUND, the slot number
       associated with task->curkey is for the "next" key while the keyval
       is for the "previous" key!
    */

    /* locate next key on file */
    switch (task->curkey->lstat)
    {
        case KEYINIT:
        case KEYEOF:
            return key_boundary(((fcn == KEYNEXT) ? KEYFRST : KEYLAST), dba, task);
            /* break; */

        case KEYREPOS:
            /* Note that if (dkeyfind() == S_NOTFOUND) then this call to
               key_locpos() will reset the keyval AND slot to the "previous"
               key.  See comment at start of function.
            */
            stat = key_locpos(task->curkey->keyval, &task->curkey->dba, task);
            if (stat != S_OKAY)
                break;
            /* else FALL THROUGH */

        case KEYFOUND:
            if (fcn == KEYNEXT)
                ++task->curkey->node_path[task->curkey->level].slot;

            break;

        default:
            break;
    }

    np_ptr = &task->curkey->node_path[task->curkey->level];
    if (dio_get(task->keyfile, (last_page = np_ptr->node), (char **) &node,
                NOPGHOLD, task) != S_OKAY)
        return task->db_status;

    node_slot_ptr = &node->slots[np_ptr->slot * task->slot_len];
    memcpy(&child, node_slot_ptr, sizeof(F_ADDR));
    if (child == NULL_NODE)
    {
        if (fcn == KEYPREV)
        {
            --np_ptr->slot;
            node_slot_ptr -= task->slot_len;
        }

        while ((fcn == KEYNEXT && np_ptr->slot >= node->used_slots) ||
               (fcn == KEYPREV && np_ptr->slot < 0))
        {
            if (task->curkey->level <= 0)
            {
                /* return end of file */
                task->curkey->lstat = KEYEOF;
                dio_unget(task->keyfile, last_page, NOPGFREE, task);
                return (task->db_status = S_NOTFOUND);
            }

            --task->curkey->level;
            node_slot_ptr = NULL;
            dio_unget(task->keyfile, last_page, NOPGFREE, task);

            if (dio_get(task->keyfile, (last_page = (--np_ptr)->node),
                        (char **) &node, NOPGHOLD, task) != S_OKAY)
            {
                dio_unget(task->keyfile, last_page, NOPGFREE, task);
                return task->db_status;
            }

            if (fcn == KEYPREV)
                --np_ptr->slot;
        }

        if (node_slot_ptr == NULL)
            node_slot_ptr = &node->slots[np_ptr->slot * task->slot_len];
    }
    else
    {
        do
        {                                /* move down to leaf node */
            dio_unget(task->keyfile, last_page, NOPGFREE, task);
            if (dio_get(task->keyfile, (last_page = child), (char **) &node,
                        NOPGHOLD, task) != S_OKAY)
                return task->db_status;

            ++task->curkey->level;
            (++np_ptr)->node = child;
            if (fcn == KEYNEXT)
            {
                np_ptr->slot = 0;
                node_slot_ptr = node->slots;
            }
            else
            {
                np_ptr->slot = node->used_slots;
                node_slot_ptr = &node->slots[np_ptr->slot * task->slot_len];
            }

            memcpy(&child, node_slot_ptr, sizeof(F_ADDR));
        } while (child != NULL_NODE);
    }

    if (np_ptr->slot == node->used_slots)
    {
        --np_ptr->slot;
        node_slot_ptr -= task->slot_len;
    }

    memcpy(&task->key_type, node_slot_ptr, task->slot_len);
    if (task->key_type.ks.keyno == task->prefix)
    {
        key_found(dba, task);
        task->curkey->lstat = KEYFOUND;
        stat = S_OKAY;
    }
    else
    {
        task->curkey->lstat = KEYEOF;
        stat = S_NOTFOUND;
    }

    dio_unget(task->keyfile, last_page, NOPGFREE, task);

    return task->db_status = stat;
}


/* ======================================================================
    Key has been found.  Save appropriate information
*/
static void INTERNAL_FCN key_found(DB_ADDR *dba, DB_TASK *task)
{
    /* save key value and database address for possible repositioning */
    memcpy(task->curkey->keyval, task->key_type.ks.data, task->key_len);
    memcpy(&task->curkey->dba, &task->key_type.ks.data[task->key_len], sizeof(DB_ADDR));

    /* return found db addr */
    if (dba)
        memcpy(dba, &task->curkey->dba, sizeof(DB_ADDR));
}


/* ======================================================================
    Find key boundary
*/
int EXTERNAL_FCN key_boundary(
    int      fcn,                /* KEYFRST or KEYLAST */
    DB_ADDR *dba,                /* to get dba of first or last key */
    DB_TASK *task)
{
    F_ADDR     pg;               /* node number */
    F_ADDR     last_page = 0L;   /* last page obtained with a dio_get */
    NODE      *node;             /* pointer to node contents in cache */
    int        cmp = 0;          /* keycmp result */
    short      match_lvl;        /* lowest level containing matched key */
    short      lvl;              /* node_path level variable */
    int        slot;             /* slot position in node */
    int        stat;
    NODE_PATH *np_ptr;
    char      *node_slot_ptr;

    if (fcn == KEYFIND)
    {
        task->curkey->lstat = KEYINIT;
        return (task->db_status);
    }

    task->curkey->lstat = KEYNOTFOUND;

    /* traverse B-tree for first or last key with specified prefix */
    match_lvl = -1;
    pg = ROOT_ADDR;

    for (lvl = 0; ; ++lvl)
    {
        /* read next node */
        if (last_page)
            dio_unget(task->keyfile, last_page, NOPGFREE, task);

        if (dio_get(task->keyfile, (last_page = pg),
                    (char **) &node, NOPGHOLD, task) != S_OKAY)
            return task->db_status;

        if (node->used_slots == 0)
        {
            /* must not be anything on file */
            task->curkey->lstat = KEYEOF;
            dio_unget(task->keyfile, last_page, NOPGFREE, task);

            return (task->db_status = S_NOTFOUND);
        }

        if (fcn == KEYFRST)
        {
            for (slot = 0, node_slot_ptr = node->slots; slot < node->used_slots;
                    ++slot, node_slot_ptr += task->slot_len)
            {
                if ((cmp = SHORTcmp((char *) &task->prefix,
                    (char *) (node_slot_ptr + sizeof(F_ADDR)))) <= 0)
                    break;
            }
        }
        else
        {
            /* KEYLAST */
            for (slot = node->used_slots - 1,
                 node_slot_ptr = &node->slots[slot * task->slot_len]; slot >= 0;
                 --slot, node_slot_ptr -= task->slot_len)
            {
                if ((cmp = SHORTcmp((char *) &task->prefix,
                    (char *) (node_slot_ptr + sizeof(F_ADDR)))) >= 0)
                    break;
            }
        }

        /* save node path position */
        np_ptr = &task->curkey->node_path[lvl];
        np_ptr->node = pg;
        np_ptr->slot = (short) slot;

        if (cmp == 0)
        {
            /* save matched level & key value */
            match_lvl = lvl;
            memcpy(&task->key_type, node_slot_ptr, task->slot_len);
        }

        /* fetch appropriate child pointer */
        if (fcn == KEYLAST)
            node_slot_ptr += task->slot_len;

        memcpy(&pg, node_slot_ptr, sizeof(F_ADDR));
        if (pg == NULL_NODE)
            break;
    }

    if (match_lvl >= 0)
    {
        task->curkey->level = match_lvl;
        key_found(dba, task);
        task->curkey->lstat = KEYREPOS;
        stat = S_OKAY;
    }
    else
    {
        /* no keys on file with requested prefix */
        task->curkey->level = 0;
        task->curkey->lstat = KEYEOF;
        stat = S_NOTFOUND;
    }

    dio_unget(task->keyfile, last_page, NOPGFREE, task);

    return task->db_status = stat;
}


/* ======================================================================
    Insert key field into B-tree
*/
int EXTERNAL_FCN key_insert(
    int         fld,                /* key field number */
    const char *key_val,            /* key value */
    DB_ADDR     dba,                /* record's database address */
    DB_TASK    *task)
{
    int stat;

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

    /* locate insertion point */
    if (key_locpos(key_val, &dba, task) == S_NOTFOUND)
    {
        task->db_status = S_OKAY;

        /* expand node to include key */
        if ((stat = expand(key_val, dba, NULL_NODE, 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);
        }

        task->db_status = stat;
    }
    else
    {
        if (task->db_status == S_OKAY)
            dberr(SYS_KEYEXIST);
    }

    return task->db_status;
}



/* ======================================================================
    Expand node for new key
*/
static int INTERNAL_FCN expand(
    const char *key_val,            /* key value */
    DB_ADDR     dba,                /* record's database address */
    F_ADDR      sibling,            /* page number of sibling node */
    DB_TASK    *task)
{
    F_ADDR     pg;
    int        slot_pos;
    NODE      *node;
    NODE_PATH *np_ptr;
    char      *node_slot_ptr;

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

    if (dio_get(task->keyfile, pg = np_ptr->node,
                (char **) &node, PGHOLD, task) != S_OKAY)
        return task->db_status;

    if (node->used_slots >= task->max_slots)
    {
        dio_unget(task->keyfile, pg, PGFREE, task);
        return (dberr(S_KEYERR));
    }

    node_slot_ptr = &node->slots[slot_pos = np_ptr->slot * task->slot_len];
    open_slots(node, slot_pos, 1, task);

    /* copy sibling into opened slot's child pointer */
    memcpy(node_slot_ptr + task->slot_len, &sibling, sizeof(F_ADDR));