1 /* $NetBSD: bt_search.c,v 1.17 2008/09/11 12:58:00 joerg 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.17 2008/09/11 12:58:00 joerg 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 EPG e;
154
155 /*
156 * Get the next page. The key is either an exact
157 * match, or not as good as the one we already have.
158 */
159 if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
160 return (0);
161 e.index = 0;
162 if (__bt_cmp(t, key, &e) == 0) {
163 mpool_put(t->bt_mp, h, 0);
164 t->bt_cur = e;
165 *exactp = 1;
166 return (1);
167 }
168 mpool_put(t->bt_mp, e.page, 0);
169 return (0);
170 }
171
172 /*
173 * __bt_sprev --
174 * Check for an exact match before the key.
175 *
176 * Parameters:
177 * t: tree
178 * h: current page
179 * key: key
180 * exactp: pointer to exact match flag
181 *
182 * Returns:
183 * If an exact match found.
184 */
185 static int
__bt_sprev(BTREE * t,PAGE * h,const DBT * key,int * exactp)186 __bt_sprev(BTREE *t, PAGE *h, const DBT *key, int *exactp)
187 {
188 EPG e;
189
190 /*
191 * Get the previous page. The key is either an exact
192 * match, or not as good as the one we already have.
193 */
194 if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
195 return (0);
196 e.index = NEXTINDEX(e.page) - 1;
197 if (__bt_cmp(t, key, &e) == 0) {
198 mpool_put(t->bt_mp, h, 0);
199 t->bt_cur = e;
200 *exactp = 1;
201 return (1);
202 }
203 mpool_put(t->bt_mp, e.page, 0);
204 return (0);
205 }
206