2N/A * Copyright (c) 1991, 1993, 1994 2N/A * The Regents of the University of California. All rights reserved. 2N/A * This code is derived from software contributed to Berkeley by 2N/A * Redistribution and use in source and binary forms, with or without 2N/A * modification, are permitted provided that the following conditions 2N/A * 1. Redistributions of source code must retain the above copyright 2N/A * notice, this list of conditions and the following disclaimer. 2N/A * 2. Redistributions in binary form must reproduce the above copyright 2N/A * notice, this list of conditions and the following disclaimer in the 2N/A * documentation and/or other materials provided with the distribution. 2N/A * 3. All advertising materials mentioning features or use of this software 2N/A * must display the following acknowledgement: 2N/A * This product includes software developed by the University of 2N/A * California, Berkeley and its contributors. 2N/A * 4. Neither the name of the University nor the names of its contributors 2N/A * may be used to endorse or promote products derived from this software 2N/A * without specific prior written permission. 2N/A * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2N/A * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2N/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2N/A * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2N/A * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2N/A * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2N/A * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2N/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2N/A * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2N/A * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2N/A * Page 0 of a btree file contains a copy of the meta-data. This page is also 2N/A * used as an out-of-band page, i.e. page pointers that point to nowhere point 2N/A * to page 0. Page 1 is the root of the btree. 2N/A#
define P_META 0
/* Tree metadata page number. */ 2N/A * There are five page layouts in the btree: btree internal pages (BINTERNAL), 2N/A * btree leaf pages (BLEAF), recno internal pages (RINTERNAL), recno leaf pages 2N/A * (RLEAF) and overflow pages. All five page types have a page header (PAGE). 2N/A * This implementation requires that values within structures NOT be padded. 2N/A * (ANSI C permits random padding.) If your compiler pads randomly you'll have 2N/A * to do some work to get this package to run. 2N/A/* First and next index. */ 2N/A * For pages other than overflow pages, there is an array of offsets into the 2N/A * rest of the page immediately following the page header. Each offset is to 2N/A * an item which is unique to the type of page. The h_lower offset is just 2N/A * past the last filled-in index. The h_upper offset is the first item on the 2N/A * page. Offsets are from the beginning of the page. 2N/A * If an item is too big to store on a single page, a flag is set and the item 2N/A * is a { page, size } pair such that the page is the first page of an overflow 2N/A * chain with size bytes of item. Overflow pages are simply bytes without any 2N/A * external structure. 2N/A * The page number and size fields in the items are db_pgno_t-aligned so they can 2N/A * be manipulated without copying. (This presumes that 32 bit items can be 2N/A * manipulated on this system.) 2N/A * For the btree internal pages, the item is a key. BINTERNALs are {key, pgno} 2N/A * pairs, such that the key compares less than or equal to all of the records 2N/A * on that page. For a tree without duplicate keys, an internal page with two 2N/A * consecutive keys, a and b, will have all records greater than or equal to a 2N/A * and less than b stored on the page associated with a. Duplicate keys are 2N/A * somewhat special and can cause duplicate internal and leaf page records and 2N/A * some minor modifications of the above rule. 2N/A/* Get the page's BINTERNAL structure at index indx. */ 2N/A/* Get the number of bytes in the entry. */ 2N/A/* Copy a BINTERNAL entry to the page. */ 2N/A * For the recno internal pages, the item is a page number with the number of 2N/A * keys found on that page and below. 2N/A/* Get the page's RINTERNAL structure at index indx. */ 2N/A/* Get the number of bytes in the entry. */ 2N/A/* Copy a RINTERAL entry to the page. */ 2N/A/* For the btree leaf pages, the item is a key and data pair. */ 2N/A/* Get the page's BLEAF structure at index indx. */ 2N/A/* Get the number of bytes in the entry. */ 2N/A/* Get the number of bytes in the user's key/data pair. */ 2N/A/* Copy a BLEAF entry to the page. */ 2N/A/* For the recno leaf pages, the item is a data entry. */ 2N/A/* Get the page's RLEAF structure at index indx. */ 2N/A/* Get the number of bytes in the entry. */ 2N/A/* Get the number of bytes from the user's data. */ 2N/A/* Copy a RLEAF entry to the page. */ 2N/A * A record in the tree is either a pointer to a page and an index in the page 2N/A * or a page number and an index. These structures are used as a cursor, stack 2N/A * entry and search returns as well as to pass records to other routines. 2N/A * One comment about searches. Internal page searches must find the largest 2N/A * record less than key in the tree so that descents work. Leaf page searches 2N/A * must find the smallest record greater than key so that the returned index 2N/A * is the record's correct position for insertion. 2N/A * About cursors. The cursor (and the page that contained the key/data pair 2N/A * that it referenced) can be deleted, which makes things a bit tricky. If 2N/A * there are no duplicates of the cursor key in the tree (i.e. B_NODUPS is set 2N/A * or there simply aren't any duplicates of the key) we copy the key that it 2N/A * referenced when it's deleted, and reacquire a new cursor key if the cursor 2N/A * is used again. If there are duplicates keys, we move to the next/previous 2N/A * key, and set a flag so that we know what happened. NOTE: if duplicate (to 2N/A * the cursor) keys are added to the tree during this process, it is undefined 2N/A * if they will be returned or not in a cursor scan. 2N/A * The flags determine the possible states of the cursor: 2N/A * CURS_INIT The cursor references *something*. 2N/A * CURS_ACQUIRE The cursor was deleted, and a key has been saved so that 2N/A * we can reacquire the right position in the tree. 2N/A * CURS_AFTER, CURS_BEFORE 2N/A * The cursor was deleted, and now references a key/data pair 2N/A * that has not yet been returned, either before or after the 2N/A * This structure is broken out so that we can eventually offer multiple 2N/A * cursors as part of the DB interface. 2N/A DBT key;
/* B: Saved key, or key.data == NULL. */ 2N/A * The metadata of the tree. The nrecs field is used only by the RECNO code. 2N/A * This is because the btree doesn't really need it and it requires that every 2N/A * put or delete call modify the metadata. 2N/A /* B: key comparison function */ 2N/A /* B: prefix comparison function */ 2N/A /* R: recno input function */ 2N/A * B_NODUPS and R_RECNO are stored on disk, and may not be changed. 2N/A#
define B_NODUPS 0x00020 /* no duplicate keys permitted */ 2N/A#
define R_EOF 0x00100 /* end of input file reached. */