37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] =
"@(#)bt_search.c 8.8 (Berkeley) 7/31/94";
41 #include <sys/types.h>
45 #include "../include/db.h"
48 static int __bt_snext __P((
BTREE *,
PAGE *,
const DBT *,
int *));
49 static int __bt_sprev __P((
BTREE *,
PAGE *,
const DBT *,
int *));
66 __bt_search(t, key, exactp)
72 indx_t base, index, lim;
78 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
83 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
84 t->bt_cur.index = index = base + (lim >> 1);
85 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
86 if (h->flags & P_BLEAF) {
106 if (h->flags & P_BLEAF) {
107 if (!F_ISSET(t, B_NODUPS)) {
109 h->prevpg != P_INVALID &&
110 __bt_sprev(t, h, key, exactp))
112 if (base == NEXTINDEX(h) &&
113 h->nextpg != P_INVALID &&
114 __bt_snext(t, h, key, exactp))
118 t->bt_cur.index = base;
129 index = base ? base - 1 : base;
131 next: BT_PUSH(t, h->pgno, index);
132 pg = GETBINTERNAL(h, index)->pgno;
133 mpool_put(t->bt_mp, h, 0);
151 __bt_snext(t, h, key, exactp)
163 if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
166 if (__bt_cmp(t, key, &e) == 0) {
167 mpool_put(t->bt_mp, h, 0);
172 mpool_put(t->bt_mp, e.page, 0);
190 __bt_sprev(t, h, key, exactp)
202 if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
204 e.index = NEXTINDEX(e.page) - 1;
205 if (__bt_cmp(t, key, &e) == 0) {
206 mpool_put(t->bt_mp, h, 0);
211 mpool_put(t->bt_mp, e.page, 0);