home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / KYOPS.C < prev    next >
Text File  |  1989-08-31  |  14KB  |  493 lines

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