home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / db / btree / bt_put.c < prev    next >
C/C++ Source or Header  |  1996-12-11  |  9KB  |  325 lines
  1. /*    $NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 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_put.c    8.4 (Berkeley) 5/31/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/types.h>
  48.  
  49. #include <errno.h>
  50. #include <stdio.h>
  51. #include <stdlib.h>
  52. #include <string.h>
  53.  
  54. #include <db.h>
  55. #include "btree.h"
  56.  
  57. static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
  58.  
  59. /*
  60.  * __BT_PUT -- Add a btree item to the tree.
  61.  *
  62.  * Parameters:
  63.  *    dbp:    pointer to access method
  64.  *    key:    key
  65.  *    data:    data
  66.  *    flag:    R_NOOVERWRITE
  67.  *
  68.  * Returns:
  69.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
  70.  *    tree and R_NOOVERWRITE specified.
  71.  */
  72. int
  73. __bt_put(dbp, key, data, flags)
  74.     const DB *dbp;
  75.     DBT *key;
  76.     const DBT *data;
  77.     u_int flags;
  78. {
  79.     BTREE *t;
  80.     DBT tkey, tdata;
  81.     EPG *e = NULL;
  82.     PAGE *h;
  83.     indx_t index, nxtindex;
  84.     pgno_t pg;
  85.     u_int32_t nbytes;
  86.     int dflags, exact, status;
  87.     char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
  88.  
  89.     t = dbp->internal;
  90.  
  91.     /* Toss any page pinned across calls. */
  92.     if (t->bt_pinned != NULL) {
  93.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  94.         t->bt_pinned = NULL;
  95.     }
  96.  
  97.     switch (flags) {
  98.     case R_CURSOR:
  99.         if (!ISSET(t, B_SEQINIT))
  100.             goto einval;
  101.         if (ISSET(t, B_DELCRSR))
  102.             goto einval;
  103.         break;
  104.     case 0:
  105.     case R_NOOVERWRITE:
  106.         break;
  107.     default:
  108. einval:        errno = EINVAL;
  109.         return (RET_ERROR);
  110.     }
  111.  
  112.     if (ISSET(t, B_RDONLY)) {
  113.         errno = EPERM;
  114.         return (RET_ERROR);
  115.     }
  116.  
  117.     /*
  118.      * If the key/data won't fit on a page, store it on indirect pages.
  119.      * Only store the key on the overflow page if it's too big after the
  120.      * data is on an overflow page.
  121.      *
  122.      * XXX
  123.      * If the insert fails later on, these pages aren't recovered.
  124.      */
  125.     dflags = 0;
  126.     if (key->size + data->size > t->bt_ovflsize) {
  127.         if (key->size > t->bt_ovflsize) {
  128. storekey:        if (__ovfl_put(t, key, &pg) == RET_ERROR)
  129.                 return (RET_ERROR);
  130.             tkey.data = kb;
  131.             tkey.size = NOVFLSIZE;
  132.             memmove(kb, &pg, sizeof(pgno_t));
  133.             memmove(kb + sizeof(pgno_t),
  134.                 &key->size, sizeof(u_int32_t));
  135.             dflags |= P_BIGKEY;
  136.             key = &tkey;
  137.         }
  138.         if (key->size + data->size > t->bt_ovflsize) {
  139.             if (__ovfl_put(t, data, &pg) == RET_ERROR)
  140.                 return (RET_ERROR);
  141.             tdata.data = db;
  142.             tdata.size = NOVFLSIZE;
  143.             memmove(db, &pg, sizeof(pgno_t));
  144.             memmove(db + sizeof(pgno_t),
  145.                 &data->size, sizeof(u_int32_t));
  146.             dflags |= P_BIGDATA;
  147.             data = &tdata;
  148.         }
  149.         if (key->size + data->size > t->bt_ovflsize)
  150.             goto storekey;
  151.     }
  152.  
  153.     /* Replace the cursor. */
  154.     if (flags == R_CURSOR) {
  155.         if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
  156.             return (RET_ERROR);
  157.         index = t->bt_bcursor.index;
  158.         goto delete;
  159.     }
  160.  
  161.     /*
  162.      * Find the key to delete, or, the location at which to insert.  Bt_fast
  163.      * and __bt_search pin the returned page.
  164.      */
  165.     if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
  166.         if ((e = __bt_search(t, key, &exact)) == NULL)
  167.             return (RET_ERROR);
  168.     h = e->page;
  169.     index = e->index;
  170.  
  171.     /*
  172.      * Add the specified key/data pair to the tree.  If an identical key
  173.      * is already in the tree, and R_NOOVERWRITE is set, an error is
  174.      * returned.  If R_NOOVERWRITE is not set, the key is either added (if
  175.      * duplicates are permitted) or an error is returned.
  176.      *
  177.      * Pages are split as required.
  178.      */
  179.     switch (flags) {
  180.     case R_NOOVERWRITE:
  181.         if (!exact)
  182.             break;
  183.         /*
  184.          * One special case is if the cursor references the record and
  185.          * it's been flagged for deletion.  Then, we delete the record,
  186.          * leaving the cursor there -- this means that the inserted
  187.          * record will not be seen in a cursor scan.
  188.          */
  189.         if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno &&
  190.             t->bt_bcursor.index == index) {
  191.             CLR(t, B_DELCRSR);
  192.             goto delete;
  193.         }
  194.         mpool_put(t->bt_mp, h, 0);
  195.         return (RET_SPECIAL);
  196.     default:
  197.         if (!exact || !ISSET(t, B_NODUPS))
  198.             break;
  199. delete:        if (__bt_dleaf(t, h, index) == RET_ERROR) {
  200.             mpool_put(t->bt_mp, h, 0);
  201.             return (RET_ERROR);
  202.         }
  203.         break;
  204.     }
  205.  
  206.     /*
  207.      * If not enough room, or the user has put a ceiling on the number of
  208.      * keys permitted in the page, split the page.  The split code will
  209.      * insert the key and data and unpin the current page.  If inserting
  210.      * into the offset array, shift the pointers up.
  211.      */
  212.     nbytes = NBLEAFDBT(key->size, data->size);
  213.     if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
  214.         if ((status = __bt_split(t, h, key,
  215.             data, dflags, nbytes, index)) != RET_SUCCESS)
  216.             return (status);
  217.         goto success;
  218.     }
  219.  
  220.     if (index < (nxtindex = NEXTINDEX(h)))
  221.         memmove(h->linp + index + 1, h->linp + index,
  222.             (nxtindex - index) * sizeof(indx_t));
  223.     h->lower += sizeof(indx_t);
  224.  
  225.     h->linp[index] = h->upper -= nbytes;
  226.     dest = (char *)h + h->upper;
  227.     WR_BLEAF(dest, key, data, dflags);
  228.  
  229.     if (t->bt_order == NOT)
  230.         if (h->nextpg == P_INVALID) {
  231.             if (index == NEXTINDEX(h) - 1) {
  232.                 t->bt_order = FORWARD;
  233.                 t->bt_last.index = index;
  234.                 t->bt_last.pgno = h->pgno;
  235.             }
  236.         } else if (h->prevpg == P_INVALID) {
  237.             if (index == 0) {
  238.                 t->bt_order = BACK;
  239.                 t->bt_last.index = 0;
  240.                 t->bt_last.pgno = h->pgno;
  241.             }
  242.         }
  243.  
  244.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  245.  
  246. success:
  247.     if (flags == R_SETCURSOR) {
  248.         t->bt_bcursor.pgno = e->page->pgno;
  249.         t->bt_bcursor.index = e->index;
  250.     }
  251.     SET(t, B_MODIFIED);
  252.     return (RET_SUCCESS);
  253. }
  254.  
  255. #ifdef STATISTICS
  256. u_long bt_cache_hit, bt_cache_miss;
  257. #endif
  258.  
  259. /*
  260.  * BT_FAST -- Do a quick check for sorted data.
  261.  *
  262.  * Parameters:
  263.  *    t:    tree
  264.  *    key:    key to insert
  265.  *
  266.  * Returns:
  267.  *     EPG for new record or NULL if not found.
  268.  */
  269. static EPG *
  270. bt_fast(t, key, data, exactp)
  271.     BTREE *t;
  272.     const DBT *key, *data;
  273.     int *exactp;
  274. {
  275.     PAGE *h;
  276.     u_int32_t nbytes;
  277.     int cmp;
  278.  
  279.     if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
  280.         t->bt_order = NOT;
  281.         return (NULL);
  282.     }
  283.     t->bt_cur.page = h;
  284.     t->bt_cur.index = t->bt_last.index;
  285.  
  286.     /*
  287.      * If won't fit in this page or have too many keys in this page, have
  288.      * to search to get split stack.
  289.      */
  290.     nbytes = NBLEAFDBT(key->size, data->size);
  291.     if (h->upper - h->lower < nbytes + sizeof(indx_t))
  292.         goto miss;
  293.  
  294.     if (t->bt_order == FORWARD) {
  295.         if (t->bt_cur.page->nextpg != P_INVALID)
  296.             goto miss;
  297.         if (t->bt_cur.index != NEXTINDEX(h) - 1)
  298.             goto miss;
  299.         if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0)
  300.             goto miss;
  301.         t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index;
  302.     } else {
  303.         if (t->bt_cur.page->prevpg != P_INVALID)
  304.             goto miss;
  305.         if (t->bt_cur.index != 0)
  306.             goto miss;
  307.         if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0)
  308.             goto miss;
  309.         t->bt_last.index = 0;
  310.     }
  311.     *exactp = cmp == 0;
  312. #ifdef STATISTICS
  313.     ++bt_cache_hit;
  314. #endif
  315.     return (&t->bt_cur);
  316.  
  317. miss:
  318. #ifdef STATISTICS
  319.     ++bt_cache_miss;
  320. #endif
  321.     t->bt_order = NOT;
  322.     mpool_put(t->bt_mp, h, 0);
  323.     return (NULL);
  324. }
  325.