lib/libc/db/btree/seq.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * 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[] = "@(#)seq.c       5.4 (Berkeley) 3/3/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42 #include <errno.h>
  43 #include <db.h>
  44 #include <stdlib.h>
  45 #include "btree.h"
  46
  47 /*
  48  *  _BT_SEQINIT -- Initialize a sequential scan on the btree.
  49  *
  50  *      Sets the tree's notion of the current scan location correctly
  51  *      given a key and a direction.
  52  *
  53  *      Parameters:
  54  *              t -- tree in which to initialize scan
  55  *              key -- key for initial scan position
  56  *              flags -- R_NEXT, R_PREV
  57  *
  58  *      Returns:
  59  *              RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data
  60  *              in the tree to scan.
  61  *
  62  *      Side Effects:
  63  *              Changes current scan position for the tree.  Almost certainly
  64  *              changes current page, as well.  Sets BTF_SEQINIT bit in tree
  65  *              flags, so that we know we've initialized a scan.
  66  */
  67
  68 int
  69 _bt_seqinit(t, key, flags)
  70         BTREE_P t;
  71         DBT *key;
  72         int flags;
  73 {
  74         BTITEM *item;
  75         BTHEADER *h;
  76         CURSOR *c;
  77         IDATUM *id;
  78         index_t last;
  79
  80         /*
  81          *  Figure out if we really have to search for the key that the
  82          *  user supplied.  If key is null, then this is an unkeyed scan
  83          *  and we can just start from an endpoint.
  84          */
  85
  86         c = &(t->bt_cursor);
  87
  88         if (flags == R_CURSOR) {
  89                 if (key->data != (u_char *) NULL) {
  90
  91                         /* key supplied, find first instance of it */
  92                         item = _bt_first(t, key);
  93                         c->c_index = item->bti_index;
  94                         c->c_pgno = t->bt_curpage->h_pgno;
  95                 } else {
  96                         errno = EINVAL;
  97                         return (RET_ERROR);
  98                 }
  99
 100         } else {
 101
 102                 /*
 103                  *  Unkeyed scan.  For backward scans, find the last item
 104                  *  in the tree; for forward scans, find the first item.
 105                  */
 106
 107                 if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
 108                         return (RET_ERROR);
 109                 h = t->bt_curpage;
 110                 if (flags == R_LAST || flags == R_PREV) {
 111
 112                         /* backward scan */
 113                         while (!(h->h_flags & F_LEAF)) {
 114                                 last = NEXTINDEX(h) - 1;
 115                                 id = (IDATUM *) GETDATUM(h,last);
 116                                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
 117                                         return (RET_ERROR);
 118                                 h = t->bt_curpage;
 119                         }
 120
 121                         /* skip empty pages */
 122                         while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE) {
 123                                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
 124                                         return (RET_ERROR);
 125                                 h = t->bt_curpage;
 126                         }
 127
 128                         c->c_pgno = h->h_pgno;
 129                         if (NEXTINDEX(h) > 0)
 130                                 c->c_index = NEXTINDEX(h) - 1;
 131                         else
 132                                 c->c_index = 0;
 133                 } else if (flags == R_FIRST || flags == R_NEXT) {
 134                         /* forward scan */
 135                         while (!(h->h_flags & F_LEAF)) {
 136                                 id = (IDATUM *) GETDATUM(h,0);
 137                                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
 138                                         return (RET_ERROR);
 139                                 h = t->bt_curpage;
 140                         }
 141
 142                         /* skip empty pages */
 143                         while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE) {
 144                                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
 145                                         return (RET_ERROR);
 146                                 h = t->bt_curpage;
 147                         }
 148
 149                         c->c_pgno = h->h_pgno;
 150                         c->c_index = 0;
 151                 } else {
 152                         /* no flags passed in */
 153                         errno = EINVAL;
 154                         return (RET_ERROR);
 155                 }
 156         }
 157
 158         /* okay, scan is initialized */
 159         t->bt_flags |= BTF_SEQINIT;
 160
 161         /* don't need the descent stack anymore */
 162         while (_bt_pop(t) != P_NONE)
 163                 continue;
 164
 165         if (c->c_index == NEXTINDEX(t->bt_curpage))
 166                 return (RET_SPECIAL);
 167
 168         return (RET_SUCCESS);
 169 }
 170
 171 /*
 172  *  _BT_SEQADVANCE -- Advance the sequential scan on this tree.
 173  *
 174  *      Moves the current location pointer for the scan on this tree one
 175  *      spot in the requested direction.
 176  *
 177  *      Parameters:
 178  *              t -- btree being scanned
 179  *              flags -- for R_NEXT, R_PREV
 180  *
 181  *      Returns:
 182  *              RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no
 183  *              more data in the specified direction.
 184  *
 185  *      Side Effects:
 186  *              May change current page.
 187  */
 188
 189 int
 190 _bt_seqadvance(t, flags)
 191         BTREE_P t;
 192         int flags;
 193 {
 194         BTHEADER *h;
 195         CURSOR *c;
 196         index_t index;
 197
 198         c = &(t->bt_cursor);
 199         index = c->c_index;
 200
 201         if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
 202                 return (RET_ERROR);
 203         h = t->bt_curpage;
 204
 205         /* by the time we get here, don't need the cursor key anymore */
 206         if (c->c_key != (char *) NULL)
 207                 (void) free(c->c_key);
 208
 209         if (flags == R_NEXT) {
 210
 211                 /*
 212                  *  This is a forward scan.  If the cursor is pointing
 213                  *  at a virtual record (that is, it was pointing at
 214                  *  a record that got deleted), then we should return
 215                  *  the record it's pointing at now.  Otherwise, we
 216                  *  should advance the scan.  In either case, we need
 217                  *  to be careful not to run off the end of the current
 218                  *  page.
 219                  */
 220
 221                 if (c->c_flags & CRSR_BEFORE) {
 222
 223                         if (index >= NEXTINDEX(h)) {
 224                                 /* out of items on this page, get next page */
 225                                 if (h->h_nextpg == P_NONE) {
 226                                         /* tell caller we're done... */
 227                                         c->c_index = NEXTINDEX(h);
 228                                         return (RET_SPECIAL);
 229                                 }
 230
 231                                 /* skip empty pages */
 232                                 do {
 233                                         if (_bt_getpage(t, h->h_nextpg)
 234                                             == RET_ERROR) {
 235                                                 c->c_index = NEXTINDEX(h);
 236                                                 return (RET_ERROR);
 237                                         }
 238                                         h = t->bt_curpage;
 239                                         c->c_pgno = h->h_pgno;
 240                                 } while (NEXTINDEX(h) == 0
 241                                          && h->h_nextpg != P_NONE);
 242
 243                                 if (NEXTINDEX(h) == 0) {
 244                                         /* tell caller we're done */
 245                                         c->c_index = NEXTINDEX(h);
 246                                         return (RET_SPECIAL);
 247                                 }
 248                                 index = 0;
 249                         }
 250                         c->c_flags &= ~CRSR_BEFORE;
 251
 252                 } else if (++index >= NEXTINDEX(h)) {
 253
 254                         /* out of items on this page, get next page */
 255                         if (h->h_nextpg == P_NONE) {
 256                                 /* tell caller we're done... */
 257                                 c->c_index = NEXTINDEX(h);
 258                                 return (RET_SPECIAL);
 259                         }
 260
 261                         /* skip empty pages */
 262                         do {
 263                                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) {
 264                                         c->c_index = NEXTINDEX(h);
 265                                         return (RET_ERROR);
 266                                 }
 267                                 h = t->bt_curpage;
 268                                 c->c_pgno = h->h_pgno;
 269                         } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
 270
 271                         if (NEXTINDEX(h) == 0) {
 272                                 /* tell caller we're done */
 273                                 c->c_index = NEXTINDEX(h);
 274                                 return (RET_SPECIAL);
 275                         }
 276                         index = 0;
 277                 }
 278         } else if (flags == R_PREV) {
 279
 280                 /* for backward scans, life is substantially easier */
 281                 c->c_flags &= ~CRSR_BEFORE;
 282                 if (c->c_key != (char *) NULL) {
 283                         (void) free(c->c_key);
 284                         c->c_key = (char *) NULL;
 285                 }
 286
 287                 if (index == 0) {
 288
 289                         /* we may be done */
 290                         c->c_index = 0;
 291
 292                         /* out of items on this page, get next page */
 293                         if (h->h_prevpg == P_NONE)
 294                                 return (RET_SPECIAL);
 295
 296                         /* skip empty pages */
 297                         do {
 298                                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
 299                                         return (RET_ERROR);
 300                                 h = t->bt_curpage;
 301                                 c->c_pgno = h->h_pgno;
 302                         } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
 303
 304                         if (NEXTINDEX(h) == 0)
 305                                 return (RET_SPECIAL);
 306
 307                         index = NEXTINDEX(h) - 1;
 308                 } else
 309                         --index;
 310         } else {
 311                 /* must specify a direction */
 312                 errno = EINVAL;
 313                 return (RET_ERROR);
 314         }
 315
 316         c->c_index = index;
 317         return (RET_SUCCESS);
 318 }