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