-: 0:Source:bt_seq.c -: 0:Graph:/var/tsitkova/Sources/v10/trunk/src/plugins/kdb/db2/libdb2/btree/bt_seq.so.gcno -: 0:Data:/var/tsitkova/Sources/v10/trunk/src/plugins/kdb/db2/libdb2/btree/bt_seq.so.gcda -: 0:Runs:1656 -: 0:Programs:2 -: 1:/* -: 2: * Copyright (C) 2002 by the Massachusetts Institute of Technology. -: 3: * All rights reserved. -: 4: * -: 5: * Export of this software from the United States of America may -: 6: * require a specific license from the United States Government. -: 7: * It is the responsibility of any person or organization contemplating -: 8: * export to obtain such a license before exporting. -: 9: * -: 10: * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and -: 11: * distribute this software and its documentation for any purpose and -: 12: * without fee is hereby granted, provided that the above copyright -: 13: * notice appear in all copies and that both that copyright notice and -: 14: * this permission notice appear in supporting documentation, and that -: 15: * the name of M.I.T. not be used in advertising or publicity pertaining -: 16: * to distribution of the software without specific, written prior -: 17: * permission. Furthermore if you modify this software you must label -: 18: * your software as modified software and not distribute it in such a -: 19: * fashion that it might be confused with the original M.I.T. software. -: 20: * M.I.T. makes no representations about the suitability of -: 21: * this software for any purpose. It is provided "as is" without express -: 22: * or implied warranty. -: 23: */ -: 24: -: 25:/*- -: 26: * Copyright (c) 1990, 1993, 1994 -: 27: * The Regents of the University of California. All rights reserved. -: 28: * -: 29: * This code is derived from software contributed to Berkeley by -: 30: * Mike Olson. -: 31: * -: 32: * Redistribution and use in source and binary forms, with or without -: 33: * modification, are permitted provided that the following conditions -: 34: * are met: -: 35: * 1. Redistributions of source code must retain the above copyright -: 36: * notice, this list of conditions and the following disclaimer. -: 37: * 2. Redistributions in binary form must reproduce the above copyright -: 38: * notice, this list of conditions and the following disclaimer in the -: 39: * documentation and/or other materials provided with the distribution. -: 40: * 3. All advertising materials mentioning features or use of this software -: 41: * must display the following acknowledgement: -: 42: * This product includes software developed by the University of -: 43: * California, Berkeley and its contributors. -: 44: * 4. Neither the name of the University nor the names of its contributors -: 45: * may be used to endorse or promote products derived from this software -: 46: * without specific prior written permission. -: 47: * -: 48: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -: 49: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -: 50: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -: 51: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -: 52: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -: 53: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -: 54: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -: 55: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -: 56: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -: 57: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -: 58: * SUCH DAMAGE. -: 59: */ -: 60: -: 61:#if defined(LIBC_SCCS) && !defined(lint) -: 62:static char sccsid[] = "@(#)bt_seq.c 8.9 (Berkeley) 6/20/95"; -: 63:#endif /* LIBC_SCCS and not lint */ -: 64: -: 65:#include -: 66: -: 67:#include -: 68:#include -: 69:#include -: 70:#include -: 71:#include -: 72: -: 73:#include "db-int.h" -: 74:#include "btree.h" -: 75: -: 76:static int __bt_first __P((BTREE *, const DBT *, EPG *, int *)); -: 77:static int __bt_seqadv __P((BTREE *, EPG *, int)); -: 78:static int __bt_seqset __P((BTREE *, EPG *, DBT *, int)); -: 79: -: 80:/* -: 81: * Sequential scan support. -: 82: * -: 83: * The tree can be scanned sequentially, starting from either end of the -: 84: * tree or from any specific key. A scan request before any scanning is -: 85: * done is initialized as starting from the least node. -: 86: */ -: 87: -: 88:/* -: 89: * __bt_seq -- -: 90: * Btree sequential scan interface. -: 91: * -: 92: * Parameters: -: 93: * dbp: pointer to access method -: 94: * key: key for positioning and return value -: 95: * data: data return value -: 96: * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV. -: 97: * -: 98: * Returns: -: 99: * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. -: 100: */ -: 101:int 8621: 102:__bt_seq(dbp, key, data, flags) -: 103: const DB *dbp; -: 104: DBT *key, *data; -: 105: u_int flags; -: 106:{ -: 107: BTREE *t; -: 108: EPG e; -: 109: int status; -: 110: 8621: 111: t = dbp->internal; -: 112: -: 113: /* Toss any page pinned across calls. */ 8621: 114: if (t->bt_pinned != NULL) { 7974: 115: mpool_put(t->bt_mp, t->bt_pinned, 0); 7974: 116: t->bt_pinned = NULL; -: 117: } -: 118: -: 119: /* -: 120: * If scan unitialized as yet, or starting at a specific record, set -: 121: * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin -: 122: * the page the cursor references if they're successful. -: 123: */ 8621: 124: switch (flags) { -: 125: case R_NEXT: -: 126: case R_PREV: 7974: 127: if (F_ISSET(&t->bt_cursor, CURS_INIT)) { 7974: 128: status = __bt_seqadv(t, &e, flags); 7974: 129: break; -: 130: } -: 131: /* FALLTHROUGH */ -: 132: case R_FIRST: -: 133: case R_LAST: -: 134: case R_CURSOR: 647: 135: status = __bt_seqset(t, &e, key, flags); 647: 136: break; -: 137: default: #####: 138: errno = EINVAL; #####: 139: return (RET_ERROR); -: 140: } -: 141: 8621: 142: if (status == RET_SUCCESS) { 7974: 143: __bt_setcur(t, e.page->pgno, e.index); -: 144: 7974: 145: status = 7974: 146: __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0); -: 147: -: 148: /* -: 149: * If the user is doing concurrent access, we copied the -: 150: * key/data, toss the page. -: 151: */ 7974: 152: if (F_ISSET(t, B_DB_LOCK)) #####: 153: mpool_put(t->bt_mp, e.page, 0); -: 154: else 7974: 155: t->bt_pinned = e.page; -: 156: } 8621: 157: return (status); -: 158:} -: 159: -: 160:/* -: 161: * __bt_seqset -- -: 162: * Set the sequential scan to a specific key. -: 163: * -: 164: * Parameters: -: 165: * t: tree -: 166: * ep: storage for returned key -: 167: * key: key for initial scan position -: 168: * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV -: 169: * -: 170: * Side effects: -: 171: * Pins the page the cursor references. -: 172: * -: 173: * Returns: -: 174: * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. -: 175: */ -: 176:static int 647: 177:__bt_seqset(t, ep, key, flags) -: 178: BTREE *t; -: 179: EPG *ep; -: 180: DBT *key; -: 181: int flags; -: 182:{ -: 183: PAGE *h; -: 184: db_pgno_t pg; -: 185: int exact; -: 186: -: 187: /* -: 188: * Find the first, last or specific key in the tree and point the -: 189: * cursor at it. The cursor may not be moved until a new key has -: 190: * been found. -: 191: */ 647: 192: switch (flags) { -: 193: case R_CURSOR: /* Keyed scan. */ -: 194: /* -: 195: * Find the first instance of the key or the smallest key -: 196: * which is greater than or equal to the specified key. -: 197: */ #####: 198: if (key->data == NULL || key->size == 0) { #####: 199: errno = EINVAL; #####: 200: return (RET_ERROR); -: 201: } #####: 202: return (__bt_first(t, key, ep, &exact)); -: 203: case R_FIRST: /* First record. */ -: 204: case R_NEXT: -: 205: /* Walk down the left-hand side of the tree. */ 647: 206: for (pg = P_ROOT;;) { 912: 207: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 208: return (RET_ERROR); -: 209: -: 210: /* Check for an empty tree. */ 912: 211: if (NEXTINDEX(h) == 0) { 4: 212: mpool_put(t->bt_mp, h, 0); 4: 213: return (RET_SPECIAL); -: 214: } -: 215: 908: 216: if (h->flags & (P_BLEAF | P_RLEAF)) -: 217: break; 265: 218: pg = GETBINTERNAL(h, 0)->pgno; 265: 219: mpool_put(t->bt_mp, h, 0); 265: 220: } 643: 221: ep->page = h; 643: 222: ep->index = 0; 643: 223: break; -: 224: case R_LAST: /* Last record. */ -: 225: case R_PREV: -: 226: /* Walk down the right-hand side of the tree. */ #####: 227: for (pg = P_ROOT;;) { #####: 228: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 229: return (RET_ERROR); -: 230: -: 231: /* Check for an empty tree. */ #####: 232: if (NEXTINDEX(h) == 0) { #####: 233: mpool_put(t->bt_mp, h, 0); #####: 234: return (RET_SPECIAL); -: 235: } -: 236: #####: 237: if (h->flags & (P_BLEAF | P_RLEAF)) -: 238: break; #####: 239: pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; #####: 240: mpool_put(t->bt_mp, h, 0); #####: 241: } -: 242: #####: 243: ep->page = h; #####: 244: ep->index = NEXTINDEX(h) - 1; -: 245: break; -: 246: } 643: 247: return (RET_SUCCESS); -: 248:} -: 249: -: 250:/* -: 251: * __bt_seqadvance -- -: 252: * Advance the sequential scan. -: 253: * -: 254: * Parameters: -: 255: * t: tree -: 256: * flags: R_NEXT, R_PREV -: 257: * -: 258: * Side effects: -: 259: * Pins the page the new key/data record is on. -: 260: * -: 261: * Returns: -: 262: * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. -: 263: */ -: 264:static int 7974: 265:__bt_seqadv(t, ep, flags) -: 266: BTREE *t; -: 267: EPG *ep; -: 268: int flags; -: 269:{ -: 270: CURSOR *c; -: 271: PAGE *h; 7974: 272: indx_t idx = 0; -: 273: db_pgno_t pg; -: 274: int exact, rval; -: 275: -: 276: /* -: 277: * There are a couple of states that we can be in. The cursor has -: 278: * been initialized by the time we get here, but that's all we know. -: 279: */ 7974: 280: c = &t->bt_cursor; -: 281: -: 282: /* -: 283: * The cursor was deleted and there weren't any duplicate records, -: 284: * so the cursor's key was saved. Find out where that key would -: 285: * be in the current tree. If the returned key is an exact match, -: 286: * it means that a key/data pair was inserted into the tree after -: 287: * the delete. We could reasonably return the key, but the problem -: 288: * is that this is the access pattern we'll see if the user is -: 289: * doing seq(..., R_NEXT)/put(..., 0) pairs, i.e. the put deletes -: 290: * the cursor record and then replaces it, so the cursor was saved, -: 291: * and we'll simply return the same "new" record until the user -: 292: * notices and doesn't do a put() of it. Since the key is an exact -: 293: * match, we could as easily put the new record before the cursor, -: 294: * and we've made no guarantee to return it. So, move forward or -: 295: * back a record if it's an exact match. -: 296: * -: 297: * XXX -: 298: * In the current implementation, put's to the cursor are done with -: 299: * delete/add pairs. This has two consequences. First, it means -: 300: * that seq(..., R_NEXT)/put(..., R_CURSOR) pairs are going to exhibit -: 301: * the same behavior as above. Second, you can return the same key -: 302: * twice if you have duplicate records. The scenario is that the -: 303: * cursor record is deleted, moving the cursor forward or backward -: 304: * to a duplicate. The add then inserts the new record at a location -: 305: * ahead of the cursor because duplicates aren't sorted in any way, -: 306: * and the new record is later returned. This has to be fixed at some -: 307: * point. -: 308: */ 7974: 309: if (F_ISSET(c, CURS_ACQUIRE)) { #####: 310: if ((rval = __bt_first(t, &c->key, ep, &exact)) == RET_ERROR) #####: 311: return (RET_ERROR); #####: 312: if (!exact) #####: 313: return (rval); -: 314: /* -: 315: * XXX -: 316: * Kluge -- get, release, get the page. -: 317: */ #####: 318: c->pg.pgno = ep->page->pgno; #####: 319: c->pg.index = ep->index; #####: 320: mpool_put(t->bt_mp, ep->page, 0); -: 321: } -: 322: -: 323: /* Get the page referenced by the cursor. */ 7974: 324: if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) #####: 325: return (RET_ERROR); -: 326: -: 327: /* -: 328: * Find the next/previous record in the tree and point the cursor at -: 329: * it. The cursor may not be moved until a new key has been found. -: 330: */ 7974: 331: switch (flags) { -: 332: case R_NEXT: /* Next record. */ -: 333: /* -: 334: * The cursor was deleted in duplicate records, and moved -: 335: * forward to a record that has yet to be returned. Clear -: 336: * that flag, and return the record. -: 337: */ 7974: 338: if (F_ISSET(c, CURS_AFTER)) #####: 339: goto usecurrent; 7974: 340: idx = c->pg.index; 7974: 341: if (++idx == NEXTINDEX(h)) { 2349: 342: pg = h->nextpg; 2349: 343: mpool_put(t->bt_mp, h, 0); 2349: 344: if (pg == P_INVALID) 643: 345: return (RET_SPECIAL); 1706: 346: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 347: return (RET_ERROR); 1706: 348: idx = 0; -: 349: } 7331: 350: break; -: 351: case R_PREV: /* Previous record. */ -: 352: /* -: 353: * The cursor was deleted in duplicate records, and moved -: 354: * backward to a record that has yet to be returned. Clear -: 355: * that flag, and return the record. -: 356: */ #####: 357: if (F_ISSET(c, CURS_BEFORE)) { #####: 358:usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE); #####: 359: ep->page = h; #####: 360: ep->index = c->pg.index; #####: 361: return (RET_SUCCESS); -: 362: } #####: 363: idx = c->pg.index; #####: 364: if (idx == 0) { #####: 365: pg = h->prevpg; #####: 366: mpool_put(t->bt_mp, h, 0); #####: 367: if (pg == P_INVALID) #####: 368: return (RET_SPECIAL); #####: 369: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 370: return (RET_ERROR); #####: 371: idx = NEXTINDEX(h) - 1; -: 372: } else #####: 373: --idx; -: 374: break; -: 375: } -: 376: 7331: 377: ep->page = h; 7331: 378: ep->index = idx; 7331: 379: return (RET_SUCCESS); -: 380:} -: 381: -: 382:/* -: 383: * __bt_first -- -: 384: * Find the first entry. -: 385: * -: 386: * Parameters: -: 387: * t: the tree -: 388: * key: the key -: 389: * erval: return EPG -: 390: * exactp: pointer to exact match flag -: 391: * -: 392: * Returns: -: 393: * The first entry in the tree greater than or equal to key, -: 394: * or RET_SPECIAL if no such key exists. -: 395: */ -: 396:static int #####: 397:__bt_first(t, key, erval, exactp) -: 398: BTREE *t; -: 399: const DBT *key; -: 400: EPG *erval; -: 401: int *exactp; -: 402:{ -: 403: PAGE *h; -: 404: EPG *ep, save; -: 405: db_pgno_t pg; -: 406: -: 407: /* -: 408: * Find any matching record; __bt_search pins the page. -: 409: * -: 410: * If it's an exact match and duplicates are possible, walk backwards -: 411: * in the tree until we find the first one. Otherwise, make sure it's -: 412: * a valid key (__bt_search may return an index just past the end of a -: 413: * page) and return it. -: 414: */ #####: 415: if ((ep = __bt_search(t, key, exactp)) == NULL) #####: 416: return (RET_SPECIAL); #####: 417: if (*exactp) { #####: 418: if (F_ISSET(t, B_NODUPS)) { #####: 419: *erval = *ep; #####: 420: return (RET_SUCCESS); -: 421: } -: 422: -: 423: /* -: 424: * Walk backwards, as long as the entry matches and there are -: 425: * keys left in the tree. Save a copy of each match in case -: 426: * we go too far. -: 427: */ #####: 428: save = *ep; #####: 429: h = ep->page; -: 430: do { #####: 431: if (save.page->pgno != ep->page->pgno) { #####: 432: mpool_put(t->bt_mp, save.page, 0); #####: 433: save = *ep; -: 434: } else #####: 435: save.index = ep->index; -: 436: -: 437: /* -: 438: * Don't unpin the page the last (or original) match -: 439: * was on, but make sure it's unpinned if an error -: 440: * occurs. -: 441: */ #####: 442: if (ep->index == 0) { #####: 443: if (h->prevpg == P_INVALID) #####: 444: break; #####: 445: if (h->pgno != save.page->pgno) #####: 446: mpool_put(t->bt_mp, h, 0); #####: 447: if ((h = mpool_get(t->bt_mp, -: 448: h->prevpg, 0)) == NULL) { #####: 449: if (h->pgno == save.page->pgno) #####: 450: mpool_put(t->bt_mp, #####: 451: save.page, 0); #####: 452: return (RET_ERROR); -: 453: } #####: 454: ep->page = h; #####: 455: ep->index = NEXTINDEX(h); -: 456: } #####: 457: --ep->index; #####: 458: } while (__bt_cmp(t, key, ep) == 0); -: 459: -: 460: /* -: 461: * Reach here with the last page that was looked at pinned, -: 462: * which may or may not be the same as the last (or original) -: 463: * match page. If it's not useful, release it. -: 464: */ #####: 465: if (h->pgno != save.page->pgno) #####: 466: mpool_put(t->bt_mp, h, 0); -: 467: #####: 468: *erval = save; #####: 469: return (RET_SUCCESS); -: 470: } -: 471: -: 472: /* If at the end of a page, find the next entry. */ #####: 473: if (ep->index == NEXTINDEX(ep->page)) { #####: 474: h = ep->page; #####: 475: pg = h->nextpg; #####: 476: mpool_put(t->bt_mp, h, 0); #####: 477: if (pg == P_INVALID) #####: 478: return (RET_SPECIAL); #####: 479: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 480: return (RET_ERROR); #####: 481: ep->index = 0; #####: 482: ep->page = h; -: 483: } #####: 484: *erval = *ep; #####: 485: return (RET_SUCCESS); -: 486:} -: 487: -: 488:/* -: 489: * __bt_setcur -- -: 490: * Set the cursor to an entry in the tree. -: 491: * -: 492: * Parameters: -: 493: * t: the tree -: 494: * pgno: page number -: 495: * index: page index -: 496: */ -: 497:void 7974: 498:__bt_setcur(t, pgno, idx) -: 499: BTREE *t; -: 500: db_pgno_t pgno; -: 501: u_int idx; -: 502:{ -: 503: /* Lose any already deleted key. */ 7974: 504: if (t->bt_cursor.key.data != NULL) { #####: 505: free(t->bt_cursor.key.data); #####: 506: t->bt_cursor.key.size = 0; #####: 507: t->bt_cursor.key.data = NULL; -: 508: } 7974: 509: F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); -: 510: -: 511: /* Update the cursor. */ 7974: 512: t->bt_cursor.pg.pgno = pgno; 7974: 513: t->bt_cursor.pg.index = idx; 7974: 514: F_SET(&t->bt_cursor, CURS_INIT); 7974: 515:} -: 516: -: 517:/* Recursive descent cursor. */ -: 518:typedef struct rcursor_ { -: 519: CURSOR cursor; -: 520: size_t ssize; -: 521: EPGNO *stack; -: 522: EPGNO *sp; -: 523:} RCURSOR; -: 524:#define RCURSOR_MINSS 64 -: 525: -: 526:static int bt_rcinit(void **); -: 527:static void bt_rcdestroy(void **); -: 528:static int bt_rcpush(RCURSOR *, db_pgno_t, u_int); -: 529:static EPGNO *bt_rcpop(RCURSOR *); -: 530:static void bt_rcclr(RCURSOR *); -: 531:static int bt_rcgrowstk(RCURSOR *); -: 532:static int bt_rseqset(BTREE *, EPG *, DBT *, RCURSOR *, int); -: 533:static int bt_rseqadv(BTREE *, EPG *, RCURSOR *, int); -: 534: -: 535:static int #####: 536:bt_rcinit(curs) -: 537: void **curs; -: 538:{ -: 539: RCURSOR *rc; -: 540: #####: 541: rc = *curs = malloc(sizeof(RCURSOR)); #####: 542: if (rc == NULL) { #####: 543: errno = ENOMEM; #####: 544: return RET_ERROR; -: 545: } #####: 546: memset(rc, 0, sizeof(*rc)); -: 547: #####: 548: rc->ssize = RCURSOR_MINSS; #####: 549: rc->stack = malloc(rc->ssize * sizeof(EPGNO)); #####: 550: if (rc->stack == NULL) { #####: 551: free(rc); #####: 552: errno = ENOMEM; #####: 553: return RET_ERROR; -: 554: } #####: 555: bt_rcclr(rc); #####: 556: return RET_SUCCESS; -: 557:} -: 558: -: 559:static void #####: 560:bt_rcdestroy(curs) -: 561: void **curs; -: 562:{ -: 563: RCURSOR *rc; -: 564: #####: 565: rc = *curs; #####: 566: free(rc->stack); #####: 567: free(rc); #####: 568: *curs = NULL; #####: 569:} -: 570: -: 571:static int #####: 572:bt_rcpush(rc, p, i) -: 573: RCURSOR *rc; -: 574: db_pgno_t p; -: 575: u_int i; -: 576:{ -: 577: int status; -: 578: #####: 579: rc->sp->pgno = p; #####: 580: rc->sp->index = i; #####: 581: if (++rc->sp > rc->stack + rc->ssize) { #####: 582: status = bt_rcgrowstk(rc); #####: 583: if (status != RET_SUCCESS) #####: 584: return status; -: 585: } #####: 586: return RET_SUCCESS; -: 587:} -: 588: -: 589:static EPGNO * #####: 590:bt_rcpop(rc) -: 591: RCURSOR *rc; -: 592:{ #####: 593: return (rc->sp == rc->stack) ? NULL : --rc->sp; -: 594:} -: 595: -: 596:static void #####: 597:bt_rcclr(rc) -: 598: RCURSOR *rc; -: 599:{ #####: 600: rc->sp = rc->stack; #####: 601:} -: 602: -: 603:static int #####: 604:bt_rcgrowstk(rc) -: 605: RCURSOR *rc; -: 606:{ -: 607: size_t osize; -: 608: EPGNO *e; -: 609: #####: 610: osize = rc->ssize; #####: 611: rc->ssize *= 2; #####: 612: e = realloc(rc->stack, rc->ssize * sizeof(EPGNO)); #####: 613: if (e == NULL) { #####: 614: rc->ssize = osize; #####: 615: errno = ENOMEM; #####: 616: return RET_ERROR; -: 617: } #####: 618: rc->stack = e; #####: 619: return RET_SUCCESS; -: 620:} -: 621: -: 622:/* -: 623: * bt_rseq -- -: 624: * Like __bt_seq but does recursive descent tree traversal -: 625: * instead of using the prev/next pointers. -: 626: */ -: 627:int #####: 628:bt_rseq(dbp, key, data, curs, flags) -: 629: const DB *dbp; -: 630: DBT *key, *data; -: 631: void **curs; -: 632: u_int flags; -: 633:{ -: 634: RCURSOR *rc; -: 635: BTREE *t; -: 636: EPG e; -: 637: int status; -: 638: #####: 639: t = dbp->internal; -: 640: -: 641: /* Toss any page pinned across calls. */ #####: 642: if (t->bt_pinned != NULL) { #####: 643: mpool_put(t->bt_mp, t->bt_pinned, 0); #####: 644: t->bt_pinned = NULL; -: 645: } -: 646: #####: 647: if (curs == NULL) { #####: 648: errno = EINVAL; #####: 649: return RET_ERROR; -: 650: } #####: 651: if (*curs == NULL) { #####: 652: status = bt_rcinit(curs); #####: 653: if (status != RET_SUCCESS) #####: 654: return RET_ERROR; -: 655: } #####: 656: rc = *curs; -: 657: -: 658: /* -: 659: * If scan unitialized as yet, or starting at a specific record, set -: 660: * the scan to a specific key. Both bt_rseqset and bt_rseqadv pin -: 661: * the page the cursor references if they're successful. -: 662: */ #####: 663: switch (flags) { -: 664: case R_NEXT: -: 665: case R_PREV: #####: 666: if (F_ISSET(&rc->cursor, CURS_INIT)) { #####: 667: status = bt_rseqadv(t, &e, rc, flags); #####: 668: break; -: 669: } -: 670: /* FALLTHROUGH */ -: 671: case R_FIRST: -: 672: case R_LAST: -: 673: case R_CURSOR: #####: 674: status = bt_rseqset(t, &e, key, rc, flags); #####: 675: break; -: 676: default: #####: 677: errno = EINVAL; #####: 678: return (RET_ERROR); -: 679: } -: 680: #####: 681: if (status == RET_SUCCESS) { #####: 682: status = #####: 683: __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0); -: 684: -: 685: /* -: 686: * If the user is doing concurrent access, we copied the -: 687: * key/data, toss the page. -: 688: */ #####: 689: if (F_ISSET(t, B_DB_LOCK)) #####: 690: mpool_put(t->bt_mp, e.page, 0); -: 691: else #####: 692: t->bt_pinned = e.page; #####: 693: } else if (status == RET_SPECIAL) #####: 694: bt_rcdestroy(curs); #####: 695: return (status); -: 696:} -: 697: -: 698:/* -: 699: * bt_rseqset -- -: 700: * Set the sequential scan to a specific key. -: 701: * -: 702: * Parameters: -: 703: * t: tree -: 704: * ep: storage for returned key -: 705: * key: key for initial scan position -: 706: * rc: recursion cursor -: 707: * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV -: 708: * -: 709: * Side effects: -: 710: * Pins the page the cursor references. -: 711: * Updates rc's stack and cursor. -: 712: * -: 713: * Returns: -: 714: * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. -: 715: */ -: 716:static int #####: 717:bt_rseqset(t, ep, key, rc, flags) -: 718: BTREE *t; -: 719: EPG *ep; -: 720: DBT *key; -: 721: RCURSOR *rc; -: 722: int flags; -: 723:{ -: 724: PAGE *h; -: 725: db_pgno_t pg; -: 726: int status; -: 727: -: 728: /* -: 729: * Find the first, last or specific key in the tree and point the -: 730: * cursor at it. The cursor may not be moved until a new key has -: 731: * been found. -: 732: */ #####: 733: switch (flags) { -: 734: case R_CURSOR: /* Not implemented. */ #####: 735: errno = EINVAL; #####: 736: return RET_ERROR; -: 737: case R_FIRST: /* First record. */ -: 738: case R_NEXT: #####: 739: bt_rcclr(rc); -: 740: /* Walk down the left-hand side of the tree. */ #####: 741: for (pg = P_ROOT;;) { #####: 742: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 743: return (RET_ERROR); -: 744: -: 745: /* Check for an empty tree. */ #####: 746: if (NEXTINDEX(h) == 0) { #####: 747: mpool_put(t->bt_mp, h, 0); #####: 748: return (RET_SPECIAL); -: 749: } -: 750: #####: 751: if (h->flags & (P_BLEAF | P_RLEAF)) -: 752: break; #####: 753: pg = GETBINTERNAL(h, 0)->pgno; #####: 754: status = bt_rcpush(rc, h->pgno, 0); #####: 755: mpool_put(t->bt_mp, h, 0); #####: 756: if (status != RET_SUCCESS) #####: 757: return status; #####: 758: } #####: 759: ep->page = h; #####: 760: ep->index = 0; #####: 761: break; -: 762: case R_LAST: /* Last record. */ -: 763: case R_PREV: #####: 764: bt_rcclr(rc); -: 765: /* Walk down the right-hand side of the tree. */ #####: 766: for (pg = P_ROOT;;) { #####: 767: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 768: return (RET_ERROR); -: 769: -: 770: /* Check for an empty tree. */ #####: 771: if (NEXTINDEX(h) == 0) { #####: 772: mpool_put(t->bt_mp, h, 0); #####: 773: return (RET_SPECIAL); -: 774: } -: 775: #####: 776: if (h->flags & (P_BLEAF | P_RLEAF)) -: 777: break; #####: 778: pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; #####: 779: status = bt_rcpush(rc, h->pgno, NEXTINDEX(h) - 1); #####: 780: mpool_put(t->bt_mp, h, 0); #####: 781: if (status != RET_SUCCESS) #####: 782: return status; #####: 783: } #####: 784: ep->page = h; #####: 785: ep->index = NEXTINDEX(h) - 1; -: 786: break; -: 787: } #####: 788: rc->cursor.pg.pgno = ep->page->pgno; #####: 789: rc->cursor.pg.index = ep->index; #####: 790: F_CLR(&rc->cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); #####: 791: F_SET(&rc->cursor, CURS_INIT); #####: 792: return (RET_SUCCESS); -: 793:} -: 794: -: 795:/* -: 796: * bt_rseqadvance -- -: 797: * Advance the sequential scan. -: 798: * -: 799: * Parameters: -: 800: * t: tree -: 801: * ep: return page -: 802: * rc: recursion cursor -: 803: * flags: R_NEXT, R_PREV -: 804: * -: 805: * Side effects: -: 806: * Pins the page the new key/data record is on. -: 807: * Updates rc's stack and cursor. -: 808: * -: 809: * Returns: -: 810: * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. -: 811: */ -: 812:static int #####: 813:bt_rseqadv(t, ep, rc, flags) -: 814: BTREE *t; -: 815: EPG *ep; -: 816: RCURSOR *rc; -: 817: int flags; -: 818:{ -: 819: CURSOR *c; -: 820: PAGE *h; #####: 821: indx_t idx = 0; -: 822: db_pgno_t pg; -: 823: int status; -: 824: EPGNO *e; -: 825: -: 826: /* -: 827: * There are a couple of states that we can be in. The cursor has -: 828: * been initialized by the time we get here, but that's all we know. -: 829: */ #####: 830: c = &rc->cursor; -: 831: -: 832: /* Get the page referenced by the cursor. */ #####: 833: if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) #####: 834: return (RET_ERROR); -: 835: -: 836: /* -: 837: * Find the next/previous record in the tree and point the cursor at -: 838: * it. The cursor may not be moved until a new key has been found. -: 839: */ #####: 840: switch (flags) { -: 841: case R_NEXT: /* Next record. */ #####: 842: idx = c->pg.index; #####: 843: while (++idx == NEXTINDEX(h)) { -: 844: /* Crawl up if we hit the right edge. */ #####: 845: e = bt_rcpop(rc); #####: 846: mpool_put(t->bt_mp, h, 0); #####: 847: if (e == NULL) /* Hit the right edge of root. */ #####: 848: return RET_SPECIAL; #####: 849: idx = e->index; #####: 850: pg = e->pgno; #####: 851: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 852: return (RET_ERROR); -: 853: } #####: 854: while (!(h->flags & (P_BLEAF | P_RLEAF))) { -: 855: /* Crawl down the left until we hit a leaf. */ #####: 856: status = bt_rcpush(rc, h->pgno, idx); #####: 857: pg = GETBINTERNAL(h, idx)->pgno; #####: 858: mpool_put(t->bt_mp, h, 0); #####: 859: if (status != RET_SUCCESS) #####: 860: return status; #####: 861: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 862: return (RET_ERROR); #####: 863: idx = 0; -: 864: } #####: 865: break; -: 866: case R_PREV: /* Previous record. */ #####: 867: idx = c->pg.index; #####: 868: while (!idx) { -: 869: /* Crawl up if we hit the left edge. */ #####: 870: e = bt_rcpop(rc); #####: 871: mpool_put(t->bt_mp, h, 0); #####: 872: if (e == NULL) /* Hit the left edge of root. */ #####: 873: return RET_SPECIAL; #####: 874: idx = e->index; #####: 875: pg = e->pgno; #####: 876: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 877: return (RET_ERROR); -: 878: } #####: 879: idx--; #####: 880: while (!(h->flags & (P_BLEAF | P_RLEAF))) { -: 881: /* Crawl down the right until we hit a leaf. */ #####: 882: status = bt_rcpush(rc, h->pgno, idx); #####: 883: pg = GETBINTERNAL(h, idx)->pgno; #####: 884: mpool_put(t->bt_mp, h, 0); #####: 885: if (status != RET_SUCCESS) #####: 886: return status; #####: 887: if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) #####: 888: return (RET_ERROR); #####: 889: idx = NEXTINDEX(h) - 1; -: 890: } -: 891: break; -: 892: } -: 893: #####: 894: ep->page = h; #####: 895: ep->index = idx; #####: 896: c->pg.pgno = h->pgno; #####: 897: c->pg.index = idx; #####: 898: F_CLR(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); #####: 899: F_SET(c, CURS_INIT); #####: 900: return (RET_SUCCESS); -: 901:}