db/btree/bt_seq.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  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.7 (Berkeley) 7/20/94";
  63 #endif /* LIBC_SCCS and not lint */
  64 #include <sys/cdefs.h>
  65
  66 #include <sys/types.h>
  67
  68 #include <errno.h>
  69 #include <stddef.h>
  70 #include <stdio.h>
  71 #include <stdlib.h>
  72
  73 #include <db.h>
  74 #include "btree.h"
  75
  76 static int __bt_first(BTREE *, const DBT *, EPG *, int *);
  77 static int __bt_seqadv(BTREE *, EPG *, int);
  78 static int __bt_seqset(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
 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
 111         t = dbp->internal;
 112
 113         /* Toss any page pinned across calls. */
 114         if (t->bt_pinned != NULL) {
 115                 mpool_put(t->bt_mp, t->bt_pinned, 0);
 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          */
 124         switch (flags) {
 125         case R_NEXT:
 126         case R_PREV:
 127                 if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
 128                         status = __bt_seqadv(t, &e, flags);
 129                         break;
 130                 }
 131                 /* FALLTHROUGH */
 132         case R_FIRST:
 133         case R_LAST:
 134         case R_CURSOR:
 135                 status = __bt_seqset(t, &e, key, flags);
 136                 break;
 137         default:
 138                 errno = EINVAL;
 139                 return (RET_ERROR);
 140         }
 141
 142         if (status == RET_SUCCESS) {
 143                 __bt_setcur(t, e.page->pgno, e.index);
 144
 145                 status =
 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                  */
 152                 if (F_ISSET(t, B_DB_LOCK))
 153                         mpool_put(t->bt_mp, e.page, 0);
 154                 else
 155                         t->bt_pinned = e.page;
 156         }
 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
 177 __bt_seqset(t, ep, key, flags)
 178         BTREE *t;
 179         EPG *ep;
 180         DBT *key;
 181         int flags;
 182 {
 183         PAGE *h;
 184         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          */
 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. */
 206                 for (pg = P_ROOT;;) {
 207                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 208                                 return (RET_ERROR);
 209
 210                         /* Check for an empty tree. */
 211                         if (NEXTINDEX(h) == 0) {
 212                                 mpool_put(t->bt_mp, h, 0);
 213                                 return (RET_SPECIAL);
 214                         }
 215
 216                         if (h->flags & (P_BLEAF | P_RLEAF))
 217                                 break;
 218                         pg = GETBINTERNAL(h, 0)->pgno;
 219                         mpool_put(t->bt_mp, h, 0);
 220                 }
 221                 ep->page = h;
 222                 ep->index = 0;
 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         }
 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
 265 __bt_seqadv(t, ep, flags)
 266         BTREE *t;
 267         EPG *ep;
 268         int flags;
 269 {
 270         CURSOR *c;
 271         PAGE *h;
 272         indx_t index;
 273         pgno_t pg;
 274         int exact;
 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          */
 280         c = &t->bt_cursor;
 281
 282         /*
 283          * The cursor was deleted where there weren't any duplicate records,
 284          * so the key was saved.  Find out where that key would go in the
 285          * current tree.  It doesn't matter if the returned key is an exact
 286          * match or not -- if it's an exact match, the record was added after
 287          * the delete so we can just return it.  If not, as long as there's
 288          * a record there, return it.
 289          */
 290         if (F_ISSET(c, CURS_ACQUIRE))
 291                 return (__bt_first(t, &c->key, ep, &exact));
 292
 293         /* Get the page referenced by the cursor. */
 294         if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
 295                 return (RET_ERROR);
 296
 297         /*
 298          * Find the next/previous record in the tree and point the cursor at
 299          * it.  The cursor may not be moved until a new key has been found.
 300          */
 301         switch (flags) {
 302         case R_NEXT:                    /* Next record. */
 303                 /*
 304                  * The cursor was deleted in duplicate records, and moved
 305                  * forward to a record that has yet to be returned.  Clear
 306                  * that flag, and return the record.
 307                  */
 308                 if (F_ISSET(c, CURS_AFTER))
 309                         goto usecurrent;
 310                 index = c->pg.index;
 311                 if (++index == NEXTINDEX(h)) {
 312                         pg = h->nextpg;
 313                         mpool_put(t->bt_mp, h, 0);
 314                         if (pg == P_INVALID)
 315                                 return (RET_SPECIAL);
 316                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 317                                 return (RET_ERROR);
 318                         index = 0;
 319                 }
 320                 break;
 321         case R_PREV:                    /* Previous record. */
 322                 /*
 323                  * The cursor was deleted in duplicate records, and moved
 324                  * backward to a record that has yet to be returned.  Clear
 325                  * that flag, and return the record.
 326                  */
 327                 if (F_ISSET(c, CURS_BEFORE)) {
 328 usecurrent:             F_CLR(c, CURS_AFTER | CURS_BEFORE);
 329                         ep->page = h;
 330                         ep->index = c->pg.index;
 331                         return (RET_SUCCESS);
 332                 }
 333                 index = c->pg.index;
 334                 if (index == 0) {
 335                         pg = h->prevpg;
 336                         mpool_put(t->bt_mp, h, 0);
 337                         if (pg == P_INVALID)
 338                                 return (RET_SPECIAL);
 339                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 340                                 return (RET_ERROR);
 341                         index = NEXTINDEX(h) - 1;
 342                 } else
 343                         --index;
 344                 break;
 345         }
 346
 347         ep->page = h;
 348         ep->index = index;
 349         return (RET_SUCCESS);
 350 }
 351
 352 /*
 353  * __bt_first --
 354  *      Find the first entry.
 355  *
 356  * Parameters:
 357  *      t:      the tree
 358  *    key:      the key
 359  *  erval:      return EPG
 360  * exactp:      pointer to exact match flag
 361  *
 362  * Returns:
 363  *      The first entry in the tree greater than or equal to key,
 364  *      or RET_SPECIAL if no such key exists.
 365  */
 366 static int
 367 __bt_first(t, key, erval, exactp)
 368         BTREE *t;
 369         const DBT *key;
 370         EPG *erval;
 371         int *exactp;
 372 {
 373         PAGE *h;
 374         EPG *ep, save;
 375         pgno_t pg;
 376
 377         /*
 378          * Find any matching record; __bt_search pins the page.
 379          *
 380          * If it's an exact match and duplicates are possible, walk backwards
 381          * in the tree until we find the first one.  Otherwise, make sure it's
 382          * a valid key (__bt_search may return an index just past the end of a
 383          * page) and return it.
 384          */
 385         if ((ep = __bt_search(t, key, exactp)) == NULL)
 386                 return (0);
 387         if (*exactp) {
 388                 if (F_ISSET(t, B_NODUPS)) {
 389                         *erval = *ep;
 390                         return (RET_SUCCESS);
 391                 }
 392
 393                 /*
 394                  * Walk backwards, as long as the entry matches and there are
 395                  * keys left in the tree.  Save a copy of each match in case
 396                  * we go too far.
 397                  */
 398                 save = *ep;
 399                 h = ep->page;
 400                 do {
 401                         if (save.page->pgno != ep->page->pgno) {
 402                                 mpool_put(t->bt_mp, save.page, 0);
 403                                 save = *ep;
 404                         } else
 405                                 save.index = ep->index;
 406
 407                         /*
 408                          * Don't unpin the page the last (or original) match
 409                          * was on, but make sure it's unpinned if an error
 410                          * occurs.
 411                          */
 412                         if (ep->index == 0) {
 413                                 if (h->prevpg == P_INVALID)
 414                                         break;
 415                                 if (h->pgno != save.page->pgno)
 416                                         mpool_put(t->bt_mp, h, 0);
 417                                 if ((h = mpool_get(t->bt_mp,
 418                                     h->prevpg, 0)) == NULL) {
 419                                         if (h->pgno == save.page->pgno)
 420                                                 mpool_put(t->bt_mp,
 421                                                     save.page, 0);
 422                                         return (RET_ERROR);
 423                                 }
 424                                 ep->page = h;
 425                                 ep->index = NEXTINDEX(h);
 426                         }
 427                         --ep->index;
 428                 } while (__bt_cmp(t, key, ep) == 0);
 429
 430                 /*
 431                  * Reach here with the last page that was looked at pinned,
 432                  * which may or may not be the same as the last (or original)
 433                  * match page.  If it's not useful, release it.
 434                  */
 435                 if (h->pgno != save.page->pgno)
 436                         mpool_put(t->bt_mp, h, 0);
 437
 438                 *erval = save;
 439                 return (RET_SUCCESS);
 440         }
 441
 442         /* If at the end of a page, find the next entry. */
 443         if (ep->index == NEXTINDEX(ep->page)) {
 444                 h = ep->page;
 445                 pg = h->nextpg;
 446                 mpool_put(t->bt_mp, h, 0);
 447                 if (pg == P_INVALID)
 448                         return (RET_SPECIAL);
 449                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 450                         return (RET_ERROR);
 451                 ep->index = 0;
 452                 ep->page = h;
 453         }
 454         *erval = *ep;
 455         return (RET_SUCCESS);
 456 }
 457
 458 /*
 459  * __bt_setcur --
 460  *      Set the cursor to an entry in the tree.
 461  *
 462  * Parameters:
 463  *      t:      the tree
 464  *   pgno:      page number
 465  *  index:      page index
 466  */
 467 void
 468 __bt_setcur(t, pgno, index)
 469         BTREE *t;
 470         pgno_t pgno;
 471         u_int index;
 472 {
 473         /* Lose any already deleted key. */
 474         if (t->bt_cursor.key.data != NULL) {
 475                 free(t->bt_cursor.key.data);
 476                 t->bt_cursor.key.size = 0;
 477                 t->bt_cursor.key.data = NULL;
 478         }
 479         F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
 480
 481         /* Update the cursor. */
 482         t->bt_cursor.pg.pgno = pgno;
 483         t->bt_cursor.pg.index = index;
 484         F_SET(&t->bt_cursor, CURS_INIT);
 485 }