db.subproj/btree.subproj/bt_seq.c

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23  * Copyright (c) 1990, 1993
  24  *      The Regents of the University of California.  All rights reserved.
  25  *
  26  * This code is derived from software contributed to Berkeley by
  27  * Mike Olson.
  28  *
  29  * Redistribution and use in source and binary forms, with or without
  30  * modification, are permitted provided that the following conditions
  31  * are met:
  32  * 1. Redistributions of source code must retain the above copyright
  33  *    notice, this list of conditions and the following disclaimer.
  34  * 2. Redistributions in binary form must reproduce the above copyright
  35  *    notice, this list of conditions and the following disclaimer in the
  36  *    documentation and/or other materials provided with the distribution.
  37  * 3. All advertising materials mentioning features or use of this software
  38  *    must display the following acknowledgement:
  39  *      This product includes software developed by the University of
  40  *      California, Berkeley and its contributors.
  41  * 4. Neither the name of the University nor the names of its contributors
  42  *    may be used to endorse or promote products derived from this software
  43  *    without specific prior written permission.
  44  *
  45  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  46  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  47  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  48  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  49  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  50  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  51  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  52  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  53  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  54  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  55  * SUCH DAMAGE.
  56  */
  57
  58
  59 #include <sys/types.h>
  60
  61 #include <errno.h>
  62 #include <stddef.h>
  63 #include <stdio.h>
  64 #include <stdlib.h>
  65
  66 #include <db.h>
  67 #include "btree.h"
  68
  69 static int       bt_seqadv __P((BTREE *, EPG *, int));
  70 static int       bt_seqset __P((BTREE *, EPG *, DBT *, int));
  71
  72 /*
  73  * Sequential scan support.
  74  *
  75  * The tree can be scanned sequentially, starting from either end of the tree
  76  * or from any specific key.  A scan request before any scanning is done is
  77  * initialized as starting from the least node.
  78  *
  79  * Each tree has an EPGNO which has the current position of the cursor.  The
  80  * cursor has to survive deletions/insertions in the tree without losing its
  81  * position.  This is done by noting deletions without doing them, and then
  82  * doing them when the cursor moves (or the tree is closed).
  83  */
  84
  85 /*
  86  * __BT_SEQ -- Btree sequential scan interface.
  87  *
  88  * Parameters:
  89  *      dbp:    pointer to access method
  90  *      key:    key for positioning and return value
  91  *      data:   data return value
  92  *      flags:  R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
  93  *
  94  * Returns:
  95  *      RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  96  */
  97 int
  98 __bt_seq(dbp, key, data, flags)
  99         const DB *dbp;
 100         DBT *key, *data;
 101         u_int flags;
 102 {
 103         BTREE *t;
 104         EPG e;
 105         int status;
 106
 107         t = dbp->internal;
 108
 109         /* Toss any page pinned across calls. */
 110         if (t->bt_pinned != NULL) {
 111                 mpool_put(t->bt_mp, t->bt_pinned, 0);
 112                 t->bt_pinned = NULL;
 113         }
 114
 115         /*
 116          * If scan unitialized as yet, or starting at a specific record, set
 117          * the scan to a specific key.  Both bt_seqset and bt_seqadv pin the
 118          * page the cursor references if they're successful.
 119          */
 120         switch(flags) {
 121         case R_NEXT:
 122         case R_PREV:
 123                 if (ISSET(t, B_SEQINIT)) {
 124                         status = bt_seqadv(t, &e, flags);
 125                         break;
 126                 }
 127                 /* FALLTHROUGH */
 128         case R_CURSOR:
 129         case R_FIRST:
 130         case R_LAST:
 131                 status = bt_seqset(t, &e, key, flags);
 132                 break;
 133         default:
 134                 errno = EINVAL;
 135                 return (RET_ERROR);
 136         }
 137
 138         if (status == RET_SUCCESS) {
 139                 status = __bt_ret(t, &e, key, data);
 140
 141                 /* Update the actual cursor. */
 142                 t->bt_bcursor.pgno = e.page->pgno;
 143                 t->bt_bcursor.index = e.index;
 144
 145                 /*
 146                  * If the user is doing concurrent access, we copied the
 147                  * key/data, toss the page.
 148                  */
 149                 if (ISSET(t, B_DB_LOCK))
 150                         mpool_put(t->bt_mp, e.page, 0);
 151                 else
 152                         t->bt_pinned = e.page;
 153                 SET(t, B_SEQINIT);
 154         }
 155         return (status);
 156 }
 157
 158 /*
 159  * BT_SEQSET -- Set the sequential scan to a specific key.
 160  *
 161  * Parameters:
 162  *      t:      tree
 163  *      ep:     storage for returned key
 164  *      key:    key for initial scan position
 165  *      flags:  R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
 166  *
 167  * Side effects:
 168  *      Pins the page the cursor references.
 169  *
 170  * Returns:
 171  *      RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
 172  */
 173 static int
 174 bt_seqset(t, ep, key, flags)
 175         BTREE *t;
 176         EPG *ep;
 177         DBT *key;
 178         int flags;
 179 {
 180         EPG *e;
 181         PAGE *h;
 182         pgno_t pg;
 183         int exact;
 184
 185         /*
 186          * Delete any already deleted record that we've been saving because
 187          * the cursor pointed to it.  Since going to a specific key, should
 188          * delete any logically deleted records so they aren't found.
 189          */
 190         if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor))
 191                 return (RET_ERROR);
 192
 193         /*
 194          * Find the first, last or specific key in the tree and point the cursor
 195          * at it.  The cursor may not be moved until a new key has been found.
 196          */
 197         switch(flags) {
 198         case R_CURSOR:                          /* Keyed scan. */
 199                 /*
 200                  * Find the first instance of the key or the smallest key which
 201                  * is greater than or equal to the specified key.  If run out
 202                  * of keys, return RET_SPECIAL.
 203                  */
 204                 if (key->data == NULL || key->size == 0) {
 205                         errno = EINVAL;
 206                         return (RET_ERROR);
 207                 }
 208                 e = __bt_first(t, key, &exact); /* Returns pinned page. */
 209                 if (e == NULL)
 210                         return (RET_ERROR);
 211                 /*
 212                  * If at the end of a page, skip any empty pages and find the
 213                  * next entry.
 214                  */
 215                 if (e->index == NEXTINDEX(e->page)) {
 216                         h = e->page;
 217                         do {
 218                                 pg = h->nextpg;
 219                                 mpool_put(t->bt_mp, h, 0);
 220                                 if (pg == P_INVALID)
 221                                         return (RET_SPECIAL);
 222                                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 223                                         return (RET_ERROR);
 224                         } while (NEXTINDEX(h) == 0);
 225                         e->index = 0;
 226                         e->page = h;
 227                 }
 228                 *ep = *e;
 229                 break;
 230         case R_FIRST:                           /* First record. */
 231         case R_NEXT:
 232                 /* Walk down the left-hand side of the tree. */
 233                 for (pg = P_ROOT;;) {
 234                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 235                                 return (RET_ERROR);
 236                         if (h->flags & (P_BLEAF | P_RLEAF))
 237                                 break;
 238                         pg = GETBINTERNAL(h, 0)->pgno;
 239                         mpool_put(t->bt_mp, h, 0);
 240                 }
 241
 242                 /* Skip any empty pages. */
 243                 while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) {
 244                         pg = h->nextpg;
 245                         mpool_put(t->bt_mp, h, 0);
 246                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 247                                 return (RET_ERROR);
 248                 }
 249
 250                 if (NEXTINDEX(h) == 0) {
 251                         mpool_put(t->bt_mp, h, 0);
 252                         return (RET_SPECIAL);
 253                 }
 254
 255                 ep->page = h;
 256                 ep->index = 0;
 257                 break;
 258         case R_LAST:                            /* Last record. */
 259         case R_PREV:
 260                 /* Walk down the right-hand side of the tree. */
 261                 for (pg = P_ROOT;;) {
 262                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 263                                 return (RET_ERROR);
 264                         if (h->flags & (P_BLEAF | P_RLEAF))
 265                                 break;
 266                         pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
 267                         mpool_put(t->bt_mp, h, 0);
 268                 }
 269
 270                 /* Skip any empty pages. */
 271                 while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) {
 272                         pg = h->prevpg;
 273                         mpool_put(t->bt_mp, h, 0);
 274                         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 275                                 return (RET_ERROR);
 276                 }
 277
 278                 if (NEXTINDEX(h) == 0) {
 279                         mpool_put(t->bt_mp, h, 0);
 280                         return (RET_SPECIAL);
 281                 }
 282
 283                 ep->page = h;
 284                 ep->index = NEXTINDEX(h) - 1;
 285                 break;
 286         }
 287         return (RET_SUCCESS);
 288 }
 289
 290 /*
 291  * BT_SEQADVANCE -- Advance the sequential scan.
 292  *
 293  * Parameters:
 294  *      t:      tree
 295  *      flags:  R_NEXT, R_PREV
 296  *
 297  * Side effects:
 298  *      Pins the page the new key/data record is on.
 299  *
 300  * Returns:
 301  *      RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
 302  */
 303 static int
 304 bt_seqadv(t, e, flags)
 305         BTREE *t;
 306         EPG *e;
 307         int flags;
 308 {
 309         EPGNO *c, delc;
 310         PAGE *h;
 311         indx_t index;
 312         pgno_t pg;
 313
 314         /* Save the current cursor if going to delete it. */
 315         c = &t->bt_bcursor;
 316         if (ISSET(t, B_DELCRSR))
 317                 delc = *c;
 318
 319         if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
 320                 return (RET_ERROR);
 321
 322         /*
 323          * Find the next/previous record in the tree and point the cursor at it.
 324          * The cursor may not be moved until a new key has been found.
 325          */
 326         index = c->index;
 327         switch(flags) {
 328         case R_NEXT:                    /* Next record. */
 329                 if (++index == NEXTINDEX(h)) {
 330                         do {
 331                                 pg = h->nextpg;
 332                                 mpool_put(t->bt_mp, h, 0);
 333                                 if (pg == P_INVALID)
 334                                         return (RET_SPECIAL);
 335                                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 336                                         return (RET_ERROR);
 337                         } while (NEXTINDEX(h) == 0);
 338                         index = 0;
 339                 }
 340                 break;
 341         case R_PREV:                    /* Previous record. */
 342                 if (index-- == 0) {
 343                         do {
 344                                 pg = h->prevpg;
 345                                 mpool_put(t->bt_mp, h, 0);
 346                                 if (pg == P_INVALID)
 347                                         return (RET_SPECIAL);
 348                                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 349                                         return (RET_ERROR);
 350                         } while (NEXTINDEX(h) == 0);
 351                         index = NEXTINDEX(h) - 1;
 352                 }
 353                 break;
 354         }
 355
 356         e->page = h;
 357         e->index = index;
 358
 359         /*
 360          * Delete any already deleted record that we've been saving because the
 361          * cursor pointed to it.  This could cause the new index to be shifted
 362          * down by one if the record we're deleting is on the same page and has
 363          * a larger index.
 364          */
 365         if (ISSET(t, B_DELCRSR)) {
 366                 CLR(t, B_DELCRSR);                      /* Don't try twice. */
 367                 if (c->pgno == delc.pgno && c->index > delc.index)
 368                         --c->index;
 369                 if (__bt_crsrdel(t, &delc))
 370                         return (RET_ERROR);
 371         }
 372         return (RET_SUCCESS);
 373 }
 374
 375 /*
 376  * __BT_CRSRDEL -- Delete the record referenced by the cursor.
 377  *
 378  * Parameters:
 379  *      t:      tree
 380  *
 381  * Returns:
 382  *      RET_ERROR, RET_SUCCESS
 383  */
 384 int
 385 __bt_crsrdel(t, c)
 386         BTREE *t;
 387         EPGNO *c;
 388 {
 389         PAGE *h;
 390         int status;
 391
 392         CLR(t, B_DELCRSR);                      /* Don't try twice. */
 393         if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
 394                 return (RET_ERROR);
 395         status = __bt_dleaf(t, h, c->index);
 396         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 397         return (status);
 398 }