1 /* 2 * Motif 3 * 4 * Copyright (c) 1987-2012, The Open Group. All rights reserved. 5 * 6 * These libraries and programs are free software; you can 7 * redistribute them and/or modify them under the terms of the GNU 8 * Lesser General Public License as published by the Free Software 9 * Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * These libraries and programs are distributed in the hope that 13 * they will be useful, but WITHOUT ANY WARRANTY; without even the 14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 15 * PURPOSE. See the GNU Lesser General Public License for more 16 * details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with these librararies and programs; if not, write 20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth 21 * Floor, Boston, MA 02110-1301 USA 22 */ 23 24 #ifndef idb_h 25 #define idb_h 1 26 27 /* 28 * This file defines the constants and structs required by the URM 29 * Indexed Data Base facility (IDB). The order of definition is: 30 * o literals 31 * o primitive typedefs 32 * o typedefs for file records 33 * o typedefs for in-memory structures 34 */ 35 36 37 /* 38 * IDB literals 39 */ 40 41 42 /* 43 * Primitive typedefs 44 */ 45 46 47 /* 48 * A data pointer. Consists of a record number (of a data record) and an 49 * offset in the record to the data entry. 50 */ 51 typedef union { 52 unsigned pointer ; /* the pointer as a value */ 53 struct { 54 IDBRecordNumber rec_no B32 ; /* record number */ 55 MrmOffset item_offs B32 ; /* offset of data entry in 56 record. Must be a 57 IDB*DataEntry struct */ 58 } internal_id ; /* 2 fields internally */ 59 } IDBDataPointer ; 60 61 /* 62 * A data pointer as a passed-by-value reference 63 */ 64 #if 0 65 typedef unsigned IDBDataHandle ; 66 #endif 67 68 typedef struct { 69 IDBRecordNumber rec_no ; /* record number */ 70 MrmOffset item_offs ; /* offset of data entry in 71 record. Must be a 72 IDB*DataEntry struct */ 73 } IDBDataHandle ; 74 75 /* 76 * A data item in a data record. 77 */ 78 79 /* 80 * entry types distinguish simple and overflow records 81 */ 82 #define IDBdrSimple 1 83 #define IDBdrOverflow 2 84 85 86 /* 87 * Common header for both simple and overflow data entries 88 */ 89 #define IDBDataEntryValid 222857390 90 typedef struct { 91 unsigned validation; /* validation code = 92 IDBDataEntryValid */ 93 MrmCode entry_type; /* IDBdrSimple, IDBdrOverflow */ 94 MrmCode resource_group; /* resource group */ 95 MrmCode resource_type; /* resource type */ 96 MrmCode access; /* URMaPrivate or URMaPublic */ 97 MrmCode lock; /* locking code */ 98 MrmSize entry_size; /* number of data bytes */ 99 MrmOffset prev_entry; /* Offset of previous entry in 100 this data record. */ 101 } IDBDataEntryHdr, *IDBDataEntryHdrPtr ; 102 103 #define SwapIDBDataEntryHdr(deh) { \ 104 swap4bytes(deh->validation); \ 105 swap2bytes(deh->entry_type) ; \ 106 swap2bytes(deh->resource_group) ; \ 107 swap2bytes(deh->resource_type) ; \ 108 swap2bytes(deh->access) ; \ 109 swap2bytes(deh->lock) ; \ 110 swap2bytes(deh->entry_size) ; \ 111 swap2bytes(deh->prev_entry) ; \ 112 } 113 114 /* 115 * A simple data entry 116 */ 117 typedef struct { 118 IDBDataEntryHdr header ; /* common header, entry_type = 119 IDBdrSimple */ 120 char data[1] ; /* First byte in data */ 121 } IDBSimpleData, *IDBSimpleDataPtr ; 122 123 124 /* 125 * An overflow data entry. These are used for all data entries which are 126 * too big to fit in a single record. These are broken up into 2 or more 127 * overflow entries, whose contents are concatenated to produce the 128 * actual data entry. 129 */ 130 typedef struct { 131 IDBDataEntryHdr header ; /* common header, entry_type = 132 IDBdrOverflow */ 133 MrmSize segment_size; /* number of data bytes in 134 this segment */ 135 MrmCount segment_count; /* number of records needed 136 to store entry */ 137 MrmCount segment_num; /* this segment's number */ 138 IDBDataPointer next_segment ; /* next segment */ 139 char data[1] ; /* first data byte */ 140 } IDBOverflowData, *IDBOverflowDataPtr ; 141 142 #define SwapIDBOverflowData(doh) { \ 143 swap2bytes(doh->segment_size) ; \ 144 swap2bytes(doh->segment_count) ; \ 145 swap2bytes(doh->segment_num) ; \ 146 swap2bytes(doh->next_segment.internal_id.rec_no) ; \ 147 swap2bytes(doh->next_segment.internal_id.item_offs) ; \ 148 } 149 150 /* 151 * Header sizes for data entries 152 */ 153 #define IDBSimpleDataHdrSize (sizeof(IDBSimpleData) - sizeof(char)) 154 #define IDBOverflowDataHdrSize (sizeof(IDBOverflowData) - sizeof(char)) 155 156 157 158 /* 159 * File record definitions 160 * 161 * IDB uses one size of fixed-length record for all its file records. 162 * The size of this record is determined as a reasonable common size 163 * which gives efficient disk access on all the file systems on which 164 * IDB runs. 165 * 166 * All records are accessed by record number. These increase monotonically 167 * from the lowest valid record number, which is maintained in the file 168 * header. 169 * 170 * IDB defines the following types of records: 171 * Header - one per file 172 * Index leaf - contains leaf nodes of the B-tree index 173 * Index node - contains non-leaf nodes of the B-tree index 174 * RID map - contains pointers which map IDB resourc IDs to 175 * data block pointers 176 * Data - Contains data blocks 177 * 178 * All records have a common record header which gives the record number 179 * and record type. This header and the information for each record type 180 * are defined below. 181 */ 182 183 /* 184 * Number of bytes in a low-level file block = # bytes in an IDB file record 185 */ 186 #define IDBRecordSize 4096 187 188 /* 189 * IDB record header 190 */ 191 #define IDBRecordHeaderValid 310144882 192 typedef struct { 193 unsigned validation; /* validation code = 194 IDBRecordHeaderValid */ 195 MrmType record_type; /* record type */ 196 IDBRecordNumber record_num; /* IDB record number */ 197 } IDBRecordHeader, *IDBRecordHeaderPtr ; 198 199 200 /* 201 * Dummy IDB record. 202 */ 203 typedef struct { 204 IDBRecordHeader header ; 205 char dummy[IDBRecordSize-sizeof(IDBRecordHeader)] ; 206 } IDBDummyRecord, *IDBDummyRecordPtr ; 207 208 209 210 /* 211 * IDB header record definition 212 * 213 * There is one header record per IDB file. It is the only record in the 214 * which must be at a fixed location; its record number is 215 * IDBHeaderRecordNumber. 216 * 217 * The header contains the following: 218 * o Information about how the file was created 219 * o A pointer to the root node record for the B-tree index 220 * o The next available resourc id (RID) 221 * o An end-of-file pointer (record number of last record in file) 222 * o Counters of the number of index and RID entries in the file 223 * o Counter of the different types of records in the file 224 * o The remainder of the record is used as the initial space in 225 * which to allocate a small RID map and data entries. This 226 * enables relatively small files to be created when a small 227 * amount of information will be stored, as the minimal file 228 * need contain only a header and (probably) and index leaf record 229 * rather than also requiring an RID map record and a data record. 230 */ 231 232 /* 233 * IDB file header record header 234 */ 235 typedef struct { 236 IDBRecordHeader header ; /* record_type = 237 IDBrtHeader, 238 record_num = 239 IDBrtHeader, */ 240 char db_version[IDBhsVersion1] ; 241 /* database version */ 242 char creator[IDBhsCreator1] ; /* creator id */ 243 char creator_version[IDBhsVersion1] ; 244 /* creator version */ 245 char creation_date[IDBhsDate1] ; 246 /* creation date */ 247 char module[IDBhsModule1] ; /* module id */ 248 char module_version[IDBhsVersion1] ; 249 /* module version */ 250 IDBRecordNumber index_root ; /* index root pointer */ 251 MrmCount num_indexed ; /* # entries in index */ 252 MrmCount num_RID ; /* # RID entries in file */ 253 IDBridDesc next_RID ; /* next available RID. */ 254 IDBRecordNumber last_record ; /* last record used in file */ 255 IDBRecordNumber last_data_record ; /* last data record in file */ 256 MrmCount group_counts[URMgVecSize] ; 257 /* vector of record counts 258 by resource group */ 259 MrmCount rt_counts[IDBrtVecSize] ; 260 /* vector of record counts by 261 record type (statistics) */ 262 } IDBHeaderHdr, *IDBHeaderHdrPtr ; 263 264 265 /* 266 * IDB file header record 267 * 268 * Max number of entries in RID pointer vector 269 */ 270 #define IDBHeaderRIDMax 20 271 typedef struct { 272 IDBHeaderHdr header_hdr ; /* header part */ 273 IDBDataPointer RID_pointers[IDBHeaderRIDMax]; 274 /* RID pointer vector */ 275 MrmCount num_entry; /* number of entries in record */ 276 MrmOffset last_entry; /* last entry in page */ 277 MrmOffset free_ptr; /* offset of first free byte. 278 initial value = 0 */ 279 MrmCount free_count; /* number of free bytes. Initial 280 value = IDBHeaderFreeMax */ 281 char data[1]; /* First available byte for data */ 282 } IDBHeaderRecord, *IDBHeaderRecordPtr ; 283 284 285 /* 286 * Free space in header record, max number of bytes available for data. 287 */ 288 #define IDBHeaderFreeMax (IDBRecordSize-sizeof(IDBHeaderRecord)+sizeof(char)) 289 290 291 /* 292 * Record number of the header record 293 */ 294 #define IDBHeaderRecordNumber 1 295 296 297 298 /* 299 * Index leaf record definition 300 * 301 * IDB provides two mutually exclusive mechanisms for accessing data. 302 * The first is an index system based on ASCII keys (indexes). This 303 * uses a B-tree index as its lookup mechanism. The second mechanism 304 * is a resource id mechanism offering potentially faster access, as 305 * described below. 306 * 307 * As usual in B-tree systems, the B-tree index has two kinds of nodes: 308 * leaf nodes, which contain only data pointers, and B-tree nodes, 309 * which contain pointers to other B-tree records. The following describes 310 * leaf records in the B-tree index. 311 * 312 * The root node of the index is a leaf record if there is exactly 1 313 * record in the index, and is a tree node otherwise. 314 * 315 * A leaf record consists of a sorted vector of index entries, ordered 316 * in increasing alphabetical order by the index value. The vector 317 * contains fixed-length entries, with the key strings being allocated 318 * at the bottom of the record. The vector grows down from the top and 319 * the string heap up from the bottom as entries are added, until the 320 * record fills. 321 */ 322 323 /* 324 * An entry in the index vector 325 */ 326 typedef struct { 327 MrmOffset index_stg; /* offset of the index string in 328 the record. Nul-terminated. */ 329 IDBDataPointer data ; /* pointer to the data entry */ 330 } IDBIndexLeafEntry, *IDBIndexLeafEntryPtr ; 331 332 /* 333 * Size of an index vector entry 334 */ 335 #define IDBIndexLeafEntrySize sizeof(IDBIndexLeafEntry) 336 337 /* 338 * Max length of an index string (terminating nul not included) 339 */ 340 #define IDBMaxIndexLength URMMaxIndexLen 341 #define IDBMaxIndexLength1 (IDBMaxIndexLength + 1) 342 343 344 /* 345 * Leaf record header 346 */ 347 typedef struct { 348 IDBRecordHeader header ; /* record_type = IDBrtIndexLeaf */ 349 IDBRecordNumber parent; /* B-tree parent record */ 350 MrmCount index_count; /* Number of index entries in record */ 351 MrmOffset heap_start; /* Offset of first byte in use for 352 index string heap storage. Offset 353 is from .index[0] */ 354 MrmCount free_bytes; /* Number of free bytes in record */ 355 } IDBIndexLeafHdr, *IDBIndexLeafHdrPtr ; 356 357 358 /* 359 * The leaf record 360 */ 361 typedef struct { 362 IDBIndexLeafHdr leaf_header ; /* header part of record. Initial 363 values: heap_start = 364 free_bytes = IDBIndexLeafFreeMax */ 365 IDBIndexLeafEntry index[1] ; /* First entry in index vector. There 366 are index_count entries. */ 367 } IDBIndexLeafRecord, *IDBIndexLeafRecordPtr ; 368 369 370 /* 371 * Max number of free bytes in leaf index record (0 entries) 372 */ 373 #define IDBIndexLeafFreeMax (IDBRecordSize - sizeof(IDBIndexLeafHdr)) 374 375 376 377 /* 378 * Index B-tree node record definition 379 * 380 * A B-tree node record is similar to a leaf entry, except that each node 381 * contains a pair of pointers to other nodes in the tree; one to a LT 382 * node, all of whose entries order < the entry's index; one to a GT node, 383 * all of whose entries order > the entry's index. The GT pointer of node 384 * m = the LT pointer of node m+1. Thus any node record containing n nodes 385 * points to n+1 tree nodes. Allocation of heap for index strings is as in 386 * a leaf record. All entries also locate a data entry. 387 */ 388 389 /* 390 * An entry in the index vector 391 */ 392 typedef struct { 393 MrmOffset index_stg; /* offset of the index string in 394 the record. Nul-terminated. */ 395 IDBDataPointer data ; /* pointer to the data entry */ 396 IDBRecordNumber LT_record; /* pointer to LT record */ 397 IDBRecordNumber GT_record; /* pointer to GT record */ 398 } IDBIndexNodeEntry, *IDBIndexNodeEntryPtr ; 399 400 /* 401 * Size of an index vector entry 402 */ 403 #define IDBIndexNodeEntrySize sizeof(IDBIndexNodeEntry) 404 405 /* 406 * Node record header 407 */ 408 typedef struct { 409 IDBRecordHeader header ; /* record_type = IDBrtIndexNode */ 410 IDBRecordNumber parent; /* B-tree parent record */ 411 MrmCount index_count; /* Number of index entries in record */ 412 MrmOffset heap_start; /* Offset of first byte in use for 413 index string heap storage. Offset 414 is from .index[0] */ 415 MrmCount free_bytes; /* Number of free bytes in record */ 416 } IDBIndexNodeHdr, *IDBIndexNodeHdrPtr ; 417 418 419 /* 420 * The B-tree node entry 421 */ 422 typedef struct { 423 IDBIndexNodeHdr node_header ; /* header part of record. Initial 424 values: heap_start = 425 free_bytes = IDBIndexNodeFreeMax */ 426 IDBIndexNodeEntry index[1] ; /* First entry in index vector. There 427 are index_count entries. */ 428 } IDBIndexNodeRecord, *IDBIndexNodeRecordPtr ; 429 430 431 /* 432 * Max number of free bytes in node index record (0 entries) 433 */ 434 #define IDBIndexNodeFreeMax (IDBRecordSize - sizeof(IDBIndexNodeHdr)) 435 436 /* 437 * Max number of bytes consumed by a new entry 438 */ 439 #define IDBIndexNodeEntryMax (IDBMaxIndexLength1 + IDBIndexNodeEntrySize \ 440 + sizeof(IDBRecordNumber)) 441 442 443 444 /* 445 * Resource ID record 446 * 447 * RID records locate the data block associated with a given resource ID. 448 * Looking up a data block accessed by RID is a two-step process: 449 * 1. The index map in the file header (maintained in-memory for open 450 * files) is used to locate the correct resource ID record. The 451 * map_index field in a RID descriptor accesses this record via 452 * the RID_maps vector in the header. 453 * 2. The Resource ID record supplies the data block pointer. The 454 * data block pointer is found in the resource_ptr vector using the 455 * res_index field of the RID descriptor. 456 * 457 * Aside from the standard record header, an RID record contains only 458 * a vector of data block pointer. 459 */ 460 461 /* 462 * The RID map record header 463 */ 464 typedef struct { 465 IDBRecordHeader header ; /* record type = IDBrdRIDMap */ 466 } IDBridMapHdr, *IDBridMapHdrPtr ; 467 468 /* 469 * The RID map record is a vector of data pointers 470 */ 471 typedef struct { 472 IDBridMapHdr map_header ; /* Header part of record */ 473 IDBDataPointer pointers[1] ; /* First pointer in vector. */ 474 } IDBridMapRecord, *IDBridMapRecordPtr ; 475 476 /* 477 * Max number of free bytes, number of vector entries in RID record 478 */ 479 #define IDBridFreeMax (IDBRecordSize - sizeof(IDBridMapHdr)) 480 #define IDBridPtrVecMax (IDBridFreeMax / sizeof(IDBDataPointer)) 481 482 483 484 /* 485 * Data record 486 * 487 * Data records hold data entries. The record maintains a free space 488 * pointer, but otherwise contains little information. IDB attempts 489 * to avoid splitting data entries into segments, and is thus willing 490 * to waste some space in a data record if a data item will fit in 491 * a new record. 492 * 493 * All the data entries in a record are chained via the prev_entry offset 494 * field. This is for the convenience of the dump routines. The first 495 * entry is always at offset 0 (= initial value of free ptr). 496 */ 497 498 /* 499 * The data record header 500 */ 501 typedef struct { 502 IDBRecordHeader header ; /* record = IDBrtData */ 503 MrmCount num_entry; /* number of entries in record */ 504 MrmOffset last_entry; /* last entry in page */ 505 MrmOffset free_ptr; /* offset of first free byte. 506 initial value = 0 */ 507 MrmCount free_count; /* number of free bytes. Initial 508 value = IDBDataFreeMax */ 509 } IDBDataHdr, *IDBDataHdrPtr ; 510 511 512 /* 513 * The data record 514 */ 515 typedef struct { 516 IDBDataHdr data_header ; /* Header part of record. Initial 517 values: free_ptr = &.data[0], 518 free_count = IDBDataFreeMax */ 519 char data[1] ; /* First available byte for data */ 520 } IDBDataRecord, *IDBDataRecordPtr ; 521 522 523 /* 524 * Max number of free bytes in data record 525 */ 526 #define IDBDataFreeMax (IDBRecordSize - sizeof(IDBDataHdr)) 527 528 529 /* 530 * Max number of bytes of data which can be stored as simple or overflow 531 * entries in a data record. 532 */ 533 #define IDBDataSimpleMax (IDBDataFreeMax - IDBSimpleDataHdrSize) 534 #define IDBDataOverflowMax (IDBDataFreeMax - IDBOverflowDataHdrSize) 535 536 537 538 /* 539 * In-memory definitions 540 * 541 * The following structs are used to save runtime informtion used 542 * by IDB. These definitions cover file management and buffer management. 543 */ 544 545 /* 546 * The IDBOpenFile/IDBFile struct is defined in Mrm.h 547 */ 548 549 /* 550 * Buffer management 551 * 552 * IDB manages a pool of record buffers which is shared among all open 553 * IDB files. All access to these buffers is via the IDB buffer manager, 554 * which must be used in all requests to access these buffers for 555 * either reading or writing. 556 */ 557 558 /* 559 * IDB buffer header 560 */ 561 #define IDBRecordBufferValid 327711354 562 typedef struct { 563 unsigned validation ; /* validation code = 564 IDBRecordBufferValid */ 565 long int activity ; /* activity count to determine 566 moldiest buffer */ 567 IDBFile cur_file ; /* file which currently owns buffer */ 568 MrmCode access ; /* URMReadAccess or URMWriteAccess */ 569 MrmCode modified ; /* t if buffer has been modified */ 570 IDBDummyRecord *IDB_record ; /* record in buffer */ 571 } IDBRecordBuffer, *IDBRecordBufferPtr ; 572 573 574 /* 575 * Macro which validates a buffer 576 */ 577 #define Idb__BM_Valid(bufptr) ((bufptr)->validation==IDBRecordBufferValid) 578 579 /* 580 * Macros which return the record type, number of the record in a buffer 581 */ 582 #define _IdbBufferRecordType(bufptr) ((bufptr)->IDB_record->header.record_type) 583 #define _IdbBufferRecordNumber(bufptr) ((bufptr)->IDB_record->header.record_num) 584 585 #endif /* idb_h */ 586 /* DON'T ADD STUFF AFTER THIS #endif */ 587