btr.c

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

    int ub;                     /* upper-bound of binary search */
    bool foundDup;              /* true if found a duplicate key */

    /* scan current node for key using binary search */
    foundDup = false;
    lb = 0; 
    ub = ct(buf) - 1;
    while (lb <= ub) {
        m = (lb + ub) / 2;
        *mkey = fkey(buf) + ks(m);
        cc = h->comp(key, key(*mkey));
        if (cc < 0)
            /* key less than key[m] */
            ub = m - 1;
        else if (cc > 0)
            /* key greater than key[m] */
            lb = m + 1;
        else {
            /* keys match */
            if (h->dupKeys) {
                switch (mode) {
                case MODE_FIRST:
                    /* backtrack to first key */
                    ub = m - 1;
                    foundDup = true;
                    break;
                case MODE_MATCH:
                    /* rec's must also match */
                    if (rec < rec(*mkey)) {
                        ub = m - 1;
                        cc = CC_LT;
                    } else if (rec > rec(*mkey)) {
                        lb = m + 1;
                        cc = CC_GT;
                    } else {
                        return CC_EQ;
                    }
                    break;
                }
            } else {
                return cc;
            }
        }
    }
    if (ct(buf) == 0) {
        /* empty list */
        *mkey = fkey(buf);
        return CC_LT;
    }
    if (h->dupKeys && (mode == MODE_FIRST) && foundDup) {
        /* next key is first key in set of duplicates */
        *mkey += ks(1);
        return CC_EQ;
    }
    /* didn't find key */
    return cc;
}

static bErrType scatterRoot(void) {
    bufType *gbuf;
    bufType *root;

    /* scatter gbuf to root */

    root = &h->root;
    gbuf = &h->gbuf;
    memcpy(fkey(root), fkey(gbuf), ks(ct(gbuf)));
    childLT(fkey(root)) = childLT(fkey(gbuf));
    ct(root) = ct(gbuf);
    leaf(root) = leaf(gbuf);
    return bErrOk;
}

static bErrType scatter(bufType *pbuf, keyType *pkey, int is, bufType **tmp) {
    bufType *gbuf;              /* gather buf */
    keyType *gkey;              /* gather buf key */
    bErrType rc;                /* return code */
    int iu;                     /* number of tmp's used */
    int k0Min;                  /* min #keys that can be mapped to tmp[0] */
    int knMin;                  /* min #keys that can be mapped to tmp[1..3] */
    int k0Max;                  /* max #keys that can be mapped to tmp[0] */
    int knMax;                  /* max #keys that can be mapped to tmp[1..3] */
    int sw;                     /* shift width */
    int len;                    /* length of remainder of buf */
    int base;                   /* base count distributed to tmps */
    int extra;                  /* extra counts */
    int ct;
    int i;

    /*
     * input:
     *   pbuf                   parent buffer of gathered keys
     *   pkey                   where we insert a key if needed in parent
     *   is                     number of supplied tmps
     *   tmp                    array of tmp's to be used for scattering
     * output:
     *   tmp                    array of tmp's used for scattering
     */

    /* scatter gbuf to tmps, placing 3/4 max in each tmp */

    gbuf = &h->gbuf;
    gkey = fkey(gbuf);
    ct = ct(gbuf);

   /****************************************
    * determine number of tmps to use (iu) *
    ****************************************/
    iu = is;

    /* determine limits */
    if (leaf(gbuf)) {
        /* minus 1 to allow for insertion */
        k0Max= h->maxCt - 1;
        knMax= h->maxCt - 1;
        /* plus 1 to allow for deletion */
        k0Min= (h->maxCt / 2) + 1;
        knMin= (h->maxCt / 2) + 1;
    } else {
        /* can hold an extra gbuf key as it's translated to a LT pointer */
        k0Max = h->maxCt - 1;
        knMax = h->maxCt;
        k0Min = (h->maxCt / 2) + 1;
        knMin = ((h->maxCt+1) / 2) + 1;
    }

    /* calculate iu, number of tmps to use */
    while(1) {
        if (iu == 0 || ct > (k0Max + (iu-1)*knMax)) {
            /* add a buffer */
            if ((rc = assignBuf(allocAdr(), &tmp[iu])) != 0) 
                return rc;
            /* update sequential links */
            if (leaf(gbuf)) {
                /* adjust sequential links */
                if (iu == 0) {
                    /* no tmps supplied when splitting root for first time */
                    prev(tmp[0]) = 0;
                    next(tmp[0]) = 0;
                } else {
                    prev(tmp[iu]) = tmp[iu-1]->adr;
                    next(tmp[iu]) = next(tmp[iu-1]);
                    next(tmp[iu-1]) = tmp[iu]->adr;
                }
            }
            iu++;
            nNodesIns++;
        } else if (iu > 1 && ct < (k0Min + (iu-1)*knMin)) {
            /* del a buffer */
            iu--;
            /* adjust sequential links */
            if (leaf(gbuf) && tmp[iu-1]->adr) {
                next(tmp[iu-1]) = next(tmp[iu]);
            }
            next(tmp[iu-1]) = next(tmp[iu]);
            nNodesDel++;
        } else {
            break;
        }
    }

    /* establish count for each tmp used */
    base = ct / iu;
    extra = ct % iu;
    for (i = 0; i < iu; i++) {
        int n;

        n = base;
        /* distribute extras, one at a time */
        /* don't do to 1st node, as it may be internal and can't hold it */
        if (i && extra) {
            n++;
            extra--;
        }
        ct(tmp[i]) = n;
    }


    /**************************************
     * update sequential links and parent *
     **************************************/
    if (iu != is) {
        /* link last node to next */
        if (leaf(gbuf) && next(tmp[iu-1])) {
            bufType *buf;
            if ((rc = readDisk(next(tmp[iu-1]), &buf)) != 0) return rc;
            prev(buf) = tmp[iu-1]->adr;
            if ((rc = writeDisk(buf)) != 0) return rc;
        }
        /* shift keys in parent */
        sw = ks(iu - is);
        if (sw < 0) {
            len = ks(ct(pbuf)) - (pkey - fkey(pbuf)) + sw;
            memmove(pkey, pkey - sw, len);
        } else {
            len = ks(ct(pbuf)) - (pkey - fkey(pbuf));
            memmove(pkey + sw, pkey, len);
        }
        /* don't count LT buffer for empty parent */
        if (ct(pbuf))
            ct(pbuf) += iu - is;
        else
            ct(pbuf) += iu - is - 1;
    }

   /*******************************
    * distribute keys to children *
    *******************************/
    for (i = 0; i < iu; i++) {

        /* update LT pointer and parent nodes */
        if (leaf(gbuf)) {
            /* update LT, tmp[i] */
            childLT(fkey(tmp[i])) = 0;

            /* update parent */
            if (i == 0) {
                childLT(pkey) = tmp[i]->adr;
            } else {
                memcpy(pkey, gkey, ks(1));
                childGE(pkey) = tmp[i]->adr;
                pkey += ks(1);
            }
        } else {
            if (i == 0) {
                /* update LT, tmp[0] */
                childLT(fkey(tmp[i])) = childLT(gkey);
                /* update LT, parent */
                childLT(pkey) = tmp[i]->adr;
            } else {
                /* update LT, tmp[i] */
                childLT(fkey(tmp[i])) = childGE(gkey);
                /* update parent key */
                memcpy(pkey, gkey, ks(1));
                childGE(pkey) = tmp[i]->adr;
                gkey += ks(1);
                pkey += ks(1);
                ct(tmp[i])--;
            }
        }

        /* install keys, tmp[i] */
        memcpy(fkey(tmp[i]), gkey, ks(ct(tmp[i])));
        leaf(tmp[i]) = leaf(gbuf);

        gkey += ks(ct(tmp[i]));
    }
    leaf(pbuf) = false;

   /************************
    * write modified nodes *
    ************************/
    if ((rc = writeDisk(pbuf)) != 0) return rc;
    for (i = 0; i < iu; i++)
        if ((rc = writeDisk(tmp[i])) != 0) return rc;

    return bErrOk;
}

static bErrType gatherRoot(void) {
    bufType *gbuf;
    bufType *root;

    /* gather root to gbuf */
    root = &h->root;
    gbuf = &h->gbuf;
    memcpy(p(gbuf), root->p, 3 * h->sectorSize);
    leaf(gbuf) = leaf(root);
    ct(root) = 0;
    return bErrOk;
}

static bErrType gather(bufType *pbuf, keyType **pkey, bufType **tmp) {
    bErrType rc;                /* return code */
    bufType *gbuf;
    keyType *gkey;

    /*
     * input:
     *   pbuf                   parent buffer
     *   pkey                   pointer to match key in parent
     * output:
     *   tmp                    buffers to use for scatter
     *   pkey                   pointer to match key in parent
     * returns:
     *   bErrOk                 operation successful
     * notes:
     *   Gather 3 buffers to gbuf.  Setup for subsequent scatter by
     *   doing the following:
     *     - setup tmp buffer array for scattered buffers
     *     - adjust pkey to point to first key of 3 buffers
     */

    /* find 3 adjacent buffers */
    if (*pkey == lkey(pbuf))
        *pkey -= ks(1);
    if ((rc = readDisk(childLT(*pkey), &tmp[0])) != 0) return rc;
    if ((rc = readDisk(childGE(*pkey), &tmp[1])) != 0) return rc;
    if ((rc = readDisk(childGE(*pkey + ks(1)), &tmp[2])) != 0) return rc;

    /* gather nodes to gbuf */
    gbuf = &h->gbuf;
    gkey = fkey(gbuf);

    /* tmp[0] */
    childLT(gkey) = childLT(fkey(tmp[0]));
    memcpy(gkey, fkey(tmp[0]), ks(ct(tmp[0])));
    gkey += ks(ct(tmp[0]));
    ct(gbuf) = ct(tmp[0]);

    /* tmp[1] */
    if (!leaf(tmp[1])) {
        memcpy(gkey, *pkey, ks(1));
        childGE(gkey) = childLT(fkey(tmp[1]));
        ct(gbuf)++;
        gkey += ks(1);
    }
    memcpy(gkey, fkey(tmp[1]), ks(ct(tmp[1])));
    gkey += ks(ct(tmp[1]));
    ct(gbuf) += ct(tmp[1]);

    /* tmp[2] */
    if (!leaf(tmp[2])) {
        memcpy(gkey, *pkey+ks(1), ks(1));
        childGE(gkey) = childLT(fkey(tmp[2]));
        ct(gbuf)++;
        gkey += ks(1);
    }
    memcpy(gkey, fkey(tmp[2]), ks(ct(tmp[2])));
    ct(gbuf) += ct(tmp[2]);

    leaf(gbuf) = leaf(tmp[0]);

    return bErrOk;
}

bErrType bOpen(bOpenType info, bHandleType *handle) {
    bErrType rc;                /* return code */
    int bufCt;                  /* number of tmp buffers */
    bufType *buf;               /* buffer */
    int maxCt;                  /* maximum number of keys in a node */
    bufType *root;
    int i;
    nodeType *p;

    if ((info.sectorSize < sizeof(hNode)) || (info.sectorSize % 4))
        return bErrSectorSize;

    /* determine sizes and offsets */
    /* leaf/n, prev, next, [childLT,key,rec]... childGE */
    /* ensure that there are at least 3 children/parent for gather/scatter */
    maxCt = info.sectorSize - (sizeof(nodeType) - sizeof(keyType));
    maxCt /= sizeof(bAdrType) + info.keySize + sizeof(eAdrType);
    if (maxCt < 6) return bErrSectorSize;

    /* copy parms to hNode */
    if ((h = malloc(sizeof(hNode))) == NULL) return error(bErrMemory);
    memset(h, 0, sizeof(hNode));
    h->keySize = info.keySize;
    h->dupKeys = info.dupKeys;
    h->sectorSize = info.sectorSize;
    h->comp = info.comp;

    /* childLT, key, rec */
    h->ks = sizeof(bAdrType) + h->keySize + sizeof(eAdrType);
    h->maxCt = maxCt;

    /* Allocate buflist.
     * During insert/delete, need simultaneous access to 7 buffers:
     *  - 4 adjacent child bufs
     *  - 1 parent buf
     *  - 1 next sequential link
     *  - 1 lastGE
     */
    bufCt = 7;
    if ((h->malloc1 = malloc(bufCt * sizeof(bufType))) == NULL) 
        return error(bErrMemory);
    buf = h->malloc1;

    /*
     * Allocate bufs.
     * We need space for the following:
     *  - bufCt buffers, of size sectorSize
     *  - 1 buffer for root, of size 3*sectorSize
     *  - 1 buffer for gbuf, size 3*sectorsize + 2 extra keys
     *    to allow for LT pointers in last 2 nodes when gathering 3 full nodes
     */
    if ((h->malloc2 = malloc((bufCt+6) * h->sectorSize + 2 * h->ks)) == NULL) 
        return error(bErrMemory);
    p = h->malloc2;

    /* initialize buflist */
    h->bufList.next = buf;
    h->bufList.prev = buf + (bufCt - 1);
    for (i = 0; i < bufCt; i++) {
        buf->next = buf + 1;
        buf->prev = buf - 1;
        buf->modified = false;
        buf->valid = false;
        buf->p = p;
        p = (nodeType *)((char *)p + h->sectorSize);
        buf++;
    }
    h->bufList.next->prev = &h->bufList;
    h->bufList.prev->next = &h->bufList;

    /* initialize root */
    root = &h->root;
    root->p = p;
    p = (nodeType *)((char *)p + 3*h->sectorSize);
    h->gbuf.p = p;      /* done last to include extra 2 keys */

    h->curBuf = NULL;
    h->curKey = NULL;

    /* initialize root */
    if ((h->fp = fopen(info.iName, "r+b")) != NULL) {
        /* open an existing database */
        if ((rc = readDisk(0, &root)) != 0) return rc;
        if (fseek(h->fp, 0, SEEK_END)) return error(bErrIO);
        if ((h->nextFreeAdr = ftell(h->fp)) == -1) return error(bErrIO);
    } else if ((h->fp = fopen(info.iName, "w+b")) != NULL) {
        /* initialize root */
        memset(root->p, 0, 3*h->sectorSize);
        leaf(root) = 1;
        h->nextFreeAdr = 3 * h->sectorSize;