home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / NDOPS.C < prev   
Text File  |  1989-08-31  |  23KB  |  1,044 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "ndops.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 "btree_.h"
  11.  
  12. /*man---------------------------------------------------------------------------
  13. NAME
  14.      bt_ndalloc - allocate memory for node
  15.  
  16. SYNOPSIS
  17.      #include "btree_.h"
  18.  
  19.      btnode_t *bt_ndalloc(btp)
  20.      btree_t *btp;
  21.  
  22. DESCRIPTION
  23.      The bt_ndalloc function creates a node of the appropriate configuration
  24.      for btree btp and initializes it.  The address of the node created is
  25.      returned.
  26.  
  27.      bt_ndalloc 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_ndfree, bt_ndinit.
  36.  
  37. DIAGNOSTICS
  38.      On failure, a value of NULL is returned, and errno set to indicate
  39.      the error.
  40.  
  41. ------------------------------------------------------------------------------*/
  42. btnode_t *bt_ndalloc(btp)
  43. btree_t *btp;
  44. {
  45.     btnode_t *    btnp    = NULL;
  46.     bttuple_t    bttuple;    /* used only for sizeof */
  47.  
  48.     errno = 0;
  49.  
  50.     /* initialize storage */
  51.     memset((void *)&bttuple, 0, sizeof(bttuple));
  52.  
  53. #ifdef DEBUG
  54.     /* validate arguments */
  55.     if (!bt_valid(btp)) {
  56.         BTEPRINT;
  57.         errno = EINVAL;
  58.         return NULL;
  59.     }
  60.  
  61.     /* check if not open */
  62.     if (!(btp->flags & BTOPEN)) {
  63.         BTEPRINT;
  64.         errno = BTENOPEN;
  65.         return NULL;
  66.     }
  67. #endif
  68.  
  69.     /* allocate storage for main node structure */
  70.     /* (calloc is used throughout to automatically set all bits 0) */
  71.     btnp = (btnode_t *)calloc(1, sizeof(btnode_t));
  72.     if (btnp == NULL) {
  73.         BTEPRINT;
  74.         errno = ENOMEM;
  75.         return NULL;
  76.     }
  77.     btnp->n = 0;
  78.     btnp->lsib = 0;
  79.     btnp->rsib = 0;
  80.     /* key array [1..(m - 1)] plus one extra for overflow */
  81.     btnp->key_p = calloc(btp->bthdr.m, btp->bthdr.keysize);
  82.     if (btnp->key_p == NULL) {
  83.         BTEPRINT;
  84.         free(btnp);
  85.         errno = ENOMEM;
  86.         return NULL;
  87.     }
  88.     /* child node file postion array [0..m] plus one extra for overflow */
  89.     btnp->child_p = (size_t *)calloc(btp->bthdr.m + 1, sizeof(bttuple.child));
  90.     if (btnp->child_p == NULL) {
  91.         BTEPRINT;
  92.         free(btnp->key_p);
  93.         free(btnp);
  94.         errno = ENOMEM;
  95.         return NULL;
  96.     }
  97.  
  98.     errno = 0;
  99.     return btnp;
  100. }
  101.  
  102. /*man---------------------------------------------------------------------------
  103. NAME
  104.      bt_ndcopy - copy btree node
  105.  
  106. SYNOPSIS
  107.      #include "btree_.h"
  108.  
  109.      int bt_ndcopy(btp, tbtnp, sbtnp)
  110.      btree_t *btp;
  111.      btnode_t *tbtnp;
  112.      btnode_t *sbtnp;
  113.  
  114. DESCRIPTION
  115.      The bt_ndcopy function makes an exact copy of source node sbtnp in
  116.      target node tbtnp.
  117.  
  118.      bt_ndcopy will fail if one or more of the following is true:
  119.  
  120.      [EINVAL]       btp is not a valid btree pointer.
  121.      [EINVAL]       tbtnp or sbtnp is the NULL pointer.
  122.  
  123. DIAGNOSTICS
  124.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  125.      value of -1 is returned, and errno set to indicate the error.
  126.  
  127. ------------------------------------------------------------------------------*/
  128. int bt_ndcopy(btp, tbtnp, sbtnp)
  129. btree_t *  btp;
  130. btnode_t * tbtnp;
  131. btnode_t * sbtnp;
  132. {
  133.     bttuple_t bttuple;        /* only used for sizeof */
  134.  
  135.     errno = 0;
  136.  
  137.     /* initialize storage */
  138.     memset((void *)&bttuple, 0, sizeof(bttuple));
  139.  
  140. #ifdef DEBUG
  141.     /* validate arguments */
  142.     if ((!bt_valid(btp)) || (tbtnp == NULL) || (sbtnp == NULL)) {
  143.         BTEPRINT;
  144.         errno = EINVAL;
  145.         return -1;
  146.     }
  147. #endif
  148.  
  149.     /* copy node sbtnp into tbtnp */
  150.     tbtnp->n = sbtnp->n;
  151.     tbtnp->lsib = sbtnp->lsib;
  152.     tbtnp->rsib = sbtnp->rsib;
  153.     memcpy(bt_kykey_p(btp, tbtnp, 1), bt_kykey_p(btp, sbtnp, 1), btp->bthdr.m * btp->bthdr.keysize);
  154.     memcpy((void *)bt_kychild_p(tbtnp, 0), (void *)bt_kychild_p(sbtnp, 0), (btp->bthdr.m + 1) * sizeof(bttuple.child));
  155.  
  156.     errno = 0;
  157.     return 0;
  158. }
  159.  
  160. /*man---------------------------------------------------------------------------
  161. NAME
  162.      bt_nddelkey - delete key from btree node
  163.  
  164. SYNOPSIS
  165.      #include "btree_.h"
  166.  
  167.      int bt_nddelkey(btp, btnp, kn)
  168.      btree_t *btp;
  169.      btnode_t *btnp;
  170.      size_t kn;
  171.  
  172. DESCRIPTION
  173.      The bt_nddelkey function deletes the knth tuple from node btnp.
  174.  
  175.      bt_nddelkey will fail if one or more of the following is true:
  176.  
  177.      [EINVAL]       btp is not a valid btree pointer.
  178.      [EINVAL]       btnp is the NULL pointer.
  179.  
  180. SEE ALSO
  181.      bt_ndinskey.
  182.  
  183. DIAGNOSTICS
  184.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  185.      value of -1 is returned, and errno set to indicate the error.
  186.  
  187. ------------------------------------------------------------------------------*/
  188. int bt_nddelkey(btp, btnp, kn)
  189. btree_t *  btp;
  190. btnode_t * btnp;
  191. size_t     kn;
  192. {
  193. #ifdef DEBUG
  194.     /* validate arguments */
  195.     if ((!bt_valid(btp)) || (btnp == NULL)) {
  196.         BTEPRINT;
  197.         errno = EINVAL;
  198.         return -1;
  199.     }
  200. #endif
  201.  
  202.     return bt_kyshift(btp, btnp, kn + 1, -1);
  203. }
  204.  
  205. /*man---------------------------------------------------------------------------
  206. NAME
  207.      bt_ndfree - free memory allocated for btree node
  208.  
  209. SYNOPSIS
  210.      #include "btree_.h"
  211.  
  212.      void bt_ndfree(btnp)
  213.      btnode_t *btnp;
  214.  
  215. DESCRIPTION
  216.      The bt_ndfree function frees all memory allocated for btree node
  217.      btnp.
  218.  
  219. SEE ALSO
  220.      bt_ndalloc.
  221.  
  222. ------------------------------------------------------------------------------*/
  223. void bt_ndfree(btnp)
  224. btnode_t *btnp;        /* <--> */
  225. {
  226.  
  227.     if (btnp == NULL) {
  228.         return;
  229.     }
  230.     free(btnp->child_p);
  231.     btnp->child_p = NULL;
  232.     free(btnp->key_p);
  233.     btnp->key_p = NULL;
  234.     free(btnp);
  235.  
  236.     return;
  237. }
  238.  
  239. /*man---------------------------------------------------------------------------
  240. NAME
  241.      bt_ndfuse - btree node fuse
  242.  
  243. SYNOPSIS
  244.      #include "btree_.h"
  245.  
  246.      int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  247.      btree_t *btp;
  248.      btnode_t *lbtnp;
  249.      btnode_t *rbtnp;
  250.      btnode_t *pbtnp;
  251.      size_t pkn;
  252.  
  253. DESCRIPTION
  254.      The bt_ndfuse function fuses nodes lbtnp and rbtnp into a single
  255.      node in lbtnp.  pbtnp is the parent of both nodes and pkn is the
  256.      key in the parent node between the two children being fused.  All
  257.      sibling connections are handled.  The right node is placed back
  258.      in the free list.  The parent is modified for the effect of the
  259.      fusion.
  260.  
  261.      bt_ndfuse will fail if one or more of the following is true:
  262.  
  263.      [EINVAL]       btp is not a valid btree pointer.
  264.      [EINVAL]       btnp, rbtnp, or pbtnp is NULL.
  265.      [BTENOPEN]     btp is not open.
  266.  
  267. SEE ALSO
  268.      bt_ndshift, bt_ndsplit.
  269.  
  270. DIAGNOSTICS
  271.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  272.      value of -1 is returned, and errno set to indicate the error.
  273.  
  274. ------------------------------------------------------------------------------*/
  275. int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  276. btree_t *  btp;
  277. btnode_t * lbtnp;
  278. btnode_t * rbtnp;
  279. btnode_t * pbtnp;
  280. size_t     pkn;
  281. {
  282.     int        rs    = 0;
  283.     bool        leaf    = FALSE;
  284.     bttuple_t    bttuple;
  285.  
  286.     errno = 0;
  287.  
  288. #ifdef DEBUG
  289.     /* validate arguments */
  290.     if (!bt_valid(btp)) {
  291.         BTEPRINT;
  292.         errno = EINVAL;
  293.         return NULL;
  294.     }
  295.     if ((lbtnp == NULL) || (rbtnp == NULL)  || (pbtnp == NULL)) {
  296.         BTEPRINT;
  297.         errno = EINVAL;
  298.         return -1;
  299.     }
  300.     if ((pkn == 0) || (pkn > pbtnp->n)) {
  301.         BTEPRINT;
  302.         errno = EINVAL;
  303.         return -1;
  304.     }
  305. #endif
  306.  
  307.     /* check if leaf */
  308.     if (*bt_kychild_p(lbtnp, 0) == 0) {
  309.         leaf = TRUE;
  310.     }
  311.  
  312.     /* check if too many keys for fusion */
  313.     if ((lbtnp->n + rbtnp->n) > (bt_ndmax(btp) - (leaf ? 0 : 1))) {
  314.         BTEPRINT;
  315.         errno = BTEPANIC;
  316.         return -1;
  317.     }
  318.  
  319.     /* bring down parent key pkn if internal node */
  320.     if (!leaf) {
  321.         bttuple.key_p = calloc(1, btp->bthdr.keysize);
  322.         if (bttuple.key_p == NULL) {
  323.             BTEPRINT;
  324.             errno = ENOMEM;
  325.             return -1;
  326.         }
  327.         rs = bt_kyread(btp, pbtnp, pkn, &bttuple);
  328.         if (rs == -1) {
  329.             BTEPRINT;
  330.             free(bttuple.key_p);
  331.             return -1;
  332.         }
  333.         bttuple.child = *bt_kychild_p(rbtnp, (size_t)0);
  334.         rs = bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttuple);
  335.         if (rs == -1) {
  336.             BTEPRINT;
  337.             free(bttuple.key_p);
  338.             return -1;
  339.         }
  340.         free(bttuple.key_p);
  341.     }
  342.  
  343.     /* move keys from rbtnp to lbtnp */
  344.     rs = bt_kymvleft(btp, lbtnp, rbtnp, rbtnp->n);
  345.     if (rs == -1) {
  346.         BTEPRINT;
  347.         return -1;
  348.     }
  349.  
  350.     /* put right node back on free list */
  351.     rs = bflpush(btp->bp, &lbtnp->rsib);
  352.     if (rs == -1) {
  353.         BTEPRINT;
  354.         return -1;
  355.     }
  356.  
  357.     /* fix sibling connections */
  358.     lbtnp->rsib = rbtnp->rsib;
  359.     if (lbtnp->rsib != 0) {
  360.         rs = bputbf(btp->bp, lbtnp->rsib, offsetof(btnode_t, lsib), (void *)&rbtnp->lsib, sizeof(rbtnp->lsib));
  361.         if (rs == -1) {
  362.             BTEPRINT;
  363.             return -1;
  364.         }
  365.     } else if (leaf) {
  366.         btp->bthdr.last = rbtnp->lsib;
  367.     }
  368.     bt_ndinit(btp, rbtnp);
  369.  
  370.     /* fix parent */
  371.     rs = bt_nddelkey(btp, pbtnp, pkn);
  372.     if (rs == -1) {
  373.         BTEPRINT;
  374.         return -1;
  375.     }
  376.  
  377.     errno = 0;
  378.     return 0;
  379. }
  380.  
  381. /*man---------------------------------------------------------------------------
  382. NAME
  383.      bt_ndget - btree node get
  384.  
  385. SYNOPSIS
  386.      #include "btree_.h"
  387.  
  388.      int bt_ndget(btp, node, btnp)
  389.      btree_t *btp;
  390.      bpos_t node;
  391.      btnode_t *btnp;
  392.  
  393. DESCRIPTION
  394.  
  395. SEE ALSO
  396.      bt_ndput.
  397.  
  398. DIAGNOSTICS
  399.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  400.      value of -1 is returned, and errno set to indicate the error.
  401.  
  402. ------------------------------------------------------------------------------*/
  403. int bt_ndget(btp, node, btnp)
  404. btree_t *  btp;
  405. bpos_t     node;
  406. btnode_t * btnp;
  407. {
  408.     int    rs    = 0;
  409.     void *    buf    = NULL;
  410.  
  411.     errno = 0;
  412.  
  413. #ifdef DEBUG
  414.     /* validate arguments */
  415.     if ((!bt_valid(btp)) || (btnp == NULL) || (node == 0)) {
  416.         BTEPRINT;
  417.         errno = EINVAL;
  418.         return -1;
  419.     }
  420.  
  421.     /* check if not open */
  422.     if (!(btp->flags & BTOPEN)) {
  423.         BTEPRINT;
  424.         errno = BTENOPEN;
  425.         return -1;
  426.     }
  427. #endif
  428.  
  429.     /* read node from file */
  430.     buf = calloc(1, bt_blksize(btp));
  431.     if (buf == NULL) {
  432.         BTEPRINT;
  433.         errno = ENOMEM;
  434.         return -1;
  435.     }
  436.     rs = bgetb(btp->bp, node, buf);
  437.     if (rs == -1) {
  438.         BTEPRINT;
  439.         free(buf);
  440.         return -1;
  441.     }
  442.  
  443.     /* convert node from file format */
  444.     memcpy((void *)btnp, buf, offsetof(btnode_t, key_p));
  445.     memcpy(btnp->key_p,
  446.             (void *)((char *)buf + offsetof(btnode_t, key_p)),
  447.                  ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  448.     memcpy(btnp->child_p,
  449.         (void *)((char *)buf + offsetof(btnode_t, key_p) +
  450.                  ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  451.                  ((btp->bthdr.m) * sizeof(size_t)));
  452.  
  453.     /* free buffer */
  454.     free(buf);
  455.  
  456.     errno = 0;
  457.     return 0;
  458. }
  459.  
  460. /*man---------------------------------------------------------------------------
  461. NAME
  462.      bt_ndinit - initialize node
  463.  
  464. SYNOPSIS
  465.      #include "btree_.h"
  466.  
  467.      void bt_ndinit(btp, btnp)
  468.      btree_t *btp;
  469.      btnode_t *btnp;
  470.  
  471. DESCRIPTION
  472.      The bt_ndinit function initializes node btnp.
  473.  
  474. ------------------------------------------------------------------------------*/
  475. void bt_ndinit(btp, btnp)
  476. btree_t *  btp;
  477. btnode_t * btnp;
  478. {
  479.     bttuple_t bttuple;    /* used only for sizeof */
  480.  
  481.     /* initialize storage */
  482.     memset((void *)&bttuple, 0, sizeof(bttuple));
  483.  
  484. #ifdef DEBUG
  485.     /* validate arguments */
  486.     if ((!bt_valid(btp)) || (btnp == NULL)) {
  487.         BTEPRINT;
  488.         return;
  489.     }
  490. #endif
  491.  
  492.     /* initialize btnp */
  493.     btnp->n = 0;
  494.     btnp->lsib = 0;
  495.     btnp->rsib = 0;
  496.     memset(btnp->key_p, 0, btp->bthdr.m * btp->bthdr.keysize);
  497.     memset((void *)btnp->child_p, 0, (btp->bthdr.m + 1) * sizeof(bttuple.child));
  498.  
  499.     return;
  500. }
  501.  
  502. /*man---------------------------------------------------------------------------
  503. NAME
  504.      bt_ndinskey - insete key into btree node
  505.  
  506. SYNOPSIS
  507.      #include "btree_.h"
  508.  
  509.      int bt_ndinskey(btp, btnp, kn, bttuple_p)
  510.      btree_t *btp;
  511.      btnode_t *btnp;
  512.      size_t kn;
  513.      bttuple_t *bttuple_p;
  514.  
  515. DESCRIPTION
  516.      The bt_ndinskey function inserts bttuple_p into the knth slot in
  517.      btree node btnp.
  518.  
  519.      bt_ndinskey will fail if one or more of the following is true:
  520.  
  521.      [EINVAL]       btp is not a valid btree pointer.
  522.      [EINVAL]       btnp is the NULL pointer.
  523.      [EINVAL]       kn is greater than then number of
  524.                     keys is btnp plus one.
  525.  
  526. SEE ALSO
  527.      bt_nddelkey.
  528.  
  529. DIAGNOSTICS
  530.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  531.      value of -1 is returned, and errno set to indicate the error.
  532.  
  533. ------------------------------------------------------------------------------*/
  534. int bt_ndinskey(btp, btnp, kn, bttuple_p)
  535. btree_t *   btp;
  536. btnode_t *  btnp;
  537. size_t      kn;
  538. bttuple_t * bttuple_p;
  539. {
  540.     int rs = 0;
  541.  
  542.     errno = 0;
  543.  
  544. #ifdef DEBUG
  545.     /* validate arguments */
  546.     if ((!bt_valid(btp)) || (btnp == NULL) || (bttuple_p == NULL)) {
  547.         BTEPRINT;
  548.         errno = EINVAL;
  549.         return -1;
  550.     }
  551.     if (kn > (btnp->n + 1)) {
  552.         BTEPRINT;
  553.         errno = EINVAL;
  554.         return -1;
  555.     }
  556. #endif
  557.  
  558.     /* check if room to insert */
  559.     if (btnp->n >= btp->bthdr.m) {
  560.         BTEPRINT;
  561.         errno = BTEPANIC;
  562.         return -1;
  563.     }
  564.  
  565.     /* make an empty slot */
  566.     rs = bt_kyshift(btp, btnp, kn, 1);
  567.     if (rs == -1) {
  568.         BTEPRINT;
  569.         return -1;
  570.     }
  571.  
  572.     /* write new key into empty slot */
  573.     rs = bt_kywrite(btp, btnp, kn, bttuple_p);
  574.     if (rs == -1) {
  575.         BTEPRINT;
  576.         return -1;
  577.     }
  578.  
  579.     errno = 0;
  580.     return 0;
  581. }
  582.  
  583. /*man---------------------------------------------------------------------------
  584. NAME
  585.      bt_ndmax - maximum keys per node
  586.  
  587. SYNOPSIS
  588.      #include "btree_.h"
  589.  
  590.      int bt_ndmax(btp)
  591.      btree_t *btp;
  592.  
  593. DESCRIPTION
  594.  
  595. SEE ALSO
  596.      bt_ndmin.
  597.  
  598. ------------------------------------------------------------------------------*/
  599.  
  600. /* bt_ndmax is #defined in btree_.h. */
  601.  
  602. /*man---------------------------------------------------------------------------
  603. NAME
  604.      bt_ndmin - minimum keys per node
  605.  
  606. SYNOPSIS
  607.      #include "btree_.h"
  608.  
  609.      int bt_ndmin(btp)
  610.      btree_t *btp;
  611.  
  612. DESCRIPTION
  613.  
  614. SEE ALSO
  615.      bt_ndmax.
  616.  
  617. ------------------------------------------------------------------------------*/
  618.  
  619. /* bt_ndmin is #defined in btree_.h. */
  620.  
  621. /*man---------------------------------------------------------------------------
  622. NAME
  623.      bt_ndput - put btree node to file
  624.  
  625. SYNOPSIS
  626.      #include "btree_.h"
  627.  
  628.      int bt_ndput(btp, node, btnp)
  629.      btree_t *btp;
  630.      bpos_t node;
  631.      btnode_t *btnp;
  632.  
  633. DESCRIPTION
  634.  
  635. SEE ALSO
  636.      bt_ndget.
  637.  
  638. DIAGNOSTICS
  639.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  640.      value of -1 is returned, and errno set to indicate the error.
  641.  
  642. ------------------------------------------------------------------------------*/
  643. int bt_ndput(btp, node, btnp)
  644. btree_t *  btp;
  645. bpos_t     node;
  646. btnode_t * btnp;
  647. {
  648.     int    rs    = 0;
  649.     void *    buf    = NULL;
  650.  
  651.     errno = 0;
  652.  
  653. #ifdef DEBUG
  654.     /* validate arguments */
  655.     if ((!bt_valid(btp)) || (btnp == NULL) || (node == 0)) {
  656.         BTEPRINT;
  657.         errno = EINVAL;
  658.         return -1;
  659.     }
  660.  
  661.     /* check if not open */
  662.     if (!(btp->flags & BTOPEN)) {
  663.         BTEPRINT;
  664.         errno = BTENOPEN;
  665.         return -1;
  666.     }
  667. #endif
  668.  
  669.     /* convert node to file format */
  670.     buf = calloc(1, bt_blksize(btp));
  671.     if (buf == NULL) {
  672.         BTEPRINT;
  673.         errno = ENOMEM;
  674.         return -1;
  675.     }
  676.     memcpy(buf, (void *)btnp, offsetof(btnode_t, key_p));
  677.     memcpy((void *)((char *)buf + offsetof(btnode_t, key_p)), btnp->key_p,
  678.                  ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  679.     memcpy((void *)((char *)buf + offsetof(btnode_t, key_p) +
  680.                  ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  681.             btnp->child_p,
  682.                  ((btp->bthdr.m) * sizeof(size_t)));
  683.  
  684.     /* write node to file */
  685.     rs = bputb(btp->bp, node, buf);
  686.     if (rs == -1) {
  687.         BTEPRINT;
  688.         free(buf);
  689.         return -1;
  690.     }
  691.  
  692.     /* free buffer */
  693.     free(buf);
  694.  
  695.     errno = 0;
  696.     return 0;
  697. }
  698.  
  699. /*man---------------------------------------------------------------------------
  700. NAME
  701.  
  702. SYNOPSIS
  703.      #include "btree_.h"
  704.  
  705.      int bt_ndsearch(btp, btnp, key_p, kn_p)
  706.      btree_t *btp;
  707.      btnode_t *btnp;
  708.      void *key_p;
  709.      size_t *kn_p;
  710.  
  711. DESCRIPTION
  712. Function searches node btnp for key key_p.  The location of the smallest
  713. key >= key_p is returned in kn_p.
  714. Returns:  0 - not found
  715.           1 - found
  716.          -1 - error
  717.  
  718. SEE ALSO
  719.  
  720. DIAGNOSTICS
  721.  
  722. ------------------------------------------------------------------------------*/
  723. int bt_ndsearch(btp, btnp, key_p, kn_p)
  724. btree_t *  btp;
  725. btnode_t * btnp;
  726. void *     key_p;
  727. size_t *   kn_p;
  728. {
  729.     int    rs    = 0;
  730.     int    i    = 0;
  731.     bool    found    = FALSE;
  732.  
  733.     errno = 0;
  734.  
  735. #ifdef DEBUG
  736.     /* validate arguments */
  737.     if ((!bt_valid(btp)) || (btnp == NULL) || (key_p == NULL) || (kn_p == NULL)) {
  738.         BTEPRINT;
  739.         errno = EINVAL;
  740.         return -1;
  741.     }
  742. #endif
  743.  
  744.     /* initialize return value */
  745.     *kn_p = 0;
  746.  
  747.     /* locate key */
  748.     for (i = 1; (i <= btnp->n); i++) {
  749.         rs = (*btp->cmp_p)(bt_kykey_p(btp, btnp, i), key_p, btp->bthdr.keysize);
  750.         if (rs == 0) {
  751.             found = TRUE;
  752.             break;
  753.         }
  754.         if (rs > 0) {
  755.             break;
  756.         }
  757.     }
  758.     *kn_p = i;
  759.  
  760.     errno = 0;
  761.     return (found ? 1 : 0);
  762. }
  763.  
  764. /*man---------------------------------------------------------------------------
  765. NAME
  766.      bt_ndshift - node shift
  767.  
  768. SYNOPSIS
  769.      #include "btree_.h"
  770.  
  771.      int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn)
  772.      btree_t *btp;
  773.      btnode_t *lbtnp;
  774.      btnode_t *rbtnp;
  775.      btnode_t *pbtnp;
  776.      size_t pkn;
  777.  
  778. DESCRIPTION
  779.      The bt_ndshift function shifts keys between the two sibling nodes lbtnp
  780.      and rbtnp to give them both the same number of keys (+/- 1).  The
  781.      key in slot pkn in node pbtnp is the parent of the right node rbtnp.
  782.      It is updated for the shift.
  783.  
  784.      bt_ndshift will fail if one or more of the following is true:
  785.  
  786.      [EINVAL]       btp is not a valid btree pointer.
  787.      [EINVAL]       btnp, rbtnp, or pbtnp is NULL.
  788.      [EINVAL]       pkn is 0 or greater than pbtnp->n.
  789.      [BTENOPEN]     btp is not open.
  790.  
  791. SEE ALSO
  792.      bt_ndfuse, bt_ndsplit.
  793.  
  794. DIAGNOSTICS
  795.      Upon successful completion, the number of keys shifted is returned.
  796.      Otherwise, a value of -1 is returned, and errno set to indicate the error.
  797.  
  798. ------------------------------------------------------------------------------*/
  799. int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn)
  800. btree_t *  btp;
  801. btnode_t * lbtnp;
  802. btnode_t * rbtnp;
  803. btnode_t * pbtnp;
  804. size_t     pkn;
  805. {
  806.     int        rs    = 0;
  807.     int        ns    = 0;
  808.     bool        leaf    = FALSE;
  809.     bttuple_t    bttuple;
  810.  
  811.     errno = 0;
  812.  
  813.     /* initialize storage */
  814.     memset((void *)&bttuple, 0, sizeof(bttuple));
  815.  
  816. #ifdef DEBUG
  817.     /* validate arguments */
  818.     if (!bt_valid(btp)) {
  819.         BTEPRINT;
  820.         errno = EINVAL;
  821.         return NULL;
  822.     }
  823.     if ((lbtnp == NULL) || (rbtnp == NULL)  || (pbtnp == NULL)) {
  824.         BTEPRINT;
  825.         errno = EINVAL;
  826.         return -1;
  827.     }
  828.     if ((pkn == 0) || (pkn > pbtnp->n)) {
  829.         BTEPRINT;
  830.         errno = EINVAL;
  831.         return -1;
  832.     }
  833.  
  834.     /* check if not open */
  835.     if (!(btp->flags & BTOPEN)) {
  836.         BTEPRINT;
  837.         errno = BTENOPEN;
  838.         return NULL;
  839.     }
  840. #endif
  841.  
  842.     /* check if leaf */
  843.     if (*bt_kychild_p(lbtnp, (size_t)0) == 0) {
  844.         leaf = TRUE;
  845.     }
  846.  
  847.     /* check if enough keys to shift */
  848.     if ((((lbtnp->n + rbtnp->n) / 2) < bt_ndmin(btp))) {
  849.         errno = BTEPANIC;
  850.         return -1;
  851.     }
  852.  
  853.     /* calculate number of keys to shift */
  854.     ns = ((int)lbtnp->n - (int)rbtnp->n) / 2;
  855.     if (ns == 0) {
  856.         return 0;
  857.     }
  858.  
  859.     /* bring down parent key pkn if internal node */
  860.     if (!leaf) {
  861.         bttuple.key_p = calloc(1, btp->bthdr.keysize);
  862.         if (bttuple.key_p == NULL) {
  863.             BTEPRINT;
  864.             errno = ENOMEM;
  865.             return -1;
  866.         }
  867.         rs = bt_kyread(btp, pbtnp, pkn, &bttuple);
  868.         if (rs == -1) {
  869.             BTEPRINT;
  870.             free(bttuple.key_p);
  871.             return -1;
  872.         }
  873.         bttuple.child = *bt_kychild_p(rbtnp, 0);
  874.         rs = bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttuple);
  875.         if (rs == -1) {
  876.             BTEPRINT;
  877.             free(bttuple.key_p);
  878.             return -1;
  879.         }
  880.         free(bttuple.key_p);
  881.         bttuple.key_p = NULL;
  882.     }
  883.  
  884.     /* shift keys */
  885.     if (ns > 0) {
  886.         rs = bt_kymvright(btp, lbtnp, rbtnp, (size_t)ns);
  887.         if (rs == -1) {
  888.             BTEPRINT;
  889.             return -1;
  890.         }
  891.     } else {
  892.         rs = bt_kymvleft(btp, lbtnp, rbtnp, (size_t)(-ns));
  893.         if (rs == -1) {
  894.             BTEPRINT;
  895.             return -1;
  896.         }
  897.     }
  898.  
  899.     if (!leaf) {
  900.         memcpy(bt_kykey_p(btp, pbtnp, pkn), bt_kykey_p(btp, lbtnp, lbtnp->n), btp->bthdr.keysize);
  901.         rs = bt_nddelkey(btp, lbtnp, lbtnp->n);
  902.         if (rs == -1) {
  903.             BTEPRINT;
  904.             return -1;
  905.         }
  906.     } else {
  907.         memcpy(bt_kykey_p(btp, pbtnp, pkn), bt_kykey_p(btp, rbtnp, 1), btp->bthdr.keysize);
  908.     }
  909.  
  910.     errno = 0;
  911.     return ((ns >= 0) ? ns : -ns);
  912. }
  913.  
  914. /*man---------------------------------------------------------------------------
  915. NAME
  916.      bt_ndsplit - split btree node
  917.  
  918. SYNOPSIS
  919.      #include "btree_.h"
  920.  
  921.      int bt_ndsplit(btp, node, btnp, rbtnp, bttuple_p)
  922.      btree_t *btp;
  923.      bpos_t node;
  924.      btnode_t *btnp;
  925.      btnode_t *rbtnp;
  926.      bttuple_t *bttuple_p;
  927.  
  928. DESCRIPTION
  929.      The bt_ndsplit function splits node btnp located in the indicated
  930.      node block into left and right nodes.  btnp becomes the left node
  931.      and rbtnp the right.  The key to be inserted in the parent node is
  932.      returned in bttuple_p; the address of the new node rbtnp is in
  933.      bttuple_p->child.
  934.  
  935.      bt_ndsplit will fail if one or more of the following is true:
  936.  
  937.      [EINVAL]       btp is not a valid btree pointer.
  938.      [EINVAL]       btnp, rbtnp, or bttuple_p is NULL.
  939.      [EINVAL]       btnp and rbtnp point to the same node.
  940.      [BTENOPEN]     btp is not open.
  941.  
  942. SEE ALSO
  943.      bt_ndfuse, bt_ndshift.
  944.  
  945. DIAGNOSTICS
  946.      Upon successful completion, a value of 0 is returned.  Otherwise, a
  947.      value of -1 is returned, and errno set to indicate the error.
  948.  
  949. ------------------------------------------------------------------------------*/
  950. int bt_ndsplit(btp, node, btnp, rbtnp, bttuple_p)
  951. btree_t *   btp;
  952. bpos_t      node;
  953. btnode_t *  btnp;
  954. btnode_t *  rbtnp;
  955. bttuple_t * bttuple_p;
  956. {
  957.     int    rs    = 0;
  958.     bool    leaf    = FALSE;
  959.     int    midkey    = 0;        /* middle key */
  960.     bpos_t    rnode    = 0;        /* right node block number */
  961.  
  962.     errno = 0;
  963.  
  964. #ifdef DEBUG
  965.     /* validate arguments */
  966.     if (!bt_valid(btp)) {
  967.         BTEPRINT;
  968.         errno = EINVAL;
  969.         return NULL;
  970.     }
  971.     if ((btnp == NULL) || (rbtnp == NULL) || (bttuple_p == NULL) || (btnp == rbtnp)) {
  972.         BTEPRINT;
  973.         errno = EINVAL;
  974.         return -1;
  975.     }
  976.  
  977.     /* check if not open */
  978.     if (!(btp->flags & BTOPEN)) {
  979.         BTEPRINT;
  980.         errno = BTENOPEN;
  981.         return NULL;
  982.     }
  983. #endif
  984.  
  985.     /* check if node not full */
  986.     if (btnp->n < (btp->bthdr.m - 1)) {
  987.         BTEPRINT;
  988.         errno = BTEPANIC;
  989.         return -1;
  990.     }
  991.  
  992.     /* check if leaf node */
  993.     if (*bt_kychild_p(btnp, (size_t)0) == 0) {
  994.         leaf = TRUE;
  995.     }
  996.  
  997.     /* find center node */
  998.     midkey = (btnp->n / 2) + 1;
  999.  
  1000.     /* get new node for right sibling */
  1001.     bt_ndinit(btp, rbtnp);
  1002.     rs = bflpop(btp->bp, &rnode);
  1003.     if (rs == -1) {
  1004.         BTEPRINT;
  1005.         return -1;
  1006.     }
  1007.  
  1008.     /* make nodes siblings */
  1009.     rbtnp->rsib = btnp->rsib;
  1010.     btnp->rsib = rnode;
  1011.     rbtnp->lsib = node;
  1012.  
  1013.     /* load bttuple_p */
  1014.     rs = bt_kyread(btp, btnp, midkey, bttuple_p);
  1015.     if (rs == -1) {
  1016.         BTEPRINT;
  1017.         return -1;
  1018.     }
  1019.     bttuple_p->child = rnode;
  1020.  
  1021.     /* move keys midkey through n to the right sibling */
  1022.     if (leaf) {
  1023.         rs = bt_kymvright(btp, btnp, rbtnp, btnp->n - midkey + 1);
  1024.         if (rs == -1) {
  1025.             BTEPRINT;
  1026.             return -1;
  1027.         }
  1028.     } else {
  1029.         rs = bt_kymvright(btp, btnp, rbtnp, btnp->n - midkey);
  1030.         if (rs == -1) {
  1031.             BTEPRINT;
  1032.             return -1;
  1033.         }
  1034.         rs = bt_nddelkey(btp, btnp, btnp->n);
  1035.         if (rs == -1) {
  1036.             BTEPRINT;
  1037.             return -1;
  1038.         }
  1039.     }
  1040.  
  1041.     errno = 0;
  1042.     return 0;
  1043. }
  1044.