Update.
[glibc.git] / db / btree / bt_seq.c
blob90f896036f5cd55ef822de0bc03cd77e820e9c6e
1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
6 * Mike Olson.
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. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)bt_seq.c 8.7 (Berkeley) 7/20/94";
39 #endif /* LIBC_SCCS and not lint */
41 #include <sys/types.h>
43 #include <errno.h>
44 #include <stddef.h>
45 #include <stdio.h>
46 #include <stdlib.h>
48 #include <db.h>
49 #include "btree.h"
51 static int __bt_first __P((BTREE *, const DBT *, EPG *, int *));
52 static int __bt_seqadv __P((BTREE *, EPG *, int));
53 static int __bt_seqset __P((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.
64 * __bt_seq --
65 * Btree sequential scan interface.
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.
73 * Returns:
74 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
76 int
77 __bt_seq(dbp, key, data, flags)
78 const DB *dbp;
79 DBT *key, *data;
80 u_int flags;
82 BTREE *t;
83 EPG e;
84 int status;
86 t = dbp->internal;
88 /* Toss any page pinned across calls. */
89 if (t->bt_pinned != NULL) {
90 mpool_put(t->bt_mp, t->bt_pinned, 0);
91 t->bt_pinned = NULL;
95 * If scan uninitialized as yet, or starting at a specific record, set
96 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin
97 * the page the cursor references if they're successful.
99 switch (flags) {
100 case R_NEXT:
101 case R_PREV:
102 if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
103 status = __bt_seqadv(t, &e, flags);
104 break;
106 /* FALLTHROUGH */
107 case R_FIRST:
108 case R_LAST:
109 case R_CURSOR:
110 status = __bt_seqset(t, &e, key, flags);
111 break;
112 default:
113 errno = EINVAL;
114 return (RET_ERROR);
117 if (status == RET_SUCCESS) {
118 __bt_setcur(t, e.page->pgno, e.index);
120 status =
121 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
124 * If the user is doing concurrent access, we copied the
125 * key/data, toss the page.
127 if (F_ISSET(t, B_DB_LOCK))
128 mpool_put(t->bt_mp, e.page, 0);
129 else
130 t->bt_pinned = e.page;
132 return (status);
136 * __bt_seqset --
137 * Set the sequential scan to a specific key.
139 * Parameters:
140 * t: tree
141 * ep: storage for returned key
142 * key: key for initial scan position
143 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
145 * Side effects:
146 * Pins the page the cursor references.
148 * Returns:
149 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
151 static int
152 __bt_seqset(t, ep, key, flags)
153 BTREE *t;
154 EPG *ep;
155 DBT *key;
156 int flags;
158 PAGE *h;
159 pgno_t pg;
160 int exact;
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.
167 switch (flags) {
168 case R_CURSOR: /* Keyed scan. */
170 * Find the first instance of the key or the smallest key
171 * which is greater than or equal to the specified key.
173 if (key->data == NULL || key->size == 0) {
174 errno = EINVAL;
175 return (RET_ERROR);
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);
185 /* Check for an empty tree. */
186 if (NEXTINDEX(h) == 0) {
187 mpool_put(t->bt_mp, h, 0);
188 return (RET_SPECIAL);
191 if (h->flags & (P_BLEAF | P_RLEAF))
192 break;
193 pg = GETBINTERNAL(h, 0)->pgno;
194 mpool_put(t->bt_mp, h, 0);
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);
206 /* Check for an empty tree. */
207 if (NEXTINDEX(h) == 0) {
208 mpool_put(t->bt_mp, h, 0);
209 return (RET_SPECIAL);
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);
218 ep->page = h;
219 ep->index = NEXTINDEX(h) - 1;
220 break;
222 return (RET_SUCCESS);
226 * __bt_seqadvance --
227 * Advance the sequential scan.
229 * Parameters:
230 * t: tree
231 * flags: R_NEXT, R_PREV
233 * Side effects:
234 * Pins the page the new key/data record is on.
236 * Returns:
237 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
239 static int
240 __bt_seqadv(t, ep, flags)
241 BTREE *t;
242 EPG *ep;
243 int flags;
245 CURSOR *c;
246 PAGE *h;
247 indx_t index;
248 pgno_t pg;
249 int exact;
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.
255 c = &t->bt_cursor;
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.
265 if (F_ISSET(c, CURS_ACQUIRE))
266 return (__bt_first(t, &c->key, ep, &exact));
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);
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.
276 switch (flags) {
277 case R_NEXT: /* Next record. */
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.
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;
295 break;
296 case R_PREV: /* Previous record. */
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.
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);
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;
322 ep->page = h;
323 ep->index = index;
324 return (RET_SUCCESS);
328 * __bt_first --
329 * Find the first entry.
331 * Parameters:
332 * t: the tree
333 * key: the key
334 * erval: return EPG
335 * exactp: pointer to exact match flag
337 * Returns:
338 * The first entry in the tree greater than or equal to key,
339 * or RET_SPECIAL if no such key exists.
341 static int
342 __bt_first(t, key, erval, exactp)
343 BTREE *t;
344 const DBT *key;
345 EPG *erval;
346 int *exactp;
348 PAGE *h;
349 EPG *ep, save;
350 pgno_t pg;
353 * Find any matching record; __bt_search pins the page.
355 * If it's an exact match and duplicates are possible, walk backwards
356 * in the tree until we find the first one. Otherwise, make sure it's
357 * a valid key (__bt_search may return an index just past the end of a
358 * page) and return it.
360 if ((ep = __bt_search(t, key, exactp)) == NULL)
361 return (RET_SPECIAL);
362 if (*exactp) {
363 if (F_ISSET(t, B_NODUPS)) {
364 *erval = *ep;
365 return (RET_SUCCESS);
369 * Walk backwards, as long as the entry matches and there are
370 * keys left in the tree. Save a copy of each match in case
371 * we go too far.
373 save = *ep;
374 h = ep->page;
375 do {
376 if (save.page->pgno != ep->page->pgno) {
377 mpool_put(t->bt_mp, save.page, 0);
378 save = *ep;
379 } else
380 save.index = ep->index;
383 * Don't unpin the page the last (or original) match
384 * was on, but make sure it's unpinned if an error
385 * occurs.
387 if (ep->index == 0) {
388 if (h->prevpg == P_INVALID)
389 break;
390 if (h->pgno != save.page->pgno)
391 mpool_put(t->bt_mp, h, 0);
392 if ((h = mpool_get(t->bt_mp,
393 h->prevpg, 0)) == NULL) {
394 if (h->pgno == save.page->pgno)
395 mpool_put(t->bt_mp,
396 save.page, 0);
397 return (RET_ERROR);
399 ep->page = h;
400 ep->index = NEXTINDEX(h);
402 --ep->index;
403 } while (__bt_cmp(t, key, ep) == 0);
406 * Reach here with the last page that was looked at pinned,
407 * which may or may not be the same as the last (or original)
408 * match page. If it's not useful, release it.
410 if (h->pgno != save.page->pgno)
411 mpool_put(t->bt_mp, h, 0);
413 *erval = save;
414 return (RET_SUCCESS);
417 /* If at the end of a page, find the next entry. */
418 if (ep->index == NEXTINDEX(ep->page)) {
419 h = ep->page;
420 pg = h->nextpg;
421 mpool_put(t->bt_mp, h, 0);
422 if (pg == P_INVALID)
423 return (RET_SPECIAL);
424 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
425 return (RET_ERROR);
426 ep->index = 0;
427 ep->page = h;
429 *erval = *ep;
430 return (RET_SUCCESS);
434 * __bt_setcur --
435 * Set the cursor to an entry in the tree.
437 * Parameters:
438 * t: the tree
439 * pgno: page number
440 * index: page index
442 void
443 __bt_setcur(t, pgno, index)
444 BTREE *t;
445 pgno_t pgno;
446 u_int index;
448 /* Lose any already deleted key. */
449 if (t->bt_cursor.key.data != NULL) {
450 free(t->bt_cursor.key.data);
451 t->bt_cursor.key.size = 0;
452 t->bt_cursor.key.data = NULL;
454 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
456 /* Update the cursor. */
457 t->bt_cursor.pg.pgno = pgno;
458 t->bt_cursor.pg.index = index;
459 F_SET(&t->bt_cursor, CURS_INIT);