1/*-
2 * Copyright (c) 1990, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 *    may be used to endorse or promote products derived from this software
15 *    without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30#if defined(LIBC_SCCS) && !defined(lint)
31static char sccsid[] = "@(#)rec_search.c	8.4 (Berkeley) 7/14/94";
32#endif /* LIBC_SCCS and not lint */
33#include <sys/cdefs.h>
34__FBSDID("$FreeBSD$");
35
36#include <sys/types.h>
37
38#include <errno.h>
39#include <stdio.h>
40
41#include <db.h>
42#include "recno.h"
43
44/*
45 * __REC_SEARCH -- Search a btree for a key.
46 *
47 * Parameters:
48 *	t:	tree to search
49 *	recno:	key to find
50 *	op:	search operation
51 *
52 * Returns:
53 *	EPG for matching record, if any, or the EPG for the location of the
54 *	key, if it were inserted into the tree.
55 *
56 * Returns:
57 *	The EPG for matching record, if any, or the EPG for the location
58 *	of the key, if it were inserted into the tree, is entered into
59 *	the bt_cur field of the tree.  A pointer to the field is returned.
60 */
61EPG *
62__rec_search(BTREE *t, recno_t recno, enum SRCHOP op)
63{
64	indx_t idx;
65	PAGE *h;
66	EPGNO *parent;
67	RINTERNAL *r;
68	pgno_t pg;
69	indx_t top;
70	recno_t total;
71	int sverrno;
72
73	BT_CLR(t);
74	for (pg = P_ROOT, total = 0;;) {
75		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
76			goto err;
77		if (h->flags & P_RLEAF) {
78			t->bt_cur.page = h;
79			t->bt_cur.index = recno - total;
80			return (&t->bt_cur);
81		}
82		for (idx = 0, top = NEXTINDEX(h);;) {
83			r = GETRINTERNAL(h, idx);
84			if (++idx == top || total + r->nrecs > recno)
85				break;
86			total += r->nrecs;
87		}
88
89		BT_PUSH(t, pg, idx - 1);
90
91		pg = r->pgno;
92		switch (op) {
93		case SDELETE:
94			--GETRINTERNAL(h, (idx - 1))->nrecs;
95			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
96			break;
97		case SINSERT:
98			++GETRINTERNAL(h, (idx - 1))->nrecs;
99			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
100			break;
101		case SEARCH:
102			mpool_put(t->bt_mp, h, 0);
103			break;
104		}
105
106	}
107	/* Try and recover the tree. */
108err:	sverrno = errno;
109	if (op != SEARCH)
110		while  ((parent = BT_POP(t)) != NULL) {
111			if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
112				break;
113			if (op == SINSERT)
114				--GETRINTERNAL(h, parent->index)->nrecs;
115			else
116				++GETRINTERNAL(h, parent->index)->nrecs;
117			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
118		}
119	errno = sverrno;
120	return (NULL);
121}
122