/*static char *SCCSID = "@(#)storage.h	6.1 90/11/18";*/
/*static char *SCCSID = "@(#)storage.h	13.3 90/01/30";*/
/**	File Allocation Tracking
 *
 *	File space is allocated as a list of extents, each extent as
 *	large as we can make it.  This list is kept in a B+TREE format.
 *	Each B+TREE block consists of a single sector containing an
 *	ALSEC record, except for the top most block.  The topmost block
 *	consists of just an ALBLK structure, is usually much smaller than
 *	512 bytes, and is typically included in another structure.
 *
 *	The leaf block(s) in the tree contain triples which indicate
 *	the logical to physical mapping for this file.	Typically this
 *	extent list is small enough that it is wholy contained in the
 *	fnode ALBLK stucture.  If more than ALCNT extents are required
 *	then the tree is split into two levels.  Note that when the
 *	topmost B+TREE block is 'split' no actual split is necessary,
 *	since the new child block is much bigger than the parent block
 *	and can contain all of the old records plus the new one.  Thus,
 *	we can have B+TREEs where the root block contains only one
 *	downpointer.
 *
 *	The following rules apply:
 *
 *	1) if the file is not empty, there is at least one sector allocated
 *	   to logical offset 0.  This simplifys some critical loops.
 *
 *	2) The last entry in the last node block contains a AN_LOF value of
 *	   FFFFFFFF.  This allows us to extend that last leaf block
 *	   without having to update the node block.
 *
 *	3) For the node records, the AN_SEC points to a node or leaf
 *	   sector which describes extents which occur before that
 *	   record's AN_LOF value.
 */

/**	Bigger description
 *	ALLEAF is a structure that describes a section of a file as a
 *	contiguous run of sectors on the disk.
 *
 *	    ALLEAF.lsnLog is the sector offset within the file of a block of
 *		data on the disk
 *	    ALLEAF.csecRun is the length in sectors of the block of data on
 *		the disk
 *	    ALLEAF.lsnPhys is the sector number on the disk of the first sector
 *		of the block.
 *
 *	ALNODE is a structure that describes a section of a file's allocation
 *	on disk that is a collection of contiguous runs on the disk.
 *	Typically, this is a B+tree with all actual data descriptions
 *	occurring in the lowest-level of the tree.
 *
 *	    ALNODE.lsnLog is the sector offset within the file.
 *	    ALNODE.lsnPhys is the number of a sector on disk that contains an
 *		array of ALNODEs or an array of ALLEAFs.  All data represented
 *		in this tree will occur before logical sector ALNODE.lsnLog
 *		within the file.
 *
 *	8 ALLEAF's or 12 ALNODE's fit in a FILESTORAGE structure in the FNODE
 *	or OFT.
 *
 *	ALBLK is a header describing an array of ALLEAFs or array of ALNODEs
 *	and always immediately precedes such an array.
 *
 *	    ALBLK.bFlag is a set of flags.
 *		ABF_NODE set indicates that the following array contains
 *		    ALNODEs rather than ALLEAFs.
 *		ABF_BIN set indicates that it is suggested that the following
 *		    array be binary searched instead of linear searched.  No
 *		    code today performs such a binary scan.
 *		ABF_FNP set indicates that the parent node is an FNODE.  This
 *		    is used during splits to indicate that the OFT/FNODE
 *		    FILESTORAGE structure us the guy being updated.
 *	    ALBLK.cFree is a count of the number of free entries left in the
 *		array.
 *	    ALBLK.cUsed is a count of the number of entries in the array that
 *		are in use.
 *	    ALBLK.oFree is the offset to the next free element in the array.
 *
 *	ALSEC is a header for each allocation block below that in the
 *	OFT/FNODE.
 *
 *	    ALSEC.sig is a signature to help CHKDSK recover the disk
 *	    ALSEC.lsnSelf is the sector of the allocation block.  This is used
 *		for allocating other blocks "near" the current one as well as
 *		helping maintain the most-recent-access spot (speeds up
 *		sequential I/O).
 *	    ALSEC.lsnRent is the lsn of an allocation block that points to this
 *		one.  If ALBLK.bFlag indicates that the parent is an FNODE,
 *		ALSEC.lsnRent is the lsn of the FNODE.
 *	    ALSEC.alb is an ALBLK.
 */

typedef struct ALBLK { /* ALBLK*/
    BYTE    bFlag;		/* AB_FLAG bit mask describing block.
				 * Note: bFlag *MUST* be first field, or
				 * FIELDOFFSET() calls in COLS() will fail.
				 */
    BYTE    bPad[3];		/* AB_FLAG2 align to 4 byte boundary */
    BYTE    cFree;		/* AB_FCNT count of free entries left */
    BYTE    cUsed;		/* AB_OCNT count of used entries */
    USHORT  oFree;		/* AB_FREP offset to first free entry */
} ALBLK;

typedef ALBLK far *PALBLK;

#define ABF_NODE	0x80	/* if not a leaf node	       */
#define ABF_BIN		0x40	/* suggest using binary search to find	*/
#define ABF_FNP		0x20	/* parent is an FNODE */
#define ABF_NFG	    	0x01	/* not a flag, high order bit of oFree */

typedef struct ALLEAF { /* ALLEAF*/    
    ULONG   lsnLog;		/* AL_LOF file sector number of data block */
    ULONG   csecRun;		/* AL_LEN length of run in sectors */
    ULONG   lsnPhys;		/* AL_POF disk sector number of data block */
} ALLEAF;

typedef ALLEAF far *PALLEAF;

typedef struct ALNODE { /* ALNODE*/    
    ULONG   lsnLog;		/* AN_LOF children have data below this pos */
    ULONG   lsnPhys;		/* AN_SEC disk sector number of child block */
} ALNODE;

typedef ALNODE far *PALNODE;

#define LEAFPERSEC  40
#define NODEPERSEC  60

typedef struct ALSEC { /* ALSEC*/    
    ULONG   sig;		/* AS_SIG signature for CHKDSK to track */
    ULONG   lsnSelf;		/* AS_SEC sector number of block itself */
    ULONG   lsnRent;		/* AS_RENT sector number of parent block */
    ALBLK   alb;        /* AS_ALBLK header for array of objects */
    union {
	ALLEAF aall[LEAFPERSEC];	/* array of leaves */
	ALNODE aaln[NODEPERSEC];	/* array of nodes */
	} a;
} ALSEC;

typedef ALSEC far *PALSEC;

#define LEAFPERFNODE	8
#define NODEPERFNODE	12

typedef struct FILESTORAGE { /* FILESTORAGE*/
    ALBLK   alb;                /* header for array of objects */
    union {
	ALLEAF aall[LEAFPERFNODE];	/* array of leaves */
	ALNODE aaln[NODEPERFNODE];	/* array of nodes */
    } a;
    ULONG ulVLen;		/* (O)FN_VLEN	length of valid data in file.
						If DIR_SIZE is > FN_VLEN
						then the space inbetween
						must be zapped before being
						shown to user. */
} FILESTORAGE;

typedef FILESTORAGE far *PFILESTORAGE;

#define PALLFROMPALB(palb)  ((ALLEAF far *) ((PBYTE) (palb) + sizeof (ALBLK)))
#define PALNFROMPALB(palb)  ((ALNODE far *) ((PBYTE) (palb) + sizeof (ALBLK)))
