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 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)bt_search.c 5.4 (Berkeley) 09/12/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <db.h> 17 #include <stdio.h> 18 #include "btree.h" 19 20 /* 21 * __BT_SEARCH -- Search a btree for a key. 22 * 23 * Parameters: 24 * t: tree to search 25 * key: key to find 26 * exactp: pointer to exact match flag 27 * 28 * Returns: 29 * EPG for matching record, if any, or the EPG for the location of the 30 * key, if it were inserted into the tree. 31 * 32 * Warnings: 33 * The EPG returned is in static memory, and will be overwritten by the 34 * next search of any kind in any tree. 35 */ 36 EPG * 37 __bt_search(t, key, exactp) 38 BTREE *t; 39 const DBT *key; 40 int *exactp; 41 { 42 register index_t index; 43 register int base, cmp, lim; 44 register PAGE *h; 45 pgno_t pg; 46 static EPG e; 47 48 for (pg = P_ROOT;;) { 49 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 50 return (NULL); 51 52 /* Do a binary search on the current page. */ 53 e.page = h; 54 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 55 e.index = index = base + (lim >> 1); 56 if ((cmp = __bt_cmp(t, key, &e)) == 0) { 57 if (h->flags & P_BLEAF) { 58 *exactp = 1; 59 return (&e); 60 } 61 goto next; 62 } 63 if (cmp > 0) { 64 base = index + 1; 65 --lim; 66 } 67 } 68 69 /* 70 * No match found. Base is the smallest index greater than 71 * key but may be an illegal index. Use base if it's a leaf 72 * page, decrement it by one if it's an internal page. This 73 * is safe because internal pages can't be empty. 74 */ 75 index = h->flags & P_BLEAF ? base : base - 1; 76 77 /* If it's a leaf page, we're done. */ 78 if (h->flags & P_BLEAF) { 79 e.index = index; 80 *exactp = 0; 81 return (&e); 82 } 83 84 next: if (__bt_push(t, h->pgno, index) == RET_ERROR) 85 return (NULL); 86 pg = GETBINTERNAL(h, index)->pgno; 87 mpool_put(t->bt_mp, h, 0); 88 } 89 } 90