db/btree/bt_utils.c

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