home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / c / cbase.zoo / btree101.zoo / btops.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-20  |  19.6 KB  |  847 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)btops.c    1.4 - 90/06/20" */
  5.  
  6. #include <blkio.h>
  7. #include <bool.h>
  8. #include <errno.h>
  9. /*#include <stddef.h*/
  10. /*#include <stdlib.h>*/
  11. /*#include <string.h>*/
  12.  
  13. /* local headers */
  14. #include "btree_.h"
  15.  
  16. /*man---------------------------------------------------------------------------
  17. NAME
  18.      bt_alloc - allocate memory for btree
  19.  
  20. SYNOPSIS
  21.      #include "btree_.h"
  22.  
  23.      int bt_alloc(btp);
  24.      btree_t *btp;
  25.  
  26. DESCRIPTION
  27.      The bt_alloc function allocates the memory needed by btp.  The
  28.      memory is is initialized to all zeros.
  29.  
  30.      bt_alloc will fail if one or more of the following is true:
  31.  
  32.      [EINVAL]       btp is not a valid btree pointer.
  33.      [ENOMEM]       Not enough memory is available for allocation by
  34.                     the calling process.
  35.  
  36. SEE ALSO
  37.      bt_free.
  38.  
  39. DIAGNOSTICS
  40.      Upon successful completion, a value of 0 is returned.  Otherwise,
  41.      a value of -1 is returned, and errno set to indicate the error.
  42.  
  43. ------------------------------------------------------------------------------*/
  44. int bt_alloc(btp)
  45. btree_t *btp;
  46. {
  47. #ifdef DEBUG
  48.     /* validate arguments */
  49.     if (!bt_valid(btp)) {
  50.         BTEPRINT;
  51.         errno = EINVAL;
  52.         return -1;
  53.     }
  54.  
  55.     /* check for memory leak */
  56.     if (btp->fldv != NULL || btp->sp != NULL || btp->cbtnp != NULL) {
  57.         BTEPRINT;
  58.         errno = BTEPANIC;
  59.         return -1;
  60.     }
  61. #endif
  62.     /* field definition array */
  63.     btp->fldv = (btfield_t *)calloc((size_t)btp->fldc, sizeof(*btp->fldv));
  64.     if (btp->fldv == NULL) {
  65.         BTEPRINT;
  66.         errno = ENOMEM;
  67.         return -1;
  68.     }
  69.  
  70.     /* search path (one extra element for when root splits) */
  71.     btp->sp = (btpos_t *)calloc((size_t)(btp->bthdr.height + 1), sizeof(*btp->sp));
  72.     if (btp->sp == NULL) {
  73.         BTEPRINT;
  74.         free(btp->fldv);
  75.         errno = ENOMEM;
  76.         return -1;
  77.     }
  78.  
  79.     /* current node */
  80.     btp->cbtnp = bt_ndalloc(btp);
  81.     if (btp->cbtnp == NULL) {
  82.         BTEPRINT;
  83.         free(btp->fldv);
  84.         free(btp->sp);
  85.         return -1;
  86.     }
  87.  
  88.     errno = 0;
  89.     return 0;
  90. }
  91.  
  92. /*man---------------------------------------------------------------------------
  93. NAME
  94.      bt_blksize - btree block size
  95.  
  96. SYNOPSIS
  97.      #include <btree.h>
  98.  
  99.      size_t bt_blksize(btp)
  100.      btree_t *btp;
  101.  
  102. DESCRIPTION
  103.      bt_blksize returns the size of the blocks in btree file btp.  If
  104.      btp is not a valid open btree, the results are undefined.
  105.      bt_blksize is a macro.
  106.  
  107. ------------------------------------------------------------------------------*/
  108. /* bt_blksize defined in btree_.h. */
  109.  
  110. /*man---------------------------------------------------------------------------
  111. NAME
  112.      bt_delete - delete btree key
  113.  
  114. SYNOPSIS
  115.      #include <btree.h>
  116.  
  117.      int bt_delete(btp)
  118.      btree_t *btp;
  119.  
  120. DESCRIPTION
  121.      The bt_delete function deletes the current key from btree btp.
  122.      The search path must be generated prior to calling bt_delete.
  123.      The cursor is positioned to null.
  124.  
  125.      bt_delete will fail if one or more of the following is true:
  126.  
  127.      [EINVAL]       btp is not a valid btree pointer.
  128.      [BTELOCK]      btree btp is not write locked.
  129.      [BTENKEY]      The cursor is null.
  130.      [BTENOPEN]     btree btp is not open.
  131.  
  132. SEE ALSO
  133.      btdelete, btinsert, btsearch.
  134.  
  135. DIAGNOSTICS
  136.      Upon successful completion, a value of 0 is returned.  Otherwise,
  137.      a value of -1 is returned, and errno set to indicate the error.
  138.  
  139. ------------------------------------------------------------------------------*/
  140. int bt_delete(btp)
  141. btree_t *btp;
  142. {
  143.     btnode_t *    btnp    = NULL;        /* node receiving new key */
  144.     bool        err    = FALSE;    /* error flag */
  145.     btnode_t *    lbtnp    = NULL;        /* left sibling node */
  146.     bpos_t        lsib    = NIL;        /* lsib location */
  147.     /*bpos_t    node    = NIL;        /* node location */
  148.     btnode_t *    pbtnp    = NULL;        /* parent node */
  149.     int        pkn    = 0;        /* parent key number */
  150.     bpos_t        pnode    = 0;        /* parent node location */
  151.     btnode_t *    rbtnp    = NULL;        /* right sibling node */
  152.     bpos_t        rsib    = NIL;        /* rsib location */
  153.     unsigned long    spi    = 0;        /* search path index */
  154.     int        terrno    = 0;        /* tmp errno */
  155.     int        total    = 0;        /* total keys in node and sib */
  156. #ifdef DEBUG
  157.     /* validate arguments */
  158.     if (!bt_valid(btp)) {
  159.         errno = EINVAL;
  160.         return -1;
  161.     }
  162.  
  163.     /* check if not open */
  164.     if (!(btp->flags & BTOPEN)) {
  165.         errno = BTENOPEN;
  166.         return -1;
  167.     }
  168.  
  169.     /* check lock */
  170.     if (!(btp->flags & BTWRLCK)) {
  171.         errno = BTELOCK;
  172.         return -1;
  173.     }
  174.  
  175.     /* check if cursor is null */
  176.     if (btcursor(btp) == NULL) {
  177.         errno = BTENKEY;
  178.         return -1;
  179.     }
  180. #endif
  181.     /* initialize working nodes */
  182.     btnp = bt_ndalloc(btp);
  183.     if (btnp == NULL) {
  184.         BTEPRINT;
  185.         return -1;
  186.     }
  187.     lbtnp = bt_ndalloc(btp);    /* left sibling */
  188.     if (lbtnp == NULL) {
  189.         BTEPRINT;
  190.         terrno = errno;
  191.         bt_ndfree(btnp);
  192.         errno = terrno;
  193.         return -1;
  194.     }
  195.     rbtnp = bt_ndalloc(btp);    /* right sibling */
  196.     if (rbtnp == NULL) {
  197.         BTEPRINT;
  198.         terrno = errno;
  199.         bt_ndfree(btnp);
  200.         bt_ndfree(lbtnp);
  201.         errno = terrno;
  202.         return -1;
  203.     }
  204.     pbtnp = bt_ndalloc(btp);    /* parent */
  205.     if (pbtnp == NULL) {
  206.         BTEPRINT;
  207.         terrno = errno;
  208.         bt_ndfree(btnp);
  209.         bt_ndfree(lbtnp);
  210.         bt_ndfree(rbtnp);
  211.         errno = terrno;
  212.         return -1;
  213.     }
  214.  
  215.     /* initialize btnp with current node */
  216.     if (bt_ndcopy(btp, btnp, btp->cbtnp) == -1) {
  217.         BTEPRINT;
  218.         terrno = errno;
  219.         bt_ndfree(btnp);
  220.         bt_ndfree(lbtnp);
  221.         bt_ndfree(rbtnp);
  222.         bt_ndfree(pbtnp);
  223.         errno = terrno;
  224.         return -1;
  225.     }
  226.  
  227.     /* delete key from node */
  228.     if (bt_nddelkey(btp, btnp, btp->cbtpos.key) == -1) {
  229.         BTEPRINT;
  230.         terrno = errno;
  231.         bt_ndfree(btnp);
  232.         bt_ndfree(lbtnp);
  233.         bt_ndfree(rbtnp);
  234.         bt_ndfree(pbtnp);
  235.         errno = terrno;
  236.         return -1;
  237.     }
  238.  
  239.     /* set modify bit in in-core header and write to file */
  240.     btp->bthdr.flags |= BTHMOD;
  241.     if (bputhf(btp->bp, sizeof(bpos_t),
  242.                 (char *)&btp->bthdr + sizeof(bpos_t),
  243.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  244.         BTEPRINT;
  245.         terrno = errno;
  246.         bt_ndfree(btnp);
  247.         bt_ndfree(lbtnp);
  248.         bt_ndfree(rbtnp);
  249.         bt_ndfree(pbtnp);
  250.         errno = terrno;
  251.         return -1;
  252.     }
  253.     if (bsync(btp->bp) == -1) {
  254.         BTEPRINT;
  255.         terrno = errno;
  256.         bt_ndfree(btnp);
  257.         bt_ndfree(lbtnp);
  258.         bt_ndfree(rbtnp);
  259.         bt_ndfree(pbtnp);
  260.         errno = terrno;
  261.         return -1;
  262.     }
  263.  
  264.     /* loop from leaf node to root */
  265.     for (spi = 0; spi < btp->bthdr.height; ++spi) {
  266.         /* write to disk if node not too small */
  267. /*??*/        if (btnp->n >= bt_ndmin(btp) || spi == btp->bthdr.height - 1 && btnp->n != 0) {
  268.             if (bt_ndput(btp, btp->sp[spi].node, btnp) == -1) {
  269.                 BTEPRINT;
  270.                 err = TRUE;
  271.                 break;
  272.             }
  273.             break;
  274.         }
  275.         if (spi == btp->bthdr.height - 1) {        /* empty root */
  276.             if (bt_shrink(btp, bt_kychildp(btnp, 0)) == -1) {
  277.                 BTEPRINT;
  278.                 err = TRUE;
  279.                 break;
  280.             }
  281.             break;
  282.         }
  283.  
  284.         /* node needs more keys */
  285.         /* try to shift keys with siblings */
  286.         /* read in parent node */
  287.         if (bt_ndget(btp, btp->sp[spi + 1].node, pbtnp) == -1) {
  288.             BTEPRINT;
  289.             err = TRUE;
  290.             break;
  291.         }
  292.         /* get locations of nodes */
  293.         /*node = btp->sp[spi].node;*/
  294.         pnode = btp->sp[spi + 1].node;
  295.         pkn = btp->sp[spi + 1].key - 1;
  296.         if (pkn == 0) {
  297.             lsib = NIL;
  298.         } else {
  299.             lsib = btnp->lsib;
  300.         }
  301.         if (pkn == pbtnp->n) {
  302.             rsib = NIL;
  303.         } else {
  304.             rsib = btnp->rsib;
  305.         }
  306.  
  307.         /* try shifting keys with right sibling */
  308.         if (rsib != NIL) {
  309.             if (bt_ndget(btp, rsib, rbtnp) == -1) {
  310.                 BTEPRINT;
  311.                 err = TRUE;
  312.                 break;
  313.             }
  314.             total = btnp->n + rbtnp->n;
  315.             if (total >= 2 * bt_ndmin(btp)) {
  316.                 if (bt_ndshift(btp, btnp, rbtnp, pbtnp, pkn + 1, pnode) == -1) {
  317.                     BTEPRINT;
  318.                     err = TRUE;
  319.                     break;
  320.                 }
  321.                 break;
  322.             }
  323.         }
  324.  
  325.         /* try shifting keys with left sibling */
  326.         if (lsib != NIL) {
  327.             if (bt_ndget(btp, lsib, lbtnp) == -1) {
  328.                 BTEPRINT;
  329.                 err = TRUE;
  330.                 break;
  331.             }
  332.             total = lbtnp->n + btnp->n;
  333.             if (total >= 2 * bt_ndmin(btp)) {
  334.                 btp->sp[spi].key = lbtnp->n + btp->sp[spi].key;
  335.                 if (bt_ndshift(btp, lbtnp, btnp, pbtnp, pkn, pnode) == -1) {
  336.                     BTEPRINT;
  337.                     err = TRUE;
  338.                     break;
  339.                 }
  340.                 break;
  341.             }
  342.         }
  343.  
  344.         /* try fusing with right sibling */
  345.         if (rsib != NIL) {
  346.             if (bt_ndfuse(btp, btnp, rbtnp, pbtnp, pkn + 1) == -1) {
  347.                 BTEPRINT;
  348.                 err = TRUE;
  349.                 break;
  350.             }
  351.             if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
  352.                 BTEPRINT;
  353.                 err = TRUE;
  354.                 break;
  355.             }
  356.             continue;
  357.         }
  358.  
  359.         /* try fusing with left sibling */
  360.         if (lsib != NIL) {
  361.             if (bt_ndfuse(btp, lbtnp, btnp, pbtnp, pkn) == -1) {
  362.                 BTEPRINT;
  363.                 err = TRUE;
  364.                 break;
  365.             }
  366.             if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
  367.                 BTEPRINT;
  368.                 err = TRUE;
  369.                 break;
  370.             }
  371.             continue;
  372.         }
  373.  
  374.         BTEPRINT;
  375.         errno = BEPANIC;
  376.         err = TRUE;
  377.         break;
  378.     }
  379.     if (err) {
  380.         BTEPRINT;
  381.         terrno = errno;
  382.         bt_ndfree(btnp);
  383.         bt_ndfree(lbtnp);
  384.         bt_ndfree(rbtnp);
  385.         bt_ndfree(pbtnp);
  386.         errno = terrno;
  387.         return -1;
  388.     }
  389.  
  390.     bt_ndfree(btnp);
  391.     bt_ndfree(lbtnp);
  392.     bt_ndfree(rbtnp);
  393.     bt_ndfree(pbtnp);
  394.  
  395.     /* decrement key count in header */
  396.     btp->bthdr.keycnt--;
  397.  
  398.     /* clear modify bit in in-core header and write to file */
  399.     btp->bthdr.flags &= ~BTHMOD;
  400.     if (bputhf(btp->bp, sizeof(bpos_t),
  401.                 (char *)&btp->bthdr + sizeof(bpos_t),
  402.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  403.         BTEPRINT;
  404.         return -1;
  405.     }
  406.     if (bsync(btp->bp) == -1) {
  407.         BTEPRINT;
  408.         return -1;
  409.     }
  410.  
  411.     /* set cursor to null */
  412.     btp->cbtpos.node = NIL;
  413.     btp->cbtpos.key = 0;
  414.     bt_ndinit(btp, btp->cbtnp);
  415.  
  416.     errno = 0;
  417.     return 0;
  418. }
  419.  
  420. /*man---------------------------------------------------------------------------
  421. NAME
  422.      bt_free - free memory allocated for btree
  423.  
  424. SYNOPSIS
  425.      #include "btree_.h"
  426.  
  427.      void bt_free(btp)
  428.      btree_t *btp;
  429.  
  430. DESCRIPTION
  431.      The bt_free function frees all memory allocated for btree btp.
  432.      If btp is not a valid btree, no action is taken.
  433.  
  434. SEE ALSO
  435.      bt_alloc.
  436.  
  437. ------------------------------------------------------------------------------*/
  438. void bt_free(btp)
  439. btree_t *btp;
  440. {
  441. #ifdef DEBUG
  442.     /* validate arguments */
  443.     if (!bt_valid(btp)) {
  444.         BTEPRINT;
  445.         return;
  446.     }
  447. #endif
  448.     /* free memory */
  449.     if (btp->fldv != NULL) free(btp->fldv);
  450.     btp->fldv = NULL;
  451.     if (btp->sp != NULL) free(btp->sp);
  452.     btp->sp = NULL;
  453.     bt_ndfree(btp->cbtnp);
  454.     btp->cbtnp = NULL;
  455.  
  456.     return;
  457. }
  458.  
  459. /*man---------------------------------------------------------------------------
  460. NAME
  461.      bt_fvalid - validate field definition list
  462.  
  463. SYNOPSIS
  464.      #include "btree_.h"
  465.  
  466.      bool bt_fvalid(keysize, fldc, fldv)
  467.      size_t keysize;
  468.      int fldc;
  469.      const btfield_t fldv[];
  470.  
  471. DESCRIPTION
  472.      The bt_fvalid function determines if keysize, fldc, and fldv
  473.      constitute a valid btree field definition list.  If valid, then
  474.      TRUE is returned.  If not, then FALSE is returned.
  475.  
  476. ------------------------------------------------------------------------------*/
  477. bool bt_fvalid(keysize, fldc, fldv)
  478. size_t keysize;
  479. int fldc;
  480. const btfield_t fldv[];
  481. {
  482.     size_t end = 0;
  483.     int i = 0;
  484.  
  485.     if (keysize < 1 || fldc < 1 || fldv == NULL) {
  486.         return FALSE;
  487.     }
  488.  
  489.     for (i = 0; i < fldc; ++i) {
  490.         if (fldv[i].offset < end) {
  491.             return FALSE;
  492.         }
  493.         if (fldv[i].len < 1) {
  494.             return FALSE;
  495.         }
  496.         end = fldv[i].offset + fldv[i].len;
  497.         if (end > keysize) {
  498.             return FALSE;
  499.         }
  500.         if (fldv[i].cmp == NULL) {
  501.             return FALSE;
  502.         }
  503.         if (fldv[i].flags & ~(BT_FFLAGS)) {
  504.             return FALSE;
  505.         }
  506.     }
  507.  
  508.     return TRUE;
  509. }
  510.  
  511. /*man---------------------------------------------------------------------------
  512. NAME
  513.      bt_grow - btree grow
  514.  
  515. SYNOPSIS
  516.      #include "btree_.h"
  517.  
  518.      int bt_grow(btp, bttplp)
  519.      btree_t *btp;
  520.      const bttpl_t *bttplp;
  521.  
  522. DESCRIPTION
  523.      The bt_grow function creates a new root for btree btp and inserts
  524.      the (key, child) tuple pointed to by bttplp into the new root
  525.      node.  This increases the tree height by one; it is the only way
  526.      by which the height can increase.  If the tree was previously
  527.      empty, the first and last key links in the in-core header are set
  528.      to the new root.
  529.  
  530.      bt_grow will fail if one or more of the following is true:
  531.  
  532.      [EINVAL]       btp is not a valid btree pointer.
  533.      [EINVAL]       bttplp is the NULL pointer.
  534.      [BTENOPEN]     btp is not open.
  535.  
  536. SEE ALSO
  537.      bt_shrink.
  538.  
  539. DIAGNOSTICS
  540.      Upon successful completion, a value of 0 is returned.  Otherwise,
  541.      a value of -1 is returned, and errno set to indicate the error.
  542.  
  543. ------------------------------------------------------------------------------*/
  544. int bt_grow(btp, bttplp)
  545. btree_t *btp;
  546. const bttpl_t *bttplp;
  547. {
  548.     btnode_t *    btnp    = NULL;
  549.     bpos_t        oldroot    = NIL;
  550.     bpos_t        newroot    = NIL;
  551.     btpos_t    *    sp    = NULL;
  552.     int        terrno    = 0;
  553. #ifdef DEBUG
  554.     /* validate arguments */
  555.     if (!bt_valid(btp) || bttplp == NULL) {
  556.         BTEPRINT;
  557.         errno = EINVAL;
  558.         return -1;
  559.     }
  560.  
  561.     /* check if not open */
  562.     if (!(btp->flags & BTOPEN)) {
  563.         BTEPRINT;
  564.         errno = BTENOPEN;
  565.         return -1;
  566.     }
  567. #endif
  568.     /* get node from free list */
  569.     if (bflpop(btp->bp, &newroot) == -1) {
  570.         BTEPRINT;
  571.         return -1;
  572.     }
  573.  
  574.     /* set root link in in-core header */
  575.     oldroot = btp->bthdr.root;
  576.     btp->bthdr.root = newroot;
  577.  
  578.     /* add element to search path */
  579.     btp->sp[btp->bthdr.height].node = newroot;
  580.     btp->sp[btp->bthdr.height].key = 1;
  581.     ++btp->bthdr.height;
  582.     sp = (btpos_t *)realloc(btp->sp, (size_t)(btp->bthdr.height + 1) * sizeof(*sp));
  583.     if (sp == NULL) {
  584.         BTEPRINT;
  585.         btp->bthdr.root = oldroot;
  586.         --btp->bthdr.height;
  587.         errno = ENOMEM;
  588.         return -1;
  589.     }
  590.     btp->sp = sp;
  591.     sp = NULL;
  592.     btp->sp[btp->bthdr.height].node = NIL;
  593.     btp->sp[btp->bthdr.height].key = 0;
  594.  
  595.     /* write new root to file */
  596.     btnp = bt_ndalloc(btp);
  597.     if (btnp == NULL) {
  598.         BTEPRINT;
  599.         terrno = errno;
  600.         btp->bthdr.root = oldroot;
  601.         --btp->bthdr.height;
  602.         bflpush(btp->bp, &newroot);
  603.         errno = terrno;
  604.         return -1;
  605.     }
  606.     *bt_kychildp(btnp, 0) = oldroot;    /* link to old root */
  607.     if (bt_ndinskey(btp, btnp, 1, bttplp) == -1) {
  608.         BTEPRINT;
  609.         terrno = errno;
  610.         bt_ndfree(btnp);
  611.         btp->bthdr.root = oldroot;
  612.         --btp->bthdr.height;
  613.         bflpush(btp->bp, &newroot);
  614.         errno = terrno;
  615.         return -1;
  616.     }
  617.     if (bt_ndput(btp, newroot, btnp) == -1) {
  618.         BTEPRINT;
  619.         terrno = errno;
  620.         bt_ndfree(btnp);
  621.         btp->bthdr.root = oldroot;
  622.         --btp->bthdr.height;
  623.         bflpush(btp->bp, &newroot);
  624.         errno = terrno;
  625.         return -1;
  626.     }
  627.     bt_ndfree(btnp);
  628.  
  629.     /* update first and last key links */
  630.     if (oldroot == NIL) {
  631.         btp->bthdr.first = btp->bthdr.last = newroot;
  632.     }
  633.  
  634.     errno = 0;
  635.     return 0;
  636. }
  637.  
  638. /*man---------------------------------------------------------------------------
  639. NAME
  640.      bt_search - search a btree
  641.  
  642. SYNOPSIS
  643.      #include <btree.h>
  644.  
  645.      int bt_search(btp, buf)
  646.      btree_t *btp;
  647.      const void *buf;
  648.  
  649. DESCRIPTION
  650.      The bt_search function searches the btree btp for the key pointed
  651.      to by buf.  If it is found, the cursor is set to the location of
  652.      the key and 1 is returned.  If it is not found, the cursor is set
  653.      to the location at which it should be inserted and 0 is returned.
  654.      Note that in the latter case the cursor may be positioned to an
  655.      empty location.
  656.  
  657.      bt_search will fail if one or more of the following is true:
  658.  
  659.      [EINVAL]       btp is not a valid btree pointer.
  660.      [EINVAL]       buf is the NULL pointer.
  661.  
  662. DIAGNOSTICS
  663.      Upon successful completion, a value of 1 is returned if the key
  664.      was found or a value of 0 if it was not found.  On failure, a
  665.      value of -1 is returned, and errno set to indicate the error.
  666.  
  667. ------------------------------------------------------------------------------*/
  668. int bt_search(btp, buf)
  669. btree_t *btp;
  670. const void *buf;
  671. {
  672.     int        found    = 0;        /* found flag */
  673.     bpos_t        node    = NIL;        /* node position */
  674.     unsigned long    spi    = 0;        /* search path index */
  675. #ifdef DEBUG
  676.     /* validate arguments */
  677.     if (!bt_valid(btp) || buf == NULL) {
  678.         errno = EINVAL;
  679.         return -1;
  680.     }
  681. #endif
  682.     /* initialize btree structure for search */
  683.     btp->cbtpos.node = NIL;            /* init cursor */
  684.     btp->cbtpos.key = 0;
  685.     btp->sp[btp->bthdr.height].node = NIL;    /* init search path head */
  686.     btp->sp[btp->bthdr.height].key = 0;
  687.  
  688.     /* loop from root to leaf node */
  689.     /* Note: spi is unsigned, so spi >= 0 will not terminate loop */
  690.     spi = btp->bthdr.height;
  691.     for (node = btp->bthdr.root; node != NIL;
  692.             node = *bt_kychildp(btp->cbtnp, btp->sp[spi].key - 1)) {
  693.         btp->sp[--spi].node = node;
  694.         if (bt_ndget(btp, node, btp->cbtnp) == -1) {
  695.             BTEPRINT;
  696.             return -1;
  697.         }
  698.         found = bt_ndsearch(btp, btp->cbtnp, buf, &btp->sp[spi].key);
  699.         if (found == -1) {
  700.             BTEPRINT;
  701.             return -1;
  702.         }
  703.         if (found == 1) {
  704.             btp->sp[spi].key++;    /* move forward one */
  705.         }
  706.         if (spi == 0) {            /* leaf node */
  707.             break;
  708.         }
  709.     }
  710.     if (spi != 0) {
  711.         BTEPRINT;    /* height value probably incorrect */
  712.         errno = BTEPANIC;
  713.         return -1;
  714.     }
  715.  
  716.     /* set cursor */
  717.     btp->cbtpos.node = btp->sp[0].node;
  718.     btp->cbtpos.key = btp->sp[0].key - ((found == 1) ? 1 : 0);
  719.  
  720.     errno = 0;
  721.     return ((found == 1) ? 1: 0);
  722. }
  723.  
  724. /*man---------------------------------------------------------------------------
  725. NAME
  726.      bt_shrink - btree shrink
  727.  
  728. SYNOPSIS
  729.      #include "btree_.h"
  730.  
  731.      int bt_shrink(btp, newrootp)
  732.      btree_t *btp;
  733.      const bpos_t *newrootp;
  734.  
  735. DESCRIPTION
  736.      The bt_shrink function makes *newrootp the new root for btree btp
  737.      and returns the old root back to the free list.  This decreases
  738.      the tree height by one; it is the only way in which the height
  739.      can decrease.  If the old root node was also a leaf node, the
  740.      first and last key links in the in-core header are set to NIL.
  741.  
  742.      bt_shrink will fail if one or more of the following is true:
  743.  
  744.      [EINVAL]       btp is not a valid btree pointer.
  745.      [BTEPANIC]     btp is already empty.
  746.  
  747. SEE ALSO
  748.      bt_grow.
  749.  
  750. DIAGNOSTICS
  751.      Upon successful completion, a value of 0 is returned.  Otherwise,
  752.      a value of -1 is returned, and errno set to indicate the error.
  753.  
  754. ------------------------------------------------------------------------------*/
  755. int bt_shrink(btp, newrootp)
  756. btree_t *btp;
  757. const bpos_t *newrootp;
  758. {
  759.     bpos_t        newroot    = NIL;
  760.     bpos_t        oldroot    = NIL;
  761.     btpos_t *    sp    = NULL;
  762. #ifdef DEBUG
  763.     /* validate arguments */
  764.     if (!bt_valid(btp) || newrootp == NULL) {
  765.         BTEPRINT;
  766.         errno = EINVAL;
  767.         return -1;
  768.     }
  769.  
  770.     /* check if not open */
  771.     if (!(btp->flags & BTOPEN)) {
  772.         BTEPRINT;
  773.         errno = BTENOPEN;
  774.         return -1;
  775.     }
  776.  
  777.     /* check if tree already empty */
  778.     if (btp->bthdr.root == NIL) {
  779.         BTEPRINT;
  780.         errno = BTEPANIC;
  781.         return -1;
  782.     }
  783. #endif
  784.     /* set root link in in-core header */
  785.     oldroot = btp->bthdr.root;
  786.     btp->bthdr.root = newroot = *newrootp;
  787.  
  788.     /* remove element from search path */
  789.     --btp->bthdr.height;
  790.     sp = (btpos_t *)realloc(btp->sp, (size_t)(btp->bthdr.height + 1) * sizeof(*sp));
  791.     if (sp == NULL) {
  792.         BTEPRINT;
  793.         btp->bthdr.root = oldroot;
  794.         ++btp->bthdr.height;
  795.         errno = ENOMEM;
  796.         return -1;
  797.     }
  798.     btp->sp = sp;
  799.     sp = NULL;
  800.     btp->sp[btp->bthdr.height].node = NIL;
  801.     btp->sp[btp->bthdr.height].key = 0;
  802.  
  803.     /* push root back onto free list stack */
  804.     if (bflpush(btp->bp, &oldroot) == -1) {
  805.         BTEPRINT;
  806.         btp->bthdr.root = oldroot;
  807.         ++btp->bthdr.height;
  808.         return -1;
  809.     }
  810.  
  811.     /* update first and last key links */
  812.     if (newroot == NIL) {
  813.         btp->bthdr.first = btp->bthdr.last = NIL;
  814.     }
  815.  
  816.     errno = 0;
  817.     return 0;
  818. }
  819.  
  820. /*man---------------------------------------------------------------------------
  821. NAME
  822.      bt_valid - validate btree pointer
  823.  
  824. SYNOPSIS
  825.      #include "btree_.h"
  826.  
  827.      bool bt_valid(btp)
  828.      btree_t *btp;
  829.  
  830. DESCRIPTION
  831.      The bt_valid function determines if btp is a valid btree pointer.
  832.      If valid, then TRUE is returned.  If not, then FALSE is returned.
  833.  
  834. ------------------------------------------------------------------------------*/
  835. bool bt_valid(btp)
  836. btree_t *btp;
  837. {
  838.     if (btp < btb || btp > (btb + BTOPEN_MAX - 1)) {
  839.         return FALSE;
  840.     }
  841.     if ((((char *)btp - (char *)btb)) % sizeof(*btb) != 0) {
  842.         return FALSE;
  843.     }
  844.  
  845.     return TRUE;
  846. }
  847.