lib/libc/db/btree/search.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Mike Olson.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)search.c    5.2 (Berkeley) 4/8/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42 #include <db.h>
  43 #include "btree.h"
  44
  45 /*
  46  *  _BT_FIRST -- Find the first item in the tree that matches the supplied
  47  *               key.
  48  *
  49  *      This routine supports deletion.  When the user supplies a key to
  50  *      be deleted, we find the first one, and iteratively delete all the
  51  *      matching ones that follow it.
  52  *
  53  *      Parameters:
  54  *              t -- btree in which to find first occurrence
  55  *              key -- key to find
  56  *
  57  *      Returns:
  58  *              The BTITEM for the matching item.  If there's no match,
  59  *              this may point to the first item > than the supplied key,
  60  *              or off the end of the page.
  61  *
  62  *      Warnings:
  63  *              The BTITEM returned is in static space and will be overwritten
  64  *              by the next search of any kind in any btree.
  65  */
  66
  67 BTITEM *
  68 _bt_first(t, key)
  69         BTREE_P t;
  70         DBT *key;
  71 {
  72         BTHEADER *h;
  73         BTITEM *item;
  74         index_t next;
  75         int r;
  76
  77         /* find any matching item */
  78         item = _bt_search(t, key);
  79         h = t->bt_curpage;
  80         next = NEXTINDEX(h);
  81
  82         /* if we're off the end of the page, search failed and we're done */
  83         if (item->bti_index >= next)
  84                 return (item);
  85
  86         /* as long as we have an exact match, walk backwards */
  87         while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) {
  88
  89                 /* at start of page? */
  90                 if (item->bti_index == 0) {
  91
  92                         /* if no prev page, we're done */
  93                         if (h->h_prevpg == P_NONE)
  94                                 return (item);
  95
  96                         /* walk backward, skipping empty pages */
  97                         do {
  98                                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  99                                         return ((BTITEM *) NULL);
 100                                 h = t->bt_curpage;
 101                         } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
 102
 103                         if (NEXTINDEX(h) != 0)
 104                                 item->bti_index = NEXTINDEX(h) - 1;
 105                         else
 106                                 item->bti_index = 0;
 107
 108                         item->bti_pgno = h->h_pgno;
 109                 } else {
 110                         item->bti_index--;
 111                 }
 112         }
 113
 114         /* if we went too far backwards, step forward one entry */
 115         if (r > 0) {
 116                 if (++(item->bti_index) >= NEXTINDEX(h)
 117                     && h->h_nextpg != P_NONE) {
 118
 119                         /* walk forward, skipping empty pages */
 120                         do {
 121                                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
 122                                         return ((BTITEM *) NULL);
 123                                 h = t->bt_curpage;
 124                         } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0);
 125
 126                         item->bti_index = 0;
 127                         item->bti_pgno = h->h_pgno;
 128                 }
 129         }
 130
 131         /* got it */
 132         return (item);
 133 }
 134
 135 /*
 136  *  _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree.
 137  *
 138  *      Parameters:
 139  *              t -- btree in which to search
 140  *              key -- key to find
 141  *
 142  *      Returns:
 143  *              BTITEM for matching item, if any, or the BTITEM for the
 144  *              location of the key, if it were in the tree.
 145  *
 146  *      Warnings:
 147  *              The BTITEM returned is in static memory, and will be
 148  *              overwritten by the next search of any kind in any tree.
 149  */
 150
 151 BTITEM *
 152 _bt_search(t, key)
 153         BTREE_P t;
 154         DBT *key;
 155 {
 156         /* we want to start all of our searches at the root */
 157         if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
 158                 return ((BTITEM *) NULL);
 159
 160         return (_bt_searchr(t, key));
 161 }
 162
 163 BTITEM *
 164 _bt_searchr(t, key)
 165         BTREE_P t;
 166         DBT *key;
 167 {
 168         BTHEADER *h = t->bt_curpage;
 169         index_t index;
 170         IDATUM *id;
 171         DATUM *d;
 172         static BTITEM item;
 173
 174         /* do a binary search on the current page */
 175         index = _bt_binsrch(t, key->data);
 176
 177         /*
 178          *  At this point, the binary search terminated because the endpoints
 179          *  got too close together, or we have a match.  Figure out which
 180          *  case applies and decide what to do based on the page type.
 181          */
 182         if (h->h_flags & F_LEAF) {
 183                 item.bti_pgno = h->h_pgno;
 184                 item.bti_index = index;
 185                 if (index < NEXTINDEX(h))
 186                         d = (DATUM *) GETDATUM(h,index);
 187                 else
 188                         d = (DATUM *) NULL;
 189
 190                 item.bti_datum = d;
 191                 return(&item);
 192         } else {
 193                 id = (IDATUM *) GETDATUM(h, index);
 194                 if (_bt_push(t, h->h_pgno) == RET_ERROR)
 195                         return ((BTITEM *) NULL);
 196                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
 197                         return ((BTITEM *) NULL);
 198                 return (_bt_searchr(t, key));
 199         }
 200 }
 201
 202 /*
 203  *  _BT_BINSRCH -- Do a binary search for a given key on the current page.
 204  *
 205  *      Searches on internal pages are handled slightly differently from
 206  *      searches on leaf pages.  This is because internal page searches
 207  *      find the largest item <= key in the tree, and leaf searches find
 208  *      the smallest item >= key.  This guarantees that leaf page searches
 209  *      leave us pointing at the item's correct position, and internal
 210  *      searches descend the tree correctly.
 211  *
 212  *      Parameters:
 213  *              t -- tree to search
 214  *              key -- key we're looking for
 215  *
 216  *      Returns:
 217  *              Index of the line pointer array entry for the (closest)
 218  *              match to key on the current page, with "closest" as defined
 219  *              above.
 220  */
 221
 222 index_t
 223 _bt_binsrch(t, key)
 224         BTREE_P t;
 225         char *key;
 226 {
 227         index_t lbound, ubound, cur;
 228         BTHEADER *h = t->bt_curpage;
 229         int match = 0;
 230         int r;
 231
 232         lbound = 0;
 233         ubound = NEXTINDEX(h);
 234         if (ubound > 0)
 235                 --ubound;
 236
 237         /* do a binary search on the current page */
 238         while ((ubound - lbound) > 1) {
 239                 cur = lbound + ((ubound - lbound) / 2);
 240                 r = _bt_cmp(t, key, cur);
 241
 242                 if (r > 0)
 243                         lbound = cur + 1;
 244                 else if (r < 0)
 245                         ubound = cur;
 246                 else {
 247                         match++;
 248                         break;
 249                 }
 250         }
 251
 252         /*
 253          *  At this point, the binary search terminated because the endpoints
 254          *  got too close together, or we have a match.  Figure out which
 255          *  case applies, decide what to do based on the page type (leaf or
 256          *  internal), and do the right thing.
 257          */
 258         if (match) {
 259                 return (cur);
 260         } else if (ubound != lbound) {
 261                 if (h->h_flags & F_LEAF) {
 262                         r = _bt_cmp(t, key, lbound);
 263                         if (r <= 0) {
 264                                 return (lbound);
 265                         }
 266                 } else {
 267                         r = _bt_cmp(t, key, ubound);
 268
 269                         /* for internal nodes, move as far left as possible */
 270                         if (r < 0) {
 271                                 r = _bt_cmp(t, key, lbound);
 272                                 if (r < 0 && lbound > 0)
 273                                         --lbound;
 274                                 return (lbound);
 275                         } else {
 276                                 return (ubound);
 277                         }
 278                 }
 279         }
 280
 281         if (h->h_flags & F_LEAF) {
 282                 if (ubound < NEXTINDEX(h)) {
 283                         r = _bt_cmp(t, key, ubound);
 284                         if (r > 0)
 285                                 ubound++;
 286                 }
 287         } else {
 288                 /* for internal pages, move as far left as possible */
 289                 if (ubound == NEXTINDEX(h))
 290                         ubound--;
 291
 292                 while (_bt_cmp(t, key, ubound) < 0)
 293                         ubound--;
 294         }
 295         return (ubound);
 296 }