/* * @OPENGROUP_COPYRIGHT@ * COPYRIGHT NOTICE * Copyright (c) 1990, 1991, 1992, 1993 Open Software Foundation, Inc. * Copyright (c) 1996, 1997, 1998, 1999, 2000 The Open Group * ALL RIGHTS RESERVED (MOTIF). See the file named COPYRIGHT.MOTIF for * the full copyright text. * * This software is subject to an open license. It may only be * used on, with or for operating systems which are themselves open * source systems. You must contact The Open Group for a license * allowing distribution and sublicensing of this software on, with, * or for operating systems which are not Open Source programs. * * See http://www.opengroup.org/openmotif/license for full * details of the license agreement. Any use, reproduction, or * distribution of the program constitutes recipient's acceptance of * this agreement. * * EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS * PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, EITHER EXPRESS OR IMPLIED INCLUDING, WITHOUT LIMITATION, ANY * WARRANTIES OR CONDITIONS OF TITLE, NON-INFRINGEMENT, MERCHANTABILITY * OR FITNESS FOR A PARTICULAR PURPOSE * * EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT * NOR ANY CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING WITHOUT LIMITATION LOST PROFITS), HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * ANY WAY OUT OF THE USE OR DISTRIBUTION OF THE PROGRAM OR THE * EXERCISE OF ANY RIGHTS GRANTED HEREUNDER, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGES. */ /* * 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 */