db/btree/bt_put.c

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