[linux.git] / fs / jfs / jfs_dtree.h

/*
 *   Copyright (C) International Business Machines Corp., 2000-2002
 *
 *   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_DTREE
#define	_H_JFS_DTREE

/*
 *	jfs_dtree.h: directory B+-tree manager
 */

#include "jfs_btree.h"

typedef union {
	struct {
		tid_t tid;
		struct inode *ip;
		u32 ino;
	} leaf;
	pxd_t xd;
} ddata_t;


/*
 *	entry segment/slot
 *
 * an entry consists of type dependent head/only segment/slot and
 * additional segments/slots linked vi next field;
 * N.B. last/only segment of entry is terminated by next = -1;
 */
/*
 *	directory page slot
 */
struct dtslot {
	s8 next;		/* 1: */
	s8 cnt;			/* 1: */
	__le16 name[15];	/* 30: */
};				/* (32) */


#define DATASLOTSIZE	16
#define L2DATASLOTSIZE	4
#define	DTSLOTSIZE	32
#define	L2DTSLOTSIZE	5
#define DTSLOTHDRSIZE	2
#define DTSLOTDATASIZE	30
#define DTSLOTDATALEN	15

/*
 *	 internal node entry head/only segment
 */
struct idtentry {
	pxd_t xd;		/* 8: child extent descriptor */

	s8 next;		/* 1: */
	u8 namlen;		/* 1: */
	__le16 name[11];	/* 22: 2-byte aligned */
};				/* (32) */

#define DTIHDRSIZE	10
#define DTIHDRDATALEN	11

/* compute number of slots for entry */
#define	NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))


/*
 *	leaf node entry head/only segment
 *
 *	For legacy filesystems, name contains 13 wchars -- no index field
 */
struct ldtentry {
	__le32 inumber;		/* 4: 4-byte aligned */
	s8 next;		/* 1: */
	u8 namlen;		/* 1: */
	__le16 name[11];	/* 22: 2-byte aligned */
	__le32 index;		/* 4: index into dir_table */
};				/* (32) */

#define DTLHDRSIZE	6
#define DTLHDRDATALEN_LEGACY	13	/* Old (OS/2) format */
#define DTLHDRDATALEN	11

/*
 * dir_table used for directory traversal during readdir
 */

/*
 * Keep persistent index for directory entries
 */
#define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)

/*
 * Maximum entry in inline directory table
 */
#define MAX_INLINE_DIRTABLE_ENTRY 13

struct dir_table_slot {
	u8 rsrvd;		/* 1: */
	u8 flag;		/* 1: 0 if free */
	u8 slot;		/* 1: slot within leaf page of entry */
	u8 addr1;		/* 1: upper 8 bits of leaf page address */
	__le32 addr2;		/* 4: lower 32 bits of leaf page address -OR-
				   index of next entry when this entry was deleted */
};				/* (8) */

/*
 * flag values
 */
#define DIR_INDEX_VALID 1
#define DIR_INDEX_FREE 0

#define DTSaddress(dir_table_slot, address64)\
{\
	(dir_table_slot)->addr1 = ((u64)address64) >> 32;\
	(dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
}

#define addressDTS(dts)\
	( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )

/* compute number of slots for entry */
#define	NDTLEAF_LEGACY(klen)	(DIV_ROUND_UP((2 + (klen)), 15))
#define	NDTLEAF	NDTINTERNAL


/*
 *	directory root page (in-line in on-disk inode):
 *
 * cf. dtpage_t below.
 */
typedef union {
	struct {
		struct dasd DASD; /* 16: DASD limit/usage info */

		u8 flag;	/* 1: */
		u8 nextindex;	/* 1: next free entry in stbl */
		s8 freecnt;	/* 1: free count */
		s8 freelist;	/* 1: freelist header */

		__le32 idotdot;	/* 4: parent inode number */

		s8 stbl[8];	/* 8: sorted entry index table */
	} header;		/* (32) */

	struct dtslot slot[9];
} dtroot_t;

#define PARENT(IP) \
	(le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))

#define DTROOTMAXSLOT	9

#define	dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)


/*
 *	directory regular page:
 *
 *	entry slot array of 32 byte slot
 *
 * sorted entry slot index table (stbl):
 * contiguous slots at slot specified by stblindex,
 * 1-byte per entry
 *   512 byte block:  16 entry tbl (1 slot)
 *  1024 byte block:  32 entry tbl (1 slot)
 *  2048 byte block:  64 entry tbl (2 slot)
 *  4096 byte block: 128 entry tbl (4 slot)
 *
 * data area:
 *   512 byte block:  16 - 2 =  14 slot
 *  1024 byte block:  32 - 2 =  30 slot
 *  2048 byte block:  64 - 3 =  61 slot
 *  4096 byte block: 128 - 5 = 123 slot
 *
 * N.B. index is 0-based; index fields refer to slot index
 * except nextindex which refers to entry index in stbl;
 * end of entry stot list or freelist is marked with -1.
 */
typedef union {
	struct {
		__le64 next;	/* 8: next sibling */
		__le64 prev;	/* 8: previous sibling */

		u8 flag;	/* 1: */
		u8 nextindex;	/* 1: next entry index in stbl */
		s8 freecnt;	/* 1: */
		s8 freelist;	/* 1: slot index of head of freelist */

		u8 maxslot;	/* 1: number of slots in page slot[] */
		u8 stblindex;	/* 1: slot index of start of stbl */
		u8 rsrvd[2];	/* 2: */

		pxd_t self;	/* 8: self pxd */
	} header;		/* (32) */

	struct dtslot slot[128];
} dtpage_t;

#define DTPAGEMAXSLOT        128

#define DT8THPGNODEBYTES     512
#define DT8THPGNODETSLOTS      1
#define DT8THPGNODESLOTS      16

#define DTQTRPGNODEBYTES    1024
#define DTQTRPGNODETSLOTS      1
#define DTQTRPGNODESLOTS      32

#define DTHALFPGNODEBYTES   2048
#define DTHALFPGNODETSLOTS     2
#define DTHALFPGNODESLOTS     64

#define DTFULLPGNODEBYTES   4096
#define DTFULLPGNODETSLOTS     4
#define DTFULLPGNODESLOTS    128

#define DTENTRYSTART	1

/* get sorted entry table of the page */
#define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
	((dtroot_t *)(p))->header.stbl : \
	(s8 *)&(p)->slot[(p)->header.stblindex] )

/*
 * Flags for dtSearch
 */
#define JFS_CREATE 1
#define JFS_LOOKUP 2
#define JFS_REMOVE 3
#define JFS_RENAME 4

/*
 * Maximum file offset for directories.
 */
#define DIREND	INT_MAX

/*
 *	external declarations
 */
extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);

extern int dtSearch(struct inode *ip, struct component_name * key,
		    ino_t * data, struct btstack * btstack, int flag);

extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
		    ino_t * ino, struct btstack * btstack);

extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
		    ino_t * data, int flag);

extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
		    ino_t * orig_ino, ino_t new_ino, int flag);

extern int jfs_readdir(struct file *file, struct dir_context *ctx);
#endif				/* !_H_JFS_DTREE */
Commit	Line	Data
1da177e4	1	/*
63f83c9f	2	* Copyright (C) International Business Machines Corp., 2000-2002
1da177e4 LT	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
63f83c9f	6	* the Free Software Foundation; either version 2 of the License, or
1da177e4	7	* (at your option) any later version.
63f83c9f	8	*
1da177e4 LT	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
63f83c9f	15	* along with this program; if not, write to the Free Software
1da177e4 LT	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
	27	typedef 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	/*
f720e3ba	38	* entry segment/slot
1da177e4 LT	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	*/
	47	struct 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	*/
	65	struct 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 */
a7fe0ba7	77	#define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))
1da177e4 LT	78
	79
	80	/*
	81	* leaf node entry head/only segment
	82	*
63f83c9f	83	* For legacy filesystems, name contains 13 wchars -- no index field
1da177e4 LT	84	*/
	85	struct 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
	111	struct 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 */
a7fe0ba7	136	#define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15))
1da177e4 LT	137	#define NDTLEAF NDTINTERNAL
	138
	139
	140	/*
	141	* directory root page (in-line in on-disk inode):
	142	*
	143	* cf. dtpage_t below.
	144	*/
	145	typedef 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	*/
	193	typedef 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
1da177e4 LT	246	/*
	247	* Maximum file offset for directories.
	248	*/
	249	#define DIREND INT_MAX
	250
	251	/*
	252	* external declarations
	253	*/
	254	extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
	255
	256	extern int dtSearch(struct inode ip, struct component_name key,
	257	ino_t * data, struct btstack * btstack, int flag);
	258
	259	extern int dtInsert(tid_t tid, struct inode ip, struct component_name key,
	260	ino_t * ino, struct btstack * btstack);
	261
	262	extern int dtDelete(tid_t tid, struct inode ip, struct component_name key,
	263	ino_t * data, int flag);
	264
	265	extern int dtModify(tid_t tid, struct inode ip, struct component_name key,
	266	ino_t * orig_ino, ino_t new_ino, int flag);
	267
070a0ebf	268	extern int jfs_readdir(struct file file, struct dir_context ctx);
1da177e4	269	#endif /* !_H_JFS_DTREE */