db/btree/bt_overflow.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_overflow.c       8.5 (Berkeley) 7/16/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  * Big key/data code.
  77  *
  78  * Big key and data entries are stored on linked lists of pages.  The initial
  79  * reference is byte string stored with the key or data and is the page number
  80  * and size.  The actual record is stored in a chain of pages linked by the
  81  * nextpg field of the PAGE header.
  82  *
  83  * The first page of the chain has a special property.  If the record is used
  84  * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
  85  * in the header.
  86  *
  87  * XXX
  88  * A single DBT is written to each chain, so a lot of space on the last page
  89  * is wasted.  This is a fairly major bug for some data sets.
  90  */
  91
  92 /*
  93  * __OVFL_GET -- Get an overflow key/data item.
  94  *
  95  * Parameters:
  96  *      t:      tree
  97  *      p:      pointer to { pgno_t, u_int32_t }
  98  *      buf:    storage address
  99  *      bufsz:  storage size
 100  *
 101  * Returns:
 102  *      RET_ERROR, RET_SUCCESS
 103  */
 104 int
 105 __ovfl_get(t, p, ssz, buf, bufsz)
 106         BTREE *t;
 107         void *p;
 108         size_t *ssz;
 109         void **buf;
 110         size_t *bufsz;
 111 {
 112         PAGE *h;
 113         pgno_t pg;
 114         size_t nb, plen;
 115         u_int32_t sz;
 116
 117         memmove(&pg, p, sizeof(pgno_t));
 118         memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
 119         *ssz = sz;
 120
 121 #ifdef DEBUG
 122         if (pg == P_INVALID || sz == 0)
 123                 abort();
 124 #endif
 125         /* Make the buffer bigger as necessary. */
 126         if (*bufsz < sz) {
 127                 *buf = (char *)(*buf == NULL ? malloc(sz) : reallocf(*buf, sz));
 128                 if (*buf == NULL)
 129                         return (RET_ERROR);
 130                 *bufsz = sz;
 131         }
 132
 133         /*
 134          * Step through the linked list of pages, copying the data on each one
 135          * into the buffer.  Never copy more than the data's length.
 136          */
 137         plen = t->bt_psize - BTDATAOFF;
 138         for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
 139                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 140                         return (RET_ERROR);
 141
 142                 nb = MIN(sz, plen);
 143                 memmove(p, (char *)h + BTDATAOFF, nb);
 144                 mpool_put(t->bt_mp, h, 0);
 145
 146                 if ((sz -= nb) == 0)
 147                         break;
 148         }
 149         return (RET_SUCCESS);
 150 }
 151
 152 /*
 153  * __OVFL_PUT -- Store an overflow key/data item.
 154  *
 155  * Parameters:
 156  *      t:      tree
 157  *      data:   DBT to store
 158  *      pgno:   storage page number
 159  *
 160  * Returns:
 161  *      RET_ERROR, RET_SUCCESS
 162  */
 163 int
 164 __ovfl_put(t, dbt, pg)
 165         BTREE *t;
 166         const DBT *dbt;
 167         pgno_t *pg;
 168 {
 169         PAGE *h, *last;
 170         void *p;
 171         pgno_t npg;
 172         size_t nb, plen;
 173         u_int32_t sz;
 174
 175         /*
 176          * Allocate pages and copy the key/data record into them.  Store the
 177          * number of the first page in the chain.
 178          */
 179         plen = t->bt_psize - BTDATAOFF;
 180         for (last = NULL, p = dbt->data, sz = dbt->size;;
 181             p = (char *)p + plen, last = h) {
 182                 if ((h = __bt_new(t, &npg)) == NULL)
 183                         return (RET_ERROR);
 184
 185                 h->pgno = npg;
 186                 h->nextpg = h->prevpg = P_INVALID;
 187                 h->flags = P_OVERFLOW;
 188                 h->lower = h->upper = 0;
 189
 190                 nb = MIN(sz, plen);
 191                 memmove((char *)h + BTDATAOFF, p, nb);
 192
 193                 if (last) {
 194                         last->nextpg = h->pgno;
 195                         mpool_put(t->bt_mp, last, MPOOL_DIRTY);
 196                 } else
 197                         *pg = h->pgno;
 198
 199                 if ((sz -= nb) == 0) {
 200                         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 201                         break;
 202                 }
 203         }
 204         return (RET_SUCCESS);
 205 }
 206
 207 /*
 208  * __OVFL_DELETE -- Delete an overflow chain.
 209  *
 210  * Parameters:
 211  *      t:      tree
 212  *      p:      pointer to { pgno_t, u_int32_t }
 213  *
 214  * Returns:
 215  *      RET_ERROR, RET_SUCCESS
 216  */
 217 int
 218 __ovfl_delete(t, p)
 219         BTREE *t;
 220         void *p;
 221 {
 222         PAGE *h;
 223         pgno_t pg;
 224         size_t plen;
 225         u_int32_t sz;
 226
 227         memmove(&pg, p, sizeof(pgno_t));
 228         memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
 229
 230 #ifdef DEBUG
 231         if (pg == P_INVALID || sz == 0)
 232                 abort();
 233 #endif
 234         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 235                 return (RET_ERROR);
 236
 237         /* Don't delete chains used by internal pages. */
 238         if (h->flags & P_PRESERVE) {
 239                 mpool_put(t->bt_mp, h, 0);
 240                 return (RET_SUCCESS);
 241         }
 242
 243         /* Step through the chain, calling the free routine for each page. */
 244         for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
 245                 pg = h->nextpg;
 246                 __bt_free(t, h);
 247                 if (sz <= plen)
 248                         break;
 249                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 250                         return (RET_ERROR);
 251         }
 252         return (RET_SUCCESS);
 253 }