1 /* $NetBSD: bt_search.c,v 1.19 2016/09/24 21:31:25 christos Exp $ */
2
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 HAVE_NBTOOL_CONFIG_H
36 #include "nbtool_config.h"
37 #endif
38
39 #include <sys/cdefs.h>
40 __RCSID("$NetBSD: bt_search.c,v 1.19 2016/09/24 21:31:25 christos Exp $");
41
42 #include "namespace.h"
43 #include <sys/types.h>
44
45 #include <assert.h>
46 #include <stdio.h>
47
48 #include <db.h>
49 #include "btree.h"
50
51 static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
52 static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);
53
54 /*
55 * __bt_search --
56 * Search a btree for a key.
57 *
58 * Parameters:
59 * t: tree to search
60 * key: key to find
61 * exactp: pointer to exact match flag
62 *
63 * Returns:
64 * The EPG for matching record, if any, or the EPG for the location
65 * of the key, if it were inserted into the tree, is entered into
66 * the bt_cur field of the tree. A pointer to the field is returned.
67 */
68 EPG *
__bt_search(BTREE * t,const DBT * key,int * exactp)69 __bt_search(BTREE *t, const DBT *key, int *exactp)
70 {
71 PAGE *h;
72 indx_t base, idx, lim;
73 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 + ((uint32_t)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(BTREE * t,PAGE * h,const DBT * key,int * exactp)151 __bt_snext(BTREE *t, PAGE *h, const DBT *key, int *exactp)
152 {
153 BINTERNAL *bi;
154 EPG e;
155 EPGNO *parent;
156 indx_t idx = 0;
157 pgno_t pgno;
158 int level;
159
160 /*
161 * Get the next page. The key is either an exact
162 * match, or not as good as the one we already have.
163 */
164 if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
165 return 0;
166 e.index = 0;
167 if (__bt_cmp(t, key, &e) != 0) {
168 mpool_put(t->bt_mp, e.page, 0);
169 return 0;
170 }
171 mpool_put(t->bt_mp, h, 0);
172 t->bt_cur = e;
173 *exactp = 1;
174
175 /*
176 * Adjust the stack for the movement.
177 *
178 * Move up the stack.
179 */
180 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
181 /* Get the parent page. */
182 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
183 return 0;
184
185 /* Move to the next index. */
186 if (parent->index != NEXTINDEX(h) - 1) {
187 idx = parent->index + 1;
188 BT_PUSH(t, h->pgno, idx);
189 break;
190 }
191
192 mpool_put(t->bt_mp, h, 0);
193 }
194
195 /* Restore the stack. */
196 while (level--) {
197 /* Push the next level down onto the stack. */
198 bi = GETBINTERNAL(h, idx);
199 pgno = bi->pgno;
200 BT_PUSH(t, pgno, 0);
201
202 /* Lose the currently pinned page. */
203 mpool_put(t->bt_mp, h, 0);
204
205 /* Get the next level down. */
206 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
207 return 0;
208 idx = 0;
209 }
210 mpool_put(t->bt_mp, h, 0);
211 return 1;
212 }
213
214 /*
215 * __bt_sprev --
216 * Check for an exact match before the key.
217 *
218 * Parameters:
219 * t: tree
220 * h: current page
221 * key: key
222 * exactp: pointer to exact match flag
223 *
224 * Returns:
225 * If an exact match found.
226 */
227 static int
__bt_sprev(BTREE * t,PAGE * h,const DBT * key,int * exactp)228 __bt_sprev(BTREE *t, PAGE *h, const DBT *key, int *exactp)
229 {
230 BINTERNAL *bi;
231 EPG e;
232 EPGNO *parent;
233 indx_t idx = 0;
234 pgno_t pgno;
235 int level;
236
237 /*
238 * Get the previous page. The key is either an exact
239 * match, or not as good as the one we already have.
240 */
241 if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
242 return 0;
243 e.index = NEXTINDEX(e.page) - 1;
244 if (__bt_cmp(t, key, &e) != 0) {
245 mpool_put(t->bt_mp, e.page, 0);
246 return 0;
247 }
248
249 mpool_put(t->bt_mp, h, 0);
250 t->bt_cur = e;
251 *exactp = 1;
252
253 /*
254 * Adjust the stack for the movement.
255 *
256 * Move up the stack.
257 */
258 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
259 /* Get the parent page. */
260 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
261 return 1;
262
263 /* Move to the next index. */
264 if (parent->index != 0) {
265 idx = parent->index - 1;
266 BT_PUSH(t, h->pgno, idx);
267 break;
268 }
269 mpool_put(t->bt_mp, h, 0);
270 }
271
272 /* Restore the stack. */
273 while (level--) {
274 /* Push the next level down onto the stack. */
275 bi = GETBINTERNAL(h, idx);
276 pgno = bi->pgno;
277
278 /* Lose the currently pinned page. */
279 mpool_put(t->bt_mp, h, 0);
280
281 /* Get the next level down. */
282 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
283 return 1;
284
285 idx = NEXTINDEX(h) - 1;
286 BT_PUSH(t, pgno, idx);
287 }
288 mpool_put(t->bt_mp, h, 0);
289 return 1;
290 }
291