db/btree/bt_utils.c

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