* Copyright (c) 1990 The Regents of the University of California.
* 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 5.4 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
* _BT_SEQINIT -- Initialize a sequential scan on the btree.
* Sets the tree's notion of the current scan location correctly
* given a key and a direction.
* t -- tree in which to initialize scan
* key -- key for initial scan position
* flags -- R_NEXT, R_PREV
* RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data
* Changes current scan position for the tree. Almost certainly
* changes current page, as well. Sets BTF_SEQINIT bit in tree
* flags, so that we know we've initialized a scan.
_bt_seqinit(t
, key
, flags
)
* Figure out if we really have to search for the key that the
* user supplied. If key is null, then this is an unkeyed scan
* and we can just start from an endpoint.
if (key
->data
!= (u_char
*) NULL
) {
/* key supplied, find first instance of it */
item
= _bt_first(t
, key
);
c
->c_index
= item
->bti_index
;
c
->c_pgno
= t
->bt_curpage
->h_pgno
;
* Unkeyed scan. For backward scans, find the last item
* in the tree; for forward scans, find the first item.
if (_bt_getpage(t
, (pgno_t
) P_ROOT
) == RET_ERROR
)
if (flags
== R_LAST
|| flags
== R_PREV
) {
while (!(h
->h_flags
& F_LEAF
)) {
id
= (IDATUM
*) GETDATUM(h
,last
);
if (_bt_getpage(t
, id
->i_pgno
) == RET_ERROR
)
while (NEXTINDEX(h
) == 0 && h
->h_prevpg
!= P_NONE
) {
if (_bt_getpage(t
, h
->h_prevpg
) == RET_ERROR
)
c
->c_index
= NEXTINDEX(h
) - 1;
} else if (flags
== R_FIRST
|| flags
== R_NEXT
) {
while (!(h
->h_flags
& F_LEAF
)) {
id
= (IDATUM
*) GETDATUM(h
,0);
if (_bt_getpage(t
, id
->i_pgno
) == RET_ERROR
)
while (NEXTINDEX(h
) == 0 && h
->h_nextpg
!= P_NONE
) {
if (_bt_getpage(t
, h
->h_nextpg
) == RET_ERROR
)
/* okay, scan is initialized */
t
->bt_flags
|= BTF_SEQINIT
;
/* don't need the descent stack anymore */
while (_bt_pop(t
) != P_NONE
)
if (c
->c_index
== NEXTINDEX(t
->bt_curpage
))
* _BT_SEQADVANCE -- Advance the sequential scan on this tree.
* Moves the current location pointer for the scan on this tree one
* spot in the requested direction.
* t -- btree being scanned
* flags -- for R_NEXT, R_PREV
* RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no
* more data in the specified direction.
* May change current page.
if (_bt_getpage(t
, c
->c_pgno
) == RET_ERROR
)
/* by the time we get here, don't need the cursor key anymore */
if (c
->c_key
!= (char *) NULL
)
* This is a forward scan. If the cursor is pointing
* at a virtual record (that is, it was pointing at
* a record that got deleted), then we should return
* the record it's pointing at now. Otherwise, we
* should advance the scan. In either case, we need
* to be careful not to run off the end of the current
if (c
->c_flags
& CRSR_BEFORE
) {
if (index
>= NEXTINDEX(h
)) {
/* out of items on this page, get next page */
if (h
->h_nextpg
== P_NONE
) {
/* tell caller we're done... */
c
->c_index
= NEXTINDEX(h
);
if (_bt_getpage(t
, h
->h_nextpg
)
c
->c_index
= NEXTINDEX(h
);
} while (NEXTINDEX(h
) == 0
&& h
->h_nextpg
!= P_NONE
);
/* tell caller we're done */
c
->c_index
= NEXTINDEX(h
);
c
->c_flags
&= ~CRSR_BEFORE
;
} else if (++index
>= NEXTINDEX(h
)) {
/* out of items on this page, get next page */
if (h
->h_nextpg
== P_NONE
) {
/* tell caller we're done... */
c
->c_index
= NEXTINDEX(h
);
if (_bt_getpage(t
, h
->h_nextpg
) == RET_ERROR
) {
c
->c_index
= NEXTINDEX(h
);
} while (NEXTINDEX(h
) == 0 && h
->h_nextpg
!= P_NONE
);
/* tell caller we're done */
c
->c_index
= NEXTINDEX(h
);
} else if (flags
== R_PREV
) {
/* for backward scans, life is substantially easier */
c
->c_flags
&= ~CRSR_BEFORE
;
if (c
->c_key
!= (char *) NULL
) {
c
->c_key
= (char *) NULL
;
/* out of items on this page, get next page */
if (h
->h_prevpg
== P_NONE
)
if (_bt_getpage(t
, h
->h_prevpg
) == RET_ERROR
)
} while (NEXTINDEX(h
) == 0 && h
->h_prevpg
!= P_NONE
);
index
= NEXTINDEX(h
) - 1;
/* must specify a direction */