xref: /freebsd/lib/libc/db/btree/bt_search.c (revision 7ab1a32cd43cbae61ad4dd435d6a482bbf61cb52)
1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
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 #include <sys/types.h>
36 
37 #include <stdio.h>
38 
39 #include <db.h>
40 #include "btree.h"
41 
42 static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
43 static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);
44 
45 /*
46  * __bt_search --
47  *	Search a btree for a key.
48  *
49  * Parameters:
50  *	t:	tree to search
51  *	key:	key to find
52  *	exactp:	pointer to exact match flag
53  *
54  * Returns:
55  *	The EPG for matching record, if any, or the EPG for the location
56  *	of the key, if it were inserted into the tree, is entered into
57  *	the bt_cur field of the tree.  A pointer to the field is returned.
58  */
59 EPG *
60 __bt_search(BTREE *t, const DBT *key, int *exactp)
61 {
62 	PAGE *h;
63 	indx_t base, idx, lim;
64 	pgno_t pg;
65 	int cmp;
66 
67 	BT_CLR(t);
68 	for (pg = P_ROOT;;) {
69 		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
70 			return (NULL);
71 
72 		/* Do a binary search on the current page. */
73 		t->bt_cur.page = h;
74 		for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
75 			t->bt_cur.index = idx = base + (lim >> 1);
76 			if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
77 				if (h->flags & P_BLEAF) {
78 					*exactp = 1;
79 					return (&t->bt_cur);
80 				}
81 				goto next;
82 			}
83 			if (cmp > 0) {
84 				base = idx + 1;
85 				--lim;
86 			}
87 		}
88 
89 		/*
90 		 * If it's a leaf page, we're almost done.  If no duplicates
91 		 * are allowed, or we have an exact match, we're done.  Else,
92 		 * it's possible that there were matching keys on this page,
93 		 * which later deleted, and we're on a page with no matches
94 		 * while there are matches on other pages.  If at the start or
95 		 * end of a page, check the adjacent page.
96 		 */
97 		if (h->flags & P_BLEAF) {
98 			if (!F_ISSET(t, B_NODUPS)) {
99 				if (base == 0 &&
100 				    h->prevpg != P_INVALID &&
101 				    __bt_sprev(t, h, key, exactp))
102 					return (&t->bt_cur);
103 				if (base == NEXTINDEX(h) &&
104 				    h->nextpg != P_INVALID &&
105 				    __bt_snext(t, h, key, exactp))
106 					return (&t->bt_cur);
107 			}
108 			*exactp = 0;
109 			t->bt_cur.index = base;
110 			return (&t->bt_cur);
111 		}
112 
113 		/*
114 		 * No match found.  Base is the smallest index greater than
115 		 * key and may be zero or a last + 1 index.  If it's non-zero,
116 		 * decrement by one, and record the internal page which should
117 		 * be a parent page for the key.  If a split later occurs, the
118 		 * inserted page will be to the right of the saved page.
119 		 */
120 		idx = base ? base - 1 : base;
121 
122 next:		BT_PUSH(t, h->pgno, idx);
123 		pg = GETBINTERNAL(h, idx)->pgno;
124 		mpool_put(t->bt_mp, h, 0);
125 	}
126 }
127 
128 /*
129  * __bt_snext --
130  *	Check for an exact match after the key.
131  *
132  * Parameters:
133  *	t:	tree
134  *	h:	current page
135  *	key:	key
136  *	exactp:	pointer to exact match flag
137  *
138  * Returns:
139  *	If an exact match found.
140  */
141 static int
142 __bt_snext(BTREE *t, PAGE *h, const DBT *key, int *exactp)
143 {
144 	EPG e;
145 
146 	/*
147 	 * Get the next page.  The key is either an exact
148 	 * match, or not as good as the one we already have.
149 	 */
150 	if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
151 		return (0);
152 	e.index = 0;
153 	if (__bt_cmp(t, key, &e) == 0) {
154 		mpool_put(t->bt_mp, h, 0);
155 		t->bt_cur = e;
156 		*exactp = 1;
157 		return (1);
158 	}
159 	mpool_put(t->bt_mp, e.page, 0);
160 	return (0);
161 }
162 
163 /*
164  * __bt_sprev --
165  *	Check for an exact match before the key.
166  *
167  * Parameters:
168  *	t:	tree
169  *	h:	current page
170  *	key:	key
171  *	exactp:	pointer to exact match flag
172  *
173  * Returns:
174  *	If an exact match found.
175  */
176 static int
177 __bt_sprev(BTREE *t, PAGE *h, const DBT *key, int *exactp)
178 {
179 	EPG e;
180 
181 	/*
182 	 * Get the previous page.  The key is either an exact
183 	 * match, or not as good as the one we already have.
184 	 */
185 	if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
186 		return (0);
187 	e.index = NEXTINDEX(e.page) - 1;
188 	if (__bt_cmp(t, key, &e) == 0) {
189 		mpool_put(t->bt_mp, h, 0);
190 		t->bt_cur = e;
191 		*exactp = 1;
192 		return (1);
193 	}
194 	mpool_put(t->bt_mp, e.page, 0);
195 	return (0);
196 }
197