bt_seq.c

Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  * The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Mike Olson.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. All advertising materials mentioning features or use of this software
00017  *    must display the following acknowledgement:
00018  * This product includes software developed by the University of
00019  * California, Berkeley and its contributors.
00020  * 4. Neither the name of the University nor the names of its contributors
00021  *    may be used to endorse or promote products derived from this software
00022  *    without specific prior written permission.
00023  *
00024  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00025  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00026  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00027  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00028  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00029  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00030  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00031  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00032  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00033  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00034  * SUCH DAMAGE.
00035  */
00036 
00037 #if defined(LIBC_SCCS) && !defined(lint)
00038 static char sccsid[] = "@(#)bt_seq.c   8.7 (Berkeley) 7/20/94";
00039 #endif /* LIBC_SCCS and not lint */
00040 
00041 #include <sys/types.h>
00042 
00043 #include <errno.h>
00044 #include <stddef.h>
00045 #include <stdio.h>
00046 #include <stdlib.h>
00047 
00048 #include "../include/db.h"
00049 #include "btree.h"
00050 
00051 static int __bt_first __P((BTREE *, const DBT *, EPG *, int *));
00052 static int __bt_seqadv __P((BTREE *, EPG *, int));
00053 static int __bt_seqset __P((BTREE *, EPG *, DBT *, int));
00054 
00055 /*
00056  * Sequential scan support.
00057  *
00058  * The tree can be scanned sequentially, starting from either end of the
00059  * tree or from any specific key.  A scan request before any scanning is
00060  * done is initialized as starting from the least node.
00061  */
00062 
00063 /*
00064  * __bt_seq --
00065  * Btree sequential scan interface.
00066  *
00067  * Parameters:
00068  * dbp:  pointer to access method
00069  * key:  key for positioning and return value
00070  * data: data return value
00071  * flags:   R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
00072  *
00073  * Returns:
00074  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
00075  */
00076 int
00077 __bt_seq(dbp, key, data, flags)
00078    const DB *dbp;
00079    DBT *key, *data;
00080    u_int flags;
00081 {
00082    BTREE *t;
00083    EPG e;
00084    int status;
00085 
00086    t = dbp->internal;
00087 
00088    /* Toss any page pinned across calls. */
00089    if (t->bt_pinned != NULL) {
00090       mpool_put(t->bt_mp, t->bt_pinned, 0);
00091       t->bt_pinned = NULL;
00092    }
00093 
00094    /*
00095     * If scan uninitialized as yet, or starting at a specific record, set
00096     * the scan to a specific key.  Both __bt_seqset and __bt_seqadv pin
00097     * the page the cursor references if they're successful.
00098     */
00099    switch (flags) {
00100    case R_NEXT:
00101    case R_PREV:
00102       if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
00103          status = __bt_seqadv(t, &e, flags);
00104          break;
00105       }
00106       /* FALLTHROUGH */
00107    case R_FIRST:
00108    case R_LAST:
00109    case R_CURSOR:
00110       status = __bt_seqset(t, &e, key, flags);
00111       break;
00112    default:
00113       errno = EINVAL;
00114       return (RET_ERROR);
00115    }
00116 
00117    if (status == RET_SUCCESS) {
00118       __bt_setcur(t, e.page->pgno, e.index);
00119 
00120       status =
00121           __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
00122 
00123       /*
00124        * If the user is doing concurrent access, we copied the
00125        * key/data, toss the page.
00126        */
00127       if (F_ISSET(t, B_DB_LOCK))
00128          mpool_put(t->bt_mp, e.page, 0);
00129       else
00130          t->bt_pinned = e.page;
00131    }
00132    return (status);
00133 }
00134 
00135 /*
00136  * __bt_seqset --
00137  * Set the sequential scan to a specific key.
00138  *
00139  * Parameters:
00140  * t: tree
00141  * ep:   storage for returned key
00142  * key:  key for initial scan position
00143  * flags:   R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
00144  *
00145  * Side effects:
00146  * Pins the page the cursor references.
00147  *
00148  * Returns:
00149  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
00150  */
00151 static int
00152 __bt_seqset(t, ep, key, flags)
00153    BTREE *t;
00154    EPG *ep;
00155    DBT *key;
00156    int flags;
00157 {
00158    PAGE *h;
00159    pgno_t pg;
00160    int exact;
00161 
00162    /*
00163     * Find the first, last or specific key in the tree and point the
00164     * cursor at it.  The cursor may not be moved until a new key has
00165     * been found.
00166     */
00167    switch (flags) {
00168    case R_CURSOR:          /* Keyed scan. */
00169       /*
00170        * Find the first instance of the key or the smallest key
00171        * which is greater than or equal to the specified key.
00172        */
00173       if (key->data == NULL || key->size == 0) {
00174          errno = EINVAL;
00175          return (RET_ERROR);
00176       }
00177       return (__bt_first(t, key, ep, &exact));
00178    case R_FIRST:           /* First record. */
00179    case R_NEXT:
00180       /* Walk down the left-hand side of the tree. */
00181       for (pg = P_ROOT;;) {
00182          if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
00183             return (RET_ERROR);
00184 
00185          /* Check for an empty tree. */
00186          if (NEXTINDEX(h) == 0) {
00187             mpool_put(t->bt_mp, h, 0);
00188             return (RET_SPECIAL);
00189          }
00190 
00191          if (h->flags & (P_BLEAF | P_RLEAF))
00192             break;
00193          pg = GETBINTERNAL(h, 0)->pgno;
00194          mpool_put(t->bt_mp, h, 0);
00195       }
00196       ep->page = h;
00197       ep->index = 0;
00198       break;
00199    case R_LAST:            /* Last record. */
00200    case R_PREV:
00201       /* Walk down the right-hand side of the tree. */
00202       for (pg = P_ROOT;;) {
00203          if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
00204             return (RET_ERROR);
00205 
00206          /* Check for an empty tree. */
00207          if (NEXTINDEX(h) == 0) {
00208             mpool_put(t->bt_mp, h, 0);
00209             return (RET_SPECIAL);
00210          }
00211 
00212          if (h->flags & (P_BLEAF | P_RLEAF))
00213             break;
00214          pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
00215          mpool_put(t->bt_mp, h, 0);
00216       }
00217 
00218       ep->page = h;
00219       ep->index = NEXTINDEX(h) - 1;
00220       break;
00221    }
00222    return (RET_SUCCESS);
00223 }
00224 
00225 /*
00226  * __bt_seqadvance --
00227  * Advance the sequential scan.
00228  *
00229  * Parameters:
00230  * t: tree
00231  * flags:   R_NEXT, R_PREV
00232  *
00233  * Side effects:
00234  * Pins the page the new key/data record is on.
00235  *
00236  * Returns:
00237  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
00238  */
00239 static int
00240 __bt_seqadv(t, ep, flags)
00241    BTREE *t;
00242    EPG *ep;
00243    int flags;
00244 {
00245    CURSOR *c;
00246    PAGE *h;
00247    indx_t index = 0;
00248    pgno_t pg;
00249    int exact;
00250 
00251    /*
00252     * There are a couple of states that we can be in.  The cursor has
00253     * been initialized by the time we get here, but that's all we know.
00254     */
00255    c = &t->bt_cursor;
00256 
00257    /*
00258     * The cursor was deleted where there weren't any duplicate records,
00259     * so the key was saved.  Find out where that key would go in the
00260     * current tree.  It doesn't matter if the returned key is an exact
00261     * match or not -- if it's an exact match, the record was added after
00262     * the delete so we can just return it.  If not, as long as there's
00263     * a record there, return it.
00264     */
00265    if (F_ISSET(c, CURS_ACQUIRE))
00266       return (__bt_first(t, &c->key, ep, &exact));
00267 
00268    /* Get the page referenced by the cursor. */
00269    if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
00270       return (RET_ERROR);
00271 
00272    /*
00273     * Find the next/previous record in the tree and point the cursor at
00274     * it.  The cursor may not be moved until a new key has been found.
00275     */
00276    switch (flags) {
00277    case R_NEXT:         /* Next record. */
00278       /*
00279        * The cursor was deleted in duplicate records, and moved
00280        * forward to a record that has yet to be returned.  Clear
00281        * that flag, and return the record.
00282        */
00283       if (F_ISSET(c, CURS_AFTER))
00284          goto usecurrent;
00285       index = c->pg.index;
00286       if (++index == NEXTINDEX(h)) {
00287          pg = h->nextpg;
00288          mpool_put(t->bt_mp, h, 0);
00289          if (pg == P_INVALID)
00290             return (RET_SPECIAL);
00291          if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
00292             return (RET_ERROR);
00293          index = 0;
00294       }
00295       break;
00296    case R_PREV:         /* Previous record. */
00297       /*
00298        * The cursor was deleted in duplicate records, and moved
00299        * backward to a record that has yet to be returned.  Clear
00300        * that flag, and return the record.
00301        */
00302       if (F_ISSET(c, CURS_BEFORE)) {
00303 usecurrent:    F_CLR(c, CURS_AFTER | CURS_BEFORE);
00304          ep->page = h;
00305          ep->index = c->pg.index;
00306          return (RET_SUCCESS);
00307       }
00308       index = c->pg.index;
00309       if (index == 0) {
00310          pg = h->prevpg;
00311          mpool_put(t->bt_mp, h, 0);
00312          if (pg == P_INVALID)
00313             return (RET_SPECIAL);
00314          if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
00315             return (RET_ERROR);
00316          index = NEXTINDEX(h) - 1;
00317       } else
00318          --index;
00319       break;
00320    }
00321 
00322    ep->page = h;
00323    ep->index = index;
00324    return (RET_SUCCESS);
00325 }
00326 
00327 /*
00328  * __bt_first --
00329  * Find the first entry.
00330  *
00331  * Parameters:
00332  * t: the tree
00333  *    key:  the key
00334  *  erval:  return EPG
00335  * exactp:  pointer to exact match flag
00336  *
00337  * Returns:
00338  * The first entry in the tree greater than or equal to key,
00339  * or RET_SPECIAL if no such key exists.
00340  */
00341 static int
00342 __bt_first(t, key, erval, exactp)
00343    BTREE *t;
00344    const DBT *key;
00345    EPG *erval;
00346    int *exactp;
00347 {
00348    PAGE *h;
00349    EPG *ep, save;
00350    pgno_t pg;
00351 
00352    /*
00353     * Find any matching record; __bt_search pins the page.
00354     *
00355     * If it's an exact match and duplicates are possible, walk backwards
00356     * in the tree until we find the first one.  Otherwise, make sure it's
00357     * a valid key (__bt_search may return an index just past the end of a
00358     * page) and return it.
00359     */
00360    if ((ep = __bt_search(t, key, exactp)) == NULL)
00361       return (RET_SPECIAL);
00362    if (*exactp) {
00363       if (F_ISSET(t, B_NODUPS)) {
00364          *erval = *ep;
00365          return (RET_SUCCESS);
00366       }
00367 
00368       /*
00369        * Walk backwards, as long as the entry matches and there are
00370        * keys left in the tree.  Save a copy of each match in case
00371        * we go too far.
00372        */
00373       save = *ep;
00374       h = ep->page;
00375       do {
00376          if (save.page->pgno != ep->page->pgno) {
00377             mpool_put(t->bt_mp, save.page, 0);
00378             save = *ep;
00379          } else
00380             save.index = ep->index;
00381 
00382          /*
00383           * Don't unpin the page the last (or original) match
00384           * was on, but make sure it's unpinned if an error
00385           * occurs.
00386           */
00387          if (ep->index == 0) {
00388             if (h->prevpg == P_INVALID)
00389                break;
00390             if (h->pgno != save.page->pgno)
00391                mpool_put(t->bt_mp, h, 0);
00392             if ((h = mpool_get(t->bt_mp,
00393                 h->prevpg, 0)) == NULL) {
00394                if (h->pgno == save.page->pgno)
00395                   mpool_put(t->bt_mp,
00396                       save.page, 0);
00397                return (RET_ERROR);
00398             }
00399             ep->page = h;
00400             ep->index = NEXTINDEX(h);
00401          }
00402          --ep->index;
00403       } while (__bt_cmp(t, key, ep) == 0);
00404 
00405       /*
00406        * Reach here with the last page that was looked at pinned,
00407        * which may or may not be the same as the last (or original)
00408        * match page.  If it's not useful, release it.
00409        */
00410       if (h->pgno != save.page->pgno)
00411          mpool_put(t->bt_mp, h, 0);
00412 
00413       *erval = save;
00414       return (RET_SUCCESS);
00415    }
00416 
00417    /* If at the end of a page, find the next entry. */
00418    if (ep->index == NEXTINDEX(ep->page)) {
00419       h = ep->page;
00420       pg = h->nextpg;
00421       mpool_put(t->bt_mp, h, 0);
00422       if (pg == P_INVALID)
00423          return (RET_SPECIAL);
00424       if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
00425          return (RET_ERROR);
00426       ep->index = 0;
00427       ep->page = h;
00428    }
00429    *erval = *ep;
00430    return (RET_SUCCESS);
00431 }
00432 
00433 /*
00434  * __bt_setcur --
00435  * Set the cursor to an entry in the tree.
00436  *
00437  * Parameters:
00438  * t: the tree
00439  *   pgno:  page number
00440  *  index:  page index
00441  */
00442 void
00443 __bt_setcur(t, pgno, index)
00444    BTREE *t;
00445    pgno_t pgno;
00446    u_int index;
00447 {
00448    /* Lose any already deleted key. */
00449    if (t->bt_cursor.key.data != NULL) {
00450       free(t->bt_cursor.key.data);
00451       t->bt_cursor.key.size = 0;
00452       t->bt_cursor.key.data = NULL;
00453    }
00454    F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
00455 
00456    /* Update the cursor. */
00457    t->bt_cursor.pg.pgno = pgno;
00458    t->bt_cursor.pg.index = index;
00459    F_SET(&t->bt_cursor, CURS_INIT);
00460 }

Generated on Thu Apr 16 06:27:16 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6