head 1.14; branch ; access ; symbols Version_2_1:1.14 Version_2:1.11 C_Demo_1:1.5; locks ; strict; comment @ * @; 1.14 date 91.03.03.00.36.16; author mao; state Exp; branches ; next 1.13; 1.13 date 90.08.18.00.39.49; author cimarron; state Exp; branches ; next 1.12; 1.12 date 90.08.17.08.50.38; author cimarron; state Exp; branches ; next 1.11; 1.11 date 90.06.08.15.51.47; author cimarron; state Version_2; branches ; next 1.10; 1.10 date 90.04.02.20.58.29; author mao; state Exp; branches ; next 1.9; 1.9 date 90.03.12.13.53.17; author mao; state Exp; branches ; next 1.8; 1.8 date 90.02.08.14.38.39; author hong; state Exp; branches ; next 1.7; 1.7 date 89.11.13.13.07.42; author cimarron; state Exp; branches ; next 1.6; 1.6 date 89.09.28.18.24.31; author mao; state Exp; branches ; next 1.5; 1.5 date 89.09.05.17.04.00; author mao; state C_Demo_1; branches ; next 1.4; 1.4 date 89.07.20.12.27.31; author mao; state Exp; branches ; next 1.3; 1.3 date 89.04.12.19.52.56; author dillon; state Exp; branches ; next 1.2; 1.2 date 89.03.22.17.32.22; author muir; state Stab; branches ; next 1.1; 1.1 date 89.01.17.05.53.48; author cimarron; state Exp; branches ; next ; desc @@ 1.14 log @get arbitrary-length index keys working @ text @/* ---------------------------------------------------------------- * btree.h -- * B-tree definitions. * * Note: * Based on Philip L. Lehman and S. Bing Yao's paper, "Efficient * Locking for Concurrent Operations on B-trees," ACM Transactions * on Database Systems, v.6, n.4, Dec. '81, pp650-670. * * Identification: * $Header: RCS/btree.h,v 1.13 90/08/18 00:39:49 cimarron Exp Locker: mao $ * ---------------------------------------------------------------- */ #ifndef BTreeIncluded /* Include this file only once. */ #define BTreeIncluded 1 /* #define DebuggingBtreeStuff 1 */ /* ---------------------------------------------------------------- * btree access method include files * ---------------------------------------------------------------- */ #include "tmp/postgres.h" #include "access/attnum.h" #include "access/attval.h" #include "access/ftup.h" #include "access/genam.h" #include "access/heapam.h" #include "access/ibit.h" #include "access/imark.h" #include "access/iqual.h" #include "access/isop.h" #include "access/istrat.h" #include "access/itup.h" #include "access/relscan.h" #include "access/sdir.h" #include "access/skey.h" #include "access/tqual.h" #include "rules/rlock.h" #include "storage/block.h" #include "storage/buf.h" #include "storage/bufmgr.h" #include "storage/bufpage.h" #include "storage/form.h" #include "storage/item.h" #include "storage/itemid.h" #include "storage/itemptr.h" #include "storage/page.h" #include "storage/pagenum.h" #include "storage/part.h" #include "utils/memutils.h" #include "tmp/miscadmin.h" #include "utils/log.h" #include "utils/rel.h" /* ---------------- * dependencies from obsoleted misc.h * ---------------- */ #define forever for (;;) #define FUNCTION /* empty macro used for cross referencing */ #define OFFSET(type,mem) ((int) &(((type *) NULL)->mem)) /* ---------------------------------------------------------------- * B-Tree constants * ---------------------------------------------------------------- */ #define BTreeRootBlockNumber ((BlockNumber) 0) #define BTreeRootPageNumber ((PageNumber) 0) #define FirstOffsetNumber 1 #define BTreeDefaultPageSize (BLCKSZ) extern Name BTreeAccessMethodName; extern ItemPointer BTreeRootItemPointer; extern PagePartition BTreeDefaultPagePartition; #define BTreeNumberOfStrategies 5 #define BTreeLessThanStrategyNumber ((StrategyNumber) 1) #define BTreeLessThanOrEqualStrategyNumber ((StrategyNumber) 2) #define BTreeEqualStrategyNumber ((StrategyNumber) 3) #define BTreeGreaterThanOrEqualStrategyNumber ((StrategyNumber) 4) #define BTreeGreaterThanStrategyNumber ((StrategyNumber) 5) #define EmptyPageOffsetIndex ((OffsetIndex) -1) /* * During insertion, we need to know whether we should search for the * first (last) tuple matching a given key, or whether it's okay just * to find any tuple. We need to find the bounding tuple when we are * inserting rule locks. */ #define NO_BOUND ((int8) 0) #define LEFT_BOUND ((int8) 1) #define RIGHT_BOUND ((int8) 2) /* ---------------------------------------------------------------- * BTreeHeaders form the "link" information in the btree * nodes. They are stored in the "Special" space on a page. * ---------------------------------------------------------------- */ /* ---------------- * btree header structure definitions * ---------------- * Note: * It might be better to treat the first page of a block * specially by adding a bitmap of the used pages!?! * ---------------- */ /* ---------------- * BTreeHeaderData * ---------------- */ typedef bits8 BTreeHeaderTypeData; #define BTREE_PAGE_IS_FREE ((BTreeHeaderTypeData) 0) #define BTREE_INTERNAL_HEADER ((BTreeHeaderTypeData) 1<<0) #define BTREE_LEAF_HEADER ((BTreeHeaderTypeData) 1<<1) #define BTREE_PAGE_HAS_RULES ((BTreeHeaderTypeData) 1<<2) typedef struct BTreeHeaderData { BTreeHeaderTypeData type; ItemPointerData linkData; ItemPointerData prevData; } BTreeHeaderData; typedef BTreeHeaderData *BTreeHeader; #define BTreeHeaderSize sizeof(BTreeHeaderData) /* ---------------------------------------------------------------- * BTreeNodes are the in-memory representations of * the nodes in the btree. They reference pages on disk * which contain the actual btree information. * ---------------------------------------------------------------- */ /* ---------------- * BTreeNodeData -- * B-tree node information. * * Note: * blockNumber and partition are computable from Buffer. * ---------------- */ typedef struct BTreeNodeData { Relation relation; Buffer buffer; BlockNumber blockNumber; PageNumber pageNumber; PagePartition partition; BTreeHeaderTypeData type; } BTreeNodeData; typedef BTreeNodeData *BTreeNode; #define InvalidBTreeNode NULL /* ---------------------------------------------------------------- * BTreeItemPointerData * ---------------------------------------------------------------- */ typedef struct BTreeItemPointerData { BTreeNode node; OffsetNumber offsetNumber; } BTreeItemPointerData; typedef struct BTreeItemPointerData *BTreeItemPointer; /* ---------------------------------------------------------------- * BTreeItems form the (key, ptr) tuples stored on the * page. * ---------------------------------------------------------------- */ /* ---------------- * BTreeItemFlags are used to classify btree items * * RLOCK_L and RLOCK_R are used to identify rule lock marker tuples * in the index. L is the left-hand delimiter (left to right ordering * in the index), and R is the right-hand. L and R locks ALWAYS come * in pairs. No other type of rule lock appears in the index. * ---------------- */ typedef bits16 BTreeItemFlags; #define BTREE_ITEM_IS_LEAF ((BTreeItemFlags) (1 << 0)) #define BTREE_ITEM_IS_HIGHKEY ((BTreeItemFlags) (1 << 1)) #define BTREE_ITEM_IS_RLOCK_L ((BTreeItemFlags) (1 << 2)) #define BTREE_ITEM_IS_RLOCK_R ((BTreeItemFlags) (1 << 3)) #define BTREE_ITEM_IS_RLOCK (BTREE_ITEM_IS_RLOCK_L|BTREE_ITEM_IS_RLOCK_R) /* ---------------- * BTreeItem -- * Either a pointer to an internal or leaf B-tree node item. * ---------------- */ typedef struct BTreeItemHeaderData { BTreeItemFlags flags; IndexTupleData ituple; } BTreeItemHeaderData; typedef struct BTreeItemData { BTreeItemHeaderData header; FormData form; /* VARIABLE LENGTH STRUCTURE */ } BTreeItemData; typedef BTreeItemData *BTreeItem; /* ---------------- * BTreeRuleLock -- * A marker tuple in the btree index for starting or ending a * rule lock. * * Rule locks that use the index always have some qual. This qual * is a simple (func_oid, key) pair. When the access method is * inserting new tuples, or placing rule lock tuples, it uses the * func_oid to call a function comparing the "current" key (whatever * that is, at the time) with the key stored in the rule qual. It * then places the new tuple appropriately based on the result. * * Since the key value to use in calling the function manager is * already stored in the BTreeItemData, we don't bother with it here. * ---------------- */ typedef struct BTreeRuleLockData { BTreeItemHeaderData header; ObjectId func; FormData form; /* VARIABLE LENGTH STRUCTURE */ } BTreeRuleLockData; typedef BTreeRuleLockData *BTreeRuleLock; /* ---------------------------------------------------------------- * BTreeInsertData, BTreeSearchKeys and * ItemPointerElements are internal structures used during * searching for and insertion of btree items. * ---------------------------------------------------------------- */ /* ---------------- * BTreeInsertData definition * ---------------- */ #define BTREE_NO_FLAGS ((int8) 0) #define BTREE_INTERNAL_INSERT_DATA ((int8) 1<<0) #define BTREE_LEAF_INSERT_DATA ((int8) 1<<1) #define BTREE_RLOCK_L_INSERT_DATA ((int8) 1<<2) #define BTREE_RLOCK_R_INSERT_DATA ((int8) 1<<3) #define BTREE_RLOCK_INSERT_DATA (BTREE_RLOCK_L_INSERT_DATA|BTREE_RLOCK_R_INSERT_DATA) typedef struct BTreeInsertDataData { int8 type; /* internal or leaf */ /* data necessary to form both internal and leaf btree items */ IndexTuple indexTuple; Size size; /* data specific to leaf insertions */ ItemPointerData leafPointerData; /* return */ double leafOffset; /* return */ } BTreeInsertDataData; typedef BTreeInsertDataData *BTreeInsertData; /* ---------------- * BTreeSearchKey definition * * Note: * originalInsertData is a redundant pointer to the initial * insertData placed into the key. Because insertData may change * in the case of node splitting, we keep a spare pointer to * the initial insertData. This is necessary because information * is returned in insertData->pointer which is used by the top * level BTreeAMInsert and BTreeAMGetTuple routines. * ---------------- */ typedef struct BTreeSearchKeyData { ItemPointer pointer; /* position to start from */ Relation relation; /* index relation */ ScanKeySize scanKeySize; /* number of atts in scan key */ ScanKey scanKey; /* scan key for scans */ BTreeInsertData insertData; /* data to insert into a node */ BTreeInsertData originalInsertData; /* data to insert into leaf node */ ScanDirection direction; /* forward or reverse scan */ bool wasSuccessfulSearch; /* return: was search successful? */ bool isForInsertion; /* is this an insert or a scan? */ bool isStartingAtEndpoint; /* where should our scan start? */ } BTreeSearchKeyData; typedef BTreeSearchKeyData *BTreeSearchKey; /* ---------------- * ItemPointerElement definition * * ItemPointerElements are used by the btree item pointer * stack algorithm to implement more efficient locking. * ---------------- */ typedef struct ItemPointerElementData { ItemPointer pointer; struct ItemPointerElementData *next; } ItemPointerElementData; typedef ItemPointerElementData *ItemPointerElement; typedef ItemPointerElement *ItemPointerStack; /* ---------------------------------------------------------------- * extern definitions * ---------------------------------------------------------------- */ #include "btree-externs.h" #endif BTreeIncluded @ 1.13 log @eliminated less significant .h files @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.12 90/08/17 08:50:38 cimarron Exp Locker: cimarron $ d212 1 a212 1 * BTreeItem -- @ 1.12 log @added pathnames to #include statements @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.11 90/06/08 15:51:47 cimarron Version_2 Locker: cimarron $ d55 2 a56 6 #include "tmp/align.h" #include "tmp/clib.h" #include "tmp/datum.h" #include "tmp/globals.h" #include "tmp/name.h" #include "tmp/regproc.h" @ 1.11 log @removed dependencies on misc.h which is being obsoleted. @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.10 90/04/02 20:58:29 mao Exp $ d25 1 a25 3 #ifndef C_H #include "c.h" #endif d27 36 a62 108 #ifndef ALIGN_H #include "align.h" #endif #ifndef ATTNUM_H #include "attnum.h" #endif #ifndef ATTVAL_H #include "attval.h" #endif #ifndef BLOCK_H #include "block.h" #endif #ifndef BUF_H #include "buf.h" #endif #ifndef BUFMGR_H #include "bufmgr.h" #endif #ifndef BUFPAGE_H #include "bufpage.h" #endif #ifndef CLIB_H #include "clib.h" #endif #ifndef DATUM_H #include "datum.h" #endif #ifndef FORM_H #include "form.h" #endif #ifndef FTUP_H #include "ftup.h" #endif #ifndef GENAM_H #include "genam.h" #endif #ifndef GLOBALS_H #include "globals.h" #endif #ifndef HEAPAM_H #include "heapam.h" #endif #ifndef IBIT_H #include "ibit.h" #endif #ifndef IMARK_H #include "imark.h" #endif #ifndef IQUAL_H #include "iqual.h" #endif #ifndef ISOP_H #include "isop.h" #endif #ifndef ISTRAT_H #include "istrat.h" #endif #ifndef ITEM_H #include "item.h" #endif #ifndef ITEMID_H #include "itemid.h" #endif #ifndef ITEMPTR_H #include "itemptr.h" #endif #ifndef ITUP_H #include "itup.h" #endif #ifndef LOG_H #include "log.h" #endif #ifndef NAME_H #include "name.h" #endif #ifndef PAGE_H #include "page.h" #endif #ifndef PAGENUM_H #include "pagenum.h" #endif #ifndef PART_H #include "part.h" #endif #ifndef POSTGRES_H #include "postgres.h" #endif #ifndef REGPROC_H #include "regproc.h" #endif #ifndef REL_H #include "rel.h" #endif #ifndef RELSCAN_H #include "relscan.h" #endif #ifndef RLOCK_H #include "rlock.h" #endif #ifndef SDIR_H #include "sdir.h" #endif #ifndef SKEY_H #include "skey.h" #endif #ifndef TQUAL_H #include "tqual.h" #endif @ 1.10 log @rule locks work on single pages @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.9 90/03/12 13:53:17 mao Exp $ a100 3 #ifndef MISC_H #include "misc.h" #endif d137 10 @ 1.9 log @checkin for first integration @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.8 90/02/08 14:38:39 hong Exp Locker: mao $ d280 1 d344 1 @ 1.8 log @fix for hermes to reduce levels of #include nesting. @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.7 89/11/13 13:07:42 cimarron Exp $ a145 8 /* ---------------- * BTREEISUNORDERED -- * Set iff the B-tree should be treated as an unordered index. * ---------------- */ #define BTREEISUNORDERED 0 d166 11 d200 3 a202 2 #define BTREE_INTERNAL_HEADER ((BTreeHeaderTypeData) 1) #define BTREE_LEAF_HEADER ((BTreeHeaderTypeData) 2) d266 5 d278 2 d300 16 d317 6 d324 1 a325 2 d327 1 a327 1 * BTreeData, BTreeInsertData, BTreeSearchKeys and a333 12 * BTreeData definition * ---------------- */ typedef struct BTreeDataData { ItemPointer pointer; RuleLock lock; } BTreeDataData; typedef BTreeDataData *BTreeData; /* ---------------- d338 5 a342 2 #define BTREE_INTERNAL_INSERT_DATA 1 #define BTREE_LEAF_INSERT_DATA 2 a352 1 RuleLock leafLock; /* return */ /* unused */ a411 1 @ 1.7 log @added btree debugging stuff and moved NDBUFS to globals.h @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.6 89/09/28 18:24:31 mao Exp $ d29 1 d31 2 d34 2 d37 2 d40 2 d43 2 d46 2 d49 2 d52 2 d55 2 d58 2 d61 2 d64 2 d67 2 d70 2 d73 2 d76 2 d79 2 d82 2 d85 2 d88 2 d91 2 d94 2 d97 2 d100 2 d103 2 d106 2 d109 2 d112 2 d115 2 d118 2 d121 2 d124 2 d127 2 d130 2 d133 2 d136 2 d139 1 @ 1.6 log @include tqual.h for NowTimeQual @ text @d11 1 a11 1 * $Header: RCS/btree.h,v 1.5 89/09/05 17:04:00 mao C_Demo_1 Locker: mao $ d41 1 @ 1.5 log @Working version of C-only demo @ text @d11 1 a11 1 * $Header: /usr6/postgres/mao/postgres/src/lib/H/RCS/btree.h,v 1.4 89/07/20 12:27:31 mao Exp $ d64 1 @ 1.4 log @turn off debugging. @ text @d11 1 a11 1 * $Header: btree.h,v 1.3 89/04/12 19:52:56 mao Locked $ @ 1.3 log @c.h @ text @d11 1 a11 1 * $Header: /usr6/postgres/dillon/ptree/src/lib/H/RCS/btree.h,v 1.2 89/03/22 17:32:22 muir Stab $ d18 1 a18 1 #define DebuggingBtreeStuff 1 @ 1.2 log @copyright removal @ text @d11 1 a11 1 * $Header: /usr6/postgres/muir/postgres/src/lib/H/RCS/btree.h,v 1.1 89/01/17 05:53:48 cimarron Exp $ d25 1 d27 1 @ 1.1 log @Initial revision @ text @a0 27 ; /* ; * ; * POSTGRES Data Base Management System ; * ; * Copyright (c) 1988 Regents of the University of California ; * ; * Permission to use, copy, modify, and distribute this software and its ; * documentation for educational, research, and non-profit purposes and ; * without fee is hereby granted, provided that the above copyright ; * notice appear in all copies and that both that copyright notice and ; * this permission notice appear in supporting documentation, and that ; * the name of the University of California not be used in advertising ; * or publicity pertaining to distribution of the software without ; * specific, written prior permission. Permission to incorporate this ; * software into commercial products can be obtained from the Campus ; * Software Office, 295 Evans Hall, University of California, Berkeley, ; * Ca., 94720 provided only that the the requestor give the University ; * of California a free licence to any derived software for educational ; * and research purposes. The University of California makes no ; * representations about the suitability of this software for any ; * purpose. It is provided "as is" without express or implied warranty. ; * ; */ d11 1 a11 1 * $Header: btree.h,v 1.1 88/11/11 16:36:54 postgres Exp $ @