2 * Copyright (c) International Business Machines Corp., 2000-2002
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.
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.
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
22 * jfs_dtree.h: directory B+-tree manager
25 #include "jfs_btree.h"
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;
50 __le16 name
[15]; /* 30: */
54 #define DATASLOTSIZE 16
55 #define L2DATASLOTSIZE 4
57 #define L2DTSLOTSIZE 5
58 #define DTSLOTHDRSIZE 2
59 #define DTSLOTDATASIZE 30
60 #define DTSLOTDATALEN 15
63 * internal node entry head/only segment
66 pxd_t xd
; /* 8: child extent descriptor */
70 __le16 name
[11]; /* 22: 2-byte aligned */
74 #define DTIHDRDATALEN 11
76 /* compute number of slots for entry */
77 #define NDTINTERNAL(klen) ( ((4 + (klen)) + (15 - 1)) / 15 )
81 * leaf node entry head/only segment
83 * For legacy filesystems, name contains 13 wchars -- no index field
86 __le32 inumber
; /* 4: 4-byte aligned */
89 __le16 name
[11]; /* 22: 2-byte aligned */
90 __le32 index
; /* 4: index into dir_table */
94 #define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */
95 #define DTLHDRDATALEN 11
98 * dir_table used for directory traversal during readdir
102 * Keep persistent index for directory entries
104 #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
107 * Maximum entry in inline directory table
109 #define MAX_INLINE_DIRTABLE_ENTRY 13
111 struct dir_table_slot
{
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 */
123 #define DIR_INDEX_VALID 1
124 #define DIR_INDEX_FREE 0
126 #define DTSaddress(dir_table_slot, address64)\
128 (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
129 (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
132 #define addressDTS(dts)\
133 ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
135 /* compute number of slots for entry */
136 #define NDTLEAF_LEGACY(klen) ( ((2 + (klen)) + (15 - 1)) / 15 )
137 #define NDTLEAF NDTINTERNAL
141 * directory root page (in-line in on-disk inode):
143 * cf. dtpage_t below.
147 struct dasd DASD
; /* 16: DASD limit/usage info */
150 u8 nextindex
; /* 1: next free entry in stbl */
151 s8 freecnt
; /* 1: free count */
152 s8 freelist
; /* 1: freelist header */
154 __le32 idotdot
; /* 4: parent inode number */
156 s8 stbl
[8]; /* 8: sorted entry index table */
159 struct dtslot slot
[9];
163 (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
165 #define DTROOTMAXSLOT 9
167 #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
171 * directory regular page:
173 * entry slot array of 32 byte slot
175 * sorted entry slot index table (stbl):
176 * contiguous slots at slot specified by stblindex,
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)
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
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.
195 __le64 next
; /* 8: next sibling */
196 __le64 prev
; /* 8: previous sibling */
199 u8 nextindex
; /* 1: next entry index in stbl */
201 s8 freelist
; /* 1: slot index of head of freelist */
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: */
207 pxd_t self
; /* 8: self pxd */
210 struct dtslot slot
[128];
213 #define DTPAGEMAXSLOT 128
215 #define DT8THPGNODEBYTES 512
216 #define DT8THPGNODETSLOTS 1
217 #define DT8THPGNODESLOTS 16
219 #define DTQTRPGNODEBYTES 1024
220 #define DTQTRPGNODETSLOTS 1
221 #define DTQTRPGNODESLOTS 32
223 #define DTHALFPGNODEBYTES 2048
224 #define DTHALFPGNODETSLOTS 2
225 #define DTHALFPGNODESLOTS 64
227 #define DTFULLPGNODEBYTES 4096
228 #define DTFULLPGNODETSLOTS 4
229 #define DTFULLPGNODESLOTS 128
231 #define DTENTRYSTART 1
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] )
246 #define DIRENTSIZ(namlen) \
247 ( (sizeof(struct dirent) - 2*(JFS_NAME_MAX+1) + 2*((namlen)+1) + 3) &~ 3 )
250 * Maximum file offset for directories.
252 #define DIREND INT_MAX
255 * external declarations
257 extern void dtInitRoot(tid_t tid
, struct inode
*ip
, u32 idotdot
);
259 extern int dtSearch(struct inode
*ip
, struct component_name
* key
,
260 ino_t
* data
, struct btstack
* btstack
, int flag
);
262 extern int dtInsert(tid_t tid
, struct inode
*ip
, struct component_name
* key
,
263 ino_t
* ino
, struct btstack
* btstack
);
265 extern int dtDelete(tid_t tid
, struct inode
*ip
, struct component_name
* key
,
266 ino_t
* data
, int flag
);
268 extern int dtModify(tid_t tid
, struct inode
*ip
, struct component_name
* key
,
269 ino_t
* orig_ino
, ino_t new_ino
, int flag
);
271 extern int jfs_readdir(struct file
*filp
, void *dirent
, filldir_t filldir
);
272 #endif /* !_H_JFS_DTREE */
This page took 0.035481 seconds and 6 git commands to generate.