1*50995Sbostic /*- 2*50995Sbostic * Copyright (c) 1990 The Regents of the University of California. 3*50995Sbostic * All rights reserved. 4*50995Sbostic * 5*50995Sbostic * %sccs.include.redist.c% 6*50995Sbostic */ 7*50995Sbostic 8*50995Sbostic #if defined(LIBC_SCCS) && !defined(lint) 9*50995Sbostic static char sccsid[] = "@(#)rec_search.c 5.1 (Berkeley) 09/04/91"; 10*50995Sbostic #endif /* LIBC_SCCS and not lint */ 11*50995Sbostic 12*50995Sbostic #include <sys/types.h> 13*50995Sbostic #include <errno.h> 14*50995Sbostic #include <db.h> 15*50995Sbostic #include <stdio.h> 16*50995Sbostic #include "../btree/btree.h" 17*50995Sbostic 18*50995Sbostic /* 19*50995Sbostic * __REC_SEARCH -- Search a btree for a key. 20*50995Sbostic * 21*50995Sbostic * Parameters: 22*50995Sbostic * t: tree to search 23*50995Sbostic * key: key to find 24*50995Sbostic * exactp: pointer to exact match flag 25*50995Sbostic * 26*50995Sbostic * Returns: 27*50995Sbostic * EPG for matching record, if any, or the EPG for the location of the 28*50995Sbostic * key, if it were inserted into the tree. 29*50995Sbostic * 30*50995Sbostic * Warnings: 31*50995Sbostic * The EPG returned is in static memory, and will be overwritten by the 32*50995Sbostic * next search of any kind in any tree. 33*50995Sbostic */ 34*50995Sbostic EPG * 35*50995Sbostic __rec_search(t, recno, exactp) 36*50995Sbostic BTREE *t; 37*50995Sbostic recno_t recno; 38*50995Sbostic int *exactp; 39*50995Sbostic { 40*50995Sbostic static EPG e; 41*50995Sbostic register index_t index; 42*50995Sbostic register PAGE *h; 43*50995Sbostic RINTERNAL *r; 44*50995Sbostic pgno_t pg; 45*50995Sbostic index_t top; 46*50995Sbostic recno_t total; 47*50995Sbostic 48*50995Sbostic for (pg = P_ROOT, total = 0;;) { 49*50995Sbostic if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 50*50995Sbostic return (NULL); 51*50995Sbostic if (h->flags & P_RLEAF) { 52*50995Sbostic e.page = h; 53*50995Sbostic e.index = recno - total; 54*50995Sbostic top = NEXTINDEX(h); 55*50995Sbostic 56*50995Sbostic if (e.index > top) { 57*50995Sbostic mpool_put(t->bt_mp, h, 0); 58*50995Sbostic errno = EINVAL; 59*50995Sbostic return (NULL); 60*50995Sbostic } 61*50995Sbostic 62*50995Sbostic *exactp = e.index < top ? 1 : 0; 63*50995Sbostic return (&e); 64*50995Sbostic } 65*50995Sbostic 66*50995Sbostic for (index = 0, top = NEXTINDEX(h);;) { 67*50995Sbostic r = GETRINTERNAL(h, index); 68*50995Sbostic if (++index == top || total + r->nrecs >= recno) 69*50995Sbostic break; 70*50995Sbostic total += r->nrecs; 71*50995Sbostic } 72*50995Sbostic 73*50995Sbostic if (bt_push(t, h->pgno, index - 1) == RET_ERROR) 74*50995Sbostic return (NULL); 75*50995Sbostic 76*50995Sbostic pg = r->pgno; 77*50995Sbostic mpool_put(t->bt_mp, h, 0); 78*50995Sbostic } 79*50995Sbostic } 80