bt_put.c revision 92905
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 * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 351573Srgrimes */ 361573Srgrimes 371573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3814272Spststatic char sccsid[] = "@(#)bt_put.c 8.8 (Berkeley) 7/26/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 4092905Sobrien#include <sys/cdefs.h> 4192905Sobrien__FBSDID("$FreeBSD: head/lib/libc/db/btree/bt_put.c 92905 2002-03-21 22:49:10Z obrien $"); 421573Srgrimes 431573Srgrimes#include <sys/types.h> 441573Srgrimes 451573Srgrimes#include <errno.h> 461573Srgrimes#include <stdio.h> 471573Srgrimes#include <stdlib.h> 481573Srgrimes#include <string.h> 491573Srgrimes 501573Srgrimes#include <db.h> 511573Srgrimes#include "btree.h" 521573Srgrimes 5392905Sobrienstatic EPG *bt_fast(BTREE *, const DBT *, const DBT *, int *); 541573Srgrimes 551573Srgrimes/* 561573Srgrimes * __BT_PUT -- Add a btree item to the tree. 571573Srgrimes * 581573Srgrimes * Parameters: 591573Srgrimes * dbp: pointer to access method 601573Srgrimes * key: key 611573Srgrimes * data: data 621573Srgrimes * flag: R_NOOVERWRITE 631573Srgrimes * 641573Srgrimes * Returns: 651573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the 661573Srgrimes * tree and R_NOOVERWRITE specified. 671573Srgrimes */ 681573Srgrimesint 691573Srgrimes__bt_put(dbp, key, data, flags) 701573Srgrimes const DB *dbp; 711573Srgrimes DBT *key; 721573Srgrimes const DBT *data; 731573Srgrimes u_int flags; 741573Srgrimes{ 751573Srgrimes BTREE *t; 761573Srgrimes DBT tkey, tdata; 771573Srgrimes EPG *e; 781573Srgrimes PAGE *h; 791573Srgrimes indx_t index, nxtindex; 801573Srgrimes pgno_t pg; 8114272Spst u_int32_t nbytes; 821573Srgrimes int dflags, exact, status; 831573Srgrimes char *dest, db[NOVFLSIZE], kb[NOVFLSIZE]; 841573Srgrimes 851573Srgrimes t = dbp->internal; 861573Srgrimes 871573Srgrimes /* Toss any page pinned across calls. */ 881573Srgrimes if (t->bt_pinned != NULL) { 891573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 901573Srgrimes t->bt_pinned = NULL; 911573Srgrimes } 921573Srgrimes 9314272Spst /* Check for change to a read-only tree. */ 9414272Spst if (F_ISSET(t, B_RDONLY)) { 9514272Spst errno = EPERM; 9614272Spst return (RET_ERROR); 9714272Spst } 9814272Spst 991573Srgrimes switch (flags) { 1001573Srgrimes case 0: 1011573Srgrimes case R_NOOVERWRITE: 1021573Srgrimes break; 10314272Spst case R_CURSOR: 10414272Spst /* 10514272Spst * If flags is R_CURSOR, put the cursor. Must already 10614272Spst * have started a scan and not have already deleted it. 10714272Spst */ 10814272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 10914272Spst !F_ISSET(&t->bt_cursor, 11014272Spst CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) 11114272Spst break; 11214272Spst /* FALLTHROUGH */ 1131573Srgrimes default: 11414272Spst errno = EINVAL; 1151573Srgrimes return (RET_ERROR); 1161573Srgrimes } 1171573Srgrimes 1181573Srgrimes /* 11914272Spst * If the key/data pair won't fit on a page, store it on overflow 12014272Spst * pages. Only put the key on the overflow page if the pair are 12114272Spst * still too big after moving the data to an overflow page. 1221573Srgrimes * 1231573Srgrimes * XXX 12414272Spst * If the insert fails later on, the overflow pages aren't recovered. 1251573Srgrimes */ 1261573Srgrimes dflags = 0; 1271573Srgrimes if (key->size + data->size > t->bt_ovflsize) { 1281573Srgrimes if (key->size > t->bt_ovflsize) { 1291573Srgrimesstorekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) 1301573Srgrimes return (RET_ERROR); 1311573Srgrimes tkey.data = kb; 1321573Srgrimes tkey.size = NOVFLSIZE; 1331573Srgrimes memmove(kb, &pg, sizeof(pgno_t)); 1341573Srgrimes memmove(kb + sizeof(pgno_t), 13514272Spst &key->size, sizeof(u_int32_t)); 1361573Srgrimes dflags |= P_BIGKEY; 1371573Srgrimes key = &tkey; 1381573Srgrimes } 1391573Srgrimes if (key->size + data->size > t->bt_ovflsize) { 1401573Srgrimes if (__ovfl_put(t, data, &pg) == RET_ERROR) 1411573Srgrimes return (RET_ERROR); 1421573Srgrimes tdata.data = db; 1431573Srgrimes tdata.size = NOVFLSIZE; 1441573Srgrimes memmove(db, &pg, sizeof(pgno_t)); 1451573Srgrimes memmove(db + sizeof(pgno_t), 14614272Spst &data->size, sizeof(u_int32_t)); 1471573Srgrimes dflags |= P_BIGDATA; 1481573Srgrimes data = &tdata; 1491573Srgrimes } 1501573Srgrimes if (key->size + data->size > t->bt_ovflsize) 1511573Srgrimes goto storekey; 1521573Srgrimes } 1531573Srgrimes 1541573Srgrimes /* Replace the cursor. */ 1551573Srgrimes if (flags == R_CURSOR) { 15614272Spst if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL) 1571573Srgrimes return (RET_ERROR); 15814272Spst index = t->bt_cursor.pg.index; 1591573Srgrimes goto delete; 1601573Srgrimes } 1611573Srgrimes 1621573Srgrimes /* 16314272Spst * Find the key to delete, or, the location at which to insert. 16414272Spst * Bt_fast and __bt_search both pin the returned page. 1651573Srgrimes */ 1661573Srgrimes if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) 1671573Srgrimes if ((e = __bt_search(t, key, &exact)) == NULL) 1681573Srgrimes return (RET_ERROR); 1691573Srgrimes h = e->page; 1701573Srgrimes index = e->index; 1711573Srgrimes 1721573Srgrimes /* 17314272Spst * Add the key/data pair to the tree. If an identical key is already 17414272Spst * in the tree, and R_NOOVERWRITE is set, an error is returned. If 17514272Spst * R_NOOVERWRITE is not set, the key is either added (if duplicates are 17614272Spst * permitted) or an error is returned. 1771573Srgrimes */ 1781573Srgrimes switch (flags) { 1791573Srgrimes case R_NOOVERWRITE: 1801573Srgrimes if (!exact) 1811573Srgrimes break; 1821573Srgrimes mpool_put(t->bt_mp, h, 0); 1831573Srgrimes return (RET_SPECIAL); 1841573Srgrimes default: 18514272Spst if (!exact || !F_ISSET(t, B_NODUPS)) 1861573Srgrimes break; 18714272Spst /* 18814272Spst * !!! 18914272Spst * Note, the delete may empty the page, so we need to put a 19014272Spst * new entry into the page immediately. 19114272Spst */ 19214272Spstdelete: if (__bt_dleaf(t, key, h, index) == RET_ERROR) { 1931573Srgrimes mpool_put(t->bt_mp, h, 0); 1941573Srgrimes return (RET_ERROR); 1951573Srgrimes } 1961573Srgrimes break; 1971573Srgrimes } 1981573Srgrimes 1991573Srgrimes /* 2001573Srgrimes * If not enough room, or the user has put a ceiling on the number of 2011573Srgrimes * keys permitted in the page, split the page. The split code will 2021573Srgrimes * insert the key and data and unpin the current page. If inserting 2031573Srgrimes * into the offset array, shift the pointers up. 2041573Srgrimes */ 2051573Srgrimes nbytes = NBLEAFDBT(key->size, data->size); 2061573Srgrimes if (h->upper - h->lower < nbytes + sizeof(indx_t)) { 2071573Srgrimes if ((status = __bt_split(t, h, key, 2081573Srgrimes data, dflags, nbytes, index)) != RET_SUCCESS) 2091573Srgrimes return (status); 2101573Srgrimes goto success; 2111573Srgrimes } 2121573Srgrimes 2131573Srgrimes if (index < (nxtindex = NEXTINDEX(h))) 2141573Srgrimes memmove(h->linp + index + 1, h->linp + index, 2151573Srgrimes (nxtindex - index) * sizeof(indx_t)); 2161573Srgrimes h->lower += sizeof(indx_t); 2171573Srgrimes 2181573Srgrimes h->linp[index] = h->upper -= nbytes; 2191573Srgrimes dest = (char *)h + h->upper; 2201573Srgrimes WR_BLEAF(dest, key, data, dflags); 2211573Srgrimes 22214272Spst /* If the cursor is on this page, adjust it as necessary. */ 22314272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 22414272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 22514272Spst t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= index) 22614272Spst ++t->bt_cursor.pg.index; 22714272Spst 2281573Srgrimes if (t->bt_order == NOT) 2291573Srgrimes if (h->nextpg == P_INVALID) { 2301573Srgrimes if (index == NEXTINDEX(h) - 1) { 2311573Srgrimes t->bt_order = FORWARD; 2321573Srgrimes t->bt_last.index = index; 2331573Srgrimes t->bt_last.pgno = h->pgno; 2341573Srgrimes } 2351573Srgrimes } else if (h->prevpg == P_INVALID) { 2361573Srgrimes if (index == 0) { 2371573Srgrimes t->bt_order = BACK; 2381573Srgrimes t->bt_last.index = 0; 2391573Srgrimes t->bt_last.pgno = h->pgno; 2401573Srgrimes } 2411573Srgrimes } 2421573Srgrimes 2431573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 2441573Srgrimes 2451573Srgrimessuccess: 24614272Spst if (flags == R_SETCURSOR) 24714272Spst __bt_setcur(t, e->page->pgno, e->index); 24814272Spst 24914272Spst F_SET(t, B_MODIFIED); 2501573Srgrimes return (RET_SUCCESS); 2511573Srgrimes} 2521573Srgrimes 2531573Srgrimes#ifdef STATISTICS 2541573Srgrimesu_long bt_cache_hit, bt_cache_miss; 2551573Srgrimes#endif 2561573Srgrimes 2571573Srgrimes/* 2581573Srgrimes * BT_FAST -- Do a quick check for sorted data. 2591573Srgrimes * 2601573Srgrimes * Parameters: 2611573Srgrimes * t: tree 2621573Srgrimes * key: key to insert 2631573Srgrimes * 2641573Srgrimes * Returns: 2651573Srgrimes * EPG for new record or NULL if not found. 2661573Srgrimes */ 2671573Srgrimesstatic EPG * 2681573Srgrimesbt_fast(t, key, data, exactp) 2691573Srgrimes BTREE *t; 2701573Srgrimes const DBT *key, *data; 2711573Srgrimes int *exactp; 2721573Srgrimes{ 2731573Srgrimes PAGE *h; 27414272Spst u_int32_t nbytes; 2751573Srgrimes int cmp; 2761573Srgrimes 2771573Srgrimes if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) { 2781573Srgrimes t->bt_order = NOT; 2791573Srgrimes return (NULL); 2801573Srgrimes } 2811573Srgrimes t->bt_cur.page = h; 2821573Srgrimes t->bt_cur.index = t->bt_last.index; 2831573Srgrimes 2841573Srgrimes /* 28514272Spst * If won't fit in this page or have too many keys in this page, 28614272Spst * have to search to get split stack. 2871573Srgrimes */ 2881573Srgrimes nbytes = NBLEAFDBT(key->size, data->size); 2891573Srgrimes if (h->upper - h->lower < nbytes + sizeof(indx_t)) 2901573Srgrimes goto miss; 2911573Srgrimes 2921573Srgrimes if (t->bt_order == FORWARD) { 2931573Srgrimes if (t->bt_cur.page->nextpg != P_INVALID) 2941573Srgrimes goto miss; 2951573Srgrimes if (t->bt_cur.index != NEXTINDEX(h) - 1) 2961573Srgrimes goto miss; 2971573Srgrimes if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0) 2981573Srgrimes goto miss; 2991573Srgrimes t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index; 3001573Srgrimes } else { 3011573Srgrimes if (t->bt_cur.page->prevpg != P_INVALID) 3021573Srgrimes goto miss; 3031573Srgrimes if (t->bt_cur.index != 0) 3041573Srgrimes goto miss; 3051573Srgrimes if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0) 3061573Srgrimes goto miss; 3071573Srgrimes t->bt_last.index = 0; 3081573Srgrimes } 3091573Srgrimes *exactp = cmp == 0; 3101573Srgrimes#ifdef STATISTICS 3111573Srgrimes ++bt_cache_hit; 3121573Srgrimes#endif 3131573Srgrimes return (&t->bt_cur); 3141573Srgrimes 3151573Srgrimesmiss: 3161573Srgrimes#ifdef STATISTICS 3171573Srgrimes ++bt_cache_miss; 3181573Srgrimes#endif 3191573Srgrimes t->bt_order = NOT; 3201573Srgrimes mpool_put(t->bt_mp, h, 0); 3211573Srgrimes return (NULL); 3221573Srgrimes} 323