1 /*-
2 * Copyright (c) 1990, 1993
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 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)bt_search.c 8.6 (Berkeley) 03/15/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <stdio.h>
18
19 #include <db.h>
20 #include "btree.h"
21
22 static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
23 static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
24
25 /*
26 * __BT_SEARCH -- Search a btree for a key.
27 *
28 * Parameters:
29 * t: tree to search
30 * key: key to find
31 * exactp: pointer to exact match flag
32 *
33 * Returns:
34 * The EPG for matching record, if any, or the EPG for the location
35 * of the key, if it were inserted into the tree, is entered into
36 * the bt_cur field of the tree. A pointer to the field is returned.
37 */
38 EPG *
__bt_search(t,key,exactp)39 __bt_search(t, key, exactp)
40 BTREE *t;
41 const DBT *key;
42 int *exactp;
43 {
44 PAGE *h;
45 indx_t base, index, lim;
46 pgno_t pg;
47 int cmp;
48
49 BT_CLR(t);
50 for (pg = P_ROOT;;) {
51 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
52 return (NULL);
53
54 /* Do a binary search on the current page. */
55 t->bt_cur.page = h;
56 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
57 t->bt_cur.index = index = base + (lim >> 1);
58 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
59 if (h->flags & P_BLEAF) {
60 *exactp = 1;
61 return (&t->bt_cur);
62 }
63 goto next;
64 }
65 if (cmp > 0) {
66 base = index + 1;
67 --lim;
68 }
69 }
70
71 /*
72 * If it's a leaf page, and duplicates aren't allowed, we're
73 * done. If duplicates are allowed, it's possible that there
74 * were duplicate keys on duplicate pages, and they were later
75 * deleted, so we could be on a page with no matches while
76 * there are matches on other pages. If we're at the start or
77 * end of a page, check on both sides.
78 */
79 if (h->flags & P_BLEAF) {
80 t->bt_cur.index = base;
81 *exactp = 0;
82 if (!ISSET(t, B_NODUPS)) {
83 if (base == 0 &&
84 bt_sprev(t, h, key, exactp))
85 return (&t->bt_cur);
86 if (base == NEXTINDEX(h) &&
87 bt_snext(t, h, key, exactp))
88 return (&t->bt_cur);
89 }
90 return (&t->bt_cur);
91 }
92
93 /*
94 * No match found. Base is the smallest index greater than
95 * key and may be zero or a last + 1 index. If it's non-zero,
96 * decrement by one, and record the internal page which should
97 * be a parent page for the key. If a split later occurs, the
98 * inserted page will be to the right of the saved page.
99 */
100 index = base ? base - 1 : base;
101
102 next: if (__bt_push(t, h->pgno, index) == RET_ERROR)
103 return (NULL);
104 pg = GETBINTERNAL(h, index)->pgno;
105 mpool_put(t->bt_mp, h, 0);
106 }
107 }
108
109 /*
110 * BT_SNEXT -- Check for an exact match after the key.
111 *
112 * Parameters:
113 * t: tree to search
114 * h: current page.
115 * key: key to find
116 * exactp: pointer to exact match flag
117 *
118 * Returns:
119 * If an exact match found.
120 */
121 static int
bt_snext(t,h,key,exactp)122 bt_snext(t, h, key, exactp)
123 BTREE *t;
124 PAGE *h;
125 const DBT *key;
126 int *exactp;
127 {
128 EPG e;
129 PAGE *tp;
130 pgno_t pg;
131
132 /* Skip until reach the end of the tree or a key. */
133 for (pg = h->nextpg; pg != P_INVALID;) {
134 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
135 mpool_put(t->bt_mp, h, 0);
136 return (NULL);
137 }
138 if (NEXTINDEX(tp) != 0)
139 break;
140 pg = tp->prevpg;
141 mpool_put(t->bt_mp, tp, 0);
142 }
143 /*
144 * The key is either an exact match, or not as good as
145 * the one we already have.
146 */
147 if (pg != P_INVALID) {
148 e.page = tp;
149 e.index = NEXTINDEX(tp) - 1;
150 if (__bt_cmp(t, key, &e) == 0) {
151 mpool_put(t->bt_mp, h, 0);
152 t->bt_cur = e;
153 *exactp = 1;
154 return (1);
155 }
156 }
157 return (0);
158 }
159
160 /*
161 * BT_SPREV -- Check for an exact match before the key.
162 *
163 * Parameters:
164 * t: tree to search
165 * h: current page.
166 * key: key to find
167 * exactp: pointer to exact match flag
168 *
169 * Returns:
170 * If an exact match found.
171 */
172 static int
bt_sprev(t,h,key,exactp)173 bt_sprev(t, h, key, exactp)
174 BTREE *t;
175 PAGE *h;
176 const DBT *key;
177 int *exactp;
178 {
179 EPG e;
180 PAGE *tp;
181 pgno_t pg;
182
183 /* Skip until reach the beginning of the tree or a key. */
184 for (pg = h->prevpg; pg != P_INVALID;) {
185 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
186 mpool_put(t->bt_mp, h, 0);
187 return (NULL);
188 }
189 if (NEXTINDEX(tp) != 0)
190 break;
191 pg = tp->prevpg;
192 mpool_put(t->bt_mp, tp, 0);
193 }
194 /*
195 * The key is either an exact match, or not as good as
196 * the one we already have.
197 */
198 if (pg != P_INVALID) {
199 e.page = tp;
200 e.index = NEXTINDEX(tp) - 1;
201 if (__bt_cmp(t, key, &e) == 0) {
202 mpool_put(t->bt_mp, h, 0);
203 t->bt_cur = e;
204 *exactp = 1;
205 return (1);
206 }
207 }
208 return (0);
209 }
210