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 *
17struct 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 */
98struct 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
105struct 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
131static 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