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*56739Sbostic static char sccsid[] = "@(#)bt_search.c 5.5 (Berkeley) 11/13/92"; 1346132Smao #endif /* LIBC_SCCS and not lint */ 1446132Smao 1546132Smao #include <sys/types.h> 16*56739Sbostic 1746132Smao #include <db.h> 1850989Sbostic #include <stdio.h> 19*56739Sbostic 2046132Smao #include "btree.h" 2146132Smao 2246132Smao /* 2350989Sbostic * __BT_SEARCH -- Search a btree for a key. 2446132Smao * 2550989Sbostic * Parameters: 2650989Sbostic * t: tree to search 2750989Sbostic * key: key to find 2850989Sbostic * exactp: pointer to exact match flag 2946132Smao * 3050989Sbostic * Returns: 3150989Sbostic * EPG for matching record, if any, or the EPG for the location of the 3250989Sbostic * key, if it were inserted into the tree. 3346132Smao * 3450989Sbostic * Warnings: 3550989Sbostic * The EPG returned is in static memory, and will be overwritten by the 3650989Sbostic * next search of any kind in any tree. 3746132Smao */ 3850989Sbostic EPG * 3950989Sbostic __bt_search(t, key, exactp) 4050989Sbostic BTREE *t; 4150989Sbostic const DBT *key; 4250989Sbostic int *exactp; 4346132Smao { 4450989Sbostic register index_t index; 4550989Sbostic register int base, cmp, lim; 4650989Sbostic register PAGE *h; 4750989Sbostic pgno_t pg; 4850989Sbostic static EPG e; 4946132Smao 5050989Sbostic for (pg = P_ROOT;;) { 5150989Sbostic if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 5250989Sbostic return (NULL); 5346132Smao 5450989Sbostic /* Do a binary search on the current page. */ 5550989Sbostic e.page = h; 5650989Sbostic for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 5750989Sbostic e.index = index = base + (lim >> 1); 5850989Sbostic if ((cmp = __bt_cmp(t, key, &e)) == 0) { 5950989Sbostic if (h->flags & P_BLEAF) { 6050989Sbostic *exactp = 1; 6150989Sbostic return (&e); 6250989Sbostic } 6350989Sbostic goto next; 6446132Smao } 6550989Sbostic if (cmp > 0) { 6650989Sbostic base = index + 1; 6750989Sbostic --lim; 6846132Smao } 6946132Smao } 7046132Smao 7150989Sbostic /* 7250989Sbostic * No match found. Base is the smallest index greater than 7350989Sbostic * key but may be an illegal index. Use base if it's a leaf 7450989Sbostic * page, decrement it by one if it's an internal page. This 7550989Sbostic * is safe because internal pages can't be empty. 7650989Sbostic */ 7750989Sbostic index = h->flags & P_BLEAF ? base : base - 1; 7850989Sbostic 7950989Sbostic /* If it's a leaf page, we're done. */ 8050989Sbostic if (h->flags & P_BLEAF) { 8150989Sbostic e.index = index; 8250989Sbostic *exactp = 0; 8350989Sbostic return (&e); 8446132Smao } 8546132Smao 8651105Sbostic next: if (__bt_push(t, h->pgno, index) == RET_ERROR) 8750989Sbostic return (NULL); 8850989Sbostic pg = GETBINTERNAL(h, index)->pgno; 8950989Sbostic mpool_put(t->bt_mp, h, 0); 9046132Smao } 9146132Smao } 92