| 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 | } |