158f0484fSRodney W. Grimes /*-
28a16b7a1SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause
38a16b7a1SPedro F. Giffuni *
458f0484fSRodney W. Grimes * Copyright (c) 1990, 1993
558f0484fSRodney W. Grimes * The Regents of the University of California. All rights reserved.
658f0484fSRodney W. Grimes *
758f0484fSRodney W. Grimes * Redistribution and use in source and binary forms, with or without
858f0484fSRodney W. Grimes * modification, are permitted provided that the following conditions
958f0484fSRodney W. Grimes * are met:
1058f0484fSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright
1158f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer.
1258f0484fSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright
1358f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the
1458f0484fSRodney W. Grimes * documentation and/or other materials provided with the distribution.
15fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors
1658f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software
1758f0484fSRodney W. Grimes * without specific prior written permission.
1858f0484fSRodney W. Grimes *
1958f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2058f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2158f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2258f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2358f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2458f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2558f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2658f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2758f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
2858f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
2958f0484fSRodney W. Grimes * SUCH DAMAGE.
3058f0484fSRodney W. Grimes */
3158f0484fSRodney W. Grimes
3258f0484fSRodney W. Grimes #include <sys/types.h>
3358f0484fSRodney W. Grimes
3458f0484fSRodney W. Grimes #include <errno.h>
3558f0484fSRodney W. Grimes #include <stdio.h>
3658f0484fSRodney W. Grimes
3758f0484fSRodney W. Grimes #include <db.h>
3858f0484fSRodney W. Grimes #include "recno.h"
3958f0484fSRodney W. Grimes
4058f0484fSRodney W. Grimes /*
4158f0484fSRodney W. Grimes * __REC_SEARCH -- Search a btree for a key.
4258f0484fSRodney W. Grimes *
4358f0484fSRodney W. Grimes * Parameters:
4458f0484fSRodney W. Grimes * t: tree to search
4558f0484fSRodney W. Grimes * recno: key to find
4658f0484fSRodney W. Grimes * op: search operation
4758f0484fSRodney W. Grimes *
4858f0484fSRodney W. Grimes * Returns:
4958f0484fSRodney W. Grimes * EPG for matching record, if any, or the EPG for the location of the
5058f0484fSRodney W. Grimes * key, if it were inserted into the tree.
5158f0484fSRodney W. Grimes *
5258f0484fSRodney W. Grimes * Returns:
5358f0484fSRodney W. Grimes * The EPG for matching record, if any, or the EPG for the location
5458f0484fSRodney W. Grimes * of the key, if it were inserted into the tree, is entered into
5558f0484fSRodney W. Grimes * the bt_cur field of the tree. A pointer to the field is returned.
5658f0484fSRodney W. Grimes */
5758f0484fSRodney W. Grimes EPG *
__rec_search(BTREE * t,recno_t recno,enum SRCHOP op)580ac22237SXin LI __rec_search(BTREE *t, recno_t recno, enum SRCHOP op)
5958f0484fSRodney W. Grimes {
604c66e4b6SXin LI indx_t idx;
618fb3f3f6SDavid E. O'Brien PAGE *h;
6258f0484fSRodney W. Grimes EPGNO *parent;
6358f0484fSRodney W. Grimes RINTERNAL *r;
6458f0484fSRodney W. Grimes pgno_t pg;
6558f0484fSRodney W. Grimes indx_t top;
6658f0484fSRodney W. Grimes recno_t total;
6758f0484fSRodney W. Grimes int sverrno;
6858f0484fSRodney W. Grimes
6958f0484fSRodney W. Grimes BT_CLR(t);
7058f0484fSRodney W. Grimes for (pg = P_ROOT, total = 0;;) {
7158f0484fSRodney W. Grimes if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
7258f0484fSRodney W. Grimes goto err;
7358f0484fSRodney W. Grimes if (h->flags & P_RLEAF) {
7458f0484fSRodney W. Grimes t->bt_cur.page = h;
7558f0484fSRodney W. Grimes t->bt_cur.index = recno - total;
7658f0484fSRodney W. Grimes return (&t->bt_cur);
7758f0484fSRodney W. Grimes }
784c66e4b6SXin LI for (idx = 0, top = NEXTINDEX(h);;) {
794c66e4b6SXin LI r = GETRINTERNAL(h, idx);
804c66e4b6SXin LI if (++idx == top || total + r->nrecs > recno)
8158f0484fSRodney W. Grimes break;
8258f0484fSRodney W. Grimes total += r->nrecs;
8358f0484fSRodney W. Grimes }
8458f0484fSRodney W. Grimes
854c66e4b6SXin LI BT_PUSH(t, pg, idx - 1);
8658f0484fSRodney W. Grimes
8758f0484fSRodney W. Grimes pg = r->pgno;
8858f0484fSRodney W. Grimes switch (op) {
8958f0484fSRodney W. Grimes case SDELETE:
904c66e4b6SXin LI --GETRINTERNAL(h, (idx - 1))->nrecs;
9158f0484fSRodney W. Grimes mpool_put(t->bt_mp, h, MPOOL_DIRTY);
9258f0484fSRodney W. Grimes break;
9358f0484fSRodney W. Grimes case SINSERT:
944c66e4b6SXin LI ++GETRINTERNAL(h, (idx - 1))->nrecs;
9558f0484fSRodney W. Grimes mpool_put(t->bt_mp, h, MPOOL_DIRTY);
9658f0484fSRodney W. Grimes break;
9758f0484fSRodney W. Grimes case SEARCH:
9858f0484fSRodney W. Grimes mpool_put(t->bt_mp, h, 0);
9958f0484fSRodney W. Grimes break;
10058f0484fSRodney W. Grimes }
10158f0484fSRodney W. Grimes
10258f0484fSRodney W. Grimes }
10358f0484fSRodney W. Grimes /* Try and recover the tree. */
10458f0484fSRodney W. Grimes err: sverrno = errno;
10558f0484fSRodney W. Grimes if (op != SEARCH)
10658f0484fSRodney W. Grimes while ((parent = BT_POP(t)) != NULL) {
10758f0484fSRodney W. Grimes if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
10858f0484fSRodney W. Grimes break;
10958f0484fSRodney W. Grimes if (op == SINSERT)
11058f0484fSRodney W. Grimes --GETRINTERNAL(h, parent->index)->nrecs;
11158f0484fSRodney W. Grimes else
11258f0484fSRodney W. Grimes ++GETRINTERNAL(h, parent->index)->nrecs;
11358f0484fSRodney W. Grimes mpool_put(t->bt_mp, h, MPOOL_DIRTY);
11458f0484fSRodney W. Grimes }
11558f0484fSRodney W. Grimes errno = sverrno;
11658f0484fSRodney W. Grimes return (NULL);
11758f0484fSRodney W. Grimes }
118