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