1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Mike Olson.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
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.
21 *
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
32 * SUCH DAMAGE.
33 */
34
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$");
40
41 #include <sys/types.h>
42
43 #include <errno.h>
44 #include <stddef.h>
45 #include <stdio.h>
46 #include <stdlib.h>
47
48 #include <db.h>
49 #include "btree.h"
50
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);
54
55 /*
56 * Sequential scan support.
57 *
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.
61 */
62
63 /*
64 * __bt_seq --
65 * Btree sequential scan interface.
66 *
67 * Parameters:
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.
72 *
73 * Returns:
74 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
75 */
76 int
__bt_seq(const DB * dbp,DBT * key,DBT * data,u_int flags)77 __bt_seq(const DB *dbp, DBT *key, DBT *data, u_int flags)
78 {
79 BTREE *t;
80 EPG e;
81 int status;
82
83 t = dbp->internal;
84
85 /* Toss any page pinned across calls. */
86 if (t->bt_pinned != NULL) {
87 mpool_put(t->bt_mp, t->bt_pinned, 0);
88 t->bt_pinned = NULL;
89 }
90
91 /*
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.
95 */
96 switch (flags) {
97 case R_NEXT:
98 case R_PREV:
99 if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
100 status = __bt_seqadv(t, &e, flags);
101 break;
102 }
103 /* FALLTHROUGH */
104 case R_FIRST:
105 case R_LAST:
106 case R_CURSOR:
107 status = __bt_seqset(t, &e, key, flags);
108 break;
109 default:
110 errno = EINVAL;
111 return (RET_ERROR);
112 }
113
114 if (status == RET_SUCCESS) {
115 __bt_setcur(t, e.page->pgno, e.index);
116
117 status =
118 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
119
120 /*
121 * If the user is doing concurrent access, we copied the
122 * key/data, toss the page.
123 */
124 if (F_ISSET(t, B_DB_LOCK))
125 mpool_put(t->bt_mp, e.page, 0);
126 else
127 t->bt_pinned = e.page;
128 }
129 return (status);
130 }
131
132 /*
133 * __bt_seqset --
134 * Set the sequential scan to a specific key.
135 *
136 * Parameters:
137 * t: tree
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
141 *
142 * Side effects:
143 * Pins the page the cursor references.
144 *
145 * Returns:
146 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
147 */
148 static int
__bt_seqset(BTREE * t,EPG * ep,DBT * key,int flags)149 __bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags)
150 {
151 PAGE *h;
152 pgno_t pg;
153 int exact;
154
155 /*
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
158 * been found.
159 */
160 switch (flags) {
161 case R_CURSOR: /* Keyed scan. */
162 /*
163 * Find the first instance of the key or the smallest key
164 * which is greater than or equal to the specified key.
165 */
166 if (key->data == NULL || key->size == 0) {
167 errno = EINVAL;
168 return (RET_ERROR);
169 }
170 return (__bt_first(t, key, ep, &exact));
171 case R_FIRST: /* First record. */
172 case R_NEXT:
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)
176 return (RET_ERROR);
177
178 /* Check for an empty tree. */
179 if (NEXTINDEX(h) == 0) {
180 mpool_put(t->bt_mp, h, 0);
181 return (RET_SPECIAL);
182 }
183
184 if (h->flags & (P_BLEAF | P_RLEAF))
185 break;
186 pg = GETBINTERNAL(h, 0)->pgno;
187 mpool_put(t->bt_mp, h, 0);
188 }
189 ep->page = h;
190 ep->index = 0;
191 break;
192 case R_LAST: /* Last record. */
193 case R_PREV:
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)
197 return (RET_ERROR);
198
199 /* Check for an empty tree. */
200 if (NEXTINDEX(h) == 0) {
201 mpool_put(t->bt_mp, h, 0);
202 return (RET_SPECIAL);
203 }
204
205 if (h->flags & (P_BLEAF | P_RLEAF))
206 break;
207 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
208 mpool_put(t->bt_mp, h, 0);
209 }
210
211 ep->page = h;
212 ep->index = NEXTINDEX(h) - 1;
213 break;
214 }
215 return (RET_SUCCESS);
216 }
217
218 /*
219 * __bt_seqadvance --
220 * Advance the sequential scan.
221 *
222 * Parameters:
223 * t: tree
224 * flags: R_NEXT, R_PREV
225 *
226 * Side effects:
227 * Pins the page the new key/data record is on.
228 *
229 * Returns:
230 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
231 */
232 static int
__bt_seqadv(BTREE * t,EPG * ep,int flags)233 __bt_seqadv(BTREE *t, EPG *ep, int flags)
234 {
235 CURSOR *c;
236 PAGE *h;
237 indx_t idx;
238 pgno_t pg;
239 int exact;
240
241 /*
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.
244 */
245 c = &t->bt_cursor;
246
247 /*
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.
254 */
255 if (F_ISSET(c, CURS_ACQUIRE))
256 return (__bt_first(t, &c->key, ep, &exact));
257
258 /* Get the page referenced by the cursor. */
259 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
260 return (RET_ERROR);
261
262 /*
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.
265 */
266 switch (flags) {
267 case R_NEXT: /* Next record. */
268 /*
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.
272 */
273 if (F_ISSET(c, CURS_AFTER))
274 goto usecurrent;
275 idx = c->pg.index;
276 if (++idx == NEXTINDEX(h)) {
277 pg = h->nextpg;
278 mpool_put(t->bt_mp, h, 0);
279 if (pg == P_INVALID)
280 return (RET_SPECIAL);
281 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
282 return (RET_ERROR);
283 idx = 0;
284 }
285 break;
286 case R_PREV: /* Previous record. */
287 /*
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.
291 */
292 if (F_ISSET(c, CURS_BEFORE)) {
293 usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE);
294 ep->page = h;
295 ep->index = c->pg.index;
296 return (RET_SUCCESS);
297 }
298 idx = c->pg.index;
299 if (idx == 0) {
300 pg = h->prevpg;
301 mpool_put(t->bt_mp, h, 0);
302 if (pg == P_INVALID)
303 return (RET_SPECIAL);
304 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
305 return (RET_ERROR);
306 idx = NEXTINDEX(h) - 1;
307 } else
308 --idx;
309 break;
310 }
311
312 ep->page = h;
313 ep->index = idx;
314 return (RET_SUCCESS);
315 }
316
317 /*
318 * __bt_first --
319 * Find the first entry.
320 *
321 * Parameters:
322 * t: the tree
323 * key: the key
324 * erval: return EPG
325 * exactp: pointer to exact match flag
326 *
327 * Returns:
328 * The first entry in the tree greater than or equal to key,
329 * or RET_SPECIAL if no such key exists.
330 */
331 static int
__bt_first(BTREE * t,const DBT * key,EPG * erval,int * exactp)332 __bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp)
333 {
334 PAGE *h;
335 EPG *ep, save;
336 pgno_t pg;
337
338 /*
339 * Find any matching record; __bt_search pins the page.
340 *
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.
345 */
346 if ((ep = __bt_search(t, key, exactp)) == NULL)
347 return (0);
348 if (*exactp) {
349 if (F_ISSET(t, B_NODUPS)) {
350 *erval = *ep;
351 return (RET_SUCCESS);
352 }
353
354 /*
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
357 * we go too far.
358 */
359 save = *ep;
360 h = ep->page;
361 do {
362 if (save.page->pgno != ep->page->pgno) {
363 mpool_put(t->bt_mp, save.page, 0);
364 save = *ep;
365 } else
366 save.index = ep->index;
367
368 /*
369 * Don't unpin the page the last (or original) match
370 * was on, but make sure it's unpinned if an error
371 * occurs.
372 */
373 if (ep->index == 0) {
374 if (h->prevpg == P_INVALID)
375 break;
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)
381 mpool_put(t->bt_mp,
382 save.page, 0);
383 return (RET_ERROR);
384 }
385 ep->page = h;
386 ep->index = NEXTINDEX(h);
387 }
388 --ep->index;
389 } while (__bt_cmp(t, key, ep) == 0);
390
391 /*
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.
395 */
396 if (h->pgno != save.page->pgno)
397 mpool_put(t->bt_mp, h, 0);
398
399 *erval = save;
400 return (RET_SUCCESS);
401 }
402
403 /* If at the end of a page, find the next entry. */
404 if (ep->index == NEXTINDEX(ep->page)) {
405 h = ep->page;
406 pg = h->nextpg;
407 mpool_put(t->bt_mp, h, 0);
408 if (pg == P_INVALID)
409 return (RET_SPECIAL);
410 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
411 return (RET_ERROR);
412 ep->index = 0;
413 ep->page = h;
414 }
415 *erval = *ep;
416 return (RET_SUCCESS);
417 }
418
419 /*
420 * __bt_setcur --
421 * Set the cursor to an entry in the tree.
422 *
423 * Parameters:
424 * t: the tree
425 * pgno: page number
426 * idx: page index
427 */
428 void
__bt_setcur(BTREE * t,pgno_t pgno,u_int idx)429 __bt_setcur(BTREE *t, pgno_t pgno, u_int idx)
430 {
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;
436 }
437 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
438
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);
443 }
444