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