Linux Audio

Check our new training course

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