xref: /freebsd/lib/libc/db/btree/bt_seq.c (revision 8df8b2d3e51d1b816201d8a1fe8bc29fe192e562)
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
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
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
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
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
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