keyfcns.c

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

/***************************************************************************
 *                                                                         *
 * db.*                                                                    *
 * open source database kernel                                             *
 *                                                                         *
 * Copyright (c) 2000 Centura Software Corporation. All rights reserved.   *
 *                                                                         *
 * Use of this software, whether in source code format, or in executable,  *
 * binary object code form, is governed by the CENTURA OPEN SOURCE LICENSE *
 * which is fully described in the LICENSE.TXT file, included within this  *
 * distribution of source code files.                                      * 
 *                                                                         *
 **************************************************************************/

/*---------------------------------------------------------------------------

    db.* Key File/Field Manipulation Functions
    -----------------------------------------
    An implementation of the B-tree indexing method  described in
    "Sorting and Searching: The Art of Computer Programming, Vol III",
    Knuth, Donald E., Addison-Wesley, 1975. pp 473-480.

    A more detailed description of the generic algorithms can be found
    in "Fundamentals of Data Structures in Pascal", Horowitz & Sahni,
    Computer Science Press, 1984. pp 491-512.

    A tutorial survey of B-tree methods can be found in "The Ubiquitous
    B-Tree", Comer, D., ACM Computing Surveys, Vol 11, No. 2, June 1979.

---------------------------------------------------------------------------*/

#include "db.star.h"

/* Internal function prototypes */
static int  INTERNAL_FCN node_search(const char *, DB_ADDR *, NODE *, int *, int *, F_ADDR *, DB_TASK *);
static int  INTERNAL_FCN keycmp(const char *, KEY_SLOT *, DB_ADDR *, DB_TASK *);
static int  INTERNAL_FCN expand(const char *, DB_ADDR, F_ADDR, DB_TASK *);
static int  INTERNAL_FCN split_root(NODE *, DB_TASK *);
static int  INTERNAL_FCN split_node(F_ADDR, NODE *, DB_TASK *);
static int  INTERNAL_FCN delete(DB_TASK *);
static void INTERNAL_FCN open_slots(NODE *, int, int, DB_TASK *);
static void INTERNAL_FCN close_slots(NODE *, int, int, DB_TASK *);
static void INTERNAL_FCN key_found(DB_ADDR *, DB_TASK *);

/* Number of used slots plus orphan */
#define NODE_WIDTH(node)      ((node)->used_slots*task->slot_len + sizeof(F_ADDR))

/* Data definitions used for the B-tree algorithms */
#define ROOT_ADDR    1L             /* node number of root */
#define NULL_NODE    -1L            /* null node pointer */

/* last status value */
#define KEYEOF       -1
#define KEYINIT      0
#define KEYFOUND     1
#define KEYNOTFOUND  2
#define KEYREPOS     3

/* ======================================================================
    Open B-tree key field index processing
*/
int EXTERNAL_FCN key_open(DB_TASK *task)
{
    int           fd_lc;            /* loop control */
    F_ADDR        t;                /* total keys thru level l */
    F_ADDR        max;
    short         l;                /* level number */
    short         i;                /* field subscript */
    FIELD_ENTRY  *fld_ptr;
    KEY_INFO     *ki_ptr;
    FILE_ENTRY   *file_ptr;
    int           old_no_of_keys;

    /* child ptr      key number   */
    task->key_data = sizeof(F_ADDR) + sizeof(short);

    /* count total number of key fields */
    old_no_of_keys = task->no_of_keys;
    for (fd_lc = task->size_fd - task->old_size_fd,
         fld_ptr = &task->field_table[task->old_size_fd];
         --fd_lc >= 0; ++fld_ptr)
    {
        if (fld_ptr->fd_key != NOKEY)
            ++task->no_of_keys;
    }

    if (task->no_of_keys)
    {
        if (alloc_table((void **) &task->key_info, task->no_of_keys *
            sizeof(KEY_INFO), old_no_of_keys * sizeof(KEY_INFO),
            task) != S_OKAY)
            return task->db_status;

        for (i = task->old_size_fd,
             fld_ptr = &task->field_table[task->old_size_fd];
             i < task->size_fd; ++i, ++fld_ptr)
        {
            if (fld_ptr->fd_key != NOKEY)
            {
                ki_ptr = &task->key_info[fld_ptr->fd_keyno];
                ki_ptr->level = 0;
                ki_ptr->lstat = KEYINIT;
                ki_ptr->fldno = i;
                ki_ptr->keyfile = fld_ptr->fd_keyfile;
                ki_ptr->dba = NULL_DBA;
                file_ptr = &task->file_table[fld_ptr->fd_keyfile];
                ki_ptr->keyval = psp_getMemory(file_ptr->ft_slsize, 0);
                if (!ki_ptr->keyval)
                    return (dberr(S_NOMEMORY));

                /* compute maximum possible levels */
                max = MAXRECORDS / file_ptr->ft_slots;
                for (t = file_ptr->ft_slots, l = 1; t < MAXRECORDS; ++l)
                {
                    /* test whether overflow would occur on next iteration */
                    if (t > max)
                        t = MAXRECORDS;
                    else
                        t *= file_ptr->ft_slots;
                }

                ki_ptr->max_lvls = ++l;
                ki_ptr->node_path = (NODE_PATH *) psp_getMemory(l * sizeof(NODE_PATH), 0);

                if (!ki_ptr->node_path)
                    return (dberr(S_NOMEMORY));

                memset(ki_ptr->node_path, 0, l * sizeof(NODE_PATH));
            }
        }
    }        /* end of if (task->no_of_keys) */

    return (task->db_status);
}



/* ======================================================================
    Close key field processing
*/
void INTERNAL_FCN key_close(int dbn, DB_TASK *task)
{
    int           k;
    KEY_INFO     *ki_ptr;
    int           fd_lc;
    int           low, high, total;
    FIELD_ENTRY  *fld_ptr;

    if (task->key_info)
    {
        /* free memory allocated for key functions */
        if (dbn == ALL_DBS)
        {
            for (k = 0, ki_ptr = task->key_info; k < task->no_of_keys; ++k,
                    ++ki_ptr)
            {
                psp_freeMemory(ki_ptr->node_path, 0);
                psp_freeMemory(ki_ptr->keyval, 0);
            }

            psp_freeMemory(task->key_info, 0);

        }
        else
        {
            for ( fd_lc = low = high = 0, fld_ptr = task->field_table;
                  fd_lc < DB_REF(Size_fd) + DB_REF(fd_offset);
                  ++fd_lc, ++fld_ptr)
            {
                if (fld_ptr->fd_key != NOKEY)
                {
                    if (fd_lc < DB_REF(fd_offset))
                        low++;
                    else
                        high++;
                }
            }

            high += low;
            total = task->no_of_keys;

            for (k = low, ki_ptr = &task->key_info[low]; k < high; ++k, ++ki_ptr)
            {
                psp_freeMemory(ki_ptr->node_path, 0);
                psp_freeMemory(ki_ptr->keyval, 0);
            }

            free_table((void **) &task->key_info, low, high, total,
                       sizeof(KEY_INFO), task);
            task->no_of_keys -= (high - low);

            for (k = low, ki_ptr = &task->key_info[low]; k < task->no_of_keys;
                 ++k, ++ki_ptr)
            {
                ki_ptr->keyfile -= task->db_table[dbn].Size_ft;
                ki_ptr->fldno -= task->db_table[dbn].Size_fd;
            }
        }
    }
}


/* ======================================================================
    Initialize key function operation
*/
int EXTERNAL_FCN key_init(int field, DB_TASK *task)
{
    FIELD_ENTRY  *fld_ptr;
    FILE_ENTRY   *file_ptr;

    fld_ptr = &task->field_table[field];

    if (fld_ptr->fd_key == NOKEY)
        return (dberr(S_NOTKEY));

    task->fldno       = (short) field;
    task->cfld_ptr    = fld_ptr;
    task->keyno       = fld_ptr->fd_keyno;
    task->prefix      = (short) (task->keyno - task->curr_db_table->key_offset);
    task->key_len     = fld_ptr->fd_len;
    task->keyfile     = fld_ptr->fd_keyfile;
    file_ptr          = &task->file_table[task->keyfile];
    task->slot_len    = file_ptr->ft_slsize;
    task->max_slots   = file_ptr->ft_slots;
    task->mid_slot    = (short) (task->max_slots / 2);
    task->curkey      = &task->key_info[task->keyno];
    task->unique      = (fld_ptr->fd_key == UNIQUE);
    task->last_keyfld = task->fldno;

    return (task->db_status);
}



/* ======================================================================
    Reset task->key_info last status to reposition keys on file "fno"
*/
int INTERNAL_FCN key_reset(FILE_NO fno, DB_TASK *task)
{
    int        i;
    KEY_INFO  *ki_ptr;

    for (i = 0, ki_ptr = task->key_info; i < task->no_of_keys; ++i, ++ki_ptr)
    {
        if ((fno == task->size_ft || ki_ptr->keyfile == fno) &&
            (ki_ptr->lstat == KEYFOUND || ki_ptr->lstat == KEYNOTFOUND))
            ki_ptr->lstat = KEYREPOS;
    }

    return (task->db_status);
}



/* ======================================================================
    Locate proper key position on B-tree
*/
int EXTERNAL_FCN key_locpos(
    const char *key_val,         /* key search value */
    DB_ADDR    *dba,             /* database address of located key */
    DB_TASK    *task)
{
    NODE      *node;             /* pointer to current node */
    F_ADDR     child;            /* page number of child node */
    F_ADDR     pg;               /* page number of current node */
    F_ADDR     last_page = 0L;   /* last page number */
    int        stat;             /* saves node search status */
    int        slot, slot_pos;
    short      match_lvl;        /* lowest level with duplicate key */
    NODE_PATH *np_ptr;
    char      *node_slot_ptr;

    match_lvl = -1;

    for (task->curkey->level = 0, np_ptr = task->curkey->node_path,
         pg = ROOT_ADDR; ; ++task->curkey->level, ++np_ptr, pg = child)
    {
        /* sanity check for the b-tree being malformed */
        if (task->curkey->level > task->curkey->max_lvls)
            return (dberr(SYS_BADTREE));

        /* read in 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;

        np_ptr->node = pg;
        if (node->used_slots == 0)
        {
            np_ptr->slot = 0;
            task->curkey->lstat = KEYEOF;
            dio_unget(task->keyfile, pg, NOPGFREE, task);

            return (task->db_status = S_NOTFOUND);
        }

        /* search node for key */
        stat = node_search(key_val, ((*dba == NULL_DBA) ? NULL : dba), node,
                           &slot, &slot_pos, &child, task);
        np_ptr->slot = (short) slot;

        node_slot_ptr = &node->slots[slot_pos];
        if (stat == S_OKAY)
        {
            if (task->unique || *dba != NULL_DBA)
                break;

            /* mark level as having matching key */
            match_lvl = task->curkey->level;

            /* save the key value */
            memcpy(&task->key_type, node_slot_ptr, task->slot_len);
        }

        /* if node_search failed, try next level in B-tree - reset db_status */
        if (task->db_status == S_NOTFOUND)
            task->db_status = S_OKAY;

        /* check for end of search */
        if (child == NULL_NODE)
            break;
    }

    if (match_lvl >= 0)
    {
        /* set to lowest duplicate key */
        task->curkey->level = match_lvl;
        stat = S_OKAY;
        task->curkey->lstat = KEYFOUND;
    }
    else if (stat == S_OKAY)
    {
        memcpy(&task->key_type, node_slot_ptr, task->slot_len);
        stat = S_OKAY;
        task->curkey->lstat = KEYFOUND;
    }
    else
    {
        /* key not found -- save key data at a positioned slot.  Note that
           the key data from the "previous" slot is saved but the slot
           number saved is still the "next" key.
        */
        if (np_ptr->slot > 0)
            node_slot_ptr -= task->slot_len;

        memcpy(&task->key_type, node_slot_ptr, task->slot_len);
        task->curkey->lstat = KEYNOTFOUND;
        stat = S_NOTFOUND;
    }

    key_found(*dba == NULL_DBA ? dba : NULL, task);   /* whether exact match or not */

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

    return task->db_status = stat;
}



/* ======================================================================
    Search node for key value
*/
static int INTERNAL_FCN node_search(
    const char   *key_val,      /* key being searched */
    DB_ADDR      *dba,          /* dbaddr included in comparison if not null */
    NODE         *node,         /* node being searched */
    int          *slotno,       /* slot number of key position in node */
    int          *slot_offset,  /* slot position offset */
    F_ADDR       *child,        /* child ptr of located key */
    DB_TASK *task)
{
    int     cmp, i, l, u, slot_pos;
    char   *node_slot_ptr;

    /* perform binary search on node */
    l = 0;
    u = node->used_slots - 1;

    do
    {
        i = (l + u) / 2;
        slot_pos = i * task->slot_len;
        node_slot_ptr = &node->slots[slot_pos];
        cmp = keycmp(key_val, (KEY_SLOT *) node_slot_ptr, dba, task);
        if (cmp < 0)
            u = i - 1;
        else if (cmp > 0)
            l = i + 1;
        else if (i && !task->unique && !dba)
        {
            /* backup to lowest duplicate in node */
            while (keycmp(key_val, (KEY_SLOT *) (node_slot_ptr -= task->slot_len),
                   dba, task) == 0)
            {
                slot_pos -= task->slot_len;
                if (--i == 0)
                    goto have_slot;
            }

            node_slot_ptr += task->slot_len;
            goto have_slot;
        }
        else
            goto have_slot;