2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 #if defined(LIBC_SCCS) && !defined(lint)
36 static char sccsid[] = "@(#)bt_seq.c 8.7 (Berkeley) 7/20/94";
37 #endif /* LIBC_SCCS and not lint */
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
41 #include <sys/types.h>
51 static int __bt_first(BTREE *, const DBT *, EPG *, int *);
52 static int __bt_seqadv(BTREE *, EPG *, int);
53 static int __bt_seqset(BTREE *, EPG *, DBT *, int);
56 * Sequential scan support.
58 * The tree can be scanned sequentially, starting from either end of the
59 * tree or from any specific key. A scan request before any scanning is
60 * done is initialized as starting from the least node.
65 * Btree sequential scan interface.
68 * dbp: pointer to access method
69 * key: key for positioning and return value
70 * data: data return value
71 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
74 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
77 __bt_seq(const DB *dbp, DBT *key, DBT *data, u_int flags)
85 /* Toss any page pinned across calls. */
86 if (t->bt_pinned != NULL) {
87 mpool_put(t->bt_mp, t->bt_pinned, 0);
92 * If scan unitialized as yet, or starting at a specific record, set
93 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin
94 * the page the cursor references if they're successful.
99 if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
100 status = __bt_seqadv(t, &e, flags);
107 status = __bt_seqset(t, &e, key, flags);
114 if (status == RET_SUCCESS) {
115 __bt_setcur(t, e.page->pgno, e.index);
118 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
121 * If the user is doing concurrent access, we copied the
122 * key/data, toss the page.
124 if (F_ISSET(t, B_DB_LOCK))
125 mpool_put(t->bt_mp, e.page, 0);
127 t->bt_pinned = e.page;
134 * Set the sequential scan to a specific key.
138 * ep: storage for returned key
139 * key: key for initial scan position
140 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
143 * Pins the page the cursor references.
146 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
149 __bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags)
156 * Find the first, last or specific key in the tree and point the
157 * cursor at it. The cursor may not be moved until a new key has
161 case R_CURSOR: /* Keyed scan. */
163 * Find the first instance of the key or the smallest key
164 * which is greater than or equal to the specified key.
166 if (key->data == NULL || key->size == 0) {
170 return (__bt_first(t, key, ep, &exact));
171 case R_FIRST: /* First record. */
173 /* Walk down the left-hand side of the tree. */
174 for (pg = P_ROOT;;) {
175 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
178 /* Check for an empty tree. */
179 if (NEXTINDEX(h) == 0) {
180 mpool_put(t->bt_mp, h, 0);
181 return (RET_SPECIAL);
184 if (h->flags & (P_BLEAF | P_RLEAF))
186 pg = GETBINTERNAL(h, 0)->pgno;
187 mpool_put(t->bt_mp, h, 0);
192 case R_LAST: /* Last record. */
194 /* Walk down the right-hand side of the tree. */
195 for (pg = P_ROOT;;) {
196 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
199 /* Check for an empty tree. */
200 if (NEXTINDEX(h) == 0) {
201 mpool_put(t->bt_mp, h, 0);
202 return (RET_SPECIAL);
205 if (h->flags & (P_BLEAF | P_RLEAF))
207 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
208 mpool_put(t->bt_mp, h, 0);
212 ep->index = NEXTINDEX(h) - 1;
215 return (RET_SUCCESS);
220 * Advance the sequential scan.
224 * flags: R_NEXT, R_PREV
227 * Pins the page the new key/data record is on.
230 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
233 __bt_seqadv(BTREE *t, EPG *ep, int flags)
242 * There are a couple of states that we can be in. The cursor has
243 * been initialized by the time we get here, but that's all we know.
248 * The cursor was deleted where there weren't any duplicate records,
249 * so the key was saved. Find out where that key would go in the
250 * current tree. It doesn't matter if the returned key is an exact
251 * match or not -- if it's an exact match, the record was added after
252 * the delete so we can just return it. If not, as long as there's
253 * a record there, return it.
255 if (F_ISSET(c, CURS_ACQUIRE))
256 return (__bt_first(t, &c->key, ep, &exact));
258 /* Get the page referenced by the cursor. */
259 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
263 * Find the next/previous record in the tree and point the cursor at
264 * it. The cursor may not be moved until a new key has been found.
267 case R_NEXT: /* Next record. */
269 * The cursor was deleted in duplicate records, and moved
270 * forward to a record that has yet to be returned. Clear
271 * that flag, and return the record.
273 if (F_ISSET(c, CURS_AFTER))
276 if (++idx == NEXTINDEX(h)) {
278 mpool_put(t->bt_mp, h, 0);
280 return (RET_SPECIAL);
281 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
286 case R_PREV: /* Previous record. */
288 * The cursor was deleted in duplicate records, and moved
289 * backward to a record that has yet to be returned. Clear
290 * that flag, and return the record.
292 if (F_ISSET(c, CURS_BEFORE)) {
293 usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE);
295 ep->index = c->pg.index;
296 return (RET_SUCCESS);
301 mpool_put(t->bt_mp, h, 0);
303 return (RET_SPECIAL);
304 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
306 idx = NEXTINDEX(h) - 1;
314 return (RET_SUCCESS);
319 * Find the first entry.
325 * exactp: pointer to exact match flag
328 * The first entry in the tree greater than or equal to key,
329 * or RET_SPECIAL if no such key exists.
332 __bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp)
339 * Find any matching record; __bt_search pins the page.
341 * If it's an exact match and duplicates are possible, walk backwards
342 * in the tree until we find the first one. Otherwise, make sure it's
343 * a valid key (__bt_search may return an index just past the end of a
344 * page) and return it.
346 if ((ep = __bt_search(t, key, exactp)) == NULL)
349 if (F_ISSET(t, B_NODUPS)) {
351 return (RET_SUCCESS);
355 * Walk backwards, as long as the entry matches and there are
356 * keys left in the tree. Save a copy of each match in case
362 if (save.page->pgno != ep->page->pgno) {
363 mpool_put(t->bt_mp, save.page, 0);
366 save.index = ep->index;
369 * Don't unpin the page the last (or original) match
370 * was on, but make sure it's unpinned if an error
373 if (ep->index == 0) {
374 if (h->prevpg == P_INVALID)
376 if (h->pgno != save.page->pgno)
377 mpool_put(t->bt_mp, h, 0);
378 if ((h = mpool_get(t->bt_mp,
379 h->prevpg, 0)) == NULL) {
380 if (h->pgno == save.page->pgno)
386 ep->index = NEXTINDEX(h);
389 } while (__bt_cmp(t, key, ep) == 0);
392 * Reach here with the last page that was looked at pinned,
393 * which may or may not be the same as the last (or original)
394 * match page. If it's not useful, release it.
396 if (h->pgno != save.page->pgno)
397 mpool_put(t->bt_mp, h, 0);
400 return (RET_SUCCESS);
403 /* If at the end of a page, find the next entry. */
404 if (ep->index == NEXTINDEX(ep->page)) {
407 mpool_put(t->bt_mp, h, 0);
409 return (RET_SPECIAL);
410 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
416 return (RET_SUCCESS);
421 * Set the cursor to an entry in the tree.
429 __bt_setcur(BTREE *t, pgno_t pgno, u_int idx)
431 /* Lose any already deleted key. */
432 if (t->bt_cursor.key.data != NULL) {
433 free(t->bt_cursor.key.data);
434 t->bt_cursor.key.size = 0;
435 t->bt_cursor.key.data = NULL;
437 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
439 /* Update the cursor. */
440 t->bt_cursor.pg.pgno = pgno;
441 t->bt_cursor.pg.index = idx;
442 F_SET(&t->bt_cursor, CURS_INIT);