1*5da14d93Schristos /* $NetBSD: bt_search.c,v 1.19 2016/09/24 21:31:25 christos Exp $ */
2a954b078Scgd
39f0aa214Scgd /*-
424420c01Scgd * Copyright (c) 1990, 1993, 1994
59f0aa214Scgd * The Regents of the University of California. All rights reserved.
69f0aa214Scgd *
79f0aa214Scgd * This code is derived from software contributed to Berkeley by
89f0aa214Scgd * Mike Olson.
99f0aa214Scgd *
109f0aa214Scgd * Redistribution and use in source and binary forms, with or without
119f0aa214Scgd * modification, are permitted provided that the following conditions
129f0aa214Scgd * are met:
139f0aa214Scgd * 1. Redistributions of source code must retain the above copyright
149f0aa214Scgd * notice, this list of conditions and the following disclaimer.
159f0aa214Scgd * 2. Redistributions in binary form must reproduce the above copyright
169f0aa214Scgd * notice, this list of conditions and the following disclaimer in the
179f0aa214Scgd * documentation and/or other materials provided with the distribution.
18eb7c1594Sagc * 3. Neither the name of the University nor the names of its contributors
199f0aa214Scgd * may be used to endorse or promote products derived from this software
209f0aa214Scgd * without specific prior written permission.
219f0aa214Scgd *
229f0aa214Scgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
239f0aa214Scgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
249f0aa214Scgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
259f0aa214Scgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
269f0aa214Scgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
279f0aa214Scgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
289f0aa214Scgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
299f0aa214Scgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
309f0aa214Scgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
319f0aa214Scgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
329f0aa214Scgd * SUCH DAMAGE.
339f0aa214Scgd */
349f0aa214Scgd
35d3595ddfSjoerg #if HAVE_NBTOOL_CONFIG_H
36d3595ddfSjoerg #include "nbtool_config.h"
37d3595ddfSjoerg #endif
38d3595ddfSjoerg
3900ae392dSchristos #include <sys/cdefs.h>
40*5da14d93Schristos __RCSID("$NetBSD: bt_search.c,v 1.19 2016/09/24 21:31:25 christos Exp $");
419f0aa214Scgd
4243fa6fe3Sjtc #include "namespace.h"
439f0aa214Scgd #include <sys/types.h>
449f0aa214Scgd
45cb9daf8fSchristos #include <assert.h>
469f0aa214Scgd #include <stdio.h>
479f0aa214Scgd
489f0aa214Scgd #include <db.h>
499f0aa214Scgd #include "btree.h"
509f0aa214Scgd
51cb9daf8fSchristos static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
52cb9daf8fSchristos static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);
53f7b4cb00Scgd
549f0aa214Scgd /*
5524420c01Scgd * __bt_search --
5624420c01Scgd * Search a btree for a key.
579f0aa214Scgd *
589f0aa214Scgd * Parameters:
599f0aa214Scgd * t: tree to search
609f0aa214Scgd * key: key to find
619f0aa214Scgd * exactp: pointer to exact match flag
629f0aa214Scgd *
639f0aa214Scgd * Returns:
6465aeeefbScgd * The EPG for matching record, if any, or the EPG for the location
6565aeeefbScgd * of the key, if it were inserted into the tree, is entered into
6665aeeefbScgd * the bt_cur field of the tree. A pointer to the field is returned.
679f0aa214Scgd */
689f0aa214Scgd EPG *
__bt_search(BTREE * t,const DBT * key,int * exactp)69cb9daf8fSchristos __bt_search(BTREE *t, const DBT *key, int *exactp)
709f0aa214Scgd {
71a6d14e36Scgd PAGE *h;
7242a6d413Sthorpej indx_t base, idx, lim;
739f0aa214Scgd pgno_t pg;
74a6d14e36Scgd int cmp;
759f0aa214Scgd
769f0aa214Scgd BT_CLR(t);
779f0aa214Scgd for (pg = P_ROOT;;) {
78*5da14d93Schristos if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
799f0aa214Scgd return (NULL);
809f0aa214Scgd
819f0aa214Scgd /* Do a binary search on the current page. */
8265aeeefbScgd t->bt_cur.page = h;
839f0aa214Scgd for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
8440b37a3bSjoerg t->bt_cur.index = idx = base + ((uint32_t)lim >> 1);
8565aeeefbScgd if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
869f0aa214Scgd if (h->flags & P_BLEAF) {
879f0aa214Scgd *exactp = 1;
8865aeeefbScgd return (&t->bt_cur);
899f0aa214Scgd }
909f0aa214Scgd goto next;
919f0aa214Scgd }
929f0aa214Scgd if (cmp > 0) {
9342a6d413Sthorpej base = idx + 1;
949f0aa214Scgd --lim;
959f0aa214Scgd }
969f0aa214Scgd }
979f0aa214Scgd
98f7b4cb00Scgd /*
9924420c01Scgd * If it's a leaf page, we're almost done. If no duplicates
10024420c01Scgd * are allowed, or we have an exact match, we're done. Else,
10124420c01Scgd * it's possible that there were matching keys on this page,
10224420c01Scgd * which later deleted, and we're on a page with no matches
10324420c01Scgd * while there are matches on other pages. If at the start or
10424420c01Scgd * end of a page, check the adjacent page.
105f7b4cb00Scgd */
1069f0aa214Scgd if (h->flags & P_BLEAF) {
10724420c01Scgd if (!F_ISSET(t, B_NODUPS)) {
108f7b4cb00Scgd if (base == 0 &&
10924420c01Scgd h->prevpg != P_INVALID &&
11024420c01Scgd __bt_sprev(t, h, key, exactp))
111f7b4cb00Scgd return (&t->bt_cur);
112f7b4cb00Scgd if (base == NEXTINDEX(h) &&
11324420c01Scgd h->nextpg != P_INVALID &&
11424420c01Scgd __bt_snext(t, h, key, exactp))
115f7b4cb00Scgd return (&t->bt_cur);
116f7b4cb00Scgd }
11724420c01Scgd *exactp = 0;
11824420c01Scgd t->bt_cur.index = base;
11965aeeefbScgd return (&t->bt_cur);
1209f0aa214Scgd }
1219f0aa214Scgd
1229f0aa214Scgd /*
1239f0aa214Scgd * No match found. Base is the smallest index greater than
1249f0aa214Scgd * key and may be zero or a last + 1 index. If it's non-zero,
1259f0aa214Scgd * decrement by one, and record the internal page which should
1269f0aa214Scgd * be a parent page for the key. If a split later occurs, the
1279f0aa214Scgd * inserted page will be to the right of the saved page.
1289f0aa214Scgd */
12942a6d413Sthorpej idx = base ? base - 1 : base;
1309f0aa214Scgd
13142a6d413Sthorpej next: BT_PUSH(t, h->pgno, idx);
13242a6d413Sthorpej pg = GETBINTERNAL(h, idx)->pgno;
1339f0aa214Scgd mpool_put(t->bt_mp, h, 0);
1349f0aa214Scgd }
1359f0aa214Scgd }
136f7b4cb00Scgd
137f7b4cb00Scgd /*
13824420c01Scgd * __bt_snext --
13924420c01Scgd * Check for an exact match after the key.
140f7b4cb00Scgd *
141f7b4cb00Scgd * Parameters:
14224420c01Scgd * t: tree
14324420c01Scgd * h: current page
14424420c01Scgd * key: key
145f7b4cb00Scgd * exactp: pointer to exact match flag
146f7b4cb00Scgd *
147f7b4cb00Scgd * Returns:
148f7b4cb00Scgd * If an exact match found.
149f7b4cb00Scgd */
150f7b4cb00Scgd static int
__bt_snext(BTREE * t,PAGE * h,const DBT * key,int * exactp)151cb9daf8fSchristos __bt_snext(BTREE *t, PAGE *h, const DBT *key, int *exactp)
152f7b4cb00Scgd {
153a75949abSchristos BINTERNAL *bi;
154f7b4cb00Scgd EPG e;
155a75949abSchristos EPGNO *parent;
156a75949abSchristos indx_t idx = 0;
157a75949abSchristos pgno_t pgno;
158a75949abSchristos int level;
159f7b4cb00Scgd
160f7b4cb00Scgd /*
16124420c01Scgd * Get the next page. The key is either an exact
16224420c01Scgd * match, or not as good as the one we already have.
163f7b4cb00Scgd */
164*5da14d93Schristos if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
165a75949abSchristos return 0;
16624420c01Scgd e.index = 0;
167a75949abSchristos if (__bt_cmp(t, key, &e) != 0) {
168a75949abSchristos mpool_put(t->bt_mp, e.page, 0);
169a75949abSchristos return 0;
170a75949abSchristos }
171f7b4cb00Scgd mpool_put(t->bt_mp, h, 0);
172f7b4cb00Scgd t->bt_cur = e;
173f7b4cb00Scgd *exactp = 1;
174a75949abSchristos
175a75949abSchristos /*
176a75949abSchristos * Adjust the stack for the movement.
177a75949abSchristos *
178a75949abSchristos * Move up the stack.
179a75949abSchristos */
180a75949abSchristos for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
181a75949abSchristos /* Get the parent page. */
182*5da14d93Schristos if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
183a75949abSchristos return 0;
184a75949abSchristos
185a75949abSchristos /* Move to the next index. */
186a75949abSchristos if (parent->index != NEXTINDEX(h) - 1) {
187a75949abSchristos idx = parent->index + 1;
188a75949abSchristos BT_PUSH(t, h->pgno, idx);
189a75949abSchristos break;
190f7b4cb00Scgd }
191a75949abSchristos
192a75949abSchristos mpool_put(t->bt_mp, h, 0);
193a75949abSchristos }
194a75949abSchristos
195a75949abSchristos /* Restore the stack. */
196a75949abSchristos while (level--) {
197a75949abSchristos /* Push the next level down onto the stack. */
198a75949abSchristos bi = GETBINTERNAL(h, idx);
199a75949abSchristos pgno = bi->pgno;
200a75949abSchristos BT_PUSH(t, pgno, 0);
201a75949abSchristos
202a75949abSchristos /* Lose the currently pinned page. */
203a75949abSchristos mpool_put(t->bt_mp, h, 0);
204a75949abSchristos
205a75949abSchristos /* Get the next level down. */
206*5da14d93Schristos if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
207a75949abSchristos return 0;
208a75949abSchristos idx = 0;
209a75949abSchristos }
210a75949abSchristos mpool_put(t->bt_mp, h, 0);
211a75949abSchristos return 1;
212f7b4cb00Scgd }
213f7b4cb00Scgd
214f7b4cb00Scgd /*
21524420c01Scgd * __bt_sprev --
21624420c01Scgd * Check for an exact match before the key.
217f7b4cb00Scgd *
218f7b4cb00Scgd * Parameters:
21924420c01Scgd * t: tree
22024420c01Scgd * h: current page
22124420c01Scgd * key: key
222f7b4cb00Scgd * exactp: pointer to exact match flag
223f7b4cb00Scgd *
224f7b4cb00Scgd * Returns:
225f7b4cb00Scgd * If an exact match found.
226f7b4cb00Scgd */
227f7b4cb00Scgd static int
__bt_sprev(BTREE * t,PAGE * h,const DBT * key,int * exactp)228cb9daf8fSchristos __bt_sprev(BTREE *t, PAGE *h, const DBT *key, int *exactp)
229f7b4cb00Scgd {
230a75949abSchristos BINTERNAL *bi;
231f7b4cb00Scgd EPG e;
232a75949abSchristos EPGNO *parent;
233a75949abSchristos indx_t idx = 0;
234a75949abSchristos pgno_t pgno;
235a75949abSchristos int level;
236f7b4cb00Scgd
237f7b4cb00Scgd /*
23824420c01Scgd * Get the previous page. The key is either an exact
23924420c01Scgd * match, or not as good as the one we already have.
240f7b4cb00Scgd */
241*5da14d93Schristos if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
242a75949abSchristos return 0;
24324420c01Scgd e.index = NEXTINDEX(e.page) - 1;
244a75949abSchristos if (__bt_cmp(t, key, &e) != 0) {
245a75949abSchristos mpool_put(t->bt_mp, e.page, 0);
246a75949abSchristos return 0;
247a75949abSchristos }
248a75949abSchristos
249f7b4cb00Scgd mpool_put(t->bt_mp, h, 0);
250f7b4cb00Scgd t->bt_cur = e;
251f7b4cb00Scgd *exactp = 1;
252a75949abSchristos
253a75949abSchristos /*
254a75949abSchristos * Adjust the stack for the movement.
255a75949abSchristos *
256a75949abSchristos * Move up the stack.
257a75949abSchristos */
258a75949abSchristos for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
259a75949abSchristos /* Get the parent page. */
260*5da14d93Schristos if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
261a75949abSchristos return 1;
262a75949abSchristos
263a75949abSchristos /* Move to the next index. */
264a75949abSchristos if (parent->index != 0) {
265a75949abSchristos idx = parent->index - 1;
266a75949abSchristos BT_PUSH(t, h->pgno, idx);
267a75949abSchristos break;
268f7b4cb00Scgd }
269a75949abSchristos mpool_put(t->bt_mp, h, 0);
270a75949abSchristos }
271a75949abSchristos
272a75949abSchristos /* Restore the stack. */
273a75949abSchristos while (level--) {
274a75949abSchristos /* Push the next level down onto the stack. */
275a75949abSchristos bi = GETBINTERNAL(h, idx);
276a75949abSchristos pgno = bi->pgno;
277a75949abSchristos
278a75949abSchristos /* Lose the currently pinned page. */
279a75949abSchristos mpool_put(t->bt_mp, h, 0);
280a75949abSchristos
281a75949abSchristos /* Get the next level down. */
282*5da14d93Schristos if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
283a75949abSchristos return 1;
284a75949abSchristos
285a75949abSchristos idx = NEXTINDEX(h) - 1;
286a75949abSchristos BT_PUSH(t, pgno, idx);
287a75949abSchristos }
288a75949abSchristos mpool_put(t->bt_mp, h, 0);
289a75949abSchristos return 1;
290f7b4cb00Scgd }
291