fs/jfs/jfs_btree.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 /*
0003  *   Copyright (C) International Business Machines Corp., 2000-2004
0004  */
0005 #ifndef _H_JFS_BTREE
0006 #define _H_JFS_BTREE
0007
0008 /*
0009  *  jfs_btree.h: B+-tree
0010  *
0011  * JFS B+-tree (dtree and xtree) common definitions
0012  */
0013
0014 /*
0015  *  basic btree page - btpage
0016  *
0017 struct btpage {
0018     s64 next;       right sibling bn
0019     s64 prev;       left sibling bn
0020
0021     u8 flag;
0022     u8 rsrvd[7];        type specific
0023     s64 self;       self address
0024
0025     u8 entry[4064];
0026 };                      */
0027
0028 /* btpaget_t flag */
0029 #define BT_TYPE     0x07    /* B+-tree index */
0030 #define BT_ROOT     0x01    /* root page */
0031 #define BT_LEAF     0x02    /* leaf page */
0032 #define BT_INTERNAL 0x04    /* internal page */
0033 #define BT_RIGHTMOST    0x10    /* rightmost page */
0034 #define BT_LEFTMOST 0x20    /* leftmost page */
0035 #define BT_SWAPPED  0x80    /* used by fsck for endian swapping */
0036
0037 /* btorder (in inode) */
0038 #define BT_RANDOM       0x0000
0039 #define BT_SEQUENTIAL       0x0001
0040 #define BT_LOOKUP       0x0010
0041 #define BT_INSERT       0x0020
0042 #define BT_DELETE       0x0040
0043
0044 /*
0045  *  btree page buffer cache access
0046  */
0047 #define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0)
0048
0049 /* get page from buffer page */
0050 #define BT_PAGE(IP, MP, TYPE, ROOT)\
0051     (BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data)
0052
0053 /* get the page buffer and the page for specified block address */
0054 #define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\
0055 {\
0056     if ((BN) == 0)\
0057     {\
0058         MP = (struct metapage *)&JFS_IP(IP)->bxflag;\
0059         P = (TYPE *)&JFS_IP(IP)->ROOT;\
0060         RC = 0;\
0061     }\
0062     else\
0063     {\
0064         MP = read_metapage((IP), BN, SIZE, 1);\
0065         if (MP) {\
0066             RC = 0;\
0067             P = (MP)->data;\
0068         } else {\
0069             P = NULL;\
0070             jfs_err("bread failed!");\
0071             RC = -EIO;\
0072         }\
0073     }\
0074 }
0075
0076 #define BT_MARK_DIRTY(MP, IP)\
0077 {\
0078     if (BT_IS_ROOT(MP))\
0079         mark_inode_dirty(IP);\
0080     else\
0081         mark_metapage_dirty(MP);\
0082 }
0083
0084 /* put the page buffer */
0085 #define BT_PUTPAGE(MP)\
0086 {\
0087     if (! BT_IS_ROOT(MP)) \
0088         release_metapage(MP); \
0089 }
0090
0091
0092 /*
0093  *  btree traversal stack
0094  *
0095  * record the path traversed during the search;
0096  * top frame record the leaf page/entry selected.
0097  */
0098 struct btframe {    /* stack frame */
0099     s64 bn;         /* 8: */
0100     s16 index;      /* 2: */
0101     s16 lastindex;      /* 2: unused */
0102     struct metapage *mp;    /* 4/8: */
0103 };              /* (16/24) */
0104
0105 struct btstack {
0106     struct btframe *top;
0107     int nsplit;
0108     struct btframe stack[MAXTREEHEIGHT];
0109 };
0110
0111 #define BT_CLR(btstack)\
0112     (btstack)->top = (btstack)->stack
0113
0114 #define BT_STACK_FULL(btstack)\
0115     ( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1]))
0116
0117 #define BT_PUSH(BTSTACK, BN, INDEX)\
0118 {\
0119     assert(!BT_STACK_FULL(BTSTACK));\
0120     (BTSTACK)->top->bn = BN;\
0121     (BTSTACK)->top->index = INDEX;\
0122     ++(BTSTACK)->top;\
0123 }
0124
0125 #define BT_POP(btstack)\
0126     ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )
0127
0128 #define BT_STACK(btstack)\
0129     ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )
0130
0131 static inline void BT_STACK_DUMP(struct btstack *btstack)
0132 {
0133     int i;
0134     printk("btstack dump:\n");
0135     for (i = 0; i < MAXTREEHEIGHT; i++)
0136         printk(KERN_ERR "bn = %Lx, index = %d\n",
0137                (long long)btstack->stack[i].bn,
0138                btstack->stack[i].index);
0139 }
0140
0141 /* retrieve search results */
0142 #define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\
0143 {\
0144     BN = (LEAF)->bn;\
0145     MP = (LEAF)->mp;\
0146     if (BN)\
0147         P = (TYPE *)MP->data;\
0148     else\
0149         P = (TYPE *)&JFS_IP(IP)->ROOT;\
0150     INDEX = (LEAF)->index;\
0151 }
0152
0153 /* put the page buffer of search */
0154 #define BT_PUTSEARCH(BTSTACK)\
0155 {\
0156     if (! BT_IS_ROOT((BTSTACK)->top->mp))\
0157         release_metapage((BTSTACK)->top->mp);\
0158 }
0159 #endif              /* _H_JFS_BTREE */