cde/programs/dtinfo/DtMmdb/btree_berkeley/bt_overflow.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these libraries and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: bt_overflow.c /main/3 1996/06/11 17:12:45 cde-hal $ */
  24 /*-
  25  * Copyright (c) 1990, 1993
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * This code is derived from software contributed to Berkeley by
  29  * Mike Olson.
  30  *
  31  * Redistribution and use in source and binary forms, with or without
  32  * modification, are permitted provided that the following conditions
  33  * are met:
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in the
  38  *    documentation and/or other materials provided with the distribution.
  39  * 3. All advertising materials mentioning features or use of this software
  40  *    must display the following acknowledgement:
  41  *      This product includes software developed by the University of
  42  *      California, Berkeley and its contributors.
  43  * 4. Neither the name of the University nor the names of its contributors
  44  *    may be used to endorse or promote products derived from this software
  45  *    without specific prior written permission.
  46  *
  47  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57  * SUCH DAMAGE.
  58  */
  59
  60 #if defined(LIBC_SCCS) && !defined(lint)
  61 static char sccsid[] = "@(#)bt_overflow.c       8.1 (Berkeley) 6/4/93";
  62 #endif /* LIBC_SCCS and not lint */
  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, size_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         char **buf;
 108         size_t *bufsz;
 109 {
 110         PAGE *h;
 111         pgno_t pg;
 112         size_t nb, plen, sz;
 113
 114         memmove(&pg, p, sizeof(pgno_t));
 115         memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t));
 116         *ssz = sz;
 117
 118 #ifdef DEBUG
 119         if (pg == P_INVALID || sz == 0)
 120                 abort();
 121 #endif
 122         /* Make the buffer bigger as necessary. */
 123         if (*bufsz < sz) {
 124                 if ((*buf = __fix_realloc(*buf, sz)) == NULL)
 125                         return (RET_ERROR);
 126                 *bufsz = sz;
 127         }
 128
 129         /*
 130          * Step through the linked list of pages, copying the data on each one
 131          * into the buffer.  Never copy more than the data's length.
 132          */
 133         plen = t->bt_psize - BTDATAOFF;
 134         for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
 135                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 136                         return (RET_ERROR);
 137
 138                 nb = MIN(sz, plen);
 139                 memmove(p, (char *)h + BTDATAOFF, nb);
 140                 mpool_put(t->bt_mp, h, 0);
 141
 142                 if ((sz -= nb) == 0)
 143                         break;
 144         }
 145         return (RET_SUCCESS);
 146 }
 147
 148 /*
 149  * __OVFL_PUT -- Store an overflow key/data item.
 150  *
 151  * Parameters:
 152  *      t:      tree
 153  *      data:   DBT to store
 154  *      pgno:   storage page number
 155  *
 156  * Returns:
 157  *      RET_ERROR, RET_SUCCESS
 158  */
 159 int
 160 __ovfl_put(t, dbt, pg)
 161         BTREE *t;
 162         const DBT *dbt;
 163         pgno_t *pg;
 164 {
 165         PAGE *h, *last;
 166         void *p;
 167         pgno_t npg;
 168         size_t nb, plen, sz;
 169
 170         /*
 171          * Allocate pages and copy the key/data record into them.  Store the
 172          * number of the first page in the chain.
 173          */
 174         plen = t->bt_psize - BTDATAOFF;
 175         for (last = NULL, p = dbt->data, sz = dbt->size;;
 176             p = (char *)p + plen, last = h) {
 177                 if ((h = __bt_new(t, &npg)) == NULL)
 178                         return (RET_ERROR);
 179
 180                 h->pgno = npg;
 181                 h->nextpg = h->prevpg = P_INVALID;
 182                 h->flags = P_OVERFLOW;
 183                 h->lower = h->upper = 0;
 184
 185                 nb = MIN(sz, plen);
 186                 memmove((char *)h + BTDATAOFF, p, nb);
 187
 188                 if (last) {
 189                         last->nextpg = h->pgno;
 190                         mpool_put(t->bt_mp, last, MPOOL_DIRTY);
 191                 } else
 192                         *pg = h->pgno;
 193
 194                 if ((sz -= nb) == 0) {
 195                         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 196                         break;
 197                 }
 198         }
 199         return (RET_SUCCESS);
 200 }
 201
 202 /*
 203  * __OVFL_DELETE -- Delete an overflow chain.
 204  *
 205  * Parameters:
 206  *      t:      tree
 207  *      p:      pointer to { pgno_t, size_t }
 208  *
 209  * Returns:
 210  *      RET_ERROR, RET_SUCCESS
 211  */
 212 int
 213 __ovfl_delete(t, p)
 214         BTREE *t;
 215         void *p;
 216 {
 217         PAGE *h;
 218         pgno_t pg;
 219         size_t plen, sz;
 220
 221         memmove(&pg, p, sizeof(pgno_t));
 222         memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t));
 223
 224 #ifdef DEBUG
 225         if (pg == P_INVALID || sz == 0)
 226                 abort();
 227 #endif
 228         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 229                 return (RET_ERROR);
 230
 231         /* Don't delete chains used by internal pages. */
 232         if (h->flags & P_PRESERVE) {
 233                 mpool_put(t->bt_mp, h, 0);
 234                 return (RET_SUCCESS);
 235         }
 236
 237         /* Step through the chain, calling the free routine for each page. */
 238         for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
 239                 pg = h->nextpg;
 240                 __bt_free(t, h);
 241                 if (sz <= plen)
 242                         break;
 243                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
 244                         return (RET_ERROR);
 245         }
 246         return (RET_SUCCESS);
 247 }