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 * Delete the items referenced by a key. 1N/A * PUBLIC: int __bam_delete __P((DB *, DB_TXN *, DBT *, u_int32_t)); 1N/A /* Check for invalid flags. */ 1N/A /* Allocate a cursor. */ 1N/A * Walk a cursor through the key/data pairs, deleting as we go. Set 1N/A * the DB_DBT_USERMEM flag, as this might be a threaded application 1N/A * and the flags checking will catch us. We don't actually want the 1N/A * keys or data, so request a partial of length 0. 1N/A /* If locking, set read-modify-write flag. */ 1N/A /* Walk through the set of key/data pairs, deleting as we go. */ 1N/A * Delete one or more entries from a page. 1N/A * PUBLIC: int __bam_ditem __P((DBC *, PAGE *, u_int32_t)); 1N/A * If it's a duplicate key, discard the index and don't touch 1N/A * the actual page item. 1N/A * This works because no data item can have an index matching 1N/A * any other index so even if the data item is in a key "slot", 1N/A * it won't match any other index. 1N/A * Check for a duplicate after us on the page. NOTE: 1N/A * we have to delete the key item before deleting the 1N/A * data item, otherwise the "indx + P_INDX" calculation 1N/A * Check for a duplicate before us on the page. It 1N/A * doesn't matter if we delete the key item before or 1N/A * after the data item for the purposes of this one. 1N/A /* Delete the item. */ 1N/A /* Mark the page dirty. */ 1N/A * Adjust an index on the page. 1N/A * PUBLIC: int __bam_adjindx __P((DBC *, PAGE *, u_int32_t, u_int32_t, int)); 1N/A /* Log the change. */ 1N/A /* Mark the page dirty. */ 1N/A /* Adjust the cursors. */ 1N/A * Delete a page from the tree. 1N/A * PUBLIC: int __bam_dpage __P((DBC *, const DBT *)); 1N/A int level;
/* !!!: has to hold number of tree levels. */ 1N/A * The locking protocol is that we acquire locks by walking down the 1N/A * tree, to avoid the obvious deadlocks. 1N/A * Call __bam_search to reacquire the empty leaf page, but this time 1N/A * get both the leaf page and it's parent, locked. Walk back up the 1N/A * tree, until we have the top pair of pages that we want to delete. 1N/A * Once we have the top page that we want to delete locked, lock the 1N/A * underlying pages and check to make sure they're still empty. If 1N/A * they are, delete them. 1N/A /* Acquire a page and its parent, locked. */ 1N/A * If we reach the root or the page isn't going to be empty 1N/A * when we delete one record, quit. 1N/A /* Release the two locked pages. */ 1N/A * Leave the stack pointer one after the last entry, we may be about 1N/A * to push more items on the stack. 1N/A * cp->csp[-2].page is the top page, which we're not going to delete, 1N/A * and cp->csp[-1].page is the first page we are going to delete. 1N/A * Walk down the chain, acquiring the rest of the pages until we've 1N/A * retrieved the leaf page. If we find any pages that aren't going 1N/A * to be emptied by the delete, someone else added something while we 1N/A * were walking the tree, and we discontinue the delete. 1N/A * Get the next page, write lock it and push it onto the stack. 1N/A * We know it's index 0, because it can only have one element. 1N/A /* Adjust back to reference the last page on the stack. */ 1N/A /* Delete the pages. */ 1N/A /* Adjust back to reference the last page on the stack. */ 1N/A /* Discard any locked pages and return. */ 1N/A * Delete a set of locked pages. 1N/A * PUBLIC: int __bam_dpages __P((DBC *)); 1N/A * There is an interesting deadlock situation here. We have to relink 1N/A * the leaf page chain around the leaf page being deleted. Consider 1N/A * a cursor walking through the leaf pages, that has the previous page 1N/A * read-locked and is waiting on a lock for the page we're deleting. 1N/A * It will deadlock here. This is a problem, because if our process is 1N/A * selected to resolve the deadlock, we'll leave an empty leaf page 1N/A * that we can never again access by walking down the tree. So, before 1N/A * we unlink the subtree, we relink the leaf page chain. 1N/A * We have the entire stack of deletable pages locked. 1N/A * Delete the highest page in the tree's reference to the underlying 1N/A * stack of pages. Then, release that page, letting the rest of the 1N/A * tree get back to business. 1N/A * Free the rest of the stack of pages. 1N/A * Don't bother checking for errors. We've unlinked the subtree from 1N/A * the tree, and there's no possibility of recovery outside of doing 1N/A * Delete page entries so they will be restored as part of 1N/A * Try and collapse the tree a level -- this is only applicable 1N/A * if we've deleted the next-to-last element from the root page. 1N/A * There are two cases when collapsing a tree. 1N/A * If we've just deleted the last item from the root page, there is no 1N/A * further work to be done. The code above has emptied the root page 1N/A * and freed all pages below it. 1N/A * If we just deleted the next-to-last item from the root page, the 1N/A * tree can collapse one or more levels. While there remains only a 1N/A * single item on the root page, write lock the last page referenced 1N/A * by the root page and copy it over the root page. If we can't get a 1N/A * write lock, that's okay, the tree just stays deeper than we'd like. 1N/A /* Lock the root. */ 1N/A /* Lock the child page. */ 1N/A /* Log the change. */ 1N/A * One fixup -- if the tree has record numbers and we're not 1N/A * converting to a leaf page, we have to preserve the total 1N/A * record count. Note that we are about to overwrite everything 1N/A * on the parent, including its LSN. This is actually OK, 1N/A * because the above log message, which describes this update, 1N/A * stores its LSN on the child page. When the child is copied 1N/A * to the parent, the correct LSN is going to copied into 1N/A * place in the parent. 1N/A /* Mark the pages dirty. */ 1N/A /* Adjust the cursors. */ 1N/A * Free the page copied onto the root page and discard its 1N/A * lock. (The call to __bam_free() discards our reference