fs/jfs/jfs_btree.h

   1 /* SPDX-License-Identifier: GPL-2.0-or-later */
   2 /*
   3  *   Copyright (C) International Business Machines Corp., 2000-2004
   4  */
   5 #ifndef _H_JFS_BTREE
   6 #define _H_JFS_BTREE
   7
   8 /*
   9  *      jfs_btree.h: B+-tree
  10  *
  11  * JFS B+-tree (dtree and xtree) common definitions
  12  */
  13
  14 /*
  15  *      basic btree page - btpage
  16  *
  17 struct btpage {
  18         s64 next;               right sibling bn
  19         s64 prev;               left sibling bn
  20
  21         u8 flag;
  22         u8 rsrvd[7];            type specific
  23         s64 self;               self address
  24
  25         u8 entry[4064];
  26 };                                              */
  27
  28 /* btpaget_t flag */
  29 #define BT_TYPE         0x07    /* B+-tree index */
  30 #define BT_ROOT         0x01    /* root page */
  31 #define BT_LEAF         0x02    /* leaf page */
  32 #define BT_INTERNAL     0x04    /* internal page */
  33 #define BT_RIGHTMOST    0x10    /* rightmost page */
  34 #define BT_LEFTMOST     0x20    /* leftmost page */
  35 #define BT_SWAPPED      0x80    /* used by fsck for endian swapping */
  36
  37 /* btorder (in inode) */
  38 #define BT_RANDOM               0x0000
  39 #define BT_SEQUENTIAL           0x0001
  40 #define BT_LOOKUP               0x0010
  41 #define BT_INSERT               0x0020
  42 #define BT_DELETE               0x0040
  43
  44 /*
  45  *      btree page buffer cache access
  46  */
  47 #define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0)
  48
  49 /* get page from buffer page */
  50 #define BT_PAGE(IP, MP, TYPE, ROOT)\
  51         (BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data)
  52
  53 /* get the page buffer and the page for specified block address */
  54 #define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\
  55 {\
  56         if ((BN) == 0)\
  57         {\
  58                 MP = (struct metapage *)&JFS_IP(IP)->bxflag;\
  59                 P = (TYPE *)&JFS_IP(IP)->ROOT;\
  60                 RC = 0;\
  61         }\
  62         else\
  63         {\
  64                 MP = read_metapage((IP), BN, SIZE, 1);\
  65                 if (MP) {\
  66                         RC = 0;\
  67                         P = (MP)->data;\
  68                 } else {\
  69                         P = NULL;\
  70                         jfs_err("bread failed!");\
  71                         RC = -EIO;\
  72                 }\
  73         }\
  74 }
  75
  76 #define BT_MARK_DIRTY(MP, IP)\
  77 {\
  78         if (BT_IS_ROOT(MP))\
  79                 mark_inode_dirty(IP);\
  80         else\
  81                 mark_metapage_dirty(MP);\
  82 }
  83
  84 /* put the page buffer */
  85 #define BT_PUTPAGE(MP)\
  86 {\
  87         if (! BT_IS_ROOT(MP)) \
  88                 release_metapage(MP); \
  89 }
  90
  91
  92 /*
  93  *      btree traversal stack
  94  *
  95  * record the path traversed during the search;
  96  * top frame record the leaf page/entry selected.
  97  */
  98 struct btframe {        /* stack frame */
  99         s64 bn;                 /* 8: */
 100         s16 index;              /* 2: */
 101         s16 lastindex;          /* 2: unused */
 102         struct metapage *mp;    /* 4/8: */
 103 };                              /* (16/24) */
 104
 105 struct btstack {
 106         struct btframe *top;
 107         int nsplit;
 108         struct btframe stack[MAXTREEHEIGHT];
 109 };
 110
 111 #define BT_CLR(btstack)\
 112         (btstack)->top = (btstack)->stack
 113
 114 #define BT_STACK_FULL(btstack)\
 115         ( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1]))
 116
 117 #define BT_PUSH(BTSTACK, BN, INDEX)\
 118 {\
 119         assert(!BT_STACK_FULL(BTSTACK));\
 120         (BTSTACK)->top->bn = BN;\
 121         (BTSTACK)->top->index = INDEX;\
 122         ++(BTSTACK)->top;\
 123 }
 124
 125 #define BT_POP(btstack)\
 126         ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )
 127
 128 #define BT_STACK(btstack)\
 129         ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )
 130
 131 static inline void BT_STACK_DUMP(struct btstack *btstack)
 132 {
 133         int i;
 134         printk("btstack dump:\n");
 135         for (i = 0; i < MAXTREEHEIGHT; i++)
 136                 printk(KERN_ERR "bn = %Lx, index = %d\n",
 137                        (long long)btstack->stack[i].bn,
 138                        btstack->stack[i].index);
 139 }
 140
 141 /* retrieve search results */
 142 #define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\
 143 {\
 144         BN = (LEAF)->bn;\
 145         MP = (LEAF)->mp;\
 146         if (BN)\
 147                 P = (TYPE *)MP->data;\
 148         else\
 149                 P = (TYPE *)&JFS_IP(IP)->ROOT;\
 150         INDEX = (LEAF)->index;\
 151 }
 152
 153 /* put the page buffer of search */
 154 #define BT_PUTSEARCH(BTSTACK)\
 155 {\
 156         if (! BT_IS_ROOT((BTSTACK)->top->mp))\
 157                 release_metapage((BTSTACK)->top->mp);\
 158 }
 159 #endif                          /* _H_JFS_BTREE */