/*

   *   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 *filp, void *dirent, filldir_t filldir);

  #endif				/* !_H_JFS_DTREE */