home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / cbase103 / btree / btinsert.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-23  |  8.9 KB  |  411 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)btinsert.c    1.5 - 91/09/23" */
  5.  
  6. #include <ansi.h>
  7.  
  8. /* ansi headers */
  9. #include <errno.h>
  10. #ifdef AC_STDDEF
  11. #include <stddef.h>
  12. #endif
  13. #ifdef AC_STDLIB
  14. #include <stdlib.h>
  15. #endif
  16. #ifdef AC_STRING
  17. #include <string.h>
  18. #endif
  19.  
  20. /* library headers */
  21. #include <blkio.h>
  22. #include <bool.h>
  23.  
  24. /* local headers */
  25. #include "btree_.h"
  26.  
  27. /* FREE:  free all allocated storage */
  28. #define FREE {                                \
  29.     terrno = errno;                            \
  30.     bt_ndfree(btnp);                        \
  31.     btnp = NULL;                            \
  32.     bt_ndfree(lbtnp);                        \
  33.     lbtnp = NULL;                            \
  34.     bt_ndfree(pbtnp);                        \
  35.     pbtnp = NULL;                            \
  36.     bt_ndfree(rbtnp);                        \
  37.     rbtnp = NULL;                            \
  38.     free(bttpl.keyp);                        \
  39.     bttpl.keyp = NULL;                        \
  40.     errno = terrno;                            \
  41. }
  42.  
  43. #ifdef AC_PROTO
  44. static int setcursor(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp)
  45. #else
  46. static int setcursor(btp, lbtnp, rbtnp)
  47. btree_t *btp;
  48. btnode_t *lbtnp;
  49. btnode_t *rbtnp;
  50. #endif
  51. {
  52.     if (btp->sp[0].key <= lbtnp->n) {
  53.         if (bt_ndcopy(btp, btp->cbtnp, lbtnp) == -1) {
  54.             BTEPRINT;
  55.             return -1;
  56.         }
  57.         btp->cbtpos.node = btp->sp[0].node;
  58.         btp->cbtpos.key = btp->sp[0].key;
  59.     } else {
  60.         if (bt_ndcopy(btp, btp->cbtnp, rbtnp) == -1) {
  61.             BTEPRINT;
  62.             return -1;
  63.         }
  64.         btp->cbtpos.node = lbtnp->rsib;
  65.         btp->cbtpos.key = btp->sp[0].key - lbtnp->n;
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
  71. /*man---------------------------------------------------------------------------
  72. NAME
  73.      btinsert - btree insert
  74.  
  75. SYNOPSIS
  76.      #include <btree.h>
  77.  
  78.      int btinsert(btp, buf)
  79.      btree_t *btp;
  80.      const void *buf;
  81.  
  82. DESCRIPTION
  83.      The btinsert function inserts the key pointed to by buf into
  84.      btree btp.  The cursor is positioned to the inserted key.  If the
  85.      insertion fails, the position of the cursor is undefined.  buf
  86.      must point to a storage area as large as the key size for the
  87.      specified btree.
  88.  
  89.      btinsert will fail if one or more of the following is true:
  90.  
  91.      [EINVAL]       btp is not a valid btree pointer.
  92.      [EINVAL]       buf is the NULL pointer.
  93.      [BTEDUP]       The key at buf is already in btree btp.
  94.      [BTELOCK]      btp is not write locked.
  95.      [BTENOPEN]     btp is not open.
  96.  
  97. SEE ALSO
  98.      btdelete, btsearch.
  99.  
  100. DIAGNOSTICS
  101.      Upon successful completion, a value of 0 is returned.  Otherwise,
  102.      a value of -1 is returned, and errno set to indicate the error.
  103.  
  104. ------------------------------------------------------------------------------*/
  105. #ifdef AC_PROTO
  106. int btinsert(btree_t *btp, const void *buf)
  107. #else
  108. int btinsert(btp, buf)
  109. btree_t *btp;
  110. const void *buf;
  111. #endif
  112. {
  113.     btnode_t *    btnp    = NULL;        /* node receiving new key */
  114.     bttpl_t        bttpl;            /* btree tuple */
  115.     bool        err    = FALSE;    /* error flag */
  116.     int        found    = 0;        /* key found flag */
  117.     bool        grow    = FALSE;    /* tree grow flag */
  118.     btnode_t *    lbtnp    = NULL;        /* left sibling node */
  119.     bpos_t        lsib    = NIL;        /* lsib location */
  120.     bpos_t        node    = NIL;        /* node location */
  121.     btnode_t *    pbtnp    = NULL;        /* parent node */
  122.     int        pkn    = 0;        /* parent key number */
  123.     bpos_t        pnode    = 0;        /* parent node location */
  124.     btnode_t *    rbtnp    = NULL;        /* right sibling node */
  125.     bpos_t        rsib    = NIL;        /* rsib location */
  126.     unsigned long    spi    = 0;        /* search path index */
  127.     int        terrno    = 0;        /* tmp errno */
  128.     int        total    = 0;        /* total keys in node and sib */
  129.  
  130.     /* initialize automatic aggregates */
  131.     memset(&bttpl, 0, sizeof(bttpl));
  132.  
  133.     /* validate arguments */
  134.     if (!bt_valid(btp) || buf == NULL) {
  135.         errno = EINVAL;
  136.         return -1;
  137.     }
  138.  
  139.     /* check if not open */
  140.     if (!(btp->flags & BTOPEN)) {
  141.         errno = BTENOPEN;
  142.         return -1;
  143.     }
  144.  
  145.     /* check lock */
  146.     if (!(btp->flags & BTWRLCK)) {
  147.         errno = BTELOCK;
  148.         return -1;
  149.     }
  150.  
  151.     /* locate position for key and generate search path */
  152.     found = bt_search(btp, buf);
  153.     if (found == -1) {
  154.         BTEPRINT;
  155.         return -1;
  156.     }
  157.     if (found == 1) {            /* check for duplicate key */
  158.         errno = BTEDUP;
  159.         return -1;
  160.     }
  161.  
  162.     /* create working nodes */
  163.     btnp = bt_ndalloc(btp);
  164.     if (btnp == NULL) {
  165.         BTEPRINT;
  166.         return -1;
  167.     }
  168.     lbtnp = bt_ndalloc(btp);    /* left sibling */
  169.     if (lbtnp == NULL) {
  170.         BTEPRINT;
  171.         FREE;
  172.         return -1;
  173.     }
  174.     rbtnp = bt_ndalloc(btp);    /* right sibling */
  175.     if (rbtnp == NULL) {
  176.         BTEPRINT;
  177.         FREE;
  178.         return -1;
  179.     }
  180.     pbtnp = bt_ndalloc(btp);    /* parent */
  181.     if (pbtnp == NULL) {
  182.         BTEPRINT;
  183.         FREE;
  184.         return -1;
  185.     }
  186.  
  187.     /* initialize btnp with current node */
  188.     if (bt_ndcopy(btp, btnp, btp->cbtnp) == -1) {
  189.         BTEPRINT;
  190.         FREE;
  191.         return -1;
  192.     }
  193.  
  194.     /* initialize bttpl with key to insert */
  195.     bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  196.     if (bttpl.keyp == NULL) {
  197.         BTEPRINT;
  198.         FREE;
  199.         errno = ENOMEM;
  200.         return -1;
  201.     }
  202.     memcpy(bttpl.keyp, buf, btp->bthdr.keysize);
  203.     bttpl.child = NIL;
  204.  
  205.     /* set modify bit in in-core header and write to file */
  206.     btp->bthdr.flags |= BTHMOD;
  207.     if (bputhf(btp->bp, sizeof(bpos_t),
  208.                 (char *)&btp->bthdr + sizeof(bpos_t),
  209.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  210.         BTEPRINT;
  211.         FREE;
  212.         return -1;
  213.     }
  214.     if (bsync(btp->bp) == -1) {
  215.         BTEPRINT;
  216.         FREE;
  217.         return -1;
  218.     }
  219.  
  220.     if (btp->bthdr.height == 0) {
  221.         grow = TRUE;
  222.     }
  223.  
  224.     /* loop from leaf node to root */
  225.     for (spi = 0; spi < btp->bthdr.height; ++spi) {
  226.         /* insert new key into node */
  227.         if (bt_ndinskey(btp, btnp, btp->sp[spi].key, &bttpl) == -1) {
  228.             BTEPRINT;
  229.             err = TRUE;
  230.             break;
  231.         }
  232.  
  233.         /* write to disk if node not too big */
  234.         if (btnp->n <= bt_ndmax(btp)) {
  235.             if (bt_ndput(btp, btp->sp[spi].node, btnp) == -1) {
  236.                 BTEPRINT;
  237.                 err = TRUE;
  238.                 break;
  239.             }
  240.             if (spi == 0) {        /* set cursor */
  241.                 if (bt_ndcopy(btp, btp->cbtnp, btnp) == -1) {
  242.                     BTEPRINT;
  243.                     err = TRUE;
  244.                     break;
  245.                 }
  246.                 btp->cbtpos.node = btp->sp[0].node;
  247.                 btp->cbtpos.key = btp->sp[0].key;
  248.             }
  249.             break;
  250.         }
  251.  
  252.         /* check if root */
  253.         if (spi == btp->bthdr.height - 1) {
  254.             if (bt_ndsplit(btp, btp->sp[spi].node, btnp, rbtnp, &bttpl) == -1) {
  255.                 BTEPRINT;
  256.                 err = TRUE;
  257.                 break;
  258.             }
  259.             if (spi == 0) {        /* set cursor */
  260.                 if (setcursor(btp, btnp, rbtnp) == -1) {
  261.                     BTEPRINT;
  262.                     err = TRUE;
  263.                     break;
  264.                 }
  265.             }
  266.             grow = TRUE;
  267.             break;
  268.         }
  269.  
  270.         /* try to shift keys with siblings */
  271.         /* read in parent node */
  272.         if (bt_ndget(btp, btp->sp[spi + 1].node, pbtnp) == -1) {
  273.             BTEPRINT;
  274.             err = TRUE;
  275.             break;
  276.         }
  277.         /* get locations of nodes */
  278.         node = btp->sp[spi].node;
  279.         pnode = btp->sp[spi + 1].node;
  280.         pkn = btp->sp[spi + 1].key - 1;
  281.         if (pkn == 0) {
  282.             lsib = NIL;
  283.         } else {
  284.             lsib = btnp->lsib;
  285.         }
  286.         if (pkn == pbtnp->n) {
  287.             rsib = NIL;
  288.         } else {
  289.             rsib = btnp->rsib;
  290.         }
  291.  
  292.         /* try shifting keys with right sibling */
  293.         if (rsib != NIL) {
  294.             if (bt_ndget(btp, rsib, rbtnp) == -1) {
  295.                 BTEPRINT;
  296.                 err = TRUE;
  297.                 break;
  298.             }
  299.             total = btnp->n + rbtnp->n;
  300.             if (total <= 2 * bt_ndmax(btp)) {
  301.                 if (bt_ndshift(btp, btnp, rbtnp, pbtnp, pkn + 1, pnode) == -1) {
  302.                     BTEPRINT;
  303.                     err = TRUE;
  304.                     break;
  305.                 }
  306.                 if (spi == 0) {        /* set cursor */
  307.                     if (setcursor(btp, btnp, rbtnp) == -1) {
  308.                         BTEPRINT;
  309.                         err = TRUE;
  310.                         break;
  311.                     }
  312.                 }
  313.                 break;
  314.             }
  315.         }
  316.  
  317.         /* try shifting keys with left sibling */
  318.         if (lsib != NIL) {
  319.             if (bt_ndget(btp, lsib, lbtnp) == -1) {
  320.                 BTEPRINT;
  321.                 err = TRUE;
  322.                 break;
  323.             }
  324.             total = lbtnp->n + btnp->n;
  325.             if (total <= 2 * bt_ndmax(btp)) {
  326.                 btp->sp[spi].key = lbtnp->n + btp->sp[spi].key;
  327.                 if (bt_ndshift(btp, lbtnp, btnp, pbtnp, pkn, pnode) == -1) {
  328.                     BTEPRINT;
  329.                     err = TRUE;
  330.                     break;
  331.                 }
  332.                 if (spi == 0) {        /* set cursor */
  333.                     if (setcursor(btp, lbtnp, btnp) == -1) {
  334.                         BTEPRINT;
  335.                         err = TRUE;
  336.                         break;
  337.                     }
  338.                 }
  339.                 break;
  340.             }
  341.         }
  342.  
  343.         /* split node */
  344.         if (bt_ndsplit(btp, node, btnp, rbtnp, &bttpl) == -1) {
  345.             BTEPRINT;
  346.             err = TRUE;
  347.             break;
  348.         }
  349.         if (spi == 0) {        /* set cursor */
  350.             if (setcursor(btp, btnp, rbtnp) == -1) {
  351.                 BTEPRINT;
  352.                 err = TRUE;
  353.                 break;
  354.             }
  355.         }
  356.  
  357.         /* bttpl must be inserted in pbtnp */
  358.         if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
  359.             BTEPRINT;
  360.             err = TRUE;
  361.             break;
  362.         }
  363.     }
  364.     if (err) {
  365.         BTEPRINT;
  366.         FREE;
  367.         return -1;
  368.     }
  369.     bt_ndfree(btnp);    /* free in-core nodes */
  370.     bt_ndfree(lbtnp);
  371.     bt_ndfree(rbtnp);
  372.     bt_ndfree(pbtnp);
  373.  
  374.     /* check if the tree grew */
  375.     if (grow) {
  376.         if (bt_grow(btp, &bttpl) == -1) {
  377.             BTEPRINT;
  378.             free(bttpl.keyp);
  379.             return -1;
  380.         }
  381.         if (btp->bthdr.height == 1) {        /* set cursor */
  382.             if (bt_ndget(btp, btp->bthdr.root, btp->cbtnp) == -1) {
  383.                 BTEPRINT;
  384.                 free(bttpl.keyp);
  385.                 return -1;
  386.             }
  387.             btp->cbtpos.node = btp->bthdr.root;
  388.             btp->cbtpos.key = 1;
  389.         }
  390.     }
  391.     free(bttpl.keyp);
  392.  
  393.     /* increment key count */
  394.     btp->bthdr.keycnt++;
  395.  
  396.     /* clear modify bit in in-core header and write to file */
  397.     btp->bthdr.flags &= ~BTHMOD;
  398.     if (bputhf(btp->bp, sizeof(bpos_t),
  399.                 (char *)&btp->bthdr + sizeof(bpos_t),
  400.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  401.         BTEPRINT;
  402.         return -1;
  403.     }
  404.     if (bsync(btp->bp) == -1) {
  405.         BTEPRINT;
  406.         return -1;
  407.     }
  408.  
  409.     return 0;
  410. }
  411.