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