home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Tickle-4.0.sit.hqx / Tickle-4.0 / cbtree / src / seq.c < prev    next >
Text File  |  1992-05-02  |  6KB  |  288 lines
  1.  
  2. #include <types.h>
  3. #include <errno.h>
  4. #include "db.h"
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include "btree.h"
  8.  
  9. /*
  10.  *  _BT_SEQINIT -- Initialize a sequential scan on the btree.
  11.  *
  12.  *    Sets the tree's notion of the current scan location correctly
  13.  *    given a key and a direction.
  14.  *
  15.  *    Parameters:
  16.  *        t -- tree in which to initialize scan
  17.  *        key -- key for initial scan position
  18.  *        flags -- R_NEXT, R_PREV
  19.  *
  20.  *    Returns:
  21.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data
  22.  *        in the tree to scan.
  23.  *
  24.  *    Side Effects:
  25.  *        Changes current scan position for the tree.  Almost certainly
  26.  *        changes current page, as well.  Sets BTF_SEQINIT bit in tree
  27.  *        flags, so that we know we've initialized a scan.
  28.  */
  29.  
  30. int
  31. _bt_seqinit(t, key, flags)
  32.     BTREE_P t;
  33.     DBT *key;
  34.     int flags;
  35. {
  36.     BTITEM *item;
  37.     BTHEADER *h;
  38.     CURSOR *c;
  39.     IDATUM *id;
  40.     index_t last;
  41.  
  42.     /*
  43.      *  Figure out if we really have to search for the key that the
  44.      *  user supplied.  If key is null, then this is an unkeyed scan
  45.      *  and we can just start from an endpoint.
  46.      */
  47.  
  48.     c = &(t->bt_cursor);
  49.  
  50.     if (flags == R_CURSOR) {
  51.         if (key->data != (u_char *) NULL) {
  52.  
  53.             /* key supplied, find first instance of it */
  54.             item = _bt_first(t, key);
  55.             c->c_index = item->bti_index;
  56.             c->c_pgno = t->bt_curpage->h_pgno;
  57.         } else {
  58.             errno = EINVAL;
  59.             return (RET_ERROR);
  60.         }
  61.  
  62.     } else {
  63.  
  64.         /*
  65.          *  Unkeyed scan.  For backward scans, find the last item
  66.          *  in the tree; for forward scans, find the first item.
  67.          */
  68.  
  69.         if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  70.             return (RET_ERROR);
  71.         h = t->bt_curpage;
  72.         if (flags == R_LAST || flags == R_PREV) {
  73.  
  74.             /* backward scan */
  75.             while (!(h->h_flags & F_LEAF)) {
  76.                 last = NEXTINDEX(h) - 1;
  77.                 id = (IDATUM *) GETDATUM(h,last);
  78.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  79.                     return (RET_ERROR);
  80.                 h = t->bt_curpage;
  81.             }
  82.  
  83.             /* skip empty pages */
  84.             while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE) {
  85.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  86.                     return (RET_ERROR);
  87.                 h = t->bt_curpage;
  88.             }
  89.  
  90.             c->c_pgno = h->h_pgno;
  91.             if (NEXTINDEX(h) > 0)
  92.                 c->c_index = NEXTINDEX(h) - 1;
  93.             else
  94.                 c->c_index = 0;
  95.         } else if (flags == R_FIRST || flags == R_NEXT) {
  96.             /* forward scan */
  97.             while (!(h->h_flags & F_LEAF)) {
  98.                 id = (IDATUM *) GETDATUM(h,0);
  99.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  100.                     return (RET_ERROR);
  101.                 h = t->bt_curpage;
  102.             }
  103.  
  104.             /* skip empty pages */
  105.             while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE) {
  106.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  107.                     return (RET_ERROR);
  108.                 h = t->bt_curpage;
  109.             }
  110.  
  111.             c->c_pgno = h->h_pgno;
  112.             c->c_index = 0;
  113.         } else {
  114.             /* no flags passed in */
  115.             errno = EINVAL;
  116.             return (RET_ERROR);
  117.         }
  118.     }
  119.  
  120.     /* okay, scan is initialized */
  121.     t->bt_flags |= BTF_SEQINIT;
  122.  
  123.     /* don't need the descent stack anymore */
  124.     while (_bt_pop(t) != P_NONE)
  125.         continue;
  126.  
  127.     if (c->c_index == NEXTINDEX(t->bt_curpage))
  128.         return (RET_SPECIAL);
  129.  
  130.     return (RET_SUCCESS);
  131. }
  132.  
  133. /*
  134.  *  _BT_SEQADVANCE -- Advance the sequential scan on this tree.
  135.  *
  136.  *    Moves the current location pointer for the scan on this tree one
  137.  *    spot in the requested direction.
  138.  *
  139.  *    Parameters:
  140.  *        t -- btree being scanned
  141.  *        flags -- for R_NEXT, R_PREV
  142.  *
  143.  *    Returns:
  144.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no
  145.  *        more data in the specified direction.
  146.  *
  147.  *    Side Effects:
  148.  *        May change current page.
  149.  */
  150.  
  151. int
  152. _bt_seqadvance(t, flags)
  153.     BTREE_P t;
  154.     int flags;
  155. {
  156.     BTHEADER *h;
  157.     CURSOR *c;
  158.     index_t index;
  159.  
  160.     c = &(t->bt_cursor);
  161.     index = c->c_index;
  162.  
  163.     if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  164.         return (RET_ERROR);
  165.     h = t->bt_curpage;
  166.  
  167.     /* by the time we get here, don't need the cursor key anymore */
  168.     if (c->c_key != (char *) NULL)
  169.         {
  170.         FREE(c->c_key);
  171.         c->c_key = NULL; /* TGE */
  172.         }
  173.  
  174.     if (flags == R_NEXT) {
  175.  
  176.         /*
  177.          *  This is a forward scan.  If the cursor is pointing
  178.          *  at a virtual record (that is, it was pointing at
  179.          *  a record that got deleted), then we should return
  180.          *  the record it's pointing at now.  Otherwise, we
  181.          *  should advance the scan.  In either case, we need
  182.          *  to be careful not to run off the end of the current
  183.          *  page.
  184.          */
  185.  
  186.         if (c->c_flags & CRSR_BEFORE) {
  187.             if (index >= NEXTINDEX(h)) {
  188.                 /* out of items on this page, get next page */
  189.                 if (h->h_nextpg == P_NONE) {
  190.                     /* tell caller we're done... */
  191.                     c->c_index = NEXTINDEX(h);
  192.                     return (RET_SPECIAL);
  193.                 }
  194.  
  195.                 /* skip empty pages */
  196.                 do {
  197.                     if (_bt_getpage(t, h->h_nextpg)
  198.                         == RET_ERROR) {
  199.                         c->c_index = NEXTINDEX(h);
  200.                         return (RET_ERROR);
  201.                     }
  202.                     h = t->bt_curpage;
  203.                     c->c_pgno = h->h_pgno;
  204.                 } while (NEXTINDEX(h) == 0
  205.                      && h->h_nextpg != P_NONE);
  206.  
  207.                 if (NEXTINDEX(h) == 0) {
  208.                     /* tell caller we're done */
  209.                     c->c_index = NEXTINDEX(h);
  210.                     return (RET_SPECIAL);
  211.                 }
  212.                 index = 0;
  213.             }
  214.             c->c_flags &= ~CRSR_BEFORE;
  215.  
  216.         } else {
  217.             if (++index >= NEXTINDEX(h))
  218.                 {
  219.                 /* out of items on this page, get next page */
  220.                 if (h->h_nextpg == P_NONE)
  221.                     {
  222.                     /* tell caller we're done... */
  223.                     c->c_index = NEXTINDEX(h);
  224.                     return (RET_SPECIAL);
  225.                     }
  226.     
  227.                 /* skip empty pages */
  228.                 do {
  229.                     if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  230.                         {
  231.                         c->c_index = NEXTINDEX(h);
  232.                         return (RET_ERROR);
  233.                         }
  234.                     h = t->bt_curpage;
  235.                     c->c_pgno = h->h_pgno;
  236.                     } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
  237.     
  238.                 if (NEXTINDEX(h) == 0)
  239.                     {
  240.                     /* tell caller we're done */
  241.                     c->c_index = NEXTINDEX(h);
  242.                     return (RET_SPECIAL);
  243.                     }
  244.                 index = 0;
  245.             }
  246.         }
  247.     } else if (flags == R_PREV) {
  248.  
  249.         /* for backward scans, life is substantially easier */
  250.         c->c_flags &= ~CRSR_BEFORE;
  251.         if (c->c_key != (char *) NULL) {
  252.             FREE(c->c_key);
  253.             c->c_key = (char *) NULL;
  254.         }
  255.  
  256.         if (index == 0) {
  257.  
  258.             /* we may be done */
  259.             c->c_index = 0;
  260.  
  261.             /* out of items on this page, get next page */
  262.             if (h->h_prevpg == P_NONE)
  263.                 return (RET_SPECIAL);
  264.  
  265.             /* skip empty pages */
  266.             do {
  267.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  268.                     return (RET_ERROR);
  269.                 h = t->bt_curpage;
  270.                 c->c_pgno = h->h_pgno;
  271.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  272.  
  273.             if (NEXTINDEX(h) == 0)
  274.                 return (RET_SPECIAL);
  275.  
  276.             index = NEXTINDEX(h) - 1;
  277.         } else
  278.             --index;
  279.     } else {
  280.         /* must specify a direction */
  281.         errno = EINVAL;
  282.         return (RET_ERROR);
  283.     }
  284.  
  285.     c->c_index = index;
  286.     return (RET_SUCCESS);
  287. }
  288.