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.6 (Berkeley) 09/12/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <errno.h> 17 #include <db.h> 18 #include <stdio.h> 19 #include <stdlib.h> 20 #include <stddef.h> 21 #include "btree.h" 22 23 static int bt_seqadv __P((BTREE *, EPG *, int)); 24 static int bt_seqset __P((BTREE *, EPG *, DBT *, int)); 25 26 /* 27 * Sequential scan support. 28 * 29 * The tree can be scanned sequentially, starting from either end of the tree 30 * or from any specific key. A scan request before any scanning is done is 31 * initialized as starting from the least node. 32 * 33 * Each tree has an EPGNO which has the current position of the cursor. The 34 * cursor has to survive deletions/insertions in the tree without losing its 35 * position. This is done by noting deletions without doing them, and then 36 * doing them when the cursor moves (or the tree is closed). 37 */ 38 39 /* 40 * __BT_SEQ -- Btree sequential scan interface. 41 * 42 * Parameters: 43 * dbp: pointer to access method 44 * key: key for positioning and return value 45 * data: data return value 46 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV. 47 * 48 * Returns: 49 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 50 */ 51 int 52 __bt_seq(dbp, key, data, flags) 53 const DB *dbp; 54 DBT *key, *data; 55 u_int flags; 56 { 57 BTREE *t; 58 EPG e; 59 int status; 60 61 /* 62 * If scan unitialized as yet, or starting at a specific record, set 63 * the scan to a specific key. Both bt_seqset and bt_seqadv pin the 64 * page the cursor references if they're successful. 65 */ 66 t = dbp->internal; 67 switch(flags) { 68 case R_NEXT: 69 case R_PREV: 70 if (ISSET(t, BTF_SEQINIT)) { 71 status = bt_seqadv(t, &e, flags); 72 break; 73 } 74 /* FALLTHROUGH */ 75 case R_CURSOR: 76 case R_FIRST: 77 case R_LAST: 78 status = bt_seqset(t, &e, key, flags); 79 break; 80 default: 81 errno = EINVAL; 82 return (RET_ERROR); 83 } 84 85 if (status == RET_SUCCESS) { 86 status = __bt_ret(t, &e, key, data); 87 88 /* Update the actual cursor. */ 89 t->bt_bcursor.pgno = e.page->pgno; 90 t->bt_bcursor.index = e.index; 91 mpool_put(t->bt_mp, e.page, 0); 92 SET(t, BTF_SEQINIT); 93 } 94 return (status); 95 } 96 97 /* 98 * BT_SEQSET -- Set the sequential scan to a specific key. 99 * 100 * Parameters: 101 * t: tree 102 * ep: storage for returned key 103 * key: key for initial scan position 104 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV 105 * 106 * Side effects: 107 * Pins the page the cursor references. 108 * 109 * Returns: 110 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 111 */ 112 static int 113 bt_seqset(t, ep, key, flags) 114 BTREE *t; 115 EPG *ep; 116 DBT *key; 117 int flags; 118 { 119 EPG *e; 120 PAGE *h; 121 pgno_t pg; 122 int exact; 123 124 /* 125 * Delete any already deleted record that we've been saving because 126 * the cursor pointed to it. Since going to a specific key, should 127 * delete any logically deleted records so they aren't found. 128 */ 129 if (ISSET(t, BTF_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) 130 return (RET_ERROR); 131 132 /* 133 * Find the first, last or specific key in the tree and point the cursor 134 * at it. The cursor may not be moved until a new key has been found. 135 */ 136 switch(flags) { 137 case R_CURSOR: /* Keyed scan. */ 138 /* 139 * Find the first instance of the key or the smallest key which 140 * is greater than or equal to the specified key. If run out 141 * of keys, return RET_SPECIAL. 142 */ 143 if (key->data == NULL || key->size == 0) { 144 errno = EINVAL; 145 return (RET_ERROR); 146 } 147 e = __bt_first(t, key, &exact); /* Returns pinned page. */ 148 if (e == NULL) 149 return (RET_ERROR); 150 /* 151 * If at the end of a page, skip any empty pages and find the 152 * next entry. 153 */ 154 if (e->index == NEXTINDEX(e->page)) { 155 h = e->page; 156 do { 157 pg = h->nextpg; 158 mpool_put(t->bt_mp, h, 0); 159 if (pg == P_INVALID) 160 return (RET_SPECIAL); 161 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 162 return (RET_ERROR); 163 } while (NEXTINDEX(h) == 0); 164 e->index = 0; 165 e->page = h; 166 } 167 *ep = *e; 168 break; 169 case R_FIRST: /* First record. */ 170 case R_NEXT: 171 /* Walk down the left-hand side of the tree. */ 172 for (pg = P_ROOT;;) { 173 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 174 return (RET_ERROR); 175 if (h->flags & (P_BLEAF|P_RLEAF)) 176 break; 177 pg = GETBINTERNAL(h, 0)->pgno; 178 mpool_put(t->bt_mp, h, 0); 179 } 180 181 /* Skip any empty pages. */ 182 while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) { 183 pg = h->nextpg; 184 mpool_put(t->bt_mp, h, 0); 185 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 186 return (RET_ERROR); 187 } 188 189 if (NEXTINDEX(h) == 0) { 190 mpool_put(t->bt_mp, h, 0); 191 return (RET_SPECIAL); 192 } 193 194 ep->page = h; 195 ep->index = 0; 196 break; 197 case R_LAST: /* Last record. */ 198 case R_PREV: 199 /* Walk down the right-hand side of the tree. */ 200 for (pg = P_ROOT;;) { 201 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 202 return (RET_ERROR); 203 if (h->flags & (P_BLEAF|P_RLEAF)) 204 break; 205 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; 206 mpool_put(t->bt_mp, h, 0); 207 } 208 209 /* Skip any empty pages. */ 210 while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) { 211 pg = h->prevpg; 212 mpool_put(t->bt_mp, h, 0); 213 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 214 return (RET_ERROR); 215 } 216 217 if (NEXTINDEX(h) == 0) { 218 mpool_put(t->bt_mp, h, 0); 219 return (RET_SPECIAL); 220 } 221 222 ep->page = h; 223 ep->index = NEXTINDEX(h) - 1; 224 break; 225 } 226 return (RET_SUCCESS); 227 } 228 229 /* 230 * BT_SEQADVANCE -- Advance the sequential scan. 231 * 232 * Parameters: 233 * t: tree 234 * flags: R_NEXT, R_PREV 235 * 236 * Side effects: 237 * Pins the page the new key/data record is on. 238 * 239 * Returns: 240 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 241 */ 242 static int 243 bt_seqadv(t, e, flags) 244 BTREE *t; 245 EPG *e; 246 int flags; 247 { 248 EPGNO *c, delc; 249 PAGE *h; 250 index_t index; 251 pgno_t pg; 252 253 /* Save the current cursor if going to delete it. */ 254 c = &t->bt_bcursor; 255 if (ISSET(t, BTF_DELCRSR)) 256 delc = *c; 257 258 if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) 259 return (RET_ERROR); 260 261 /* 262 * Find the next/previous record in the tree and point the cursor at it. 263 * The cursor may not be moved until a new key has been found. 264 */ 265 index = c->index; 266 switch(flags) { 267 case R_NEXT: /* Next record. */ 268 if (++index == NEXTINDEX(h)) { 269 do { 270 pg = h->nextpg; 271 mpool_put(t->bt_mp, h, 0); 272 if (pg == P_INVALID) 273 return (RET_SPECIAL); 274 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 275 return (RET_ERROR); 276 } while (NEXTINDEX(h) == 0); 277 index = 0; 278 } 279 break; 280 case R_PREV: /* Previous record. */ 281 if (index-- == 0) { 282 do { 283 pg = h->prevpg; 284 mpool_put(t->bt_mp, h, 0); 285 if (pg == P_INVALID) 286 return (RET_SPECIAL); 287 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 288 return (RET_ERROR); 289 } while (NEXTINDEX(h) == 0); 290 index = NEXTINDEX(h) - 1; 291 } 292 break; 293 } 294 295 e->page = h; 296 e->index = index; 297 298 /* 299 * Delete any already deleted record that we've been saving because the 300 * cursor pointed to it. This could cause the new index to be shifted 301 * down by one if the record we're deleting is on the same page and has 302 * a larger index. 303 */ 304 if (ISSET(t, BTF_DELCRSR)) { 305 UNSET(t, BTF_DELCRSR); /* Don't try twice. */ 306 if (c->pgno == delc.pgno && c->index > delc.index) 307 --c->index; 308 if (__bt_crsrdel(t, &delc)) 309 return (RET_ERROR); 310 } 311 return (RET_SUCCESS); 312 } 313 314 /* 315 * __BT_CRSRDEL -- Delete the record referenced by the cursor. 316 * 317 * Parameters: 318 * t: tree 319 * 320 * Returns: 321 * RET_ERROR, RET_SUCCESS 322 */ 323 int 324 __bt_crsrdel(t, c) 325 BTREE *t; 326 EPGNO *c; 327 { 328 PAGE *h; 329 int status; 330 331 UNSET(t, BTF_DELCRSR); /* Don't try twice. */ 332 if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) 333 return (RET_ERROR); 334 status = __bt_dleaf(t, h, c->index); 335 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 336 return (status); 337 } 338