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.2 (Berkeley) 09/11/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 "recno.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 * op: search operation 25 * exactp: pointer to exact match flag 26 * 27 * Returns: 28 * EPG for matching record, if any, or the EPG for the location of the 29 * key, if it were inserted into the tree. 30 * 31 * Warnings: 32 * The EPG returned is in static memory, and will be overwritten by the 33 * next search of any kind in any tree. 34 */ 35 EPG * 36 __rec_search(t, recno, op) 37 BTREE *t; 38 recno_t recno; 39 enum SRCHOP op; 40 { 41 static EPG e; 42 register index_t index; 43 register PAGE *h; 44 EPGNO *parent; 45 RINTERNAL *r; 46 pgno_t pg; 47 index_t top; 48 recno_t total; 49 int serrno; 50 51 for (pg = P_ROOT, total = 0;;) { 52 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 53 goto err; 54 if (h->flags & P_RLEAF) { 55 e.page = h; 56 e.index = recno - total; 57 return (&e); 58 } 59 for (index = 0, top = NEXTINDEX(h);;) { 60 r = GETRINTERNAL(h, index); 61 if (++index == top || total + r->nrecs >= recno) 62 break; 63 total += r->nrecs; 64 } 65 66 if (__bt_push(t, pg, index) == RET_ERROR) 67 return (NULL); 68 69 pg = r->pgno; 70 switch (op) { 71 case SDELETE: 72 --GETRINTERNAL(h, index)->nrecs; 73 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 74 break; 75 case SINSERT: 76 ++GETRINTERNAL(h, index)->nrecs; 77 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 78 break; 79 case SEARCH: 80 mpool_put(t->bt_mp, h, 0); 81 break; 82 } 83 84 } 85 /* Try and recover the tree. */ 86 err: serrno = errno; 87 if (op != SEARCH) 88 while ((parent = BT_POP(t)) != NULL) { 89 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 90 break; 91 if (op == SINSERT) 92 --GETRINTERNAL(h, parent->index)->nrecs; 93 else 94 ++GETRINTERNAL(h, parent->index)->nrecs; 95 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 96 } 97 errno = serrno; 98 return (NULL); 99 } 100