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