btree/bt_compare.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996-2009 Oracle.  All rights reserved.
   5  */
   6 /*
   7  * Copyright (c) 1990, 1993, 1994, 1995, 1996
   8  *      Keith Bostic.  All rights reserved.
   9  */
  10 /*
  11  * Copyright (c) 1990, 1993, 1994, 1995
  12  *      The Regents of the University of California.  All rights reserved.
  13  *
  14  * This code is derived from software contributed to Berkeley by
  15  * Mike Olson.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions
  19  * are met:
  20  * 1. Redistributions of source code must retain the above copyright
  21  *    notice, this list of conditions and the following disclaimer.
  22  * 2. Redistributions in binary form must reproduce the above copyright
  23  *    notice, this list of conditions and the following disclaimer in the
  24  *    documentation and/or other materials provided with the distribution.
  25  * 3. Neither the name of the University nor the names of its contributors
  26  *    may be used to endorse or promote products derived from this software
  27  *    without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  *
  41  * $Id$
  42  */
  43
  44 #include "db_config.h"
  45
  46 #include "db_int.h"
  47 #include "dbinc/db_page.h"
  48 #include "dbinc/btree.h"
  49
  50 /*
  51  * __bam_cmp --
  52  *      Compare a key to a given record.
  53  *
  54  * PUBLIC: int __bam_cmp __P((DBC *, const DBT *, PAGE *, u_int32_t,
  55  * PUBLIC:    int (*)(DB *, const DBT *, const DBT *), int *));
  56  */
  57 int
  58 __bam_cmp(dbc, dbt, h, indx, func, cmpp)
  59         DBC *dbc;
  60         const DBT *dbt;
  61         PAGE *h;
  62         u_int32_t indx;
  63         int (*func)__P((DB *, const DBT *, const DBT *));
  64         int *cmpp;
  65 {
  66         BINTERNAL *bi;
  67         BKEYDATA *bk;
  68         BOVERFLOW *bo;
  69         DB *dbp;
  70         DBT pg_dbt;
  71
  72         dbp = dbc->dbp;
  73
  74         /*
  75          * Returns:
  76          *      < 0 if dbt is < page record
  77          *      = 0 if dbt is = page record
  78          *      > 0 if dbt is > page record
  79          *
  80          * !!!
  81          * We do not clear the pg_dbt DBT even though it's likely to contain
  82          * random bits.  That should be okay, because the app's comparison
  83          * routine had better not be looking at fields other than data, size
  84          * and app_data.  We don't clear it because we go through this path a
  85          * lot and it's expensive.
  86          */
  87         switch (TYPE(h)) {
  88         case P_LBTREE:
  89         case P_LDUP:
  90         case P_LRECNO:
  91                 bk = GET_BKEYDATA(dbp, h, indx);
  92                 if (B_TYPE(bk->type) == B_OVERFLOW)
  93                         bo = (BOVERFLOW *)bk;
  94                 else {
  95                         pg_dbt.app_data = NULL;
  96                         pg_dbt.data = bk->data;
  97                         pg_dbt.size = bk->len;
  98                         *cmpp = func(dbp, dbt, &pg_dbt);
  99                         return (0);
 100                 }
 101                 break;
 102         case P_IBTREE:
 103                 /*
 104                  * The following code guarantees that the left-most key on an
 105                  * internal page at any place in the tree sorts less than any
 106                  * user-specified key.  The reason is that if we have reached
 107                  * this internal page, we know the user key must sort greater
 108                  * than the key we're storing for this page in any internal
 109                  * pages at levels above us in the tree.  It then follows that
 110                  * any user-specified key cannot sort less than the first page
 111                  * which we reference, and so there's no reason to call the
 112                  * comparison routine.  While this may save us a comparison
 113                  * routine call or two, the real reason for this is because
 114                  * we don't maintain a copy of the smallest key in the tree,
 115                  * so that we don't have to update all the levels of the tree
 116                  * should the application store a new smallest key.  And, so,
 117                  * we may not have a key to compare, which makes doing the
 118                  * comparison difficult and error prone.
 119                  */
 120                 if (indx == 0) {
 121                         *cmpp = 1;
 122                         return (0);
 123                 }
 124
 125                 bi = GET_BINTERNAL(dbp, h, indx);
 126                 if (B_TYPE(bi->type) == B_OVERFLOW)
 127                         bo = (BOVERFLOW *)(bi->data);
 128                 else {
 129                         pg_dbt.app_data = NULL;
 130                         pg_dbt.data = bi->data;
 131                         pg_dbt.size = bi->len;
 132                         *cmpp = func(dbp, dbt, &pg_dbt);
 133                         return (0);
 134                 }
 135                 break;
 136         default:
 137                 return (__db_pgfmt(dbp->env, PGNO(h)));
 138         }
 139
 140         /*
 141          * Overflow.
 142          */
 143         return (__db_moff(dbc, dbt, bo->pgno, bo->tlen,
 144             func == __bam_defcmp ? NULL : func, cmpp));
 145 }
 146
 147 /*
 148  * __bam_defcmp --
 149  *      Default comparison routine.
 150  *
 151  * PUBLIC: int __bam_defcmp __P((DB *, const DBT *, const DBT *));
 152  */
 153 int
 154 __bam_defcmp(dbp, a, b)
 155         DB *dbp;
 156         const DBT *a, *b;
 157 {
 158         size_t len;
 159         u_int8_t *p1, *p2;
 160
 161         COMPQUIET(dbp, NULL);
 162
 163         /*
 164          * Returns:
 165          *      < 0 if a is < b
 166          *      = 0 if a is = b
 167          *      > 0 if a is > b
 168          *
 169          * XXX
 170          * If a size_t doesn't fit into a long, or if the difference between
 171          * any two characters doesn't fit into an int, this routine can lose.
 172          * What we need is a signed integral type that's guaranteed to be at
 173          * least as large as a size_t, and there is no such thing.
 174          */
 175         len = a->size > b->size ? b->size : a->size;
 176         for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
 177                 if (*p1 != *p2)
 178                         return ((long)*p1 - (long)*p2);
 179         return ((long)a->size - (long)b->size);
 180 }
 181
 182 /*
 183  * __bam_defpfx --
 184  *      Default prefix routine.
 185  *
 186  * PUBLIC: size_t __bam_defpfx __P((DB *, const DBT *, const DBT *));
 187  */
 188 size_t
 189 __bam_defpfx(dbp, a, b)
 190         DB *dbp;
 191         const DBT *a, *b;
 192 {
 193         size_t cnt, len;
 194         u_int8_t *p1, *p2;
 195
 196         COMPQUIET(dbp, NULL);
 197
 198         cnt = 1;
 199         len = a->size > b->size ? b->size : a->size;
 200         for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
 201                 if (*p1 != *p2)
 202                         return (cnt);
 203
 204         /*
 205          * They match up to the smaller of the two sizes.
 206          * Collate the longer after the shorter.
 207          */
 208         if (a->size < b->size)
 209                 return (a->size + 1);
 210         if (b->size < a->size)
 211                 return (b->size + 1);
 212         return (b->size);
 213 }