db/btree/bt_utils.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*-
  24  * Copyright (c) 1990, 1993, 1994
  25  *      The Regents of the University of California.  All rights reserved.
  26  *
  27  * This code is derived from software contributed to Berkeley by
  28  * Mike Olson.
  29  *
  30  * Redistribution and use in source and binary forms, with or without
  31  * modification, are permitted provided that the following conditions
  32  * are met:
  33  * 1. Redistributions of source code must retain the above copyright
  34  *    notice, this list of conditions and the following disclaimer.
  35  * 2. Redistributions in binary form must reproduce the above copyright
  36  *    notice, this list of conditions and the following disclaimer in the
  37  *    documentation and/or other materials provided with the distribution.
  38  * 3. All advertising materials mentioning features or use of this software
  39  *    must display the following acknowledgement:
  40  *      This product includes software developed by the University of
  41  *      California, Berkeley and its contributors.
  42  * 4. Neither the name of the University nor the names of its contributors
  43  *    may be used to endorse or promote products derived from this software
  44  *    without specific prior written permission.
  45  *
  46  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  47  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  48  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  49  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  50  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  51  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  52  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  53  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  54  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  55  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  56  * SUCH DAMAGE.
  57  */
  58
  59 #if defined(LIBC_SCCS) && !defined(lint)
  60 static char sccsid[] = "@(#)bt_utils.c  8.8 (Berkeley) 7/20/94";
  61 #endif /* LIBC_SCCS and not lint */
  62 #include <sys/cdefs.h>
  63
  64 #include <sys/param.h>
  65
  66 #include <stdio.h>
  67 #include <stdlib.h>
  68 #include <string.h>
  69
  70 #include <db.h>
  71 #include "btree.h"
  72
  73 /*
  74  * __bt_ret --
  75  *      Build return key/data pair.
  76  *
  77  * Parameters:
  78  *      t:      tree
  79  *      e:      key/data pair to be returned
  80  *      key:    user's key structure (NULL if not to be filled in)
  81  *      rkey:   memory area to hold key
  82  *      data:   user's data structure (NULL if not to be filled in)
  83  *      rdata:  memory area to hold data
  84  *       copy:  always copy the key/data item
  85  *
  86  * Returns:
  87  *      RET_SUCCESS, RET_ERROR.
  88  */
  89 int
  90 __bt_ret(t, e, key, rkey, data, rdata, copy)
  91         BTREE *t;
  92         EPG *e;
  93         DBT *key, *rkey, *data, *rdata;
  94         int copy;
  95 {
  96         BLEAF *bl;
  97         void *p;
  98
  99         bl = GETBLEAF(e->page, e->index);
 100
 101         /*
 102          * We must copy big keys/data to make them contigous.  Otherwise,
 103          * leave the page pinned and don't copy unless the user specified
 104          * concurrent access.
 105          */
 106         if (key == NULL)
 107                 goto dataonly;
 108
 109         if (bl->flags & P_BIGKEY) {
 110                 if (__ovfl_get(t, bl->bytes,
 111                     &key->size, &rkey->data, &rkey->size))
 112                         return (RET_ERROR);
 113                 key->data = rkey->data;
 114         } else if (copy || F_ISSET(t, B_DB_LOCK)) {
 115                 if (bl->ksize > rkey->size) {
 116                         p = (void *)(rkey->data == NULL ?
 117                             malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
 118                         if (p == NULL)
 119                                 return (RET_ERROR);
 120                         rkey->data = p;
 121                         rkey->size = bl->ksize;
 122                 }
 123                 memmove(rkey->data, bl->bytes, bl->ksize);
 124                 key->size = bl->ksize;
 125                 key->data = rkey->data;
 126         } else {
 127                 key->size = bl->ksize;
 128                 key->data = bl->bytes;
 129         }
 130
 131 dataonly:
 132         if (data == NULL)
 133                 return (RET_SUCCESS);
 134
 135         if (bl->flags & P_BIGDATA) {
 136                 if (__ovfl_get(t, bl->bytes + bl->ksize,
 137                     &data->size, &rdata->data, &rdata->size))
 138                         return (RET_ERROR);
 139                 data->data = rdata->data;
 140         } else if (copy || F_ISSET(t, B_DB_LOCK)) {
 141                 /* Use +1 in case the first record retrieved is 0 length. */
 142                 if (bl->dsize + 1 > rdata->size) {
 143                         p = (void *)(rdata->data == NULL ?
 144                             malloc(bl->dsize + 1) :
 145                             realloc(rdata->data, bl->dsize + 1));
 146                         if (p == NULL)
 147                                 return (RET_ERROR);
 148                         rdata->data = p;
 149                         rdata->size = bl->dsize + 1;
 150                 }
 151                 memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
 152                 data->size = bl->dsize;
 153                 data->data = rdata->data;
 154         } else {
 155                 data->size = bl->dsize;
 156                 data->data = bl->bytes + bl->ksize;
 157         }
 158
 159         return (RET_SUCCESS);
 160 }
 161
 162 /*
 163  * __BT_CMP -- Compare a key to a given record.
 164  *
 165  * Parameters:
 166  *      t:      tree
 167  *      k1:     DBT pointer of first arg to comparison
 168  *      e:      pointer to EPG for comparison
 169  *
 170  * Returns:
 171  *      < 0 if k1 is < record
 172  *      = 0 if k1 is = record
 173  *      > 0 if k1 is > record
 174  */
 175 int
 176 __bt_cmp(t, k1, e)
 177         BTREE *t;
 178         const DBT *k1;
 179         EPG *e;
 180 {
 181         BINTERNAL *bi;
 182         BLEAF *bl;
 183         DBT k2;
 184         PAGE *h;
 185         void *bigkey;
 186
 187         /*
 188          * The left-most key on internal pages, at any level of the tree, is
 189          * guaranteed by the following code to be less than any user key.
 190          * This saves us from having to update the leftmost key on an internal
 191          * page when the user inserts a new key in the tree smaller than
 192          * anything we've yet seen.
 193          */
 194         h = e->page;
 195         if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
 196                 return (1);
 197
 198         bigkey = NULL;
 199         if (h->flags & P_BLEAF) {
 200                 bl = GETBLEAF(h, e->index);
 201                 if (bl->flags & P_BIGKEY)
 202                         bigkey = bl->bytes;
 203                 else {
 204                         k2.data = bl->bytes;
 205                         k2.size = bl->ksize;
 206                 }
 207         } else {
 208                 bi = GETBINTERNAL(h, e->index);
 209                 if (bi->flags & P_BIGKEY)
 210                         bigkey = bi->bytes;
 211                 else {
 212                         k2.data = bi->bytes;
 213                         k2.size = bi->ksize;
 214                 }
 215         }
 216
 217         if (bigkey) {
 218                 if (__ovfl_get(t, bigkey,
 219                     &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
 220                         return (RET_ERROR);
 221                 k2.data = t->bt_rdata.data;
 222         }
 223         return ((*t->bt_cmp)(k1, &k2));
 224 }
 225
 226 /*
 227  * __BT_DEFCMP -- Default comparison routine.
 228  *
 229  * Parameters:
 230  *      a:      DBT #1
 231  *      b:      DBT #2
 232  *
 233  * Returns:
 234  *      < 0 if a is < b
 235  *      = 0 if a is = b
 236  *      > 0 if a is > b
 237  */
 238 int
 239 __bt_defcmp(a, b)
 240         const DBT *a, *b;
 241 {
 242         size_t len;
 243         u_char *p1, *p2;
 244
 245         /*
 246          * XXX
 247          * If a size_t doesn't fit in an int, this routine can lose.
 248          * What we need is an integral type which is guaranteed to be
 249          * larger than a size_t, and there is no such thing.
 250          */
 251         len = MIN(a->size, b->size);
 252         for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
 253                 if (*p1 != *p2)
 254                         return ((int)*p1 - (int)*p2);
 255         return ((int)a->size - (int)b->size);
 256 }
 257
 258 /*
 259  * __BT_DEFPFX -- Default prefix routine.
 260  *
 261  * Parameters:
 262  *      a:      DBT #1
 263  *      b:      DBT #2
 264  *
 265  * Returns:
 266  *      Number of bytes needed to distinguish b from a.
 267  */
 268 size_t
 269 __bt_defpfx(a, b)
 270         const DBT *a, *b;
 271 {
 272         u_char *p1, *p2;
 273         size_t cnt, len;
 274
 275         cnt = 1;
 276         len = MIN(a->size, b->size);
 277         for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
 278                 if (*p1 != *p2)
 279                         return (cnt);
 280
 281         /* a->size must be <= b->size, or they wouldn't be in this order. */
 282         return (a->size < b->size ? a->size + 1 : a->size);
 283 }