db/btree/bt_seq.c

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