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 * Search a btree for a key. 1N/A * PUBLIC: int __bam_search __P((DBC *, 1N/A * PUBLIC: const DBT *, u_int32_t, int, db_recno_t *, int *)); 1N/A * There are several ways we search a btree tree. The flags argument 1N/A * specifies if we're acquiring read or write locks, if we position 1N/A * to the first or last item in a set of duplicates, if we return 1N/A * deleted items, and if we are locking pairs of pages. In addition, 1N/A * if we're modifying record numbers, we have to lock the entire tree 1N/A * If write-locking pages, we need to know whether or not to acquire a 1N/A * write lock on a page before getting it. This depends on how deep it 1N/A * is in tree, which we don't know until we acquire the root page. So, 1N/A * if we need to lock the root page we may have to upgrade it later, 1N/A * because we won't get the correct lock initially. 1N/A * Retrieve the root page. 1N/A * Decide if we need to save this page; if we do, write lock it. 1N/A * We deliberately don't lock-couple on this call. If the tree 1N/A * is tiny, i.e., one page, and two threads are busily updating 1N/A * the root page, we're almost guaranteed deadlocks galore, as 1N/A * each one gets a read lock and then blocks the other's attempt 1N/A * Do a binary search on the current page. If we're searching 1N/A * a leaf page, we have to manipulate the indices in groups of 1N/A * two. If we're searching an internal page, they're an index 1N/A * per page item. If we find an exact match on a leaf page, 1N/A * No match found. Base is the smallest index greater than 1N/A * key and may be zero or a last + O_INDX index. 1N/A * If it's a leaf page, return base as the "found" value. 1N/A * Delete only deletes exact matches. 1N/A * Possibly returning a deleted record -- DB_SET_RANGE, 1N/A * DB_KEYFIRST and DB_KEYLAST don't require an exact 1N/A * match, and we don't want to walk multiple pages here 1N/A * to find an undeleted record. This is handled in the 1N/A * __bam_c_search() routine. 1N/A * If it's not a leaf page, record the internal page (which is 1N/A * a parent page for the key). Decrement the base by 1 if it's 1N/A * non-zero so that if a split later occurs, the inserted page 1N/A * will be to the right of the saved page. 1N/A * If we're trying to calculate the record number, sum up 1N/A * all the record numbers on this page up to the indx point. 1N/A /* Return if this is the lowest page wanted. */ 1N/A * Decide if we want to return a reference to the next 1N/A * page in the return stack. If so, lock it and never 1N/A * If we're trying to calculate the record number, add in the 1N/A * offset on this page and correct for the fact that records 1N/A * in the tree are 0-based. 1N/A * If we got here, we know that we have a btree leaf page. 1N/A * If there are duplicates, go to the first/last one. This is 1N/A * safe because we know that we're not going to leave the page, 1N/A * all duplicate sets that are not on overflow pages exist on a 1N/A * Now check if we are allowed to return deleted items; if not 1N/A * find the next (or previous) non-deleted item. 1N/A * Release all pages currently held in the stack. 1N/A * PUBLIC: int __bam_stkrel __P((DBC *, int)); 1N/A /* Release inner pages first. */ 1N/A /* Clear the stack, all pages have been released. */ 1N/A * PUBLIC: int __bam_stkgrow __P((CURSOR *));