home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / BTDELCUR.C < prev    next >
Text File  |  1989-08-31  |  11KB  |  495 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "btdelcur.c    1.1 - 89/07/03" */
  5.  
  6. #include <blkio.h>
  7. #include <errno.h>
  8. #include "btree_.h"
  9.  
  10. static int dshuffle(/* btree_t *btp, btnode_t *btnp, btpos_t  *btpos_p, btnode_t *pbtnp, size_t pkn */);
  11.  
  12. /*man---------------------------------------------------------------------------
  13. NAME
  14.      btdelcur - delete current btree key
  15.  
  16. SYNOPSIS
  17.      #include <btree.h>
  18.  
  19.      int btdelcur(btp)
  20.      btree_t *btp;
  21.  
  22. DESCRIPTION
  23.      The btdelcur function deletes the current key from btree btp.  The
  24.      cursor is positioned to the key following the one deleted.
  25.  
  26.      btdelcur will fail if one or more of the following is true:
  27.  
  28.      [EINVAL]       btp is not a valid btree pointer.
  29.      [BTELOCK]      btree btp is not write locked.
  30.      [BTENKEY]      The cursor is null.
  31.      [BTENOPEN]     btree btp is not open.
  32.  
  33. SEE ALSO
  34.      btdelete, btinsert, btsearch.
  35.  
  36. DIAGNOSTICS
  37.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  38.      value of -1 is returned, and errno set to indicate the error.
  39.  
  40. ------------------------------------------------------------------------------*/
  41. int btdelcur(btp)
  42. btree_t *btp;
  43. {
  44.     int        rt    = 0;
  45.     int        rs    = 0;
  46.     int        spi    = 0;        /* search path index */
  47.     btnode_t *    btnp    = NULL;        /* node losing key */
  48.     btnode_t *    pbtnp    = NULL;        /* parent node */
  49.  
  50.     /* validate arguments */
  51.     if (!bt_valid(btp)) {
  52.         errno = EINVAL;
  53.         return -1;
  54.     }
  55.  
  56.     /* check if not open */
  57.     if (!(btp->flags & BTOPEN)) {
  58.         errno = BTENOPEN;
  59.         return -1;
  60.     }
  61.  
  62.     /* check if not write locked */
  63.     if (!(btp->flags & BTWRLCK)) {
  64.         errno = BTELOCK;
  65.         return -1;
  66.     }
  67.  
  68.     /* check if cursor is null */
  69.     if (btcursor(btp) == NULL) {
  70.         errno = BTENKEY;
  71.         return -1;
  72.     }
  73.  
  74.     /* generate search path if necessary */
  75.     if (btp->sp[btp->bthdr.height].node == btp->cbtpos.node) {
  76.         btp->sp[btp->bthdr.height].key = btp->cbtpos.key;
  77.     } else {
  78.         rs = btsearch(btp, bt_kykey_p(btp, btp->cbtnp, btp->cbtpos.key));
  79.         if (rs == -1) {
  80.             BTEPRINT;
  81.             return -1;
  82.         }
  83.         if (rs == 0) {
  84.             BTEPRINT;
  85.             errno = BTEPANIC;
  86.             return -1;
  87.         }
  88.     }
  89.  
  90.     /* initialize working nodes */
  91.     btnp = bt_ndalloc(btp);
  92.     if (btnp == NULL) {
  93.         BTEPRINT;
  94.         return -1;
  95.     }
  96.     pbtnp = bt_ndalloc(btp);
  97.     if (pbtnp == NULL) {
  98.         BTEPRINT;
  99.         bt_ndfree(btnp);
  100.         return -1;
  101.     }
  102.     rs = bt_ndcopy(btp, btnp, btp->cbtnp);
  103.     if (rs == -1) {
  104.         BTEPRINT;
  105.         bt_ndfree(pbtnp);
  106.         bt_ndfree(btnp);
  107.         return -1;
  108.     }
  109.  
  110.     /* delete key from node */
  111.     rs = bt_nddelkey(btp, btnp, btp->cbtpos.key);
  112.     if (rs == -1) {
  113.         BTEPRINT;
  114.         bt_ndfree(pbtnp);
  115.         bt_ndfree(btnp);
  116.         return -1;
  117.     }
  118.  
  119.     /* set modify bit in header */
  120.     btp->bthdr.flags |= BTHMOD;
  121.     rs = bputh(btp->bp, (void *)&btp->bthdr);
  122.     if (rs == -1) {
  123.         BTEPRINT;
  124.         bt_ndfree(pbtnp);
  125.         bt_ndfree(btnp);
  126.         return -1;
  127.     }
  128.     rs = bsync(btp->bp);
  129.     if (rs == -1) {
  130.         BTEPRINT;
  131.         bt_ndfree(pbtnp);
  132.         bt_ndfree(btnp);
  133.         return -1;
  134.     }
  135.  
  136.     for (spi = btp->bthdr.height; spi > 0; spi--) {
  137.         /* write to disk if node not too small */
  138.         if (btnp->n >= bt_ndmin(btp)) {
  139.             rs = bt_ndput(btp, btp->sp[spi].node, btnp);
  140.             if (rs == -1) {
  141.                 BTEPRINT;
  142.                 rt = -1;
  143.                 break;
  144.             }
  145.             /* set cursor */
  146.             if (spi == btp->bthdr.height) {
  147.                 rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  148.                 if (rs == -1) {
  149.                     BTEPRINT;
  150.                     rt = -1;
  151.                     break;
  152.                 }
  153.             }
  154.             break;
  155.         }
  156.         /* write to disk if root */
  157.         if (spi == 1) {
  158.             if (btnp->n != 0) {
  159.                 rs = bt_ndput(btp, btp->sp[spi].node, btnp);
  160.                 if (rs == -1) {
  161.                     BTEPRINT;
  162.                     rt = -1;
  163.                     break;
  164.                 }
  165.             } else {
  166.                 rs = bt_shrink(btp, *bt_kychild_p(btnp, 0));
  167.                 if (rs == -1) {
  168.                     BTEPRINT;
  169.                     rt = -1;
  170.                     break;
  171.                 }
  172.             }
  173.             break;
  174.         }
  175.         /* node needs more keys */
  176.         /* read in parent node */
  177.         rs = bt_ndget(btp, btp->sp[spi - 1].node, pbtnp);
  178.         if (rs == -1) {
  179.             BTEPRINT;
  180.             rt = -1;
  181.             break;
  182.         }
  183.         rs = dshuffle(btp, btnp, &btp->sp[spi], pbtnp, btp->sp[spi - 1].key);
  184.         if (rs == -1) {
  185.             BTEPRINT;
  186.             rt = -1;
  187.             break;
  188.         }
  189.         rs = bt_ndcopy(btp, btnp, pbtnp);
  190.         if (rs == -1) {
  191.             BTEPRINT;
  192.             rt = -1;
  193.             break;
  194.         }
  195.     }
  196.     if (rt == -1) {
  197.         BTEPRINT;
  198.         bt_ndfree(pbtnp);
  199.         bt_ndfree(btnp);
  200.         return -1;
  201.     }
  202.  
  203.     bt_ndfree(pbtnp);
  204.     bt_ndfree(btnp);
  205.  
  206.     /* decrement key count in header */
  207.     btp->bthdr.keycnt--;
  208.  
  209.     /* clear modify bit in header */
  210.     btp->bthdr.flags &= ~BTHMOD;
  211.     rs = bputh(btp->bp, (void *)&btp->bthdr);
  212.     if (rs == -1) {
  213.         BTEPRINT;
  214.         return -1;
  215.     }
  216.     rs = bsync(btp->bp);
  217.     if (rs == -1) {
  218.         BTEPRINT;
  219.         return -1;
  220.     }
  221.  
  222.     errno = 0;
  223.     return 0;
  224. }
  225.  
  226. /*------------------------------------------------------------------------------
  227. NAME
  228.      dshuffle - delete shuffle
  229.  
  230. SYNOPSIS
  231.      #include <btree.h>
  232.  
  233.      static int dshuffle(btp, btnp, btpos_p, pbtnp, pkn)
  234.      btree_t *  btp;
  235.      btnode_t * btnp;
  236.      btpos_t  * btpos_p;
  237.      btnode_t * pbtnp;
  238.      size_t     pkn;
  239.  
  240. DESCRIPTION
  241.      The dshuffle function shuffles keys to give btree node btnp at least
  242.      the minimum necessary for a btree btp.  It first tries to shift some
  243.      over from one of the siblings.  If neither sibling can provide enough
  244.      keys, it will fuse btnp with one of the siblings.  The parent node
  245.      pbtnp is adjusted for each operation.  All child nodes modified are
  246.      written to the file, but the parent node is not.
  247.  
  248.      btpos_p points to the btree position of the key just deleted from
  249.      node btnp.  pkn is the number of the key in the parent node which
  250.      was traversed in the search path.
  251.  
  252. DIAGNOSTICS
  253.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  254.      value of -1 is returned, and errno set to indicate the error.
  255.  
  256. ------------------------------------------------------------------------------*/
  257. static int dshuffle(btp, btnp, btpos_p, pbtnp, pkn)
  258. btree_t *  btp;
  259. btnode_t * btnp;
  260. btpos_t  * btpos_p;
  261. btnode_t * pbtnp;
  262. size_t     pkn;
  263. {
  264.     int        rs        = 0;
  265.     bool        leaf        = FALSE;
  266.     size_t        lsib        = 0;
  267.     size_t        rsib        = 0;
  268.     btnode_t *    lbtnp        = NULL;
  269.     btnode_t *    rbtnp        = NULL;
  270.     int        ns        = 0;
  271.  
  272.     errno = 0;
  273.  
  274.     /* validate arguments */
  275.     if ((pkn == 0) || (pkn > (pbtnp->n + 1))) {
  276.         BTEPRINT;
  277.         errno = BTEPANIC;
  278.         return -1;
  279.     }
  280.  
  281.     /* check if leaf or internal node */
  282.     if (*bt_kychild_p(btnp, 0) == 0) {
  283.         leaf = TRUE;
  284.     }
  285.  
  286.     /* find parent key */
  287.     if (pkn == (pbtnp->n + 1)) {
  288.         pkn = pbtnp->n;
  289.     } else  if (*bt_kychild_p(pbtnp, pkn) != btpos_p->node) {
  290.         pkn--;
  291.     }
  292.     if (*bt_kychild_p(pbtnp, pkn) != btpos_p->node) {
  293.         BTEPRINT;
  294.         errno = BTEPANIC;
  295.         return -1;
  296.     }
  297.  
  298.     /* find block numbers of siblings nodes */
  299.     if (pkn == 0) {
  300.         lsib = 0;
  301.     } else {
  302.         /* lsib = btnp->lsib; */
  303.         lsib = *bt_kychild_p(pbtnp, pkn - 1);
  304.     }
  305.     if (pkn == pbtnp->n) {
  306.         rsib = 0;
  307.     } else {
  308.         /* rsib = btnp->rsib; */
  309.         rsib = *bt_kychild_p(pbtnp, pkn + 1);
  310.     }
  311.  
  312.     /* read sibling nodes */
  313.     lbtnp = bt_ndalloc(btp);
  314.     if (lbtnp == NULL) {
  315.         BTEPRINT;
  316.         return -1;
  317.     }
  318.     rbtnp = bt_ndalloc(btp);
  319.     if (rbtnp == NULL) {
  320.         BTEPRINT;
  321.         bt_ndfree(lbtnp);
  322.         return -1;
  323.     }
  324.     if (lsib != 0) {
  325.         rs = bt_ndget(btp, lsib, lbtnp);
  326.         if (rs == -1) {
  327.             BTEPRINT;
  328.             bt_ndfree(rbtnp);
  329.             bt_ndfree(lbtnp);
  330.             return -1;
  331.         }
  332.     }
  333.     if (rsib != 0) {
  334.         rs = bt_ndget(btp, rsib, rbtnp);
  335.         if (rs == -1) {
  336.             BTEPRINT;
  337.             bt_ndfree(rbtnp);
  338.             bt_ndfree(lbtnp);
  339.             return -1;
  340.         }
  341.     }
  342.  
  343.     /* first try shifting keys from the right sibling */
  344.     if ((rsib != 0) && (((btnp->n + rbtnp->n) / 2) >= bt_ndmin(btp))) {
  345.         ns = bt_ndshift(btp, btnp, rbtnp, pbtnp, pkn + 1);
  346.         if (ns == -1) {
  347.             BTEPRINT;
  348.             bt_ndfree(rbtnp);
  349.             bt_ndfree(lbtnp);
  350.             return -1;
  351.         }
  352.         /* position cursor */
  353.         if (leaf) {
  354.             btp->cbtpos.node = btpos_p->node;
  355.             btp->cbtpos.key = btpos_p->key;
  356.             rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  357.             if (rs == -1) {
  358.                 BTEPRINT;
  359.                 bt_ndfree(rbtnp);
  360.                 bt_ndfree(lbtnp);
  361.                 return -1;
  362.             }
  363.         }
  364.         rs = bt_ndput(btp, btpos_p->node, btnp);
  365.         if (rs == -1) {
  366.             BTEPRINT;
  367.             bt_ndfree(rbtnp);
  368.             bt_ndfree(lbtnp);
  369.             return -1;
  370.         }
  371.         rs = bt_ndput(btp, rsib, rbtnp);
  372.         if (rs == -1) {
  373.             BTEPRINT;
  374.             bt_ndfree(rbtnp);
  375.             bt_ndfree(lbtnp);
  376.             return -1;
  377.         }
  378.     /* then from the left sibling */
  379.     } else if ((lsib != 0) && (((btnp->n + lbtnp->n) / 2) >= bt_ndmin(btp))) {
  380.         ns = bt_ndshift(btp, lbtnp, btnp, pbtnp, pkn);
  381.         if (ns == -1) {
  382.             BTEPRINT;
  383.             bt_ndfree(rbtnp);
  384.             bt_ndfree(lbtnp);
  385.             return -1;
  386.         }
  387.         /* position cursor */
  388.         if (leaf) {
  389.             btp->cbtpos.node = btpos_p->node;
  390.             btp->cbtpos.key = btpos_p->key + ns;
  391.             rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  392.             if (rs == -1) {
  393.                 BTEPRINT;
  394.                 bt_ndfree(rbtnp);
  395.                 bt_ndfree(lbtnp);
  396.                 return -1;
  397.             }
  398.         }
  399.         rs = bt_ndput(btp, lsib, lbtnp);
  400.         if (rs == -1) {
  401.             BTEPRINT;
  402.             bt_ndfree(rbtnp);
  403.             bt_ndfree(lbtnp);
  404.             return -1;
  405.         }
  406.         rs = bt_ndput(btp, btpos_p->node, btnp);
  407.         if (rs == -1) {
  408.             BTEPRINT;
  409.             bt_ndfree(rbtnp);
  410.             bt_ndfree(lbtnp);
  411.             return -1;
  412.         }
  413.     /* then try to fuse nodes */
  414.     } else {
  415.         /* first try to fuse with the right node */
  416.         if (rsib != 0) {
  417.             rs = bt_ndfuse(btp, btnp, rbtnp, pbtnp, pkn + 1);
  418.             if (rs == -1) {
  419.                 BTEPRINT;
  420.                 bt_ndfree(rbtnp);
  421.                 bt_ndfree(lbtnp);
  422.                 return -1;
  423.             }
  424.             /* position cursor */
  425.             if (leaf) {
  426.                 btp->cbtpos.node = btpos_p->node;
  427.                 btp->cbtpos.key = btpos_p->key;
  428.                 if (btnp->rsib == 0) {
  429.                     btp->bthdr.last = btpos_p->node;
  430.                 }
  431.                 rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  432.                 if (rs == -1) {
  433.                     BTEPRINT;
  434.                     bt_ndfree(rbtnp);
  435.                     bt_ndfree(lbtnp);
  436.                     return -1;
  437.                 }
  438.             }
  439.             rs = bt_ndput(btp, btpos_p->node, btnp);
  440.             if (rs == -1) {
  441.                 BTEPRINT;
  442.                 bt_ndfree(rbtnp);
  443.                 bt_ndfree(lbtnp);
  444.                 return -1;
  445.             }
  446.         /* then with the left node */
  447.         } else if (lsib != 0) {
  448.             /* position cursor */
  449.             if (leaf) {
  450.                 btp->cbtpos.key = lbtnp->n + btpos_p->key;
  451.                 btp->cbtpos.node = lsib;
  452.             }
  453.             rs = bt_ndfuse(btp, lbtnp, btnp, pbtnp, pkn);
  454.             if (rs == -1) {
  455.                 BTEPRINT;
  456.                 bt_ndfree(rbtnp);
  457.                 bt_ndfree(lbtnp);
  458.                 return -1;
  459.             }
  460.             /* copy current node */
  461.             if (leaf) {
  462.                 if (lbtnp->rsib == 0) {
  463.                     btp->bthdr.last = lsib;
  464.                 }
  465.                 rs = bt_ndcopy(btp, btp->cbtnp, lbtnp);
  466.                 if (rs == -1) {
  467.                     BTEPRINT;
  468.                     bt_ndfree(rbtnp);
  469.                     bt_ndfree(lbtnp);
  470.                     return -1;
  471.                 }
  472.             }
  473.             rs = bt_ndput(btp, lsib, lbtnp);
  474.             if (rs == -1) {
  475.                 BTEPRINT;
  476.                 bt_ndfree(rbtnp);
  477.                 bt_ndfree(lbtnp);
  478.                 return -1;
  479.             }
  480.         } else {
  481.             BTEPRINT;
  482.             bt_ndfree(rbtnp);
  483.             bt_ndfree(lbtnp);
  484.             errno = BTEPANIC;
  485.             return -1;
  486.         }
  487.     }
  488.  
  489.     bt_ndfree(rbtnp);
  490.     bt_ndfree(lbtnp);
  491.  
  492.     errno = 0;
  493.     return 0;
  494. }
  495.