lib/libc/db/btree/search.c

/*-
 * Copyright (c) 1990 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * 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[] = "@(#)search.c    5.2 (Berkeley) 4/8/91";
#endif /* LIBC_SCCS and not lint */

#include <sys/types.h>
#include <db.h>
#include "btree.h"

/*
 *  _BT_FIRST -- Find the first item in the tree that matches the supplied
 *               key.
 *
 *      This routine supports deletion.  When the user supplies a key to
 *      be deleted, we find the first one, and iteratively delete all the
 *      matching ones that follow it.
 *
 *      Parameters:
 *              t -- btree in which to find first occurrence
 *              key -- key to find
 *
 *      Returns:
 *              The BTITEM for the matching item.  If there's no match,
 *              this may point to the first item > than the supplied key,
 *              or off the end of the page.
 *
 *      Warnings:
 *              The BTITEM returned is in static space and will be overwritten
 *              by the next search of any kind in any btree.
 */

BTITEM *
_bt_first(t, key)
        BTREE_P t;
        DBT *key;
{
        BTHEADER *h;
        BTITEM *item;
        index_t next;
        int r;

        /* find any matching item */
        item = _bt_search(t, key);
        h = t->bt_curpage;
        next = NEXTINDEX(h);

        /* if we're off the end of the page, search failed and we're done */
        if (item->bti_index >= next)
                return (item);

        /* as long as we have an exact match, walk backwards */
        while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) {

                /* at start of page? */
                if (item->bti_index == 0) {

                        /* if no prev page, we're done */
                        if (h->h_prevpg == P_NONE)
                                return (item);

                        /* walk backward, skipping empty pages */
                        do {
                                if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
                                        return ((BTITEM *) NULL);
                                h = t->bt_curpage;
                        } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);

                        if (NEXTINDEX(h) != 0)
                                item->bti_index = NEXTINDEX(h) - 1;
                        else
                                item->bti_index = 0;

                        item->bti_pgno = h->h_pgno;
                } else {
                        item->bti_index--;
                }
        }

        /* if we went too far backwards, step forward one entry */
        if (r > 0) {
                if (++(item->bti_index) >= NEXTINDEX(h)
                    && h->h_nextpg != P_NONE) {

                        /* walk forward, skipping empty pages */
                        do {
                                if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
                                        return ((BTITEM *) NULL);
                                h = t->bt_curpage;
                        } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0);

                        item->bti_index = 0;
                        item->bti_pgno = h->h_pgno;
                }
        }

        /* got it */
        return (item);
}

/*
 *  _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree.
 *
 *      Parameters:
 *              t -- btree in which to search
 *              key -- key to find
 *
 *      Returns:
 *              BTITEM for matching item, if any, or the BTITEM for the
 *              location of the key, if it were in the tree.
 *
 *      Warnings:
 *              The BTITEM returned is in static memory, and will be
 *              overwritten by the next search of any kind in any tree.
 */

BTITEM *
_bt_search(t, key)
        BTREE_P t;
        DBT *key;
{
        /* we want to start all of our searches at the root */
        if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
                return ((BTITEM *) NULL);

        return (_bt_searchr(t, key));
}

BTITEM *
_bt_searchr(t, key)
        BTREE_P t;
        DBT *key;
{
        BTHEADER *h = t->bt_curpage;
        index_t index;
        IDATUM *id;
        DATUM *d;
        static BTITEM item;

        /* do a binary search on the current page */
        index = _bt_binsrch(t, key->data);

        /*
         *  At this point, the binary search terminated because the endpoints
         *  got too close together, or we have a match.  Figure out which
         *  case applies and decide what to do based on the page type.
         */
        if (h->h_flags & F_LEAF) {
                item.bti_pgno = h->h_pgno;
                item.bti_index = index;
                if (index < NEXTINDEX(h))
                        d = (DATUM *) GETDATUM(h,index);
                else
                        d = (DATUM *) NULL;

                item.bti_datum = d;
                return(&item);
        } else {
                id = (IDATUM *) GETDATUM(h, index);
                if (_bt_push(t, h->h_pgno) == RET_ERROR)
                        return ((BTITEM *) NULL);
                if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
                        return ((BTITEM *) NULL);
                return (_bt_searchr(t, key));
        }
}

/*
 *  _BT_BINSRCH -- Do a binary search for a given key on the current page.
 *
 *      Searches on internal pages are handled slightly differently from
 *      searches on leaf pages.  This is because internal page searches
 *      find the largest item <= key in the tree, and leaf searches find
 *      the smallest item >= key.  This guarantees that leaf page searches
 *      leave us pointing at the item's correct position, and internal
 *      searches descend the tree correctly.
 *
 *      Parameters:
 *              t -- tree to search
 *              key -- key we're looking for
 *
 *      Returns:
 *              Index of the line pointer array entry for the (closest)
 *              match to key on the current page, with "closest" as defined
 *              above.
 */

index_t
_bt_binsrch(t, key)
        BTREE_P t;
        char *key;
{
        index_t lbound, ubound, cur;
        BTHEADER *h = t->bt_curpage;
        int match = 0;
        int r;

        lbound = 0;
        ubound = NEXTINDEX(h);
        if (ubound > 0)
                --ubound;

        /* do a binary search on the current page */
        while ((ubound - lbound) > 1) {
                cur = lbound + ((ubound - lbound) / 2);
                r = _bt_cmp(t, key, cur);

                if (r > 0)
                        lbound = cur + 1;
                else if (r < 0)
                        ubound = cur;
                else {
                        match++;
                        break;
                }
        }

        /*
         *  At this point, the binary search terminated because the endpoints
         *  got too close together, or we have a match.  Figure out which
         *  case applies, decide what to do based on the page type (leaf or
         *  internal), and do the right thing.
         */
        if (match) {
                return (cur);
        } else if (ubound != lbound) {
                if (h->h_flags & F_LEAF) {
                        r = _bt_cmp(t, key, lbound);
                        if (r <= 0) {
                                return (lbound);
                        }
                } else {
                        r = _bt_cmp(t, key, ubound);

                        /* for internal nodes, move as far left as possible */
                        if (r < 0) {
                                r = _bt_cmp(t, key, lbound);
                                if (r < 0 && lbound > 0)
                                        --lbound;
                                return (lbound);
                        } else {
                                return (ubound);
                        }
                }
        }

        if (h->h_flags & F_LEAF) {
                if (ubound < NEXTINDEX(h)) {
                        r = _bt_cmp(t, key, ubound);
                        if (r > 0)
                                ubound++;
                }
        } else {
                /* for internal pages, move as far left as possible */
                if (ubound == NEXTINDEX(h))
                        ubound--;

                while (_bt_cmp(t, key, ubound) < 0)
                        ubound--;
        }
        return (ubound);
}