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