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 *
__rec_search(t,recno,op)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