Root/
1 | /* |
2 | * Copyright (C) International Business Machines Corp., 2000-2004 |
3 | * |
4 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License as published by |
6 | * the Free Software Foundation; either version 2 of the License, or |
7 | * (at your option) any later version. |
8 | * |
9 | * This program is distributed in the hope that it will be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See |
12 | * the GNU General Public License for more details. |
13 | * |
14 | * You should have received a copy of the GNU General Public License |
15 | * along with this program; if not, write to the Free Software |
16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
17 | */ |
18 | #ifndef _H_JFS_BTREE |
19 | #define _H_JFS_BTREE |
20 | |
21 | /* |
22 | * jfs_btree.h: B+-tree |
23 | * |
24 | * JFS B+-tree (dtree and xtree) common definitions |
25 | */ |
26 | |
27 | /* |
28 | * basic btree page - btpage |
29 | * |
30 | struct btpage { |
31 | s64 next; right sibling bn |
32 | s64 prev; left sibling bn |
33 | |
34 | u8 flag; |
35 | u8 rsrvd[7]; type specific |
36 | s64 self; self address |
37 | |
38 | u8 entry[4064]; |
39 | }; */ |
40 | |
41 | /* btpaget_t flag */ |
42 | #define BT_TYPE 0x07 /* B+-tree index */ |
43 | #define BT_ROOT 0x01 /* root page */ |
44 | #define BT_LEAF 0x02 /* leaf page */ |
45 | #define BT_INTERNAL 0x04 /* internal page */ |
46 | #define BT_RIGHTMOST 0x10 /* rightmost page */ |
47 | #define BT_LEFTMOST 0x20 /* leftmost page */ |
48 | #define BT_SWAPPED 0x80 /* used by fsck for endian swapping */ |
49 | |
50 | /* btorder (in inode) */ |
51 | #define BT_RANDOM 0x0000 |
52 | #define BT_SEQUENTIAL 0x0001 |
53 | #define BT_LOOKUP 0x0010 |
54 | #define BT_INSERT 0x0020 |
55 | #define BT_DELETE 0x0040 |
56 | |
57 | /* |
58 | * btree page buffer cache access |
59 | */ |
60 | #define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0) |
61 | |
62 | /* get page from buffer page */ |
63 | #define BT_PAGE(IP, MP, TYPE, ROOT)\ |
64 | (BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data) |
65 | |
66 | /* get the page buffer and the page for specified block address */ |
67 | #define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\ |
68 | {\ |
69 | if ((BN) == 0)\ |
70 | {\ |
71 | MP = (struct metapage *)&JFS_IP(IP)->bxflag;\ |
72 | P = (TYPE *)&JFS_IP(IP)->ROOT;\ |
73 | RC = 0;\ |
74 | }\ |
75 | else\ |
76 | {\ |
77 | MP = read_metapage((IP), BN, SIZE, 1);\ |
78 | if (MP) {\ |
79 | RC = 0;\ |
80 | P = (MP)->data;\ |
81 | } else {\ |
82 | P = NULL;\ |
83 | jfs_err("bread failed!");\ |
84 | RC = -EIO;\ |
85 | }\ |
86 | }\ |
87 | } |
88 | |
89 | #define BT_MARK_DIRTY(MP, IP)\ |
90 | {\ |
91 | if (BT_IS_ROOT(MP))\ |
92 | mark_inode_dirty(IP);\ |
93 | else\ |
94 | mark_metapage_dirty(MP);\ |
95 | } |
96 | |
97 | /* put the page buffer */ |
98 | #define BT_PUTPAGE(MP)\ |
99 | {\ |
100 | if (! BT_IS_ROOT(MP)) \ |
101 | release_metapage(MP); \ |
102 | } |
103 | |
104 | |
105 | /* |
106 | * btree traversal stack |
107 | * |
108 | * record the path traversed during the search; |
109 | * top frame record the leaf page/entry selected. |
110 | */ |
111 | struct btframe { /* stack frame */ |
112 | s64 bn; /* 8: */ |
113 | s16 index; /* 2: */ |
114 | s16 lastindex; /* 2: unused */ |
115 | struct metapage *mp; /* 4/8: */ |
116 | }; /* (16/24) */ |
117 | |
118 | struct btstack { |
119 | struct btframe *top; |
120 | int nsplit; |
121 | struct btframe stack[MAXTREEHEIGHT]; |
122 | }; |
123 | |
124 | #define BT_CLR(btstack)\ |
125 | (btstack)->top = (btstack)->stack |
126 | |
127 | #define BT_STACK_FULL(btstack)\ |
128 | ( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1])) |
129 | |
130 | #define BT_PUSH(BTSTACK, BN, INDEX)\ |
131 | {\ |
132 | assert(!BT_STACK_FULL(BTSTACK));\ |
133 | (BTSTACK)->top->bn = BN;\ |
134 | (BTSTACK)->top->index = INDEX;\ |
135 | ++(BTSTACK)->top;\ |
136 | } |
137 | |
138 | #define BT_POP(btstack)\ |
139 | ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top ) |
140 | |
141 | #define BT_STACK(btstack)\ |
142 | ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top ) |
143 | |
144 | static inline void BT_STACK_DUMP(struct btstack *btstack) |
145 | { |
146 | int i; |
147 | printk("btstack dump:\n"); |
148 | for (i = 0; i < MAXTREEHEIGHT; i++) |
149 | printk(KERN_ERR "bn = %Lx, index = %d\n", |
150 | (long long)btstack->stack[i].bn, |
151 | btstack->stack[i].index); |
152 | } |
153 | |
154 | /* retrieve search results */ |
155 | #define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\ |
156 | {\ |
157 | BN = (LEAF)->bn;\ |
158 | MP = (LEAF)->mp;\ |
159 | if (BN)\ |
160 | P = (TYPE *)MP->data;\ |
161 | else\ |
162 | P = (TYPE *)&JFS_IP(IP)->ROOT;\ |
163 | INDEX = (LEAF)->index;\ |
164 | } |
165 | |
166 | /* put the page buffer of search */ |
167 | #define BT_PUTSEARCH(BTSTACK)\ |
168 | {\ |
169 | if (! BT_IS_ROOT((BTSTACK)->top->mp))\ |
170 | release_metapage((BTSTACK)->top->mp);\ |
171 | } |
172 | #endif /* _H_JFS_BTREE */ |
173 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9