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.3 (Berkeley) 06/23/92"; 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 * recno: key to find 24 * op: search operation 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, op) 36 BTREE *t; 37 recno_t recno; 38 enum SRCHOP op; 39 { 40 static EPG e; 41 register index_t index; 42 register PAGE *h; 43 EPGNO *parent; 44 RINTERNAL *r; 45 pgno_t pg; 46 index_t top; 47 recno_t total; 48 int serrno; 49 50 for (pg = P_ROOT, total = 0;;) { 51 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 52 goto err; 53 if (h->flags & P_RLEAF) { 54 e.page = h; 55 e.index = recno - total; 56 return (&e); 57 } 58 for (index = 0, top = NEXTINDEX(h);;) { 59 r = GETRINTERNAL(h, index); 60 if (++index == top || total + r->nrecs >= recno) 61 break; 62 total += r->nrecs; 63 } 64 65 if (__bt_push(t, pg, index - 1) == RET_ERROR) 66 return (NULL); 67 68 pg = r->pgno; 69 switch (op) { 70 case SDELETE: 71 --GETRINTERNAL(h, index)->nrecs; 72 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 73 break; 74 case SINSERT: 75 ++GETRINTERNAL(h, index)->nrecs; 76 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 77 break; 78 case SEARCH: 79 mpool_put(t->bt_mp, h, 0); 80 break; 81 } 82 83 } 84 /* Try and recover the tree. */ 85 err: serrno = errno; 86 if (op != SEARCH) 87 while ((parent = BT_POP(t)) != NULL) { 88 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 89 break; 90 if (op == SINSERT) 91 --GETRINTERNAL(h, parent->index)->nrecs; 92 else 93 ++GETRINTERNAL(h, parent->index)->nrecs; 94 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 95 } 96 errno = serrno; 97 return (NULL); 98 } 99