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_get.c 8.2 (Berkeley) 09/07/93";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <errno.h>
18 #include <stddef.h>
19 #include <stdio.h>
20
21 #include <db.h>
22 #include "btree.h"
23
24 /*
25 * __BT_GET -- Get a record from the btree.
26 *
27 * Parameters:
28 * dbp: pointer to access method
29 * key: key to find
30 * data: data to return
31 * flag: currently unused
32 *
33 * Returns:
34 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
35 */
36 int
__bt_get(dbp,key,data,flags)37 __bt_get(dbp, key, data, flags)
38 const DB *dbp;
39 const DBT *key;
40 DBT *data;
41 u_int flags;
42 {
43 BTREE *t;
44 EPG *e;
45 int exact, status;
46
47 t = dbp->internal;
48
49 /* Toss any page pinned across calls. */
50 if (t->bt_pinned != NULL) {
51 mpool_put(t->bt_mp, t->bt_pinned, 0);
52 t->bt_pinned = NULL;
53 }
54
55 /* Get currently doesn't take any flags. */
56 if (flags) {
57 errno = EINVAL;
58 return (RET_ERROR);
59 }
60
61 if ((e = __bt_search(t, key, &exact)) == NULL)
62 return (RET_ERROR);
63 if (!exact) {
64 mpool_put(t->bt_mp, e->page, 0);
65 return (RET_SPECIAL);
66 }
67
68 /*
69 * A special case is if we found the record but it's flagged for
70 * deletion. In this case, we want to find another record with the
71 * same key, if it exists. Rather than look around the tree we call
72 * __bt_first and have it redo the search, as __bt_first will not
73 * return keys marked for deletion. Slow, but should never happen.
74 */
75 if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
76 e->index == t->bt_bcursor.index) {
77 mpool_put(t->bt_mp, e->page, 0);
78 if ((e = __bt_first(t, key, &exact)) == NULL)
79 return (RET_ERROR);
80 if (!exact)
81 return (RET_SPECIAL);
82 }
83
84 status = __bt_ret(t, e, NULL, data);
85 /*
86 * If the user is doing concurrent access, we copied the
87 * key/data, toss the page.
88 */
89 if (ISSET(t, B_DB_LOCK))
90 mpool_put(t->bt_mp, e->page, 0);
91 else
92 t->bt_pinned = e->page;
93 return (status);
94 }
95
96 /*
97 * __BT_FIRST -- Find the first entry.
98 *
99 * Parameters:
100 * t: the tree
101 * key: the key
102 *
103 * Returns:
104 * The first entry in the tree greater than or equal to key.
105 */
106 EPG *
__bt_first(t,key,exactp)107 __bt_first(t, key, exactp)
108 BTREE *t;
109 const DBT *key;
110 int *exactp;
111 {
112 register PAGE *h;
113 register EPG *e;
114 EPG save;
115 pgno_t cpgno, pg;
116 indx_t cindex;
117 int found;
118
119 /*
120 * Find any matching record; __bt_search pins the page. Only exact
121 * matches are tricky, otherwise just return the location of the key
122 * if it were to be inserted into the tree.
123 */
124 if ((e = __bt_search(t, key, exactp)) == NULL)
125 return (NULL);
126 if (!*exactp)
127 return (e);
128
129 if (ISSET(t, B_DELCRSR)) {
130 cpgno = t->bt_bcursor.pgno;
131 cindex = t->bt_bcursor.index;
132 } else {
133 cpgno = P_INVALID;
134 cindex = 0; /* GCC thinks it's uninitialized. */
135 }
136
137 /*
138 * Walk backwards, skipping empty pages, as long as the entry matches
139 * and there are keys left in the tree. Save a copy of each match in
140 * case we go too far. A special case is that we don't return a match
141 * on records that the cursor references that have already been flagged
142 * for deletion.
143 */
144 save = *e;
145 h = e->page;
146 found = 0;
147 do {
148 if (cpgno != h->pgno || cindex != e->index) {
149 if (save.page->pgno != e->page->pgno) {
150 mpool_put(t->bt_mp, save.page, 0);
151 save = *e;
152 } else
153 save.index = e->index;
154 found = 1;
155 }
156 /*
157 * Make a special effort not to unpin the page the last (or
158 * original) match was on, but also make sure it's unpinned
159 * if an error occurs.
160 */
161 while (e->index == 0) {
162 if (h->prevpg == P_INVALID)
163 goto done1;
164 if (h->pgno != save.page->pgno)
165 mpool_put(t->bt_mp, h, 0);
166 if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
167 if (h->pgno == save.page->pgno)
168 mpool_put(t->bt_mp, save.page, 0);
169 return (NULL);
170 }
171 e->page = h;
172 e->index = NEXTINDEX(h);
173 }
174 --e->index;
175 } while (__bt_cmp(t, key, e) == 0);
176
177 /*
178 * Reach here with the last page that was looked at pinned, which may
179 * or may not be the same as the last (or original) match page. If
180 * it's not useful, release it.
181 */
182 done1: if (h->pgno != save.page->pgno)
183 mpool_put(t->bt_mp, h, 0);
184
185 /*
186 * If still haven't found a record, the only possibility left is the
187 * next one. Move forward one slot, skipping empty pages and check.
188 */
189 if (!found) {
190 h = save.page;
191 if (++save.index == NEXTINDEX(h)) {
192 do {
193 pg = h->nextpg;
194 mpool_put(t->bt_mp, h, 0);
195 if (pg == P_INVALID) {
196 *exactp = 0;
197 return (e);
198 }
199 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
200 return (NULL);
201 } while ((save.index = NEXTINDEX(h)) == 0);
202 save.page = h;
203 }
204 if (__bt_cmp(t, key, &save) != 0) {
205 *exactp = 0;
206 return (e);
207 }
208 }
209 *e = save;
210 *exactp = 1;
211 return (e);
212 }
213