home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Spezial / SPEZIAL2_97.zip / SPEZIAL2_97.iso / ANWEND / EDITOR / NVI179B / NVI179B.ZIP / db / btree / bt_put.c < prev    next >
C/C++ Source or Header  |  1994-07-26  |  9KB  |  321 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_put.c    8.8 (Berkeley) 7/26/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42.  
  43. #include <errno.h>
  44. #include <stdio.h>
  45. #include <stdlib.h>
  46. #include <string.h>
  47.  
  48. #include <db.h>
  49. #include "btree.h"
  50.  
  51. static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
  52.  
  53. /*
  54.  * __BT_PUT -- Add a btree item to the tree.
  55.  *
  56.  * Parameters:
  57.  *    dbp:    pointer to access method
  58.  *    key:    key
  59.  *    data:    data
  60.  *    flag:    R_NOOVERWRITE
  61.  *
  62.  * Returns:
  63.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
  64.  *    tree and R_NOOVERWRITE specified.
  65.  */
  66. int
  67. __bt_put(dbp, key, data, flags)
  68.     const DB *dbp;
  69.     DBT *key;
  70.     const DBT *data;
  71.     u_int flags;
  72. {
  73.     BTREE *t;
  74.     DBT tkey, tdata;
  75.     EPG *e;
  76.     PAGE *h;
  77.     indx_t index, nxtindex;
  78.     pgno_t pg;
  79.     u_int32_t nbytes;
  80.     int dflags, exact, status;
  81.     char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
  82.  
  83.     t = dbp->internal;
  84.  
  85.     /* Toss any page pinned across calls. */
  86.     if (t->bt_pinned != NULL) {
  87.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  88.         t->bt_pinned = NULL;
  89.     }
  90.  
  91.     /* Check for change to a read-only tree. */
  92.     if (F_ISSET(t, B_RDONLY)) {
  93.         errno = EPERM;
  94.         return (RET_ERROR);
  95.     }
  96.  
  97.     switch (flags) {
  98.     case 0:
  99.     case R_NOOVERWRITE:
  100.         break;
  101.     case R_CURSOR:
  102.         /*
  103.          * If flags is R_CURSOR, put the cursor.  Must already
  104.          * have started a scan and not have already deleted it.
  105.          */
  106.         if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
  107.             !F_ISSET(&t->bt_cursor,
  108.                 CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
  109.             break;
  110.         /* FALLTHROUGH */
  111.     default:
  112.         errno = EINVAL;
  113.         return (RET_ERROR);
  114.     }
  115.  
  116.     /*
  117.      * If the key/data pair won't fit on a page, store it on overflow
  118.      * pages.  Only put the key on the overflow page if the pair are
  119.      * still too big after moving the data to an overflow page.
  120.      *
  121.      * XXX
  122.      * If the insert fails later on, the overflow pages aren't recovered.
  123.      */
  124.     dflags = 0;
  125.     if (key->size + data->size > t->bt_ovflsize) {
  126.         if (key->size > t->bt_ovflsize) {
  127. storekey:        if (__ovfl_put(t, key, &pg) == RET_ERROR)
  128.                 return (RET_ERROR);
  129.             tkey.data = kb;
  130.             tkey.size = NOVFLSIZE;
  131.             memmove(kb, &pg, sizeof(pgno_t));
  132.             memmove(kb + sizeof(pgno_t),
  133.                 &key->size, sizeof(u_int32_t));
  134.             dflags |= P_BIGKEY;
  135.             key = &tkey;
  136.         }
  137.         if (key->size + data->size > t->bt_ovflsize) {
  138.             if (__ovfl_put(t, data, &pg) == RET_ERROR)
  139.                 return (RET_ERROR);
  140.             tdata.data = db;
  141.             tdata.size = NOVFLSIZE;
  142.             memmove(db, &pg, sizeof(pgno_t));
  143.             memmove(db + sizeof(pgno_t),
  144.                 &data->size, sizeof(u_int32_t));
  145.             dflags |= P_BIGDATA;
  146.             data = &tdata;
  147.         }
  148.         if (key->size + data->size > t->bt_ovflsize)
  149.             goto storekey;
  150.     }
  151.  
  152.     /* Replace the cursor. */
  153.     if (flags == R_CURSOR) {
  154.         if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL)
  155.             return (RET_ERROR);
  156.         index = t->bt_cursor.pg.index;
  157.         goto delete;
  158.     }
  159.  
  160.     /*
  161.      * Find the key to delete, or, the location at which to insert.
  162.      * Bt_fast and __bt_search both pin the returned page.
  163.      */
  164.     if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
  165.         if ((e = __bt_search(t, key, &exact)) == NULL)
  166.             return (RET_ERROR);
  167.     h = e->page;
  168.     index = e->index;
  169.  
  170.     /*
  171.      * Add the key/data pair to the tree.  If an identical key is already
  172.      * in the tree, and R_NOOVERWRITE is set, an error is returned.  If
  173.      * R_NOOVERWRITE is not set, the key is either added (if duplicates are
  174.      * permitted) or an error is returned.
  175.      */
  176.     switch (flags) {
  177.     case R_NOOVERWRITE:
  178.         if (!exact)
  179.             break;
  180.         mpool_put(t->bt_mp, h, 0);
  181.         return (RET_SPECIAL);
  182.     default:
  183.         if (!exact || !F_ISSET(t, B_NODUPS))
  184.             break;
  185.         /*
  186.          * !!!
  187.          * Note, the delete may empty the page, so we need to put a
  188.          * new entry into the page immediately.
  189.          */
  190. delete:        if (__bt_dleaf(t, key, h, index) == RET_ERROR) {
  191.             mpool_put(t->bt_mp, h, 0);
  192.             return (RET_ERROR);
  193.         }
  194.         break;
  195.     }
  196.  
  197.     /*
  198.      * If not enough room, or the user has put a ceiling on the number of
  199.      * keys permitted in the page, split the page.  The split code will
  200.      * insert the key and data and unpin the current page.  If inserting
  201.      * into the offset array, shift the pointers up.
  202.      */
  203.     nbytes = NBLEAFDBT(key->size, data->size);
  204.     if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
  205.         if ((status = __bt_split(t, h, key,
  206.             data, dflags, nbytes, index)) != RET_SUCCESS)
  207.             return (status);
  208.         goto success;
  209.     }
  210.  
  211.     if (index < (nxtindex = NEXTINDEX(h)))
  212.         memmove(h->linp + index + 1, h->linp + index,
  213.             (nxtindex - index) * sizeof(indx_t));
  214.     h->lower += sizeof(indx_t);
  215.  
  216.     h->linp[index] = h->upper -= nbytes;
  217.     dest = (char *)h + h->upper;
  218.     WR_BLEAF(dest, key, data, dflags);
  219.  
  220.     /* If the cursor is on this page, adjust it as necessary. */
  221.     if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
  222.         !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
  223.         t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= index)
  224.         ++t->bt_cursor.pg.index;
  225.  
  226.     if (t->bt_order == NOT)
  227.         if (h->nextpg == P_INVALID) {
  228.             if (index == NEXTINDEX(h) - 1) {
  229.                 t->bt_order = FORWARD;
  230.                 t->bt_last.index = index;
  231.                 t->bt_last.pgno = h->pgno;
  232.             }
  233.         } else if (h->prevpg == P_INVALID) {
  234.             if (index == 0) {
  235.                 t->bt_order = BACK;
  236.                 t->bt_last.index = 0;
  237.                 t->bt_last.pgno = h->pgno;
  238.             }
  239.         }
  240.  
  241.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  242.  
  243. success:
  244.     if (flags == R_SETCURSOR)
  245.         __bt_setcur(t, e->page->pgno, e->index);
  246.  
  247.     F_SET(t, B_MODIFIED);
  248.     return (RET_SUCCESS);
  249. }
  250.  
  251. #ifdef STATISTICS
  252. u_long bt_cache_hit, bt_cache_miss;
  253. #endif
  254.  
  255. /*
  256.  * BT_FAST -- Do a quick check for sorted data.
  257.  *
  258.  * Parameters:
  259.  *    t:    tree
  260.  *    key:    key to insert
  261.  *
  262.  * Returns:
  263.  *     EPG for new record or NULL if not found.
  264.  */
  265. static EPG *
  266. bt_fast(t, key, data, exactp)
  267.     BTREE *t;
  268.     const DBT *key, *data;
  269.     int *exactp;
  270. {
  271.     PAGE *h;
  272.     u_int32_t nbytes;
  273.     int cmp;
  274.  
  275.     if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
  276.         t->bt_order = NOT;
  277.         return (NULL);
  278.     }
  279.     t->bt_cur.page = h;
  280.     t->bt_cur.index = t->bt_last.index;
  281.  
  282.     /*
  283.      * If won't fit in this page or have too many keys in this page,
  284.      * have to search to get split stack.
  285.      */
  286.     nbytes = NBLEAFDBT(key->size, data->size);
  287.     if (h->upper - h->lower < nbytes + sizeof(indx_t))
  288.         goto miss;
  289.  
  290.     if (t->bt_order == FORWARD) {
  291.         if (t->bt_cur.page->nextpg != P_INVALID)
  292.             goto miss;
  293.         if (t->bt_cur.index != NEXTINDEX(h) - 1)
  294.             goto miss;
  295.         if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0)
  296.             goto miss;
  297.         t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index;
  298.     } else {
  299.         if (t->bt_cur.page->prevpg != P_INVALID)
  300.             goto miss;
  301.         if (t->bt_cur.index != 0)
  302.             goto miss;
  303.         if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0)
  304.             goto miss;
  305.         t->bt_last.index = 0;
  306.     }
  307.     *exactp = cmp == 0;
  308. #ifdef STATISTICS
  309.     ++bt_cache_hit;
  310. #endif
  311.     return (&t->bt_cur);
  312.  
  313. miss:
  314. #ifdef STATISTICS
  315.     ++bt_cache_miss;
  316. #endif
  317.     t->bt_order = NOT;
  318.     mpool_put(t->bt_mp, h, 0);
  319.     return (NULL);
  320. }
  321.