/* ![[previous]](../icons/n_left.png)
![[next]](../icons/n_right.png)
![[first]](../icons/first.png)
![[last]](../icons/last.png)
![[top]](../icons/n_top.png)
![[bottom]](../icons/bottom.png)
![[index]](../icons/index.png)
![[help]](../icons/help.png)
*/
This source file includes following definitions.
- __bt_seq
- __bt_seqset
- __bt_seqadv
- __bt_first
- __bt_setcur
1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Mike Olson.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33 #if defined(LIBC_SCCS) && !defined(lint)
34 static char sccsid[] = "@(#)bt_seq.c 8.7 (Berkeley) 7/20/94";
35 #endif /* LIBC_SCCS and not lint */
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40 #include <sys/types.h>
41
42 #include <errno.h>
43 #include <stddef.h>
44 #include <stdio.h>
45 #ifdef STDC_HEADERS
46 #include <stdlib.h>
47 #endif
48
49 #include "db.h"
50 #include "btree.h"
51
52 static int __bt_first(BTREE *, const DBT *, EPG *, int *);
53 static int __bt_seqadv(BTREE *, EPG *, int);
54 static int __bt_seqset(BTREE *, EPG *, DBT *, int);
55
56 /**
57 * @file
58 * Sequential scan support.
59 *
60 * The tree can be scanned sequentially, starting from either end of the
61 * tree or from any specific key. A scan request before any scanning is
62 * done is initialized as starting from the least node.
63 */
64
65 /**
66 * __bt_seq --
67 * Btree sequential scan interface.
68 *
69 * @param dbp pointer to access method
70 * @param key key for positioning and return value
71 * @param data data return value
72 * @param flags #R_CURSOR, #R_FIRST, #R_LAST, #R_NEXT, #R_PREV.
73 *
74 * @return
75 * #RET_ERROR, #RET_SUCCESS or #RET_SPECIAL if there's no next key.
76 */
77 int
78 __bt_seq(dbp, key, data, flags)
79 const DB *dbp;
80 DBT *key, *data;
81 u_int flags;
82 {
83 BTREE *t;
84 EPG e;
85 int status;
86
87 t = dbp->internal;
88
89 /* Toss any page pinned across calls. */
90 if (t->bt_pinned != NULL) {
91 mpool_put(t->bt_mp, t->bt_pinned, 0);
92 t->bt_pinned = NULL;
93 }
94
95 /*
96 * If scan unitialized as yet, or starting at a specific record, set
97 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin
98 * the page the cursor references if they're successful.
99 */
100 switch (flags) {
101 case R_NEXT:
102 case R_PREV:
103 if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
104 status = __bt_seqadv(t, &e, flags);
105 break;
106 }
107 /* FALLTHROUGH */
108 case R_FIRST:
109 case R_LAST:
110 case R_CURSOR:
111 status = __bt_seqset(t, &e, key, flags);
112 break;
113 default:
114 errno = EINVAL;
115 return (RET_ERROR);
116 }
117
118 if (status == RET_SUCCESS) {
119 __bt_setcur(t, e.page->pgno, e.index);
120
121 status =
122 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
123
124 /*
125 * If the user is doing concurrent access, we copied the
126 * key/data, toss the page.
127 */
128 if (F_ISSET(t, B_DB_LOCK))
129 mpool_put(t->bt_mp, e.page, 0);
130 else
131 t->bt_pinned = e.page;
132 }
133 return (status);
134 }
135
136 /**
137 * __bt_seqset --
138 * Set the sequential scan to a specific key.
139 *
140 * @param t tree
141 * @param ep storage for returned key
142 * @param key key for initial scan position
143 * @param flags #R_CURSOR, #R_FIRST, #R_LAST, #R_NEXT, #R_PREV
144 *
145 * @par Side effects:
146 * Pins the page the cursor references.
147 *
148 * @return
149 * #RET_ERROR, #RET_SUCCESS or #RET_SPECIAL if there's no next key.
150 */
151 static int
152 __bt_seqset(t, ep, key, flags)
153 BTREE *t;
154 EPG *ep;
155 DBT *key;
156 int flags;
157 {
158 PAGE *h;
159 pgno_t pg;
160 int exact;
161
162 /*
163 * Find the first, last or specific key in the tree and point the
164 * cursor at it. The cursor may not be moved until a new key has
165 * been found.
166 */
167 switch (flags) {
168 case R_CURSOR: /* Keyed scan. */
169 /*
170 * Find the first instance of the key or the smallest key
171 * which is greater than or equal to the specified key.
172 */
173 if (key->data == NULL || key->size == 0) {
174 errno = EINVAL;
175 return (RET_ERROR);
176 }
177 return (__bt_first(t, key, ep, &exact));
178 case R_FIRST: /* First record. */
179 case R_NEXT:
180 /* Walk down the left-hand side of the tree. */
181 for (pg = P_ROOT;;) {
182 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
183 return (RET_ERROR);
184
185 /* Check for an empty tree. */
186 if (NEXTINDEX(h) == 0) {
187 mpool_put(t->bt_mp, h, 0);
188 return (RET_SPECIAL);
189 }
190
191 if (h->flags & (P_BLEAF | P_RLEAF))
192 break;
193 pg = GETBINTERNAL(h, 0)->pgno;
194 mpool_put(t->bt_mp, h, 0);
195 }
196 ep->page = h;
197 ep->index = 0;
198 break;
199 case R_LAST: /* Last record. */
200 case R_PREV:
201 /* Walk down the right-hand side of the tree. */
202 for (pg = P_ROOT;;) {
203 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
204 return (RET_ERROR);
205
206 /* Check for an empty tree. */
207 if (NEXTINDEX(h) == 0) {
208 mpool_put(t->bt_mp, h, 0);
209 return (RET_SPECIAL);
210 }
211
212 if (h->flags & (P_BLEAF | P_RLEAF))
213 break;
214 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
215 mpool_put(t->bt_mp, h, 0);
216 }
217
218 ep->page = h;
219 ep->index = NEXTINDEX(h) - 1;
220 break;
221 }
222 return (RET_SUCCESS);
223 }
224
225 /**
226 * __bt_seqadvance --
227 * Advance the sequential scan.
228 *
229 * @param t tree
230 * @param ep
231 * @param flags #R_NEXT, #R_PREV
232 *
233 * @par Side effects:
234 * Pins the page the new key/data record is on.
235 *
236 * @return
237 * #RET_ERROR, #RET_SUCCESS or #RET_SPECIAL if there's no next key.
238 */
239 static int
240 __bt_seqadv(t, ep, flags)
241 BTREE *t;
242 EPG *ep;
243 int flags;
244 {
245 CURSOR *c;
246 PAGE *h;
247 indx_t index = 0;
248 pgno_t pg;
249 int exact;
250
251 /*
252 * There are a couple of states that we can be in. The cursor has
253 * been initialized by the time we get here, but that's all we know.
254 */
255 c = &t->bt_cursor;
256
257 /*
258 * The cursor was deleted where there weren't any duplicate records,
259 * so the key was saved. Find out where that key would go in the
260 * current tree. It doesn't matter if the returned key is an exact
261 * match or not -- if it's an exact match, the record was added after
262 * the delete so we can just return it. If not, as long as there's
263 * a record there, return it.
264 */
265 if (F_ISSET(c, CURS_ACQUIRE))
266 return (__bt_first(t, &c->key, ep, &exact));
267
268 /* Get the page referenced by the cursor. */
269 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
270 return (RET_ERROR);
271
272 /*
273 * Find the next/previous record in the tree and point the cursor at
274 * it. The cursor may not be moved until a new key has been found.
275 */
276 switch (flags) {
277 case R_NEXT: /* Next record. */
278 /*
279 * The cursor was deleted in duplicate records, and moved
280 * forward to a record that has yet to be returned. Clear
281 * that flag, and return the record.
282 */
283 if (F_ISSET(c, CURS_AFTER))
284 goto usecurrent;
285 index = c->pg.index;
286 if (++index == NEXTINDEX(h)) {
287 pg = h->nextpg;
288 mpool_put(t->bt_mp, h, 0);
289 if (pg == P_INVALID)
290 return (RET_SPECIAL);
291 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
292 return (RET_ERROR);
293 index = 0;
294 }
295 break;
296 case R_PREV: /* Previous record. */
297 /*
298 * The cursor was deleted in duplicate records, and moved
299 * backward to a record that has yet to be returned. Clear
300 * that flag, and return the record.
301 */
302 if (F_ISSET(c, CURS_BEFORE)) {
303 usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE);
304 ep->page = h;
305 ep->index = c->pg.index;
306 return (RET_SUCCESS);
307 }
308 index = c->pg.index;
309 if (index == 0) {
310 pg = h->prevpg;
311 mpool_put(t->bt_mp, h, 0);
312 if (pg == P_INVALID)
313 return (RET_SPECIAL);
314 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
315 return (RET_ERROR);
316 index = NEXTINDEX(h) - 1;
317 } else
318 --index;
319 break;
320 }
321
322 ep->page = h;
323 ep->index = index;
324 return (RET_SUCCESS);
325 }
326
327 /**
328 * __bt_first --
329 * Find the first entry.
330 *
331 * @param t the tree
332 * @param key the key
333 * @param erval return #EPG
334 * @param exactp pointer to exact match flag
335 *
336 * @return
337 * The first entry in the tree greater than or equal to @a key,
338 * or #RET_SPECIAL if no such key exists.
339 */
340 static int
341 __bt_first(t, key, erval, exactp)
342 BTREE *t;
343 const DBT *key;
344 EPG *erval;
345 int *exactp;
346 {
347 PAGE *h;
348 EPG *ep, save;
349 pgno_t pg;
350
351 /*
352 * Find any matching record; __bt_search pins the page.
353 *
354 * If it's an exact match and duplicates are possible, walk backwards
355 * in the tree until we find the first one. Otherwise, make sure it's
356 * a valid key (__bt_search may return an index just past the end of a
357 * page) and return it.
358 */
359 if ((ep = __bt_search(t, key, exactp)) == NULL)
360 return (0);
361 if (*exactp) {
362 if (F_ISSET(t, B_NODUPS)) {
363 *erval = *ep;
364 return (RET_SUCCESS);
365 }
366
367 /*
368 * Walk backwards, as long as the entry matches and there are
369 * keys left in the tree. Save a copy of each match in case
370 * we go too far.
371 */
372 save = *ep;
373 h = ep->page;
374 do {
375 if (save.page->pgno != ep->page->pgno) {
376 mpool_put(t->bt_mp, save.page, 0);
377 save = *ep;
378 } else
379 save.index = ep->index;
380
381 /*
382 * Don't unpin the page the last (or original) match
383 * was on, but make sure it's unpinned if an error
384 * occurs.
385 */
386 if (ep->index == 0) {
387 if (h->prevpg == P_INVALID)
388 break;
389 if (h->pgno != save.page->pgno)
390 mpool_put(t->bt_mp, h, 0);
391 if ((h = mpool_get(t->bt_mp,
392 h->prevpg, 0)) == NULL) {
393 if (h->pgno == save.page->pgno)
394 mpool_put(t->bt_mp,
395 save.page, 0);
396 return (RET_ERROR);
397 }
398 ep->page = h;
399 ep->index = NEXTINDEX(h);
400 }
401 --ep->index;
402 } while (__bt_cmp(t, key, ep) == 0);
403
404 /*
405 * Reach here with the last page that was looked at pinned,
406 * which may or may not be the same as the last (or original)
407 * match page. If it's not useful, release it.
408 */
409 if (h->pgno != save.page->pgno)
410 mpool_put(t->bt_mp, h, 0);
411
412 *erval = save;
413 return (RET_SUCCESS);
414 }
415
416 /* If at the end of a page, find the next entry. */
417 if (ep->index == NEXTINDEX(ep->page)) {
418 h = ep->page;
419 pg = h->nextpg;
420 mpool_put(t->bt_mp, h, 0);
421 if (pg == P_INVALID)
422 return (RET_SPECIAL);
423 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
424 return (RET_ERROR);
425 ep->index = 0;
426 ep->page = h;
427 }
428 *erval = *ep;
429 return (RET_SUCCESS);
430 }
431
432 /**
433 * __bt_setcur --
434 * Set the cursor to an entry in the tree.
435 *
436 * @param t the tree
437 * @param pgno page number
438 * @param index page index
439 */
440 void
441 __bt_setcur(t, pgno, index)
442 BTREE *t;
443 pgno_t pgno;
444 u_int index;
445 {
446 /* Lose any already deleted key. */
447 if (t->bt_cursor.key.data != NULL) {
448 free(t->bt_cursor.key.data);
449 t->bt_cursor.key.size = 0;
450 t->bt_cursor.key.data = NULL;
451 }
452 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
453
454 /* Update the cursor. */
455 t->bt_cursor.pg.pgno = pgno;
456 t->bt_cursor.pg.index = index;
457 F_SET(&t->bt_cursor, CURS_INIT);
458 }
/* ![[top]](../icons/top.png)
![[bottom]](../icons/n_bottom.png)
*/