17c478bd9Sstevel@tonic-gate /*-
27c478bd9Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994
37c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved.
47c478bd9Sstevel@tonic-gate *
57c478bd9Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by
67c478bd9Sstevel@tonic-gate * Mike Olson.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without
97c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions
107c478bd9Sstevel@tonic-gate * are met:
117c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright
127c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer.
137c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright
147c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the
157c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution.
167c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software
177c478bd9Sstevel@tonic-gate * must display the following acknowledgement:
187c478bd9Sstevel@tonic-gate * This product includes software developed by the University of
197c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors.
207c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors
217c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software
227c478bd9Sstevel@tonic-gate * without specific prior written permission.
237c478bd9Sstevel@tonic-gate *
247c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
257c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
267c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
277c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
287c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
297c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
307c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
317c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
327c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
337c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
347c478bd9Sstevel@tonic-gate * SUCH DAMAGE.
357c478bd9Sstevel@tonic-gate */
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate #if defined(LIBC_SCCS) && !defined(lint)
387c478bd9Sstevel@tonic-gate static char sccsid[] = "@(#)bt_search.c 8.9 (Berkeley) 10/26/95";
397c478bd9Sstevel@tonic-gate #endif /* LIBC_SCCS and not lint */
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate #include <sys/types.h>
427c478bd9Sstevel@tonic-gate
437c478bd9Sstevel@tonic-gate #include <stdio.h>
447c478bd9Sstevel@tonic-gate
457c478bd9Sstevel@tonic-gate #include "db-int.h"
467c478bd9Sstevel@tonic-gate #include "btree.h"
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
497c478bd9Sstevel@tonic-gate static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
507c478bd9Sstevel@tonic-gate
517c478bd9Sstevel@tonic-gate /*
527c478bd9Sstevel@tonic-gate * __bt_search --
537c478bd9Sstevel@tonic-gate * Search a btree for a key.
547c478bd9Sstevel@tonic-gate *
557c478bd9Sstevel@tonic-gate * Parameters:
567c478bd9Sstevel@tonic-gate * t: tree to search
577c478bd9Sstevel@tonic-gate * key: key to find
587c478bd9Sstevel@tonic-gate * exactp: pointer to exact match flag
597c478bd9Sstevel@tonic-gate *
607c478bd9Sstevel@tonic-gate * Returns:
617c478bd9Sstevel@tonic-gate * The EPG for matching record, if any, or the EPG for the location
627c478bd9Sstevel@tonic-gate * of the key, if it were inserted into the tree, is entered into
637c478bd9Sstevel@tonic-gate * the bt_cur field of the tree. A pointer to the field is returned.
647c478bd9Sstevel@tonic-gate */
657c478bd9Sstevel@tonic-gate EPG *
__bt_search(t,key,exactp)667c478bd9Sstevel@tonic-gate __bt_search(t, key, exactp)
677c478bd9Sstevel@tonic-gate BTREE *t;
687c478bd9Sstevel@tonic-gate const DBT *key;
697c478bd9Sstevel@tonic-gate int *exactp;
707c478bd9Sstevel@tonic-gate {
717c478bd9Sstevel@tonic-gate PAGE *h;
7256a424ccSmp indx_t base, idx, lim;
737c478bd9Sstevel@tonic-gate db_pgno_t pg;
747c478bd9Sstevel@tonic-gate int cmp;
757c478bd9Sstevel@tonic-gate
767c478bd9Sstevel@tonic-gate BT_CLR(t);
777c478bd9Sstevel@tonic-gate for (pg = P_ROOT;;) {
787c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
797c478bd9Sstevel@tonic-gate return (NULL);
807c478bd9Sstevel@tonic-gate
817c478bd9Sstevel@tonic-gate /* Do a binary search on the current page. */
827c478bd9Sstevel@tonic-gate t->bt_cur.page = h;
837c478bd9Sstevel@tonic-gate for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
8456a424ccSmp t->bt_cur.index = idx = base + (lim >> 1);
857c478bd9Sstevel@tonic-gate if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
867c478bd9Sstevel@tonic-gate if (h->flags & P_BLEAF) {
877c478bd9Sstevel@tonic-gate *exactp = 1;
887c478bd9Sstevel@tonic-gate return (&t->bt_cur);
897c478bd9Sstevel@tonic-gate }
907c478bd9Sstevel@tonic-gate goto next;
917c478bd9Sstevel@tonic-gate }
927c478bd9Sstevel@tonic-gate if (cmp > 0) {
9356a424ccSmp base = idx + 1;
947c478bd9Sstevel@tonic-gate --lim;
957c478bd9Sstevel@tonic-gate }
967c478bd9Sstevel@tonic-gate }
977c478bd9Sstevel@tonic-gate
987c478bd9Sstevel@tonic-gate /*
997c478bd9Sstevel@tonic-gate * If it's a leaf page, we're almost done. If no duplicates
1007c478bd9Sstevel@tonic-gate * are allowed, or we have an exact match, we're done. Else,
1017c478bd9Sstevel@tonic-gate * it's possible that there were matching keys on this page,
1027c478bd9Sstevel@tonic-gate * which later deleted, and we're on a page with no matches
1037c478bd9Sstevel@tonic-gate * while there are matches on other pages. If at the start or
1047c478bd9Sstevel@tonic-gate * end of a page, check the adjacent page.
1057c478bd9Sstevel@tonic-gate */
1067c478bd9Sstevel@tonic-gate if (h->flags & P_BLEAF) {
1077c478bd9Sstevel@tonic-gate if (!F_ISSET(t, B_NODUPS)) {
1087c478bd9Sstevel@tonic-gate if (base == 0 &&
1097c478bd9Sstevel@tonic-gate h->prevpg != P_INVALID &&
1107c478bd9Sstevel@tonic-gate __bt_sprev(t, h, key, exactp))
1117c478bd9Sstevel@tonic-gate return (&t->bt_cur);
1127c478bd9Sstevel@tonic-gate if (base == NEXTINDEX(h) &&
1137c478bd9Sstevel@tonic-gate h->nextpg != P_INVALID &&
1147c478bd9Sstevel@tonic-gate __bt_snext(t, h, key, exactp))
1157c478bd9Sstevel@tonic-gate return (&t->bt_cur);
1167c478bd9Sstevel@tonic-gate }
1177c478bd9Sstevel@tonic-gate *exactp = 0;
1187c478bd9Sstevel@tonic-gate t->bt_cur.index = base;
1197c478bd9Sstevel@tonic-gate return (&t->bt_cur);
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate
1227c478bd9Sstevel@tonic-gate /*
1237c478bd9Sstevel@tonic-gate * No match found. Base is the smallest index greater than
1247c478bd9Sstevel@tonic-gate * key and may be zero or a last + 1 index. If it's non-zero,
1257c478bd9Sstevel@tonic-gate * decrement by one, and record the internal page which should
1267c478bd9Sstevel@tonic-gate * be a parent page for the key. If a split later occurs, the
1277c478bd9Sstevel@tonic-gate * inserted page will be to the right of the saved page.
1287c478bd9Sstevel@tonic-gate */
12956a424ccSmp idx = base ? base - 1 : base;
1307c478bd9Sstevel@tonic-gate
13156a424ccSmp next: BT_PUSH(t, h->pgno, idx);
13256a424ccSmp pg = GETBINTERNAL(h, idx)->pgno;
1337c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate }
1367c478bd9Sstevel@tonic-gate
1377c478bd9Sstevel@tonic-gate /*
1387c478bd9Sstevel@tonic-gate * __bt_snext --
1397c478bd9Sstevel@tonic-gate * Check for an exact match after the key.
1407c478bd9Sstevel@tonic-gate *
1417c478bd9Sstevel@tonic-gate * Parameters:
1427c478bd9Sstevel@tonic-gate * t: tree
1437c478bd9Sstevel@tonic-gate * h: current page
1447c478bd9Sstevel@tonic-gate * key: key
1457c478bd9Sstevel@tonic-gate * exactp: pointer to exact match flag
1467c478bd9Sstevel@tonic-gate *
1477c478bd9Sstevel@tonic-gate * Returns:
1487c478bd9Sstevel@tonic-gate * If an exact match found.
1497c478bd9Sstevel@tonic-gate */
1507c478bd9Sstevel@tonic-gate static int
__bt_snext(t,h,key,exactp)1517c478bd9Sstevel@tonic-gate __bt_snext(t, h, key, exactp)
1527c478bd9Sstevel@tonic-gate BTREE *t;
1537c478bd9Sstevel@tonic-gate PAGE *h;
1547c478bd9Sstevel@tonic-gate const DBT *key;
1557c478bd9Sstevel@tonic-gate int *exactp;
1567c478bd9Sstevel@tonic-gate {
1577c478bd9Sstevel@tonic-gate BINTERNAL *bi;
1587c478bd9Sstevel@tonic-gate EPG e;
1597c478bd9Sstevel@tonic-gate EPGNO *parent;
16056a424ccSmp indx_t idx;
1617c478bd9Sstevel@tonic-gate db_pgno_t pgno;
1627c478bd9Sstevel@tonic-gate int level;
1637c478bd9Sstevel@tonic-gate
1647c478bd9Sstevel@tonic-gate /*
1657c478bd9Sstevel@tonic-gate * Get the next page. The key is either an exact
1667c478bd9Sstevel@tonic-gate * match, or not as good as the one we already have.
1677c478bd9Sstevel@tonic-gate */
1687c478bd9Sstevel@tonic-gate if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
1697c478bd9Sstevel@tonic-gate return (0);
1707c478bd9Sstevel@tonic-gate e.index = 0;
1717c478bd9Sstevel@tonic-gate if (__bt_cmp(t, key, &e) != 0) {
1727c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, e.page, 0);
1737c478bd9Sstevel@tonic-gate return (0);
1747c478bd9Sstevel@tonic-gate }
1757c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
1767c478bd9Sstevel@tonic-gate t->bt_cur = e;
1777c478bd9Sstevel@tonic-gate *exactp = 1;
1787c478bd9Sstevel@tonic-gate
1797c478bd9Sstevel@tonic-gate /*
1807c478bd9Sstevel@tonic-gate * Adjust the stack for the movement.
1817c478bd9Sstevel@tonic-gate *
1827c478bd9Sstevel@tonic-gate * Move up the stack.
1837c478bd9Sstevel@tonic-gate */
1847c478bd9Sstevel@tonic-gate for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
1857c478bd9Sstevel@tonic-gate /* Get the parent page. */
1867c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
1877c478bd9Sstevel@tonic-gate return (0);
1887c478bd9Sstevel@tonic-gate
1897c478bd9Sstevel@tonic-gate /* Move to the next index. */
1907c478bd9Sstevel@tonic-gate if (parent->index != NEXTINDEX(h) - 1) {
19156a424ccSmp idx = parent->index + 1;
19256a424ccSmp BT_PUSH(t, h->pgno, idx);
1937c478bd9Sstevel@tonic-gate break;
1947c478bd9Sstevel@tonic-gate }
1957c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
1967c478bd9Sstevel@tonic-gate }
1977c478bd9Sstevel@tonic-gate
1987c478bd9Sstevel@tonic-gate /* Restore the stack. */
1997c478bd9Sstevel@tonic-gate while (level--) {
2007c478bd9Sstevel@tonic-gate /* Push the next level down onto the stack. */
20156a424ccSmp bi = GETBINTERNAL(h, idx);
2027c478bd9Sstevel@tonic-gate pgno = bi->pgno;
2037c478bd9Sstevel@tonic-gate BT_PUSH(t, pgno, 0);
2047c478bd9Sstevel@tonic-gate
2057c478bd9Sstevel@tonic-gate /* Lose the currently pinned page. */
2067c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2077c478bd9Sstevel@tonic-gate
2087c478bd9Sstevel@tonic-gate /* Get the next level down. */
2097c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
2107c478bd9Sstevel@tonic-gate return (0);
21156a424ccSmp idx = 0;
2127c478bd9Sstevel@tonic-gate }
2137c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2147c478bd9Sstevel@tonic-gate return (1);
2157c478bd9Sstevel@tonic-gate }
2167c478bd9Sstevel@tonic-gate
2177c478bd9Sstevel@tonic-gate /*
2187c478bd9Sstevel@tonic-gate * __bt_sprev --
2197c478bd9Sstevel@tonic-gate * Check for an exact match before the key.
2207c478bd9Sstevel@tonic-gate *
2217c478bd9Sstevel@tonic-gate * Parameters:
2227c478bd9Sstevel@tonic-gate * t: tree
2237c478bd9Sstevel@tonic-gate * h: current page
2247c478bd9Sstevel@tonic-gate * key: key
2257c478bd9Sstevel@tonic-gate * exactp: pointer to exact match flag
2267c478bd9Sstevel@tonic-gate *
2277c478bd9Sstevel@tonic-gate * Returns:
2287c478bd9Sstevel@tonic-gate * If an exact match found.
2297c478bd9Sstevel@tonic-gate */
2307c478bd9Sstevel@tonic-gate static int
__bt_sprev(t,h,key,exactp)2317c478bd9Sstevel@tonic-gate __bt_sprev(t, h, key, exactp)
2327c478bd9Sstevel@tonic-gate BTREE *t;
2337c478bd9Sstevel@tonic-gate PAGE *h;
2347c478bd9Sstevel@tonic-gate const DBT *key;
2357c478bd9Sstevel@tonic-gate int *exactp;
2367c478bd9Sstevel@tonic-gate {
2377c478bd9Sstevel@tonic-gate BINTERNAL *bi;
2387c478bd9Sstevel@tonic-gate EPG e;
2397c478bd9Sstevel@tonic-gate EPGNO *parent;
24056a424ccSmp indx_t idx;
2417c478bd9Sstevel@tonic-gate db_pgno_t pgno;
2427c478bd9Sstevel@tonic-gate int level;
2437c478bd9Sstevel@tonic-gate
2447c478bd9Sstevel@tonic-gate /*
2457c478bd9Sstevel@tonic-gate * Get the previous page. The key is either an exact
2467c478bd9Sstevel@tonic-gate * match, or not as good as the one we already have.
2477c478bd9Sstevel@tonic-gate */
2487c478bd9Sstevel@tonic-gate if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
2497c478bd9Sstevel@tonic-gate return (0);
2507c478bd9Sstevel@tonic-gate e.index = NEXTINDEX(e.page) - 1;
2517c478bd9Sstevel@tonic-gate if (__bt_cmp(t, key, &e) != 0) {
2527c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, e.page, 0);
2537c478bd9Sstevel@tonic-gate return (0);
2547c478bd9Sstevel@tonic-gate }
2557c478bd9Sstevel@tonic-gate
2567c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2577c478bd9Sstevel@tonic-gate t->bt_cur = e;
2587c478bd9Sstevel@tonic-gate *exactp = 1;
2597c478bd9Sstevel@tonic-gate
2607c478bd9Sstevel@tonic-gate /*
2617c478bd9Sstevel@tonic-gate * Adjust the stack for the movement.
2627c478bd9Sstevel@tonic-gate *
2637c478bd9Sstevel@tonic-gate * Move up the stack.
2647c478bd9Sstevel@tonic-gate */
2657c478bd9Sstevel@tonic-gate for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
2667c478bd9Sstevel@tonic-gate /* Get the parent page. */
2677c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
2687c478bd9Sstevel@tonic-gate return (1);
2697c478bd9Sstevel@tonic-gate
2707c478bd9Sstevel@tonic-gate /* Move to the next index. */
2717c478bd9Sstevel@tonic-gate if (parent->index != 0) {
27256a424ccSmp idx = parent->index - 1;
27356a424ccSmp BT_PUSH(t, h->pgno, idx);
2747c478bd9Sstevel@tonic-gate break;
2757c478bd9Sstevel@tonic-gate }
2767c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2777c478bd9Sstevel@tonic-gate }
2787c478bd9Sstevel@tonic-gate
2797c478bd9Sstevel@tonic-gate /* Restore the stack. */
2807c478bd9Sstevel@tonic-gate while (level--) {
2817c478bd9Sstevel@tonic-gate /* Push the next level down onto the stack. */
28256a424ccSmp bi = GETBINTERNAL(h, idx);
2837c478bd9Sstevel@tonic-gate pgno = bi->pgno;
2847c478bd9Sstevel@tonic-gate
2857c478bd9Sstevel@tonic-gate /* Lose the currently pinned page. */
2867c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2877c478bd9Sstevel@tonic-gate
2887c478bd9Sstevel@tonic-gate /* Get the next level down. */
2897c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
2907c478bd9Sstevel@tonic-gate return (1);
2917c478bd9Sstevel@tonic-gate
29256a424ccSmp idx = NEXTINDEX(h) - 1;
29356a424ccSmp BT_PUSH(t, pgno, idx);
2947c478bd9Sstevel@tonic-gate }
2957c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, 0);
2967c478bd9Sstevel@tonic-gate return (1);
2977c478bd9Sstevel@tonic-gate }
298