aboutsummaryrefslogtreecommitdiff
path: root/db2/include/btree.h
diff options
context:
space:
mode:
Diffstat (limited to 'db2/include/btree.h')
-rw-r--r--db2/include/btree.h312
1 files changed, 312 insertions, 0 deletions
diff --git a/db2/include/btree.h b/db2/include/btree.h
new file mode 100644
index 0000000000..5cf4224ae6
--- /dev/null
+++ b/db2/include/btree.h
@@ -0,0 +1,312 @@
+/*-
+ * See the file LICENSE for redistribution information.
+ *
+ * Copyright (c) 1996, 1997
+ * 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
+ * documentation and/or other materials provided with the distribution.
+ * 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.16 (Sleepycat) 8/24/97
+ */
+
+/* Forward structure declarations. */
+struct __btree; typedef struct __btree BTREE;
+struct __cursor; typedef struct __cursor CURSOR;
+struct __epg; typedef struct __epg EPG;
+struct __rcursor; typedef struct __rcursor RCURSOR;
+struct __recno; typedef struct __recno RECNO;
+
+#undef DEFMINKEYPAGE /* Minimum keys per page */
+#define DEFMINKEYPAGE (2)
+
+#undef ISINTERNAL /* If an internal page. */
+#define ISINTERNAL(p) (TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO)
+#undef ISLEAF /* If a leaf page. */
+#define ISLEAF(p) (TYPE(p) == P_LBTREE || TYPE(p) == P_LRECNO)
+
+/* Allocate and discard thread structures. */
+#define GETHANDLE(dbp, set_txn, dbpp, ret) { \
+ if (F_ISSET(dbp, DB_AM_THREAD)) { \
+ if ((ret = __db_gethandle(dbp, __bam_bdup, dbpp)) != 0) \
+ return (ret); \
+ } else \
+ *dbpp = dbp; \
+ *dbpp->txn = set_txn; \
+}
+#define PUTHANDLE(dbp) { \
+ dbp->txn = NULL; \
+ if (F_ISSET(dbp, DB_AM_THREAD)) \
+ __db_puthandle(dbp); \
+}
+
+/*
+ * 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.
+ */
+#define __BT_LPUT(dbp, lock) \
+ (F_ISSET((dbp), DB_AM_LOCKING) ? \
+ lock_put((dbp)->dbenv->lk_info, lock) : 0)
+#define __BT_TLPUT(dbp, lock) \
+ (F_ISSET((dbp), DB_AM_LOCKING) && (dbp)->txn == NULL ? \
+ lock_put((dbp)->dbenv->lk_info, lock) : 0)
+
+/*
+ * Flags to __bt_search() and __rec_search().
+ *
+ * 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.
+ */
+#define S_READ 0x0001 /* Read locks. */
+#define S_WRITE 0x0002 /* Write locks. */
+
+#define S_APPEND 0x0040 /* Append to the tree. */
+#define S_DELNO 0x0080 /* Don't return deleted items. */
+#define S_DUPFIRST 0x0100 /* Return first duplicate. */
+#define S_DUPLAST 0x0200 /* Return last duplicate. */
+#define S_EXACT 0x0400 /* Exact items only. */
+#define S_PARENT 0x0800 /* Lock page pair. */
+
+#define S_DELETE (S_WRITE | S_DUPFIRST | S_DELNO | S_EXACT)
+#define S_FIND (S_READ | S_DUPFIRST | S_DELNO)
+#define S_INSERT (S_WRITE | S_DUPLAST)
+#define S_KEYFIRST (S_WRITE | S_DUPFIRST)
+#define S_KEYLAST (S_WRITE | S_DUPLAST)
+#define S_WRPAIR (S_WRITE | S_DUPLAST | S_PARENT)
+
+/*
+ * Flags to __bam_iitem().
+ */
+#define BI_NEWKEY 0x01 /* New key. */
+#define BI_DELETED 0x02 /* Key/data pair only placeholder. */
+
+/*
+ * 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 {
+ PAGE *page; /* The page. */
+ db_indx_t indx; /* The index on the page. */
+ DB_LOCK lock; /* The page's lock. */
+};
+
+/*
+ * Btree cursor.
+ *
+ * Arguments passed to __bam_ca_replace().
+ */
+typedef enum {
+ REPLACE_SETUP,
+ REPLACE_SUCCESS,
+ REPLACE_FAILED
+} ca_replace_arg;
+struct __cursor {
+ DBC *dbc; /* Enclosing DBC. */
+
+ PAGE *page; /* Cursor page. */
+
+ db_pgno_t pgno; /* Page. */
+ db_indx_t indx; /* Page item ref'd by the cursor. */
+
+ db_pgno_t dpgno; /* Duplicate page. */
+ db_indx_t dindx; /* Page item ref'd by the cursor. */
+
+ DB_LOCK lock; /* Cursor read lock. */
+ db_lockmode_t mode; /* Lock mode. */
+
+ /*
+ * If a cursor record is deleted, the key/data pair has to remain on
+ * the page so that subsequent inserts/deletes don't interrupt the
+ * cursor progression through the file. This results in interesting
+ * cases when "standard" operations, e.g., dbp->put() are done in the
+ * context of "deleted" cursors.
+ *
+ * C_DELETED -- The item referenced by the cursor has been "deleted"
+ * but not physically removed from the page.
+ * C_REPLACE -- The "deleted" item referenced by a cursor has been
+ * replaced by a dbp->put(), so the cursor is no longer
+ * responsible for physical removal from the page.
+ * C_REPLACE_SETUP --
+ * We are about to overwrite a "deleted" item, flag any
+ * cursors referencing it for transition to C_REPLACE
+ * state.
+ */
+#define C_DELETED 0x0001
+#define C_REPLACE 0x0002
+#define C_REPLACE_SETUP 0x0004
+ u_int32_t flags;
+};
+
+/*
+ * Recno cursor.
+ *
+ * Arguments passed to __ram_ca().
+ */
+typedef enum {
+ CA_DELETE,
+ CA_IAFTER,
+ CA_IBEFORE
+} ca_recno_arg;
+struct __rcursor {
+ DBC *dbc; /* Enclosing DBC. */
+
+ db_recno_t recno; /* Current record number. */
+
+ /*
+ * Cursors referencing "deleted" records are positioned between
+ * two records, and so must be specially adjusted until they are
+ * moved.
+ */
+#define CR_DELETED 0x0001 /* Record deleted. */
+ u_int32_t flags;
+};
+
+/*
+ * 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
+ * do inserts/deletes, however. Grow the stack as necessary.
+ */
+#undef BT_STK_CLR
+#define BT_STK_CLR(t) \
+ ((t)->bt_csp = (t)->bt_sp)
+
+#undef BT_STK_ENTER
+#define BT_STK_ENTER(t, pagep, page_indx, lock, ret) do { \
+ if ((ret = \
+ (t)->bt_csp == (t)->bt_esp ? __bam_stkgrow(t) : 0) == 0) { \
+ (t)->bt_csp->page = pagep; \
+ (t)->bt_csp->indx = page_indx; \
+ (t)->bt_csp->lock = lock; \
+ } \
+} while (0)
+
+#undef BT_STK_PUSH
+#define BT_STK_PUSH(t, pagep, page_indx, lock, ret) do { \
+ BT_STK_ENTER(t, pagep, page_indx, lock, ret); \
+ ++(t)->bt_csp; \
+} while (0)
+
+#undef BT_STK_POP
+#define BT_STK_POP(t) \
+ ((t)->bt_csp == (t)->bt_stack ? NULL : --(t)->bt_csp)
+
+/*
+ * 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.
+ */
+#undef RECNO_OOB
+#define RECNO_OOB 0 /* Illegal record number. */
+
+struct __recno {
+ int re_delim; /* Variable-length delimiting byte. */
+ int re_pad; /* Fixed-length padding byte. */
+ u_int32_t re_len; /* Length for fixed-length records. */
+
+ char *re_source; /* Source file name. */
+ int re_fd; /* Source file descriptor */
+ db_recno_t re_last; /* Last record number read. */
+ void *re_cmap; /* Current point in mapped space. */
+ void *re_smap; /* Start of mapped space. */
+ void *re_emap; /* End of mapped space. */
+ size_t re_msize; /* Size of mapped region. */
+ /* Recno input function. */
+ int (*re_irec) __P((DB *, db_recno_t));
+
+#define RECNO_EOF 0x0001 /* EOF on backing source file. */
+#define RECNO_MODIFIED 0x0002 /* Tree was modified. */
+ u_int32_t flags;
+};
+
+/*
+ * The in-memory btree data structure.
+ */
+struct __btree {
+/*
+ * These fields are per-thread and are initialized when the BTREE structure
+ * is created.
+ */
+ db_pgno_t bt_lpgno; /* Last insert location. */
+
+ DBT bt_rkey; /* Returned key. */
+ DBT bt_rdata; /* Returned data. */
+
+ EPG *bt_sp; /* Stack pointer. */
+ EPG *bt_csp; /* Current stack entry. */
+ EPG *bt_esp; /* End stack pointer. */
+ EPG bt_stack[5];
+
+ RECNO *bt_recno; /* Private recno structure. */
+
+ DB_BTREE_LSTAT lstat; /* Btree local statistics. */
+
+/*
+ * These fields are copied from the original BTREE structure and never
+ * change.
+ */
+ db_indx_t bt_maxkey; /* Maximum keys per page. */
+ db_indx_t bt_minkey; /* Minimum keys per page. */
+
+ int (*bt_compare) /* Comparison function. */
+ __P((const DBT *, const DBT *));
+ size_t(*bt_prefix) /* Prefix function. */
+ __P((const DBT *, const DBT *));
+
+ db_indx_t bt_ovflsize; /* Maximum key/data on-page size. */
+};
+
+#include "btree_auto.h"
+#include "btree_ext.h"
+#include "db_am.h"
+#include "common_ext.h"