11573Srgrimes/*- 214272Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Mike Olson. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414272Spststatic char sccsid[] = "@(#)bt_put.c 8.8 (Berkeley) 7/26/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692905Sobrien#include <sys/cdefs.h> 3792905Sobrien__FBSDID("$FreeBSD$"); 381573Srgrimes 391573Srgrimes#include <sys/types.h> 401573Srgrimes 411573Srgrimes#include <errno.h> 421573Srgrimes#include <stdio.h> 431573Srgrimes#include <stdlib.h> 441573Srgrimes#include <string.h> 451573Srgrimes 461573Srgrimes#include <db.h> 471573Srgrimes#include "btree.h" 481573Srgrimes 4992905Sobrienstatic EPG *bt_fast(BTREE *, const DBT *, const DBT *, int *); 501573Srgrimes 511573Srgrimes/* 521573Srgrimes * __BT_PUT -- Add a btree item to the tree. 531573Srgrimes * 541573Srgrimes * Parameters: 551573Srgrimes * dbp: pointer to access method 561573Srgrimes * key: key 571573Srgrimes * data: data 58262826Sjlh * flag: R_NOOVERWRITE, R_SETCURSOR, R_CURSOR 591573Srgrimes * 601573Srgrimes * Returns: 611573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the 621573Srgrimes * tree and R_NOOVERWRITE specified. 631573Srgrimes */ 641573Srgrimesint 65189291Sdelphij__bt_put(const DB *dbp, DBT *key, const DBT *data, u_int flags) 661573Srgrimes{ 671573Srgrimes BTREE *t; 681573Srgrimes DBT tkey, tdata; 691573Srgrimes EPG *e; 701573Srgrimes PAGE *h; 71189292Sdelphij indx_t idx, nxtindex; 721573Srgrimes pgno_t pg; 73115411Stmm u_int32_t nbytes, tmp; 741573Srgrimes int dflags, exact, status; 751573Srgrimes char *dest, db[NOVFLSIZE], kb[NOVFLSIZE]; 761573Srgrimes 771573Srgrimes t = dbp->internal; 781573Srgrimes 791573Srgrimes /* Toss any page pinned across calls. */ 801573Srgrimes if (t->bt_pinned != NULL) { 811573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 821573Srgrimes t->bt_pinned = NULL; 831573Srgrimes } 841573Srgrimes 8514272Spst /* Check for change to a read-only tree. */ 8614272Spst if (F_ISSET(t, B_RDONLY)) { 8714272Spst errno = EPERM; 8814272Spst return (RET_ERROR); 8914272Spst } 9014272Spst 911573Srgrimes switch (flags) { 921573Srgrimes case 0: 931573Srgrimes case R_NOOVERWRITE: 94262826Sjlh case R_SETCURSOR: 951573Srgrimes break; 9614272Spst case R_CURSOR: 9714272Spst /* 9814272Spst * If flags is R_CURSOR, put the cursor. Must already 9914272Spst * have started a scan and not have already deleted it. 10014272Spst */ 10114272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 10214272Spst !F_ISSET(&t->bt_cursor, 103189327Sdelphij CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) 10414272Spst break; 10514272Spst /* FALLTHROUGH */ 1061573Srgrimes default: 10714272Spst errno = EINVAL; 1081573Srgrimes return (RET_ERROR); 1091573Srgrimes } 1101573Srgrimes 1111573Srgrimes /* 11214272Spst * If the key/data pair won't fit on a page, store it on overflow 11314272Spst * pages. Only put the key on the overflow page if the pair are 11414272Spst * still too big after moving the data to an overflow page. 1151573Srgrimes * 1161573Srgrimes * XXX 11714272Spst * If the insert fails later on, the overflow pages aren't recovered. 1181573Srgrimes */ 1191573Srgrimes dflags = 0; 1201573Srgrimes if (key->size + data->size > t->bt_ovflsize) { 1211573Srgrimes if (key->size > t->bt_ovflsize) { 1221573Srgrimesstorekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) 1231573Srgrimes return (RET_ERROR); 1241573Srgrimes tkey.data = kb; 1251573Srgrimes tkey.size = NOVFLSIZE; 1261573Srgrimes memmove(kb, &pg, sizeof(pgno_t)); 127115411Stmm tmp = key->size; 1281573Srgrimes memmove(kb + sizeof(pgno_t), 129115411Stmm &tmp, sizeof(u_int32_t)); 1301573Srgrimes dflags |= P_BIGKEY; 1311573Srgrimes key = &tkey; 1321573Srgrimes } 1331573Srgrimes if (key->size + data->size > t->bt_ovflsize) { 1341573Srgrimes if (__ovfl_put(t, data, &pg) == RET_ERROR) 1351573Srgrimes return (RET_ERROR); 1361573Srgrimes tdata.data = db; 1371573Srgrimes tdata.size = NOVFLSIZE; 1381573Srgrimes memmove(db, &pg, sizeof(pgno_t)); 139115411Stmm tmp = data->size; 1401573Srgrimes memmove(db + sizeof(pgno_t), 141115411Stmm &tmp, sizeof(u_int32_t)); 1421573Srgrimes dflags |= P_BIGDATA; 1431573Srgrimes data = &tdata; 1441573Srgrimes } 1451573Srgrimes if (key->size + data->size > t->bt_ovflsize) 1461573Srgrimes goto storekey; 1471573Srgrimes } 1481573Srgrimes 1491573Srgrimes /* Replace the cursor. */ 1501573Srgrimes if (flags == R_CURSOR) { 15114272Spst if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL) 1521573Srgrimes return (RET_ERROR); 153189292Sdelphij idx = t->bt_cursor.pg.index; 1541573Srgrimes goto delete; 1551573Srgrimes } 1561573Srgrimes 1571573Srgrimes /* 15814272Spst * Find the key to delete, or, the location at which to insert. 15914272Spst * Bt_fast and __bt_search both pin the returned page. 1601573Srgrimes */ 1611573Srgrimes if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) 1621573Srgrimes if ((e = __bt_search(t, key, &exact)) == NULL) 1631573Srgrimes return (RET_ERROR); 1641573Srgrimes h = e->page; 165189292Sdelphij idx = e->index; 1661573Srgrimes 1671573Srgrimes /* 16814272Spst * Add the key/data pair to the tree. If an identical key is already 16914272Spst * in the tree, and R_NOOVERWRITE is set, an error is returned. If 17014272Spst * R_NOOVERWRITE is not set, the key is either added (if duplicates are 17114272Spst * permitted) or an error is returned. 1721573Srgrimes */ 1731573Srgrimes switch (flags) { 1741573Srgrimes case R_NOOVERWRITE: 1751573Srgrimes if (!exact) 1761573Srgrimes break; 1771573Srgrimes mpool_put(t->bt_mp, h, 0); 1781573Srgrimes return (RET_SPECIAL); 1791573Srgrimes default: 18014272Spst if (!exact || !F_ISSET(t, B_NODUPS)) 1811573Srgrimes break; 18214272Spst /* 18314272Spst * !!! 18414272Spst * Note, the delete may empty the page, so we need to put a 18514272Spst * new entry into the page immediately. 18614272Spst */ 187189292Sdelphijdelete: if (__bt_dleaf(t, key, h, idx) == RET_ERROR) { 1881573Srgrimes mpool_put(t->bt_mp, h, 0); 1891573Srgrimes return (RET_ERROR); 1901573Srgrimes } 1911573Srgrimes break; 1921573Srgrimes } 1931573Srgrimes 1941573Srgrimes /* 1951573Srgrimes * If not enough room, or the user has put a ceiling on the number of 1961573Srgrimes * keys permitted in the page, split the page. The split code will 1971573Srgrimes * insert the key and data and unpin the current page. If inserting 1981573Srgrimes * into the offset array, shift the pointers up. 1991573Srgrimes */ 2001573Srgrimes nbytes = NBLEAFDBT(key->size, data->size); 201190484Sdelphij if ((u_int32_t)(h->upper - h->lower) < nbytes + sizeof(indx_t)) { 2021573Srgrimes if ((status = __bt_split(t, h, key, 203189292Sdelphij data, dflags, nbytes, idx)) != RET_SUCCESS) 2041573Srgrimes return (status); 2051573Srgrimes goto success; 2061573Srgrimes } 2071573Srgrimes 208189292Sdelphij if (idx < (nxtindex = NEXTINDEX(h))) 209189292Sdelphij memmove(h->linp + idx + 1, h->linp + idx, 210189292Sdelphij (nxtindex - idx) * sizeof(indx_t)); 2111573Srgrimes h->lower += sizeof(indx_t); 2121573Srgrimes 213189292Sdelphij h->linp[idx] = h->upper -= nbytes; 2141573Srgrimes dest = (char *)h + h->upper; 2151573Srgrimes WR_BLEAF(dest, key, data, dflags); 2161573Srgrimes 21714272Spst /* If the cursor is on this page, adjust it as necessary. */ 21814272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 21914272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 220189292Sdelphij t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= idx) 22114272Spst ++t->bt_cursor.pg.index; 22214272Spst 223111010Snectar if (t->bt_order == NOT) { 2241573Srgrimes if (h->nextpg == P_INVALID) { 225189292Sdelphij if (idx == NEXTINDEX(h) - 1) { 2261573Srgrimes t->bt_order = FORWARD; 227189292Sdelphij t->bt_last.index = idx; 2281573Srgrimes t->bt_last.pgno = h->pgno; 2291573Srgrimes } 2301573Srgrimes } else if (h->prevpg == P_INVALID) { 231189292Sdelphij if (idx == 0) { 2321573Srgrimes t->bt_order = BACK; 2331573Srgrimes t->bt_last.index = 0; 2341573Srgrimes t->bt_last.pgno = h->pgno; 2351573Srgrimes } 2361573Srgrimes } 237111010Snectar } 2381573Srgrimes 2391573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 2401573Srgrimes 2411573Srgrimessuccess: 24214272Spst if (flags == R_SETCURSOR) 24314272Spst __bt_setcur(t, e->page->pgno, e->index); 24414272Spst 24514272Spst F_SET(t, B_MODIFIED); 2461573Srgrimes return (RET_SUCCESS); 2471573Srgrimes} 2481573Srgrimes 2491573Srgrimes#ifdef STATISTICS 2501573Srgrimesu_long bt_cache_hit, bt_cache_miss; 2511573Srgrimes#endif 2521573Srgrimes 2531573Srgrimes/* 2541573Srgrimes * BT_FAST -- Do a quick check for sorted data. 2551573Srgrimes * 2561573Srgrimes * Parameters: 2571573Srgrimes * t: tree 2581573Srgrimes * key: key to insert 2591573Srgrimes * 2601573Srgrimes * Returns: 261189327Sdelphij * EPG for new record or NULL if not found. 2621573Srgrimes */ 2631573Srgrimesstatic EPG * 264189291Sdelphijbt_fast(BTREE *t, const DBT *key, const DBT *data, int *exactp) 2651573Srgrimes{ 2661573Srgrimes PAGE *h; 26714272Spst u_int32_t nbytes; 2681573Srgrimes int cmp; 2691573Srgrimes 2701573Srgrimes if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) { 2711573Srgrimes t->bt_order = NOT; 2721573Srgrimes return (NULL); 2731573Srgrimes } 2741573Srgrimes t->bt_cur.page = h; 2751573Srgrimes t->bt_cur.index = t->bt_last.index; 2761573Srgrimes 2771573Srgrimes /* 27814272Spst * If won't fit in this page or have too many keys in this page, 27914272Spst * have to search to get split stack. 2801573Srgrimes */ 2811573Srgrimes nbytes = NBLEAFDBT(key->size, data->size); 282190484Sdelphij if ((u_int32_t)(h->upper - h->lower) < nbytes + sizeof(indx_t)) 2831573Srgrimes goto miss; 2841573Srgrimes 2851573Srgrimes if (t->bt_order == FORWARD) { 2861573Srgrimes if (t->bt_cur.page->nextpg != P_INVALID) 2871573Srgrimes goto miss; 2881573Srgrimes if (t->bt_cur.index != NEXTINDEX(h) - 1) 2891573Srgrimes goto miss; 2901573Srgrimes if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0) 2911573Srgrimes goto miss; 2921573Srgrimes t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index; 2931573Srgrimes } else { 2941573Srgrimes if (t->bt_cur.page->prevpg != P_INVALID) 2951573Srgrimes goto miss; 2961573Srgrimes if (t->bt_cur.index != 0) 2971573Srgrimes goto miss; 2981573Srgrimes if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0) 2991573Srgrimes goto miss; 3001573Srgrimes t->bt_last.index = 0; 3011573Srgrimes } 3021573Srgrimes *exactp = cmp == 0; 3031573Srgrimes#ifdef STATISTICS 3041573Srgrimes ++bt_cache_hit; 3051573Srgrimes#endif 3061573Srgrimes return (&t->bt_cur); 3071573Srgrimes 3081573Srgrimesmiss: 3091573Srgrimes#ifdef STATISTICS 3101573Srgrimes ++bt_cache_miss; 3111573Srgrimes#endif 3121573Srgrimes t->bt_order = NOT; 3131573Srgrimes mpool_put(t->bt_mp, h, 0); 3141573Srgrimes return (NULL); 3151573Srgrimes} 316