lib/libc/db/btree/insert.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * 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[] = "@(#)insert.c    5.3 (Berkeley) 2/22/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42 #include <db.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include "btree.h"
  46
  47 /*
  48  *  _BT_INSERT -- Insert a new user datum in the btree.
  49  *
  50  *      This routine is called by bt_put, the public interface, once the
  51  *      location for the new item is known.  We do the work here, and
  52  *      handle splits if necessary.
  53  *
  54  *      Parameters:
  55  *              t -- btree in which to do the insertion.
  56  *              item -- BTITEM describing location of new datum
  57  *              key -- key to insert
  58  *              data -- data associated with key
  59  *              flag -- magic cookie passed recursively to bt_put if we
  60  *                      have to do a split
  61  *
  62  *      Returns:
  63  *              RET_SUCCESS, RET_ERROR.
  64  */
  65
  66 int
  67 _bt_insert(t, item, key, data, flag)
  68         BTREE_P t;
  69         BTITEM *item;
  70         DBT *key;
  71         DBT *data;
  72         int flag;
  73 {
  74         index_t index;
  75         BTHEADER *h;
  76         DATUM *d;
  77         int nbytes;
  78         int status;
  79         pgno_t pgno;
  80         int keysize, datasize;
  81         int bigkey, bigdata;
  82
  83         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  84                 return (RET_ERROR);
  85         h = t->bt_curpage;
  86
  87         if (TOOBIG(t, data->size)) {
  88                 bigdata = TRUE;
  89                 datasize = sizeof(pgno_t);
  90         } else {
  91                 bigdata = FALSE;
  92                 datasize = data->size;
  93         }
  94
  95         if (TOOBIG(t, key->size)) {
  96                 bigkey = TRUE;
  97                 keysize = sizeof(pgno_t);
  98         } else {
  99                 bigkey = FALSE;
 100                 keysize = key->size;
 101         }
 102
 103         nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
 104         nbytes = LONGALIGN(nbytes) + sizeof(index_t);
 105
 106         /* if there's not enough room here, split the page */
 107         if ((h->h_upper - h->h_lower) < nbytes) {
 108                 if (_bt_split(t) == RET_ERROR)
 109                         return (RET_ERROR);
 110
 111                 /* okay, try again (empty the stack first, though) */
 112                 while (_bt_pop((BTREE) t) != P_NONE)
 113                         continue;
 114
 115                 return (bt_put((BTREE) t, key, data, flag));
 116         }
 117
 118         /* put together a leaf page datum from the key/data pair */
 119         index = item->bti_index;
 120         nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
 121
 122         if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL)
 123                 return (RET_ERROR);
 124
 125         d->d_ksize = keysize;
 126         d->d_dsize = datasize;
 127         d->d_flags = 0;
 128
 129         if (bigkey) {
 130                 if (_bt_indirect(t, key, &pgno) == RET_ERROR)
 131                         return (RET_ERROR);
 132                 (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
 133                 d->d_flags |= D_BIGKEY;
 134                 if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
 135                         return (RET_ERROR);
 136         } else {
 137                 if (d->d_ksize > 0) {
 138                         (void) bcopy((char *) key->data,
 139                                       (char *) &(d->d_bytes[0]),
 140                                       (int) d->d_ksize);
 141                 }
 142         }
 143
 144         if (bigdata) {
 145                 if (_bt_indirect(t, data, &pgno) == RET_ERROR)
 146                         return (RET_ERROR);
 147                 (void) bcopy((char *) &pgno,
 148                              &(d->d_bytes[keysize]),
 149                              sizeof(pgno));
 150                 d->d_flags |= D_BIGDATA;
 151                 if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
 152                         return (RET_ERROR);
 153         } else {
 154                 if (d->d_dsize > 0) {
 155                         (void) bcopy((char *) data->data,
 156                                       (char *) &(d->d_bytes[keysize]),
 157                                       (int) d->d_dsize);
 158                 }
 159         }
 160
 161         /* do the insertion */
 162         status = _bt_insertat(t, (char *) d, index);
 163
 164         (void) free((char *) d);
 165
 166         return (status);
 167 }
 168
 169 /*
 170  *  _BT_INSERTI -- Insert IDATUM on current page in the btree.
 171  *
 172  *      This routine handles insertions to internal pages after splits
 173  *      lower in the tree.  On entry, t->bt_curpage is the page to get
 174  *      the new IDATUM.  We are also given pgno, the page number of the
 175  *      IDATUM that is immediately left of the new IDATUM's position.
 176  *      This guarantees that the IDATUM for the right half of the page
 177  *      after a split goes next to the IDATUM for its left half.
 178  *
 179  *      Parameters:
 180  *              t -- tree in which to do insertion.
 181  *              id -- new IDATUM to insert
 182  *              pgno -- page number of IDATUM left of id's position
 183  *
 184  *      Returns:
 185  *              RET_SUCCESS, RET_ERROR.
 186  */
 187
 188 int
 189 _bt_inserti(t, id, pgno)
 190         BTREE_P t;
 191         IDATUM *id;
 192         pgno_t pgno;
 193 {
 194         BTHEADER *h = t->bt_curpage;
 195         index_t next, i;
 196         IDATUM *idx;
 197         char *key;
 198         pgno_t chain;
 199         int free_key;
 200         int ignore;
 201
 202         if (id->i_flags & D_BIGKEY) {
 203                 free_key = TRUE;
 204                 bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
 205                 if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
 206                         return (RET_ERROR);
 207         } else {
 208                 free_key = FALSE;
 209                 key = &(id->i_bytes[0]);
 210         }
 211         i = _bt_binsrch(t, key);
 212
 213         next = NEXTINDEX(h);
 214         while (i < next && _bt_cmp(t, key, i) >= 0)
 215                 i++;
 216
 217         if (free_key)
 218                 (void) free(key);
 219
 220         /* okay, now we're close; find adjacent IDATUM */
 221         for (;;) {
 222                 idx = (IDATUM *) GETDATUM(h,i);
 223                 if (idx->i_pgno == pgno) {
 224                         i++;
 225                         break;
 226                 }
 227                 --i;
 228         }
 229
 230         /* correctly positioned, do the insertion */
 231         return (_bt_insertat(t, (char *) id, i));
 232 }
 233
 234 /*
 235  *  _BT_INSERTAT -- Insert a datum at a given location on the current page.
 236  *
 237  *      This routine does insertions on both leaf and internal pages.
 238  *
 239  *      Parameters:
 240  *              t -- tree in which to do insertion.
 241  *              p -- DATUM or IDATUM to insert.
 242  *              index -- index in line pointer array to put this item.
 243  *
 244  *      Returns:
 245  *              RET_SUCCESS, RET_ERROR.
 246  *
 247  *      Side Effects:
 248  *              Will rearrange line pointers to make space for the new
 249  *              entry.  This means that any scans currently active are
 250  *              invalid after this.
 251  *
 252  *      Warnings:
 253  *              There must be sufficient room for the new item on the page.
 254  */
 255
 256 int
 257 _bt_insertat(t, p, index)
 258         BTREE_P t;
 259         char *p;
 260         index_t index;
 261 {
 262         IDATUM *id = (IDATUM *) p;
 263         DATUM *d = (DATUM *) p;
 264         BTHEADER *h;
 265         CURSOR *c;
 266         index_t nxtindex;
 267         char *src, *dest;
 268         int nbytes;
 269
 270         /* insertion may confuse an active scan.  fix it. */
 271         c = &(t->bt_cursor);
 272         if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
 273                 if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
 274                         return (RET_ERROR);
 275
 276         h = t->bt_curpage;
 277         nxtindex = (index_t) NEXTINDEX(h);
 278
 279         /*
 280          *  If we're inserting at the middle of the line pointer array,
 281          *  copy pointers that will follow the new one up on the page.
 282          */
 283
 284         if (index < nxtindex) {
 285                 src = (char *) &(h->h_linp[index]);
 286                 dest = (char *) &(h->h_linp[index + 1]);
 287                 nbytes = (h->h_lower - (src - ((char *) h)))
 288                          + sizeof(h->h_linp[0]);
 289                 (void) bcopy(src, dest, nbytes);
 290         }
 291
 292         /* compute size and copy data to page */
 293         if (h->h_flags & F_LEAF) {
 294                 nbytes = d->d_ksize + d->d_dsize
 295                          + (sizeof(DATUM) - sizeof(char));
 296         } else {
 297                 nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
 298         }
 299         dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
 300         (void) bcopy((char *) p, dest, nbytes);
 301
 302         /* update statistics */
 303         dest -= (int) h;
 304         h->h_linp[index] = (index_t) dest;
 305         h->h_upper = (index_t) dest;
 306         h->h_lower += sizeof(index_t);
 307
 308         /* we're done */
 309         h->h_flags |= F_DIRTY;
 310
 311         return (RET_SUCCESS);
 312 }