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 */ |
160 | |