1 /*- 2 * Copyright (c) 1990, 1993 3 * The Regents of the University of California. 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 8.1 (Berkeley) 06/04/93"; 10 #endif /* LIBC_SCCS and not lint */ 11 12 #include <sys/types.h> 13 14 #include <errno.h> 15 #include <stdio.h> 16 17 #include <db.h> 18 #include "recno.h" 19 20 /* 21 * __REC_SEARCH -- Search a btree for a key. 22 * 23 * Parameters: 24 * t: tree to search 25 * recno: key to find 26 * op: search operation 27 * 28 * Returns: 29 * EPG for matching record, if any, or the EPG for the location of the 30 * key, if it were inserted into the tree. 31 * 32 * Warnings: 33 * The EPG returned is in static memory, and will be overwritten by the 34 * next search of any kind in any tree. 35 */ 36 EPG * 37 __rec_search(t, recno, op) 38 BTREE *t; 39 recno_t recno; 40 enum SRCHOP op; 41 { 42 static EPG e; 43 register indx_t index; 44 register PAGE *h; 45 EPGNO *parent; 46 RINTERNAL *r; 47 pgno_t pg; 48 indx_t top; 49 recno_t total; 50 int serrno; 51 52 BT_CLR(t); 53 for (pg = P_ROOT, total = 0;;) { 54 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 55 goto err; 56 if (h->flags & P_RLEAF) { 57 e.page = h; 58 e.index = recno - total; 59 return (&e); 60 } 61 for (index = 0, top = NEXTINDEX(h);;) { 62 r = GETRINTERNAL(h, index); 63 if (++index == top || total + r->nrecs > recno) 64 break; 65 total += r->nrecs; 66 } 67 68 if (__bt_push(t, pg, index - 1) == RET_ERROR) 69 return (NULL); 70 71 pg = r->pgno; 72 switch (op) { 73 case SDELETE: 74 --GETRINTERNAL(h, (index - 1))->nrecs; 75 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 76 break; 77 case SINSERT: 78 ++GETRINTERNAL(h, (index - 1))->nrecs; 79 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 80 break; 81 case SEARCH: 82 mpool_put(t->bt_mp, h, 0); 83 break; 84 } 85 86 } 87 /* Try and recover the tree. */ 88 err: serrno = errno; 89 if (op != SEARCH) 90 while ((parent = BT_POP(t)) != NULL) { 91 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 92 break; 93 if (op == SINSERT) 94 --GETRINTERNAL(h, parent->index)->nrecs; 95 else 96 ++GETRINTERNAL(h, parent->index)->nrecs; 97 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 98 } 99 errno = serrno; 100 return (NULL); 101 } 102