cde/programs/dtinfo/DtMmdb/btree_berkeley/bt_get.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: bt_get.c /main/3 1996/06/11 17:12:34 cde-hal $ */
  24 /*-
  25  * Copyright (c) 1990, 1993
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * This code is derived from software contributed to Berkeley by
  29  * Mike Olson.
  30  *
  31  * Redistribution and use in source and binary forms, with or without
  32  * modification, are permitted provided that the following conditions
  33  * are met:
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in the
  38  *    documentation and/or other materials provided with the distribution.
  39  * 3. All advertising materials mentioning features or use of this software
  40  *    must display the following acknowledgement:
  41  *      This product includes software developed by the University of
  42  *      California, Berkeley and its contributors.
  43  * 4. Neither the name of the University nor the names of its contributors
  44  *    may be used to endorse or promote products derived from this software
  45  *    without specific prior written permission.
  46  *
  47  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57  * SUCH DAMAGE.
  58  */
  59
  60 #if defined(LIBC_SCCS) && !defined(lint)
  61 static char sccsid[] = "@(#)bt_get.c    8.2 (Berkeley) 9/7/93";
  62 #endif /* LIBC_SCCS and not lint */
  63
  64 #include <sys/types.h>
  65
  66 #include <errno.h>
  67 #include <stddef.h>
  68 #include <stdio.h>
  69
  70 #include <db.h>
  71 #include "btree.h"
  72
  73 /*
  74  * __BT_GET -- Get a record from the btree.
  75  *
  76  * Parameters:
  77  *      dbp:    pointer to access method
  78  *      key:    key to find
  79  *      data:   data to return
  80  *      flag:   currently unused
  81  *
  82  * Returns:
  83  *      RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  84  */
  85 int
  86 __bt_get(dbp, key, data, flags)
  87         const DB *dbp;
  88         const DBT *key;
  89         DBT *data;
  90         u_int flags;
  91 {
  92         BTREE *t;
  93         EPG *e;
  94         int exact, status;
  95
  96         t = dbp->internal;
  97
  98         /* Toss any page pinned across calls. */
  99         if (t->bt_pinned != NULL) {
 100                 mpool_put(t->bt_mp, t->bt_pinned, 0);
 101                 t->bt_pinned = NULL;
 102         }
 103
 104         /* Get currently doesn't take any flags. */
 105         if (flags) {
 106                 errno = EINVAL;
 107                 return (RET_ERROR);
 108         }
 109
 110         if ((e = __bt_search(t, key, &exact)) == NULL)
 111                 return (RET_ERROR);
 112         if (!exact) {
 113                 mpool_put(t->bt_mp, e->page, 0);
 114                 return (RET_SPECIAL);
 115         }
 116
 117         /*
 118          * A special case is if we found the record but it's flagged for
 119          * deletion.  In this case, we want to find another record with the
 120          * same key, if it exists.  Rather than look around the tree we call
 121          * __bt_first and have it redo the search, as __bt_first will not
 122          * return keys marked for deletion.  Slow, but should never happen.
 123          */
 124         if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
 125             e->index == t->bt_bcursor.index) {
 126                 mpool_put(t->bt_mp, e->page, 0);
 127                 if ((e = __bt_first(t, key, &exact)) == NULL)
 128                         return (RET_ERROR);
 129                 if (!exact)
 130                         return (RET_SPECIAL);
 131         }
 132
 133         status = __bt_ret(t, e, NULL, data);
 134         /*
 135          * If the user is doing concurrent access, we copied the
 136          * key/data, toss the page.
 137          */
 138         if (ISSET(t, B_DB_LOCK))
 139                 mpool_put(t->bt_mp, e->page, 0);
 140         else
 141                 t->bt_pinned = e->page;
 142         return (status);
 143 }
 144
 145 /*
 146  * __BT_FIRST -- Find the first entry.
 147  *
 148  * Parameters:
 149  *      t:      the tree
 150  *      key:    the key
 151  *
 152  * Returns:
 153  *      The first entry in the tree greater than or equal to key.
 154  */
 155 EPG *
 156 __bt_first(t, key, exactp)
 157         BTREE *t;
 158         const DBT *key;
 159         int *exactp;
 160 {
 161         register PAGE *h;
 162         register EPG *e;
 163         EPG save;
 164         pgno_t cpgno, pg;
 165         indx_t cindex;
 166         int found;
 167
 168         /*
 169          * Find any matching record; __bt_search pins the page.  Only exact
 170          * matches are tricky, otherwise just return the location of the key
 171          * if it were to be inserted into the tree.
 172          */
 173         if ((e = __bt_search(t, key, exactp)) == NULL)
 174                 return (NULL);
 175         if (!*exactp)
 176                 return (e);
 177
 178         if (ISSET(t, B_DELCRSR)) {
 179                 cpgno = t->bt_bcursor.pgno;
 180                 cindex = t->bt_bcursor.index;
 181         } else {
 182                 cpgno = P_INVALID;
 183                 cindex = 0;             /* GCC thinks it's uninitialized. */
 184         }
 185
 186         /*
 187          * Walk backwards, skipping empty pages, as long as the entry matches
 188          * and there are keys left in the tree.  Save a copy of each match in
 189          * case we go too far.  A special case is that we don't return a match
 190          * on records that the cursor references that have already been flagged
 191          * for deletion.
 192          */
 193         save = *e;
 194         h = e->page;
 195         found = 0;
 196         do {
 197                 if (cpgno != h->pgno || cindex != e->index) {
 198                         if (save.page->pgno != e->page->pgno) {
 199                                 mpool_put(t->bt_mp, save.page, 0);
 200                                 save = *e;
 201                         } else
 202                                 save.index = e->index;
 203                         found = 1;
 204                 }
 205                 /*
 206                  * Make a special effort not to unpin the page the last (or
 207                  * original) match was on, but also make sure it's unpinned
 208                  * if an error occurs.
 209                  */
 210                 while (e->index == 0) {
 211                         if (h->prevpg == P_INVALID)
 212                                 goto done1;
 213                         if (h->pgno != save.page->pgno)
 214                                 mpool_put(t->bt_mp, h, 0);
 215                         if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
 216                                 if (h->pgno == save.page->pgno)
 217                                         mpool_put(t->bt_mp, save.page, 0);
 218                                 return (NULL);
 219                         }
 220                         e->page = h;
 221                         e->index = NEXTINDEX(h);
 222                 }
 223                 --e->index;
 224         } while (__bt_cmp(t, key, e) == 0);
 225
 226         /*
 227          * Reach here with the last page that was looked at pinned, which may
 228          * or may not be the same as the last (or original) match page.  If
 229          * it's not useful, release it.
 230          */
 231 done1:  if (h->pgno != save.page->pgno)
 232                 mpool_put(t->bt_mp, h, 0);
 233
 234         /*
 235          * If still haven't found a record, the only possibility left is the
 236          * next one.  Move forward one slot, skipping empty pages and check.
 237          */
 238         if (!found) {
 239                 h = save.page;
 240                 if (++save.index == NEXTINDEX(h)) {
 241                         do {
 242                                 pg = h->nextpg;
 243                                 mpool_put(t->bt_mp, h, 0);
 244                                 if (pg == P_INVALID) {
 245                                         *exactp = 0;
 246                                         return (e);
 247                                 }
 248                                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 249                                         return (NULL);
 250                         } while ((save.index = NEXTINDEX(h)) == 0);
 251                         save.page = h;
 252                 }
 253                 if (__bt_cmp(t, key, &save) != 0) {
 254                         *exactp = 0;
 255                         return (e);
 256                 }
 257         }
 258         *e = save;
 259         *exactp = 1;
 260         return (e);
 261 }