xref: /csrg-svn/lib/libc/db/recno/rec_search.c (revision 51092)
150995Sbostic /*-
250995Sbostic  * Copyright (c) 1990 The Regents of the University of California.
350995Sbostic  * All rights reserved.
450995Sbostic  *
550995Sbostic  * %sccs.include.redist.c%
650995Sbostic  */
750995Sbostic 
850995Sbostic #if defined(LIBC_SCCS) && !defined(lint)
9*51092Sbostic static char sccsid[] = "@(#)rec_search.c	5.2 (Berkeley) 09/11/91";
1050995Sbostic #endif /* LIBC_SCCS and not lint */
1150995Sbostic 
1250995Sbostic #include <sys/types.h>
1350995Sbostic #include <errno.h>
1450995Sbostic #include <db.h>
1550995Sbostic #include <stdio.h>
16*51092Sbostic #include "recno.h"
1750995Sbostic 
1850995Sbostic /*
1950995Sbostic  * __REC_SEARCH -- Search a btree for a key.
2050995Sbostic  *
2150995Sbostic  * Parameters:
2250995Sbostic  *	t:	tree to search
2350995Sbostic  *	key:	key to find
24*51092Sbostic  *	op: 	search operation
2550995Sbostic  *	exactp:	pointer to exact match flag
2650995Sbostic  *
2750995Sbostic  * Returns:
2850995Sbostic  *	EPG for matching record, if any, or the EPG for the location of the
2950995Sbostic  *	key, if it were inserted into the tree.
3050995Sbostic  *
3150995Sbostic  * Warnings:
3250995Sbostic  *	The EPG returned is in static memory, and will be overwritten by the
3350995Sbostic  *	next search of any kind in any tree.
3450995Sbostic  */
3550995Sbostic EPG *
36*51092Sbostic __rec_search(t, recno, op)
3750995Sbostic 	BTREE *t;
3850995Sbostic 	recno_t recno;
39*51092Sbostic 	enum SRCHOP op;
4050995Sbostic {
4150995Sbostic 	static EPG e;
4250995Sbostic 	register index_t index;
4350995Sbostic 	register PAGE *h;
44*51092Sbostic 	EPGNO *parent;
4550995Sbostic 	RINTERNAL *r;
4650995Sbostic 	pgno_t pg;
4750995Sbostic 	index_t top;
4850995Sbostic 	recno_t total;
49*51092Sbostic 	int serrno;
5050995Sbostic 
5150995Sbostic 	for (pg = P_ROOT, total = 0;;) {
5250995Sbostic 		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
53*51092Sbostic 			goto err;
5450995Sbostic 		if (h->flags & P_RLEAF) {
5550995Sbostic 			e.page = h;
5650995Sbostic 			e.index = recno - total;
5750995Sbostic 			return (&e);
5850995Sbostic 		}
5950995Sbostic 		for (index = 0, top = NEXTINDEX(h);;) {
6050995Sbostic 			r = GETRINTERNAL(h, index);
6150995Sbostic 			if (++index == top || total + r->nrecs >= recno)
6250995Sbostic 				break;
6350995Sbostic 			total += r->nrecs;
6450995Sbostic 		}
6550995Sbostic 
66*51092Sbostic 		if (__bt_push(t, pg, index) == RET_ERROR)
6750995Sbostic 			return (NULL);
68*51092Sbostic 
69*51092Sbostic 		pg = r->pgno;
70*51092Sbostic 		switch (op) {
71*51092Sbostic 		case SDELETE:
72*51092Sbostic 			--GETRINTERNAL(h, index)->nrecs;
73*51092Sbostic 			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
74*51092Sbostic 			break;
75*51092Sbostic 		case SINSERT:
76*51092Sbostic 			++GETRINTERNAL(h, index)->nrecs;
77*51092Sbostic 			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
78*51092Sbostic 			break;
79*51092Sbostic 		case SEARCH:
80*51092Sbostic 			mpool_put(t->bt_mp, h, 0);
81*51092Sbostic 			break;
82*51092Sbostic 		}
8350995Sbostic 
8450995Sbostic 	}
85*51092Sbostic 	/* Try and recover the tree. */
86*51092Sbostic err:	serrno = errno;
87*51092Sbostic 	if (op != SEARCH)
88*51092Sbostic 		while  ((parent = BT_POP(t)) != NULL) {
89*51092Sbostic 			if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
90*51092Sbostic 				break;
91*51092Sbostic 			if (op == SINSERT)
92*51092Sbostic 				--GETRINTERNAL(h, parent->index)->nrecs;
93*51092Sbostic 			else
94*51092Sbostic 				++GETRINTERNAL(h, parent->index)->nrecs;
95*51092Sbostic                         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
96*51092Sbostic                 }
97*51092Sbostic 	errno = serrno;
98*51092Sbostic 	return (NULL);
9950995Sbostic }
100