bt_seq.c File Reference

#include <sys/types.h>
#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "../include/db.h"
#include "btree.h"

Include dependency graph for bt_seq.c:

Go to the source code of this file.

Functions

static int __bt_first (BTREE *t, const DBT *key, EPG *erval, int *exactp)
int __bt_seq (DB *dbp, DBT *key, DBT *data, u_int flags) const
static int __bt_seqadv (BTREE *t, EPG *ep, int flags)
static int __bt_seqset (BTREE *t, EPG *ep, DBT *key, int flags)
void __bt_setcur (BTREE *t, pgno_t pgno, u_int index)
static int __bt_seqset __P ((BTREE *, EPG *, DBT *, int))
static int __bt_seqadv __P ((BTREE *, EPG *, int))
static int __bt_first __P ((BTREE *, const DBT *, EPG *, int *))


Function Documentation

static int __bt_first ( BTREE t,
const DBT key,
EPG erval,
int *  exactp 
) [static]

Definition at line 342 of file bt_seq.c.

References __bt_cmp(), __bt_search(), B_NODUPS, F_ISSET, h, _epg::index, mpool_get, mpool_put, NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _page::pgno, _page::prevpg, RET_ERROR, RET_SPECIAL, and RET_SUCCESS.

Referenced by __bt_seqadv(), and __bt_seqset().

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 }

int __bt_seq ( DB dbp,
DBT key,
DBT data,
u_int  flags 
) const

Definition at line 77 of file bt_seq.c.

References __bt_ret(), __bt_seqadv(), __bt_seqset(), __bt_setcur(), B_DB_LOCK, _btree::bt_cursor, _btree::bt_mp, _btree::bt_pinned, _btree::bt_rdata, _btree::bt_rkey, CURS_INIT, e, errno, F_ISSET, _epg::index, mpool_put, NULL, _epg::page, _page::pgno, R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV, RET_ERROR, RET_SUCCESS, and status.

Referenced by __bt_open().

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 }

static int __bt_seqadv ( BTREE t,
EPG ep,
int  flags 
) [static]

Definition at line 240 of file bt_seq.c.

References __bt_first(), c, CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, F_CLR, F_ISSET, h, _epg::index, _epgno::index, _cursor::key, mpool_get, mpool_put, NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _cursor::pg, _epgno::pgno, _page::prevpg, R_NEXT, R_PREV, RET_ERROR, RET_SPECIAL, and RET_SUCCESS.

Referenced by __bt_seq().

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 }

static int __bt_seqset ( BTREE t,
EPG ep,
DBT key,
int  flags 
) [static]

Definition at line 152 of file bt_seq.c.

References __bt_first(), DBT::data, errno, _page::flags, GETBINTERNAL, h, _epg::index, mpool_get, mpool_put, NEXTINDEX, NULL, P_BLEAF, P_RLEAF, P_ROOT, _epg::page, R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV, RET_ERROR, RET_SPECIAL, RET_SUCCESS, and DBT::size.

Referenced by __bt_seq().

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 }

void __bt_setcur ( BTREE t,
pgno_t  pgno,
u_int  index 
)

Definition at line 443 of file bt_seq.c.

References CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, CURS_INIT, F_CLR, F_SET, free, and NULL.

Referenced by __bt_put(), and __bt_seq().

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 }

static int __bt_seqset __P ( (BTREE *, EPG *, DBT *, int)   )  [static]

static int __bt_seqadv __P ( (BTREE *, EPG *, int)   )  [static]

static int __bt_first __P ( (BTREE *, const DBT *, EPG *, int *)   )  [static]


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