db/btree/bt_search.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_search.c 8.8 (Berkeley) 7/31/94";
  63 #endif /* LIBC_SCCS and not lint */
  64 #include <sys/cdefs.h>
  65
  66 #include <sys/types.h>
  67
  68 #include <stdio.h>
  69
  70 #include <db.h>
  71 #include "btree.h"
  72
  73 static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
  74 static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);
  75
  76 /*
  77  * __bt_search --
  78  *      Search a btree for a key.
  79  *
  80  * Parameters:
  81  *      t:      tree to search
  82  *      key:    key to find
  83  *      exactp: pointer to exact match flag
  84  *
  85  * Returns:
  86  *      The EPG for matching record, if any, or the EPG for the location
  87  *      of the key, if it were inserted into the tree, is entered into
  88  *      the bt_cur field of the tree.  A pointer to the field is returned.
  89  */
  90 EPG *
  91 __bt_search(t, key, exactp)
  92         BTREE *t;
  93         const DBT *key;
  94         int *exactp;
  95 {
  96         PAGE *h;
  97         indx_t base, index, lim;
  98         pgno_t pg;
  99         int cmp;
 100
 101         BT_CLR(t);
 102         for (pg = P_ROOT;;) {
 103                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 104                         return (NULL);
 105
 106                 /* Do a binary search on the current page. */
 107                 t->bt_cur.page = h;
 108                 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
 109                         t->bt_cur.index = index = base + (lim >> 1);
 110                         if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
 111                                 if (h->flags & P_BLEAF) {
 112                                         *exactp = 1;
 113                                         return (&t->bt_cur);
 114                                 }
 115                                 goto next;
 116                         }
 117                         if (cmp > 0) {
 118                                 base = index + 1;
 119                                 --lim;
 120                         }
 121                 }
 122
 123                 /*
 124                  * If it's a leaf page, we're almost done.  If no duplicates
 125                  * are allowed, or we have an exact match, we're done.  Else,
 126                  * it's possible that there were matching keys on this page,
 127                  * which later deleted, and we're on a page with no matches
 128                  * while there are matches on other pages.  If at the start or
 129                  * end of a page, check the adjacent page.
 130                  */
 131                 if (h->flags & P_BLEAF) {
 132                         if (!F_ISSET(t, B_NODUPS)) {
 133                                 if (base == 0 &&
 134                                     h->prevpg != P_INVALID &&
 135                                     __bt_sprev(t, h, key, exactp))
 136                                         return (&t->bt_cur);
 137                                 if (base == NEXTINDEX(h) &&
 138                                     h->nextpg != P_INVALID &&
 139                                     __bt_snext(t, h, key, exactp))
 140                                         return (&t->bt_cur);
 141                         }
 142                         *exactp = 0;
 143                         t->bt_cur.index = base;
 144                         return (&t->bt_cur);
 145                 }
 146
 147                 /*
 148                  * No match found.  Base is the smallest index greater than
 149                  * key and may be zero or a last + 1 index.  If it's non-zero,
 150                  * decrement by one, and record the internal page which should
 151                  * be a parent page for the key.  If a split later occurs, the
 152                  * inserted page will be to the right of the saved page.
 153                  */
 154                 index = base ? base - 1 : base;
 155
 156 next:           BT_PUSH(t, h->pgno, index);
 157                 pg = GETBINTERNAL(h, index)->pgno;
 158                 mpool_put(t->bt_mp, h, 0);
 159         }
 160 }
 161
 162 /*
 163  * __bt_snext --
 164  *      Check for an exact match after the key.
 165  *
 166  * Parameters:
 167  *      t:      tree
 168  *      h:      current page
 169  *      key:    key
 170  *      exactp: pointer to exact match flag
 171  *
 172  * Returns:
 173  *      If an exact match found.
 174  */
 175 static int
 176 __bt_snext(t, h, key, exactp)
 177         BTREE *t;
 178         PAGE *h;
 179         const DBT *key;
 180         int *exactp;
 181 {
 182         EPG e;
 183
 184         /*
 185          * Get the next page.  The key is either an exact
 186          * match, or not as good as the one we already have.
 187          */
 188         if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
 189                 return (0);
 190         e.index = 0;
 191         if (__bt_cmp(t, key, &e) == 0) {
 192                 mpool_put(t->bt_mp, h, 0);
 193                 t->bt_cur = e;
 194                 *exactp = 1;
 195                 return (1);
 196         }
 197         mpool_put(t->bt_mp, e.page, 0);
 198         return (0);
 199 }
 200
 201 /*
 202  * __bt_sprev --
 203  *      Check for an exact match before the key.
 204  *
 205  * Parameters:
 206  *      t:      tree
 207  *      h:      current page
 208  *      key:    key
 209  *      exactp: pointer to exact match flag
 210  *
 211  * Returns:
 212  *      If an exact match found.
 213  */
 214 static int
 215 __bt_sprev(t, h, key, exactp)
 216         BTREE *t;
 217         PAGE *h;
 218         const DBT *key;
 219         int *exactp;
 220 {
 221         EPG e;
 222
 223         /*
 224          * Get the previous page.  The key is either an exact
 225          * match, or not as good as the one we already have.
 226          */
 227         if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
 228                 return (0);
 229         e.index = NEXTINDEX(e.page) - 1;
 230         if (__bt_cmp(t, key, &e) == 0) {
 231                 mpool_put(t->bt_mp, h, 0);
 232                 t->bt_cur = e;
 233                 *exactp = 1;
 234                 return (1);
 235         }
 236         mpool_put(t->bt_mp, e.page, 0);
 237         return (0);
 238 }