Deleted Added
sdiff udiff text old ( 1573 ) new ( 14272 )
full compact
bt_search.c (1573) bt_search.c (14272)
1/*-
1/*-
2 * Copyright (c) 1990, 1993
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:

--- 19 unchanged lines hidden (view full) ---

30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#if defined(LIBC_SCCS) && !defined(lint)
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:

--- 19 unchanged lines hidden (view full) ---

30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#if defined(LIBC_SCCS) && !defined(lint)
38static char sccsid[] = "@(#)bt_search.c 8.6 (Berkeley) 3/15/94";
38static char sccsid[] = "@(#)bt_search.c 8.8 (Berkeley) 7/31/94";
39#endif /* LIBC_SCCS and not lint */
40
41#include <sys/types.h>
42
43#include <stdio.h>
44
45#include <db.h>
46#include "btree.h"
47
39#endif /* LIBC_SCCS and not lint */
40
41#include <sys/types.h>
42
43#include <stdio.h>
44
45#include <db.h>
46#include "btree.h"
47
48static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
49static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
48static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
49static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
50
51/*
50
51/*
52 * __BT_SEARCH -- Search a btree for a key.
52 * __bt_search --
53 * Search a btree for a key.
53 *
54 * Parameters:
55 * t: tree to search
56 * key: key to find
57 * exactp: pointer to exact match flag
58 *
59 * Returns:
60 * The EPG for matching record, if any, or the EPG for the location

--- 29 unchanged lines hidden (view full) ---

90 }
91 if (cmp > 0) {
92 base = index + 1;
93 --lim;
94 }
95 }
96
97 /*
54 *
55 * Parameters:
56 * t: tree to search
57 * key: key to find
58 * exactp: pointer to exact match flag
59 *
60 * Returns:
61 * The EPG for matching record, if any, or the EPG for the location

--- 29 unchanged lines hidden (view full) ---

91 }
92 if (cmp > 0) {
93 base = index + 1;
94 --lim;
95 }
96 }
97
98 /*
98 * If it's a leaf page, and duplicates aren't allowed, we're
99 * done. If duplicates are allowed, it's possible that there
100 * were duplicate keys on duplicate pages, and they were later
101 * deleted, so we could be on a page with no matches while
102 * there are matches on other pages. If we're at the start or
103 * end of a page, check on both sides.
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.
104 */
105 if (h->flags & P_BLEAF) {
105 */
106 if (h->flags & P_BLEAF) {
106 t->bt_cur.index = base;
107 *exactp = 0;
108 if (!ISSET(t, B_NODUPS)) {
107 if (!F_ISSET(t, B_NODUPS)) {
109 if (base == 0 &&
108 if (base == 0 &&
110 bt_sprev(t, h, key, exactp))
109 h->prevpg != P_INVALID &&
110 __bt_sprev(t, h, key, exactp))
111 return (&t->bt_cur);
112 if (base == NEXTINDEX(h) &&
111 return (&t->bt_cur);
112 if (base == NEXTINDEX(h) &&
113 bt_snext(t, h, key, exactp))
113 h->nextpg != P_INVALID &&
114 __bt_snext(t, h, key, exactp))
114 return (&t->bt_cur);
115 }
115 return (&t->bt_cur);
116 }
117 *exactp = 0;
118 t->bt_cur.index = base;
116 return (&t->bt_cur);
117 }
118
119 /*
120 * No match found. Base is the smallest index greater than
121 * key and may be zero or a last + 1 index. If it's non-zero,
122 * decrement by one, and record the internal page which should
123 * be a parent page for the key. If a split later occurs, the
124 * inserted page will be to the right of the saved page.
125 */
126 index = base ? base - 1 : base;
127
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 index = base ? base - 1 : base;
130
128next: if (__bt_push(t, h->pgno, index) == RET_ERROR)
129 return (NULL);
131next: BT_PUSH(t, h->pgno, index);
130 pg = GETBINTERNAL(h, index)->pgno;
131 mpool_put(t->bt_mp, h, 0);
132 }
133}
134
135/*
132 pg = GETBINTERNAL(h, index)->pgno;
133 mpool_put(t->bt_mp, h, 0);
134 }
135}
136
137/*
136 * BT_SNEXT -- Check for an exact match after the key.
138 * __bt_snext --
139 * Check for an exact match after the key.
137 *
138 * Parameters:
140 *
141 * Parameters:
139 * t: tree to search
140 * h: current page.
141 * key: key to find
142 * t: tree
143 * h: current page
144 * key: key
142 * exactp: pointer to exact match flag
143 *
144 * Returns:
145 * If an exact match found.
146 */
147static int
145 * exactp: pointer to exact match flag
146 *
147 * Returns:
148 * If an exact match found.
149 */
150static int
148bt_snext(t, h, key, exactp)
151__bt_snext(t, h, key, exactp)
149 BTREE *t;
150 PAGE *h;
151 const DBT *key;
152 int *exactp;
153{
154 EPG e;
152 BTREE *t;
153 PAGE *h;
154 const DBT *key;
155 int *exactp;
156{
157 EPG e;
155 PAGE *tp;
156 pgno_t pg;
157
158
158 /* Skip until reach the end of the tree or a key. */
159 for (pg = h->nextpg; pg != P_INVALID;) {
160 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
161 mpool_put(t->bt_mp, h, 0);
162 return (NULL);
163 }
164 if (NEXTINDEX(tp) != 0)
165 break;
166 pg = tp->prevpg;
167 mpool_put(t->bt_mp, tp, 0);
168 }
169 /*
159 /*
170 * The key is either an exact match, or not as good as
171 * the one we already have.
160 * Get the next page. The key is either an exact
161 * match, or not as good as the one we already have.
172 */
162 */
173 if (pg != P_INVALID) {
174 e.page = tp;
175 e.index = NEXTINDEX(tp) - 1;
176 if (__bt_cmp(t, key, &e) == 0) {
177 mpool_put(t->bt_mp, h, 0);
178 t->bt_cur = e;
179 *exactp = 1;
180 return (1);
181 }
163 if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
164 return (0);
165 e.index = 0;
166 if (__bt_cmp(t, key, &e) == 0) {
167 mpool_put(t->bt_mp, h, 0);
168 t->bt_cur = e;
169 *exactp = 1;
170 return (1);
182 }
171 }
172 mpool_put(t->bt_mp, e.page, 0);
183 return (0);
184}
185
186/*
173 return (0);
174}
175
176/*
187 * BT_SPREV -- Check for an exact match before the key.
177 * __bt_sprev --
178 * Check for an exact match before the key.
188 *
189 * Parameters:
179 *
180 * Parameters:
190 * t: tree to search
191 * h: current page.
192 * key: key to find
181 * t: tree
182 * h: current page
183 * key: key
193 * exactp: pointer to exact match flag
194 *
195 * Returns:
196 * If an exact match found.
197 */
198static int
184 * exactp: pointer to exact match flag
185 *
186 * Returns:
187 * If an exact match found.
188 */
189static int
199bt_sprev(t, h, key, exactp)
190__bt_sprev(t, h, key, exactp)
200 BTREE *t;
201 PAGE *h;
202 const DBT *key;
203 int *exactp;
204{
205 EPG e;
191 BTREE *t;
192 PAGE *h;
193 const DBT *key;
194 int *exactp;
195{
196 EPG e;
206 PAGE *tp;
207 pgno_t pg;
208
197
209 /* Skip until reach the beginning of the tree or a key. */
210 for (pg = h->prevpg; pg != P_INVALID;) {
211 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
212 mpool_put(t->bt_mp, h, 0);
213 return (NULL);
214 }
215 if (NEXTINDEX(tp) != 0)
216 break;
217 pg = tp->prevpg;
218 mpool_put(t->bt_mp, tp, 0);
219 }
220 /*
198 /*
221 * The key is either an exact match, or not as good as
222 * the one we already have.
199 * Get the previous page. The key is either an exact
200 * match, or not as good as the one we already have.
223 */
201 */
224 if (pg != P_INVALID) {
225 e.page = tp;
226 e.index = NEXTINDEX(tp) - 1;
227 if (__bt_cmp(t, key, &e) == 0) {
228 mpool_put(t->bt_mp, h, 0);
229 t->bt_cur = e;
230 *exactp = 1;
231 return (1);
232 }
202 if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
203 return (0);
204 e.index = NEXTINDEX(e.page) - 1;
205 if (__bt_cmp(t, key, &e) == 0) {
206 mpool_put(t->bt_mp, h, 0);
207 t->bt_cur = e;
208 *exactp = 1;
209 return (1);
233 }
210 }
211 mpool_put(t->bt_mp, e.page, 0);
234 return (0);
235}
212 return (0);
213}