db_idx.c

数据库C语言开发工具包,可以方便地移植到嵌入式系统中

/****************************************************************************/
/*                                                                          */
/*                                                                          */
/*      db_idx.c  v1.3  (c) 1987-1990  Ken Harris                           */
/*                                                                          */
/*                                                                          */
/****************************************************************************/
/*                                                                          */
/*      This software is made available on an AS-IS basis. Unrestricted     */
/*      use is granted provided that the copyright notice remains intact.   */
/*      The author makes no warranties expressed or implied.                */
/*                                                                          */
/****************************************************************************/

#include "dblib.h"


/*
 *      db_add_idx  -  Add record to an index file
 */

void db_add_idx(df, user_data)
 DATA_FILE df;
 char *user_data;
{
        FILE_HDR    fh;
        INDEX_HDR ihdr;
        INDEX_REC irec;
        BUFFER     buf;
        char     *rbuf, *src, *dst;
        ushort     rec;
        int        cnt;

        db_error     = 0;

        fh   = (FILE_HDR) df->df_fhdr->buf_data;
        buf  = df->df_buf;
        ihdr = (INDEX_HDR) buf->buf_data;
        rbuf = buf->buf_data + sizeof(struct db_index_hdr);

        if (!fh->fh_root_ptr)
        {       db_get_next_avail(df, buf);
                if (db_error) return;
        }
        else
        {       db_find_insert_idx(df, user_data, fh->fh_key_size);
                if (db_match_blk)
                        if (!(fh->fh_file_stat & DB_DUP_ALLOWED))
                        {       db_error = DB_DUP_NOT_ALLOWED;
                                return;
                        }
        }
                 
        ihdr->idx_rec_cnt++;
        rec = buf->buf_rec_inx;

        db_add_blk = buf->buf_cur_blk;
        db_add_rec = buf->buf_rec_inx;

        if (rec <= ihdr->idx_rec_cnt)
        {       src = rbuf + (rec - 1) * fh->fh_rec_size;
                dst = src + fh->fh_rec_size;
                cnt = (ihdr->idx_rec_cnt - rec + 1) * fh->fh_rec_size;
                memcpy(dst, src, cnt);
        }                             
        
        irec = (INDEX_REC) src;
        irec->idx_idx_ptr = 0;
        dst = (char *) irec + fh->fh_ctl_size;
        memcpy(dst, user_data, fh->fh_data_size);

        fh->fh_rec_cnt++;

        db_split_blk_idx(df);
        if (db_error) return;

        db_put_blk(df, df->df_fhdr);
}
      
/*
 *      db_find_insert_idx  -  Find Insert Point in an index File
 */

void db_find_insert_idx(df, key, key_size)
 DATA_FILE df;
 char *key;                         
 int   key_size;
{
        FILE_HDR    fh;
        INDEX_HDR ihdr;
        INDEX_REC irec;
        BUFFER     buf;
        char     *rbuf, *ikey;
        ulong      blk;
        ushort     rec;
        int          x;
                       

        db_error     = 0;
        db_match_blk = 0;
        db_match_rec = 0;

        fh   = (FILE_HDR) df->df_fhdr->buf_data;
        buf  = df->df_buf;
        ihdr = (INDEX_HDR) buf->buf_data;
        blk  = fh->fh_root_ptr;

        if (!key_size) key_size = fh->fh_key_size;

        while (blk)
        {       db_get_blk(df, blk, buf);
                if (db_error) return;

                rbuf = buf->buf_data + sizeof(struct db_index_hdr);

                for (rec=1; rec <= ihdr->idx_rec_cnt; rec++)
                {       irec = (INDEX_REC) rbuf;
                        ikey = rbuf + fh->fh_ctl_size;

                        x = memcmp(key, ikey, key_size);
        
                        if (x == 0)
                        {       db_match_blk = blk;
                                db_match_rec = rec;
                                blk = irec->idx_idx_ptr;
                                break;
                        }

                        if (x < 0)
                        {       blk = irec->idx_idx_ptr;
                                break;
                        }

                        rbuf += fh->fh_rec_size;

                        if (rec == ihdr->idx_rec_cnt)
                        {       irec = (INDEX_REC) rbuf;
                                blk  = irec->idx_idx_ptr;
                        }
                }        
        }
        buf->buf_rec_inx = rec;
}

/*
 *      db_split_blk_idx  -  Check for a block split
 */

void db_split_blk_idx(df)
 DATA_FILE df;
{
        FILE_HDR   fh;
        BUFFER     buf,  tmp,  aux;
        INDEX_HDR ihdr,  thdr, ahdr;
        INDEX_REC  idx;
        char     *hold, *rbuf, *src,  *dst;
        ushort     cnt,  cnt1,  cnt2;
        ushort     rec,  left, right;

        db_error = 0;

        fh  = (FILE_HDR) df->df_fhdr->buf_data;
        buf = df->df_buf;
        tmp = df->df_tmp;

        ihdr = (INDEX_HDR) buf->buf_data;

        if (ihdr->idx_rec_cnt <= fh->fh_recs_per_blk)
        {       db_put_blk(df, buf);
                return;
        }

        buf        = df->df_tmp;
        tmp        = df->df_buf;
        df->df_buf = buf;
        df->df_tmp = tmp;
        aux        = df->df_aux;

        db_get_next_avail(df, buf);
        if (db_error) return;

        ihdr = (INDEX_HDR) buf->buf_data;
        thdr = (INDEX_HDR) tmp->buf_data;
        ahdr = (INDEX_HDR) aux->buf_data;

        left   = tmp->buf_cur_blk;
        right  = buf->buf_cur_blk;

        cnt1 = thdr->idx_rec_cnt / 2;
        cnt2 = thdr->idx_rec_cnt - (cnt1 + 1);

        ihdr->idx_parent  = thdr->idx_parent;
        ihdr->idx_rec_cnt = cnt2;         

        src = tmp->buf_data + sizeof(struct db_index_hdr)
                                                + (cnt1 + 1) * fh->fh_rec_size;
        dst = buf->buf_data + sizeof(struct db_index_hdr);
        cnt = (cnt2 + 1) * fh->fh_rec_size;
        memcpy(dst, src, cnt);

        db_put_blk(df, buf);
        if (db_error) return;

        if (db_add_blk == tmp->buf_cur_blk)
                if (db_add_rec > cnt1 + 1)
                {       db_add_blk  =  buf->buf_cur_blk;
                        db_add_rec -= cnt1 + 1;         
                }

        rbuf = buf->buf_data + sizeof(struct db_index_hdr);
        if (!thdr->idx_parent)
        {       if (tmp->buf_cur_blk != fh->fh_root_ptr)
                {       db_error = DB_INVALID_INDEX;
                        return;
                }
                db_get_next_avail(df, buf);
                thdr->idx_parent = buf->buf_cur_blk;
                fh->fh_root_ptr  = buf->buf_cur_blk;
                idx              = (INDEX_REC) rbuf;
                rec              = 1;
        }
        else
        {       db_get_blk(df, (long)thdr->idx_parent, buf);
                if (db_error) return;

                for (rec=1; rec <= ihdr->idx_rec_cnt+1; rec++)
                {       idx = (INDEX_REC) rbuf;

                        if (idx->idx_idx_ptr == left)
                                break;

                        rbuf += fh->fh_rec_size;
                }

                if (idx->idx_idx_ptr != left)
                {       db_error = DB_INVALID_INDEX;
                        return;
                }
        }

        idx->idx_idx_ptr = right;

        if (db_add_blk == tmp->buf_cur_blk)
                if (db_add_rec == cnt1 + 1)
                {       db_add_blk =  buf->buf_cur_blk;
                        db_add_rec =  rec;
                }

        src = rbuf;
        dst = rbuf + fh->fh_rec_size;
        cnt = ((ihdr->idx_rec_cnt + 1) - rec + 1) * fh->fh_rec_size;
        memcpy(dst, src, cnt);

        src = tmp->buf_data + sizeof(struct db_index_hdr)
                                         + cnt1 * fh->fh_rec_size;
        dst = rbuf;
        cnt = fh->fh_rec_size;
        memcpy(dst, src, cnt);

        idx->idx_idx_ptr = left;
        ihdr->idx_rec_cnt++;

        thdr->idx_rec_cnt = cnt1;
        db_put_blk(df, tmp);
        if (db_error) return;

        db_get_blk(df, (long) right, tmp);
        if (db_error) return;

        if (thdr->idx_parent != buf->buf_cur_blk)
        {       thdr->idx_parent = buf->buf_cur_blk;
                db_put_blk(df, tmp);
                if (db_error) return;
        }

        rbuf = tmp->buf_data + sizeof(struct db_index_hdr);
        for (cnt=1; cnt <= thdr->idx_rec_cnt + 1; cnt++)
        {       idx = (INDEX_REC) rbuf;

                if (idx->idx_idx_ptr)
                {       db_get_blk(df, (long)idx->idx_idx_ptr, aux);
                        if (db_error) return;

                        ahdr->idx_parent = tmp->buf_cur_blk;
                        db_put_blk(df, aux);
                        if (db_error) return;
                }

                rbuf += fh->fh_rec_size;
        }

        db_split_blk_idx(df);
}

/*
 *      db_read_first_idx  -  Read First Record in an Index File
 */

void db_read_first_idx(df, blk, user_data)                           
 DATA_FILE df;
 int blk;
 char *user_data;
{
        FILE_HDR    fh;
        BUFFER     buf;
        INDEX_HDR ihdr;
        INDEX_REC  idx;
        char      *src;

                    
        db_error = 0;

        if (!blk)
        {       db_error = DB_END_OF_FILE;
                return;
        }

        fh   = (FILE_HDR) df->df_fhdr->buf_data;
        buf  = df->df_buf;
        ihdr = (INDEX_HDR)  buf->buf_data;
        idx  = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr));

        while (blk)
        {       db_get_blk(df, (long) blk, buf);
                if (db_error) return;
         

                if (!ihdr->idx_rec_cnt)
                {       db_error = DB_INVALID_INDEX;
                        return;
                }

                blk = idx->idx_idx_ptr;
        }