btree.h revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 1996, 1997, 1998
* Sleepycat Software. All rights reserved.
*/
/*
* Copyright (c) 1990, 1993, 1994, 1995, 1996
* Keith Bostic. All rights reserved.
*/
/*
* Copyright (c) 1990, 1993, 1994, 1995
* 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 10.26 (Sleepycat) 12/16/98
*/
/* Forward structure declarations. */
#define DEFMINKEYPAGE (2)
/*
* If doing transactions we have to hold the locks associated with a data item
* from a page for the entire transaction. However, we don't have to hold the
* locks associated with walking the tree. Distinguish between the two so that
* we don't tie up the internal pages of the tree longer than necessary.
*/
/*
* Flags to __bam_search() and __bam_rsearch().
*
* Note, 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.
*
* The flags parameter to the search routines describes three aspects of the
* search: the type of locking required (including if we're locking a pair of
* pages), the item to return in the presence of duplicates and whether or not
* to return deleted entries. To simplify both the mnemonic representation
* and the code that checks for various cases, we construct a set of bitmasks.
*/
* or keylast operations), or a split
* on behalf of an insert, it's okay to
* return an entry one past end-of-page.
*/
/*
* Flags to __bam_iitem().
*/
/*
* Various routines pass around page references. A page reference can be a
* pointer to the page or a page number; for either, an indx can designate
* an item on the page.
*/
struct __epg {
};
/*
* We maintain a stack of the pages that we're locking in the tree. Btree's
* (currently) only save two levels of the tree at a time, so the default
* stack is always large enough. Recno trees have to lock the entire tree to
*/
#define BT_STK_CLR(c) \
if ((ret = \
} \
} while (0)
++(c)->csp; \
} while (0)
#define BT_STK_POP(c) \
/*
* Arguments passed to __bam_ca_replace().
*/
typedef enum {
/* Arguments passed to __ram_ca(). */
typedef enum {
} ca_recno_arg;
#define RECNO_OOB 0 /* Illegal record number. */
struct __cursor {
/* Per-thread information: btree private. */
/* Per-thread information: recno private. */
/*
* Btree:
* We set a flag in the cursor structure if the underlying object has
* been deleted. It's not strictly necessary, we could get the same
* information by looking at the page itself.
*
* Recno:
* When renumbering recno databases during deletes, cursors referencing
* "deleted" records end up positioned between two records, and so must
* be specially adjusted on the next operation.
*/
};
/*
* The in-memory recno data structure.
*
* !!!
* These fields are ignored as far as multi-threading is concerned. There
* are no transaction semantics associated with backing files, nor is there
* any thread protection.
*/
struct __recno {
int re_delim; /* Variable-length delimiting byte. */
int re_pad; /* Fixed-length padding byte. */
char *re_source; /* Source file name. */
int re_fd; /* Source file descriptor */
void *re_cmap; /* Current point in mapped space. */
void *re_smap; /* Start of mapped space. */
void *re_emap; /* End of mapped space. */
/* Recno input function. */
};
/*
* The in-memory, per-tree btree data structure.
*/
struct __btree {
int (*bt_compare) /* Comparison function. */
};
#include "btree_auto.h"
#include "btree_ext.h"
#include "db_am.h"
#include "common_ext.h"