1*24420c01Scgd /* $NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $ */ 2a954b078Scgd 39f0aa214Scgd /*- 4*24420c01Scgd * Copyright (c) 1990, 1993, 1994 59f0aa214Scgd * The Regents of the University of California. All rights reserved. 69f0aa214Scgd * 79f0aa214Scgd * This code is derived from software contributed to Berkeley by 89f0aa214Scgd * Mike Olson. 99f0aa214Scgd * 109f0aa214Scgd * Redistribution and use in source and binary forms, with or without 119f0aa214Scgd * modification, are permitted provided that the following conditions 129f0aa214Scgd * are met: 139f0aa214Scgd * 1. Redistributions of source code must retain the above copyright 149f0aa214Scgd * notice, this list of conditions and the following disclaimer. 159f0aa214Scgd * 2. Redistributions in binary form must reproduce the above copyright 169f0aa214Scgd * notice, this list of conditions and the following disclaimer in the 179f0aa214Scgd * documentation and/or other materials provided with the distribution. 189f0aa214Scgd * 3. All advertising materials mentioning features or use of this software 199f0aa214Scgd * must display the following acknowledgement: 209f0aa214Scgd * This product includes software developed by the University of 219f0aa214Scgd * California, Berkeley and its contributors. 229f0aa214Scgd * 4. Neither the name of the University nor the names of its contributors 239f0aa214Scgd * may be used to endorse or promote products derived from this software 249f0aa214Scgd * without specific prior written permission. 259f0aa214Scgd * 269f0aa214Scgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 279f0aa214Scgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 289f0aa214Scgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 299f0aa214Scgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 309f0aa214Scgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 319f0aa214Scgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 329f0aa214Scgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 339f0aa214Scgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 349f0aa214Scgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 359f0aa214Scgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 369f0aa214Scgd * SUCH DAMAGE. 379f0aa214Scgd */ 389f0aa214Scgd 399f0aa214Scgd #if defined(LIBC_SCCS) && !defined(lint) 40a954b078Scgd #if 0 41*24420c01Scgd static char sccsid[] = "@(#)bt_search.c 8.8 (Berkeley) 7/31/94"; 42a954b078Scgd #else 43*24420c01Scgd static char rcsid[] = "$NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $"; 44a954b078Scgd #endif 459f0aa214Scgd #endif /* LIBC_SCCS and not lint */ 469f0aa214Scgd 479f0aa214Scgd #include <sys/types.h> 489f0aa214Scgd 499f0aa214Scgd #include <stdio.h> 509f0aa214Scgd 519f0aa214Scgd #include <db.h> 529f0aa214Scgd #include "btree.h" 539f0aa214Scgd 54*24420c01Scgd static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); 55*24420c01Scgd static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); 56f7b4cb00Scgd 579f0aa214Scgd /* 58*24420c01Scgd * __bt_search -- 59*24420c01Scgd * Search a btree for a key. 609f0aa214Scgd * 619f0aa214Scgd * Parameters: 629f0aa214Scgd * t: tree to search 639f0aa214Scgd * key: key to find 649f0aa214Scgd * exactp: pointer to exact match flag 659f0aa214Scgd * 669f0aa214Scgd * Returns: 6765aeeefbScgd * The EPG for matching record, if any, or the EPG for the location 6865aeeefbScgd * of the key, if it were inserted into the tree, is entered into 6965aeeefbScgd * the bt_cur field of the tree. A pointer to the field is returned. 709f0aa214Scgd */ 719f0aa214Scgd EPG * 729f0aa214Scgd __bt_search(t, key, exactp) 739f0aa214Scgd BTREE *t; 749f0aa214Scgd const DBT *key; 759f0aa214Scgd int *exactp; 769f0aa214Scgd { 77a6d14e36Scgd PAGE *h; 78a6d14e36Scgd indx_t base, index, lim; 799f0aa214Scgd pgno_t pg; 80a6d14e36Scgd int cmp; 819f0aa214Scgd 829f0aa214Scgd BT_CLR(t); 839f0aa214Scgd for (pg = P_ROOT;;) { 849f0aa214Scgd if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 859f0aa214Scgd return (NULL); 869f0aa214Scgd 879f0aa214Scgd /* Do a binary search on the current page. */ 8865aeeefbScgd t->bt_cur.page = h; 899f0aa214Scgd for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 9065aeeefbScgd t->bt_cur.index = index = base + (lim >> 1); 9165aeeefbScgd if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { 929f0aa214Scgd if (h->flags & P_BLEAF) { 939f0aa214Scgd *exactp = 1; 9465aeeefbScgd return (&t->bt_cur); 959f0aa214Scgd } 969f0aa214Scgd goto next; 979f0aa214Scgd } 989f0aa214Scgd if (cmp > 0) { 999f0aa214Scgd base = index + 1; 1009f0aa214Scgd --lim; 1019f0aa214Scgd } 1029f0aa214Scgd } 1039f0aa214Scgd 104f7b4cb00Scgd /* 105*24420c01Scgd * If it's a leaf page, we're almost done. If no duplicates 106*24420c01Scgd * are allowed, or we have an exact match, we're done. Else, 107*24420c01Scgd * it's possible that there were matching keys on this page, 108*24420c01Scgd * which later deleted, and we're on a page with no matches 109*24420c01Scgd * while there are matches on other pages. If at the start or 110*24420c01Scgd * end of a page, check the adjacent page. 111f7b4cb00Scgd */ 1129f0aa214Scgd if (h->flags & P_BLEAF) { 113*24420c01Scgd if (!F_ISSET(t, B_NODUPS)) { 114f7b4cb00Scgd if (base == 0 && 115*24420c01Scgd h->prevpg != P_INVALID && 116*24420c01Scgd __bt_sprev(t, h, key, exactp)) 117f7b4cb00Scgd return (&t->bt_cur); 118f7b4cb00Scgd if (base == NEXTINDEX(h) && 119*24420c01Scgd h->nextpg != P_INVALID && 120*24420c01Scgd __bt_snext(t, h, key, exactp)) 121f7b4cb00Scgd return (&t->bt_cur); 122f7b4cb00Scgd } 123*24420c01Scgd *exactp = 0; 124*24420c01Scgd t->bt_cur.index = base; 12565aeeefbScgd return (&t->bt_cur); 1269f0aa214Scgd } 1279f0aa214Scgd 1289f0aa214Scgd /* 1299f0aa214Scgd * No match found. Base is the smallest index greater than 1309f0aa214Scgd * key and may be zero or a last + 1 index. If it's non-zero, 1319f0aa214Scgd * decrement by one, and record the internal page which should 1329f0aa214Scgd * be a parent page for the key. If a split later occurs, the 1339f0aa214Scgd * inserted page will be to the right of the saved page. 1349f0aa214Scgd */ 1359f0aa214Scgd index = base ? base - 1 : base; 1369f0aa214Scgd 137*24420c01Scgd next: BT_PUSH(t, h->pgno, index); 1389f0aa214Scgd pg = GETBINTERNAL(h, index)->pgno; 1399f0aa214Scgd mpool_put(t->bt_mp, h, 0); 1409f0aa214Scgd } 1419f0aa214Scgd } 142f7b4cb00Scgd 143f7b4cb00Scgd /* 144*24420c01Scgd * __bt_snext -- 145*24420c01Scgd * Check for an exact match after the key. 146f7b4cb00Scgd * 147f7b4cb00Scgd * Parameters: 148*24420c01Scgd * t: tree 149*24420c01Scgd * h: current page 150*24420c01Scgd * key: key 151f7b4cb00Scgd * exactp: pointer to exact match flag 152f7b4cb00Scgd * 153f7b4cb00Scgd * Returns: 154f7b4cb00Scgd * If an exact match found. 155f7b4cb00Scgd */ 156f7b4cb00Scgd static int 157*24420c01Scgd __bt_snext(t, h, key, exactp) 158f7b4cb00Scgd BTREE *t; 159f7b4cb00Scgd PAGE *h; 160f7b4cb00Scgd const DBT *key; 161f7b4cb00Scgd int *exactp; 162f7b4cb00Scgd { 163f7b4cb00Scgd EPG e; 164f7b4cb00Scgd 165f7b4cb00Scgd /* 166*24420c01Scgd * Get the next page. The key is either an exact 167*24420c01Scgd * match, or not as good as the one we already have. 168f7b4cb00Scgd */ 169*24420c01Scgd if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 170*24420c01Scgd return (0); 171*24420c01Scgd e.index = 0; 172f7b4cb00Scgd if (__bt_cmp(t, key, &e) == 0) { 173f7b4cb00Scgd mpool_put(t->bt_mp, h, 0); 174f7b4cb00Scgd t->bt_cur = e; 175f7b4cb00Scgd *exactp = 1; 176f7b4cb00Scgd return (1); 177f7b4cb00Scgd } 178*24420c01Scgd mpool_put(t->bt_mp, e.page, 0); 179f7b4cb00Scgd return (0); 180f7b4cb00Scgd } 181f7b4cb00Scgd 182f7b4cb00Scgd /* 183*24420c01Scgd * __bt_sprev -- 184*24420c01Scgd * Check for an exact match before the key. 185f7b4cb00Scgd * 186f7b4cb00Scgd * Parameters: 187*24420c01Scgd * t: tree 188*24420c01Scgd * h: current page 189*24420c01Scgd * key: key 190f7b4cb00Scgd * exactp: pointer to exact match flag 191f7b4cb00Scgd * 192f7b4cb00Scgd * Returns: 193f7b4cb00Scgd * If an exact match found. 194f7b4cb00Scgd */ 195f7b4cb00Scgd static int 196*24420c01Scgd __bt_sprev(t, h, key, exactp) 197f7b4cb00Scgd BTREE *t; 198f7b4cb00Scgd PAGE *h; 199f7b4cb00Scgd const DBT *key; 200f7b4cb00Scgd int *exactp; 201f7b4cb00Scgd { 202f7b4cb00Scgd EPG e; 203f7b4cb00Scgd 204f7b4cb00Scgd /* 205*24420c01Scgd * Get the previous page. The key is either an exact 206*24420c01Scgd * match, or not as good as the one we already have. 207f7b4cb00Scgd */ 208*24420c01Scgd if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 209*24420c01Scgd return (0); 210*24420c01Scgd e.index = NEXTINDEX(e.page) - 1; 211f7b4cb00Scgd if (__bt_cmp(t, key, &e) == 0) { 212f7b4cb00Scgd mpool_put(t->bt_mp, h, 0); 213f7b4cb00Scgd t->bt_cur = e; 214f7b4cb00Scgd *exactp = 1; 215f7b4cb00Scgd return (1); 216f7b4cb00Scgd } 217*24420c01Scgd mpool_put(t->bt_mp, e.page, 0); 218f7b4cb00Scgd return (0); 219f7b4cb00Scgd } 220