146132Smao /*- 261196Sbostic * Copyright (c) 1990, 1993 361196Sbostic * The Regents of the University of California. 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*64484Sbostic static char sccsid[] = "@(#)bt_search.c 8.2 (Berkeley) 09/14/93"; 1346132Smao #endif /* LIBC_SCCS and not lint */ 1446132Smao 1546132Smao #include <sys/types.h> 1656739Sbostic 1750989Sbostic #include <stdio.h> 1856739Sbostic 1957932Sbostic #include <db.h> 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: 31*64484Sbostic * The EPG for matching record, if any, or the EPG for the location 32*64484Sbostic * of the key, if it were inserted into the tree, is entered into 33*64484Sbostic * the bt_cur field of the tree. A pointer to the field is returned. 3446132Smao */ 3550989Sbostic EPG * 3650989Sbostic __bt_search(t, key, exactp) 3750989Sbostic BTREE *t; 3850989Sbostic const DBT *key; 3950989Sbostic int *exactp; 4046132Smao { 4157989Sbostic register indx_t index; 4250989Sbostic register int base, cmp, lim; 4350989Sbostic register PAGE *h; 4450989Sbostic pgno_t pg; 4546132Smao 4657449Sbostic BT_CLR(t); 4750989Sbostic for (pg = P_ROOT;;) { 4850989Sbostic if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 4950989Sbostic return (NULL); 5046132Smao 5150989Sbostic /* Do a binary search on the current page. */ 52*64484Sbostic t->bt_cur.page = h; 5350989Sbostic for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 54*64484Sbostic t->bt_cur.index = index = base + (lim >> 1); 55*64484Sbostic if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { 5650989Sbostic if (h->flags & P_BLEAF) { 5750989Sbostic *exactp = 1; 58*64484Sbostic return (&t->bt_cur); 5950989Sbostic } 6050989Sbostic goto next; 6146132Smao } 6250989Sbostic if (cmp > 0) { 6350989Sbostic base = index + 1; 6450989Sbostic --lim; 6546132Smao } 6646132Smao } 6746132Smao 6850989Sbostic /* If it's a leaf page, we're done. */ 6950989Sbostic if (h->flags & P_BLEAF) { 70*64484Sbostic t->bt_cur.index = base; 7150989Sbostic *exactp = 0; 72*64484Sbostic return (&t->bt_cur); 7346132Smao } 7446132Smao 7557448Sbostic /* 7657448Sbostic * No match found. Base is the smallest index greater than 7757448Sbostic * key and may be zero or a last + 1 index. If it's non-zero, 7857448Sbostic * decrement by one, and record the internal page which should 7957448Sbostic * be a parent page for the key. If a split later occurs, the 8057448Sbostic * inserted page will be to the right of the saved page. 8157448Sbostic */ 8257448Sbostic index = base ? base - 1 : base; 8357448Sbostic 8451105Sbostic next: if (__bt_push(t, h->pgno, index) == RET_ERROR) 8550989Sbostic return (NULL); 8650989Sbostic pg = GETBINTERNAL(h, index)->pgno; 8750989Sbostic mpool_put(t->bt_mp, h, 0); 8846132Smao } 8946132Smao } 90