00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 * 00007 * $Id: db__page_8h-source.html,v 1.1 2008年06月08日 10:17:56 sebdiaz Exp $ 00008 */ 00009 00010 #ifndef _DB_PAGE_H_ 00011 #define _DB_PAGE_H_ 00012 00013 #if defined(__cplusplus) 00014 extern "C" { 00015 #endif 00016 00017 /* 00018 * DB page formats. 00019 * 00020 * !!! 00021 * This implementation requires that values within the following structures 00022 * NOT be padded -- note, ANSI C permits random padding within structures. 00023 * If your compiler pads randomly you can just forget ever making DB run on 00024 * your system. In addition, no data type can require larger alignment than 00025 * its own size, e.g., a 4-byte data element may not require 8-byte alignment. 00026 * 00027 * Note that key/data lengths are often stored in db_indx_t's -- this is 00028 * not accidental, nor does it limit the key/data size. If the key/data 00029 * item fits on a page, it's guaranteed to be small enough to fit into a 00030 * db_indx_t, and storing it in one saves space. 00031 */ 00032 00033 #define PGNO_INVALID 0 /* Invalid page number in any database. */ 00034 #define PGNO_BASE_MD 1 /* Base database: metadata page number. */ 00035 00036 /* Page types. */ 00037 #define P_INVALID 0 /* Invalid page type. */ 00038 #define __P_DUPLICATE 1 /* Duplicate. DEPRECATED in 3.1 */ 00039 #define P_HASH 2 /* Hash. */ 00040 #define P_IBTREE 3 /* Btree internal. */ 00041 #define P_IRECNO 4 /* Recno internal. */ 00042 #define P_LBTREE 5 /* Btree leaf. */ 00043 #define P_LRECNO 6 /* Recno leaf. */ 00044 #define P_OVERFLOW 7 /* Overflow. */ 00045 #define P_HASHMETA 8 /* Hash metadata page. */ 00046 #define P_BTREEMETA 9 /* Btree metadata page. */ 00047 #define P_QAMMETA 10 /* Queue metadata page. */ 00048 #define P_QAMDATA 11 /* Queue data page. */ 00049 #define P_LDUP 12 /* Off-page duplicate leaf. */ 00050 /* 00051 * These page types are artificially built by io compression 00052 * when trying to access a page number that is not the 00053 * beginning of a page compression chain. 00054 * Utilities that walk the file by incrementing the page 00055 * number can make use of these page types or safely consider 00056 * them as equivalent to P_INVALID. 00057 */ 00058 #define P_CMPR_INTERNAL 13 /* Compression internal page. */ 00059 #define P_CMPR_FREE 14 /* Compression free page. */ 00060 #define P_PAGETYPE_MAX 15 00061 00062 /* 00063 * When we create pages in mpool, we ask mpool to clear some number of bytes 00064 * in the header. This number must be at least as big as the regular page 00065 * headers and cover enough of the btree and hash meta-data pages to obliterate 00066 * the page type. 00067 */ 00068 #define DB_PAGE_DB_LEN 32 00069 #define DB_PAGE_QUEUE_LEN 0 00070 00071 /************************************************************************ 00072 GENERIC METADATA PAGE HEADER 00073 * 00074 * !!! 00075 * The magic and version numbers have to be in the same place in all versions 00076 * of the metadata page as the application may not have upgraded the database. 00077 ************************************************************************/ 00078 typedef struct _dbmeta31 { 00079 DB_LSN lsn; /* 00-07: LSN. */ 00080 db_pgno_t pgno; /* 08-11: Current page number. */ 00081 u_int32_t magic; /* 12-15: Magic number. */ 00082 u_int32_t version; /* 16-19: Version. */ 00083 u_int32_t pagesize; /* 20-23: Pagesize. */ 00084 u_int8_t unused1[1]; /* 24: Unused. */ 00085 u_int8_t type; /* 25: Page type. */ 00086 u_int8_t unused2[2]; /* 26-27: Unused. */ 00087 u_int32_t free; /* 28-31: Free list page number. */ 00088 DB_LSN alloc_lsn; /* 32-39: Lsn for allocation */ 00089 u_int32_t key_count; /* 40-43: Cached key count. */ 00090 u_int32_t record_count; /* 44-47: Cached record count. */ 00091 u_int32_t flags; /* 48-51: Flags: unique to each AM. */ 00092 /* 52-71: Unique file ID. */ 00093 u_int8_t uid[DB_FILE_ID_LEN]; 00094 } DBMETA31, DBMETA; 00095 00096 /************************************************************************ 00097 BTREE METADATA PAGE LAYOUT 00098 ************************************************************************/ 00099 typedef struct _btmeta31 { 00100 #define BTM_DUP 0x001 /* Duplicates. */ 00101 #define BTM_RECNO 0x002 /* Recno tree. */ 00102 #define BTM_RECNUM 0x004 /* Btree: maintain record count. */ 00103 #define BTM_FIXEDLEN 0x008 /* Recno: fixed length records. */ 00104 #define BTM_RENUMBER 0x010 /* Recno: renumber on insert/delete. */ 00105 #define BTM_SUBDB 0x020 /* Subdatabases. */ 00106 #define BTM_DUPSORT 0x040 /* Duplicates are sorted. */ 00107 #define BTM_MASK 0x07f 00108 DBMETA dbmeta; /* 00-71: Generic meta-data header. */ 00109 00110 u_int32_t maxkey; /* 72-75: Btree: Maxkey. */ 00111 u_int32_t minkey; /* 76-79: Btree: Minkey. */ 00112 u_int32_t re_len; /* 80-83: Recno: fixed-length record length. */ 00113 u_int32_t re_pad; /* 84-87: Recno: fixed-length record pad. */ 00114 u_int32_t root; /* 88-92: Root page. */ 00115 00116 /* 00117 * Minimum page size is 128. 00118 */ 00119 } BTMETA31, BTMETA; 00120 00121 /************************************************************************ 00122 HASH METADATA PAGE LAYOUT 00123 ************************************************************************/ 00124 typedef struct _hashmeta31 { 00125 #define DB_HASH_DUP 0x01 /* Duplicates. */ 00126 #define DB_HASH_SUBDB 0x02 /* Subdatabases. */ 00127 #define DB_HASH_DUPSORT 0x04 /* Duplicates are sorted. */ 00128 DBMETA dbmeta; /* 00-71: Generic meta-data page header. */ 00129 00130 u_int32_t max_bucket; /* 72-75: ID of Maximum bucket in use */ 00131 u_int32_t high_mask; /* 76-79: Modulo mask into table */ 00132 u_int32_t low_mask; /* 80-83: Modulo mask into table lower half */ 00133 u_int32_t ffactor; /* 84-87: Fill factor */ 00134 u_int32_t nelem; /* 88-91: Number of keys in hash table */ 00135 u_int32_t h_charkey; /* 92-95: Value of hash(CHARKEY) */ 00136 #define NCACHED 32 /* number of spare points */ 00137 /* 96-223: Spare pages for overflow */ 00138 u_int32_t spares[NCACHED]; 00139 00140 /* 00141 * Minimum page size is 256. 00142 */ 00143 } HMETA31, HMETA; 00144 00145 /************************************************************************ 00146 QUEUE METADATA PAGE LAYOUT 00147 ************************************************************************/ 00148 /* 00149 * QAM Meta data page structure 00150 * 00151 */ 00152 typedef struct _qmeta31 { 00153 DBMETA dbmeta; /* 00-71: Generic meta-data header. */ 00154 00155 u_int32_t start; /* 72-75: Start offset. */ 00156 u_int32_t first_recno; /* 76-79: First not deleted record. */ 00157 u_int32_t cur_recno; /* 80-83: Last recno allocated. */ 00158 u_int32_t re_len; /* 84-87: Fixed-length record length. */ 00159 u_int32_t re_pad; /* 88-91: Fixed-length record pad. */ 00160 u_int32_t rec_page; /* 92-95: Records Per Page. */ 00161 00162 /* 00163 * Minimum page size is 128. 00164 */ 00165 } QMETA31, QMETA; 00166 00167 /* 00168 * DBMETASIZE is a constant used by __db_file_setup and DB->verify 00169 * as a buffer which is guaranteed to be larger than any possible 00170 * metadata page size and smaller than any disk sector. 00171 */ 00172 #define DBMETASIZE 256 00173 00174 /************************************************************************ 00175 BTREE/HASH MAIN PAGE LAYOUT 00176 ************************************************************************/ 00177 /* 00178 * +-----------------------------------+ 00179 * | lsn | pgno | prev pgno | 00180 * +-----------------------------------+ 00181 * | next pgno | entries | hf offset | 00182 * +-----------------------------------+ 00183 * | level | type | index | 00184 * +-----------------------------------+ 00185 * | index | free --> | 00186 * +-----------+-----------------------+ 00187 * | F R E E A R E A | 00188 * +-----------------------------------+ 00189 * | <-- free | item | 00190 * +-----------------------------------+ 00191 * | item | item | item | 00192 * +-----------------------------------+ 00193 * 00194 * sizeof(PAGE) == 26 bytes, and the following indices are guaranteed to be 00195 * two-byte aligned. 00196 * 00197 * For hash and btree leaf pages, index items are paired, e.g., inp[0] is the 00198 * key for inp[1]'s data. All other types of pages only contain single items. 00199 */ 00200 typedef struct _db_page { 00201 DB_LSN lsn; /* 00-07: Log sequence number. */ 00202 db_pgno_t pgno; /* 08-11: Current page number. */ 00203 db_pgno_t prev_pgno; /* 12-15: Previous page number. */ 00204 db_pgno_t next_pgno; /* 16-19: Next page number. */ 00205 db_indx_t entries; /* 20-21: Number of items on the page. */ 00206 db_indx_t hf_offset; /* 22-23: High free byte page offset. */ 00207 00208 /* 00209 * The btree levels are numbered from the leaf to the root, starting 00210 * with 1, so the leaf is level 1, its parent is level 2, and so on. 00211 * We maintain this level on all btree pages, but the only place that 00212 * we actually need it is on the root page. It would not be difficult 00213 * to hide the byte on the root page once it becomes an internal page, 00214 * so we could get this byte back if we needed it for something else. 00215 */ 00216 #define LEAFLEVEL 1 00217 #define MAXBTREELEVEL 255 00218 u_int8_t level; /* 24: Btree tree level. */ 00219 u_int8_t type; /* 25: Page type. */ 00220 db_indx_t inp[1]; /* Variable length index of items. */ 00221 } PAGE; 00222 00223 #define TYPE_MASK 0x0f 00224 #define TAGS_MASK 0xf0 00225 00226 /* PAGE element macros. */ 00227 #define LSN(p) (((PAGE *)p)->lsn) 00228 #define PGNO(p) (((PAGE *)p)->pgno) 00229 #define PREV_PGNO(p) (((PAGE *)p)->prev_pgno) 00230 #define NEXT_PGNO(p) (((PAGE *)p)->next_pgno) 00231 #define NUM_ENT(p) (((PAGE *)p)->entries) 00232 #define HOFFSET(p) (((PAGE *)p)->hf_offset) 00233 #define LEVEL(p) (((PAGE *)p)->level) 00234 #define TYPE(p) ((((PAGE *)p)->type) & TYPE_MASK) 00235 #define TYPE_SET(p,v) (TYPE_TAGS(p) = ((v) & TYPE_MASK) | TAGS(p)) 00236 #define TYPE_TAGS(p) (((PAGE *)p)->type) 00237 #define TAGS(p) (((PAGE *)p)->type & TAGS_MASK) 00238 #define TAGS_SET(p,v) (TYPE_TAGS(p) = TYPE(p) | ((v) & TAGS_MASK)) 00239 00240 /************************************************************************ 00241 QUEUE MAIN PAGE LAYOUT 00242 ************************************************************************/ 00243 typedef struct _qpage { 00244 DB_LSN lsn; /* 00-07: Log sequence number. */ 00245 db_pgno_t pgno; /* 08-11: Current page number. */ 00246 u_int32_t unused0[3]; /* 12-23: Unused. */ 00247 u_int8_t unused1[1]; /* 24: Unused. */ 00248 u_int8_t type; /* 25: Page type. */ 00249 u_int8_t unused2[2]; /* 26-27: Unused. */ 00250 } QPAGE; 00251 00252 /* 00253 * !!! 00254 * The next_pgno and prev_pgno fields are not maintained for btree and recno 00255 * internal pages. Doing so only provides a minor performance improvement, 00256 * it's hard to do when deleting internal pages, and it increases the chance 00257 * of deadlock during deletes and splits because we have to re-link pages at 00258 * more than the leaf level. 00259 * 00260 * !!! 00261 * The btree/recno access method needs db_recno_t bytes of space on the root 00262 * page to specify how many records are stored in the tree. (The alternative 00263 * is to store the number of records in the meta-data page, which will create 00264 * a second hot spot in trees being actively modified, or recalculate it from 00265 * the BINTERNAL fields on each access.) Overload the PREV_PGNO field. 00266 */ 00267 #define RE_NREC(p) \ 00268 ((TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO) ? \ 00269 PREV_PGNO(p) : (TYPE(p) == P_LBTREE ? NUM_ENT(p) / 2 : NUM_ENT(p))) 00270 #define RE_NREC_ADJ(p, adj) \ 00271 PREV_PGNO(p) += adj; 00272 #define RE_NREC_SET(p, num) \ 00273 PREV_PGNO(p) = num; 00274 00275 /* 00276 * Initialize a page. 00277 * 00278 * !!! 00279 * Don't modify the page's LSN, code depends on it being unchanged after a 00280 * P_INIT call. 00281 */ 00282 #define P_INIT(pg, pg_size, n, pg_prev, pg_next, btl, pg_type, pg_tags) do {\ 00283 PGNO(pg) = n; \ 00284 PREV_PGNO(pg) = pg_prev; \ 00285 NEXT_PGNO(pg) = pg_next; \ 00286 NUM_ENT(pg) = 0; \ 00287 HOFFSET(pg) = pg_size; \ 00288 LEVEL(pg) = btl; \ 00289 TYPE_TAGS(pg) = (pg_type | pg_tags); \ 00290 } while (0) 00291 00292 /* Page header length (offset to first index). */ 00293 #define P_OVERHEAD (SSZA(PAGE, inp)) 00294 00295 /* First free byte. */ 00296 #define LOFFSET(pg) (P_OVERHEAD + NUM_ENT(pg) * sizeof(db_indx_t)) 00297 00298 /* Free space on a regular page. */ 00299 #define P_FREESPACE(pg) (HOFFSET(pg) - LOFFSET(pg)) 00300 00301 /* Get a pointer to the bytes at a specific index. */ 00302 #define P_ENTRY(pg, indx) ((u_int8_t *)pg + ((PAGE *)pg)->inp[indx]) 00303 00304 /************************************************************************ 00305 OVERFLOW PAGE LAYOUT 00306 ************************************************************************/ 00307 00308 /* 00309 * Overflow items are referenced by HOFFPAGE and BOVERFLOW structures, which 00310 * store a page number (the first page of the overflow item) and a length 00311 * (the total length of the overflow item). The overflow item consists of 00312 * some number of overflow pages, linked by the next_pgno field of the page. 00313 * A next_pgno field of PGNO_INVALID flags the end of the overflow item. 00314 * 00315 * Overflow page overloads: 00316 * The amount of overflow data stored on each page is stored in the 00317 * hf_offset field. 00318 * 00319 * The implementation reference counts overflow items as it's possible 00320 * for them to be promoted onto btree internal pages. The reference 00321 * count is stored in the entries field. 00322 */ 00323 #define OV_LEN(p) (((PAGE *)p)->hf_offset) 00324 #define OV_REF(p) (((PAGE *)p)->entries) 00325 00326 /* Maximum number of bytes that you can put on an overflow page. */ 00327 #define P_MAXSPACE(psize) ((psize) - P_OVERHEAD) 00328 00329 /* Free space on an overflow page. */ 00330 #define P_OVFLSPACE(psize, pg) (P_MAXSPACE(psize) - HOFFSET(pg)) 00331 00332 /************************************************************************ 00333 HASH PAGE LAYOUT 00334 ************************************************************************/ 00335 00336 /* Each index references a group of bytes on the page. */ 00337 #define H_KEYDATA 1 /* Key/data item. */ 00338 #define H_DUPLICATE 2 /* Duplicate key/data item. */ 00339 #define H_OFFPAGE 3 /* Overflow key/data item. */ 00340 #define H_OFFDUP 4 /* Overflow page of duplicates. */ 00341 00342 /* 00343 * !!! 00344 * Items on hash pages are (potentially) unaligned, so we can never cast the 00345 * (page + offset) pointer to an HKEYDATA, HOFFPAGE or HOFFDUP structure, as 00346 * we do with B+tree on-page structures. Because we frequently want the type 00347 * field, it requires no alignment, and it's in the same location in all three 00348 * structures, there's a pair of macros. 00349 */ 00350 #define HPAGE_PTYPE(p) (*(u_int8_t *)p) 00351 #define HPAGE_TYPE(pg, indx) (*P_ENTRY(pg, indx)) 00352 00353 /* 00354 * The first and second types are H_KEYDATA and H_DUPLICATE, represented 00355 * by the HKEYDATA structure: 00356 * 00357 * +-----------------------------------+ 00358 * | type | key/data ... | 00359 * +-----------------------------------+ 00360 * 00361 * For duplicates, the data field encodes duplicate elements in the data 00362 * field: 00363 * 00364 * +---------------------------------------------------------------+ 00365 * | type | len1 | element1 | len1 | len2 | element2 | len2 | 00366 * +---------------------------------------------------------------+ 00367 * 00368 * Thus, by keeping track of the offset in the element, we can do both 00369 * backward and forward traversal. 00370 */ 00371 typedef struct _hkeydata { 00372 u_int8_t type; /* 00: Page type. */ 00373 u_int8_t data[1]; /* Variable length key/data item. */ 00374 } HKEYDATA; 00375 #define HKEYDATA_DATA(p) (((u_int8_t *)p) + SSZA(HKEYDATA, data)) 00376 00377 /* 00378 * The length of any HKEYDATA item. Note that indx is an element index, 00379 * not a PAIR index. 00380 */ 00381 #define LEN_HITEM(pg, pgsize, indx) \ 00382 (((indx) == 0 ? pgsize : \ 00383 ((PAGE *)(pg))->inp[indx - 1]) - ((PAGE *)(pg))->inp[indx]) 00384 00385 #define LEN_HKEYDATA(pg, psize, indx) \ 00386 (((indx) == 0 ? psize : ((PAGE *)(pg))->inp[indx - 1]) - \ 00387 ((PAGE *)(pg))->inp[indx] - HKEYDATA_SIZE(0)) 00388 00389 /* 00390 * Page space required to add a new HKEYDATA item to the page, with and 00391 * without the index value. 00392 */ 00393 #define HKEYDATA_SIZE(len) \ 00394 ((len) + SSZA(HKEYDATA, data)) 00395 #define HKEYDATA_PSIZE(len) \ 00396 (HKEYDATA_SIZE(len) + sizeof(db_indx_t)) 00397 00398 /* Put a HKEYDATA item at the location referenced by a page entry. */ 00399 #define PUT_HKEYDATA(pe, kd, len, type) { \ 00400 ((HKEYDATA *)pe)->type = type; \ 00401 memcpy((u_int8_t *)pe + sizeof(u_int8_t), kd, len); \ 00402 } 00403 00404 /* 00405 * Macros the describe the page layout in terms of key-data pairs. 00406 */ 00407 #define H_NUMPAIRS(pg) (NUM_ENT(pg) / 2) 00408 #define H_KEYINDEX(indx) (indx) 00409 #define H_DATAINDEX(indx) ((indx) + 1) 00410 #define H_PAIRKEY(pg, indx) P_ENTRY(pg, H_KEYINDEX(indx)) 00411 #define H_PAIRDATA(pg, indx) P_ENTRY(pg, H_DATAINDEX(indx)) 00412 #define H_PAIRSIZE(pg, psize, indx) \ 00413 (LEN_HITEM(pg, psize, H_KEYINDEX(indx)) + \ 00414 LEN_HITEM(pg, psize, H_DATAINDEX(indx))) 00415 #define LEN_HDATA(p, psize, indx) LEN_HKEYDATA(p, psize, H_DATAINDEX(indx)) 00416 #define LEN_HKEY(p, psize, indx) LEN_HKEYDATA(p, psize, H_KEYINDEX(indx)) 00417 00418 /* 00419 * The third type is the H_OFFPAGE, represented by the HOFFPAGE structure: 00420 */ 00421 typedef struct _hoffpage { 00422 u_int8_t type; /* 00: Page type and delete flag. */ 00423 u_int8_t unused[3]; /* 01-03: Padding, unused. */ 00424 db_pgno_t pgno; /* 04-07: Offpage page number. */ 00425 u_int32_t tlen; /* 08-11: Total length of item. */ 00426 } HOFFPAGE; 00427 00428 #define HOFFPAGE_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, pgno)) 00429 #define HOFFPAGE_TLEN(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, tlen)) 00430 00431 /* 00432 * Page space required to add a new HOFFPAGE item to the page, with and 00433 * without the index value. 00434 */ 00435 #define HOFFPAGE_SIZE (sizeof(HOFFPAGE)) 00436 #define HOFFPAGE_PSIZE (HOFFPAGE_SIZE + sizeof(db_indx_t)) 00437 00438 /* 00439 * The fourth type is H_OFFDUP represented by the HOFFDUP structure: 00440 */ 00441 typedef struct _hoffdup { 00442 u_int8_t type; /* 00: Page type and delete flag. */ 00443 u_int8_t unused[3]; /* 01-03: Padding, unused. */ 00444 db_pgno_t pgno; /* 04-07: Offpage page number. */ 00445 } HOFFDUP; 00446 #define HOFFDUP_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFDUP, pgno)) 00447 00448 /* 00449 * Page space required to add a new HOFFDUP item to the page, with and 00450 * without the index value. 00451 */ 00452 #define HOFFDUP_SIZE (sizeof(HOFFDUP)) 00453 #define HOFFDUP_PSIZE (HOFFDUP_SIZE + sizeof(db_indx_t)) 00454 00455 /************************************************************************ 00456 BTREE PAGE LAYOUT 00457 ************************************************************************/ 00458 00459 /* Each index references a group of bytes on the page. */ 00460 #define B_KEYDATA 1 /* Key/data item. */ 00461 #define B_DUPLICATE 2 /* Duplicate key/data item. */ 00462 #define B_OVERFLOW 3 /* Overflow key/data item. */ 00463 00464 /* 00465 * We have to store a deleted entry flag in the page. The reason is complex, 00466 * but the simple version is that we can't delete on-page items referenced by 00467 * a cursor -- the return order of subsequent insertions might be wrong. The 00468 * delete flag is an overload of the top bit of the type byte. 00469 */ 00470 #define B_DELETE (0x80) 00471 #define B_DCLR(t) (t) &= ~B_DELETE 00472 #define B_DSET(t) (t) |= B_DELETE 00473 #define B_DISSET(t) ((t) & B_DELETE) 00474 00475 #define B_TYPE(t) ((t) & ~B_DELETE) 00476 #define B_TSET(t, type, deleted) { \ 00477 (t) = (type); \ 00478 if (deleted) \ 00479 B_DSET(t); \ 00480 } 00481 00482 /* 00483 * The first type is B_KEYDATA, represented by the BKEYDATA structure: 00484 */ 00485 typedef struct _bkeydata { 00486 db_indx_t len; /* 00-01: Key/data item length. */ 00487 u_int8_t type; /* 02: Page type AND DELETE FLAG. */ 00488 u_int8_t data[1]; /* Variable length key/data item. */ 00489 } BKEYDATA; 00490 00491 /* Get a BKEYDATA item for a specific index. */ 00492 #define GET_BKEYDATA(pg, indx) \ 00493 ((BKEYDATA *)P_ENTRY(pg, indx)) 00494 00495 /* 00496 * Page space required to add a new BKEYDATA item to the page, with and 00497 * without the index value. 00498 */ 00499 #define BKEYDATA_SIZE(len) \ 00500 ALIGN((len) + SSZA(BKEYDATA, data), 4) 00501 #define BKEYDATA_PSIZE(len) \ 00502 (BKEYDATA_SIZE(len) + sizeof(db_indx_t)) 00503 00504 /* 00505 * The second and third types are B_DUPLICATE and B_OVERFLOW, represented 00506 * by the BOVERFLOW structure. 00507 */ 00508 typedef struct _boverflow { 00509 db_indx_t unused1; /* 00-01: Padding, unused. */ 00510 u_int8_t type; /* 02: Page type AND DELETE FLAG. */ 00511 u_int8_t unused2; /* 03: Padding, unused. */ 00512 db_pgno_t pgno; /* 04-07: Next page number. */ 00513 u_int32_t tlen; /* 08-11: Total length of item. */ 00514 } BOVERFLOW; 00515 00516 /* Get a BOVERFLOW item for a specific index. */ 00517 #define GET_BOVERFLOW(pg, indx) \ 00518 ((BOVERFLOW *)P_ENTRY(pg, indx)) 00519 00520 /* 00521 * Page space required to add a new BOVERFLOW item to the page, with and 00522 * without the index value. 00523 */ 00524 #define BOVERFLOW_SIZE \ 00525 ALIGN(sizeof(BOVERFLOW), 4) 00526 #define BOVERFLOW_PSIZE \ 00527 (BOVERFLOW_SIZE + sizeof(db_indx_t)) 00528 00529 /* 00530 * Btree leaf and hash page layouts group indices in sets of two, one for the 00531 * key and one for the data. Everything else does it in sets of one to save 00532 * space. Use the following macros so that it's real obvious what's going on. 00533 */ 00534 #define O_INDX 1 00535 #define P_INDX 2 00536 00537 /************************************************************************ 00538 BTREE INTERNAL PAGE LAYOUT 00539 ************************************************************************/ 00540 00541 /* 00542 * Btree internal entry. 00543 */ 00544 typedef struct _binternal { 00545 db_indx_t len; /* 00-01: Key/data item length. */ 00546 u_int8_t type; /* 02: Page type AND DELETE FLAG. */ 00547 u_int8_t unused; /* 03: Padding, unused. */ 00548 db_pgno_t pgno; /* 04-07: Page number of referenced page. */ 00549 db_recno_t nrecs; /* 08-11: Subtree record count. */ 00550 u_int8_t data[1]; /* Variable length key item. */ 00551 } BINTERNAL; 00552 00553 /* Get a BINTERNAL item for a specific index. */ 00554 #define GET_BINTERNAL(pg, indx) \ 00555 ((BINTERNAL *)P_ENTRY(pg, indx)) 00556 00557 /* 00558 * Page space required to add a new BINTERNAL item to the page, with and 00559 * without the index value. 00560 */ 00561 #define BINTERNAL_SIZE(len) \ 00562 ALIGN((len) + SSZA(BINTERNAL, data), 4) 00563 #define BINTERNAL_PSIZE(len) \ 00564 (BINTERNAL_SIZE(len) + sizeof(db_indx_t)) 00565 00566 /************************************************************************ 00567 RECNO INTERNAL PAGE LAYOUT 00568 ************************************************************************/ 00569 00570 /* 00571 * The recno internal entry. 00572 */ 00573 typedef struct _rinternal { 00574 db_pgno_t pgno; /* 00-03: Page number of referenced page. */ 00575 db_recno_t nrecs; /* 04-07: Subtree record count. */ 00576 } RINTERNAL; 00577 00578 /* Get a RINTERNAL item for a specific index. */ 00579 #define GET_RINTERNAL(pg, indx) \ 00580 ((RINTERNAL *)P_ENTRY(pg, indx)) 00581 00582 /* 00583 * Page space required to add a new RINTERNAL item to the page, with and 00584 * without the index value. 00585 */ 00586 #define RINTERNAL_SIZE \ 00587 ALIGN(sizeof(RINTERNAL), 4) 00588 #define RINTERNAL_PSIZE \ 00589 (RINTERNAL_SIZE + sizeof(db_indx_t)) 00590 00591 #if defined(__cplusplus) 00592 } 00593 #endif 00594 00595 #endif /* _DB_PAGE_H_ */