btr.c

排序算法、字典和B-树的C++语言实现 代码内容 包括以下算法： qui.c sort: quicksort qsort.c sort: qsort ins.c sort: insert

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>

/*
 * this file is divided into sections:
 *   stuff you'll probably want to place in a .h file...
 *     implementation dependent
 *       - you'll probably have to change something here
 *     implementation independent
 *       - types and function prototypes that typically go in a .h file
 *     function prototypes
 *       - prototypes for user functions
 *   internals
 *     - local functions
 *     - user functions
 *   main()
 */

/****************************
 * implementation dependent *
 ****************************/
typedef long eAdrType;          /* record address for external record */
typedef long bAdrType;          /* record address for btree node */

#define CC_EQ           0
#define CC_GT           1
#define CC_LT          -1

/* compare two keys and return:
 *    CC_LT     key1 < key2
 *    CC_GT     key1 > key2
 *    CC_EQ     key1 = key2
 */
typedef int (*bCompType)(const void *key1, const void *key2);

/******************************
 * implementation independent *
 ******************************/

/* statistics */
int maxHeight;          /* maximum height attained */
int nNodesIns;          /* number of nodes inserted */
int nNodesDel;          /* number of nodes deleted */
int nKeysIns;           /* number of keys inserted */
int nKeysDel;           /* number of keys deleted */
int nDiskReads;         /* number of disk reads */
int nDiskWrites;        /* number of disk writes */

/* line number for last IO or memory error */
int bErrLineNo;

typedef enum {false, true} bool;
typedef enum {
    bErrOk,
    bErrKeyNotFound,
    bErrDupKeys,
    bErrSectorSize,
    bErrFileNotOpen,
    bErrFileExists,
    bErrIO,
    bErrMemory 
} bErrType;

typedef void *bHandleType;

typedef struct {                /* info for bOpen() */
    char *iName;                /* name of index file */
    int keySize;                /* length, in bytes, of key */
    bool dupKeys;               /* true if duplicate keys allowed */
    int sectorSize;             /* size of sector on disk */
    bCompType comp;             /* pointer to compare function */
} bOpenType;

/***********************
 * function prototypes *
 ***********************/
bErrType bOpen(bOpenType info, bHandleType *handle);
    /*
     * input:
     *   info                   info for open
     * output:
     *   handle                 handle to btree, used in subsequent calls
     * returns:
     *   bErrOk                 open was successful
     *   bErrMemory             insufficient memory
     *   bErrSectorSize         sector size too small or not 0 mod 4
     *   bErrFileNotOpen        unable to open index file
     */

bErrType bClose(bHandleType handle);
    /*
     * input:
     *   handle                 handle returned by bOpen
     * returns:
     *   bErrOk                 file closed, resources deleted
     */

bErrType bInsertKey(bHandleType handle, void *key, eAdrType rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     *   key                    key to insert
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrDupKeys            duplicate keys (and info.dupKeys = false)
     * notes:
     *   If dupKeys is false, then all records inserted must have a
     *   unique key.  If dupkeys is true, then duplicate keys are
     *   allowed, but they must all have unique record addresses.
     *   In this case, record addresses are included in internal
     *   nodes to generate a "unique" key.
     */

bErrType bDeleteKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     *   key                    key to delete
     *   rec                    record address of key to delete
     * output:
     *   rec                    record address deleted
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     * notes:
     *   If dupKeys is false, all keys are unique, and rec is not used
     *   to determine which key to delete.  If dupKeys is true, then
     *   rec is used to determine which key to delete.
     */

bErrType bFindKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     *   key                    key to find
     * output:
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     */

bErrType bFindFirstKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     * output:
     *   key                    first key in sequential set
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     */

bErrType bFindLastKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     * output:
     *   key                    last key in sequential set
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     */

bErrType bFindNextKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     * output:
     *   key                    key found
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     */

bErrType bFindPrevKey(bHandleType handle, void *key, eAdrType *rec);
    /*
     * input:
     *   handle                 handle returned by bOpen
     * output:
     *   key                    key found
     *   rec                    record address
     * returns:
     *   bErrOk                 operation successful
     *   bErrKeyNotFound        key not found
     */

/*************
 * internals *
 *************/

/*
 *  algorithm:
 *    A B+tree implementation, with keys stored in internal nodes,
 *    and keys/record addresses stored in leaf nodes.  Each node is
 *    one sector in length, except the root node whose length is
 *    3 sectors.  When traversing the tree to insert a key, full
 *    children are adjusted to make room for possible new entries.
 *    Similarly, on deletion, half-full nodes are adjusted to allow for
 *    possible deleted entries.  Adjustments are first done by 
 *    examining 2 nearest neighbors at the same level, and redistibuting
 *    the keys if possible.  If redistribution won't solve the problem,
 *    nodes are split/joined as needed.  Typically, a node is 3/4 full.
 *    On insertion, if 3 nodes are full, they are split into 4 nodes,
 *    each 3/4 full.  On deletion, if 3 nodes are 1/2 full, they are
 *    joined to create 2 nodes 3/4 full.
 *
 *    A LRR (least-recently-read) buffering scheme for nodes is used to
 *    simplify storage management, and, assuming some locality of reference,
 *    improve performance.
 *
 *    To simplify matters, both internal nodes and leafs contain the
 *    same fields.
 *   
 */

/* macros for addressing fields */

/* primitives */
#define bAdr(p) *(bAdrType *)(p)
#define eAdr(p) *(eAdrType *)(p)

/* based on k = &[key,rec,childGE] */
#define childLT(k) bAdr((char *)k - sizeof(bAdrType))
#define key(k) (k)
#define rec(k) eAdr((char *)(k) + h->keySize)
#define childGE(k) bAdr((char *)(k) + h->keySize + sizeof(eAdrType))

/* based on b = &bufType */
#define leaf(b) b->p->leaf
#define ct(b) b->p->ct
#define next(b) b->p->next
#define prev(b) b->p->prev
#define fkey(b) &b->p->fkey
#define lkey(b) (fkey(b) + ks((ct(b) - 1)))
#define p(b) (char *)(b->p)

/* shortcuts */
#define ks(ct) ((ct) * h->ks)

typedef char keyType;           /* keys entries are treated as char arrays */

typedef struct {
    unsigned int leaf:1;        /* first bit = 1 if leaf */
    unsigned int ct:15;         /* count of keys present */
    bAdrType prev;              /* prev node in sequence (leaf) */
    bAdrType next;              /* next node in sequence (leaf) */
    bAdrType childLT;           /* child LT first key */
    /* ct occurrences of [key,rec,childGE] */
    keyType fkey;               /* first occurrence */
} nodeType;

typedef struct bufTypeTag {     /* location of node */
    struct bufTypeTag *next;    /* next */
    struct bufTypeTag *prev;    /* previous */
    bAdrType adr;               /* on disk */
    nodeType *p;                /* in memory */
    bool valid;                 /* true if buffer contents valid */
    bool modified;              /* true if buffer modified */
} bufType;

/* one node for each open handle */
typedef struct hNodeTag {
    struct hNodeTag *prev;      /* previous node */
    struct hNodeTag *next;      /* next node */
    FILE *fp;                   /* idx file */
    int keySize;                /* key length */
    bool dupKeys;               /* true if duplicate keys */
    int sectorSize;             /* block size for idx records */
    bCompType comp;             /* pointer to compare routine */
    bufType root;               /* root of b-tree, room for 3 sets */
    bufType bufList;            /* head of buf list */
    void *malloc1;              /* malloc'd resources */
    void *malloc2;              /* malloc'd resources */
    bufType gbuf;               /* gather buffer, room for 3 sets */
    bufType *curBuf;            /* current location */
    keyType *curKey;            /* current key in current node */
    unsigned int maxCt;         /* minimum # keys in node */
    int ks;                     /* sizeof key entry */
    bAdrType nextFreeAdr;       /* next free b-tree record address */
} hNode;

static hNode hList;             /* list of hNodes */
static hNode *h;                /* current hNode */

#define error(rc) lineError(__LINE__, rc)

static bErrType lineError(int lineno, bErrType rc) {
    if (rc == bErrIO || rc == bErrMemory)
        if (!bErrLineNo) 
            bErrLineNo = lineno;
    return rc;
}

static bAdrType allocAdr(void) {
    bAdrType adr;
    adr = h->nextFreeAdr;
    h->nextFreeAdr += h->sectorSize;
    return adr;
}

static bErrType flush(bufType *buf) {
    int len;            /* number of bytes to write */

    /* flush buffer to disk */
    len = h->sectorSize;
    if (buf->adr == 0) len *= 3;        /* root */
    if (fseek(h->fp, buf->adr, SEEK_SET)) return error(bErrIO);
    if (fwrite(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
    buf->modified = false;
    nDiskWrites++;
    return bErrOk;
}

static bErrType flushAll(void) {
    bErrType rc;                /* return code */
    bufType *buf;               /* buffer */

    if (h->root.modified)
        if ((rc = flush(&h->root)) != 0) return rc;

    buf = h->bufList.next;
    while (buf != &h->bufList) {
        if (buf->modified)
            if ((rc = flush(buf)) != 0) return rc;
        buf = buf->next;
    }
}

static bErrType assignBuf(bAdrType adr, bufType **b) {
    /* assign buf to adr */
    bufType *buf;               /* buffer */
    bErrType rc;                /* return code */

    if (adr == 0) {
        *b = &h->root;
        return bErrOk;
    }

    /* search for buf with matching adr */
    buf = h->bufList.next;
    while (buf->next != &h->bufList) {
        if (buf->valid && buf->adr == adr) break;
        buf = buf->next;
    }

    /* either buf points to a match, or it's last one in list (LRR) */
    if (buf->valid) {
        if (buf->adr != adr) {
            if (buf->modified) {
                if ((rc = flush(buf)) != 0) return rc;
            }
            buf->adr = adr;
            buf->valid = false;
        }
    } else {
        buf->adr = adr;
    }

    /* remove from current position and place at front of list */
    buf->next->prev = buf->prev;
    buf->prev->next = buf->next;
    buf->next = h->bufList.next;
    buf->prev = &h->bufList;
    buf->next->prev = buf;
    buf->prev->next = buf;
    *b = buf;
    return bErrOk;
}

static bErrType writeDisk(bufType *buf) {
    /* write buf to disk */
    buf->valid = true;
    buf->modified = true;
    return bErrOk;
}

static bErrType readDisk(bAdrType adr, bufType **b) {
    /* read data into buf */
    int len;
    bufType *buf;               /* buffer */
    bErrType rc;                /* return code */

    if ((rc = assignBuf(adr, &buf)) != 0) return rc;
    if (!buf->valid) {
        len = h->sectorSize;
        if (adr == 0) len *= 3;         /* root */
        if (fseek(h->fp, adr, SEEK_SET)) return error(bErrIO);
        if (fread(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
        buf->modified = false;
        buf->valid = true;
        nDiskReads++;
    }
    *b = buf;
    return bErrOk;
}

typedef enum { MODE_FIRST, MODE_MATCH } modeEnum;

static int search(
    bufType *buf,
    void *key, 
    eAdrType rec, 
    keyType **mkey,
    modeEnum mode) {
    /*
     * input:
     *   p                      pointer to node
     *   key                    key to find
     *   rec                    record address (dupkey only)
     * output:
     *   k                      pointer to keyType info
     * returns:
     *   CC_EQ                  key = mkey
     *   CC_LT                  key < mkey
     *   CC_GT                  key > mkey
     */
    int cc;                     /* condition code */
    int m;                      /* midpoint of search */
    int lb;                     /* lower-bound of binary search */