home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / lib / H / access / btree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  10.0 KB  |  343 lines
  1. /* ----------------------------------------------------------------
  2.  * btree.h --
  3.  *    B-tree definitions.
  4.  *
  5.  * Note:
  6.  *    Based on Philip L. Lehman and S. Bing Yao's paper, "Efficient
  7.  *    Locking for Concurrent Operations on B-trees," ACM Transactions
  8.  *    on Database Systems, v.6, n.4, Dec. '81, pp650-670.
  9.  *
  10.  * Identification:
  11.  *    $Header: /private/postgres/src/lib/H/access/RCS/btree.h,v 1.14 1991/03/03 00:36:16 mao Exp $
  12.  * ----------------------------------------------------------------
  13.  */
  14.  
  15. #ifndef    BTreeIncluded    /* Include this file only once. */
  16. #define BTreeIncluded    1
  17.  
  18. /* #define DebuggingBtreeStuff 1 */
  19.  
  20. /* ----------------------------------------------------------------
  21.  *    btree access method include files
  22.  * ----------------------------------------------------------------
  23.  */
  24.  
  25. #include "tmp/postgres.h"
  26.  
  27. #include "access/attnum.h"
  28. #include "access/attval.h"
  29. #include "access/ftup.h"
  30. #include "access/genam.h"
  31. #include "access/heapam.h"
  32. #include "access/ibit.h"
  33. #include "access/imark.h"
  34. #include "access/iqual.h"
  35. #include "access/isop.h"
  36. #include "access/istrat.h"
  37. #include "access/itup.h"
  38. #include "access/relscan.h"
  39. #include "access/sdir.h"
  40. #include "access/skey.h"
  41. #include "access/tqual.h"
  42.  
  43. #include "rules/rlock.h"
  44. #include "storage/block.h"
  45. #include "storage/buf.h"
  46. #include "storage/bufmgr.h"
  47. #include "storage/bufpage.h"
  48. #include "storage/form.h"
  49. #include "storage/item.h"
  50. #include "storage/itemid.h"
  51. #include "storage/itemptr.h"
  52. #include "storage/page.h"
  53. #include "storage/pagenum.h"
  54. #include "storage/part.h"
  55. #include "utils/memutils.h"
  56. #include "tmp/miscadmin.h"
  57. #include "utils/log.h"
  58. #include "utils/rel.h"
  59.  
  60. /* ----------------
  61.  *   dependencies from obsoleted misc.h
  62.  * ----------------
  63.  */
  64. #define forever for (;;)
  65.  
  66. #define FUNCTION  /* empty macro used for cross referencing */
  67.  
  68. #define OFFSET(type,mem)    ((int) &(((type *) NULL)->mem))
  69.  
  70. /* ----------------------------------------------------------------
  71.  *    B-Tree constants
  72.  * ----------------------------------------------------------------
  73.  */
  74.  
  75. #define BTreeRootBlockNumber    ((BlockNumber) 0)
  76. #define BTreeRootPageNumber    ((PageNumber) 0)
  77. #define FirstOffsetNumber    1
  78.  
  79. #define BTreeDefaultPageSize    (BLCKSZ)
  80.  
  81. extern  Name            BTreeAccessMethodName;
  82. extern    ItemPointer        BTreeRootItemPointer;
  83. extern    PagePartition        BTreeDefaultPagePartition;
  84.  
  85. #define BTreeNumberOfStrategies            5
  86.  
  87. #define BTreeLessThanStrategyNumber        ((StrategyNumber) 1)
  88. #define BTreeLessThanOrEqualStrategyNumber    ((StrategyNumber) 2)
  89. #define BTreeEqualStrategyNumber        ((StrategyNumber) 3)
  90. #define BTreeGreaterThanOrEqualStrategyNumber    ((StrategyNumber) 4)
  91. #define BTreeGreaterThanStrategyNumber        ((StrategyNumber) 5)
  92.  
  93. #define EmptyPageOffsetIndex    ((OffsetIndex) -1)
  94.  
  95. /*
  96.  *  During insertion, we need to know whether we should search for the
  97.  *  first (last) tuple matching a given key, or whether it's okay just
  98.  *  to find any tuple.  We need to find the bounding tuple when we are
  99.  *  inserting rule locks.
  100.  */
  101.  
  102. #define NO_BOUND    ((int8) 0)
  103. #define LEFT_BOUND    ((int8) 1)
  104. #define RIGHT_BOUND    ((int8) 2)
  105.  
  106. /* ----------------------------------------------------------------
  107.  *    BTreeHeaders form the "link" information in the btree
  108.  *    nodes. They are stored in the "Special" space on a page.
  109.  * ----------------------------------------------------------------
  110.  */
  111.  
  112. /* ----------------
  113.  *    btree header structure definitions
  114.  * ----------------
  115.  * Note:
  116.  *    It might be better to treat the first page of a block
  117.  *    specially by adding a bitmap of the used pages!?!
  118.  * ----------------
  119.  */
  120.  
  121. /* ----------------
  122.  *     BTreeHeaderData
  123.  * ----------------
  124.  */
  125.  
  126. typedef bits8 BTreeHeaderTypeData;
  127.  
  128. #define BTREE_PAGE_IS_FREE    ((BTreeHeaderTypeData) 0)
  129. #define BTREE_INTERNAL_HEADER    ((BTreeHeaderTypeData) 1<<0)
  130. #define BTREE_LEAF_HEADER    ((BTreeHeaderTypeData) 1<<1)
  131. #define BTREE_PAGE_HAS_RULES    ((BTreeHeaderTypeData) 1<<2)
  132.  
  133. typedef struct BTreeHeaderData {
  134.    BTreeHeaderTypeData    type;
  135.    ItemPointerData    linkData;
  136.    ItemPointerData    prevData;
  137. } BTreeHeaderData;
  138.  
  139. typedef BTreeHeaderData *BTreeHeader;
  140.  
  141. #define BTreeHeaderSize    sizeof(BTreeHeaderData)
  142.  
  143.  
  144.  
  145.  
  146. /* ----------------------------------------------------------------
  147.  *    BTreeNodes are the in-memory representations of
  148.  *    the nodes in the btree. They reference pages on disk
  149.  *    which contain the actual btree information.
  150.  * ----------------------------------------------------------------
  151.  */
  152.  
  153. /* ----------------
  154.  * BTreeNodeData --
  155.  *    B-tree node information.
  156.  *
  157.  * Note:
  158.  *    blockNumber and partition are computable from Buffer.
  159.  * ----------------
  160.  */
  161. typedef struct BTreeNodeData {
  162.         Relation        relation;
  163.     Buffer            buffer;
  164.     BlockNumber        blockNumber;
  165.     PageNumber        pageNumber;
  166.     PagePartition        partition;
  167.     BTreeHeaderTypeData type;
  168. } BTreeNodeData;
  169.  
  170. typedef BTreeNodeData    *BTreeNode;
  171.  
  172. #define InvalidBTreeNode    NULL
  173.  
  174.  
  175. /* ----------------------------------------------------------------
  176.  *    BTreeItemPointerData
  177.  * ----------------------------------------------------------------
  178.  */
  179.  
  180. typedef struct BTreeItemPointerData {
  181.    BTreeNode     node;
  182.    OffsetNumber offsetNumber;
  183. } BTreeItemPointerData;
  184.  
  185. typedef struct BTreeItemPointerData *BTreeItemPointer;
  186.  
  187. /* ----------------------------------------------------------------
  188.  *    BTreeItems form the (key, ptr) tuples stored on the
  189.  *    page. 
  190.  * ----------------------------------------------------------------
  191.  */
  192.  
  193. /* ----------------
  194.  *    BTreeItemFlags are used to classify btree items
  195.  *
  196.  *    RLOCK_L and RLOCK_R are used to identify rule lock marker tuples
  197.  *    in the index.  L is the left-hand delimiter (left to right ordering
  198.  *    in the index), and R is the right-hand.  L and R locks ALWAYS come
  199.  *    in pairs.  No other type of rule lock appears in the index.
  200.  * ----------------
  201.  */
  202.  
  203. typedef bits16 BTreeItemFlags;
  204.  
  205. #define    BTREE_ITEM_IS_LEAF    ((BTreeItemFlags) (1 << 0))
  206. #define    BTREE_ITEM_IS_HIGHKEY    ((BTreeItemFlags) (1 << 1))
  207. #define    BTREE_ITEM_IS_RLOCK_L    ((BTreeItemFlags) (1 << 2))
  208. #define    BTREE_ITEM_IS_RLOCK_R    ((BTreeItemFlags) (1 << 3))
  209. #define    BTREE_ITEM_IS_RLOCK    (BTREE_ITEM_IS_RLOCK_L|BTREE_ITEM_IS_RLOCK_R)
  210.  
  211. /* ----------------
  212. * BTreeItem --
  213.  *    Either a pointer to an internal or leaf B-tree node item.
  214.  * ----------------
  215.  */
  216.  
  217. typedef struct BTreeItemHeaderData {
  218.    BTreeItemFlags        flags;
  219.    IndexTupleData        ituple;
  220. } BTreeItemHeaderData;
  221.  
  222. typedef struct BTreeItemData {
  223.    BTreeItemHeaderData        header;
  224.    FormData            form;
  225.        /* VARIABLE LENGTH STRUCTURE */
  226. } BTreeItemData;
  227.  
  228. typedef BTreeItemData *BTreeItem;
  229.  
  230. /* ----------------
  231.  * BTreeRuleLock --
  232.  *    A marker tuple in the btree index for starting or ending a
  233.  *    rule lock.
  234.  *
  235.  *    Rule locks that use the index always have some qual.  This qual
  236.  *    is a simple (func_oid, key) pair.  When the access method is
  237.  *    inserting new tuples, or placing rule lock tuples, it uses the
  238.  *    func_oid to call a function comparing the "current" key (whatever
  239.  *    that is, at the time) with the key stored in the rule qual.  It
  240.  *    then places the new tuple appropriately based on the result.
  241.  *
  242.  *    Since the key value to use in calling the function manager is
  243.  *    already stored in the BTreeItemData, we don't bother with it here.
  244.  * ----------------
  245.  */
  246.  
  247. typedef struct BTreeRuleLockData {
  248.    BTreeItemHeaderData        header;
  249.    ObjectId            func;
  250.    FormData            form;
  251.     /* VARIABLE LENGTH STRUCTURE */
  252. } BTreeRuleLockData;
  253.  
  254. typedef BTreeRuleLockData *BTreeRuleLock;
  255.  
  256. /* ----------------------------------------------------------------
  257.  *    BTreeInsertData, BTreeSearchKeys and
  258.  *    ItemPointerElements are internal structures used during
  259.  *    searching for and insertion of btree items.
  260.  * ----------------------------------------------------------------
  261.  */
  262.  
  263. /* ----------------
  264.  *    BTreeInsertData definition
  265.  * ----------------
  266.  */
  267.  
  268. #define BTREE_NO_FLAGS            ((int8) 0)
  269. #define BTREE_INTERNAL_INSERT_DATA    ((int8) 1<<0)
  270. #define BTREE_LEAF_INSERT_DATA        ((int8) 1<<1)
  271. #define BTREE_RLOCK_L_INSERT_DATA    ((int8) 1<<2)
  272. #define BTREE_RLOCK_R_INSERT_DATA    ((int8) 1<<3)
  273. #define BTREE_RLOCK_INSERT_DATA        (BTREE_RLOCK_L_INSERT_DATA|BTREE_RLOCK_R_INSERT_DATA)
  274.  
  275. typedef struct BTreeInsertDataData {
  276.    int8            type;            /* internal or leaf */
  277.    
  278.    /* data necessary to form both internal and leaf btree items */
  279.    IndexTuple        indexTuple;
  280.    Size            size;
  281.  
  282.    /* data specific to leaf insertions */
  283.    ItemPointerData    leafPointerData;     /* return */
  284.    double        leafOffset;        /* return */
  285. } BTreeInsertDataData;
  286.  
  287. typedef BTreeInsertDataData    *BTreeInsertData;
  288.  
  289.  
  290. /* ----------------
  291.  *     BTreeSearchKey definition
  292.  *
  293.  *    Note:
  294.  *    originalInsertData is a redundant pointer to the initial
  295.  *    insertData placed into the key. Because insertData may change
  296.  *    in the case of node splitting, we keep a spare pointer to
  297.  *    the initial insertData. This is necessary because information
  298.  *    is returned in insertData->pointer which is used by the top
  299.  *    level BTreeAMInsert and BTreeAMGetTuple routines.
  300.  * ----------------
  301.  */
  302.  
  303. typedef struct BTreeSearchKeyData {
  304.    ItemPointer       pointer;        /* position to start from */
  305.    Relation       relation;        /* index relation */
  306.    ScanKeySize       scanKeySize;        /* number of atts in scan key */
  307.    ScanKey       scanKey;        /* scan key for scans */
  308.    BTreeInsertData insertData;        /* data to insert into a node */
  309.    BTreeInsertData originalInsertData;    /* data to insert into leaf node */
  310.    ScanDirection   direction;        /* forward or reverse scan */
  311.    bool           wasSuccessfulSearch;    /* return: was search successful? */
  312.    bool           isForInsertion;    /* is this an insert or a scan? */
  313.    bool           isStartingAtEndpoint; /* where should our scan start? */
  314. } BTreeSearchKeyData;
  315.  
  316. typedef BTreeSearchKeyData    *BTreeSearchKey;
  317.  
  318. /* ----------------
  319.  *     ItemPointerElement definition
  320.  *
  321.  *    ItemPointerElements are used by the btree item pointer
  322.  *    stack algorithm to implement more efficient locking.
  323.  * ----------------
  324.  */
  325.  
  326. typedef struct ItemPointerElementData {
  327.     ItemPointer    pointer;
  328.     struct ItemPointerElementData    *next;
  329. } ItemPointerElementData;
  330.  
  331. typedef ItemPointerElementData    *ItemPointerElement;
  332.  
  333. typedef ItemPointerElement    *ItemPointerStack;
  334.  
  335. /* ----------------------------------------------------------------
  336.  *    extern definitions
  337.  * ----------------------------------------------------------------
  338.  */
  339.  
  340. #include "btree-externs.h"
  341.  
  342. #endif    BTreeIncluded
  343.