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.1 (Berkeley) 01/23/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 if (c->c_index == NEXTINDEX(t->bt_curpage)) 135 return (RET_SPECIAL); 136 137 return (RET_SUCCESS); 138 } 139 140 /* 141 * _BT_SEQADVANCE -- Advance the sequential scan on this tree. 142 * 143 * Moves the current location pointer for the scan on this tree one 144 * spot in the requested direction. 145 * 146 * Parameters: 147 * t -- btree being scanned 148 * flags -- for R_NEXT, R_PREV 149 * 150 * Returns: 151 * RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no 152 * more data in the specified direction. 153 * 154 * Side Effects: 155 * May change current page. 156 */ 157 158 int 159 _bt_seqadvance(t, flags) 160 BTREE_P t; 161 int flags; 162 { 163 BTHEADER *h; 164 CURSOR *c; 165 index_t index; 166 167 c = &(t->bt_cursor); 168 index = c->c_index; 169 170 if (_bt_getpage(t, c->c_pgno) == RET_ERROR) 171 return (RET_ERROR); 172 h = t->bt_curpage; 173 174 /* by the time we get here, don't need the cursor key anymore */ 175 if (c->c_key != (char *) NULL) 176 (void) free(c->c_key); 177 178 if (flags == R_NEXT) { 179 180 /* 181 * This is a forward scan. If the cursor is pointing 182 * at a virtual record (that is, it was pointing at 183 * a record that got deleted), then we should return 184 * the record it's pointing at now. Otherwise, we 185 * should advance the scan. In either case, we need 186 * to be careful not to run off the end of the current 187 * page. 188 */ 189 190 if (c->c_flags & CRSR_BEFORE) { 191 192 if (index >= NEXTINDEX(h)) { 193 /* out of items on this page, get next page */ 194 if (h->h_nextpg == P_NONE) { 195 /* tell caller we're done... */ 196 c->c_index = NEXTINDEX(h); 197 return (RET_SPECIAL); 198 } 199 200 /* skip empty pages */ 201 do { 202 if (_bt_getpage(t, h->h_nextpg) 203 == RET_ERROR) { 204 c->c_index = NEXTINDEX(h); 205 return (RET_ERROR); 206 } 207 h = t->bt_curpage; 208 c->c_pgno = h->h_pgno; 209 } while (NEXTINDEX(h) == 0 210 && h->h_nextpg != P_NONE); 211 212 if (NEXTINDEX(h) == 0) { 213 /* tell caller we're done */ 214 c->c_index = NEXTINDEX(h); 215 return (RET_SPECIAL); 216 } 217 index = 0; 218 } 219 c->c_flags &= ~CRSR_BEFORE; 220 221 } else if (++index >= NEXTINDEX(h)) { 222 223 /* out of items on this page, get next page */ 224 if (h->h_nextpg == P_NONE) { 225 /* tell caller we're done... */ 226 c->c_index = NEXTINDEX(h); 227 return (RET_SPECIAL); 228 } 229 230 /* skip empty pages */ 231 do { 232 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) { 233 c->c_index = NEXTINDEX(h); 234 return (RET_ERROR); 235 } 236 h = t->bt_curpage; 237 c->c_pgno = h->h_pgno; 238 } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE); 239 240 if (NEXTINDEX(h) == 0) { 241 /* tell caller we're done */ 242 c->c_index = NEXTINDEX(h); 243 return (RET_SPECIAL); 244 } 245 index = 0; 246 } 247 } else if (flags == R_PREV) { 248 249 /* for backward scans, life is substantially easier */ 250 c->c_flags &= ~CRSR_BEFORE; 251 if (c->c_key != (char *) NULL) { 252 (void) free(c->c_key); 253 c->c_key = (char *) NULL; 254 } 255 256 if (index == 0) { 257 258 /* we may be done */ 259 c->c_index = 0; 260 261 /* out of items on this page, get next page */ 262 if (h->h_prevpg == P_NONE) 263 return (RET_SPECIAL); 264 265 /* skip empty pages */ 266 do { 267 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR) 268 return (RET_ERROR); 269 h = t->bt_curpage; 270 c->c_pgno = h->h_pgno; 271 } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE); 272 273 if (NEXTINDEX(h) == 0) 274 return (RET_SPECIAL); 275 276 index = NEXTINDEX(h) - 1; 277 } else 278 --index; 279 } else { 280 /* must specify a direction */ 281 errno = EINVAL; 282 return (RET_ERROR); 283 } 284 285 c->c_index = index; 286 return (RET_SUCCESS); 287 } 288