aboutsummaryrefslogtreecommitdiffstats
path: root/trunk/main/db1-ast/recno/rec_search.c
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/main/db1-ast/recno/rec_search.c')
-rw-r--r--trunk/main/db1-ast/recno/rec_search.c126
1 files changed, 126 insertions, 0 deletions
diff --git a/trunk/main/db1-ast/recno/rec_search.c b/trunk/main/db1-ast/recno/rec_search.c
new file mode 100644
index 000000000..e70fe4c13
--- /dev/null
+++ b/trunk/main/db1-ast/recno/rec_search.c
@@ -0,0 +1,126 @@
+/*-
+ * Copyright (c) 1990, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)rec_search.c 8.4 (Berkeley) 7/14/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stdio.h>
+
+#include "../include/db.h"
+#include "recno.h"
+
+/*
+ * __REC_SEARCH -- Search a btree for a key.
+ *
+ * Parameters:
+ * t: tree to search
+ * recno: key to find
+ * op: search operation
+ *
+ * Returns:
+ * EPG for matching record, if any, or the EPG for the location of the
+ * key, if it were inserted into the tree.
+ *
+ * Returns:
+ * The EPG for matching record, if any, or the EPG for the location
+ * of the key, if it were inserted into the tree, is entered into
+ * the bt_cur field of the tree. A pointer to the field is returned.
+ */
+EPG *
+__rec_search(t, recno, op)
+ BTREE *t;
+ recno_t recno;
+ enum SRCHOP op;
+{
+ register indx_t index;
+ register PAGE *h;
+ EPGNO *parent;
+ RINTERNAL *r;
+ pgno_t pg;
+ indx_t top;
+ recno_t total;
+ int sverrno;
+
+ BT_CLR(t);
+ for (pg = P_ROOT, total = 0;;) {
+ if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
+ goto err;
+ if (h->flags & P_RLEAF) {
+ t->bt_cur.page = h;
+ t->bt_cur.index = recno - total;
+ return (&t->bt_cur);
+ }
+ for (index = 0, top = NEXTINDEX(h);;) {
+ r = GETRINTERNAL(h, index);
+ if (++index == top || total + r->nrecs > recno)
+ break;
+ total += r->nrecs;
+ }
+
+ BT_PUSH(t, pg, index - 1);
+
+ pg = r->pgno;
+ switch (op) {
+ case SDELETE:
+ --GETRINTERNAL(h, (index - 1))->nrecs;
+ mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+ break;
+ case SINSERT:
+ ++GETRINTERNAL(h, (index - 1))->nrecs;
+ mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+ break;
+ case SEARCH:
+ mpool_put(t->bt_mp, h, 0);
+ break;
+ }
+
+ }
+ /* Try and recover the tree. */
+err: sverrno = errno;
+ if (op != SEARCH)
+ while ((parent = BT_POP(t)) != NULL) {
+ if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
+ break;
+ if (op == SINSERT)
+ --GETRINTERNAL(h, parent->index)->nrecs;
+ else
+ ++GETRINTERNAL(h, parent->index)->nrecs;
+ mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+ }
+ errno = sverrno;
+ return (NULL);
+}