1 /*- 2 * Copyright (c) 1990, 1993 3 * The Regents of the University of California. 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 8.2 (Berkeley) 09/14/93"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 17 #include <stdio.h> 18 19 #include <db.h> 20 #include "btree.h" 21 22 /* 23 * __BT_SEARCH -- Search a btree for a key. 24 * 25 * Parameters: 26 * t: tree to search 27 * key: key to find 28 * exactp: pointer to exact match flag 29 * 30 * Returns: 31 * The EPG for matching record, if any, or the EPG for the location 32 * of the key, if it were inserted into the tree, is entered into 33 * the bt_cur field of the tree. A pointer to the field is returned. 34 */ 35 EPG * 36 __bt_search(t, key, exactp) 37 BTREE *t; 38 const DBT *key; 39 int *exactp; 40 { 41 register indx_t index; 42 register int base, cmp, lim; 43 register PAGE *h; 44 pgno_t pg; 45 46 BT_CLR(t); 47 for (pg = P_ROOT;;) { 48 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 49 return (NULL); 50 51 /* Do a binary search on the current page. */ 52 t->bt_cur.page = h; 53 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 54 t->bt_cur.index = index = base + (lim >> 1); 55 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { 56 if (h->flags & P_BLEAF) { 57 *exactp = 1; 58 return (&t->bt_cur); 59 } 60 goto next; 61 } 62 if (cmp > 0) { 63 base = index + 1; 64 --lim; 65 } 66 } 67 68 /* If it's a leaf page, we're done. */ 69 if (h->flags & P_BLEAF) { 70 t->bt_cur.index = base; 71 *exactp = 0; 72 return (&t->bt_cur); 73 } 74 75 /* 76 * No match found. Base is the smallest index greater than 77 * key and may be zero or a last + 1 index. If it's non-zero, 78 * decrement by one, and record the internal page which should 79 * be a parent page for the key. If a split later occurs, the 80 * inserted page will be to the right of the saved page. 81 */ 82 index = base ? base - 1 : base; 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