aboutsummaryrefslogtreecommitdiffstats
path: root/fs/jfs/jfs_btree.h
blob: 7f3e9ac454fff1f34678e002740d65ecb9754415 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*
 *   Copyright (C) International Business Machines Corp., 2000-2004
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or 
 *   (at your option) any later version.
 * 
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software 
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
#ifndef	_H_JFS_BTREE
#define _H_JFS_BTREE

/*
 *	jfs_btree.h: B+-tree
 *
 * JFS B+-tree (dtree and xtree) common definitions
 */

/*
 *	basic btree page - btpage
 *
struct btpage {
	s64 next;		right sibling bn
	s64 prev;		left sibling bn

	u8 flag;
	u8 rsrvd[7];		type specific
	s64 self;		self address

	u8 entry[4064];
};						*/

/* btpaget_t flag */
#define BT_TYPE		0x07	/* B+-tree index */
#define	BT_ROOT		0x01	/* root page */
#define	BT_LEAF		0x02	/* leaf page */
#define	BT_INTERNAL	0x04	/* internal page */
#define	BT_RIGHTMOST	0x10	/* rightmost page */
#define	BT_LEFTMOST	0x20	/* leftmost page */
#define	BT_SWAPPED	0x80	/* used by fsck for endian swapping */

/* btorder (in inode) */
#define	BT_RANDOM		0x0000
#define	BT_SEQUENTIAL		0x0001
#define	BT_LOOKUP		0x0010
#define	BT_INSERT		0x0020
#define	BT_DELETE		0x0040

/*
 *	btree page buffer cache access
 */
#define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0)

/* get page from buffer page */
#define BT_PAGE(IP, MP, TYPE, ROOT)\
	(BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data)

/* get the page buffer and the page for specified block address */
#define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\
{\
	if ((BN) == 0)\
	{\
		MP = (struct metapage *)&JFS_IP(IP)->bxflag;\
		P = (TYPE *)&JFS_IP(IP)->ROOT;\
		RC = 0;\
	}\
	else\
	{\
		MP = read_metapage((IP), BN, SIZE, 1);\
		if (MP) {\
			RC = 0;\
			P = (MP)->data;\
		} else {\
			P = NULL;\
			jfs_err("bread failed!");\
			RC = -EIO;\
		}\
	}\
}

#define BT_MARK_DIRTY(MP, IP)\
{\
	if (BT_IS_ROOT(MP))\
		mark_inode_dirty(IP);\
	else\
		mark_metapage_dirty(MP);\
}

/* put the page buffer */
#define BT_PUTPAGE(MP)\
{\
	if (! BT_IS_ROOT(MP)) \
		release_metapage(MP); \
}


/*
 *	btree traversal stack
 *
 * record the path traversed during the search;
 * top frame record the leaf page/entry selected.
 */
struct btframe {	/* stack frame */
	s64 bn;			/* 8: */
	s16 index;		/* 2: */
	s16 lastindex;		/* 2: unused */
	struct metapage *mp;	/* 4/8: */
};				/* (16/24) */

struct btstack {
	struct btframe *top;
	int nsplit;
	struct btframe stack[MAXTREEHEIGHT];
};

#define BT_CLR(btstack)\
	(btstack)->top = (btstack)->stack

#define BT_STACK_FULL(btstack)\
	( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1]))

#define BT_PUSH(BTSTACK, BN, INDEX)\
{\
	assert(!BT_STACK_FULL(BTSTACK));\
	(BTSTACK)->top->bn = BN;\
	(BTSTACK)->top->index = INDEX;\
	++(BTSTACK)->top;\
}

#define BT_POP(btstack)\
	( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )

#define BT_STACK(btstack)\
	( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )

static inline void BT_STACK_DUMP(struct btstack *btstack)
{
	int i;
	printk("btstack dump:\n");
	for (i = 0; i < MAXTREEHEIGHT; i++)
		printk(KERN_ERR "bn = %Lx, index = %d\n",
		       (long long)btstack->stack[i].bn,
		       btstack->stack[i].index);
}

/* retrieve search results */
#define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\
{\
	BN = (LEAF)->bn;\
	MP = (LEAF)->mp;\
	if (BN)\
		P = (TYPE *)MP->data;\
	else\
		P = (TYPE *)&JFS_IP(IP)->ROOT;\
	INDEX = (LEAF)->index;\
}

/* put the page buffer of search */
#define BT_PUTSEARCH(BTSTACK)\
{\
	if (! BT_IS_ROOT((BTSTACK)->top->mp))\
		release_metapage((BTSTACK)->top->mp);\
}
#endif				/* _H_JFS_BTREE */