xref: /dragonfly/lib/libc/db/btree/bt_search.c (revision abd448c3)
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. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  * @(#)bt_search.c	8.8 (Berkeley) 7/31/94
33  * $FreeBSD: head/lib/libc/db/btree/bt_search.c 189292 2009-03-03 02:16:12Z delphij $
34  */
35 
36 #include <sys/types.h>
37 
38 #include <stdio.h>
39 
40 #include <db.h>
41 #include "btree.h"
42 
43 static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
44 static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);
45 
46 /*
47  * __bt_search --
48  *	Search a btree for a key.
49  *
50  * Parameters:
51  *	t:	tree to search
52  *	key:	key to find
53  *	exactp:	pointer to exact match flag
54  *
55  * Returns:
56  *	The EPG for matching record, if any, or the EPG for the location
57  *	of the key, if it were inserted into the tree, is entered into
58  *	the bt_cur field of the tree.  A pointer to the field is returned.
59  */
60 EPG *
__bt_search(BTREE * t,const DBT * key,int * exactp)61 __bt_search(BTREE *t, const DBT *key, int *exactp)
62 {
63 	PAGE *h;
64 	indx_t base, idx, lim;
65 	pgno_t pg;
66 	int cmp;
67 
68 	BT_CLR(t);
69 	for (pg = P_ROOT;;) {
70 		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
71 			return (NULL);
72 
73 		/* Do a binary search on the current page. */
74 		t->bt_cur.page = h;
75 		for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
76 			t->bt_cur.index = idx = base + (lim >> 1);
77 			if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
78 				if (h->flags & P_BLEAF) {
79 					*exactp = 1;
80 					return (&t->bt_cur);
81 				}
82 				goto next;
83 			}
84 			if (cmp > 0) {
85 				base = idx + 1;
86 				--lim;
87 			}
88 		}
89 
90 		/*
91 		 * If it's a leaf page, we're almost done.  If no duplicates
92 		 * are allowed, or we have an exact match, we're done.  Else,
93 		 * it's possible that there were matching keys on this page,
94 		 * which later deleted, and we're on a page with no matches
95 		 * while there are matches on other pages.  If at the start or
96 		 * end of a page, check the adjacent page.
97 		 */
98 		if (h->flags & P_BLEAF) {
99 			if (!F_ISSET(t, B_NODUPS)) {
100 				if (base == 0 &&
101 				    h->prevpg != P_INVALID &&
102 				    __bt_sprev(t, h, key, exactp))
103 					return (&t->bt_cur);
104 				if (base == NEXTINDEX(h) &&
105 				    h->nextpg != P_INVALID &&
106 				    __bt_snext(t, h, key, exactp))
107 					return (&t->bt_cur);
108 			}
109 			*exactp = 0;
110 			t->bt_cur.index = base;
111 			return (&t->bt_cur);
112 		}
113 
114 		/*
115 		 * No match found.  Base is the smallest index greater than
116 		 * key and may be zero or a last + 1 index.  If it's non-zero,
117 		 * decrement by one, and record the internal page which should
118 		 * be a parent page for the key.  If a split later occurs, the
119 		 * inserted page will be to the right of the saved page.
120 		 */
121 		idx = base ? base - 1 : base;
122 
123 next:		BT_PUSH(t, h->pgno, idx);
124 		pg = GETBINTERNAL(h, idx)->pgno;
125 		mpool_put(t->bt_mp, h, 0);
126 	}
127 }
128 
129 /*
130  * __bt_snext --
131  *	Check for an exact match after the key.
132  *
133  * Parameters:
134  *	t:	tree
135  *	h:	current page
136  *	key:	key
137  *	exactp:	pointer to exact match flag
138  *
139  * Returns:
140  *	If an exact match found.
141  */
142 static int
__bt_snext(BTREE * t,PAGE * h,const DBT * key,int * exactp)143 __bt_snext(BTREE *t, PAGE *h, const DBT *key, int *exactp)
144 {
145 	EPG e;
146 
147 	/*
148 	 * Get the next page.  The key is either an exact
149 	 * match, or not as good as the one we already have.
150 	 */
151 	if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
152 		return (0);
153 	e.index = 0;
154 	if (__bt_cmp(t, key, &e) == 0) {
155 		mpool_put(t->bt_mp, h, 0);
156 		t->bt_cur = e;
157 		*exactp = 1;
158 		return (1);
159 	}
160 	mpool_put(t->bt_mp, e.page, 0);
161 	return (0);
162 }
163 
164 /*
165  * __bt_sprev --
166  *	Check for an exact match before the key.
167  *
168  * Parameters:
169  *	t:	tree
170  *	h:	current page
171  *	key:	key
172  *	exactp:	pointer to exact match flag
173  *
174  * Returns:
175  *	If an exact match found.
176  */
177 static int
__bt_sprev(BTREE * t,PAGE * h,const DBT * key,int * exactp)178 __bt_sprev(BTREE *t, PAGE *h, const DBT *key, int *exactp)
179 {
180 	EPG e;
181 
182 	/*
183 	 * Get the previous page.  The key is either an exact
184 	 * match, or not as good as the one we already have.
185 	 */
186 	if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
187 		return (0);
188 	e.index = NEXTINDEX(e.page) - 1;
189 	if (__bt_cmp(t, key, &e) == 0) {
190 		mpool_put(t->bt_mp, h, 0);
191 		t->bt_cur = e;
192 		*exactp = 1;
193 		return (1);
194 	}
195 	mpool_put(t->bt_mp, e.page, 0);
196 	return (0);
197 }
198