home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / BTOPS.C < prev    next >
Text File  |  1989-08-31  |  12KB  |  514 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "btops.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.      bt_alloc - allocate memory for a btree
  16.  
  17. SYNOPSIS
  18.      #include "btree_.h"
  19.  
  20.      int bt_alloc(btp);
  21.      btree_t *btp;
  22.  
  23. DESCRIPTION
  24.      The bt_alloc function allocates the memory needed by btree btp.  The
  25.      storage is initialized to 0.
  26.  
  27.      bt_alloc will fail if one or more of the following is true:
  28.  
  29.      [EINVAL]       btp is not a valid btree pointer.
  30.      [ENOMEM]       Not enough memory is available for the
  31.                     calling process to allocate.
  32.      [BTENOPEN]     btp is not open.
  33.  
  34. SEE ALSO
  35.      bt_free.
  36.  
  37. DIAGNOSTICS
  38.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  39.      value of -1 is returned, and errno set to indicate the error.
  40.  
  41. ------------------------------------------------------------------------------*/
  42. int bt_alloc(btp)
  43. btree_t *btp;
  44. {
  45.     errno = 0;
  46.  
  47. #ifdef DEBUG
  48.     /* validate arguments */
  49.     if (!bt_valid(btp)) {
  50.         BTEPRINT;
  51.         errno = EINVAL;
  52.         return -1;
  53.     }
  54.  
  55.     /* check if not open */
  56.     if (!(btp->flags & BTOPEN)) {
  57.         BTEPRINT;
  58.         errno = BTENOPEN;
  59.         return -1;
  60.     }
  61. #endif
  62.  
  63.     /* free any previously allocated storage */
  64.     bt_free(btp);
  65.  
  66.     /* search path */
  67.     btp->sp = (btpos_t *)calloc(btp->bthdr.height + 1, sizeof(btpos_t));
  68.     if (btp->sp == NULL) {
  69.         BTEPRINT;
  70.         errno = ENOMEM;
  71.         return -1;
  72.     }
  73.  
  74.     /* current node */
  75.     btp->cbtnp = bt_ndalloc(btp);
  76.     if (btp->cbtnp == NULL) {
  77.         BTEPRINT;
  78.         free((void *)btp->sp);
  79.         return -1;
  80.     }
  81.  
  82.     errno = 0;
  83.     return 0;
  84. }
  85.  
  86. /*man---------------------------------------------------------------------------
  87. NAME
  88.      bt_blksize - btree block size
  89.  
  90. SYNOPSIS
  91.      #include <btree.h>
  92.  
  93.      void *bt_blksize(btp)
  94.      btree_t *btp;
  95.  
  96. DESCRIPTION
  97.      bt_blksize returns the size of the blocks in btree btp.  If btp is not
  98.      a valid open btree, the results are undefined.  bt_blksize is a macro.
  99.  
  100. ------------------------------------------------------------------------------*/
  101.  
  102. /* bt_blksize #defined in btree_.h. */
  103.  
  104. /*man---------------------------------------------------------------------------
  105. NAME
  106.      bt_free - free memory allocated for a btree
  107.  
  108. SYNOPSIS
  109.      #include "btree_.h"
  110.  
  111.      void bt_free(btp)
  112.      btree_t *btp;
  113.  
  114. DESCRIPTION
  115.      The bt_free function frees all memory allocated for btree btp.  If
  116.      btp is not a valid btree, no action is taken.
  117.  
  118. SEE ALSO
  119.      bt_alloc.
  120.  
  121. ------------------------------------------------------------------------------*/
  122. void bt_free(btp)
  123. btree_t *btp;
  124. {
  125. #ifdef DEBUG
  126.     /* validate arguments */
  127.     if (!bt_valid(btp)) {
  128.         BTEPRINT;
  129.         return;
  130.     }
  131. #endif
  132.  
  133.     /* free memory */
  134.     if (btp->sp != NULL) {
  135.         free(btp->sp);
  136.         btp->sp = NULL;
  137.     }
  138.     bt_ndfree(btp->cbtnp);
  139.     btp->cbtnp = NULL;
  140.  
  141.     return;
  142. }
  143.  
  144. /*man---------------------------------------------------------------------------
  145. NAME
  146.      bt_grow - btree grow
  147.  
  148. SYNOPSIS
  149.      #include "btree_.h"
  150.  
  151.      int bt_grow(btp, bttuple_p)
  152.      btree_t *btp;
  153.      bttuple_t *bttuple_p;
  154.  
  155. DESCRIPTION
  156.      The bt_grow function creates a new root for btree btp and inserts
  157.      the (key, child) tuple pointed to by bttuple_p into it.  This
  158.      increases the tree height by one.  This is the only way that the
  159.      height can increase.
  160.  
  161.      bt_grow will fail if one or more of the following is true:
  162.  
  163.      [EINVAL]       btp is not a valid btree pointer.
  164.      [EINVAL]       bttuple_p is the NULL pointer.
  165.      [BTENOPEN]     btp is not open.
  166.  
  167. SEE ALSO
  168.      bt_shrink.
  169.  
  170. DIAGNOSTICS
  171.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  172.      value of -1 is returned, and errno set to indicate the error.
  173.  
  174. ------------------------------------------------------------------------------*/
  175. int bt_grow(btp, bttuple_p)
  176. btree_t *   btp;
  177. bttuple_t * bttuple_p;
  178. {
  179.     int        rs    = 0;
  180.     int        terrno    = 0;
  181.     bpos_t        oldroot    = 0;
  182.     bpos_t        newroot    = 0;
  183.     btpos_t    *    sp    = NULL;
  184.     btnode_t *    btnp    = NULL;
  185.  
  186.     errno = 0;
  187.  
  188. #ifdef DEBUG
  189.     /* validate arguments */
  190.     if ((!bt_valid(btp)) || (bttuple_p == NULL)) {
  191.         BTEPRINT;
  192.         errno = EINVAL;
  193.         return -1;
  194.     }
  195.  
  196.     /* check if not open */
  197.     if (!(btp->flags & BTOPEN)) {
  198.         BTEPRINT;
  199.         errno = BTENOPEN;
  200.         return -1;
  201.     }
  202. #endif
  203.  
  204.     /* pop node off of free list stack */
  205.     rs = bflpop(btp->bp, &newroot);
  206.     if (rs == -1) {
  207.         BTEPRINT;
  208.         return -1;
  209.     }
  210.  
  211.     /* modify header in memory */
  212.     oldroot = btp->bthdr.root;
  213.     btp->bthdr.root = newroot;
  214.     btp->bthdr.height++;
  215.  
  216.     /* add slot to search path */
  217.     btp->sp[0].node = newroot;
  218.     btp->sp[0].key = 1;
  219.     sp = (btpos_t *)calloc(btp->bthdr.height + 1, sizeof(btpos_t));
  220.     if (sp == NULL) {
  221.         BTEPRINT;
  222.         btp->bthdr.root = oldroot;
  223.         btp->bthdr.height--;
  224.         bflpush(btp->bp, &newroot);
  225.         errno = ENOMEM;
  226.         return -1;
  227.     }
  228.     memcpy((void *)(sp + 1), (void *)btp->sp, btp->bthdr.height * sizeof(btpos_t));
  229.     free((void *)btp->sp);
  230.     btp->sp = sp;
  231.     sp = NULL;
  232.  
  233.     /* write new root to file */
  234.     btnp = bt_ndalloc(btp);
  235.     if (btnp == NULL) {
  236.         BTEPRINT;
  237.         terrno = errno;
  238.         btp->bthdr.root = oldroot;
  239.         btp->bthdr.height--;
  240.         bflpush(btp->bp, &newroot);
  241.         errno = terrno;
  242.         return -1;
  243.     }
  244.     memcpy(bt_kychild_p(btnp, 0), (void *)&oldroot, sizeof(bpos_t));
  245.     rs = bt_ndinskey(btp, btnp, (size_t)1, bttuple_p);
  246.     if (rs == -1) {
  247.         BTEPRINT;
  248.         terrno = errno;
  249.         bt_ndfree(btnp);
  250.         btp->bthdr.root = oldroot;
  251.         btp->bthdr.height--;
  252.         bflpush(btp->bp, &newroot);
  253.         errno = terrno;
  254.         return -1;
  255.     }
  256.     rs = bt_ndput(btp, newroot, btnp);
  257.     if (rs == -1) {
  258.         BTEPRINT;
  259.         terrno = errno;
  260.         bt_ndfree(btnp);
  261.         btp->bthdr.root = oldroot;
  262.         btp->bthdr.height--;
  263.         bflpush(btp->bp, &newroot);
  264.         errno = terrno;
  265.         return -1;
  266.     }
  267.     bt_ndfree(btnp);
  268.  
  269.     /* update first and last key positions */
  270.     if (oldroot == 0) {
  271.         btp->bthdr.first = btp->bthdr.last = newroot;
  272.     }
  273.  
  274.     errno = 0;
  275.     return 0;
  276. }
  277.  
  278. /*man---------------------------------------------------------------------------
  279. NAME
  280.      bt_search - search a btree
  281.  
  282. SYNOPSIS
  283.      #include <btree.h>
  284.  
  285.      int bt_search(btp, buf)
  286.      btree_t *btp;
  287.      void *buf;
  288.  
  289. DESCRIPTION
  290.      The bt_search function searches the btree btp for the key pointed to
  291.      by buf.  If it is found, the cursor is set to the location of the key
  292.      and 1 is returned.  If it is not found, the cursor is set to the
  293.      location at which it should be inserted and 0 is returned.
  294.  
  295.      bt_search will fail if one or more of the following is true:
  296.  
  297.      [EINVAL]       btp is not a valid btree pointer.
  298.      [EINVAL]       buf is the NULL pointer.
  299.      [BTELOCK]      btp is not read locked.
  300.  
  301. DIAGNOSTICS
  302.      Upon successful completion, a value of 1 is returned if the key was
  303.      found or a value of 0 if it was not found.  On failure, a value of
  304.      -1 is returned, and errno set to indicate the error.
  305.      
  306. ------------------------------------------------------------------------------*/
  307. int bt_search(btp, buf)
  308. btree_t * btp;
  309. void *    buf;
  310. {
  311.     int    rs    = 0;
  312.     int    spi    = 0;        /* search path index */
  313.     bpos_t    node    = 0;
  314.     int    found    = 0;
  315.  
  316.     errno = 0;
  317.  
  318. #ifdef DEBUG
  319.     /* validate arguments */
  320.     if (!bt_valid(btp)) {
  321.         errno = EINVAL;
  322.         return -1;
  323.     }
  324.     if (buf == NULL) {
  325.         errno = EINVAL;
  326.         return -1;
  327.     }
  328.  
  329.     /* check locks */
  330.     if (!(btp->flags & BTRDLCK)) {
  331.         errno = BTELOCK;
  332.         return -1;
  333.     }
  334. #endif
  335.  
  336.     /* initialize btree structure for search */
  337.     btp->cbtpos.node = 0;        /* initialize cursor */
  338.     btp->cbtpos.key =  0;
  339.     btp->sp[0].node = 0;        /* initialize search path root */
  340.     btp->sp[0].key = 0;
  341.  
  342.     /* search loop */
  343.     node = btp->bthdr.root;
  344.     for (spi = 1; (spi <= btp->bthdr.height); spi++) {
  345.         if (node == 0) {
  346.             BTEPRINT;    /* height value probably incorrect */
  347.             bt_ndinit(btp, btp->cbtnp);
  348.             errno = BTEPANIC;
  349.             return -1;
  350.         }
  351.         btp->sp[spi].node = node;
  352.         rs = bt_ndget(btp, node, btp->cbtnp);
  353.         if (rs == -1) {
  354.             BTEPRINT;
  355.             bt_ndinit(btp, btp->cbtnp);
  356.             return -1;
  357.         }
  358.         found = bt_ndsearch(btp, btp->cbtnp, buf, &btp->sp[spi].key);
  359.         if (found == -1) {
  360.             BTEPRINT;
  361.             bt_ndinit(btp, btp->cbtnp);
  362.             return -1;
  363.         }
  364.         if (found == 0) {    /* go down left subtree */
  365.             node = *bt_kychild_p(btp->cbtnp, btp->sp[spi].key - 1);
  366.         } else {        /* go down right subtree */
  367.             node = *bt_kychild_p(btp->cbtnp, btp->sp[spi].key);
  368.         }
  369.     }
  370.     if (node != 0) {
  371.         BTEPRINT;    /* height value probably incorrect */
  372.         bt_ndinit(btp, btp->cbtnp);
  373.         errno = BTEPANIC;
  374.         return -1;
  375.     }
  376.  
  377.     /* set cursor */
  378.     btp->cbtpos.node = btp->sp[btp->bthdr.height].node;
  379.     btp->cbtpos.key = btp->sp[btp->bthdr.height].key;
  380.  
  381.     errno = 0;
  382.     return ((found == 1) ? 1: 0);
  383. }
  384.  
  385. /*man---------------------------------------------------------------------------
  386. NAME
  387.      bt_shrink - btree shrink
  388.  
  389. SYNOPSIS
  390.      #include "btree_.h"
  391.  
  392.      int bt_shrink(btp, newroot)
  393.      btree_t *btp;
  394.      bpos_t newroot;
  395.  
  396. DESCRIPTION
  397.      The bt_shrink function makes newroot the new root for btree btp
  398.      and puts the old root back in the free list.  This decreases the
  399.      tree height by one.  This is the only way that the height can
  400.      decrease.
  401.  
  402.      bt_shrink will fail if one or more of the following is true:
  403.  
  404.      [EINVAL]       btp is not a valid btree pointer.
  405.      [BTEPANIC]     btp is already empty.
  406.  
  407. SEE ALSO
  408.      bt_grow.
  409.  
  410. DIAGNOSTICS
  411.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  412.      value of -1 is returned, and errno set to indicate the error.
  413.  
  414. ------------------------------------------------------------------------------*/
  415. int bt_shrink(btp, newroot)
  416. btree_t * btp;
  417. bpos_t    newroot;
  418. {
  419.     int        rs    = 0;
  420.     int        terrno    = 0;
  421.     bpos_t        oldroot    = 0;
  422.     btpos_t *    sp    = NULL;
  423.  
  424.     errno = 0;
  425.  
  426. #ifdef DEBUG
  427.     /* validate arguments */
  428.     if (!bt_valid(btp)) {
  429.         BTEPRINT;
  430.         errno = EINVAL;
  431.         return -1;
  432.     }
  433.  
  434.     /* check if not open */
  435.     if (!(btp->flags & BTOPEN)) {
  436.         BTEPRINT;
  437.         errno = BTENOPEN;
  438.         return -1;
  439.     }
  440. #endif
  441.  
  442.     /* check if tree already empty */
  443.     if (btp->bthdr.root == 0) {
  444.         BTEPRINT;
  445.         errno = BTEPANIC;
  446.         return -1;
  447.     }
  448.  
  449.     /* modify header in memory */
  450.     oldroot = btp->bthdr.root;
  451.     btp->bthdr.root = newroot;
  452.     btp->bthdr.height--;
  453.  
  454.     /* remove slot from search path */
  455.     sp = (btpos_t *)calloc(btp->bthdr.height + 1, sizeof(btpos_t));
  456.     if (sp == NULL) {
  457.         BTEPRINT;
  458.         btp->bthdr.root = oldroot;
  459.         btp->bthdr.height++;
  460.         errno = ENOMEM;
  461.         return -1;
  462.     }
  463.     memcpy((void *)(sp + 1), (void *)(btp->sp + 2), btp->bthdr.height * sizeof(btpos_t));
  464.     free((void *)btp->sp);
  465.     btp->sp = sp;
  466.     sp = NULL;
  467.  
  468.     /* push root back onto free list stack */
  469.     rs = bflpush(btp->bp, &oldroot);
  470.     if (rs == -1) {
  471.         BTEPRINT;
  472.         btp->bthdr.root = oldroot;
  473.         btp->bthdr.height++;
  474.         return -1;
  475.     }
  476.  
  477.     /* update first and last key positions */
  478.     if (newroot == 0) {
  479.         btp->bthdr.first = btp->bthdr.last = 0;
  480.     }
  481.  
  482.     errno = 0;
  483.     return 0;
  484. }
  485.  
  486. /*man---------------------------------------------------------------------------
  487. NAME
  488.      bt_valid - validate btree
  489.  
  490. SYNOPSIS
  491.      #include "btree_.h"
  492.  
  493.      bool bt_valid(btp)
  494.      btree_t *btp;
  495.  
  496. DESCRIPTION
  497.      The bt_valid function determines if btp points to a valid btree
  498.      control structure.  If it is valid, TRUE is returned.  If not,
  499.      then FALSE is returned.
  500.  
  501. ------------------------------------------------------------------------------*/
  502. bool bt_valid(btp)
  503. btree_t *btp;
  504. {
  505.     if ((btp < btb) || (btp > (btb + BTOPEN_MAX - 1))) {
  506.         return FALSE;
  507.     }
  508.     if (((size_t)((char *)btp - (char *)btb)) % sizeof(btb[0]) != 0) {
  509.         return FALSE;
  510.     }
  511.  
  512.     return TRUE;
  513. }
  514.