Commit | Line | Data |
---|---|---|
4e820f17 MO |
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 | * | |
af359dea C |
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. | |
4e820f17 MO |
35 | */ |
36 | ||
37 | #if defined(LIBC_SCCS) && !defined(lint) | |
af359dea | 38 | static char sccsid[] = "@(#)seq.c 5.4 (Berkeley) 3/3/91"; |
4e820f17 MO |
39 | #endif /* LIBC_SCCS and not lint */ |
40 | ||
41 | #include <sys/types.h> | |
fb91cf55 | 42 | #include <errno.h> |
4e820f17 | 43 | #include <db.h> |
fb91cf55 | 44 | #include <stdlib.h> |
4e820f17 MO |
45 | #include "btree.h" |
46 | ||
47 | /* | |
48 | * _BT_SEQINIT -- Initialize a sequential scan on the btree. | |
49 | * | |
50 | * Sets the tree's notion of the current scan location correctly | |
51 | * given a key and a direction. | |
52 | * | |
53 | * Parameters: | |
54 | * t -- tree in which to initialize scan | |
55 | * key -- key for initial scan position | |
56 | * flags -- R_NEXT, R_PREV | |
57 | * | |
58 | * Returns: | |
59 | * RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data | |
60 | * in the tree to scan. | |
61 | * | |
62 | * Side Effects: | |
63 | * Changes current scan position for the tree. Almost certainly | |
64 | * changes current page, as well. Sets BTF_SEQINIT bit in tree | |
65 | * flags, so that we know we've initialized a scan. | |
66 | */ | |
67 | ||
68 | int | |
69 | _bt_seqinit(t, key, flags) | |
70 | BTREE_P t; | |
71 | DBT *key; | |
72 | int flags; | |
73 | { | |
74 | BTITEM *item; | |
75 | BTHEADER *h; | |
76 | CURSOR *c; | |
77 | IDATUM *id; | |
78 | index_t last; | |
79 | ||
80 | /* | |
81 | * Figure out if we really have to search for the key that the | |
82 | * user supplied. If key is null, then this is an unkeyed scan | |
83 | * and we can just start from an endpoint. | |
84 | */ | |
85 | ||
86 | c = &(t->bt_cursor); | |
87 | ||
88 | if (flags == R_CURSOR) { | |
7d2840f6 | 89 | if (key->data != (u_char *) NULL) { |
4e820f17 MO |
90 | |
91 | /* key supplied, find first instance of it */ | |
92 | item = _bt_first(t, key); | |
93 | c->c_index = item->bti_index; | |
94 | c->c_pgno = t->bt_curpage->h_pgno; | |
95 | } else { | |
96 | errno = EINVAL; | |
97 | return (RET_ERROR); | |
98 | } | |
99 | ||
100 | } else { | |
101 | ||
102 | /* | |
103 | * Unkeyed scan. For backward scans, find the last item | |
104 | * in the tree; for forward scans, find the first item. | |
105 | */ | |
106 | ||
107 | if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR) | |
108 | return (RET_ERROR); | |
109 | h = t->bt_curpage; | |
110 | if (flags == R_LAST || flags == R_PREV) { | |
111 | ||
112 | /* backward scan */ | |
113 | while (!(h->h_flags & F_LEAF)) { | |
114 | last = NEXTINDEX(h) - 1; | |
115 | id = (IDATUM *) GETDATUM(h,last); | |
116 | if (_bt_getpage(t, id->i_pgno) == RET_ERROR) | |
117 | return (RET_ERROR); | |
118 | h = t->bt_curpage; | |
119 | } | |
120 | ||
121 | /* skip empty pages */ | |
122 | while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE) { | |
123 | if (_bt_getpage(t, h->h_prevpg) == RET_ERROR) | |
124 | return (RET_ERROR); | |
125 | h = t->bt_curpage; | |
126 | } | |
127 | ||
128 | c->c_pgno = h->h_pgno; | |
129 | if (NEXTINDEX(h) > 0) | |
130 | c->c_index = NEXTINDEX(h) - 1; | |
131 | else | |
132 | c->c_index = 0; | |
133 | } else if (flags == R_FIRST || flags == R_NEXT) { | |
134 | /* forward scan */ | |
135 | while (!(h->h_flags & F_LEAF)) { | |
136 | id = (IDATUM *) GETDATUM(h,0); | |
137 | if (_bt_getpage(t, id->i_pgno) == RET_ERROR) | |
138 | return (RET_ERROR); | |
139 | h = t->bt_curpage; | |
140 | } | |
141 | ||
142 | /* skip empty pages */ | |
143 | while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE) { | |
144 | if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) | |
145 | return (RET_ERROR); | |
146 | h = t->bt_curpage; | |
147 | } | |
148 | ||
149 | c->c_pgno = h->h_pgno; | |
150 | c->c_index = 0; | |
151 | } else { | |
152 | /* no flags passed in */ | |
153 | errno = EINVAL; | |
154 | return (RET_ERROR); | |
155 | } | |
156 | } | |
157 | ||
158 | /* okay, scan is initialized */ | |
159 | t->bt_flags |= BTF_SEQINIT; | |
160 | ||
1a18d2ca MO |
161 | /* don't need the descent stack anymore */ |
162 | while (_bt_pop(t) != P_NONE) | |
163 | continue; | |
164 | ||
4e820f17 MO |
165 | if (c->c_index == NEXTINDEX(t->bt_curpage)) |
166 | return (RET_SPECIAL); | |
167 | ||
168 | return (RET_SUCCESS); | |
169 | } | |
170 | ||
171 | /* | |
172 | * _BT_SEQADVANCE -- Advance the sequential scan on this tree. | |
173 | * | |
174 | * Moves the current location pointer for the scan on this tree one | |
175 | * spot in the requested direction. | |
176 | * | |
177 | * Parameters: | |
178 | * t -- btree being scanned | |
179 | * flags -- for R_NEXT, R_PREV | |
180 | * | |
181 | * Returns: | |
182 | * RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no | |
183 | * more data in the specified direction. | |
184 | * | |
185 | * Side Effects: | |
186 | * May change current page. | |
187 | */ | |
188 | ||
189 | int | |
190 | _bt_seqadvance(t, flags) | |
191 | BTREE_P t; | |
192 | int flags; | |
193 | { | |
194 | BTHEADER *h; | |
195 | CURSOR *c; | |
196 | index_t index; | |
197 | ||
198 | c = &(t->bt_cursor); | |
199 | index = c->c_index; | |
200 | ||
201 | if (_bt_getpage(t, c->c_pgno) == RET_ERROR) | |
202 | return (RET_ERROR); | |
203 | h = t->bt_curpage; | |
204 | ||
205 | /* by the time we get here, don't need the cursor key anymore */ | |
206 | if (c->c_key != (char *) NULL) | |
207 | (void) free(c->c_key); | |
208 | ||
209 | if (flags == R_NEXT) { | |
210 | ||
211 | /* | |
212 | * This is a forward scan. If the cursor is pointing | |
213 | * at a virtual record (that is, it was pointing at | |
214 | * a record that got deleted), then we should return | |
215 | * the record it's pointing at now. Otherwise, we | |
216 | * should advance the scan. In either case, we need | |
217 | * to be careful not to run off the end of the current | |
218 | * page. | |
219 | */ | |
220 | ||
221 | if (c->c_flags & CRSR_BEFORE) { | |
222 | ||
223 | if (index >= NEXTINDEX(h)) { | |
224 | /* out of items on this page, get next page */ | |
225 | if (h->h_nextpg == P_NONE) { | |
226 | /* tell caller we're done... */ | |
227 | c->c_index = NEXTINDEX(h); | |
228 | return (RET_SPECIAL); | |
229 | } | |
230 | ||
231 | /* skip empty pages */ | |
232 | do { | |
233 | if (_bt_getpage(t, h->h_nextpg) | |
234 | == RET_ERROR) { | |
235 | c->c_index = NEXTINDEX(h); | |
236 | return (RET_ERROR); | |
237 | } | |
238 | h = t->bt_curpage; | |
239 | c->c_pgno = h->h_pgno; | |
240 | } while (NEXTINDEX(h) == 0 | |
241 | && h->h_nextpg != P_NONE); | |
242 | ||
243 | if (NEXTINDEX(h) == 0) { | |
244 | /* tell caller we're done */ | |
245 | c->c_index = NEXTINDEX(h); | |
246 | return (RET_SPECIAL); | |
247 | } | |
248 | index = 0; | |
249 | } | |
250 | c->c_flags &= ~CRSR_BEFORE; | |
251 | ||
252 | } else if (++index >= NEXTINDEX(h)) { | |
253 | ||
254 | /* out of items on this page, get next page */ | |
255 | if (h->h_nextpg == P_NONE) { | |
256 | /* tell caller we're done... */ | |
257 | c->c_index = NEXTINDEX(h); | |
258 | return (RET_SPECIAL); | |
259 | } | |
260 | ||
261 | /* skip empty pages */ | |
262 | do { | |
263 | if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) { | |
264 | c->c_index = NEXTINDEX(h); | |
265 | return (RET_ERROR); | |
266 | } | |
267 | h = t->bt_curpage; | |
268 | c->c_pgno = h->h_pgno; | |
269 | } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE); | |
270 | ||
271 | if (NEXTINDEX(h) == 0) { | |
272 | /* tell caller we're done */ | |
273 | c->c_index = NEXTINDEX(h); | |
274 | return (RET_SPECIAL); | |
275 | } | |
276 | index = 0; | |
277 | } | |
278 | } else if (flags == R_PREV) { | |
279 | ||
280 | /* for backward scans, life is substantially easier */ | |
281 | c->c_flags &= ~CRSR_BEFORE; | |
282 | if (c->c_key != (char *) NULL) { | |
283 | (void) free(c->c_key); | |
284 | c->c_key = (char *) NULL; | |
285 | } | |
286 | ||
287 | if (index == 0) { | |
288 | ||
289 | /* we may be done */ | |
290 | c->c_index = 0; | |
291 | ||
292 | /* out of items on this page, get next page */ | |
293 | if (h->h_prevpg == P_NONE) | |
294 | return (RET_SPECIAL); | |
295 | ||
296 | /* skip empty pages */ | |
297 | do { | |
298 | if (_bt_getpage(t, h->h_prevpg) == RET_ERROR) | |
299 | return (RET_ERROR); | |
300 | h = t->bt_curpage; | |
301 | c->c_pgno = h->h_pgno; | |
302 | } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE); | |
303 | ||
304 | if (NEXTINDEX(h) == 0) | |
305 | return (RET_SPECIAL); | |
306 | ||
307 | index = NEXTINDEX(h) - 1; | |
308 | } else | |
309 | --index; | |
310 | } else { | |
311 | /* must specify a direction */ | |
312 | errno = EINVAL; | |
313 | return (RET_ERROR); | |
314 | } | |
315 | ||
316 | c->c_index = index; | |
317 | return (RET_SUCCESS); | |
318 | } |