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 1N/A * The Regents of the University of California. All rights reserved. 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 record number. 1N/A * PUBLIC: int __bam_rsearch __P((DBC *, db_recno_t *, u_int32_t, int, 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 and if we are 1N/A * locking pairs of pages. In addition, if we're adding or deleting 1N/A * an item, we have to lock the entire tree, regardless. See btree.h 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 * If appending to the tree, set the record number now -- we have the 1N/A * Delete only deletes exact matches, read only returns exact matches. 1N/A * Note, this is different from __bam_search(), which returns non-exact 1N/A * The record may not exist. We can only return the correct location 1N/A * for the record immediately after the last record in the tree, so do 1N/A * Record numbers in the tree are 0-based, but the recno is 1N/A * 1-based. All of the calculations below have to take this 1N/A * There may be logically deleted records on the page, 1N/A * walk the page correcting for them. The record may 1N/A * not exist if there are enough deleted records in the 1N/A /* Correct from 1-based to 0-based for a page offset. */ 1N/A /* Correct from 1-based to 0-based for a page offset. */ 1N/A /* Return if this is the lowest page wanted. */ 1N/A * Decide if we want to return a pointer to the next 1N/A * page in the stack. If we do, write lock it and 1N/A * Adjust the tree after adding or deleting a record. 1N/A * PUBLIC: int __bam_adjust __P((DBC *, int32_t)); 1N/A /* Update the record counts for the tree. */ 1N/A * Return the number of records in the tree. 1N/A * PUBLIC: int __bam_nrecs __P((DBC *, db_recno_t *)); 1N/A * Return the number of records below a page. 1N/A * PUBLIC: db_recno_t __bam_total __P((PAGE *)); 1N/A /* Check for logically deleted records. */