home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / cbase103 / btree / kyops.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-23  |  14.4 KB  |  542 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)kyops.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_STRING
  14. #include <string.h>
  15. #endif
  16.  
  17. /* library headers */
  18. #include <blkio.h>
  19.  
  20. /* local headers */
  21. #include "btree_.h"
  22.  
  23. /*man---------------------------------------------------------------------------
  24. NAME
  25.      bt_kychildp - btree node child
  26.  
  27. SYNOPSIS
  28.      #include "btree_.h"
  29.  
  30.      bpos_t *bt_kychildp(btnp, kn)
  31.      btnode_t *btnp;
  32.      int kn;
  33.  
  34. DESCRIPTION
  35.      bt_kychildp returns a pointer to the knth child in node btnp.
  36.      If btnp is not a valid btree node or if kn < 0 or
  37.      kn > btnp->n + 1 the results are undefined.  bt_kychildp is a macro.
  38.  
  39. SEE ALSO
  40.      bt_kykeyp.
  41.  
  42. ------------------------------------------------------------------------------*/
  43. /* bt_kychildp is defined in btree_.h. */
  44.  
  45. /*man---------------------------------------------------------------------------
  46. NAME
  47.      bt_kykeyp - btree node key
  48.  
  49. SYNOPSIS
  50.      #include "btree_.h"
  51.  
  52.      void *bt_kykeyp(btnp, kn)
  53.      btnode_t *btnp;
  54.      int kn;
  55.  
  56. DESCRIPTION
  57.      bt_kykeyp returns a pointer to the knth key in node btnp.  If
  58.      btnp is not a valid btree node or if kn < 1 or kn > btnp->n + 1
  59.      the results are undefined.  bt_kychildp is a macro.
  60.  
  61. SEE ALSO
  62.      bt_kychildp.
  63.  
  64. ------------------------------------------------------------------------------*/
  65. /* bt_kykeyp is defined in btree_.h. */
  66.  
  67. /*man---------------------------------------------------------------------------
  68. NAME
  69.      bt_kykfp - btree node key field
  70.  
  71. SYNOPSIS
  72.      #include "btree_.h"
  73.  
  74.      void *bt_kykfp(btp, btnp, kn, fn)
  75.      btree_t *btp;
  76.      btnode_t *btnp;
  77.      int kn;
  78.      int fn;
  79.  
  80. DESCRIPTION
  81.      bt_kykfp returns a pointer to the fnth field of the knth key in
  82.      node btnp.  If btnp is not a valid btree node or if kn < 1 or
  83.      kn > btnp->n + 1 the results are undefined.  bt_kychildp is a
  84.      macro.
  85.  
  86. SEE ALSO
  87.      bt_kychildp.
  88.  
  89. ------------------------------------------------------------------------------*/
  90. /* bt_kykfp is defined in btree_.h. */
  91.  
  92. /*man---------------------------------------------------------------------------
  93. NAME
  94.      bt_kymvleft - move keys left
  95.  
  96. SYNOPSIS
  97.      #include "btree_.h"
  98.  
  99.      int bt_kymvleft(btp, lbtnp, rbtnp, nm)
  100.      btree_t *btp;
  101.      btnode_t *lbtnp;
  102.      btnode_t *rbtnp;
  103.      int nm;
  104.  
  105. DESCRIPTION
  106.      Function moves the leftmost nm tuples and child 0 (keys 1..nm and
  107.      children 0..nm) from node rbtnp to lbtnp.  They are appended
  108.      after the last key in lbtnp, its rightmost child being
  109.      overwritten.  The key count in each node is corrected for the
  110.      shift.  No other changes are made.
  111.  
  112.      bt_kymvleft will fail if one or more of the following is true: 
  113.  
  114.      [EINVAL]       btp is not a valid btree pointer.
  115.      [EINVAL]       lbtnp or rbtnp is NULL. 
  116.      [EINVAL]       lbtnp and rbtnp point to the same node.
  117.      [EINVAL]       rbtnp has less than nm keys.
  118.      [EINVAL]       lbtnp does not have room for nm keys.
  119.  
  120. SEE ALSO
  121.      bt_kymvright, bt_kyshift.
  122.  
  123. DIAGNOSTICS
  124.      Upon successful completion, a value of 0 is returned.  Otherwise,
  125.      a value of -1 is returned, and errno set to indicate the error.
  126.  
  127. ------------------------------------------------------------------------------*/
  128. #ifdef AC_PROTO
  129. int bt_kymvleft(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, int nm)
  130. #else
  131. int bt_kymvleft(btp, lbtnp, rbtnp, nm)
  132. btree_t *btp;
  133. btnode_t *lbtnp;
  134. btnode_t *rbtnp;
  135. int nm;
  136. #endif
  137. {
  138.     int    ks = 0;        /* first key to copy */
  139.     int    ke = 0;        /* last key to copy */
  140.     int    kt = 0;        /* target key */
  141.     void *    ps = NULL;    /* pointer to copy source */
  142.     void *    pe = NULL;    /* pointer to copy source end */
  143.     void *    pt = NULL;    /* pointer to copy target */
  144. #ifdef DEBUG
  145.     /* validate arguments */
  146.     if (!bt_valid(btp) || lbtnp == NULL || rbtnp == NULL || lbtnp == rbtnp) {
  147.         BTEPRINT;
  148.         errno = EINVAL;
  149.         return -1;
  150.     }
  151.     if (nm > rbtnp->n || nm + lbtnp->n > bt_ndmax(btp) + 1) {
  152.         BTEPRINT;
  153.         errno = EINVAL;
  154.         return -1;
  155.     }
  156. #endif
  157.     /* move bttpls */
  158.     ks = 1;
  159.     ke = nm;
  160.     kt = lbtnp->n + 1;
  161.     ps = bt_kykeyp(btp, rbtnp, ks);
  162.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  163.     pt = bt_kykeyp(btp, lbtnp, kt);
  164.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  165.     ps = bt_kychildp(rbtnp, ks - 1);
  166.     pe = bt_kychildp(rbtnp, ke + 1);
  167.     pt = bt_kychildp(lbtnp, kt - 1);
  168.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  169.  
  170.     /* adjust key count of left node */
  171.     lbtnp->n += nm;
  172.  
  173.     /* delete keys from rbtnp */
  174.     ks = nm + 1;
  175.     ke = rbtnp->n;
  176.     kt = 1;
  177.     ps = bt_kykeyp(btp, rbtnp, ks);
  178.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  179.     pt = bt_kykeyp(btp, rbtnp, kt);
  180.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  181.     ps = bt_kychildp(rbtnp, ks - 1);
  182.     pe = bt_kychildp(rbtnp, ke + 1);
  183.     pt = bt_kychildp(rbtnp, kt - 1);
  184.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  185.  
  186.     /* adjust key count of right node */
  187.     rbtnp->n -= nm;
  188.     if (rbtnp->n < btp->bthdr.m) {
  189.         ps = bt_kykeyp(btp, rbtnp, rbtnp->n + 1);
  190.         pe = bt_kykeyp(btp, rbtnp, btp->bthdr.m + 1);
  191.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  192.         ps = bt_kychildp(rbtnp, rbtnp->n + 1);
  193.         pe = bt_kychildp(rbtnp, btp->bthdr.m + 1);
  194.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  195.     }
  196.  
  197.     return 0;
  198. }
  199.  
  200. /*man---------------------------------------------------------------------------
  201. NAME
  202.      bt_kymvright - move keys right
  203.  
  204. SYNOPSIS
  205.      #include "btree_.h"
  206.  
  207.      int bt_kymvright(btp, lbtnp, rbtnp, nm)
  208.      btree_t *btp;
  209.      btnode_t *lbtnp;
  210.      btnode_t *rbtnp;
  211.      int nm;
  212.  
  213. DESCRIPTION
  214.      Function moves the rightmost nm bttpls and the child preceding
  215.      them (keys (n + 1 - nm)..n and children (n - nm)..n) from node
  216.      lbtnp to rbtnp.  They are inserted before the first key in rbtnp,
  217.      its leftmost child being overwritten.  The key count in each node
  218.      is corrected for the shift.  No other changes are made.
  219.  
  220.      bt_kymvright will fail if one or more of the following is true: 
  221.  
  222.      [EINVAL]       btp is not a valid btree pointer.
  223.      [EINVAL]       lbtnp or rbtnp is NULL. 
  224.      [EINVAL]       lbtnp and rbtnp are same node.
  225.      [EINVAL]       rbtnp does not have nm keys.
  226.      [EINVAL]       lbtnp does not have room for nm keys.
  227.  
  228. SEE ALSO
  229.      bt_kymvleft, bt_kyshift.
  230.  
  231. DIAGNOSTICS
  232.      Upon successful completion, a value of 0 is returned.  Otherwise,
  233.      a value of -1 is returned, and errno set to indicate the error.
  234.  
  235. ------------------------------------------------------------------------------*/
  236. #ifdef AC_PROTO
  237. int bt_kymvright(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, int nm)
  238. #else
  239. int bt_kymvright(btp, lbtnp, rbtnp, nm)
  240. btree_t *btp;
  241. btnode_t *lbtnp;
  242. btnode_t *rbtnp;
  243. int nm;
  244. #endif
  245. {
  246.     int    ks = 0;        /* first key to copy */
  247.     int    ke = 0;        /* last key to copy */
  248.     int    kt = 0;        /* target key */
  249.     void *    ps = NULL;    /* pointer to copy source */
  250.     void *    pe = NULL;    /* pointer to copy source end */
  251.     void *    pt = NULL;    /* pointer to copy target */
  252. #ifdef DEBUG
  253.     /* validate arguments */
  254.     if (!bt_valid(btp) || lbtnp == NULL || rbtnp == NULL || lbtnp == rbtnp) {
  255.         BTEPRINT;
  256.         errno = EINVAL;
  257.         return -1;
  258.     }
  259.     if (nm > lbtnp->n || nm + rbtnp->n > bt_ndmax(btp) + 1) {
  260.         BTEPRINT;
  261.         errno = EINVAL;
  262.         return -1;
  263.     }
  264. #endif
  265.     /* make room in right node */
  266.     ks = 1;
  267.     ke = rbtnp->n;
  268.     kt = nm + 1;
  269.     ps = bt_kykeyp(btp, rbtnp, ks);
  270.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  271.     pt = bt_kykeyp(btp, rbtnp, kt);
  272.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  273.     ps = bt_kychildp(rbtnp, ks - 1);
  274.     pe = bt_kychildp(rbtnp, ke + 1);
  275.     pt = bt_kychildp(rbtnp, kt - 1);
  276.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  277.  
  278.     /* adjust key count of right node */
  279.     rbtnp->n += nm;
  280.  
  281.     /* move bttpls */
  282.     ks = lbtnp->n - nm + 1;
  283.     ke = lbtnp->n;
  284.     kt = 1;
  285.     ps = bt_kykeyp(btp, lbtnp, ks);
  286.     pe = bt_kykeyp(btp, lbtnp, ke + 1);
  287.     pt = bt_kykeyp(btp, rbtnp, kt);
  288.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  289.     memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  290.     ps = bt_kychildp(lbtnp, ks - 1);
  291.     pe = bt_kychildp(lbtnp, ke + 1);
  292.     pt = bt_kychildp(rbtnp, kt - 1);
  293.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  294.     ps = bt_kychildp(lbtnp, ks);
  295.     memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  296.  
  297.     /* adjust key count of left node */
  298.     lbtnp->n -= nm;
  299.  
  300.     return 0;
  301. }
  302.  
  303. /*man---------------------------------------------------------------------------
  304. NAME
  305.      bt_kyread - read key
  306.  
  307. SYNOPSIS
  308.      #include "btree_.h"
  309.  
  310.      int bt_kyread(btp, btnp, kn, bttplp)
  311.      btree_t *btp;
  312.      btnode_t *btnp;
  313.      int kn;
  314.      bttpl_t *bttplp;
  315.  
  316. DESCRIPTION
  317.      Function reads the (key, child) bttpl in slot kn of node btnp.
  318.      The results are returned in bttplp.  If kn is zero, then the key
  319.      field of bttplp is cleared and child 0 is written in the child
  320.      field.
  321.  
  322.      bt_kyread will fail if one or more of the following is true:
  323.  
  324.      [EINVAL]       btp, btnp, or bttplp is NULL. 
  325.      [EINVAL]       btnp contains fewer than kn keys.
  326.      [EINVAL]       kn < 0 or kn > btnp->n.
  327.  
  328. SEE ALSO
  329.      bt_kywrite.
  330.  
  331. DIAGNOSTICS
  332.      Upon successful completion, a value of 0 is returned.  Otherwise,
  333.      a value of -1 is returned, and errno set to indicate the error.
  334.  
  335. ------------------------------------------------------------------------------*/
  336. #ifdef AC_PROTO
  337. int bt_kyread(btree_t *btp, const btnode_t *btnp, int kn, bttpl_t *bttplp)
  338. #else
  339. int bt_kyread(btp, btnp, kn, bttplp)
  340. btree_t *btp;
  341. const btnode_t *btnp;
  342. int kn;
  343. bttpl_t *bttplp;
  344. #endif
  345. {
  346. #ifdef DEBUG
  347.     /* validate arguments */
  348.     if (!bt_valid(btp) || btnp == NULL || bttplp == NULL) {
  349.         BTEPRINT;
  350.         errno = EINVAL;
  351.         return -1;
  352.     }
  353.     if (kn < 0 || kn > btnp->n) {
  354.         BTEPRINT;
  355.         errno = EINVAL;
  356.         return -1;
  357.     }
  358. #endif
  359.     if (kn == 0) {
  360.         memset(bttplp->keyp, 0, sizeof(bttplp->keyp));
  361.     } else {
  362.         memcpy(bttplp->keyp, bt_kykeyp(btp, btnp, kn), btp->bthdr.keysize);
  363.     }
  364.     bttplp->child = *bt_kychildp(btnp, kn);
  365.  
  366.     return 0;
  367. }
  368.  
  369. /*man---------------------------------------------------------------------------
  370. NAME
  371.      bt_kyshift - shift keys
  372.  
  373. SYNOPSIS
  374.      #include "btree_.h"
  375.  
  376.      int bt_kyshift(btp, btnp, kn, ns)
  377.      btree_t *btp;
  378.      btnode_t *btnp;
  379.      int kn;
  380.      int ns;
  381.  
  382. DESCRIPTION
  383.      Function shifts bttpls kn and above in node btnp by ns slots.  If
  384.      ns > 0, the keys are shifted up.  If ns < 0, they are shifted
  385.      down.  The key count in is corrected for the shift.  No other
  386.      changes are made.
  387.  
  388.      bt_kymvleft will fail if one or more of the following is true: 
  389.  
  390.      [EINVAL]       btp is not a valid btree pointer.
  391.      [EINVAL]       btnp is NULL. 
  392.      [EINVAL]       kn < 1 or kn > btnp->n + 1.
  393.  
  394. SEE ALSO
  395.      bt_kymvleft, bt_kymvright.
  396.  
  397. DIAGNOSTICS
  398.      Upon successful completion, a value of 0 is returned.  Otherwise,
  399.      a value of -1 is returned, and errno set to indicate the error.
  400.  
  401. ------------------------------------------------------------------------------*/
  402. #ifdef AC_PROTO
  403. int bt_kyshift(btree_t *btp, btnode_t *btnp, int kn, int ns)
  404. #else
  405. int bt_kyshift(btp, btnp, kn, ns)
  406. btree_t *btp;
  407. btnode_t *btnp;
  408. int kn;
  409. int ns;
  410. #endif
  411. {
  412.     int    ks = 0;        /* first key to copy */
  413.     int    ke = 0;        /* last key to copy */
  414.     int    kt = 0;        /* target key */
  415.     void *    ps = NULL;    /* pointer to copy source */
  416.     void *    pe = NULL;    /* pointer to copy source end */
  417.     void *    pt = NULL;    /* pointer to copy target */
  418. #ifdef DEBUG
  419.     /* validate arguments */
  420.     if (!bt_valid(btp) || btnp == NULL) {
  421.         BTEPRINT;
  422.         errno = EINVAL;
  423.         return -1;
  424.     }
  425.     if (kn < 1 || kn > btnp->n + 1) {
  426.         BTEPRINT;
  427.         errno = EINVAL;
  428.         return -1;
  429.     }
  430. #endif
  431.     if (((int)btnp->n + ns) > (int)btp->bthdr.m) {/* keys shifted out top */
  432.         BTEPRINT;
  433.         errno = BTEPANIC;
  434.         return -1;
  435.     }
  436.     if (-ns >= (int)kn) {            /* keys shifted out bottom */
  437.         BTEPRINT;
  438.         errno = BTEPANIC;
  439.         return -1;
  440.     }
  441.  
  442.     /* shift keys */
  443.     ks = kn;
  444.     ke = btnp->n;
  445.     kt = kn + ns;
  446.     ps = bt_kykeyp(btp, btnp, ks);
  447.     pe = bt_kykeyp(btp, btnp, ke + 1);
  448.     pt = bt_kykeyp(btp, btnp, kt);
  449.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  450.     ps = bt_kychildp(btnp, ks);
  451.     pe = bt_kychildp(btnp, ke + 1);
  452.     pt = bt_kychildp(btnp, kt);
  453.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  454.  
  455.     /* adjust number of keys */
  456.     btnp->n = (int)btnp->n + ns;
  457.  
  458.     /* clear memory above last key */
  459.     if (ns < 0) {
  460.         ps = bt_kykeyp(btp, btnp, btnp->n + 1);
  461.         pe = bt_kykeyp(btp, btnp, btp->bthdr.m + 1);
  462.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  463.         ps = bt_kychildp(btnp, btnp->n + 1);
  464.         pe = bt_kychildp(btnp, btp->bthdr.m + 1);
  465.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  466.     }
  467.  
  468.     return 0;
  469. }
  470.  
  471. /*man---------------------------------------------------------------------------
  472. NAME
  473.      bt_kywrite - write key
  474.  
  475. SYNOPSIS
  476.      #include "btree_.h"
  477.  
  478.      int bt_kywrite(btp, btnp, kn, bttplp)
  479.      btree_t *btp;
  480.      btnode_t *btnp;
  481.      int kn;
  482.      const bttpl_t *bttplp;
  483.  
  484. DESCRIPTION
  485.      Function writes the (key, child) bttpl contained in bttplp in
  486.      slot kn of node btnp.  If kn is zero, then the contents of the
  487.      key field of bttplp are ignored and the contents of the child
  488.      field are written to child 0 of btnp.  If bttplp is NULL, the
  489.      slot is cleared.
  490.  
  491.      bt_kywrite will fail if one or more of the following is true:
  492.  
  493.      [EINVAL]       btp is not a valid btree pointer.
  494.      [EIVNAL]       btnp is NULL. 
  495.      [EINVAL]       btnp contains fewer than kn keys.
  496.  
  497. SEE ALSO
  498.      bt_kywrite.
  499.  
  500. DIAGNOSTICS
  501.      Upon successful completion, a value of 0 is returned.  Otherwise,
  502.      a value of -1 is returned, and errno set to indicate the error.
  503.  
  504. ------------------------------------------------------------------------------*/
  505. #ifdef AC_PROTO
  506. int bt_kywrite(btree_t *btp, btnode_t *btnp, int kn, const bttpl_t *bttplp)
  507. #else
  508. int bt_kywrite(btp, btnp, kn, bttplp)
  509. btree_t *btp;
  510. btnode_t *btnp;
  511. int kn;
  512. const bttpl_t *bttplp;
  513. #endif
  514. {
  515. #ifdef DEBUG
  516.     /* validate arguments */
  517.     if (!bt_valid(btp) || btnp == NULL) {
  518.         BTEPRINT;
  519.         errno = EINVAL;
  520.         return -1;
  521.     }
  522.     if (kn < 0 || kn > btnp->n) {
  523.         BTEPRINT;
  524.         errno = EINVAL;
  525.         return -1;
  526.     }
  527. #endif
  528.     if (bttplp == NULL) {
  529.         if (kn != 0) {
  530.             memset(bt_kykeyp(btp, btnp, kn), 0, btp->bthdr.keysize);
  531.         }
  532.         *bt_kychildp(btnp, kn) = NIL;
  533.     } else {
  534.         if (kn != 0) {
  535.             memcpy(bt_kykeyp(btp, btnp, kn), bttplp->keyp, btp->bthdr.keysize);
  536.         }
  537.         *bt_kychildp(btnp, kn) = bttplp->child;
  538.     }
  539.  
  540.     return 0;
  541. }
  542.