db/btree/bt_overflow.c

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