aboutsummaryrefslogtreecommitdiffstats
path: root/fs/jfs/jfs_dtree.h
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /fs/jfs/jfs_dtree.h
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'fs/jfs/jfs_dtree.h')
-rw-r--r--fs/jfs/jfs_dtree.h279
1 files changed, 279 insertions, 0 deletions
diff --git a/fs/jfs/jfs_dtree.h b/fs/jfs/jfs_dtree.h
new file mode 100644
index 000000000000..273a80130c9d
--- /dev/null
+++ b/fs/jfs/jfs_dtree.h
@@ -0,0 +1,279 @@
1/*
2 * Copyright (c) International Business Machines Corp., 2000-2002
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_DTREE
19#define _H_JFS_DTREE
20
21/*
22 * jfs_dtree.h: directory B+-tree manager
23 */
24
25#include "jfs_btree.h"
26
27typedef union {
28 struct {
29 tid_t tid;
30 struct inode *ip;
31 u32 ino;
32 } leaf;
33 pxd_t xd;
34} ddata_t;
35
36
37/*
38 * entry segment/slot
39 *
40 * an entry consists of type dependent head/only segment/slot and
41 * additional segments/slots linked vi next field;
42 * N.B. last/only segment of entry is terminated by next = -1;
43 */
44/*
45 * directory page slot
46 */
47struct dtslot {
48 s8 next; /* 1: */
49 s8 cnt; /* 1: */
50 __le16 name[15]; /* 30: */
51}; /* (32) */
52
53
54#define DATASLOTSIZE 16
55#define L2DATASLOTSIZE 4
56#define DTSLOTSIZE 32
57#define L2DTSLOTSIZE 5
58#define DTSLOTHDRSIZE 2
59#define DTSLOTDATASIZE 30
60#define DTSLOTDATALEN 15
61
62/*
63 * internal node entry head/only segment
64 */
65struct idtentry {
66 pxd_t xd; /* 8: child extent descriptor */
67
68 s8 next; /* 1: */
69 u8 namlen; /* 1: */
70 __le16 name[11]; /* 22: 2-byte aligned */
71}; /* (32) */
72
73#define DTIHDRSIZE 10
74#define DTIHDRDATALEN 11
75
76/* compute number of slots for entry */
77#define NDTINTERNAL(klen) ( ((4 + (klen)) + (15 - 1)) / 15 )
78
79
80/*
81 * leaf node entry head/only segment
82 *
83 * For legacy filesystems, name contains 13 wchars -- no index field
84 */
85struct ldtentry {
86 __le32 inumber; /* 4: 4-byte aligned */
87 s8 next; /* 1: */
88 u8 namlen; /* 1: */
89 __le16 name[11]; /* 22: 2-byte aligned */
90 __le32 index; /* 4: index into dir_table */
91}; /* (32) */
92
93#define DTLHDRSIZE 6
94#define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */
95#define DTLHDRDATALEN 11
96
97/*
98 * dir_table used for directory traversal during readdir
99 */
100
101/*
102 * Keep persistent index for directory entries
103 */
104#define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
105
106/*
107 * Maximum entry in inline directory table
108 */
109#define MAX_INLINE_DIRTABLE_ENTRY 13
110
111struct dir_table_slot {
112 u8 rsrvd; /* 1: */
113 u8 flag; /* 1: 0 if free */
114 u8 slot; /* 1: slot within leaf page of entry */
115 u8 addr1; /* 1: upper 8 bits of leaf page address */
116 __le32 addr2; /* 4: lower 32 bits of leaf page address -OR-
117 index of next entry when this entry was deleted */
118}; /* (8) */
119
120/*
121 * flag values
122 */
123#define DIR_INDEX_VALID 1
124#define DIR_INDEX_FREE 0
125
126#define DTSaddress(dir_table_slot, address64)\
127{\
128 (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
129 (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
130}
131
132#define addressDTS(dts)\
133 ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
134
135/* compute number of slots for entry */
136#define NDTLEAF_LEGACY(klen) ( ((2 + (klen)) + (15 - 1)) / 15 )
137#define NDTLEAF NDTINTERNAL
138
139
140/*
141 * directory root page (in-line in on-disk inode):
142 *
143 * cf. dtpage_t below.
144 */
145typedef union {
146 struct {
147 struct dasd DASD; /* 16: DASD limit/usage info */
148
149 u8 flag; /* 1: */
150 u8 nextindex; /* 1: next free entry in stbl */
151 s8 freecnt; /* 1: free count */
152 s8 freelist; /* 1: freelist header */
153
154 __le32 idotdot; /* 4: parent inode number */
155
156 s8 stbl[8]; /* 8: sorted entry index table */
157 } header; /* (32) */
158
159 struct dtslot slot[9];
160} dtroot_t;
161
162#define PARENT(IP) \
163 (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
164
165#define DTROOTMAXSLOT 9
166
167#define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
168
169
170/*
171 * directory regular page:
172 *
173 * entry slot array of 32 byte slot
174 *
175 * sorted entry slot index table (stbl):
176 * contiguous slots at slot specified by stblindex,
177 * 1-byte per entry
178 * 512 byte block: 16 entry tbl (1 slot)
179 * 1024 byte block: 32 entry tbl (1 slot)
180 * 2048 byte block: 64 entry tbl (2 slot)
181 * 4096 byte block: 128 entry tbl (4 slot)
182 *
183 * data area:
184 * 512 byte block: 16 - 2 = 14 slot
185 * 1024 byte block: 32 - 2 = 30 slot
186 * 2048 byte block: 64 - 3 = 61 slot
187 * 4096 byte block: 128 - 5 = 123 slot
188 *
189 * N.B. index is 0-based; index fields refer to slot index
190 * except nextindex which refers to entry index in stbl;
191 * end of entry stot list or freelist is marked with -1.
192 */
193typedef union {
194 struct {
195 __le64 next; /* 8: next sibling */
196 __le64 prev; /* 8: previous sibling */
197
198 u8 flag; /* 1: */
199 u8 nextindex; /* 1: next entry index in stbl */
200 s8 freecnt; /* 1: */
201 s8 freelist; /* 1: slot index of head of freelist */
202
203 u8 maxslot; /* 1: number of slots in page slot[] */
204 u8 stblindex; /* 1: slot index of start of stbl */
205 u8 rsrvd[2]; /* 2: */
206
207 pxd_t self; /* 8: self pxd */
208 } header; /* (32) */
209
210 struct dtslot slot[128];
211} dtpage_t;
212
213#define DTPAGEMAXSLOT 128
214
215#define DT8THPGNODEBYTES 512
216#define DT8THPGNODETSLOTS 1
217#define DT8THPGNODESLOTS 16
218
219#define DTQTRPGNODEBYTES 1024
220#define DTQTRPGNODETSLOTS 1
221#define DTQTRPGNODESLOTS 32
222
223#define DTHALFPGNODEBYTES 2048
224#define DTHALFPGNODETSLOTS 2
225#define DTHALFPGNODESLOTS 64
226
227#define DTFULLPGNODEBYTES 4096
228#define DTFULLPGNODETSLOTS 4
229#define DTFULLPGNODESLOTS 128
230
231#define DTENTRYSTART 1
232
233/* get sorted entry table of the page */
234#define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
235 ((dtroot_t *)(p))->header.stbl : \
236 (s8 *)&(p)->slot[(p)->header.stblindex] )
237
238/*
239 * Flags for dtSearch
240 */
241#define JFS_CREATE 1
242#define JFS_LOOKUP 2
243#define JFS_REMOVE 3
244#define JFS_RENAME 4
245
246#define DIRENTSIZ(namlen) \
247 ( (sizeof(struct dirent) - 2*(JFS_NAME_MAX+1) + 2*((namlen)+1) + 3) &~ 3 )
248
249/*
250 * Maximum file offset for directories.
251 */
252#define DIREND INT_MAX
253
254/*
255 * external declarations
256 */
257extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
258
259extern int dtSearch(struct inode *ip, struct component_name * key,
260 ino_t * data, struct btstack * btstack, int flag);
261
262extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
263 ino_t * ino, struct btstack * btstack);
264
265extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
266 ino_t * data, int flag);
267
268extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
269 ino_t * orig_ino, ino_t new_ino, int flag);
270
271extern int jfs_readdir(struct file *filp, void *dirent, filldir_t filldir);
272
273#ifdef _JFS_DEBUG_DTREE
274extern int dtDisplayTree(struct inode *ip);
275
276extern int dtDisplayPage(struct inode *ip, s64 bn, dtpage_t * p);
277#endif /* _JFS_DEBUG_DTREE */
278
279#endif /* !_H_JFS_DTREE */