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#
endif /* not lint */ 1N/A/* If the cursor references a deleted record. */ 1N/A/* If the cursor and index combination references a deleted record. */ 1N/A * Test to see if two cursors could point to duplicates of the same key, 1N/A * whether on-page or off-page. The leaf page numbers must be the same 1N/A * in both cases. In the case of off-page duplicates, the key indices 1N/A * on the leaf page will be the same. In the case of on-page duplicates, 1N/A * the duplicate page number must not be set, and the key index offsets 1N/A * must be the same. For the last test, as the saved copy of the cursor 1N/A * will not have a valid page pointer, we use the cursor's. 1N/A * Initialize internal cursor structure. 1N/A * Initialize the access private portion of a cursor 1N/A * PUBLIC: int __bam_c_init __P((DBC *)); 1N/A * Logical record numbers are always the same size, and we don't want 1N/A * to have to check for space every time we return one. Allocate it 1N/A /* Initialize methods. */ 1N/A /* Initialize dynamic information. */ 1N/A * Close down the cursor from a single use. 1N/A * If a cursor deleted a btree key, perform the actual deletion. 1N/A * (Recno keys are either deleted immediately or never deleted.) 1N/A /* Discard any locks not acquired inside of a transaction. */ 1N/A /* Sanity checks. */ 1N/A /* Initialize dynamic information. */ 1N/A * __bam_c_destroy -- 1N/A * Close a single cursor -- internal version. 1N/A /* Discard the structures. */ 1N/A * Delete using a cursor. 1N/A /* Check for invalid flags. */ 1N/A * If we are running CDB, this had better be either a write 1N/A * cursor or an immediate writer. 1N/A /* If already deleted, return failure. */ 1N/A * We don't physically delete the record until the cursor moves, 1N/A * so we have to have a long-lived write lock on the page instead 1N/A * of a long-lived read lock. Note, we have to have a read lock 1N/A * to even get here, so we simply discard it. 1N/A * Acquire the underlying page (which may be different from the above 1N/A * page because it may be a duplicate page), and set the on-page and 1N/A * in-cursor delete flags. We don't need to lock it as we've already 1N/A * write-locked the page leading to it. 1N/A /* Log the change. */ 1N/A * Set the intent-to-delete flag on the page and update all cursors. */ 1N/A * If the tree has record numbers, we have to adjust the counts. 1N/A * This test is right -- we don't yet support duplicates and record 1N/A * numbers in the same tree, so ignore duplicates if DB_BT_RECNUM 1N/A * Get using a cursor (btree). 1N/A /* Check for invalid flags. */ 1N/A /* Clear OR'd in additional bits so we can check for flag equality. */ 1N/A * Return a cursor's record number. It has nothing to do with the 1N/A * cursor get code except that it's been rammed into the interface. 1N/A * Initialize the cursor for a new retrieval. Clear the cursor's 1N/A * page pointer, it was set before this operation, and no longer 1N/A /* It's not possible to return a deleted record. */ 1N/A /* Acquire the current page. */ 1N/A /* Make sure we didn't go past the end of the duplicates. */ 1N/A * We cannot currently be referencing a deleted record, but we 1N/A * may be referencing off-page duplicates. 1N/A * If we're referencing off-page duplicates, move off-page. 1N/A * If we moved off-page, move to the next non-deleted record. 1N/A * If we moved to the next non-deleted record, check to make 1N/A * sure we didn't switch records because our current record 1N/A * had no non-deleted data items. 1N/A /* Acquire the current page. */ 1N/A /* If DBC_CONTINUE, move to the next item. */ 1N/A * We may be referencing a duplicates page. Move to 1N/A * the first duplicate. 1N/A /* Search for a matching entry. */ 1N/A /* Ignore deleted entries. */ 1N/A * As we didn't require an exact match, the search function 1N/A * may have returned an entry past the end of the page. If 1N/A * so, move to the next entry. 1N/A * We may be referencing off-page duplicates, if so, move 1N/A * We may be referencing a deleted record, if so, move to 1N/A * the next non-deleted record. 1N/A * Return the key if the user didn't give us one. If we've moved to 1N/A * a duplicate page, we may no longer have a pointer to the main page, 1N/A * so we have to go get it. We know that it's already read-locked, 1N/A * however, so we don't have to acquire a new lock. 1N/A /* Return the data. */ 1N/A * If the previous cursor record has been deleted, physically delete 1N/A * the entry from the page. We clear the deleted flag before we call 1N/A * the underlying delete routine so that, if an error occurs, and we 1N/A * restore the cursor, the deleted flag is cleared. This is because, 1N/A * if we manage to physically modify the page, and then restore the 1N/A * cursor, we might try to repeat the page modification when closing 1N/A /* Release the previous lock, if any; the current lock is retained. */ 1N/A /* Release the current page. */ 1N/A /* Release temporary lock upgrade. */ 1N/A * Search for a matching data item (or the first data item that's 1N/A * equal to or greater than the one we're searching for). 1N/A * If iflagp is non-NULL, we're doing an insert. 1N/A * If the duplicates are off-page, use the duplicate search routine. 1N/A /* Otherwise, do the search ourselves. */ 1N/A /* Save the last interesting cursor position. */ 1N/A /* See if the data item matches the one we're looking for. */ 1N/A * If duplicate entries are sorted, we're done if we find a 1N/A * page entry that sorts greater than the application item. 1N/A * If doing an insert, return success, otherwise DB_NOTFOUND. 1N/A * Move to the next item. If we reach the end of the page and 1N/A * we're doing an insert, set the cursor to the last item and 1N/A * set the referenced memory location so callers know to insert 1N/A * after the item, instead of before it. If not inserting, we 1N/A * return DB_NOTFOUND. 1N/A * Make sure we didn't go past the end of the duplicates. The 1N/A * error conditions are the same as above. 1N/A * Return the record number for a cursor. 1N/A /* Get the page with the current item on it. */ 1N/A /* Get a copy of the key. */ 1N/A /* Release the stack. */ 1N/A * Put using a cursor. 1N/A * If we are running CDB, this had better be either a write 1N/A * cursor or an immediate writer. If it's a regular writer, 1N/A * that means we have an IWRITE lock and we need to upgrade 1N/A * it to a write lock. 1N/A * To split, we need a valid key for the page. Since it's a 1N/A * cursor, we have to build one. 1N/A * Acquire a copy of a key from the page. 1N/A * Discard any locks and pinned pages (the locks are discarded 1N/A * even if we're running with transactions, as they lock pages 1N/A * that we're sorry we ever acquired). If stack is set and the 1N/A * cursor entries are valid, they point to the same entries as 1N/A * the stack, don't free them twice. 1N/A * Restore the cursor to its original value. This is necessary 1N/A * for two reasons. First, we are about to copy it in case of 1N/A * error, again. Second, we adjust cursors during the split, 1N/A * and we have to ensure this cursor is adjusted appropriately, 1N/A * along with all the other cursors. 1N/A * Initialize the cursor for a new retrieval. Clear the cursor's 1N/A * page pointer, it was set before this operation, and no longer 1N/A * This test is right -- we don't yet support duplicates and 1N/A * record numbers in the same tree, so ignore duplicates if 1N/A /* Acquire a complete stack. */ 1N/A /* Acquire the current page. */ 1N/A * If the user has specified a duplicate comparison function, 1N/A * we return an error if DB_CURRENT was specified and the 1N/A * replacement data doesn't compare equal to the current data. 1N/A * This stops apps from screwing up the duplicate sort order. 1N/A * If we have a duplicate comparison function, we position to 1N/A * the first of any on-page duplicates, and use __bam_dsearch 1N/A * to search for the right slot. Otherwise, we position to 1N/A * the first/last of any on-page duplicates based on the flag 1N/A * If an exact match: 1N/A * If duplicates aren't supported, replace the current 1N/A * item. (When implementing the DB->put function, our 1N/A * caller has already checked the DB_NOOVERWRITE flag.) 1N/A * If there's a duplicate comparison function, find the 1N/A * correct slot for this duplicate item. 1N/A * If there's no duplicate comparison function, set the 1N/A * insert flag based on the argument flags. 1N/A * If there's no match, the search function returned the 1N/A * smallest slot greater than the key, use it. 1N/A * If at off-page duplicate page, move to the 1N/A * first or last entry -- if a comparison 1N/A * function was specified, start searching at 1N/A * the first entry. Otherwise, move based on 1N/A * If there's a comparison function, search for 1N/A * the correct slot. Otherwise, set the insert 1N/A * flag based on the argment flag. 1N/A * Reset any cursors referencing this item that might have the item 1N/A * marked for deletion. 1N/A * It's also possible that we are the cursor that had the 1N/A * item marked for deletion, in which case we want to make 1N/A * sure that we don't delete it because we had the delete 1N/A * Update the cursor to point to the new entry. The new entry was 1N/A * stored on the current page, because we split pages until it was 1N/A * If the previous cursor record has been deleted, physically delete 1N/A * the entry from the page. We clear the deleted flag before we call 1N/A * the underlying delete routine so that, if an error occurs, and we 1N/A * restore the cursor, the deleted flag is cleared. This is because, 1N/A * if we manage to physically modify the page, and then restore the 1N/A * cursor, we might try to repeat the page modification when closing 1N/A /* Release the previous lock, if any; the current lock is retained. */ 1N/A * Discard any pages pinned in the tree and their locks, except for 1N/A * the leaf page, for which we only discard the pin, not the lock. 1N/A * Note, the leaf page participated in the stack we acquired, and so 1N/A * we have to adjust the stack as necessary. If there was only a 1N/A * single page on the stack, we don't have to free further stack pages. 1N/A /* Release the current page. */ 1N/Aerr:
/* Discard any pinned pages. */ 1N/A * Return the first record. 1N/A /* Walk down the left-hand side of the tree. */ 1N/A /* If we find a leaf page, we're done. */ 1N/A /* Check for duplicates. */ 1N/A /* If on an empty page or a deleted record, move to the next one. */ 1N/A * Return the last record. 1N/A /* Walk down the right-hand side of the tree. */ 1N/A /* If we find a leaf page, we're done. */ 1N/A /* Check for duplicates. */ 1N/A /* If on an empty page or a deleted record, move to the next one. */ 1N/A * Move to the next record. 1N/A * We're either moving through a page of duplicates or a btree leaf 1N/A * If at the end of the page, move to a subsequent page. 1N/A * Check for >= NUM_ENT. If we're here as the result of a search that 1N/A * landed us on NUM_ENT, we'll increment indx before we test. 1N/A * This code handles empty pages and pages with only deleted entries. 1N/A * If we're in a btree leaf page, we've reached the end 1N/A * of the tree. If we've reached the end of a page of 1N/A * duplicates, continue from the btree leaf page where 1N/A * we found this page of duplicates. 1N/A /* If in a btree leaf page, it's EOF. */ 1N/A /* Continue from the last btree leaf page. */ 1N/A /* Ignore deleted records. */ 1N/A * If we're not in a duplicates page, check to see if we've 1N/A * found a page of duplicates, in which case we move to the 1N/A * Move to the previous record. 1N/A * We're either moving through a page of duplicates or a btree leaf 1N/A * If at the beginning of the page, move to any previous one. 1N/A * This code handles empty pages and pages with only deleted entries. 1N/A * If we're in a btree leaf page, we've reached the 1N/A * beginning of the tree. If we've reached the first 1N/A * of a page of duplicates, continue from the btree 1N/A * leaf page where we found this page of duplicates. 1N/A /* If in a btree leaf page, it's SOF. */ 1N/A /* Continue from the last btree leaf page. */ 1N/A /* Ignore deleted records. */ 1N/A * If we're not in a duplicates page, check to see if we've 1N/A * found a page of duplicates, in which case we move to the 1N/A * Move to a specified record. 1N/A /* Find an entry in the database. */ 1N/A * If the application has a history of inserting into the first 1N/A * or last pages of the database, we check those pages first to 1N/A * avoid doing a full search. 1N/A * Record numbers can't be fast-tracked, the entire tree has to 1N/A /* Check if the application has a history of sorted input. */ 1N/A * Lock and retrieve the page on which we did the last insert. 1N/A * It's okay if it doesn't exist, or if it's not the page type 1N/A * we expected, it just means that the world changed. 1N/A * What we do here is test to see if we're at the beginning or 1N/A * first/last page entry. We don't try and catch inserts into 1N/A * the middle of the tree (although we could, as long as there 1N/A * were two keys on the page and we saved both the index and 1N/A * the page number of the last insert). 1N/A * Found a duplicate. If doing DB_KEYLAST, we're at 1N/A * the correct position, otherwise, move to the first 1N/A * of the duplicates. 1N/A * Found a duplicate. If doing DB_KEYFIRST, we're at 1N/A * the correct position, otherwise, move to the last 1N/A * of the duplicates. 1N/Afast_hit:
/* Set the exact match flag, we may have found a duplicate. */ 1N/A /* Enter the entry in the stack. */ 1N/A default:
/* XXX: Impossible. */ 1N/A * Initialize the cursor to reference it. This has to be done 1N/A * before we return (even with DB_NOTFOUND) because we have to 1N/A * free the page(s) we locked in __bam_search. 1N/A * If we inserted a key into the first or last slot of the tree, 1N/A * remember where it was so we can do it more quickly next time. 1N/A /* If we need an exact match and didn't find one, we're done. */ 1N/A * Check for an off-page duplicates entry, and if found, move to the 1N/A * first or last entry. 1N/A * PUBLIC: int __bam_dup __P((DBC *, CURSOR *, u_int32_t, int)); 1N/A * Check for an overflow entry. If we find one, move to the 1N/A * duplicates page, and optionally move to the last record on 1N/A * We don't lock duplicates pages, we've already got the correct 1N/A * lock on the main page. 1N/A /* Update the cursor's duplicate information. */ 1N/A * __bam_c_physdel -- 1N/A * Actually do the cursor deletion. 1N/A /* Figure out what we're deleting. */ 1N/A * If the item is referenced by another cursor, set that cursor's 1N/A * delete flag and leave it up to it to do the delete. 1N/A * This test for > 0 is a tricky. There are two ways that we can 1N/A * be called here. Either we are closing the cursor or we've moved 1N/A * off the page with the deleted entry. In the first case, we've 1N/A * already removed the cursor from the active queue, so we won't see 1N/A * it in __bam_ca_delete. In the second case, it will be on a different 1N/A * item, so we won't bother with it in __bam_ca_delete. 1N/A * If this is concurrent DB, upgrade the lock if necessary. 1N/A * If we don't already have the page locked, get it and delete the 1N/A * If we're deleting a duplicate entry and there are other duplicate 1N/A * entries remaining, call the common code to do the work and fix up 1N/A * the parent page as necessary. Otherwise, do a normal btree delete. 1N/A * There are 5 possible cases: 1N/A * 1. It's not a duplicate item: do a normal btree delete. 1N/A * 2. It's a duplicate item: 1N/A * 2a: We delete an item from a page of duplicates, but there are 1N/A * more items on the page. 1N/A * 2b: We delete the last item from a page of duplicates, deleting 1N/A * the last duplicate. 1N/A * 2c: We delete the last item from a page of duplicates, but there 1N/A * is a previous page of duplicates. 1N/A * 2d: We delete the last item from a page of duplicates, but there 1N/A * is a following page of duplicates. 1N/A * 1: There's nothing further to do. 1N/A * 2a: There's nothing further to do. 1N/A * 2b: Do the normal btree delete instead of a duplicate delete, as 1N/A * that deletes both the duplicate chain and the parent page's 1N/A * 2c: There's nothing further to do. 1N/A * 2d: Delete the duplicate, and update the parent page's entry. 1N/A /* Delete the duplicate. */ 1N/A * 2a: h != NULL, h->pgno == pgno 1N/A * 2b: We don't reach this clause, as the above test 1N/A * 2c: h == NULL, prev_pgno != PGNO_INVALID 1N/A * 2d: h != NULL, next_pgno != PGNO_INVALID 1N/A * Test for 2a and 2c: if we didn't empty the current 1N/A * page or there was a previous page of duplicates, we 1N/A * don't need to touch the parent page. 1N/A * Release any page we're holding and its lock. 1N/A * If there is no subsequent page in the duplicate chain, then 1N/A * __db_drem will have put page "h" and set it to NULL. 1N/A /* Acquire the parent page and switch the index to its entry. */ 1N/A * Copy, delete, update, add-back the parent page's data entry. 1N/A * If the page is going to be emptied, delete it. To delete a leaf 1N/A * page we need a copy of a key from the page. We use the 0th page 1N/A * index since it's the last key that the page held. 1N/A * We malloc the page information instead of using the return key/data 1N/A * memory because we've already set them -- the reason we've already 1N/A * set them is because we're (potentially) about to do a reverse split, 1N/A * which would make our saved page information useless. 1N/A * The following operations to delete a page might deadlock. I think 1N/A * that's OK. The problem is if we're deleting an item because we're 1N/A * closing cursors because we've already deadlocked and want to call 1N/A * txn_abort(). If we fail due to deadlock, we leave a locked empty 1N/A * page in the tree, which won't be empty long because we're going to 1N/A * Do a normal btree delete. 1N/A * Delete the key item first, otherwise the duplicate checks in 1N/A * __bam_ditem() won't work! 1N/A /* Delete the page if it was emptied. */ 1N/A * It's possible for h to be NULL, as __db_drem may have 1N/A * been relinking pages by the time that it deadlocked. 1N/A * __bam_c_getstack -- 1N/A * Acquire a full stack for a cursor. 1N/A /* Get the page with the current item on it. */ 1N/A /* Get a copy of a key from the page. */ 1N/A /* Get a write-locked stack for that page. */ 1N/A /* We no longer need the key or the page. */