1 /* $NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Mike Olson. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #if defined(LIBC_SCCS) && !defined(lint) 40 #if 0 41 static char sccsid[] = "@(#)bt_search.c 8.6 (Berkeley) 3/15/94"; 42 #else 43 static char rcsid[] = "$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $"; 44 #endif 45 #endif /* LIBC_SCCS and not lint */ 46 47 #include <sys/types.h> 48 49 #include <stdio.h> 50 51 #include <db.h> 52 #include "btree.h" 53 54 static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); 55 static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); 56 57 /* 58 * __BT_SEARCH -- Search a btree for a key. 59 * 60 * Parameters: 61 * t: tree to search 62 * key: key to find 63 * exactp: pointer to exact match flag 64 * 65 * Returns: 66 * The EPG for matching record, if any, or the EPG for the location 67 * of the key, if it were inserted into the tree, is entered into 68 * the bt_cur field of the tree. A pointer to the field is returned. 69 */ 70 EPG * 71 __bt_search(t, key, exactp) 72 BTREE *t; 73 const DBT *key; 74 int *exactp; 75 { 76 PAGE *h; 77 indx_t base, index, lim; 78 pgno_t pg; 79 int cmp; 80 81 BT_CLR(t); 82 for (pg = P_ROOT;;) { 83 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 84 return (NULL); 85 86 /* Do a binary search on the current page. */ 87 t->bt_cur.page = h; 88 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 89 t->bt_cur.index = index = base + (lim >> 1); 90 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { 91 if (h->flags & P_BLEAF) { 92 *exactp = 1; 93 return (&t->bt_cur); 94 } 95 goto next; 96 } 97 if (cmp > 0) { 98 base = index + 1; 99 --lim; 100 } 101 } 102 103 /* 104 * If it's a leaf page, and duplicates aren't allowed, we're 105 * done. If duplicates are allowed, it's possible that there 106 * were duplicate keys on duplicate pages, and they were later 107 * deleted, so we could be on a page with no matches while 108 * there are matches on other pages. If we're at the start or 109 * end of a page, check on both sides. 110 */ 111 if (h->flags & P_BLEAF) { 112 t->bt_cur.index = base; 113 *exactp = 0; 114 if (!ISSET(t, B_NODUPS)) { 115 if (base == 0 && 116 bt_sprev(t, h, key, exactp)) 117 return (&t->bt_cur); 118 if (base == NEXTINDEX(h) && 119 bt_snext(t, h, key, exactp)) 120 return (&t->bt_cur); 121 } 122 return (&t->bt_cur); 123 } 124 125 /* 126 * No match found. Base is the smallest index greater than 127 * key and may be zero or a last + 1 index. If it's non-zero, 128 * decrement by one, and record the internal page which should 129 * be a parent page for the key. If a split later occurs, the 130 * inserted page will be to the right of the saved page. 131 */ 132 index = base ? base - 1 : base; 133 134 next: if (__bt_push(t, h->pgno, index) == RET_ERROR) 135 return (NULL); 136 pg = GETBINTERNAL(h, index)->pgno; 137 mpool_put(t->bt_mp, h, 0); 138 } 139 } 140 141 /* 142 * BT_SNEXT -- Check for an exact match after the key. 143 * 144 * Parameters: 145 * t: tree to search 146 * h: current page. 147 * key: key to find 148 * exactp: pointer to exact match flag 149 * 150 * Returns: 151 * If an exact match found. 152 */ 153 static int 154 bt_snext(t, h, key, exactp) 155 BTREE *t; 156 PAGE *h; 157 const DBT *key; 158 int *exactp; 159 { 160 EPG e; 161 PAGE *tp; 162 pgno_t pg; 163 164 /* Skip until reach the end of the tree or a key. */ 165 for (pg = h->nextpg; pg != P_INVALID;) { 166 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { 167 mpool_put(t->bt_mp, h, 0); 168 return (NULL); 169 } 170 if (NEXTINDEX(tp) != 0) 171 break; 172 pg = tp->prevpg; 173 mpool_put(t->bt_mp, tp, 0); 174 } 175 /* 176 * The key is either an exact match, or not as good as 177 * the one we already have. 178 */ 179 if (pg != P_INVALID) { 180 e.page = tp; 181 e.index = NEXTINDEX(tp) - 1; 182 if (__bt_cmp(t, key, &e) == 0) { 183 mpool_put(t->bt_mp, h, 0); 184 t->bt_cur = e; 185 *exactp = 1; 186 return (1); 187 } 188 } 189 return (0); 190 } 191 192 /* 193 * BT_SPREV -- Check for an exact match before the key. 194 * 195 * Parameters: 196 * t: tree to search 197 * h: current page. 198 * key: key to find 199 * exactp: pointer to exact match flag 200 * 201 * Returns: 202 * If an exact match found. 203 */ 204 static int 205 bt_sprev(t, h, key, exactp) 206 BTREE *t; 207 PAGE *h; 208 const DBT *key; 209 int *exactp; 210 { 211 EPG e; 212 PAGE *tp; 213 pgno_t pg; 214 215 /* Skip until reach the beginning of the tree or a key. */ 216 for (pg = h->prevpg; pg != P_INVALID;) { 217 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { 218 mpool_put(t->bt_mp, h, 0); 219 return (NULL); 220 } 221 if (NEXTINDEX(tp) != 0) 222 break; 223 pg = tp->prevpg; 224 mpool_put(t->bt_mp, tp, 0); 225 } 226 /* 227 * The key is either an exact match, or not as good as 228 * the one we already have. 229 */ 230 if (pg != P_INVALID) { 231 e.page = tp; 232 e.index = NEXTINDEX(tp) - 1; 233 if (__bt_cmp(t, key, &e) == 0) { 234 mpool_put(t->bt_mp, h, 0); 235 t->bt_cur = e; 236 *exactp = 1; 237 return (1); 238 } 239 } 240 return (0); 241 } 242