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 / search.c < prev    next >
Text File  |  1992-05-03  |  6KB  |  264 lines
  1.  
  2. #include <types.h>
  3. #include <stdio.h>
  4. #include "db.h"
  5. #include "btree.h"
  6.  
  7. /*
  8.  *  _BT_FIRST -- Find the first item in the tree that matches the supplied
  9.  *         key.
  10.  *
  11.  *    This routine supports deletion.  When the user supplies a key to
  12.  *    be deleted, we find the first one, and iteratively delete all the
  13.  *    matching ones that follow it.
  14.  *
  15.  *    Parameters:
  16.  *        t -- btree in which to find first occurrence
  17.  *        key -- key to find
  18.  *
  19.  *    Returns:
  20.  *        The BTITEM for the matching item.  If there's no match,
  21.  *        this may point to the first item > than the supplied key,
  22.  *        or off the end of the page.
  23.  *
  24.  *    Warnings:
  25.  *        The BTITEM returned is in static space and will be overwritten
  26.  *        by the next search of any kind in any btree.
  27.  */
  28.  
  29. BTITEM *
  30. _bt_first(t, key)
  31.     BTREE_P t;
  32.     DBT *key;
  33. {
  34.     BTHEADER *h;
  35.     BTITEM *item;
  36.     index_t next;
  37.     int r;
  38.  
  39.     /* find any matching item */
  40.     item = _bt_search(t, key);
  41.     h = t->bt_curpage;
  42.     next = NEXTINDEX(h);
  43.  
  44.     /* if we're off the end of the page, search failed and we're done */
  45.     if (item->bti_index >= next)
  46.         return (item);
  47.  
  48.     /* as long as we have an exact match, walk backwards */
  49.     while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) {
  50.  
  51.         /* at start of page? */
  52.         if (item->bti_index == 0) {
  53.  
  54.             /* if no prev page, we're done */
  55.             if (h->h_prevpg == P_NONE)
  56.                 return (item);
  57.  
  58.             /* walk backward, skipping empty pages */
  59.             do {
  60.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  61.                     return ((BTITEM *) NULL);
  62.                 h = t->bt_curpage;
  63.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  64.  
  65.             if (NEXTINDEX(h) != 0)
  66.                 item->bti_index = NEXTINDEX(h) - 1;
  67.             else
  68.                 item->bti_index = 0;
  69.  
  70.             item->bti_pgno = h->h_pgno;
  71.         } else {
  72.             item->bti_index--;
  73.         }
  74.     }
  75.  
  76.     /* if we went too far backwards, step forward one entry */
  77.     if (r > 0) {
  78.         if (++(item->bti_index) >= NEXTINDEX(h)
  79.             && h->h_nextpg != P_NONE) {
  80.  
  81.             /* walk forward, skipping empty pages */
  82.             do {
  83.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  84.                     return ((BTITEM *) NULL);
  85.                 h = t->bt_curpage;
  86.             } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0);
  87.  
  88.             item->bti_index = 0;
  89.             item->bti_pgno = h->h_pgno;
  90.         }
  91.     }
  92.  
  93.     /* got it */
  94.     return (item);
  95. }
  96.  
  97. /*
  98.  *  _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree.
  99.  *
  100.  *    Parameters:
  101.  *        t -- btree in which to search
  102.  *        key -- key to find
  103.  *
  104.  *    Returns:
  105.  *        BTITEM for matching item, if any, or the BTITEM for the
  106.  *        location of the key, if it were in the tree.
  107.  *
  108.  *    Warnings:
  109.  *        The BTITEM returned is in static memory, and will be
  110.  *        overwritten by the next search of any kind in any tree.
  111.  */
  112.  
  113. BTITEM *
  114. _bt_search(t, key)
  115.     BTREE_P t;
  116.     DBT *key;
  117. {
  118.     /* we want to start all of our searches at the root */
  119.     if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  120.         {
  121.         return ((BTITEM *) NULL);
  122.         }
  123.  
  124.     return (_bt_searchr(t, key));
  125. }
  126.  
  127. BTITEM *
  128. _bt_searchr(t, key)
  129.     BTREE_P t;
  130.     DBT *key;
  131. {
  132.     BTHEADER *h = t->bt_curpage;
  133.     index_t index;
  134.     IDATUM *id;
  135.     DATUM *d;
  136.     static BTITEM item;
  137.  
  138.     /* do a binary search on the current page */
  139.     index = _bt_binsrch(t, key->data);
  140.  
  141.     /*
  142.      *  At this point, the binary search terminated because the endpoints
  143.      *  got too close together, or we have a match.  Figure out which
  144.      *  case applies and decide what to do based on the page type.
  145.      */
  146.     if (h->h_flags & F_LEAF) {        
  147.         item.bti_pgno = h->h_pgno;
  148.         item.bti_index = index;
  149.         if (index < NEXTINDEX(h))
  150.             d = (DATUM *) GETDATUM(h,index);
  151.         else
  152.             d = (DATUM *) NULL;
  153.  
  154.         item.bti_datum = d;
  155.         return(&item);
  156.     } else {
  157.         id = (IDATUM *) GETDATUM(h, index);
  158.         if (_bt_push(t, h->h_pgno) == RET_ERROR)
  159.             return ((BTITEM *) NULL);
  160.         if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  161.             return ((BTITEM *) NULL);
  162.         return (_bt_searchr(t, key));
  163.     }
  164. }
  165.  
  166. /*
  167.  *  _BT_BINSRCH -- Do a binary search for a given key on the current page.
  168.  *
  169.  *    Searches on internal pages are handled slightly differently from
  170.  *    searches on leaf pages.  This is because internal page searches
  171.  *    find the largest item <= key in the tree, and leaf searches find
  172.  *    the smallest item >= key.  This guarantees that leaf page searches
  173.  *    leave us pointing at the item's correct position, and internal
  174.  *    searches descend the tree correctly.
  175.  *
  176.  *    Parameters:
  177.  *        t -- tree to search
  178.  *        key -- key we're looking for
  179.  *
  180.  *    Returns:
  181.  *        Index of the line pointer array entry for the (closest)
  182.  *        match to key on the current page, with "closest" as defined
  183.  *        above.
  184.  */
  185.  
  186. index_t
  187. _bt_binsrch(t, key)
  188.     BTREE_P t;
  189.     char *key;
  190. {
  191.     index_t lbound, ubound, cur;
  192.     BTHEADER *h = t->bt_curpage;
  193.     int match = 0;
  194.     int r;
  195.     DATUM *d;
  196.  
  197.     lbound = 0;
  198.     ubound = NEXTINDEX(h);
  199.     
  200.     if (ubound > 0)
  201.         --ubound;
  202.  
  203.     /* do a binary search on the current page */
  204.     while ((ubound - lbound) > 1) {
  205.         cur = lbound + ((ubound - lbound) / 2);
  206.         d = (DATUM *) GETDATUM(h, cur);
  207.         r = _bt_cmp(t, key, cur);
  208.  
  209.         if (r > 0)
  210.             lbound = cur + 1;
  211.         else if (r < 0)
  212.             ubound = cur;
  213.         else {
  214.             match++;
  215.             break;
  216.         }
  217.     }
  218.  
  219.     /*
  220.      *  At this point, the binary search terminated because the endpoints
  221.      *  got too close together, or we have a match.  Figure out which
  222.      *  case applies, decide what to do based on the page type (leaf or
  223.      *  internal), and do the right thing.
  224.      */
  225.     if (match) {
  226.         return (cur);
  227.     } else if (ubound != lbound) {
  228.         if (h->h_flags & F_LEAF) {
  229.             r = _bt_cmp(t, key, lbound);
  230.             if (r <= 0) {
  231.                 return (lbound);
  232.             }
  233.         } else {
  234.             r = _bt_cmp(t, key, ubound);
  235.  
  236.             /* for internal nodes, move as far left as possible */
  237.             if (r < 0) {
  238.                 r = _bt_cmp(t, key, lbound);
  239.                 if (r < 0 && lbound > 0)
  240.                     --lbound;
  241.                 return (lbound);
  242.             } else {
  243.                 return (ubound);
  244.             }
  245.         }
  246.     }
  247.  
  248.     if (h->h_flags & F_LEAF) {
  249.         if (ubound < NEXTINDEX(h)) {
  250.             r = _bt_cmp(t, key, ubound);
  251.             if (r > 0)
  252.                 ubound++;
  253.         }
  254.     } else {
  255.         /* for internal pages, move as far left as possible */
  256.         if (ubound == NEXTINDEX(h))
  257.             ubound--;
  258.  
  259.         while (_bt_cmp(t, key, ubound) < 0)
  260.             ubound--;
  261.     }
  262.     return (ubound);
  263. }
  264.