1 /*- 2 * Copyright (c) 1990, 1993, 1994 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 * @(#)bt_seq.c 8.7 (Berkeley) 7/20/94 37 */ 38 39 #include <sys/types.h> 40 41 #include <errno.h> 42 #include <stddef.h> 43 #include <stdio.h> 44 #include <stdlib.h> 45 46 #include <db.h> 47 #include "btree.h" 48 49 static int __bt_first __P((BTREE *, const DBT *, EPG *, int *)); 50 static int __bt_seqadv __P((BTREE *, EPG *, int)); 51 static int __bt_seqset __P((BTREE *, EPG *, DBT *, int)); 52 53 /* 54 * Sequential scan support. 55 * 56 * The tree can be scanned sequentially, starting from either end of the 57 * tree or from any specific key. A scan request before any scanning is 58 * done is initialized as starting from the least node. 59 */ 60 61 /* 62 * __bt_seq -- 63 * Btree sequential scan interface. 64 * 65 * Parameters: 66 * dbp: pointer to access method 67 * key: key for positioning and return value 68 * data: data return value 69 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV. 70 * 71 * Returns: 72 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 73 */ 74 int 75 __bt_seq(dbp, key, data, flags) 76 const DB *dbp; 77 DBT *key, *data; 78 u_int flags; 79 { 80 BTREE *t; 81 EPG e; 82 int status; 83 84 t = dbp->internal; 85 86 /* Toss any page pinned across calls. */ 87 if (t->bt_pinned != NULL) { 88 mpool_put(t->bt_mp, t->bt_pinned, 0); 89 t->bt_pinned = NULL; 90 } 91 92 /* 93 * If scan unitialized as yet, or starting at a specific record, set 94 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin 95 * the page the cursor references if they're successful. 96 */ 97 switch (flags) { 98 case R_NEXT: 99 case R_PREV: 100 if (F_ISSET(&t->bt_cursor, CURS_INIT)) { 101 status = __bt_seqadv(t, &e, flags); 102 break; 103 } 104 /* FALLTHROUGH */ 105 case R_FIRST: 106 case R_LAST: 107 case R_CURSOR: 108 status = __bt_seqset(t, &e, key, flags); 109 break; 110 default: 111 errno = EINVAL; 112 return (RET_ERROR); 113 } 114 115 if (status == RET_SUCCESS) { 116 __bt_setcur(t, e.page->pgno, e.index); 117 118 status = 119 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0); 120 121 /* 122 * If the user is doing concurrent access, we copied the 123 * key/data, toss the page. 124 */ 125 if (F_ISSET(t, B_DB_LOCK)) 126 mpool_put(t->bt_mp, e.page, 0); 127 else 128 t->bt_pinned = e.page; 129 } 130 return (status); 131 } 132 133 /* 134 * __bt_seqset -- 135 * Set the sequential scan to a specific key. 136 * 137 * Parameters: 138 * t: tree 139 * ep: storage for returned key 140 * key: key for initial scan position 141 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV 142 * 143 * Side effects: 144 * Pins the page the cursor references. 145 * 146 * Returns: 147 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 148 */ 149 static int 150 __bt_seqset(t, ep, key, flags) 151 BTREE *t; 152 EPG *ep; 153 DBT *key; 154 int flags; 155 { 156 PAGE *h; 157 pgno_t pg; 158 int exact; 159 160 /* 161 * Find the first, last or specific key in the tree and point the 162 * cursor at it. The cursor may not be moved until a new key has 163 * been found. 164 */ 165 switch (flags) { 166 case R_CURSOR: /* Keyed scan. */ 167 /* 168 * Find the first instance of the key or the smallest key 169 * which is greater than or equal to the specified key. 170 */ 171 if (key->data == NULL || key->size == 0) { 172 errno = EINVAL; 173 return (RET_ERROR); 174 } 175 return (__bt_first(t, key, ep, &exact)); 176 case R_FIRST: /* First record. */ 177 case R_NEXT: 178 /* Walk down the left-hand side of the tree. */ 179 for (pg = P_ROOT;;) { 180 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 181 return (RET_ERROR); 182 183 /* Check for an empty tree. */ 184 if (NEXTINDEX(h) == 0) { 185 mpool_put(t->bt_mp, h, 0); 186 return (RET_SPECIAL); 187 } 188 189 if (h->flags & (P_BLEAF | P_RLEAF)) 190 break; 191 pg = GETBINTERNAL(h, 0)->pgno; 192 mpool_put(t->bt_mp, h, 0); 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 204 /* Check for an empty tree. */ 205 if (NEXTINDEX(h) == 0) { 206 mpool_put(t->bt_mp, h, 0); 207 return (RET_SPECIAL); 208 } 209 210 if (h->flags & (P_BLEAF | P_RLEAF)) 211 break; 212 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; 213 mpool_put(t->bt_mp, h, 0); 214 } 215 216 ep->page = h; 217 ep->index = NEXTINDEX(h) - 1; 218 break; 219 } 220 return (RET_SUCCESS); 221 } 222 223 /* 224 * __bt_seqadvance -- 225 * Advance the sequential scan. 226 * 227 * Parameters: 228 * t: tree 229 * flags: R_NEXT, R_PREV 230 * 231 * Side effects: 232 * Pins the page the new key/data record is on. 233 * 234 * Returns: 235 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 236 */ 237 static int 238 __bt_seqadv(t, ep, flags) 239 BTREE *t; 240 EPG *ep; 241 int flags; 242 { 243 CURSOR *c; 244 PAGE *h; 245 indx_t index; 246 pgno_t pg; 247 int exact; 248 249 /* 250 * There are a couple of states that we can be in. The cursor has 251 * been initialized by the time we get here, but that's all we know. 252 */ 253 c = &t->bt_cursor; 254 255 /* 256 * The cursor was deleted where there weren't any duplicate records, 257 * so the key was saved. Find out where that key would go in the 258 * current tree. It doesn't matter if the returned key is an exact 259 * match or not -- if it's an exact match, the record was added after 260 * the delete so we can just return it. If not, as long as there's 261 * a record there, return it. 262 */ 263 if (F_ISSET(c, CURS_ACQUIRE)) 264 return (__bt_first(t, &c->key, ep, &exact)); 265 266 /* Get the page referenced by the cursor. */ 267 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) 268 return (RET_ERROR); 269 270 /* 271 * Find the next/previous record in the tree and point the cursor at 272 * it. The cursor may not be moved until a new key has been found. 273 */ 274 switch (flags) { 275 case R_NEXT: /* Next record. */ 276 /* 277 * The cursor was deleted in duplicate records, and moved 278 * forward to a record that has yet to be returned. Clear 279 * that flag, and return the record. 280 */ 281 if (F_ISSET(c, CURS_AFTER)) 282 goto usecurrent; 283 index = c->pg.index; 284 if (++index == NEXTINDEX(h)) { 285 pg = h->nextpg; 286 mpool_put(t->bt_mp, h, 0); 287 if (pg == P_INVALID) 288 return (RET_SPECIAL); 289 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 290 return (RET_ERROR); 291 index = 0; 292 } 293 break; 294 case R_PREV: /* Previous record. */ 295 /* 296 * The cursor was deleted in duplicate records, and moved 297 * backward to a record that has yet to be returned. Clear 298 * that flag, and return the record. 299 */ 300 if (F_ISSET(c, CURS_BEFORE)) { 301 usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE); 302 ep->page = h; 303 ep->index = c->pg.index; 304 return (RET_SUCCESS); 305 } 306 index = c->pg.index; 307 if (index == 0) { 308 pg = h->prevpg; 309 mpool_put(t->bt_mp, h, 0); 310 if (pg == P_INVALID) 311 return (RET_SPECIAL); 312 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 313 return (RET_ERROR); 314 index = NEXTINDEX(h) - 1; 315 } else 316 --index; 317 break; 318 } 319 320 ep->page = h; 321 ep->index = index; 322 return (RET_SUCCESS); 323 } 324 325 /* 326 * __bt_first -- 327 * Find the first entry. 328 * 329 * Parameters: 330 * t: the tree 331 * key: the key 332 * erval: return EPG 333 * exactp: pointer to exact match flag 334 * 335 * Returns: 336 * The first entry in the tree greater than or equal to key, 337 * or RET_SPECIAL if no such key exists. 338 */ 339 static int 340 __bt_first(t, key, erval, exactp) 341 BTREE *t; 342 const DBT *key; 343 EPG *erval; 344 int *exactp; 345 { 346 PAGE *h; 347 EPG *ep, save; 348 pgno_t pg; 349 350 /* 351 * Find any matching record; __bt_search pins the page. 352 * 353 * If it's an exact match and duplicates are possible, walk backwards 354 * in the tree until we find the first one. Otherwise, make sure it's 355 * a valid key (__bt_search may return an index just past the end of a 356 * page) and return it. 357 */ 358 if ((ep = __bt_search(t, key, exactp)) == NULL) 359 return (0); 360 if (*exactp) { 361 if (F_ISSET(t, B_NODUPS)) { 362 *erval = *ep; 363 return (RET_SUCCESS); 364 } 365 366 /* 367 * Walk backwards, as long as the entry matches and there are 368 * keys left in the tree. Save a copy of each match in case 369 * we go too far. 370 */ 371 save = *ep; 372 h = ep->page; 373 do { 374 if (save.page->pgno != ep->page->pgno) { 375 mpool_put(t->bt_mp, save.page, 0); 376 save = *ep; 377 } else 378 save.index = ep->index; 379 380 /* 381 * Don't unpin the page the last (or original) match 382 * was on, but make sure it's unpinned if an error 383 * occurs. 384 */ 385 if (ep->index == 0) { 386 if (h->prevpg == P_INVALID) 387 break; 388 if (h->pgno != save.page->pgno) 389 mpool_put(t->bt_mp, h, 0); 390 if ((h = mpool_get(t->bt_mp, 391 h->prevpg, 0)) == NULL) { 392 if (h->pgno == save.page->pgno) 393 mpool_put(t->bt_mp, 394 save.page, 0); 395 return (RET_ERROR); 396 } 397 ep->page = h; 398 ep->index = NEXTINDEX(h); 399 } 400 --ep->index; 401 } while (__bt_cmp(t, key, ep) == 0); 402 403 /* 404 * Reach here with the last page that was looked at pinned, 405 * which may or may not be the same as the last (or original) 406 * match page. If it's not useful, release it. 407 */ 408 if (h->pgno != save.page->pgno) 409 mpool_put(t->bt_mp, h, 0); 410 411 *erval = save; 412 return (RET_SUCCESS); 413 } 414 415 /* If at the end of a page, find the next entry. */ 416 if (ep->index == NEXTINDEX(ep->page)) { 417 h = ep->page; 418 pg = h->nextpg; 419 mpool_put(t->bt_mp, h, 0); 420 if (pg == P_INVALID) 421 return (RET_SPECIAL); 422 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 423 return (RET_ERROR); 424 ep->index = 0; 425 ep->page = h; 426 } 427 *erval = *ep; 428 return (RET_SUCCESS); 429 } 430 431 /* 432 * __bt_setcur -- 433 * Set the cursor to an entry in the tree. 434 * 435 * Parameters: 436 * t: the tree 437 * pgno: page number 438 * index: page index 439 */ 440 void 441 __bt_setcur(t, pgno, index) 442 BTREE *t; 443 pgno_t pgno; 444 u_int index; 445 { 446 /* Lose any already deleted key. */ 447 if (t->bt_cursor.key.data != NULL) { 448 free(t->bt_cursor.key.data); 449 t->bt_cursor.key.size = 0; 450 t->bt_cursor.key.data = NULL; 451 } 452 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); 453 454 /* Update the cursor. */ 455 t->bt_cursor.pg.pgno = pgno; 456 t->bt_cursor.pg.index = index; 457 F_SET(&t->bt_cursor, CURS_INIT); 458 } 459