home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / db / btree / bt_seq.c < prev    next >
C/C++ Source or Header  |  1996-12-11  |  10KB  |  387 lines
  1. /*    $NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Mike Olson.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)bt_seq.c    8.2 (Berkeley) 9/7/93";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/types.h>
  48.  
  49. #include <errno.h>
  50. #include <stddef.h>
  51. #include <stdio.h>
  52. #include <stdlib.h>
  53.  
  54. #include <db.h>
  55. #include "btree.h"
  56.  
  57. static int     bt_seqadv __P((BTREE *, EPG *, int));
  58. static int     bt_seqset __P((BTREE *, EPG *, DBT *, int));
  59.  
  60. /*
  61.  * Sequential scan support.
  62.  *
  63.  * The tree can be scanned sequentially, starting from either end of the tree
  64.  * or from any specific key.  A scan request before any scanning is done is
  65.  * initialized as starting from the least node.
  66.  *
  67.  * Each tree has an EPGNO which has the current position of the cursor.  The
  68.  * cursor has to survive deletions/insertions in the tree without losing its
  69.  * position.  This is done by noting deletions without doing them, and then
  70.  * doing them when the cursor moves (or the tree is closed).
  71.  */
  72.  
  73. /*
  74.  * __BT_SEQ -- Btree sequential scan interface.
  75.  *
  76.  * Parameters:
  77.  *    dbp:    pointer to access method
  78.  *    key:    key for positioning and return value
  79.  *    data:    data return value
  80.  *    flags:    R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
  81.  *
  82.  * Returns:
  83.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  84.  */
  85. int
  86. __bt_seq(dbp, key, data, flags)
  87.     const DB *dbp;
  88.     DBT *key, *data;
  89.     u_int flags;
  90. {
  91.     BTREE *t;
  92.     EPG e;
  93.     int status;
  94.  
  95.     t = dbp->internal;
  96.  
  97.     /* Toss any page pinned across calls. */
  98.     if (t->bt_pinned != NULL) {
  99.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  100.         t->bt_pinned = NULL;
  101.     }
  102.  
  103.     /*
  104.      * If scan unitialized as yet, or starting at a specific record, set
  105.      * the scan to a specific key.  Both bt_seqset and bt_seqadv pin the
  106.      * page the cursor references if they're successful.
  107.      */
  108.     switch(flags) {
  109.     case R_NEXT:
  110.     case R_PREV:
  111.         if (ISSET(t, B_SEQINIT)) {
  112.             status = bt_seqadv(t, &e, flags);
  113.             break;
  114.         }
  115.         /* FALLTHROUGH */
  116.     case R_CURSOR:
  117.     case R_FIRST:
  118.     case R_LAST:
  119.         status = bt_seqset(t, &e, key, flags);
  120.         break;
  121.     default:
  122.         errno = EINVAL;
  123.         return (RET_ERROR);
  124.     }
  125.  
  126.     if (status == RET_SUCCESS) {
  127.         status = __bt_ret(t, &e, key, data);
  128.  
  129.         /* Update the actual cursor. */
  130.         t->bt_bcursor.pgno = e.page->pgno;
  131.         t->bt_bcursor.index = e.index;
  132.  
  133.         /*
  134.          * If the user is doing concurrent access, we copied the
  135.          * key/data, toss the page.
  136.          */
  137.         if (ISSET(t, B_DB_LOCK))
  138.             mpool_put(t->bt_mp, e.page, 0);
  139.         else
  140.             t->bt_pinned = e.page;
  141.         SET(t, B_SEQINIT);
  142.     }
  143.     return (status);
  144. }
  145.  
  146. /*
  147.  * BT_SEQSET -- Set the sequential scan to a specific key.
  148.  *
  149.  * Parameters:
  150.  *    t:    tree
  151.  *    ep:    storage for returned key
  152.  *    key:    key for initial scan position
  153.  *    flags:    R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
  154.  *
  155.  * Side effects:
  156.  *    Pins the page the cursor references.
  157.  *
  158.  * Returns:
  159.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  160.  */
  161. static int
  162. bt_seqset(t, ep, key, flags)
  163.     BTREE *t;
  164.     EPG *ep;
  165.     DBT *key;
  166.     int flags;
  167. {
  168.     EPG *e;
  169.     PAGE *h;
  170.     pgno_t pg;
  171.     int exact;
  172.  
  173.     /*
  174.      * Delete any already deleted record that we've been saving because
  175.      * the cursor pointed to it.  Since going to a specific key, should
  176.      * delete any logically deleted records so they aren't found.
  177.      */
  178.     if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor))
  179.         return (RET_ERROR);
  180.  
  181.     /*
  182.      * Find the first, last or specific key in the tree and point the cursor
  183.      * at it.  The cursor may not be moved until a new key has been found.
  184.      */
  185.     switch(flags) {
  186.     case R_CURSOR:                /* Keyed scan. */
  187.         /*
  188.          * Find the first instance of the key or the smallest key which
  189.          * is greater than or equal to the specified key.  If run out
  190.          * of keys, return RET_SPECIAL.
  191.          */
  192.         if (key->data == NULL || key->size == 0) {
  193.             errno = EINVAL;
  194.             return (RET_ERROR);
  195.         }
  196.         e = __bt_first(t, key, &exact);    /* Returns pinned page. */
  197.         if (e == NULL)
  198.             return (RET_ERROR);
  199.         /*
  200.          * If at the end of a page, skip any empty pages and find the
  201.          * next entry.
  202.          */
  203.         if (e->index == NEXTINDEX(e->page)) {
  204.             h = e->page;
  205.             do {
  206.                 pg = h->nextpg;
  207.                 mpool_put(t->bt_mp, h, 0);
  208.                 if (pg == P_INVALID)
  209.                     return (RET_SPECIAL);
  210.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  211.                     return (RET_ERROR);
  212.             } while (NEXTINDEX(h) == 0);
  213.             e->index = 0;
  214.             e->page = h;
  215.         }
  216.         *ep = *e;
  217.         break;
  218.     case R_FIRST:                /* First record. */
  219.     case R_NEXT:
  220.         /* Walk down the left-hand side of the tree. */
  221.         for (pg = P_ROOT;;) {
  222.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  223.                 return (RET_ERROR);
  224.             if (h->flags & (P_BLEAF | P_RLEAF))
  225.                 break;
  226.             pg = GETBINTERNAL(h, 0)->pgno;
  227.             mpool_put(t->bt_mp, h, 0);
  228.         }
  229.  
  230.         /* Skip any empty pages. */
  231.         while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) {
  232.             pg = h->nextpg;
  233.             mpool_put(t->bt_mp, h, 0);
  234.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  235.                 return (RET_ERROR);
  236.         }
  237.  
  238.         if (NEXTINDEX(h) == 0) {
  239.             mpool_put(t->bt_mp, h, 0);
  240.             return (RET_SPECIAL);
  241.         }
  242.  
  243.         ep->page = h;
  244.         ep->index = 0;
  245.         break;
  246.     case R_LAST:                /* Last record. */
  247.     case R_PREV:
  248.         /* Walk down the right-hand side of the tree. */
  249.         for (pg = P_ROOT;;) {
  250.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  251.                 return (RET_ERROR);
  252.             if (h->flags & (P_BLEAF | P_RLEAF))
  253.                 break;
  254.             pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
  255.             mpool_put(t->bt_mp, h, 0);
  256.         }
  257.  
  258.         /* Skip any empty pages. */
  259.         while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) {
  260.             pg = h->prevpg;
  261.             mpool_put(t->bt_mp, h, 0);
  262.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  263.                 return (RET_ERROR);
  264.         }
  265.  
  266.         if (NEXTINDEX(h) == 0) {
  267.             mpool_put(t->bt_mp, h, 0);
  268.             return (RET_SPECIAL);
  269.         }
  270.  
  271.         ep->page = h;
  272.         ep->index = NEXTINDEX(h) - 1;
  273.         break;
  274.     }
  275.     return (RET_SUCCESS);
  276. }
  277.  
  278. /*
  279.  * BT_SEQADVANCE -- Advance the sequential scan.
  280.  *
  281.  * Parameters:
  282.  *    t:    tree
  283.  *    flags:    R_NEXT, R_PREV
  284.  *
  285.  * Side effects:
  286.  *    Pins the page the new key/data record is on.
  287.  *
  288.  * Returns:
  289.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  290.  */
  291. static int
  292. bt_seqadv(t, e, flags)
  293.     BTREE *t;
  294.     EPG *e;
  295.     int flags;
  296. {
  297.     EPGNO *c, delc;
  298.     PAGE *h;
  299.     indx_t index;
  300.     pgno_t pg;
  301.  
  302.     /* Save the current cursor if going to delete it. */
  303.     c = &t->bt_bcursor;
  304.     if (ISSET(t, B_DELCRSR))
  305.         delc = *c;
  306.  
  307.     if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
  308.         return (RET_ERROR);
  309.  
  310.     /*
  311.       * Find the next/previous record in the tree and point the cursor at it.
  312.      * The cursor may not be moved until a new key has been found.
  313.      */
  314.     index = c->index;
  315.     switch(flags) {
  316.     case R_NEXT:            /* Next record. */
  317.         if (++index == NEXTINDEX(h)) {
  318.             do {
  319.                 pg = h->nextpg;
  320.                 mpool_put(t->bt_mp, h, 0);
  321.                 if (pg == P_INVALID)
  322.                     return (RET_SPECIAL);
  323.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  324.                     return (RET_ERROR);
  325.             } while (NEXTINDEX(h) == 0);
  326.             index = 0;
  327.         }
  328.         break;
  329.     case R_PREV:            /* Previous record. */
  330.         if (index-- == 0) {
  331.             do {
  332.                 pg = h->prevpg;
  333.                 mpool_put(t->bt_mp, h, 0);
  334.                 if (pg == P_INVALID)
  335.                     return (RET_SPECIAL);
  336.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  337.                     return (RET_ERROR);
  338.             } while (NEXTINDEX(h) == 0);
  339.             index = NEXTINDEX(h) - 1;
  340.         }
  341.         break;
  342.     }
  343.  
  344.     e->page = h;
  345.     e->index = index;
  346.  
  347.     /*
  348.      * Delete any already deleted record that we've been saving because the
  349.      * cursor pointed to it.  This could cause the new index to be shifted
  350.      * down by one if the record we're deleting is on the same page and has
  351.      * a larger index.
  352.      */
  353.     if (ISSET(t, B_DELCRSR)) {
  354.         CLR(t, B_DELCRSR);            /* Don't try twice. */
  355.         if (c->pgno == delc.pgno && c->index > delc.index)
  356.             --c->index;
  357.         if (__bt_crsrdel(t, &delc))
  358.             return (RET_ERROR);
  359.     }
  360.     return (RET_SUCCESS);
  361. }
  362.  
  363. /*
  364.  * __BT_CRSRDEL -- Delete the record referenced by the cursor.
  365.  *
  366.  * Parameters:
  367.  *    t:    tree
  368.  *
  369.  * Returns:
  370.  *    RET_ERROR, RET_SUCCESS
  371.  */
  372. int
  373. __bt_crsrdel(t, c)
  374.     BTREE *t;
  375.     EPGNO *c;
  376. {
  377.     PAGE *h;
  378.     int status;
  379.  
  380.     CLR(t, B_DELCRSR);            /* Don't try twice. */
  381.     if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
  382.         return (RET_ERROR);
  383.     status = __bt_dleaf(t, h, c->index);
  384.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  385.     return (status);
  386. }
  387.