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