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