146132Smao /*- 246132Smao * Copyright (c) 1990 The Regents of the University of California. 346132Smao * All rights reserved. 446132Smao * 546132Smao * This code is derived from software contributed to Berkeley by 646132Smao * Mike Olson. 746132Smao * 846132Smao * %sccs.include.redist.c% 946132Smao */ 1046132Smao 1146132Smao #if defined(LIBC_SCCS) && !defined(lint) 12*50989Sbostic static char sccsid[] = "@(#)bt_search.c 5.3 (Berkeley) 09/04/91"; 1346132Smao #endif /* LIBC_SCCS and not lint */ 1446132Smao 1546132Smao #include <sys/types.h> 1646132Smao #include <db.h> 17*50989Sbostic #include <stdio.h> 1846132Smao #include "btree.h" 1946132Smao 2046132Smao /* 21*50989Sbostic * __BT_SEARCH -- Search a btree for a key. 2246132Smao * 23*50989Sbostic * Parameters: 24*50989Sbostic * t: tree to search 25*50989Sbostic * key: key to find 26*50989Sbostic * exactp: pointer to exact match flag 2746132Smao * 28*50989Sbostic * Returns: 29*50989Sbostic * EPG for matching record, if any, or the EPG for the location of the 30*50989Sbostic * key, if it were inserted into the tree. 3146132Smao * 32*50989Sbostic * Warnings: 33*50989Sbostic * The EPG returned is in static memory, and will be overwritten by the 34*50989Sbostic * next search of any kind in any tree. 3546132Smao */ 36*50989Sbostic EPG * 37*50989Sbostic __bt_search(t, key, exactp) 38*50989Sbostic BTREE *t; 39*50989Sbostic const DBT *key; 40*50989Sbostic int *exactp; 4146132Smao { 42*50989Sbostic register index_t index; 43*50989Sbostic register int base, cmp, lim; 44*50989Sbostic register PAGE *h; 45*50989Sbostic pgno_t pg; 46*50989Sbostic static EPG e; 4746132Smao 48*50989Sbostic for (pg = P_ROOT;;) { 49*50989Sbostic if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 50*50989Sbostic return (NULL); 5146132Smao 52*50989Sbostic /* Do a binary search on the current page. */ 53*50989Sbostic e.page = h; 54*50989Sbostic for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 55*50989Sbostic e.index = index = base + (lim >> 1); 56*50989Sbostic if ((cmp = __bt_cmp(t, key, &e)) == 0) { 57*50989Sbostic if (h->flags & P_BLEAF) { 58*50989Sbostic *exactp = 1; 59*50989Sbostic return (&e); 60*50989Sbostic } 61*50989Sbostic goto next; 6246132Smao } 63*50989Sbostic if (cmp > 0) { 64*50989Sbostic base = index + 1; 65*50989Sbostic --lim; 6646132Smao } 6746132Smao } 6846132Smao 69*50989Sbostic /* 70*50989Sbostic * No match found. Base is the smallest index greater than 71*50989Sbostic * key but may be an illegal index. Use base if it's a leaf 72*50989Sbostic * page, decrement it by one if it's an internal page. This 73*50989Sbostic * is safe because internal pages can't be empty. 74*50989Sbostic */ 75*50989Sbostic index = h->flags & P_BLEAF ? base : base - 1; 76*50989Sbostic 77*50989Sbostic /* If it's a leaf page, we're done. */ 78*50989Sbostic if (h->flags & P_BLEAF) { 79*50989Sbostic e.index = index; 80*50989Sbostic *exactp = 0; 81*50989Sbostic return (&e); 8246132Smao } 8346132Smao 84*50989Sbostic next: if (bt_push(t, h->pgno, index) == RET_ERROR) 85*50989Sbostic return (NULL); 86*50989Sbostic pg = GETBINTERNAL(h, index)->pgno; 87*50989Sbostic mpool_put(t->bt_mp, h, 0); 8846132Smao } 8946132Smao } 90