home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1990 / 12 / stevens.asc < prev    next >
Text File  |  1990-11-15  |  26KB  |  959 lines
  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /* --------------- database.h ---------------------- */
  8. #define MXKEYLEN 80  /* maximum key length for indexes     */
  9.  
  10. #define ERROR -1
  11. #define OK 0
  12.  
  13. #ifndef TRUE
  14. #define TRUE 1
  15. #define FALSE 0
  16. #endif
  17.  
  18. typedef long RPTR;  /* B-tree node and file address     */
  19. void dberror(void);
  20.  
  21. /* ----------- dbms error codes for errno return ------ */
  22. enum dberrors {
  23.    D_OM,      /* out of memory                        */
  24.    D_IOERR    /* i/o error                            */
  25. };
  26.  
  27.  
  28. [LISTING TWO
  29.  
  30. /* --------------- btree.h ---------------------- */
  31. #define MXTREES 20
  32. #define NODE 512       /* length of a B-tree node          */
  33. #define ADR sizeof(RPTR)
  34.  
  35. /* ---------- btree prototypes -------------- */
  36. int btree_init(char *ndx_name);
  37. int btree_close(int tree);
  38. void build_b(char *name, int len);
  39. RPTR locate(int tree, char *k);
  40. int deletekey(int tree, char *x, RPTR ad);
  41. int insertkey(int tree, char *x, RPTR ad, int unique);
  42. RPTR nextkey(int tree);
  43. RPTR prevkey(int tree);
  44. RPTR firstkey(int tree);
  45. RPTR lastkey(int tree);
  46. void keyval(int tree, char *ky);
  47. RPTR currkey(int tree);
  48.  
  49. /* --------- the btree node structure -------------- */
  50. typedef struct treenode    {
  51.    int nonleaf;      /* 0 if leaf, 1 if non-leaf           */
  52.    RPTR prntnode;    /* parent node                        */
  53.    RPTR lfsib;       /* left sibling node                  */                  
  54.    RPTR rtsib;       /* right sibling node                 */
  55.    int keyct;        /* number of keys                     */
  56.    RPTR key0;        /* node # of keys < 1st key this node */
  57.    char keyspace [NODE - ((sizeof(int) * 2) + (ADR * 4))];
  58.    char spil [MXKEYLEN];  /* for insertion excess */
  59. } BTREE;
  60.  
  61. /* ---- the structure of the btree header node --------- */
  62. typedef struct treehdr    {
  63.    RPTR rootnode;            /* root node number     */
  64.    int keylength;            /* length of a key      */
  65.    int m;                    /* max keys/node        */
  66.    RPTR rlsed_node;          /* next released node   */
  67.    RPTR endnode;             /* next unassigned node */
  68.    int locked;               /* if btree is locked   */
  69.    RPTR leftmost;            /* left-most node       */
  70.    RPTR rightmost;           /* right-most node      */
  71. } HEADER;
  72.  
  73.  
  74.  
  75. [LISTING THREE]
  76.  
  77.  
  78. /* --------------------- btree.c ----------------------- */
  79. #include <stdio.h>
  80. #include <errno.h>
  81. #include <string.h>
  82. #include <stdlib.h>
  83. #include "database.h"
  84. #include "btree.h"
  85.  
  86. #define KLEN bheader[trx].keylength
  87. #define ENTLN (KLEN+ADR)
  88.  
  89. HEADER bheader[MXTREES];
  90. BTREE trnode;
  91.  
  92. static FILE *fp[MXTREES];      /* file pointers to indexes   */
  93. static RPTR currnode[MXTREES]; /* node number of current key */
  94. static int currkno[MXTREES];   /* key number of current key  */
  95. static int trx;                /* current tree               */
  96.  
  97. /* --------- local prototypes ---------- */
  98. static int btreescan(RPTR *t, char *k, char **a);
  99. static int nodescan(char *keyvalue, char **nodeadr);
  100. static int compare_keys(char *a, char *b);
  101. static RPTR fileaddr(RPTR t, char *a);
  102. static RPTR leaflevel(RPTR *t, char **a, int *p);
  103. static void implode(BTREE *left, BTREE *right);
  104. static void redist(BTREE *left, BTREE *right);
  105. static void adopt(void *ad, int kct, RPTR newp);
  106. static RPTR nextnode(void);
  107. static RPTR scannext(RPTR *p, char **a);
  108. static RPTR scanprev(RPTR *p, char **a);
  109. static char *childptr(RPTR left, RPTR parent, BTREE *btp);
  110. static void read_node(RPTR nd, void *bf);
  111. static void write_node(RPTR nd, void *bf);
  112. static void bseek(RPTR nd);
  113. static void memerr(void);
  114.  
  115. /* -------- initiate b-tree processing ---------- */
  116. int btree_init(char *ndx_name)
  117. {
  118.    for (trx = 0; trx < MXTREES; trx++)
  119.        if (fp[trx] == NULL)
  120.            break;
  121.    if (trx == MXTREES)
  122.        return ERROR;
  123.    if ((fp[trx] = fopen(ndx_name, "rb+")) == NULL)
  124.        return ERROR;
  125.    fread(&bheader[trx], sizeof(HEADER), 1, fp[trx]);
  126.    /* --- if this btree is locked, something is amiss --- */
  127.    if (bheader[trx].locked)    {
  128.        fclose(fp[trx]);
  129.        fp[trx] = NULL;
  130.        return ERROR;
  131.    }
  132.    /* ------- lock the btree --------- */
  133.    bheader[trx].locked = TRUE;
  134.    fseek(fp[trx], 0L, SEEK_SET);
  135.    fwrite(&bheader[trx], sizeof(HEADER), 1, fp[trx]);
  136.    currnode[trx] = 0;
  137.    currkno[trx] = 0;
  138.    return trx;
  139. }
  140.  
  141. /* ----------- terminate b tree processing ------------- */
  142. int btree_close(int tree)
  143. {
  144.    if (tree >= MXTREES || fp[tree] == 0)
  145.        return ERROR;
  146.    bheader[tree].locked = FALSE;
  147.    fseek(fp[tree], 0L, SEEK_SET);
  148.    fwrite(&bheader[tree], sizeof(HEADER), 1, fp[tree]);
  149.    fclose(fp[tree]);
  150.    fp[tree] = NULL;
  151.    return OK;
  152. }
  153.  
  154. /* --------Build a new b-tree ------------------ */
  155. void build_b(char *name, int len)
  156. {
  157.    HEADER *bhdp;
  158.    FILE *fp;
  159.  
  160.    if ((bhdp = malloc(NODE)) == NULL)
  161.        memerr();
  162.    memset(bhdp, '\0', NODE);
  163.    bhdp->keylength = len;
  164.    bhdp->m = ((NODE-((sizeof(int)*2)+(ADR*4)))/(len+ADR));
  165.    bhdp->endnode = 1;
  166.    remove(name);
  167.    fp = fopen(name, "wb");
  168.    fwrite(bhdp, NODE, 1, fp);
  169.    fclose(fp);
  170.    free(bhdp);
  171. }
  172.  
  173. /* --------------- Locate key in the b-tree -------------- */
  174. RPTR locate(int tree, char *k)
  175. {
  176.    int i, fnd = FALSE;
  177.    RPTR t, ad;
  178.    char *a;
  179.  
  180.    trx = tree;
  181.    t = bheader[trx].rootnode;
  182.    if (t)    {
  183.        read_node(t, &trnode);
  184.        fnd = btreescan(&t, k, &a);
  185.        ad = leaflevel(&t, &a, &i);
  186.        if (i == trnode.keyct + 1)    {
  187.            i = 0;
  188.            t = trnode.rtsib;
  189.        }
  190.        currnode[trx] = t;
  191.        currkno[trx] = i;
  192.    }
  193.    return fnd ? ad : 0;
  194. }
  195.  
  196. /* ----------- Search tree ------------- */
  197. static int btreescan(RPTR *t, char *k, char **a)
  198. {
  199.    int nl;
  200.    do    {
  201.        if (nodescan(k, a))    {
  202.            while (compare_keys(*a, k) == FALSE)
  203.                if (scanprev(t, a) == 0)
  204.                    break;
  205.            if (compare_keys(*a, k))
  206.                scannext(t, a);
  207.            return TRUE;
  208.        }
  209.        nl = trnode.nonleaf;
  210.        if (nl)    {
  211.              *t = *((RPTR *) (*a - ADR));
  212.            read_node(*t, &trnode);
  213.        }
  214.    }    while (nl);
  215.    return FALSE;
  216. }
  217.  
  218. /* ------------------ Search node ------------ */
  219. static int nodescan(char *keyvalue, char **nodeadr)
  220. {
  221.    int i;
  222.    int result;
  223.  
  224.    *nodeadr = trnode.keyspace;
  225.    for (i = 0; i < trnode.keyct; i++)    {
  226.        result = compare_keys(keyvalue, *nodeadr);
  227.        if (result == FALSE)
  228.            return TRUE;
  229.        if (result < 0)
  230.            return FALSE;
  231.        *nodeadr += ENTLN;
  232.    }
  233.    return FALSE;
  234. }
  235.  
  236. /* ------------- Compare keys ----------- */
  237. static int compare_keys(char *a, char *b)
  238. {
  239.    int len = KLEN, cm;
  240.  
  241.    while (len--)
  242.        if ((cm = (int) *a++ - (int) *b++) != 0)
  243.            break;
  244.    return cm;
  245. }
  246.  
  247. /* ------------ Compute current file address  ------------ */
  248. static RPTR fileaddr(RPTR t, char *a)
  249. {
  250.    RPTR cn, ti;
  251.    int i;
  252.  
  253.    ti = t;
  254.    cn = leaflevel(&ti, &a, &i);
  255.    read_node(t, &trnode);
  256.    return cn;
  257. }
  258.  
  259. /* ---------------- Navigate down to leaf level ----------- */
  260. static RPTR leaflevel(RPTR *t, char **a, int *p)
  261. {
  262.    if (trnode.nonleaf == FALSE)    { /* already at a leaf? */
  263.        *p = (*a - trnode.keyspace) / ENTLN + 1;
  264.        return *((RPTR *) (*a + KLEN));
  265.    }
  266.    *p = 0;
  267.    *t = *((RPTR *) (*a + KLEN));
  268.    read_node(*t, &trnode);
  269.    *a = trnode.keyspace;
  270.    while (trnode.nonleaf)    {
  271.        *t = trnode.key0;
  272.        read_node(*t, &trnode);
  273.    }
  274.    return trnode.key0;
  275. }
  276.  
  277. /* -------------- Delete a key  ------------- */
  278. int deletekey(int tree, char *x, RPTR ad)
  279. {
  280.    BTREE *qp, *yp;
  281.    int rt_len, comb;
  282.    RPTR p, adr, q, *b, y, z;
  283.    char *a;
  284.  
  285.    trx = tree;
  286.    if (trx >= MXTREES || fp[trx] == 0)
  287.        return ERROR;
  288.    p = bheader[trx].rootnode;
  289.    if (p == 0)
  290.        return OK;
  291.    read_node(p, &trnode);
  292.    if (btreescan(&p, x, &a) == FALSE)
  293.        return OK;
  294.    adr = fileaddr(p, a);
  295.    while (adr != ad)    {
  296.        adr = scannext(&p, &a);
  297.        if (compare_keys(a, x))
  298.            return OK;
  299.    }
  300.    if (trnode.nonleaf)    {
  301.        b = (RPTR *) (a + KLEN);
  302.        q = *b;
  303.        if ((qp = malloc(NODE)) == NULL)
  304.            memerr();
  305.        read_node(q, qp);
  306.        while (qp->nonleaf)    {
  307.            q = qp->key0;
  308.            read_node(q, qp);
  309.        }
  310.    /* Move the left-most key from the leaf
  311.                        to where the deleted key is */
  312.        memmove(a, qp->keyspace, KLEN);
  313.        write_node(p, &trnode);
  314.        p = q;
  315.        trnode = *qp;
  316.        a = trnode.keyspace;
  317.        b = (RPTR *) (a + KLEN);
  318.        trnode.key0 = *b;
  319.        free(qp);
  320.    }
  321.    currnode[trx] = p;
  322.    currkno[trx] = (a - trnode.keyspace) / ENTLN;
  323.    rt_len = (trnode.keyspace + (bheader[trx].m * ENTLN)) - a;
  324.    memmove(a, a+ENTLN, rt_len);
  325.    memset(a+rt_len, '\0', ENTLN);
  326.    trnode.keyct--;
  327.    if (currkno[trx] > trnode.keyct)    {
  328.        if (trnode.rtsib)    {
  329.            currnode[trx] = trnode.rtsib;
  330.            currkno[trx] = 0;
  331.        }
  332.        else
  333.            currkno[trx]--;
  334.    }
  335.    while (trnode.keyct <= bheader[trx].m / 2 &&
  336.                           p != bheader[trx].rootnode)    {
  337.        comb = FALSE;
  338.        z = trnode.prntnode;
  339.        if ((yp = malloc(NODE)) == NULL)
  340.            memerr();
  341.        if (trnode.rtsib)    {
  342.            y = trnode.rtsib;
  343.            read_node(y, yp);
  344.            if (yp->keyct + trnode.keyct <
  345.                    bheader[trx].m && yp->prntnode == z)    {
  346.                comb = TRUE;
  347.                implode(&trnode, yp);
  348.            }
  349.        }
  350.        if (comb == FALSE && trnode.lfsib)    {
  351.            y = trnode.lfsib;
  352.            read_node(y, yp);
  353.            if (yp->prntnode == z)    {
  354.                if (yp->keyct + trnode.keyct <
  355.                                    bheader[trx].m) {
  356.                    comb = TRUE;
  357.                    implode(yp, &trnode);
  358.                }
  359.                else    {
  360.                    redist(yp, &trnode);
  361.                    write_node(p, &trnode);
  362.                    write_node(y, yp);
  363.                    free(yp);
  364.                    return OK;
  365.                }
  366.            }
  367.        }
  368.        if (comb == FALSE)    {
  369.            y = trnode.rtsib;
  370.            read_node(y, yp);
  371.            redist(&trnode, yp);
  372.            write_node(y, yp);
  373.            write_node(p, &trnode);
  374.            free(yp);
  375.            return OK;
  376.        }
  377.        free(yp);
  378.        p = z;
  379.        read_node(p, &trnode);
  380.    }
  381.    if (trnode.keyct == 0)    {
  382.        bheader[trx].rootnode = trnode.key0;
  383.        trnode.nonleaf = FALSE;
  384.        trnode.key0 = 0;
  385.        trnode.prntnode = bheader[trx].rlsed_node;
  386.        bheader[trx].rlsed_node = p;
  387.    }
  388.    if (bheader[trx].rootnode == 0)
  389.        bheader[trx].rightmost = bheader[trx].leftmost = 0;
  390.    write_node(p, &trnode);
  391.    return OK;
  392. }
  393.  
  394. /* ------------ Combine two sibling nodes. ------------- */
  395. static void implode(BTREE *left, BTREE *right)
  396. {
  397.    RPTR lf, rt, p;
  398.    int rt_len, lf_len;
  399.    char *a;
  400.    RPTR *b;
  401.    BTREE *par;
  402.    RPTR c;
  403.    char *j;
  404.  
  405.    lf = right->lfsib;
  406.    rt = left->rtsib;
  407.    p = left->prntnode;
  408.    if ((par = malloc(NODE)) == NULL)
  409.        memerr();
  410.    j = childptr(lf, p, par);
  411.    /* --- move key from parent to end of left sibling --- */ 
  412.    lf_len = left->keyct * ENTLN;
  413.    a = left->keyspace + lf_len;
  414.    memmove(a, j, KLEN);
  415.    memset(j, '\0', ENTLN);
  416.    /* --- move keys from right sibling to left --- */
  417.    b = (RPTR *) (a + KLEN);
  418.    *b = right->key0;
  419.    rt_len = right->keyct * ENTLN;
  420.    a = (char *) (b + 1);
  421.    memmove(a, right->keyspace, rt_len);
  422.    /* --- point lower nodes to their new parent --- */
  423.    if (left->nonleaf)
  424.        adopt(b, right->keyct + 1, lf);
  425.    /* --- if global key pointers -> to the right sibling,
  426.                                    change to -> left --- */
  427.    if (currnode[trx] == left->rtsib)    {
  428.        currnode[trx] = right->lfsib;
  429.        currkno[trx] += left->keyct + 1;
  430.    }
  431.    /* --- update control values in left sibling node --- */    
  432.    left->keyct += right->keyct + 1;
  433.    c = bheader[trx].rlsed_node;
  434.    bheader[trx].rlsed_node = left->rtsib;
  435.    if (bheader[trx].rightmost == left->rtsib)
  436.        bheader[trx].rightmost = right->lfsib;
  437.    left->rtsib = right->rtsib;
  438.    /* --- point the deleted node's right brother
  439.                                to this left brother --- */
  440.    if (left->rtsib)    {
  441.        read_node(left->rtsib, right);
  442.        right->lfsib = lf;
  443.        write_node(left->rtsib, right);
  444.    }
  445.    memset(right, '\0', NODE);
  446.    right->prntnode = c;
  447.    /* --- remove key from parent node --- */
  448.    par->keyct--;
  449.    if (par->keyct == 0)
  450.        left->prntnode = 0;
  451.    else    {
  452.        rt_len = par->keyspace + (par->keyct * ENTLN) - j;
  453.        memmove(j, j+ENTLN, rt_len);
  454.    }
  455.    write_node(lf, left);
  456.    write_node(rt, right);
  457.    write_node(p, par);
  458.    free(par);
  459. }
  460.  
  461. /* ------------------ Insert key  ------------------- */
  462. int insertkey(int tree, char *x, RPTR ad, int unique)
  463. {
  464.    char k[MXKEYLEN + 1], *a;
  465.    BTREE *yp;
  466.    BTREE *bp;
  467.    int nl_flag, rt_len, j;
  468.    RPTR t, p, sv;
  469.    RPTR *b;
  470.    int lshft, rshft;
  471.  
  472.    trx = tree;
  473.    if (trx >= MXTREES || fp[trx] == 0)
  474.        return ERROR;
  475.    p = 0;
  476.    sv = 0;
  477.    nl_flag = 0;
  478.    memmove(k, x, KLEN);
  479.    t = bheader[trx].rootnode;
  480.    /* --------------- Find insertion point ------- */
  481.    if (t)    {
  482.        read_node(t, &trnode);
  483.        if (btreescan(&t, k, &a))    {
  484.            if (unique)
  485.                return ERROR;
  486.            else    {
  487.                leaflevel(&t, &a, &j);
  488.                currkno[trx] = j;
  489.            }
  490.        }
  491.        else
  492.            currkno[trx] = ((a - trnode.keyspace) / ENTLN)+1;
  493.        currnode[trx] = t;
  494.    }
  495.    /* --------- Insert key into leaf node -------------- */
  496.    while (t)    {
  497.        nl_flag = 1;
  498.        rt_len = (trnode.keyspace+(bheader[trx].m*ENTLN))-a;
  499.        memmove(a+ENTLN, a, rt_len);
  500.        memmove(a, k, KLEN);
  501.        b = (RPTR *) (a + KLEN);
  502.        *b = ad;
  503.        if (trnode.nonleaf == FALSE)    {
  504.            currnode[trx] = t;
  505.            currkno[trx] = ((a - trnode.keyspace) / ENTLN)+1;
  506.        }
  507.        trnode.keyct++;
  508.        if (trnode.keyct <= bheader[trx].m)    {
  509.            write_node(t, &trnode);
  510.            return OK;
  511.        }
  512.        /* --- Redistribute keys between sibling nodes ---*/
  513.        lshft = FALSE;
  514.        rshft = FALSE;
  515.        if ((yp = malloc(NODE)) == NULL)
  516.            memerr();
  517.        if (trnode.lfsib)    {
  518.            read_node(trnode.lfsib, yp);
  519.            if (yp->keyct < bheader[trx].m &&
  520.                        yp->prntnode == trnode.prntnode)    {
  521.                lshft = TRUE;
  522.                redist(yp, &trnode);
  523.                write_node(trnode.lfsib, yp);
  524.            }
  525.        }
  526.        if (lshft == FALSE && trnode.rtsib)    {
  527.            read_node(trnode.rtsib, yp);
  528.            if (yp->keyct < bheader[trx].m &&
  529.                        yp->prntnode == trnode.prntnode)    {
  530.                rshft = TRUE;
  531.                redist(&trnode, yp);
  532.                write_node(trnode.rtsib, yp);
  533.            }
  534.        }
  535.        free(yp);
  536.        if (lshft || rshft)    {
  537.            write_node(t, &trnode);
  538.            return OK;
  539.        }
  540.        p = nextnode();
  541.        /* ----------- Split node -------------------- */
  542.        if ((bp = malloc(NODE)) == NULL)
  543.            memerr();
  544.        memset(bp, '\0', NODE);
  545.        trnode.keyct = (bheader[trx].m + 1) / 2;
  546.        b = (RPTR *)
  547.              (trnode.keyspace+((trnode.keyct+1)*ENTLN)-ADR);
  548.        bp->key0 = *b;
  549.        bp->keyct = bheader[trx].m - trnode.keyct;
  550.        rt_len = bp->keyct * ENTLN;
  551.        a = (char *) (b + 1);
  552.        memmove(bp->keyspace, a, rt_len);
  553.        bp->rtsib = trnode.rtsib;
  554.        trnode.rtsib = p;
  555.        bp->lfsib = t;
  556.        bp->nonleaf = trnode.nonleaf;
  557.        a -= ENTLN;
  558.        memmove(k, a, KLEN);
  559.        memset(a, '\0', rt_len+ENTLN);
  560.        if (bheader[trx].rightmost == t)
  561.            bheader[trx].rightmost = p;
  562.        if (t == currnode[trx] &&
  563.                        currkno[trx]>trnode.keyct)    {
  564.            currnode[trx] = p;
  565.            currkno[trx] -= trnode.keyct + 1;
  566.        }
  567.        ad = p;
  568.        sv = t;
  569.        t = trnode.prntnode;
  570.        if (t)
  571.            bp->prntnode = t;
  572.        else    {
  573.            p = nextnode();
  574.            trnode.prntnode = p;
  575.            bp->prntnode = p;
  576.        }
  577.        write_node(ad, bp);
  578.        if (bp->rtsib)    {
  579.            if ((yp = malloc(NODE)) == NULL)
  580.                memerr();
  581.            read_node(bp->rtsib, yp);
  582.            yp->lfsib = ad;
  583.            write_node(bp->rtsib, yp);
  584.            free(yp);
  585.        }
  586.        if (bp->nonleaf)
  587.            adopt(&bp->key0, bp->keyct + 1, ad);
  588.        write_node(sv, &trnode);
  589.        if (t)    {
  590.            read_node(t, &trnode);
  591.            a = trnode.keyspace;
  592.            b = &trnode.key0;
  593.            while (*b != bp->lfsib)    {
  594.                a += ENTLN;
  595.                b = (RPTR *) (a - ADR);
  596.            }
  597.        }
  598.        free(bp);
  599.    }
  600.    /* --------------------- new root -------------------- */
  601.    if (p == 0)
  602.        p = nextnode();
  603.    if ((bp = malloc(NODE)) == NULL)
  604.        memerr();
  605.    memset(bp, '\0', NODE);
  606.    bp->nonleaf = nl_flag;
  607.    bp->prntnode = 0;
  608.    bp->rtsib = 0;
  609.    bp->lfsib = 0;
  610.    bp->keyct = 1;
  611.    bp->key0 = sv;
  612.    *((RPTR *) (bp->keyspace + KLEN)) = ad;
  613.    memmove(bp->keyspace, k, KLEN);
  614.    write_node(p, bp);
  615.    free(bp);
  616.    bheader[trx].rootnode = p;
  617.    if (nl_flag == FALSE)    {
  618.        bheader[trx].rightmost = p;
  619.        bheader[trx].leftmost = p;
  620.        currnode[trx] = p;
  621.        currkno[trx] = 1;
  622.    }
  623.    return OK;
  624. }
  625.  
  626. /* ----- redistribute keys in sibling nodes ------ */
  627. static void redist(BTREE *left, BTREE *right)
  628. {
  629.    int n1, n2, len;
  630.    RPTR z;
  631.    char *c, *d, *e;
  632.    BTREE *zp;
  633.  
  634.    n1 = (left->keyct + right->keyct) / 2;
  635.    if (n1 == left->keyct)
  636.        return;
  637.    n2 = (left->keyct + right->keyct) - n1;
  638.    z = left->prntnode;
  639.    if ((zp = malloc(NODE)) == NULL)
  640.        memerr();
  641.    c = childptr(right->lfsib, z, zp);
  642.    if (left->keyct < right->keyct)    {
  643.        d = left->keyspace + (left->keyct * ENTLN);
  644.        memmove(d, c, KLEN);
  645.        d += KLEN;
  646.        e = right->keyspace - ADR;
  647.        len = ((right->keyct - n2 - 1) * ENTLN) + ADR;
  648.        memmove(d, e, len);
  649.        if (left->nonleaf)
  650.            adopt(d, right->keyct - n2, right->lfsib);    
  651.        e += len;
  652.        memmove(c, e, KLEN);
  653.        e += KLEN;
  654.        d = right->keyspace - ADR;
  655.        len = (n2 * ENTLN) + ADR;
  656.        memmove(d, e, len);
  657.        memset(d+len, '\0', e-d);
  658.        if (right->nonleaf == 0 &&
  659.                            left->rtsib == currnode[trx])
  660.            if (currkno[trx] < right->keyct - n2)    {
  661.                currnode[trx] = right->lfsib;
  662.                currkno[trx] += n1 + 1;
  663.            }
  664.            else
  665.                currkno[trx] -= right->keyct - n2;
  666.        }
  667.    else    {
  668.        e = right->keyspace+((n2-right->keyct)*ENTLN)-ADR;
  669.        memmove(e, right->keyspace-ADR,
  670.            (right->keyct * ENTLN) + ADR);
  671.        e -= KLEN;
  672.        memmove(e, c, KLEN);
  673.        d = left->keyspace + (n1 * ENTLN);
  674.        memmove(c, d, KLEN);
  675.        memset(d, '\0', KLEN);
  676.        d += KLEN;
  677.        len = ((left->keyct - n1 - 1) * ENTLN) + ADR;
  678.        memmove(right->keyspace-ADR, d, len);
  679.        memset(d, '\0', len);
  680.        if (right->nonleaf)
  681.            adopt(right->keyspace - ADR,
  682.                            left->keyct - n1, left->rtsib);
  683.        if (left->nonleaf == FALSE)
  684.            if (right->lfsib == currnode[trx] &&
  685.                                    currkno[trx] > n1)    {
  686.                currnode[trx] = left->rtsib;
  687.                currkno[trx] -= n1 + 1;
  688.            }
  689.            else if (left->rtsib == currnode[trx])
  690.                currkno[trx] += left->keyct - n1;
  691.    }
  692.    right->keyct = n2;
  693.    left ->keyct = n1;
  694.    write_node(z, zp);
  695.    free(zp);
  696. }
  697.  
  698. /* ----------- assign new parents to child nodes ---------- */
  699. static void adopt(void *ad, int kct, RPTR newp)
  700. {
  701.    char *cp;
  702.    BTREE *tmp;
  703.  
  704.    if ((tmp = malloc(NODE)) == NULL)
  705.        memerr();
  706.    while (kct--)    {
  707.        read_node(*(RPTR *)ad, tmp);
  708.        tmp->prntnode = newp;
  709.        write_node(*(RPTR *)ad, tmp);
  710.        cp = ad;
  711.        cp += ENTLN;
  712.        ad = cp;
  713.    }
  714.    free(tmp);
  715. }
  716.  
  717. /* ----- compute node address for a new node -----*/
  718. static RPTR nextnode(void)
  719. {
  720.    RPTR p;
  721.    BTREE *nb;
  722.  
  723.    if (bheader[trx].rlsed_node)    {
  724.        if ((nb = malloc(NODE)) == NULL)
  725.            memerr();
  726.        p = bheader[trx].rlsed_node;
  727.        read_node(p, nb);
  728.        bheader[trx].rlsed_node = nb->prntnode;
  729.        free(nb);
  730.    }
  731.    else
  732.        p = bheader[trx].endnode++;
  733.    return p;
  734. }
  735.  
  736. /* ----- next sequential key ------- */
  737. RPTR nextkey(int tree)
  738. {
  739.    trx = tree;
  740.    if (currnode[trx] == 0)
  741.        return firstkey(trx);
  742.    read_node(currnode[trx], &trnode);
  743.    if (currkno[trx] == trnode.keyct)    {
  744.        if (trnode.rtsib == 0)    {
  745.            return 0;
  746.        }
  747.        currnode[trx] = trnode.rtsib;
  748.        currkno[trx] = 0;
  749.        read_node(trnode.rtsib, &trnode);
  750.    }
  751.    else
  752.        currkno[trx]++;
  753.    return *((RPTR *)
  754.            (trnode.keyspace+(currkno[trx]*ENTLN)-ADR));
  755. }
  756.  
  757. /* ----------- previous sequential key ----------- */
  758. RPTR prevkey(int tree)
  759. {
  760.    trx = tree;
  761.    if (currnode[trx] == 0)
  762.        return lastkey(trx);
  763.    read_node(currnode[trx], &trnode);
  764.    if (currkno[trx] == 0)    {
  765.        if (trnode.lfsib == 0)
  766.            return 0;
  767.        currnode[trx] = trnode.lfsib;
  768.        read_node(trnode.lfsib, &trnode);
  769.        currkno[trx] = trnode.keyct;
  770.    }
  771.    else
  772.        currkno[trx]--;
  773.    return *((RPTR *)
  774.        (trnode.keyspace + (currkno[trx] * ENTLN) - ADR));
  775. }
  776.  
  777. /* ------------- first key ------------- */
  778. RPTR firstkey(int tree)
  779. {
  780.    trx = tree;
  781.    if (bheader[trx].leftmost == 0)
  782.        return 0;
  783.    read_node(bheader[trx].leftmost, &trnode);
  784.    currnode[trx] = bheader[trx].leftmost;
  785.    currkno[trx] = 1;
  786.    return *((RPTR *) (trnode.keyspace + KLEN));
  787. }
  788.  
  789. /* ------------- last key ----------------- */
  790. RPTR lastkey(int tree)
  791. {
  792.    trx = tree;
  793.    if (bheader[trx].rightmost == 0)
  794.        return 0;
  795.    read_node(bheader[trx].rightmost, &trnode);
  796.    currnode[trx] = bheader[trx].rightmost;
  797.    currkno[trx] = trnode.keyct;
  798.    return *((RPTR *)
  799.        (trnode.keyspace + (trnode.keyct * ENTLN) - ADR));
  800. }
  801.  
  802. /* -------- scan to the next sequential key ------ */
  803. static RPTR scannext(RPTR *p, char **a)
  804. {
  805.    RPTR cn;
  806.  
  807.    if (trnode.nonleaf)    {
  808.        *p = *((RPTR *) (*a + KLEN));
  809.        read_node(*p, &trnode);
  810.        while (trnode.nonleaf)    {
  811.            *p = trnode.key0;
  812.            read_node(*p, &trnode);
  813.        }
  814.        *a = trnode.keyspace;
  815.        return *((RPTR *) (*a + KLEN));
  816.    }
  817.    *a += ENTLN;
  818.    while (-1)    {
  819.        if ((trnode.keyspace + (trnode.keyct) 
  820.                * ENTLN) != *a)
  821.            return fileaddr(*p, *a);
  822.        if (trnode.prntnode == 0 || trnode.rtsib == 0)
  823.            break;
  824.        cn = *p;
  825.        *p = trnode.prntnode;
  826.        read_node(*p, &trnode);
  827.        *a = trnode.keyspace;
  828.        while (*((RPTR *) (*a - ADR)) != cn)
  829.            *a += ENTLN;
  830.    }
  831.    return 0;
  832. }
  833.  
  834. /* ---- scan to the previous sequential key ---- */
  835. static RPTR scanprev(RPTR *p, char **a)
  836. {
  837.    RPTR cn;
  838.  
  839.    if (trnode.nonleaf)    {
  840.        *p = *((RPTR *) (*a - ADR));
  841.        read_node(*p, &trnode);
  842.        while (trnode.nonleaf)    {
  843.            *p = *((RPTR *)
  844.                (trnode.keyspace+(trnode.keyct)*ENTLN-ADR));
  845.            read_node(*p, &trnode);
  846.        }
  847.        *a = trnode.keyspace + (trnode.keyct - 1) * ENTLN;
  848.        return *((RPTR *) (*a + KLEN));
  849.    }
  850.    while (-1)    {
  851.        if (trnode.keyspace != *a)    {
  852.            *a -= ENTLN;
  853.            return fileaddr(*p, *a);
  854.        }
  855.        if (trnode.prntnode == 0 || trnode.lfsib == 0)
  856.            break;
  857.        cn = *p;
  858.        *p = trnode.prntnode;
  859.        read_node(*p, &trnode);
  860.        *a = trnode.keyspace;
  861.        while (*((RPTR *) (*a - ADR)) != cn)
  862.            *a += ENTLN;
  863.    }
  864.    return 0;
  865. }
  866.  
  867. /* ------ locate pointer to child ---- */
  868. static char *childptr(RPTR left, RPTR parent, BTREE *btp)
  869. {
  870.    char *c;
  871.  
  872.    read_node(parent, btp);
  873.    c = btp->keyspace;
  874.    while (*((RPTR *) (c - ADR)) != left)
  875.        c += ENTLN;
  876.    return c;
  877. }
  878.  
  879. /* -------------- current key value ---------- */
  880. void keyval(int tree, char *ky)
  881. {
  882.    RPTR b, p;
  883.    char *k;
  884.    int i;
  885.  
  886.    trx = tree;
  887.    b = currnode[trx];
  888.    if (b)    {
  889.        read_node(b, &trnode);
  890.        i = currkno[trx];
  891.        k = trnode.keyspace + ((i - 1) * ENTLN);
  892.        while (i == 0)    {
  893.            p = b;
  894.            b = trnode.prntnode;
  895.            read_node(b, &trnode);
  896.            for (; i <= trnode.keyct; i++)    {
  897.                k = trnode.keyspace + ((i - 1) * ENTLN);
  898.                if (*((RPTR *) (k + KLEN)) == p)
  899.                    break;
  900.            }
  901.        }
  902.        memmove(ky, k, KLEN);
  903.    }
  904. }
  905.  
  906. /* --------------- current key ---------- */
  907. RPTR currkey(int tree)
  908. {
  909.    RPTR f = 0;
  910.  
  911.    trx = tree;
  912.    if (currnode[trx])    {
  913.        read_node(currnode[trx], &trnode);
  914.        f = *( (RPTR *)
  915.            (trnode.keyspace+(currkno[trx]*ENTLN)-ADR));
  916.    }
  917.    return f;
  918. }
  919.  
  920. /* ---------- read a btree node ----------- */
  921. static void read_node(RPTR nd, void *bf)
  922. {
  923.    bseek(nd);
  924.    fread(bf, NODE, 1, fp[trx]);
  925.    if (ferror(fp[trx]))    {
  926.        errno = D_IOERR;
  927.        dberror();
  928.    }
  929. }
  930.  
  931. /* ---------- write a btree node ----------- */
  932. static void write_node(RPTR nd, void *bf)
  933. {
  934.    bseek(nd);
  935.    fwrite(bf, NODE, 1, fp[trx]);
  936.    if (ferror(fp[trx]))    {
  937.        errno = D_IOERR;
  938.        dberror();
  939.    }
  940. }
  941.  
  942. /* ----------- seek to the b-tree node ---------- */
  943. static void bseek(RPTR nd)
  944. {
  945.    if (fseek(fp[trx],
  946.          (long) (NODE+((nd-1)*NODE)), SEEK_SET) == ERROR) {
  947.        errno = D_IOERR;
  948.        dberror();
  949.    }
  950. }
  951.  
  952. /* ----------- out of memory error -------------- */
  953. static void memerr(void)
  954. {
  955.    errno = D_OM;
  956.    dberror();
  957. }
  958.  
  959.