* Copyright (c) 1990, 1993
* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* %sccs.include.redist.c%
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)bt_seq.c 8.1 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
static int bt_seqadv
__P((BTREE
*, EPG
*, int));
static int bt_seqset
__P((BTREE
*, EPG
*, DBT
*, int));
* Sequential scan support.
* The tree can be scanned sequentially, starting from either end of the tree
* or from any specific key. A scan request before any scanning is done is
* initialized as starting from the least node.
* Each tree has an EPGNO which has the current position of the cursor. The
* cursor has to survive deletions/insertions in the tree without losing its
* position. This is done by noting deletions without doing them, and then
* doing them when the cursor moves (or the tree is closed).
* __BT_SEQ -- Btree sequential scan interface.
* dbp: pointer to access method
* key: key for positioning and return value
* data: data return value
* flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
* RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
__bt_seq(dbp
, key
, data
, flags
)
* If scan unitialized as yet, or starting at a specific record, set
* the scan to a specific key. Both bt_seqset and bt_seqadv pin the
* page the cursor references if they're successful.
if (ISSET(t
, B_SEQINIT
)) {
status
= bt_seqadv(t
, &e
, flags
);
status
= bt_seqset(t
, &e
, key
, flags
);
if (status
== RET_SUCCESS
) {
status
= __bt_ret(t
, &e
, key
, data
);
/* Update the actual cursor. */
t
->bt_bcursor
.pgno
= e
.page
->pgno
;
t
->bt_bcursor
.index
= e
.index
;
mpool_put(t
->bt_mp
, e
.page
, 0);
* BT_SEQSET -- Set the sequential scan to a specific key.
* ep: storage for returned key
* key: key for initial scan position
* flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
* Pins the page the cursor references.
* RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
bt_seqset(t
, ep
, key
, flags
)
* Delete any already deleted record that we've been saving because
* the cursor pointed to it. Since going to a specific key, should
* delete any logically deleted records so they aren't found.
if (ISSET(t
, B_DELCRSR
) && __bt_crsrdel(t
, &t
->bt_bcursor
))
* Find the first, last or specific key in the tree and point the cursor
* at it. The cursor may not be moved until a new key has been found.
case R_CURSOR
: /* Keyed scan. */
* Find the first instance of the key or the smallest key which
* is greater than or equal to the specified key. If run out
* of keys, return RET_SPECIAL.
if (key
->data
== NULL
|| key
->size
== 0) {
e
= __bt_first(t
, key
, &exact
); /* Returns pinned page. */
* If at the end of a page, skip any empty pages and find the
if (e
->index
== NEXTINDEX(e
->page
)) {
mpool_put(t
->bt_mp
, h
, 0);
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
} while (NEXTINDEX(h
) == 0);
case R_FIRST
: /* First record. */
/* Walk down the left-hand side of the tree. */
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
if (h
->flags
& (P_BLEAF
| P_RLEAF
))
pg
= GETBINTERNAL(h
, 0)->pgno
;
mpool_put(t
->bt_mp
, h
, 0);
/* Skip any empty pages. */
while (NEXTINDEX(h
) == 0 && h
->nextpg
!= P_INVALID
) {
mpool_put(t
->bt_mp
, h
, 0);
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
mpool_put(t
->bt_mp
, h
, 0);
case R_LAST
: /* Last record. */
/* Walk down the right-hand side of the tree. */
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
if (h
->flags
& (P_BLEAF
| P_RLEAF
))
pg
= GETBINTERNAL(h
, NEXTINDEX(h
) - 1)->pgno
;
mpool_put(t
->bt_mp
, h
, 0);
/* Skip any empty pages. */
while (NEXTINDEX(h
) == 0 && h
->prevpg
!= P_INVALID
) {
mpool_put(t
->bt_mp
, h
, 0);
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
mpool_put(t
->bt_mp
, h
, 0);
ep
->index
= NEXTINDEX(h
) - 1;
* BT_SEQADVANCE -- Advance the sequential scan.
* Pins the page the new key/data record is on.
* RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
/* Save the current cursor if going to delete it. */
if ((h
= mpool_get(t
->bt_mp
, c
->pgno
, 0)) == NULL
)
* Find the next/previous record in the tree and point the cursor at it.
* The cursor may not be moved until a new key has been found.
case R_NEXT
: /* Next record. */
if (++index
== NEXTINDEX(h
)) {
mpool_put(t
->bt_mp
, h
, 0);
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
} while (NEXTINDEX(h
) == 0);
case R_PREV
: /* Previous record. */
mpool_put(t
->bt_mp
, h
, 0);
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
} while (NEXTINDEX(h
) == 0);
index
= NEXTINDEX(h
) - 1;
* Delete any already deleted record that we've been saving because the
* cursor pointed to it. This could cause the new index to be shifted
* down by one if the record we're deleting is on the same page and has
if (ISSET(t
, B_DELCRSR
)) {
CLR(t
, B_DELCRSR
); /* Don't try twice. */
if (c
->pgno
== delc
.pgno
&& c
->index
> delc
.index
)
if (__bt_crsrdel(t
, &delc
))
* __BT_CRSRDEL -- Delete the record referenced by the cursor.
CLR(t
, B_DELCRSR
); /* Don't try twice. */
if ((h
= mpool_get(t
->bt_mp
, c
->pgno
, 0)) == NULL
)
status
= __bt_dleaf(t
, h
, c
->index
);
mpool_put(t
->bt_mp
, h
, MPOOL_DIRTY
);