1N/A * See the file LICENSE for redistribution information. 1N/A * Copyright (c) 1996, 1997, 1998 1N/A * Sleepycat Software. All rights reserved. 1N/A * Copyright (c) 1990, 1993, 1994, 1995, 1996 1N/A * Keith Bostic. All rights reserved. 1N/A * Copyright (c) 1990, 1993, 1994, 1995 1N/A * The Regents of the University of California. All rights reserved. 1N/A * This code is derived from software contributed to Berkeley by 1N/A * Redistribution and use in source and binary forms, with or without 1N/A * modification, are permitted provided that the following conditions 1N/A * 1. Redistributions of source code must retain the above copyright 1N/A * notice, this list of conditions and the following disclaimer. 1N/A * 2. Redistributions in binary form must reproduce the above copyright 1N/A * notice, this list of conditions and the following disclaimer in the 1N/A * documentation and/or other materials provided with the distribution. 1N/A * 3. All advertising materials mentioning features or use of this software 1N/A * must display the following acknowledgement: 1N/A * This product includes software developed by the University of 1N/A * California, Berkeley and its contributors. 1N/A * 4. Neither the name of the University nor the names of its contributors 1N/A * may be used to endorse or promote products derived from this software 1N/A * without specific prior written permission. 1N/A * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 1N/A * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1N/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1N/A * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 1N/A * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1N/A * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 1N/A * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 1N/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 1N/A * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 1N/A * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 1N/A#
endif /* not lint */ 1N/A * Insert an item into the tree. 1N/A * PUBLIC: int __bam_iitem __P((DBC *, 1N/A * PUBLIC: PAGE **, db_indx_t *, DBT *, DBT *, u_int32_t, u_int32_t)); 1N/A * If it's a page of duplicates, call the common code to do the work. 1N/A * Here's where the hp and indxp are important. The duplicate code 1N/A * so the caller must understand that the page stack may change. 1N/A /* Adjust the index for the new item if it's a DB_AFTER op. */ 1N/A /* Remove the current item if it's a DB_CURRENT op. */ 1N/A /* Handle fixed-length records: build the real record. */ 1N/A * Figure out how much space the data will take, including if it's a 1N/A * partial record. If either of the key or data items won't fit on 1N/A * a page, we'll have to store them on overflow pages. 1N/A /* If BI_NEWKEY is set we're adding a new key and data pair. */ 1N/A * We're either overwriting the data item of a key/data pair 1N/A * or we're adding the data item only, i.e. a new duplicate. 1N/A * If there's not enough room, or the user has put a ceiling on the 1N/A * number of keys permitted in the page, split the page. 1N/A * The t->bt_maxkey test here may be insufficient -- do we have to 1N/A * check in the btree split code, so we don't undo it there!?!? 1N/A /* Handle partial puts: build the real record. */ 1N/A * The code breaks it up into six cases: 1N/A * 3. Append a new data item (a new duplicate). 1N/A * 4. Insert a new data item (a new duplicate). 1N/A * 5. Overflow item: delete and re-add the data item. 1N/A * 6. Replace the data item. 1N/A * Adjust the cursor and copy in the key for 1N/A * Adjust the cursor and copy in the key for 1N/A * If we're dealing with offpage items, we have to 1N/A * delete and then re-add the item. 1N/A /* 6. Replace the data item. */ 1N/A * If the page is at least 50% full, and we added a duplicate, see if 1N/A * that set of duplicates takes up at least 25% of the space. If it 1N/A * does, move it off onto its own page. 1N/A * If we've changed the record count, update the tree. Record counts 1N/A * need to be updated in recno databases and in btree databases where 1N/A * we are supporting records. In both cases, adjust the count if the 1N/A * operation wasn't performed on the current record or when the caller 1N/A * overrides and wants the adjustment made regardless. 1N/A /* If we've modified a recno file, set the flag */ 1N/A * Figure out how much space a partial data item is in total. 1N/A * Figure out how much total space we'll need. If the record doesn't 1N/A * already exist, it's simply the data we're provided. 1N/A * Otherwise, it's the data provided plus any already existing data 1N/A * that we're not replacing. 1N/A * There are really two cases here: 1N/A * Case 1: We are replacing some bytes that do not exist (i.e., they 1N/A * are past the end of the record). In this case the number of bytes 1N/A * we are replacing is irrelevant and all we care about is how many 1N/A * bytes we are going to add from offset. So, the new record length 1N/A * is going to be the size of the new bytes (size) plus wherever those 1N/A * new bytes begin (doff). 1N/A * Case 2: All the bytes we are replacing exist. Therefore, the new 1N/A * size is the oldsize (nbytes) minus the bytes we are replacing (dlen) 1N/A * plus the bytes we are adding (size). 1N/A * Copy an overflow item onto a page. 1N/A * Build an overflow item and put it on the page. 1N/A * Replace an item on a page. 1N/A * PUBLIC: int __bam_ritem __P((DBC *, PAGE *, u_int32_t, DBT *)); 1N/A * Replace a single item onto a page. The logic figuring out where 1N/A * to insert and whether it fits is handled in the caller. All we do 1N/A * here is manage the page shuffling. 1N/A /* Log the change. */ 1N/A * We might as well check to see if the two data items share 1N/A * a common prefix and suffix -- it can save us a lot of log 1N/A * message if they're large. 1N/A /* We only log the parts of the keys that have changed. */ 1N/A * Set references to the first in-use byte on the page and the 1N/A * first byte of the item being replaced. 1N/A * If the entry is growing in size, shift the beginning of the data 1N/A * part of the page down. If the entry is shrinking in size, shift 1N/A * the beginning of the data part of the page up. Use memmove(3), 1N/A * the regions overlap. 1N/A if (p == t)
/* First index is fast. */ 1N/A else {
/* Else, shift the page. */ 1N/A /* Adjust the indices' offsets. */ 1N/A /* Clean up the page and adjust the item's reference. */ 1N/A /* Copy the new item onto the page. */ 1N/A * Check to see if the duplicate set at indx should have its own page. 1N/A * If it should, create it. 1N/A * If this set of duplicates is using more than 25% of the page, move 1N/A * them off. The choice of 25% is a WAG, but it has to be small enough 1N/A * that we can always split regardless of the presence of duplicates. 1N/A /* Get a new page. */ 1N/A * Move this set of duplicates off the page. First points to the first 1N/A * key of the first duplicate key/data pair, cnt is the number of pairs 1N/A * we're dealing with. 1N/A /* Copy the entry to the new page. */ 1N/A * Move cursors referencing the old entry to the new entry. 1N/A * Done after the page put because __db_pitem() adjusts 1N/A * cursors on the new page, and before the delete because 1N/A * __db_ditem adjusts cursors on the old page. 1N/A /* Delete the data item. */ 1N/A /* Delete all but the first reference to the key. */ 1N/A /* Put in a new data item that points to the duplicates page. */ 1N/A * Build the real record for a fixed length put. 1N/A * If database contains fixed-length records, and the record is long, 1N/A * The caller checked to see if it was just right, so we know it's 1N/A * short. Pad it out. We use the record data return memory, it's 1N/A * only a short-term use. 1N/A * Clean up our flags and other information just in case, and 1N/A * change the caller's DBT to reference our created record. 1N/A * Build the real record for a partial put. 1N/A /* We use the record data return memory, it's only a short-term use. */ 1N/A * We use nul bytes for any part of the record that isn't specified; 1N/A * In the next clauses, we need to do three things: a) set p to point 1N/A * to the place at which to copy the user's data, b) set tlen to the 1N/A * total length of the record, not including the bytes contributed by 1N/A * the user, and c) copy any valid data from an existing record. 1N/A /* Find the current record. */ 1N/A * In the case of an overflow record, we shift things around 1N/A * in the current record rather than allocate a separate copy. 1N/A /* Skip any leading data from the original record. */ 1N/A * Copy in any trailing data from the original record. 1N/A * If the original record was larger than the original offset 1N/A * plus the bytes being deleted, there is trailing data in the 1N/A * original record we need to preserve. If we aren't deleting 1N/A * the same number of bytes as we're inserting, copy it up or 1N/A * Use memmove(), the regions may overlap. 1N/A /* Copy in any leading data from the original record. */ 1N/A /* Copy in any trailing data from the original record. */ 1N/A * Copy in the application provided data -- p and tlen must have been 1N/A * initialized above. 1N/A /* Set the DBT to reference our new record. */