home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / db / btree / bt_overflow.c < prev    next >
C/C++ Source or Header  |  1996-12-11  |  6KB  |  235 lines
  1. /*    $NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993, 1994
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Mike Olson.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)bt_overflow.c    8.4 (Berkeley) 6/20/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/param.h>
  48.  
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51. #include <string.h>
  52.  
  53. #include <db.h>
  54. #include "btree.h"
  55.  
  56. /*
  57.  * Big key/data code.
  58.  *
  59.  * Big key and data entries are stored on linked lists of pages.  The initial
  60.  * reference is byte string stored with the key or data and is the page number
  61.  * and size.  The actual record is stored in a chain of pages linked by the
  62.  * nextpg field of the PAGE header.
  63.  *
  64.  * The first page of the chain has a special property.  If the record is used
  65.  * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
  66.  * in the header.
  67.  *
  68.  * XXX
  69.  * A single DBT is written to each chain, so a lot of space on the last page
  70.  * is wasted.  This is a fairly major bug for some data sets.
  71.  */
  72.  
  73. /*
  74.  * __OVFL_GET -- Get an overflow key/data item.
  75.  *
  76.  * Parameters:
  77.  *    t:    tree
  78.  *    p:    pointer to { pgno_t, u_int32_t }
  79.  *    buf:    storage address
  80.  *    bufsz:    storage size
  81.  *
  82.  * Returns:
  83.  *    RET_ERROR, RET_SUCCESS
  84.  */
  85. int
  86. __ovfl_get(t, p, ssz, buf, bufsz)
  87.     BTREE *t;
  88.     void *p;
  89.     size_t *ssz;
  90.     char **buf;
  91.     size_t *bufsz;
  92. {
  93.     PAGE *h;
  94.     pgno_t pg;
  95.     size_t nb, plen;
  96.     u_int32_t sz;
  97.  
  98.     memmove(&pg, p, sizeof(pgno_t));
  99.     memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
  100.     *ssz = sz;
  101.  
  102. #ifdef DEBUG
  103.     if (pg == P_INVALID || sz == 0)
  104.         abort();
  105. #endif
  106.     /* Make the buffer bigger as necessary. */
  107.     if (*bufsz < sz) {
  108.         *buf = (char *)(*buf == NULL ? malloc(sz) : realloc(*buf, sz));
  109.         if (*buf == NULL)
  110.             return (RET_ERROR);
  111.         *bufsz = sz;
  112.     }
  113.  
  114.     /*
  115.      * Step through the linked list of pages, copying the data on each one
  116.      * into the buffer.  Never copy more than the data's length.
  117.      */
  118.     plen = t->bt_psize - BTDATAOFF;
  119.     for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
  120.         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  121.             return (RET_ERROR);
  122.  
  123.         nb = MIN(sz, plen);
  124.         memmove(p, (char *)h + BTDATAOFF, nb);
  125.         mpool_put(t->bt_mp, h, 0);
  126.  
  127.         if ((sz -= nb) == 0)
  128.             break;
  129.     }
  130.     return (RET_SUCCESS);
  131. }
  132.  
  133. /*
  134.  * __OVFL_PUT -- Store an overflow key/data item.
  135.  *
  136.  * Parameters:
  137.  *    t:    tree
  138.  *    data:    DBT to store
  139.  *    pgno:    storage page number
  140.  *
  141.  * Returns:
  142.  *    RET_ERROR, RET_SUCCESS
  143.  */
  144. int
  145. __ovfl_put(t, dbt, pg)
  146.     BTREE *t;
  147.     const DBT *dbt;
  148.     pgno_t *pg;
  149. {
  150.     PAGE *h, *last;
  151.     void *p;
  152.     pgno_t npg;
  153.     size_t nb, plen;
  154.     u_int32_t sz;
  155.  
  156.     /*
  157.      * Allocate pages and copy the key/data record into them.  Store the
  158.      * number of the first page in the chain.
  159.      */
  160.     plen = t->bt_psize - BTDATAOFF;
  161.     for (last = NULL, p = dbt->data, sz = dbt->size;;
  162.         p = (char *)p + plen, last = h) {
  163.         if ((h = __bt_new(t, &npg)) == NULL)
  164.             return (RET_ERROR);
  165.  
  166.         h->pgno = npg;
  167.         h->nextpg = h->prevpg = P_INVALID;
  168.         h->flags = P_OVERFLOW;
  169.         h->lower = h->upper = 0;
  170.  
  171.         nb = MIN(sz, plen);
  172.         memmove((char *)h + BTDATAOFF, p, nb);
  173.  
  174.         if (last) {
  175.             last->nextpg = h->pgno;
  176.             mpool_put(t->bt_mp, last, MPOOL_DIRTY);
  177.         } else
  178.             *pg = h->pgno;
  179.  
  180.         if ((sz -= nb) == 0) {
  181.             mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  182.             break;
  183.         }
  184.     }
  185.     return (RET_SUCCESS);
  186. }
  187.  
  188. /*
  189.  * __OVFL_DELETE -- Delete an overflow chain.
  190.  *
  191.  * Parameters:
  192.  *    t:    tree
  193.  *    p:    pointer to { pgno_t, u_int32_t }
  194.  *
  195.  * Returns:
  196.  *    RET_ERROR, RET_SUCCESS
  197.  */
  198. int
  199. __ovfl_delete(t, p)
  200.     BTREE *t;
  201.     void *p;
  202. {
  203.     PAGE *h;
  204.     pgno_t pg;
  205.     size_t plen;
  206.     u_int32_t sz;
  207.  
  208.     memmove(&pg, p, sizeof(pgno_t));
  209.     memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
  210.  
  211. #ifdef DEBUG
  212.     if (pg == P_INVALID || sz == 0)
  213.         abort();
  214. #endif
  215.     if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  216.         return (RET_ERROR);
  217.  
  218.     /* Don't delete chains used by internal pages. */
  219.     if (h->flags & P_PRESERVE) {
  220.         mpool_put(t->bt_mp, h, 0);
  221.         return (RET_SUCCESS);
  222.     }
  223.  
  224.     /* Step through the chain, calling the free routine for each page. */
  225.     for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
  226.         pg = h->nextpg;
  227.         __bt_free(t, h);
  228.         if (sz <= plen)
  229.             break;
  230.         if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  231.             return (RET_ERROR);
  232.     }
  233.     return (RET_SUCCESS);
  234. }
  235.