home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / BTINSERT.C < prev    next >
Text File  |  1989-08-31  |  6KB  |  284 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "btinsert.c    1.1 - 89/07/03" */
  5.  
  6. #include <blkio.h>
  7. #include <bool.h>
  8. #include <errno.h>
  9. /* #include <stdlib.h> */
  10. /* #include <string.h> */
  11. #include "btree_.h"
  12.  
  13. /*man---------------------------------------------------------------------------
  14. NAME
  15.      btinsert - btree insert
  16.  
  17. SYNOPSIS
  18.      #include <btree.h>
  19.  
  20.      int btinsert(btp, buf)
  21.      btree_t *btp;
  22.      void *buf;
  23.  
  24. DESCRIPTION
  25.      The btinsert function inserts the key pointed to by buf into btree
  26.      btp.  The cursor is positioned to the inserted key.  If the insertion
  27.      fails, the position of the cursor is undefined.
  28.  
  29.      btinsert will fail if one or more of the following is true:
  30.  
  31.      [EINVAL]       btp is not a valid btree pointer.
  32.      [EINVAL]       buf is the NULL pointer.
  33.      [BTEDUPKEY]    The key at buf is already in btree btp.
  34.      [BTELOCK]      btp is not write locked.
  35.      [BTENOPEN]     btp is not open.
  36.  
  37. SEE ALSO
  38.      btdelete, btsearch.
  39.  
  40. DIAGNOSTICS
  41.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  42.      value of -1 is returned and errno is set to indicate the error.
  43.  
  44. ------------------------------------------------------------------------------*/
  45. int btinsert(btp, buf)
  46. btree_t * btp;
  47. void *    buf;
  48. {
  49.     int        rs    = 0;
  50.     int        rt    = 0;
  51.     int        spi    = 0;        /* search path index */
  52.     btnode_t *    btnp    = NULL;        /* node receiving new key */
  53.     btnode_t *    rbtnp    = NULL;        /* right sibling node */
  54.     bttuple_t    bttuple;
  55.     bool        grow    = FALSE;
  56.  
  57.     errno = 0;
  58.  
  59.     /* initialize storage */
  60.     memset((void *)&bttuple, 0, sizeof(bttuple));
  61.  
  62.     /* validate arguments */
  63.     if ((!bt_valid(btp)) || (buf == NULL)) {
  64.         errno = EINVAL;
  65.         return -1;
  66.     }
  67.  
  68.     /* check if not open */
  69.     if (!(btp->flags & BTOPEN)) {
  70.         errno = BTENOPEN;
  71.         return -1;
  72.     }
  73.  
  74.     /* check locks */
  75.     if (!(btp->flags & BTWRLCK)) {
  76.         errno = BTELOCK;
  77.         return -1;
  78.     }
  79.  
  80.     /* locate slot for key */
  81.     rs = bt_search(btp, buf);
  82.     if (rs == -1) {
  83.         BTEPRINT;
  84.         return -1;
  85.     }
  86.     if (rs == 1) {            /* check for duplicate key */
  87.         errno = BTEDUPKEY;
  88.         return -1;
  89.     }
  90.  
  91.     /* initialize working nodes */
  92.     btnp = bt_ndalloc(btp);
  93.     if (btnp == NULL) {
  94.         BTEPRINT;
  95.         return -1;
  96.     }
  97.     rbtnp = bt_ndalloc(btp);
  98.     if (rbtnp == NULL) {
  99.         BTEPRINT;
  100.         bt_ndfree(btnp);
  101.         return -1;
  102.     }
  103.     rs = bt_ndcopy(btp, btnp, btp->cbtnp);
  104.     if (rs == -1) {
  105.         BTEPRINT;
  106.         bt_ndfree(rbtnp);
  107.         bt_ndfree(btnp);
  108.         return -1;
  109.     }
  110.  
  111.     /* initialize bttuple */
  112.     bttuple.key_p = calloc(1, btp->bthdr.keysize);
  113.     if (bttuple.key_p == NULL) {
  114.         BTEPRINT;
  115.         bt_ndfree(rbtnp);
  116.         bt_ndfree(btnp);
  117.         errno = ENOMEM;
  118.         return -1;
  119.     }
  120.     memcpy(bttuple.key_p, buf, btp->bthdr.keysize);
  121.     bttuple.child = 0;
  122.     if (btp->bthdr.height == 0) {
  123.         grow = TRUE;
  124.     }
  125.  
  126.     /* set modify bit in header */
  127.     btp->bthdr.flags |= BTHMOD;
  128.     rs = bputh(btp->bp, (void *)&btp->bthdr);
  129.     if (rs == -1) {
  130.         BTEPRINT;
  131.         free(bttuple.key_p);
  132.         bt_ndfree(rbtnp);
  133.         bt_ndfree(btnp);
  134.         return -1;
  135.     }
  136.     rs = bsync(btp->bp);
  137.     if (rs == -1) {
  138.         BTEPRINT;
  139.         free(bttuple.key_p);
  140.         bt_ndfree(rbtnp);
  141.         bt_ndfree(btnp);
  142.         return -1;
  143.     }
  144.  
  145.     /* loop from leaf node to root */
  146.     for (spi = btp->bthdr.height; spi > 0; spi--) {
  147.         /* insert new key into node */
  148.         rs = bt_ndinskey(btp, btnp, btp->sp[spi].key, &bttuple);
  149.         if (rs == -1) {
  150.             BTEPRINT;
  151.             rt = -1;
  152.             break;
  153.         }
  154.         /* write to disk if node not too big */
  155.         if (btnp->n <= bt_ndmax(btp)) {
  156.             rs = bt_ndput(btp, btp->sp[spi].node, btnp);
  157.             if (rs == -1) {
  158.                 BTEPRINT;
  159.                 rt = -1;
  160.                 break;
  161.             }
  162.             /* set cursor */
  163.             if (spi == btp->bthdr.height) {
  164.                 rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  165.                 if (rs == -1) {
  166.                     BTEPRINT;
  167.                     rt = -1;
  168.                     break;
  169.                 }
  170.                 memcpy((void *)&btp->cbtpos,
  171.                     (void *)&btp->sp[btp->bthdr.height],
  172.                             sizeof(btp->cbtpos));
  173.             }
  174.             break;
  175.         }
  176.         /* node must be split */
  177.         rs = bt_ndsplit(btp, btp->sp[spi].node, btnp, rbtnp, &bttuple);
  178.         if (rs == -1) {
  179.             BTEPRINT;
  180.             rt = -1;
  181.             break;
  182.         }
  183.         /* write split nodes */
  184.         rs = bt_ndput(btp, btp->sp[spi].node, btnp);
  185.         if (rs == -1) {
  186.             BTEPRINT;
  187.             rt = -1;
  188.             break;
  189.         }
  190.         rs = bt_ndput(btp, bttuple.child, rbtnp);
  191.         if (rs == -1) {
  192.             BTEPRINT;
  193.             rt = -1;
  194.             break;
  195.         }
  196.         /* update right sibling node */
  197.         if (rbtnp->rsib != 0) {
  198.             rs = bputbf(btp->bp, rbtnp->rsib, offsetof(btnode_t, lsib), (void *)&bttuple.child, sizeof(rbtnp->lsib));
  199.             if (rs == -1) {
  200.                 BTEPRINT;
  201.                 rt = -1;
  202.                 break;
  203.             }
  204.         }
  205.         /* check if at top of tree */
  206.         if (spi == 1) {
  207.             grow = TRUE;
  208.         } else {        /* read new parent node */
  209.             rs = bt_ndget(btp, btp->sp[spi - 1].node, btnp);
  210.             if (rs == -1) {
  211.                 BTEPRINT;
  212.                 rt = -1;
  213.                 break;
  214.             }
  215.         }
  216.         /* update cursor, first, and last */
  217.         if (spi == btp->bthdr.height) {
  218.             if (rbtnp->rsib == 0) {    /* new last key node */
  219.                 btp->bthdr.last = bttuple.child;
  220.             }
  221.             if (btp->sp[btp->bthdr.height].key <= btnp->n) {
  222.                 rs = bt_ndcopy(btp, btp->cbtnp, btnp);
  223.                 if (rs == -1) {
  224.                     BTEPRINT;
  225.                     rt = -1;
  226.                     break;
  227.                 }
  228.                 memcpy((void *)&btp->cbtpos,
  229.                     (void *)&btp->sp[btp->bthdr.height],
  230.                             sizeof(btp->cbtpos));
  231.             } else {
  232.                 rs = bt_ndcopy(btp, btp->cbtnp, rbtnp);
  233.                 if (rs == -1) {
  234.                     BTEPRINT;
  235.                     rt = -1;
  236.                     break;
  237.                 }
  238.                 memcpy((void *)&btp->cbtpos,
  239.                     (void *)&btp->sp[btp->bthdr.height],
  240.                             sizeof(btp->cbtpos));
  241.             }
  242.         }
  243.     }
  244.     if (rt == -1) {
  245.         BTEPRINT;
  246.         free(bttuple.key_p);
  247.         bt_ndfree(rbtnp);
  248.         bt_ndfree(btnp);
  249.         return -1;
  250.     }
  251.     bt_ndfree(rbtnp);
  252.     bt_ndfree(btnp);
  253.  
  254.     /* check if the tree grew */
  255.     if (grow) {
  256.         rs = bt_grow(btp, &bttuple);
  257.         if (rs == -1) {
  258.             BTEPRINT;
  259.             free(bttuple.key_p);
  260.             return -1;
  261.         }
  262.     }
  263.     free(bttuple.key_p);
  264.  
  265.     /* increment key count */
  266.     btp->bthdr.keycnt++;
  267.  
  268.     /* clear modify bit in header */
  269.     btp->bthdr.flags &= ~BTHMOD;
  270.     rs = bputh(btp->bp, (void *)&btp->bthdr);
  271.     if (rs == -1) {
  272.         BTEPRINT;
  273.         return -1;
  274.     }
  275.     rs = bsync(btp->bp);
  276.     if (rs == -1) {
  277.         BTEPRINT;
  278.         return -1;
  279.     }
  280.  
  281.     errno = 0;
  282.     return 0;
  283. }
  284.