1 /*-
2 * Copyright (c) 1990 The Regents of the University of California.
3 * 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. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
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)
38 static char sccsid[] = "@(#)bt_get.c 5.9 (Berkeley) 5/16/93";
39 #endif /* LIBC_SCCS and not lint */
40
41 #include <sys/types.h>
42
43 #include <errno.h>
44 #include <stddef.h>
45 #include <stdio.h>
46
47 #include <db.h>
48 #include "btree.h"
49
50 /*
51 * __BT_GET -- Get a record from the btree.
52 *
53 * Parameters:
54 * dbp: pointer to access method
55 * key: key to find
56 * data: data to return
57 * flag: currently unused
58 *
59 * Returns:
60 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
61 */
62 int
__bt_get(dbp,key,data,flags)63 __bt_get(dbp, key, data, flags)
64 const DB *dbp;
65 const DBT *key;
66 DBT *data;
67 u_int flags;
68 {
69 BTREE *t;
70 EPG *e;
71 int exact, status;
72
73 if (flags) {
74 errno = EINVAL;
75 return (RET_ERROR);
76 }
77 t = dbp->internal;
78 if ((e = __bt_search(t, key, &exact)) == NULL)
79 return (RET_ERROR);
80 if (!exact) {
81 mpool_put(t->bt_mp, e->page, 0);
82 return (RET_SPECIAL);
83 }
84
85 /*
86 * A special case is if we found the record but it's flagged for
87 * deletion. In this case, we want to find another record with the
88 * same key, if it exists. Rather than look around the tree we call
89 * __bt_first and have it redo the search, as __bt_first will not
90 * return keys marked for deletion. Slow, but should never happen.
91 */
92 if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
93 e->index == t->bt_bcursor.index) {
94 mpool_put(t->bt_mp, e->page, 0);
95 if ((e = __bt_first(t, key, &exact)) == NULL)
96 return (RET_ERROR);
97 if (!exact)
98 return (RET_SPECIAL);
99 }
100
101 status = __bt_ret(t, e, NULL, data);
102 mpool_put(t->bt_mp, e->page, 0);
103 return (status);
104 }
105
106 /*
107 * __BT_FIRST -- Find the first entry.
108 *
109 * Parameters:
110 * t: the tree
111 * key: the key
112 *
113 * Returns:
114 * The first entry in the tree greater than or equal to key.
115 */
116 EPG *
__bt_first(t,key,exactp)117 __bt_first(t, key, exactp)
118 BTREE *t;
119 const DBT *key;
120 int *exactp;
121 {
122 register PAGE *h;
123 register EPG *e;
124 EPG save;
125 pgno_t cpgno, pg;
126 indx_t cindex;
127 int found;
128
129 /*
130 * Find any matching record; __bt_search pins the page. Only exact
131 * matches are tricky, otherwise just return the location of the key
132 * if it were to be inserted into the tree.
133 */
134 if ((e = __bt_search(t, key, exactp)) == NULL)
135 return (NULL);
136 if (!*exactp)
137 return (e);
138
139 if (ISSET(t, B_DELCRSR)) {
140 cpgno = t->bt_bcursor.pgno;
141 cindex = t->bt_bcursor.index;
142 } else {
143 cpgno = P_INVALID;
144 cindex = 0; /* GCC thinks it's uninitialized. */
145 }
146
147 /*
148 * Walk backwards, skipping empty pages, as long as the entry matches
149 * and there are keys left in the tree. Save a copy of each match in
150 * case we go too far. A special case is that we don't return a match
151 * on records that the cursor references that have already been flagged
152 * for deletion.
153 */
154 save = *e;
155 h = e->page;
156 found = 0;
157 do {
158 if (cpgno != h->pgno || cindex != e->index) {
159 if (save.page->pgno != e->page->pgno) {
160 mpool_put(t->bt_mp, save.page, 0);
161 save = *e;
162 } else
163 save.index = e->index;
164 found = 1;
165 }
166 /*
167 * Make a special effort not to unpin the page the last (or
168 * original) match was on, but also make sure it's unpinned
169 * if an error occurs.
170 */
171 while (e->index == 0) {
172 if (h->prevpg == P_INVALID)
173 goto done1;
174 if (h->pgno != save.page->pgno)
175 mpool_put(t->bt_mp, h, 0);
176 if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
177 if (h->pgno == save.page->pgno)
178 mpool_put(t->bt_mp, save.page, 0);
179 return (NULL);
180 }
181 e->page = h;
182 e->index = NEXTINDEX(h);
183 }
184 --e->index;
185 } while (__bt_cmp(t, key, e) == 0);
186
187 /*
188 * Reach here with the last page that was looked at pinned, which may
189 * or may not be the same as the last (or original) match page. If
190 * it's not useful, release it.
191 */
192 done1: if (h->pgno != save.page->pgno)
193 mpool_put(t->bt_mp, h, 0);
194
195 /*
196 * If still haven't found a record, the only possibility left is the
197 * next one. Move forward one slot, skipping empty pages and check.
198 */
199 if (!found) {
200 h = save.page;
201 if (++save.index == NEXTINDEX(h)) {
202 do {
203 pg = h->nextpg;
204 mpool_put(t->bt_mp, h, 0);
205 if (pg == P_INVALID) {
206 *exactp = 0;
207 return (e);
208 }
209 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
210 return (NULL);
211 } while ((save.index = NEXTINDEX(h)) == 0);
212 save.page = h;
213 }
214 if (__bt_cmp(t, key, &save) != 0) {
215 *exactp = 0;
216 return (e);
217 }
218 }
219 *e = save;
220 *exactp = 1;
221 return (e);
222 }
223