1*54925bf6Swillf /*-
2*54925bf6Swillf * Copyright (c) 1990, 1993, 1994
3*54925bf6Swillf * The Regents of the University of California. All rights reserved.
4*54925bf6Swillf *
5*54925bf6Swillf * This code is derived from software contributed to Berkeley by
6*54925bf6Swillf * Mike Olson.
7*54925bf6Swillf *
8*54925bf6Swillf * Redistribution and use in source and binary forms, with or without
9*54925bf6Swillf * modification, are permitted provided that the following conditions
10*54925bf6Swillf * are met:
11*54925bf6Swillf * 1. Redistributions of source code must retain the above copyright
12*54925bf6Swillf * notice, this list of conditions and the following disclaimer.
13*54925bf6Swillf * 2. Redistributions in binary form must reproduce the above copyright
14*54925bf6Swillf * notice, this list of conditions and the following disclaimer in the
15*54925bf6Swillf * documentation and/or other materials provided with the distribution.
16*54925bf6Swillf * 3. All advertising materials mentioning features or use of this software
17*54925bf6Swillf * must display the following acknowledgement:
18*54925bf6Swillf * This product includes software developed by the University of
19*54925bf6Swillf * California, Berkeley and its contributors.
20*54925bf6Swillf * 4. Neither the name of the University nor the names of its contributors
21*54925bf6Swillf * may be used to endorse or promote products derived from this software
22*54925bf6Swillf * without specific prior written permission.
23*54925bf6Swillf *
24*54925bf6Swillf * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25*54925bf6Swillf * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26*54925bf6Swillf * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27*54925bf6Swillf * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28*54925bf6Swillf * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29*54925bf6Swillf * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30*54925bf6Swillf * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31*54925bf6Swillf * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32*54925bf6Swillf * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33*54925bf6Swillf * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34*54925bf6Swillf * SUCH DAMAGE.
35*54925bf6Swillf */
36*54925bf6Swillf
37*54925bf6Swillf #if defined(LIBC_SCCS) && !defined(lint)
38*54925bf6Swillf static char sccsid[] = "@(#)bt_search.c 8.9 (Berkeley) 10/26/95";
39*54925bf6Swillf #endif /* LIBC_SCCS and not lint */
40*54925bf6Swillf
41*54925bf6Swillf #include <sys/types.h>
42*54925bf6Swillf
43*54925bf6Swillf #include <stdio.h>
44*54925bf6Swillf
45*54925bf6Swillf #include "db-int.h"
46*54925bf6Swillf #include "btree.h"
47*54925bf6Swillf
48*54925bf6Swillf static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
49*54925bf6Swillf static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
50*54925bf6Swillf
51*54925bf6Swillf /*
52*54925bf6Swillf * __bt_search --
53*54925bf6Swillf * Search a btree for a key.
54*54925bf6Swillf *
55*54925bf6Swillf * Parameters:
56*54925bf6Swillf * t: tree to search
57*54925bf6Swillf * key: key to find
58*54925bf6Swillf * exactp: pointer to exact match flag
59*54925bf6Swillf *
60*54925bf6Swillf * Returns:
61*54925bf6Swillf * The EPG for matching record, if any, or the EPG for the location
62*54925bf6Swillf * of the key, if it were inserted into the tree, is entered into
63*54925bf6Swillf * the bt_cur field of the tree. A pointer to the field is returned.
64*54925bf6Swillf */
65*54925bf6Swillf EPG *
__bt_search(t,key,exactp)66*54925bf6Swillf __bt_search(t, key, exactp)
67*54925bf6Swillf BTREE *t;
68*54925bf6Swillf const DBT *key;
69*54925bf6Swillf int *exactp;
70*54925bf6Swillf {
71*54925bf6Swillf PAGE *h;
72*54925bf6Swillf indx_t base, idx, lim;
73*54925bf6Swillf db_pgno_t pg;
74*54925bf6Swillf int cmp;
75*54925bf6Swillf
76*54925bf6Swillf BT_CLR(t);
77*54925bf6Swillf for (pg = P_ROOT;;) {
78*54925bf6Swillf if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
79*54925bf6Swillf return (NULL);
80*54925bf6Swillf
81*54925bf6Swillf /* Do a binary search on the current page. */
82*54925bf6Swillf t->bt_cur.page = h;
83*54925bf6Swillf for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
84*54925bf6Swillf t->bt_cur.index = idx = base + (lim >> 1);
85*54925bf6Swillf if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
86*54925bf6Swillf if (h->flags & P_BLEAF) {
87*54925bf6Swillf *exactp = 1;
88*54925bf6Swillf return (&t->bt_cur);
89*54925bf6Swillf }
90*54925bf6Swillf goto next;
91*54925bf6Swillf }
92*54925bf6Swillf if (cmp > 0) {
93*54925bf6Swillf base = idx + 1;
94*54925bf6Swillf --lim;
95*54925bf6Swillf }
96*54925bf6Swillf }
97*54925bf6Swillf
98*54925bf6Swillf /*
99*54925bf6Swillf * If it's a leaf page, we're almost done. If no duplicates
100*54925bf6Swillf * are allowed, or we have an exact match, we're done. Else,
101*54925bf6Swillf * it's possible that there were matching keys on this page,
102*54925bf6Swillf * which later deleted, and we're on a page with no matches
103*54925bf6Swillf * while there are matches on other pages. If at the start or
104*54925bf6Swillf * end of a page, check the adjacent page.
105*54925bf6Swillf */
106*54925bf6Swillf if (h->flags & P_BLEAF) {
107*54925bf6Swillf if (!F_ISSET(t, B_NODUPS)) {
108*54925bf6Swillf if (base == 0 &&
109*54925bf6Swillf h->prevpg != P_INVALID &&
110*54925bf6Swillf __bt_sprev(t, h, key, exactp))
111*54925bf6Swillf return (&t->bt_cur);
112*54925bf6Swillf if (base == NEXTINDEX(h) &&
113*54925bf6Swillf h->nextpg != P_INVALID &&
114*54925bf6Swillf __bt_snext(t, h, key, exactp))
115*54925bf6Swillf return (&t->bt_cur);
116*54925bf6Swillf }
117*54925bf6Swillf *exactp = 0;
118*54925bf6Swillf t->bt_cur.index = base;
119*54925bf6Swillf return (&t->bt_cur);
120*54925bf6Swillf }
121*54925bf6Swillf
122*54925bf6Swillf /*
123*54925bf6Swillf * No match found. Base is the smallest index greater than
124*54925bf6Swillf * key and may be zero or a last + 1 index. If it's non-zero,
125*54925bf6Swillf * decrement by one, and record the internal page which should
126*54925bf6Swillf * be a parent page for the key. If a split later occurs, the
127*54925bf6Swillf * inserted page will be to the right of the saved page.
128*54925bf6Swillf */
129*54925bf6Swillf idx = base ? base - 1 : base;
130*54925bf6Swillf
131*54925bf6Swillf next: BT_PUSH(t, h->pgno, idx);
132*54925bf6Swillf pg = GETBINTERNAL(h, idx)->pgno;
133*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
134*54925bf6Swillf }
135*54925bf6Swillf }
136*54925bf6Swillf
137*54925bf6Swillf /*
138*54925bf6Swillf * __bt_snext --
139*54925bf6Swillf * Check for an exact match after the key.
140*54925bf6Swillf *
141*54925bf6Swillf * Parameters:
142*54925bf6Swillf * t: tree
143*54925bf6Swillf * h: current page
144*54925bf6Swillf * key: key
145*54925bf6Swillf * exactp: pointer to exact match flag
146*54925bf6Swillf *
147*54925bf6Swillf * Returns:
148*54925bf6Swillf * If an exact match found.
149*54925bf6Swillf */
150*54925bf6Swillf static int
__bt_snext(t,h,key,exactp)151*54925bf6Swillf __bt_snext(t, h, key, exactp)
152*54925bf6Swillf BTREE *t;
153*54925bf6Swillf PAGE *h;
154*54925bf6Swillf const DBT *key;
155*54925bf6Swillf int *exactp;
156*54925bf6Swillf {
157*54925bf6Swillf BINTERNAL *bi;
158*54925bf6Swillf EPG e;
159*54925bf6Swillf EPGNO *parent;
160*54925bf6Swillf indx_t idx;
161*54925bf6Swillf db_pgno_t pgno;
162*54925bf6Swillf int level;
163*54925bf6Swillf
164*54925bf6Swillf /*
165*54925bf6Swillf * Get the next page. The key is either an exact
166*54925bf6Swillf * match, or not as good as the one we already have.
167*54925bf6Swillf */
168*54925bf6Swillf if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
169*54925bf6Swillf return (0);
170*54925bf6Swillf e.index = 0;
171*54925bf6Swillf if (__bt_cmp(t, key, &e) != 0) {
172*54925bf6Swillf mpool_put(t->bt_mp, e.page, 0);
173*54925bf6Swillf return (0);
174*54925bf6Swillf }
175*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
176*54925bf6Swillf t->bt_cur = e;
177*54925bf6Swillf *exactp = 1;
178*54925bf6Swillf
179*54925bf6Swillf /*
180*54925bf6Swillf * Adjust the stack for the movement.
181*54925bf6Swillf *
182*54925bf6Swillf * Move up the stack.
183*54925bf6Swillf */
184*54925bf6Swillf for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
185*54925bf6Swillf /* Get the parent page. */
186*54925bf6Swillf if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
187*54925bf6Swillf return (0);
188*54925bf6Swillf
189*54925bf6Swillf /* Move to the next index. */
190*54925bf6Swillf if (parent->index != NEXTINDEX(h) - 1) {
191*54925bf6Swillf idx = parent->index + 1;
192*54925bf6Swillf BT_PUSH(t, h->pgno, idx);
193*54925bf6Swillf break;
194*54925bf6Swillf }
195*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
196*54925bf6Swillf }
197*54925bf6Swillf
198*54925bf6Swillf /* Restore the stack. */
199*54925bf6Swillf while (level--) {
200*54925bf6Swillf /* Push the next level down onto the stack. */
201*54925bf6Swillf bi = GETBINTERNAL(h, idx);
202*54925bf6Swillf pgno = bi->pgno;
203*54925bf6Swillf BT_PUSH(t, pgno, 0);
204*54925bf6Swillf
205*54925bf6Swillf /* Lose the currently pinned page. */
206*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
207*54925bf6Swillf
208*54925bf6Swillf /* Get the next level down. */
209*54925bf6Swillf if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
210*54925bf6Swillf return (0);
211*54925bf6Swillf idx = 0;
212*54925bf6Swillf }
213*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
214*54925bf6Swillf return (1);
215*54925bf6Swillf }
216*54925bf6Swillf
217*54925bf6Swillf /*
218*54925bf6Swillf * __bt_sprev --
219*54925bf6Swillf * Check for an exact match before the key.
220*54925bf6Swillf *
221*54925bf6Swillf * Parameters:
222*54925bf6Swillf * t: tree
223*54925bf6Swillf * h: current page
224*54925bf6Swillf * key: key
225*54925bf6Swillf * exactp: pointer to exact match flag
226*54925bf6Swillf *
227*54925bf6Swillf * Returns:
228*54925bf6Swillf * If an exact match found.
229*54925bf6Swillf */
230*54925bf6Swillf static int
__bt_sprev(t,h,key,exactp)231*54925bf6Swillf __bt_sprev(t, h, key, exactp)
232*54925bf6Swillf BTREE *t;
233*54925bf6Swillf PAGE *h;
234*54925bf6Swillf const DBT *key;
235*54925bf6Swillf int *exactp;
236*54925bf6Swillf {
237*54925bf6Swillf BINTERNAL *bi;
238*54925bf6Swillf EPG e;
239*54925bf6Swillf EPGNO *parent;
240*54925bf6Swillf indx_t idx;
241*54925bf6Swillf db_pgno_t pgno;
242*54925bf6Swillf int level;
243*54925bf6Swillf
244*54925bf6Swillf /*
245*54925bf6Swillf * Get the previous page. The key is either an exact
246*54925bf6Swillf * match, or not as good as the one we already have.
247*54925bf6Swillf */
248*54925bf6Swillf if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
249*54925bf6Swillf return (0);
250*54925bf6Swillf e.index = NEXTINDEX(e.page) - 1;
251*54925bf6Swillf if (__bt_cmp(t, key, &e) != 0) {
252*54925bf6Swillf mpool_put(t->bt_mp, e.page, 0);
253*54925bf6Swillf return (0);
254*54925bf6Swillf }
255*54925bf6Swillf
256*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
257*54925bf6Swillf t->bt_cur = e;
258*54925bf6Swillf *exactp = 1;
259*54925bf6Swillf
260*54925bf6Swillf /*
261*54925bf6Swillf * Adjust the stack for the movement.
262*54925bf6Swillf *
263*54925bf6Swillf * Move up the stack.
264*54925bf6Swillf */
265*54925bf6Swillf for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
266*54925bf6Swillf /* Get the parent page. */
267*54925bf6Swillf if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
268*54925bf6Swillf return (1);
269*54925bf6Swillf
270*54925bf6Swillf /* Move to the next index. */
271*54925bf6Swillf if (parent->index != 0) {
272*54925bf6Swillf idx = parent->index - 1;
273*54925bf6Swillf BT_PUSH(t, h->pgno, idx);
274*54925bf6Swillf break;
275*54925bf6Swillf }
276*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
277*54925bf6Swillf }
278*54925bf6Swillf
279*54925bf6Swillf /* Restore the stack. */
280*54925bf6Swillf while (level--) {
281*54925bf6Swillf /* Push the next level down onto the stack. */
282*54925bf6Swillf bi = GETBINTERNAL(h, idx);
283*54925bf6Swillf pgno = bi->pgno;
284*54925bf6Swillf
285*54925bf6Swillf /* Lose the currently pinned page. */
286*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
287*54925bf6Swillf
288*54925bf6Swillf /* Get the next level down. */
289*54925bf6Swillf if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
290*54925bf6Swillf return (1);
291*54925bf6Swillf
292*54925bf6Swillf idx = NEXTINDEX(h) - 1;
293*54925bf6Swillf BT_PUSH(t, pgno, idx);
294*54925bf6Swillf }
295*54925bf6Swillf mpool_put(t->bt_mp, h, 0);
296*54925bf6Swillf return (1);
297*54925bf6Swillf }
298