rec_search.c revision 1573
11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * Redistribution and use in source and binary forms, with or without 61573Srgrimes * modification, are permitted provided that the following conditions 71573Srgrimes * are met: 81573Srgrimes * 1. Redistributions of source code must retain the above copyright 91573Srgrimes * notice, this list of conditions and the following disclaimer. 101573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111573Srgrimes * notice, this list of conditions and the following disclaimer in the 121573Srgrimes * documentation and/or other materials provided with the distribution. 131573Srgrimes * 3. All advertising materials mentioning features or use of this software 141573Srgrimes * must display the following acknowledgement: 151573Srgrimes * This product includes software developed by the University of 161573Srgrimes * California, Berkeley and its contributors. 171573Srgrimes * 4. Neither the name of the University nor the names of its contributors 181573Srgrimes * may be used to endorse or promote products derived from this software 191573Srgrimes * without specific prior written permission. 201573Srgrimes * 211573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311573Srgrimes * SUCH DAMAGE. 321573Srgrimes */ 331573Srgrimes 341573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 351573Srgrimesstatic char sccsid[] = "@(#)rec_search.c 8.3 (Berkeley) 2/21/94"; 361573Srgrimes#endif /* LIBC_SCCS and not lint */ 371573Srgrimes 381573Srgrimes#include <sys/types.h> 391573Srgrimes 401573Srgrimes#include <errno.h> 411573Srgrimes#include <stdio.h> 421573Srgrimes 431573Srgrimes#include <db.h> 441573Srgrimes#include "recno.h" 451573Srgrimes 461573Srgrimes/* 471573Srgrimes * __REC_SEARCH -- Search a btree for a key. 481573Srgrimes * 491573Srgrimes * Parameters: 501573Srgrimes * t: tree to search 511573Srgrimes * recno: key to find 521573Srgrimes * op: search operation 531573Srgrimes * 541573Srgrimes * Returns: 551573Srgrimes * EPG for matching record, if any, or the EPG for the location of the 561573Srgrimes * key, if it were inserted into the tree. 571573Srgrimes * 581573Srgrimes * Returns: 591573Srgrimes * The EPG for matching record, if any, or the EPG for the location 601573Srgrimes * of the key, if it were inserted into the tree, is entered into 611573Srgrimes * the bt_cur field of the tree. A pointer to the field is returned. 621573Srgrimes */ 631573SrgrimesEPG * 641573Srgrimes__rec_search(t, recno, op) 651573Srgrimes BTREE *t; 661573Srgrimes recno_t recno; 671573Srgrimes enum SRCHOP op; 681573Srgrimes{ 691573Srgrimes register indx_t index; 701573Srgrimes register PAGE *h; 711573Srgrimes EPGNO *parent; 721573Srgrimes RINTERNAL *r; 731573Srgrimes pgno_t pg; 741573Srgrimes indx_t top; 751573Srgrimes recno_t total; 761573Srgrimes int sverrno; 771573Srgrimes 781573Srgrimes BT_CLR(t); 791573Srgrimes for (pg = P_ROOT, total = 0;;) { 801573Srgrimes if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 811573Srgrimes goto err; 821573Srgrimes if (h->flags & P_RLEAF) { 831573Srgrimes t->bt_cur.page = h; 841573Srgrimes t->bt_cur.index = recno - total; 851573Srgrimes return (&t->bt_cur); 861573Srgrimes } 871573Srgrimes for (index = 0, top = NEXTINDEX(h);;) { 881573Srgrimes r = GETRINTERNAL(h, index); 891573Srgrimes if (++index == top || total + r->nrecs > recno) 901573Srgrimes break; 911573Srgrimes total += r->nrecs; 921573Srgrimes } 931573Srgrimes 941573Srgrimes if (__bt_push(t, pg, index - 1) == RET_ERROR) 951573Srgrimes return (NULL); 961573Srgrimes 971573Srgrimes pg = r->pgno; 981573Srgrimes switch (op) { 991573Srgrimes case SDELETE: 1001573Srgrimes --GETRINTERNAL(h, (index - 1))->nrecs; 1011573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1021573Srgrimes break; 1031573Srgrimes case SINSERT: 1041573Srgrimes ++GETRINTERNAL(h, (index - 1))->nrecs; 1051573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1061573Srgrimes break; 1071573Srgrimes case SEARCH: 1081573Srgrimes mpool_put(t->bt_mp, h, 0); 1091573Srgrimes break; 1101573Srgrimes } 1111573Srgrimes 1121573Srgrimes } 1131573Srgrimes /* Try and recover the tree. */ 1141573Srgrimeserr: sverrno = errno; 1151573Srgrimes if (op != SEARCH) 1161573Srgrimes while ((parent = BT_POP(t)) != NULL) { 1171573Srgrimes if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 1181573Srgrimes break; 1191573Srgrimes if (op == SINSERT) 1201573Srgrimes --GETRINTERNAL(h, parent->index)->nrecs; 1211573Srgrimes else 1221573Srgrimes ++GETRINTERNAL(h, parent->index)->nrecs; 1231573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1241573Srgrimes } 1251573Srgrimes errno = sverrno; 1261573Srgrimes return (NULL); 1271573Srgrimes} 128