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