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. 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.
23 *
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.
35 */
36
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)bt_search.c 8.9 (Berkeley) 10/26/95";
39 #endif /* LIBC_SCCS and not lint */
40
41 #include <sys/types.h>
42
43 #include <stdio.h>
44
45 #include "db-int.h"
46 #include "btree.h"
47
48 static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
49 static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
50
51 /*
52 * __bt_search --
53 * Search a btree for a key.
54 *
55 * Parameters:
56 * t: tree to search
57 * key: key to find
58 * exactp: pointer to exact match flag
59 *
60 * Returns:
61 * The EPG for matching record, if any, or the EPG for the location
62 * of the key, if it were inserted into the tree, is entered into
63 * the bt_cur field of the tree. A pointer to the field is returned.
64 */
65 EPG *
__bt_search(t,key,exactp)66 __bt_search(t, key, exactp)
67 BTREE *t;
68 const DBT *key;
69 int *exactp;
70 {
71 PAGE *h;
72 indx_t base, idx, lim;
73 db_pgno_t pg;
74 int cmp;
75
76 BT_CLR(t);
77 for (pg = P_ROOT;;) {
78 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
79 return (NULL);
80
81 /* Do a binary search on the current page. */
82 t->bt_cur.page = h;
83 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
84 t->bt_cur.index = idx = base + (lim >> 1);
85 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
86 if (h->flags & P_BLEAF) {
87 *exactp = 1;
88 return (&t->bt_cur);
89 }
90 goto next;
91 }
92 if (cmp > 0) {
93 base = idx + 1;
94 --lim;
95 }
96 }
97
98 /*
99 * If it's a leaf page, we're almost done. If no duplicates
100 * are allowed, or we have an exact match, we're done. Else,
101 * it's possible that there were matching keys on this page,
102 * which later deleted, and we're on a page with no matches
103 * while there are matches on other pages. If at the start or
104 * end of a page, check the adjacent page.
105 */
106 if (h->flags & P_BLEAF) {
107 if (!F_ISSET(t, B_NODUPS)) {
108 if (base == 0 &&
109 h->prevpg != P_INVALID &&
110 __bt_sprev(t, h, key, exactp))
111 return (&t->bt_cur);
112 if (base == NEXTINDEX(h) &&
113 h->nextpg != P_INVALID &&
114 __bt_snext(t, h, key, exactp))
115 return (&t->bt_cur);
116 }
117 *exactp = 0;
118 t->bt_cur.index = base;
119 return (&t->bt_cur);
120 }
121
122 /*
123 * No match found. Base is the smallest index greater than
124 * key and may be zero or a last + 1 index. If it's non-zero,
125 * decrement by one, and record the internal page which should
126 * be a parent page for the key. If a split later occurs, the
127 * inserted page will be to the right of the saved page.
128 */
129 idx = base ? base - 1 : base;
130
131 next: BT_PUSH(t, h->pgno, idx);
132 pg = GETBINTERNAL(h, idx)->pgno;
133 mpool_put(t->bt_mp, h, 0);
134 }
135 }
136
137 /*
138 * __bt_snext --
139 * Check for an exact match after the key.
140 *
141 * Parameters:
142 * t: tree
143 * h: current page
144 * key: key
145 * exactp: pointer to exact match flag
146 *
147 * Returns:
148 * If an exact match found.
149 */
150 static int
__bt_snext(t,h,key,exactp)151 __bt_snext(t, h, key, exactp)
152 BTREE *t;
153 PAGE *h;
154 const DBT *key;
155 int *exactp;
156 {
157 BINTERNAL *bi;
158 EPG e;
159 EPGNO *parent;
160 indx_t idx;
161 db_pgno_t pgno;
162 int level;
163
164 /*
165 * Get the next page. The key is either an exact
166 * match, or not as good as the one we already have.
167 */
168 if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
169 return (0);
170 e.index = 0;
171 if (__bt_cmp(t, key, &e) != 0) {
172 mpool_put(t->bt_mp, e.page, 0);
173 return (0);
174 }
175 mpool_put(t->bt_mp, h, 0);
176 t->bt_cur = e;
177 *exactp = 1;
178
179 /*
180 * Adjust the stack for the movement.
181 *
182 * Move up the stack.
183 */
184 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
185 /* Get the parent page. */
186 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
187 return (0);
188
189 /* Move to the next index. */
190 if (parent->index != NEXTINDEX(h) - 1) {
191 idx = parent->index + 1;
192 BT_PUSH(t, h->pgno, idx);
193 break;
194 }
195 mpool_put(t->bt_mp, h, 0);
196 }
197
198 /* Restore the stack. */
199 while (level--) {
200 /* Push the next level down onto the stack. */
201 bi = GETBINTERNAL(h, idx);
202 pgno = bi->pgno;
203 BT_PUSH(t, pgno, 0);
204
205 /* Lose the currently pinned page. */
206 mpool_put(t->bt_mp, h, 0);
207
208 /* Get the next level down. */
209 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
210 return (0);
211 idx = 0;
212 }
213 mpool_put(t->bt_mp, h, 0);
214 return (1);
215 }
216
217 /*
218 * __bt_sprev --
219 * Check for an exact match before the key.
220 *
221 * Parameters:
222 * t: tree
223 * h: current page
224 * key: key
225 * exactp: pointer to exact match flag
226 *
227 * Returns:
228 * If an exact match found.
229 */
230 static int
__bt_sprev(t,h,key,exactp)231 __bt_sprev(t, h, key, exactp)
232 BTREE *t;
233 PAGE *h;
234 const DBT *key;
235 int *exactp;
236 {
237 BINTERNAL *bi;
238 EPG e;
239 EPGNO *parent;
240 indx_t idx;
241 db_pgno_t pgno;
242 int level;
243
244 /*
245 * Get the previous page. The key is either an exact
246 * match, or not as good as the one we already have.
247 */
248 if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
249 return (0);
250 e.index = NEXTINDEX(e.page) - 1;
251 if (__bt_cmp(t, key, &e) != 0) {
252 mpool_put(t->bt_mp, e.page, 0);
253 return (0);
254 }
255
256 mpool_put(t->bt_mp, h, 0);
257 t->bt_cur = e;
258 *exactp = 1;
259
260 /*
261 * Adjust the stack for the movement.
262 *
263 * Move up the stack.
264 */
265 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
266 /* Get the parent page. */
267 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
268 return (1);
269
270 /* Move to the next index. */
271 if (parent->index != 0) {
272 idx = parent->index - 1;
273 BT_PUSH(t, h->pgno, idx);
274 break;
275 }
276 mpool_put(t->bt_mp, h, 0);
277 }
278
279 /* Restore the stack. */
280 while (level--) {
281 /* Push the next level down onto the stack. */
282 bi = GETBINTERNAL(h, idx);
283 pgno = bi->pgno;
284
285 /* Lose the currently pinned page. */
286 mpool_put(t->bt_mp, h, 0);
287
288 /* Get the next level down. */
289 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
290 return (1);
291
292 idx = NEXTINDEX(h) - 1;
293 BT_PUSH(t, pgno, idx);
294 }
295 mpool_put(t->bt_mp, h, 0);
296 return (1);
297 }
298