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