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 * 4. Neither the name of the University nor the names of its contributors 141573Srgrimes * may be used to endorse or promote products derived from this software 151573Srgrimes * without specific prior written permission. 161573Srgrimes * 171573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271573Srgrimes * SUCH DAMAGE. 281573Srgrimes */ 291573Srgrimes 301573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3114287Spststatic char sccsid[] = "@(#)rec_search.c 8.4 (Berkeley) 7/14/94"; 321573Srgrimes#endif /* LIBC_SCCS and not lint */ 3392889Sobrien#include <sys/cdefs.h> 3492889Sobrien__FBSDID("$FreeBSD$"); 351573Srgrimes 361573Srgrimes#include <sys/types.h> 371573Srgrimes 381573Srgrimes#include <errno.h> 391573Srgrimes#include <stdio.h> 401573Srgrimes 411573Srgrimes#include <db.h> 421573Srgrimes#include "recno.h" 431573Srgrimes 441573Srgrimes/* 451573Srgrimes * __REC_SEARCH -- Search a btree for a key. 461573Srgrimes * 471573Srgrimes * Parameters: 481573Srgrimes * t: tree to search 491573Srgrimes * recno: key to find 50189327Sdelphij * op: search operation 511573Srgrimes * 521573Srgrimes * Returns: 531573Srgrimes * EPG for matching record, if any, or the EPG for the location of the 541573Srgrimes * key, if it were inserted into the tree. 551573Srgrimes * 561573Srgrimes * Returns: 571573Srgrimes * The EPG for matching record, if any, or the EPG for the location 581573Srgrimes * of the key, if it were inserted into the tree, is entered into 591573Srgrimes * the bt_cur field of the tree. A pointer to the field is returned. 601573Srgrimes */ 611573SrgrimesEPG * 62189291Sdelphij__rec_search(BTREE *t, recno_t recno, enum SRCHOP op) 631573Srgrimes{ 64189292Sdelphij indx_t idx; 6592889Sobrien PAGE *h; 661573Srgrimes EPGNO *parent; 671573Srgrimes RINTERNAL *r; 681573Srgrimes pgno_t pg; 691573Srgrimes indx_t top; 701573Srgrimes recno_t total; 711573Srgrimes int sverrno; 721573Srgrimes 731573Srgrimes BT_CLR(t); 741573Srgrimes for (pg = P_ROOT, total = 0;;) { 751573Srgrimes if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 761573Srgrimes goto err; 771573Srgrimes if (h->flags & P_RLEAF) { 781573Srgrimes t->bt_cur.page = h; 791573Srgrimes t->bt_cur.index = recno - total; 801573Srgrimes return (&t->bt_cur); 811573Srgrimes } 82189292Sdelphij for (idx = 0, top = NEXTINDEX(h);;) { 83189292Sdelphij r = GETRINTERNAL(h, idx); 84189292Sdelphij if (++idx == top || total + r->nrecs > recno) 851573Srgrimes break; 861573Srgrimes total += r->nrecs; 871573Srgrimes } 881573Srgrimes 89189292Sdelphij BT_PUSH(t, pg, idx - 1); 90189327Sdelphij 911573Srgrimes pg = r->pgno; 921573Srgrimes switch (op) { 931573Srgrimes case SDELETE: 94189292Sdelphij --GETRINTERNAL(h, (idx - 1))->nrecs; 951573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 961573Srgrimes break; 971573Srgrimes case SINSERT: 98189292Sdelphij ++GETRINTERNAL(h, (idx - 1))->nrecs; 991573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1001573Srgrimes break; 1011573Srgrimes case SEARCH: 1021573Srgrimes mpool_put(t->bt_mp, h, 0); 1031573Srgrimes break; 1041573Srgrimes } 1051573Srgrimes 1061573Srgrimes } 1071573Srgrimes /* Try and recover the tree. */ 1081573Srgrimeserr: sverrno = errno; 1091573Srgrimes if (op != SEARCH) 1101573Srgrimes while ((parent = BT_POP(t)) != NULL) { 1111573Srgrimes if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 1121573Srgrimes break; 1131573Srgrimes if (op == SINSERT) 1141573Srgrimes --GETRINTERNAL(h, parent->index)->nrecs; 1151573Srgrimes else 1161573Srgrimes ++GETRINTERNAL(h, parent->index)->nrecs; 117189327Sdelphij mpool_put(t->bt_mp, h, MPOOL_DIRTY); 118189327Sdelphij } 1191573Srgrimes errno = sverrno; 1201573Srgrimes return (NULL); 1211573Srgrimes} 122