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