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 * 4. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33#if defined(LIBC_SCCS) && !defined(lint) 34static char sccsid[] = "@(#)bt_seq.c 8.7 (Berkeley) 7/20/94"; 35#endif /* LIBC_SCCS and not lint */ 36#include <sys/cdefs.h> 37__FBSDID("$FreeBSD$"); 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 49static int __bt_first(BTREE *, const DBT *, EPG *, int *); 50static int __bt_seqadv(BTREE *, EPG *, int); 51static int __bt_seqset(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 */ 74int 75__bt_seq(const DB *dbp, DBT *key, DBT *data, u_int flags) 76{ 77 BTREE *t; 78 EPG e; 79 int status; 80 81 t = dbp->internal; 82 83 /* Toss any page pinned across calls. */ 84 if (t->bt_pinned != NULL) { 85 mpool_put(t->bt_mp, t->bt_pinned, 0); 86 t->bt_pinned = NULL; 87 } 88 89 /* 90 * If scan unitialized as yet, or starting at a specific record, set 91 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin 92 * the page the cursor references if they're successful. 93 */ 94 switch (flags) { 95 case R_NEXT: 96 case R_PREV: 97 if (F_ISSET(&t->bt_cursor, CURS_INIT)) { 98 status = __bt_seqadv(t, &e, flags); 99 break; 100 } 101 /* FALLTHROUGH */ 102 case R_FIRST: 103 case R_LAST: 104 case R_CURSOR: 105 status = __bt_seqset(t, &e, key, flags); 106 break; 107 default: 108 errno = EINVAL; 109 return (RET_ERROR); 110 } 111 112 if (status == RET_SUCCESS) { 113 __bt_setcur(t, e.page->pgno, e.index); 114 115 status = 116 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0); 117 118 /* 119 * If the user is doing concurrent access, we copied the 120 * key/data, toss the page. 121 */ 122 if (F_ISSET(t, B_DB_LOCK)) 123 mpool_put(t->bt_mp, e.page, 0); 124 else 125 t->bt_pinned = e.page; 126 } 127 return (status); 128} 129 130/* 131 * __bt_seqset -- 132 * Set the sequential scan to a specific key. 133 * 134 * Parameters: 135 * t: tree 136 * ep: storage for returned key 137 * key: key for initial scan position 138 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV 139 * 140 * Side effects: 141 * Pins the page the cursor references. 142 * 143 * Returns: 144 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 145 */ 146static int 147__bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags) 148{ 149 PAGE *h; 150 pgno_t pg; 151 int exact; 152 153 /* 154 * Find the first, last or specific key in the tree and point the 155 * cursor at it. The cursor may not be moved until a new key has 156 * been found. 157 */ 158 switch (flags) { 159 case R_CURSOR: /* Keyed scan. */ 160 /* 161 * Find the first instance of the key or the smallest key 162 * which is greater than or equal to the specified key. 163 */ 164 if (key->data == NULL || key->size == 0) { 165 errno = EINVAL; 166 return (RET_ERROR); 167 } 168 return (__bt_first(t, key, ep, &exact)); 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 176 /* Check for an empty tree. */ 177 if (NEXTINDEX(h) == 0) { 178 mpool_put(t->bt_mp, h, 0); 179 return (RET_SPECIAL); 180 } 181 182 if (h->flags & (P_BLEAF | P_RLEAF)) 183 break; 184 pg = GETBINTERNAL(h, 0)->pgno; 185 mpool_put(t->bt_mp, h, 0); 186 } 187 ep->page = h; 188 ep->index = 0; 189 break; 190 case R_LAST: /* Last record. */ 191 case R_PREV: 192 /* Walk down the right-hand side of the tree. */ 193 for (pg = P_ROOT;;) { 194 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 195 return (RET_ERROR); 196 197 /* Check for an empty tree. */ 198 if (NEXTINDEX(h) == 0) { 199 mpool_put(t->bt_mp, h, 0); 200 return (RET_SPECIAL); 201 } 202 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 ep->page = h; 210 ep->index = NEXTINDEX(h) - 1; 211 break; 212 } 213 return (RET_SUCCESS); 214} 215 216/* 217 * __bt_seqadvance -- 218 * Advance the sequential scan. 219 * 220 * Parameters: 221 * t: tree 222 * flags: R_NEXT, R_PREV 223 * 224 * Side effects: 225 * Pins the page the new key/data record is on. 226 * 227 * Returns: 228 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 229 */ 230static int 231__bt_seqadv(BTREE *t, EPG *ep, int flags) 232{ 233 CURSOR *c; 234 PAGE *h; 235 indx_t idx; 236 pgno_t pg; 237 int exact; 238 239 /* 240 * There are a couple of states that we can be in. The cursor has 241 * been initialized by the time we get here, but that's all we know. 242 */ 243 c = &t->bt_cursor; 244 245 /* 246 * The cursor was deleted where there weren't any duplicate records, 247 * so the key was saved. Find out where that key would go in the 248 * current tree. It doesn't matter if the returned key is an exact 249 * match or not -- if it's an exact match, the record was added after 250 * the delete so we can just return it. If not, as long as there's 251 * a record there, return it. 252 */ 253 if (F_ISSET(c, CURS_ACQUIRE)) 254 return (__bt_first(t, &c->key, ep, &exact)); 255 256 /* Get the page referenced by the cursor. */ 257 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) 258 return (RET_ERROR); 259 260 /* 261 * Find the next/previous record in the tree and point the cursor at 262 * it. The cursor may not be moved until a new key has been found. 263 */ 264 switch (flags) { 265 case R_NEXT: /* Next record. */ 266 /* 267 * The cursor was deleted in duplicate records, and moved 268 * forward to a record that has yet to be returned. Clear 269 * that flag, and return the record. 270 */ 271 if (F_ISSET(c, CURS_AFTER)) 272 goto usecurrent; 273 idx = c->pg.index; 274 if (++idx == NEXTINDEX(h)) { 275 pg = h->nextpg; 276 mpool_put(t->bt_mp, h, 0); 277 if (pg == P_INVALID) 278 return (RET_SPECIAL); 279 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 280 return (RET_ERROR); 281 idx = 0; 282 } 283 break; 284 case R_PREV: /* Previous record. */ 285 /* 286 * The cursor was deleted in duplicate records, and moved 287 * backward to a record that has yet to be returned. Clear 288 * that flag, and return the record. 289 */ 290 if (F_ISSET(c, CURS_BEFORE)) { 291usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE); 292 ep->page = h; 293 ep->index = c->pg.index; 294 return (RET_SUCCESS); 295 } 296 idx = c->pg.index; 297 if (idx == 0) { 298 pg = h->prevpg; 299 mpool_put(t->bt_mp, h, 0); 300 if (pg == P_INVALID) 301 return (RET_SPECIAL); 302 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 303 return (RET_ERROR); 304 idx = NEXTINDEX(h) - 1; 305 } else 306 --idx; 307 break; 308 } 309 310 ep->page = h; 311 ep->index = idx; 312 return (RET_SUCCESS); 313} 314 315/* 316 * __bt_first -- 317 * Find the first entry. 318 * 319 * Parameters: 320 * t: the tree 321 * key: the key 322 * erval: return EPG 323 * exactp: pointer to exact match flag 324 * 325 * Returns: 326 * The first entry in the tree greater than or equal to key, 327 * or RET_SPECIAL if no such key exists. 328 */ 329static int 330__bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp) 331{ 332 PAGE *h; 333 EPG *ep, save; 334 pgno_t pg; 335 336 /* 337 * Find any matching record; __bt_search pins the page. 338 * 339 * If it's an exact match and duplicates are possible, walk backwards 340 * in the tree until we find the first one. Otherwise, make sure it's 341 * a valid key (__bt_search may return an index just past the end of a 342 * page) and return it. 343 */ 344 if ((ep = __bt_search(t, key, exactp)) == NULL) 345 return (0); 346 if (*exactp) { 347 if (F_ISSET(t, B_NODUPS)) { 348 *erval = *ep; 349 return (RET_SUCCESS); 350 } 351 352 /* 353 * Walk backwards, as long as the entry matches and there are 354 * keys left in the tree. Save a copy of each match in case 355 * we go too far. 356 */ 357 save = *ep; 358 h = ep->page; 359 do { 360 if (save.page->pgno != ep->page->pgno) { 361 mpool_put(t->bt_mp, save.page, 0); 362 save = *ep; 363 } else 364 save.index = ep->index; 365 366 /* 367 * Don't unpin the page the last (or original) match 368 * was on, but make sure it's unpinned if an error 369 * occurs. 370 */ 371 if (ep->index == 0) { 372 if (h->prevpg == P_INVALID) 373 break; 374 if (h->pgno != save.page->pgno) 375 mpool_put(t->bt_mp, h, 0); 376 if ((h = mpool_get(t->bt_mp, 377 h->prevpg, 0)) == NULL) { 378 if (h->pgno == save.page->pgno) 379 mpool_put(t->bt_mp, 380 save.page, 0); 381 return (RET_ERROR); 382 } 383 ep->page = h; 384 ep->index = NEXTINDEX(h); 385 } 386 --ep->index; 387 } while (__bt_cmp(t, key, ep) == 0); 388 389 /* 390 * Reach here with the last page that was looked at pinned, 391 * which may or may not be the same as the last (or original) 392 * match page. If it's not useful, release it. 393 */ 394 if (h->pgno != save.page->pgno) 395 mpool_put(t->bt_mp, h, 0); 396 397 *erval = save; 398 return (RET_SUCCESS); 399 } 400 401 /* If at the end of a page, find the next entry. */ 402 if (ep->index == NEXTINDEX(ep->page)) { 403 h = ep->page; 404 pg = h->nextpg; 405 mpool_put(t->bt_mp, h, 0); 406 if (pg == P_INVALID) 407 return (RET_SPECIAL); 408 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 409 return (RET_ERROR); 410 ep->index = 0; 411 ep->page = h; 412 } 413 *erval = *ep; 414 return (RET_SUCCESS); 415} 416 417/* 418 * __bt_setcur -- 419 * Set the cursor to an entry in the tree. 420 * 421 * Parameters: 422 * t: the tree 423 * pgno: page number 424 * idx: page index 425 */ 426void 427__bt_setcur(BTREE *t, pgno_t pgno, u_int idx) 428{ 429 /* Lose any already deleted key. */ 430 if (t->bt_cursor.key.data != NULL) { 431 free(t->bt_cursor.key.data); 432 t->bt_cursor.key.size = 0; 433 t->bt_cursor.key.data = NULL; 434 } 435 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); 436 437 /* Update the cursor. */ 438 t->bt_cursor.pg.pgno = pgno; 439 t->bt_cursor.pg.index = idx; 440 F_SET(&t->bt_cursor, CURS_INIT); 441} 442