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