/* 

 * Motif

 *

 * Copyright (c) 1987-2012, The Open Group. All rights reserved.

 *

 * These libraries and programs are free software; you can

 * redistribute them and/or modify them under the terms of the GNU

 * Lesser General Public License as published by the Free Software

 * Foundation; either version 2 of the License, or (at your option)

 * any later version.

 *

 * These libraries and programs are distributed in the hope that

 * they will be useful, but WITHOUT ANY WARRANTY; without even the

 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR

 * PURPOSE. See the GNU Lesser General Public License for more

 * details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with these librararies and programs; if not, write

 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth

 * Floor, Boston, MA 02110-1301 USA

*/ 

/* 

 * HISTORY

*/ 

/*   $XConsortium: IDB.h /main/11 1995/07/14 10:36:17 drk $ */

/*

*  (c) Copyright 1989, 1990, DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASS. */

#ifndef idb_h

#define	idb_h	1

/*

 * This file defines the constants and structs required by the URM

 * Indexed Data Base facility (IDB). The order of definition is:

 *	o literals

 *	o primitive typedefs

 *	o typedefs for file records

 *	o typedefs for in-memory structures

 */

/*

 * IDB literals

 */

/*

 * Primitive typedefs

 */

/*

 * A data pointer. Consists of a record number (of a data record) and an

 * offset in the record to the data entry.

 */

typedef union {

	unsigned		pointer ;	/* the pointer as a value */

	struct {

	  IDBRecordNumber	rec_no B32 ;	/* record number */

	  MrmOffset		item_offs B32 ;	/* offset of data entry in

						   record. Must be a

						   IDB*DataEntry struct */

	}			internal_id ;	/* 2 fields internally */

} IDBDataPointer ;

/*

 * A data pointer as a passed-by-value reference

 */

#if 0

typedef unsigned		IDBDataHandle ;

#endif

typedef struct {

  IDBRecordNumber	rec_no ;		  /* record number */

  MrmOffset		item_offs ;		  /* offset of data entry in

						     record. Must be a

						     IDB*DataEntry struct */

} IDBDataHandle ;

/*

 * A data item in a data record.

 */

/*

 * entry types distinguish simple and overflow records

 */

#define IDBdrSimple	1

#define	IDBdrOverflow	2

/*

 * Common header for both simple and overflow data entries

 */

#define	IDBDataEntryValid	222857390

typedef struct {

	unsigned	validation;		/* validation code =

						   IDBDataEntryValid */

	MrmCode		entry_type;		/* IDBdrSimple, IDBdrOverflow */

	MrmCode		resource_group;		/* resource group */

	MrmCode		resource_type;		/* resource type */

	MrmCode		access;			/* URMaPrivate or URMaPublic */

	MrmCode		lock;			/* locking code */

	MrmSize		entry_size;		/* number of data bytes */

	MrmOffset	prev_entry;		/* Offset of previous entry in

						   this data record.  */

} IDBDataEntryHdr, *IDBDataEntryHdrPtr ;

#define SwapIDBDataEntryHdr(deh) { \

        swap4bytes(deh->validation); \

        swap2bytes(deh->entry_type) ; \

        swap2bytes(deh->resource_group) ; \

        swap2bytes(deh->resource_type) ; \

        swap2bytes(deh->access) ; \

        swap2bytes(deh->lock) ; \

        swap2bytes(deh->entry_size) ; \

        swap2bytes(deh->prev_entry) ; \

}

/*

 * A simple data entry

 */

typedef struct {

	IDBDataEntryHdr	header ;		/* common header, entry_type =

						   IDBdrSimple */

	char		data[1] ;		/* First byte in data */

} IDBSimpleData, *IDBSimpleDataPtr ;

/*

 * An overflow data entry. These are used for all data entries which are

 * too big to fit in a single record. These are broken up into 2 or more

 * overflow entries, whose contents are concatenated to produce the

 * actual data entry.

 */

typedef struct {

	IDBDataEntryHdr	header ;		/* common header, entry_type =

						   IDBdrOverflow */

	MrmSize		segment_size;		/* number of data bytes in

						   this segment */

	MrmCount	segment_count;		/* number of records needed

						   to store entry */

	MrmCount	segment_num;		/* this segment's number */

	IDBDataPointer	next_segment ;		/* next segment */

	char		data[1] ;		/* first data byte */

} IDBOverflowData, *IDBOverflowDataPtr ;

#define SwapIDBOverflowData(doh) { \

        swap2bytes(doh->segment_size) ; \

        swap2bytes(doh->segment_count) ; \

        swap2bytes(doh->segment_num) ; \

        swap2bytes(doh->next_segment.internal_id.rec_no) ; \

        swap2bytes(doh->next_segment.internal_id.item_offs) ; \

}

/*

 * Header sizes for data entries

 */

#define	IDBSimpleDataHdrSize	(sizeof(IDBSimpleData) - sizeof(char))

#define	IDBOverflowDataHdrSize	(sizeof(IDBOverflowData) - sizeof(char))

/*

 * File record definitions

 *

 * IDB uses one size of fixed-length record for all its file records.

 * The size of this record is determined as a reasonable common size

 * which gives efficient disk access on all the file systems on which

 * IDB runs.

 *

 * All records are accessed by record number. These increase monotonically

 * from the lowest valid record number, which is maintained in the file

 * header.

 *

 * IDB defines the following types of records:

 *	Header		- one per file

 *	Index leaf	- contains leaf nodes of the B-tree index

 *	Index node	- contains non-leaf nodes of the B-tree index

 *	RID map		- contains pointers which map IDB resourc IDs to

 *			  data block pointers

 *	Data		- Contains data blocks

 *

 * All records have a common record header which gives the record number

 * and record type. This header and the information for each record type

 * are defined below.

 */

/*

 * Number of bytes in a low-level file block = # bytes in an IDB file record

 */

#define	IDBRecordSize	4096

/*

 * IDB record header

 */

#define	IDBRecordHeaderValid	310144882

typedef struct {

	unsigned	validation;	/* validation code =

					   IDBRecordHeaderValid */

	MrmType		record_type;  	/* record type */

	IDBRecordNumber	record_num;	/* IDB record number */

} IDBRecordHeader, *IDBRecordHeaderPtr ;

/*

 * Dummy IDB record.

 */

typedef struct {

	IDBRecordHeader	header ;

	char		dummy[IDBRecordSize-sizeof(IDBRecordHeader)] ;

} IDBDummyRecord, *IDBDummyRecordPtr ;

/*

 * IDB header record definition

 *

 * There is one header record per IDB file. It is the only record in the

 * which must be at a fixed location; its record number is

 * IDBHeaderRecordNumber.

 *

 * The header contains the following:

 *	o Information about how the file was created

 *	o A pointer to the root node record for the B-tree index

 *	o The next available resourc id (RID)

 *	o An end-of-file pointer (record number of last record in file)

 *	o Counters of the number of index and RID entries in the file

 *	o Counter of the different types of records in the file

 *	o The remainder of the record is used as the initial space in

 *	  which to allocate a small RID map and data entries. This

 *	  enables relatively small files to be created when a small

 *	  amount of information will be stored, as the minimal file

 *	  need contain only a header and (probably) and index leaf record

 *	  rather than also requiring an RID map record and a data record.

 */

/*

 * IDB file header record header

 */

typedef struct {

	IDBRecordHeader	header ;		/* record_type =

						   IDBrtHeader,

						   record_num =

						   IDBrtHeader, */

	char		db_version[IDBhsVersion1] ;

						/* database version */

	char		creator[IDBhsCreator1] ; /* creator id */

	char		creator_version[IDBhsVersion1] ;

						/* creator version */

	char		creation_date[IDBhsDate1] ;

						/* creation date */

	char		module[IDBhsModule1] ;	/* module id */

	char		module_version[IDBhsVersion1] ;

						/* module version */

	IDBRecordNumber	index_root ;		/* index root pointer */

	MrmCount	num_indexed ;		/* # entries in index */

	MrmCount	num_RID ;		/* # RID entries in file */

	IDBridDesc	next_RID ;		/* next available RID. */

	IDBRecordNumber	last_record ;		/* last record used in file */

	IDBRecordNumber	last_data_record ;	/* last data record in file */

	MrmCount	group_counts[URMgVecSize] ;

						/* vector of record counts

						   by resource group */

	MrmCount	rt_counts[IDBrtVecSize] ;

						/* vector of record counts by

						   record type (statistics) */

} IDBHeaderHdr, *IDBHeaderHdrPtr ;

/*

 * IDB file header record

 *

 * Max number of entries in RID pointer vector

 */

#define	IDBHeaderRIDMax		20

typedef struct {

	IDBHeaderHdr	header_hdr ;	/* header part */

	IDBDataPointer	RID_pointers[IDBHeaderRIDMax];

					/* RID pointer vector */

	MrmCount	num_entry;	/* number of entries in record */

	MrmOffset	last_entry;	/* last entry in page */

	MrmOffset	free_ptr;	/* offset of first free byte.

					   initial value = 0 */

	MrmCount	free_count;	/* number of free bytes. Initial

					   value = IDBHeaderFreeMax */

	char		data[1];	/* First available byte for data */

} IDBHeaderRecord, *IDBHeaderRecordPtr ;

/*

 * Free space in header record, max number of bytes available for data.

 */

#define	IDBHeaderFreeMax (IDBRecordSize-sizeof(IDBHeaderRecord)+sizeof(char))

/*

 * Record number of the header record

 */

#define	IDBHeaderRecordNumber	1

/*

 * Index leaf record definition

 *

 * IDB provides two mutually exclusive mechanisms for accessing data.

 * The first is an index system based on ASCII keys (indexes). This

 * uses a B-tree index as its lookup mechanism. The second mechanism

 * is a resource id mechanism offering potentially faster access, as

 * described below.

 *

 * As usual in B-tree systems, the B-tree index has two kinds of nodes:

 * leaf nodes, which contain only data pointers, and B-tree nodes,

 * which contain pointers to other B-tree records. The following describes

 * leaf records in the B-tree index.

 *

 * The root node of the index is a leaf record if there is exactly 1

 * record in the index, and is a tree node otherwise.

 *

 * A leaf record consists of a sorted vector of index entries, ordered

 * in increasing alphabetical order by the index value. The vector

 * contains fixed-length entries, with the key strings being allocated

 * at the bottom of the record. The vector grows down from the top and

 * the string heap up from the bottom as entries are added, until the

 * record fills. 

 */

/*

 * An entry in the index vector

 */

typedef struct {

	MrmOffset	index_stg;	/* offset of the index string in

					   the record. Nul-terminated. */

	IDBDataPointer	data ;		/* pointer to the data entry */

} IDBIndexLeafEntry, *IDBIndexLeafEntryPtr ;

/*

 * Size of an index vector entry

 */

#define	IDBIndexLeafEntrySize	sizeof(IDBIndexLeafEntry)

/*

 * Max length of an index string (terminating nul not included)

 */

#define	IDBMaxIndexLength	URMMaxIndexLen

#define	IDBMaxIndexLength1	(IDBMaxIndexLength + 1)

/*

 * Leaf record header

 */

typedef struct {

	IDBRecordHeader	header ;	/* record_type = IDBrtIndexLeaf */

	IDBRecordNumber	parent;		/* B-tree parent record */

	MrmCount	index_count;	/* Number of index entries in record */

	MrmOffset	heap_start;	/* Offset of first byte in use for

					   index string heap storage. Offset

					   is from .index[0] */

	MrmCount	free_bytes;	/* Number of free bytes in record */

} IDBIndexLeafHdr, *IDBIndexLeafHdrPtr ;

/*

 * The leaf record

 */

typedef struct {

	IDBIndexLeafHdr	leaf_header ;	/* header part of record. Initial

					   values: heap_start =

					   free_bytes = IDBIndexLeafFreeMax */

	IDBIndexLeafEntry index[1] ;	/* First entry in index vector. There

					   are index_count entries. */

} IDBIndexLeafRecord, *IDBIndexLeafRecordPtr ;

/*

 * Max number of free bytes in leaf index record (0 entries)

 */

#define	IDBIndexLeafFreeMax	(IDBRecordSize - sizeof(IDBIndexLeafHdr))

/*

 * Index B-tree node record definition

 *

 * A B-tree node record is similar to a leaf entry, except that each node

 * contains a pair of pointers to other nodes in the tree; one to a LT

 * node, all of whose entries order < the entry's index; one to a GT node,

 * all of whose entries order > the entry's index. The GT pointer of node

 * m = the LT pointer of node m+1. Thus any node record containing n nodes

 * points to n+1 tree nodes. Allocation of heap for index strings is as in

 * a leaf record. All entries also locate a data entry.

 */

/*

 * An entry in the index vector

 */

typedef struct {

	MrmOffset	index_stg;	/* offset of the index string in

					   the record. Nul-terminated. */

	IDBDataPointer	data ;		/* pointer to the data entry */

	IDBRecordNumber	LT_record;	/* pointer to LT record */

	IDBRecordNumber	GT_record;	/* pointer to GT record */

} IDBIndexNodeEntry, *IDBIndexNodeEntryPtr ;

/*

 * Size of an index vector entry

 */

#define	IDBIndexNodeEntrySize	sizeof(IDBIndexNodeEntry)

/*

 * Node record header

 */

typedef struct {

	IDBRecordHeader	header ;	/* record_type = IDBrtIndexNode */

	IDBRecordNumber	parent;		/* B-tree parent record */

	MrmCount	index_count;	/* Number of index entries in record */

	MrmOffset	heap_start;	/* Offset of first byte in use for

					   index string heap storage. Offset

					   is from .index[0] */

	MrmCount	free_bytes;	/* Number of free bytes in record */

} IDBIndexNodeHdr, *IDBIndexNodeHdrPtr ;

/*

 * The B-tree node entry

 */

typedef struct {

	IDBIndexNodeHdr	node_header ;	/* header part of record. Initial

					   values: heap_start =

					   free_bytes = IDBIndexNodeFreeMax */

	IDBIndexNodeEntry index[1] ;	/* First entry in index vector. There

					   are index_count entries. */

} IDBIndexNodeRecord, *IDBIndexNodeRecordPtr ;

/*

 * Max number of free bytes in node index record (0 entries)

 */

#define	IDBIndexNodeFreeMax	(IDBRecordSize - sizeof(IDBIndexNodeHdr))

/*

 * Max number of bytes consumed by a new entry

 */

#define	IDBIndexNodeEntryMax	(IDBMaxIndexLength1 + IDBIndexNodeEntrySize \

				+ sizeof(IDBRecordNumber))

/*

 * Resource ID record

 *

 * RID records locate the data block associated with a given resource ID.

 * Looking up a data block accessed by RID is a two-step process:

 *	1. The index map in the file header (maintained in-memory for open

 *	   files) is used to locate the correct resource ID record. The

 *	   map_index field in a RID descriptor accesses this record via

 *	   the RID_maps vector in the header.

 *	2. The Resource ID record supplies the data block pointer. The

 *	   data block pointer is found in the resource_ptr vector using the

 *	   res_index field of the RID descriptor.

 *

 * Aside from the standard record header, an RID record contains only

 * a vector of data block pointer.

 */

/*

 * The RID map record header

 */

typedef struct {

	IDBRecordHeader	header ;	/* record type = IDBrdRIDMap */

} IDBridMapHdr, *IDBridMapHdrPtr ;

/*

 * The RID map record is a vector of data pointers

 */

typedef struct {

	IDBridMapHdr	map_header ;	/* Header part of record */

	IDBDataPointer	pointers[1] ;	/* First pointer in vector. */

} IDBridMapRecord, *IDBridMapRecordPtr ;

/*

 * Max number of free bytes, number of vector entries in RID record

 */

#define	IDBridFreeMax		(IDBRecordSize - sizeof(IDBridMapHdr))

#define	IDBridPtrVecMax		(IDBridFreeMax / sizeof(IDBDataPointer))

/*

 * Data record

 *

 * Data records hold data entries. The record maintains a free space

 * pointer, but otherwise contains little information. IDB attempts

 * to avoid splitting data entries into segments, and is thus willing

 * to waste some space in a data record if a data item will fit in

 * a new record.

 *

 * All the data entries in a record are chained via the prev_entry offset

 * field. This is for the convenience of the dump routines. The first

 * entry is always at offset 0 (= initial value of free ptr).

 */

/*

 * The data record header

 */

typedef struct {

	IDBRecordHeader	header ;	/* record = IDBrtData */

	MrmCount	num_entry;	/* number of entries in record */

	MrmOffset	last_entry;	/* last entry in page */

	MrmOffset	free_ptr;	/* offset of first free byte.

					   initial value = 0 */

	MrmCount	free_count;	/* number of free bytes. Initial

					   value = IDBDataFreeMax */

} IDBDataHdr, *IDBDataHdrPtr ;

/*

 * The data record

 */

typedef struct {

	IDBDataHdr	data_header ;	/* Header part of record. Initial

					   values: free_ptr = &.data[0],

					   free_count = IDBDataFreeMax */

	char		data[1] ;	/* First available byte for data */

} IDBDataRecord, *IDBDataRecordPtr ;

/*

 * Max number of free bytes in data record

 */

#define	IDBDataFreeMax		(IDBRecordSize - sizeof(IDBDataHdr))

/*

 * Max number of bytes of data which can be stored as simple or overflow

 * entries in a data record.

 */

#define	IDBDataSimpleMax	(IDBDataFreeMax - IDBSimpleDataHdrSize)

#define	IDBDataOverflowMax	(IDBDataFreeMax - IDBOverflowDataHdrSize)

/*

 * In-memory definitions

 *

 * The following structs are used to save runtime informtion used

 * by IDB. These definitions cover file management and buffer management.

 */

/*

 * The IDBOpenFile/IDBFile struct is defined in Mrm.h

 */

/*

 * Buffer management

 *

 * IDB manages a pool of record buffers which is shared among all open

 * IDB files. All access to these buffers is via the IDB buffer manager,

 * which must be used in all requests to access these buffers for

 * either reading or writing.

 */

/*

 * IDB buffer header

 */

#define	IDBRecordBufferValid	327711354

typedef struct {

	unsigned	validation ;	/* validation code =

					   IDBRecordBufferValid */

	long int	activity ;	/* activity count to determine

					   moldiest buffer */

	IDBFile		cur_file ;	/* file which currently owns buffer */

	MrmCode		access ;	/* URMReadAccess or URMWriteAccess */

	MrmCode		modified ;	/* t if buffer has been modified */

	IDBDummyRecord	*IDB_record ;	/* record in buffer */

} IDBRecordBuffer, *IDBRecordBufferPtr ;

/*

 * Macro which validates a buffer

 */

#define	Idb__BM_Valid(bufptr) ((bufptr)->validation==IDBRecordBufferValid)

/*

 * Macros which return the record type, number of the record in a buffer

 */

#define _IdbBufferRecordType(bufptr) ((bufptr)->IDB_record->header.record_type)

#define _IdbBufferRecordNumber(bufptr) ((bufptr)->IDB_record->header.record_num)

#endif /* idb_h */

/* DON'T ADD STUFF AFTER THIS #endif */