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.3 (Berkeley) 02/21/94"; 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 * Returns: 33 * The EPG for matching record, if any, or the EPG for the location 34 * of the key, if it were inserted into the tree, is entered into 35 * the bt_cur field of the tree. A pointer to the field is returned. 36 */ 37 EPG * 38 __rec_search(t, recno, op) 39 BTREE *t; 40 recno_t recno; 41 enum SRCHOP op; 42 { 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 sverrno; 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 t->bt_cur.page = h; 58 t->bt_cur.index = recno - total; 59 return (&t->bt_cur); 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: sverrno = 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 = sverrno; 100 return (NULL); 101 } 102