2
* See the file LICENSE for redistribution information.
4
* Copyright (c) 1996-2002
5
* Sleepycat Software. All rights reserved.
13
#if defined(__cplusplus)
21
* This implementation requires that values within the following structures
22
* NOT be padded -- note, ANSI C permits random padding within structures.
23
* If your compiler pads randomly you can just forget ever making DB run on
24
* your system. In addition, no data type can require larger alignment than
25
* its own size, e.g., a 4-byte data element may not require 8-byte alignment.
27
* Note that key/data lengths are often stored in db_indx_t's -- this is
28
* not accidental, nor does it limit the key/data size. If the key/data
29
* item fits on a page, it's guaranteed to be small enough to fit into a
30
* db_indx_t, and storing it in one saves space.
33
#define PGNO_INVALID 0 /* Invalid page number in any database. */
34
#define PGNO_BASE_MD 0 /* Base database: metadata page number. */
37
#define P_INVALID 0 /* Invalid page type. */
38
#define __P_DUPLICATE 1 /* Duplicate. DEPRECATED in 3.1 */
39
#define P_HASH 2 /* Hash. */
40
#define P_IBTREE 3 /* Btree internal. */
41
#define P_IRECNO 4 /* Recno internal. */
42
#define P_LBTREE 5 /* Btree leaf. */
43
#define P_LRECNO 6 /* Recno leaf. */
44
#define P_OVERFLOW 7 /* Overflow. */
45
#define P_HASHMETA 8 /* Hash metadata page. */
46
#define P_BTREEMETA 9 /* Btree metadata page. */
47
#define P_QAMMETA 10 /* Queue metadata page. */
48
#define P_QAMDATA 11 /* Queue data page. */
49
#define P_LDUP 12 /* Off-page duplicate leaf. */
50
#define P_PAGETYPE_MAX 13
53
* When we create pages in mpool, we ask mpool to clear some number of bytes
54
* in the header. This number must be at least as big as the regular page
55
* headers and cover enough of the btree and hash meta-data pages to obliterate
58
#define DB_PAGE_DB_LEN 32
59
#define DB_PAGE_QUEUE_LEN 0
61
/************************************************************************
62
GENERIC METADATA PAGE HEADER
65
* The magic and version numbers have to be in the same place in all versions
66
* of the metadata page as the application may not have upgraded the database.
67
************************************************************************/
68
typedef struct _dbmeta33 {
69
DB_LSN lsn; /* 00-07: LSN. */
70
db_pgno_t pgno; /* 08-11: Current page number. */
71
u_int32_t magic; /* 12-15: Magic number. */
72
u_int32_t version; /* 16-19: Version. */
73
u_int32_t pagesize; /* 20-23: Pagesize. */
74
u_int8_t encrypt_alg; /* 24: Encryption algorithm. */
75
u_int8_t type; /* 25: Page type. */
76
#define DBMETA_CHKSUM 0x01
77
u_int8_t metaflags; /* 26: Meta-only flags */
78
u_int8_t unused1; /* 27: Unused. */
79
u_int32_t free; /* 28-31: Free list page number. */
80
db_pgno_t last_pgno; /* 32-35: Page number of last page in db. */
81
u_int32_t unused3; /* 36-39: Unused. */
82
u_int32_t key_count; /* 40-43: Cached key count. */
83
u_int32_t record_count; /* 44-47: Cached record count. */
84
u_int32_t flags; /* 48-51: Flags: unique to each AM. */
85
/* 52-71: Unique file ID. */
86
u_int8_t uid[DB_FILE_ID_LEN];
89
/************************************************************************
90
BTREE METADATA PAGE LAYOUT
91
************************************************************************/
92
typedef struct _btmeta33 {
93
#define BTM_DUP 0x001 /* Duplicates. */
94
#define BTM_RECNO 0x002 /* Recno tree. */
95
#define BTM_RECNUM 0x004 /* Btree: maintain record count. */
96
#define BTM_FIXEDLEN 0x008 /* Recno: fixed length records. */
97
#define BTM_RENUMBER 0x010 /* Recno: renumber on insert/delete. */
98
#define BTM_SUBDB 0x020 /* Subdatabases. */
99
#define BTM_DUPSORT 0x040 /* Duplicates are sorted. */
100
#define BTM_MASK 0x07f
101
DBMETA dbmeta; /* 00-71: Generic meta-data header. */
103
u_int32_t maxkey; /* 72-75: Btree: Maxkey. */
104
u_int32_t minkey; /* 76-79: Btree: Minkey. */
105
u_int32_t re_len; /* 80-83: Recno: fixed-length record length. */
106
u_int32_t re_pad; /* 84-87: Recno: fixed-length record pad. */
107
u_int32_t root; /* 88-91: Root page. */
108
u_int32_t unused[92]; /* 92-459: Unused space */
109
u_int32_t crypto_magic; /* 460-463: Crypto magic number */
110
u_int32_t trash[3]; /* 464-475: Trash space - Do not use */
111
u_int8_t iv[DB_IV_BYTES]; /* 476-495: Crypto IV */
112
u_int8_t chksum[DB_MAC_KEY]; /* 496-511: Page chksum */
115
* Minimum page size is 512.
119
/************************************************************************
120
HASH METADATA PAGE LAYOUT
121
************************************************************************/
122
typedef struct _hashmeta33 {
123
#define DB_HASH_DUP 0x01 /* Duplicates. */
124
#define DB_HASH_SUBDB 0x02 /* Subdatabases. */
125
#define DB_HASH_DUPSORT 0x04 /* Duplicates are sorted. */
126
DBMETA dbmeta; /* 00-71: Generic meta-data page header. */
128
u_int32_t max_bucket; /* 72-75: ID of Maximum bucket in use */
129
u_int32_t high_mask; /* 76-79: Modulo mask into table */
130
u_int32_t low_mask; /* 80-83: Modulo mask into table lower half */
131
u_int32_t ffactor; /* 84-87: Fill factor */
132
u_int32_t nelem; /* 88-91: Number of keys in hash table */
133
u_int32_t h_charkey; /* 92-95: Value of hash(CHARKEY) */
134
#define NCACHED 32 /* number of spare points */
135
/* 96-223: Spare pages for overflow */
136
u_int32_t spares[NCACHED];
137
u_int32_t unused[59]; /* 224-459: Unused space */
138
u_int32_t crypto_magic; /* 460-463: Crypto magic number */
139
u_int32_t trash[3]; /* 464-475: Trash space - Do not use */
140
u_int8_t iv[DB_IV_BYTES]; /* 476-495: Crypto IV */
141
u_int8_t chksum[DB_MAC_KEY]; /* 496-511: Page chksum */
144
* Minimum page size is 512.
148
/************************************************************************
149
QUEUE METADATA PAGE LAYOUT
150
************************************************************************/
152
* QAM Meta data page structure
155
typedef struct _qmeta33 {
156
DBMETA dbmeta; /* 00-71: Generic meta-data header. */
158
u_int32_t first_recno; /* 72-75: First not deleted record. */
159
u_int32_t cur_recno; /* 76-79: Next recno to be allocated. */
160
u_int32_t re_len; /* 80-83: Fixed-length record length. */
161
u_int32_t re_pad; /* 84-87: Fixed-length record pad. */
162
u_int32_t rec_page; /* 88-91: Records Per Page. */
163
u_int32_t page_ext; /* 92-95: Pages per extent */
165
u_int32_t unused[91]; /* 96-459: Unused space */
166
u_int32_t crypto_magic; /* 460-463: Crypto magic number */
167
u_int32_t trash[3]; /* 464-475: Trash space - Do not use */
168
u_int8_t iv[DB_IV_BYTES]; /* 476-495: Crypto IV */
169
u_int8_t chksum[DB_MAC_KEY]; /* 496-511: Page chksum */
171
* Minimum page size is 512.
176
* DBMETASIZE is a constant used by __db_file_setup and DB->verify
177
* as a buffer which is guaranteed to be larger than any possible
178
* metadata page size and smaller than any disk sector.
180
#define DBMETASIZE 512
182
/************************************************************************
183
BTREE/HASH MAIN PAGE LAYOUT
184
************************************************************************/
186
* +-----------------------------------+
187
* | lsn | pgno | prev pgno |
188
* +-----------------------------------+
189
* | next pgno | entries | hf offset |
190
* +-----------------------------------+
191
* | level | type | chksum |
192
* +-----------------------------------+
193
* | iv | index | free --> |
194
* +-----------+-----------------------+
195
* | F R E E A R E A |
196
* +-----------------------------------+
197
* | <-- free | item |
198
* +-----------------------------------+
199
* | item | item | item |
200
* +-----------------------------------+
202
* sizeof(PAGE) == 26 bytes + possibly 20 bytes of checksum and possibly
203
* 16 bytes of IV (+ 2 bytes for alignment), and the following indices
204
* are guaranteed to be two-byte aligned. If we aren't doing crypto or
205
* checksumming the bytes are reclaimed for data storage.
207
* For hash and btree leaf pages, index items are paired, e.g., inp[0] is the
208
* key for inp[1]'s data. All other types of pages only contain single items.
210
typedef struct __pg_chksum {
211
u_int8_t unused[2]; /* 26-27: For alignment */
212
u_int8_t chksum[4]; /* 28-31: Checksum */
215
typedef struct __pg_crypto {
216
u_int8_t unused[2]; /* 26-27: For alignment */
217
u_int8_t chksum[DB_MAC_KEY]; /* 28-47: Checksum */
218
u_int8_t iv[DB_IV_BYTES]; /* 48-63: IV */
220
* Must be 16-byte aligned for crypto
224
typedef struct _db_page {
225
DB_LSN lsn; /* 00-07: Log sequence number. */
226
db_pgno_t pgno; /* 08-11: Current page number. */
227
db_pgno_t prev_pgno; /* 12-15: Previous page number. */
228
db_pgno_t next_pgno; /* 16-19: Next page number. */
229
db_indx_t entries; /* 20-21: Number of items on the page. */
230
db_indx_t hf_offset; /* 22-23: High free byte page offset. */
233
* The btree levels are numbered from the leaf to the root, starting
234
* with 1, so the leaf is level 1, its parent is level 2, and so on.
235
* We maintain this level on all btree pages, but the only place that
236
* we actually need it is on the root page. It would not be difficult
237
* to hide the byte on the root page once it becomes an internal page,
238
* so we could get this byte back if we needed it for something else.
241
#define MAXBTREELEVEL 255
242
u_int8_t level; /* 24: Btree tree level. */
243
u_int8_t type; /* 25: Page type. */
246
#define SIZEOF_PAGE 26
249
* DB_AM_ENCRYPT always implies DB_AM_CHKSUM so that must come first.
251
#define P_INP(dbp, pg) \
252
((db_indx_t *)((u_int8_t *)(pg) + SIZEOF_PAGE + \
253
(F_ISSET((dbp), DB_AM_ENCRYPT) ? sizeof(PG_CRYPTO) : \
254
(F_ISSET((dbp), DB_AM_CHKSUM) ? sizeof(PG_CHKSUM) : 0))))
256
#define P_IV(dbp, pg) \
257
(F_ISSET((dbp), DB_AM_ENCRYPT) ? ((u_int8_t *)(pg) + \
258
SIZEOF_PAGE + SSZA(PG_CRYPTO, iv)) \
261
#define P_CHKSUM(dbp, pg) \
262
(F_ISSET((dbp), DB_AM_ENCRYPT) ? ((u_int8_t *)(pg) + \
263
SIZEOF_PAGE + SSZA(PG_CRYPTO, chksum)) : \
264
(F_ISSET((dbp), DB_AM_CHKSUM) ? ((u_int8_t *)(pg) + \
265
SIZEOF_PAGE + SSZA(PG_CHKSUM, chksum)) \
268
/* PAGE element macros. */
269
#define LSN(p) (((PAGE *)p)->lsn)
270
#define PGNO(p) (((PAGE *)p)->pgno)
271
#define PREV_PGNO(p) (((PAGE *)p)->prev_pgno)
272
#define NEXT_PGNO(p) (((PAGE *)p)->next_pgno)
273
#define NUM_ENT(p) (((PAGE *)p)->entries)
274
#define HOFFSET(p) (((PAGE *)p)->hf_offset)
275
#define LEVEL(p) (((PAGE *)p)->level)
276
#define TYPE(p) (((PAGE *)p)->type)
278
/************************************************************************
279
QUEUE MAIN PAGE LAYOUT
280
************************************************************************/
282
* Sizes of page below. Used to reclaim space if not doing
283
* crypto or checksumming. If you change the QPAGE below you
284
* MUST adjust this too.
286
#define QPAGE_NORMAL 28
287
#define QPAGE_CHKSUM 48
290
typedef struct _qpage {
291
DB_LSN lsn; /* 00-07: Log sequence number. */
292
db_pgno_t pgno; /* 08-11: Current page number. */
293
u_int32_t unused0[3]; /* 12-23: Unused. */
294
u_int8_t unused1[1]; /* 24: Unused. */
295
u_int8_t type; /* 25: Page type. */
296
u_int8_t unused2[2]; /* 26-27: Unused. */
297
u_int8_t chksum[DB_MAC_KEY]; /* 28-47: Checksum */
298
u_int8_t iv[DB_IV_BYTES]; /* 48-63: IV */
301
#define QPAGE_SZ(dbp) \
302
(F_ISSET((dbp), DB_AM_ENCRYPT) ? QPAGE_SEC : \
303
F_ISSET((dbp), DB_AM_CHKSUM) ? QPAGE_CHKSUM : QPAGE_NORMAL)
306
* The next_pgno and prev_pgno fields are not maintained for btree and recno
307
* internal pages. Doing so only provides a minor performance improvement,
308
* it's hard to do when deleting internal pages, and it increases the chance
309
* of deadlock during deletes and splits because we have to re-link pages at
310
* more than the leaf level.
313
* The btree/recno access method needs db_recno_t bytes of space on the root
314
* page to specify how many records are stored in the tree. (The alternative
315
* is to store the number of records in the meta-data page, which will create
316
* a second hot spot in trees being actively modified, or recalculate it from
317
* the BINTERNAL fields on each access.) Overload the PREV_PGNO field.
320
((TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO) ? PREV_PGNO(p) : \
321
(db_pgno_t)(TYPE(p) == P_LBTREE ? NUM_ENT(p) / 2 : NUM_ENT(p)))
322
#define RE_NREC_ADJ(p, adj) \
324
#define RE_NREC_SET(p, num) \
331
* Don't modify the page's LSN, code depends on it being unchanged after a
334
#define P_INIT(pg, pg_size, n, pg_prev, pg_next, btl, pg_type) do { \
336
PREV_PGNO(pg) = pg_prev; \
337
NEXT_PGNO(pg) = pg_next; \
339
HOFFSET(pg) = pg_size; \
341
TYPE(pg) = pg_type; \
344
/* Page header length (offset to first index). */
345
#define P_OVERHEAD(dbp) P_TO_UINT16(P_INP(dbp, 0))
347
/* First free byte. */
348
#define LOFFSET(dbp, pg) \
349
(P_OVERHEAD(dbp) + NUM_ENT(pg) * sizeof(db_indx_t))
351
/* Free space on a regular page. */
352
#define P_FREESPACE(dbp, pg) (HOFFSET(pg) - LOFFSET(dbp, pg))
354
/* Get a pointer to the bytes at a specific index. */
355
#define P_ENTRY(dbp, pg, indx) ((u_int8_t *)pg + P_INP(dbp, pg)[indx])
357
/************************************************************************
359
************************************************************************/
362
* Overflow items are referenced by HOFFPAGE and BOVERFLOW structures, which
363
* store a page number (the first page of the overflow item) and a length
364
* (the total length of the overflow item). The overflow item consists of
365
* some number of overflow pages, linked by the next_pgno field of the page.
366
* A next_pgno field of PGNO_INVALID flags the end of the overflow item.
368
* Overflow page overloads:
369
* The amount of overflow data stored on each page is stored in the
372
* The implementation reference counts overflow items as it's possible
373
* for them to be promoted onto btree internal pages. The reference
374
* count is stored in the entries field.
376
#define OV_LEN(p) (((PAGE *)p)->hf_offset)
377
#define OV_REF(p) (((PAGE *)p)->entries)
379
/* Maximum number of bytes that you can put on an overflow page. */
380
#define P_MAXSPACE(dbp, psize) ((psize) - P_OVERHEAD(dbp))
382
/* Free space on an overflow page. */
383
#define P_OVFLSPACE(dbp, psize, pg) (P_MAXSPACE(dbp, psize) - HOFFSET(pg))
385
/************************************************************************
387
************************************************************************/
389
/* Each index references a group of bytes on the page. */
390
#define H_KEYDATA 1 /* Key/data item. */
391
#define H_DUPLICATE 2 /* Duplicate key/data item. */
392
#define H_OFFPAGE 3 /* Overflow key/data item. */
393
#define H_OFFDUP 4 /* Overflow page of duplicates. */
397
* Items on hash pages are (potentially) unaligned, so we can never cast the
398
* (page + offset) pointer to an HKEYDATA, HOFFPAGE or HOFFDUP structure, as
399
* we do with B+tree on-page structures. Because we frequently want the type
400
* field, it requires no alignment, and it's in the same location in all three
401
* structures, there's a pair of macros.
403
#define HPAGE_PTYPE(p) (*(u_int8_t *)p)
404
#define HPAGE_TYPE(dbp, pg, indx) (*P_ENTRY(dbp, pg, indx))
407
* The first and second types are H_KEYDATA and H_DUPLICATE, represented
408
* by the HKEYDATA structure:
410
* +-----------------------------------+
411
* | type | key/data ... |
412
* +-----------------------------------+
414
* For duplicates, the data field encodes duplicate elements in the data
417
* +---------------------------------------------------------------+
418
* | type | len1 | element1 | len1 | len2 | element2 | len2 |
419
* +---------------------------------------------------------------+
421
* Thus, by keeping track of the offset in the element, we can do both
422
* backward and forward traversal.
424
typedef struct _hkeydata {
425
u_int8_t type; /* 00: Page type. */
426
u_int8_t data[1]; /* Variable length key/data item. */
428
#define HKEYDATA_DATA(p) (((u_int8_t *)p) + SSZA(HKEYDATA, data))
431
* The length of any HKEYDATA item. Note that indx is an element index,
434
#define LEN_HITEM(dbp, pg, pgsize, indx) \
435
(((indx) == 0 ? pgsize : \
436
(P_INP(dbp, pg)[indx - 1])) - (P_INP(dbp, pg)[indx]))
438
#define LEN_HKEYDATA(dbp, pg, psize, indx) \
439
(db_indx_t)(LEN_HITEM(dbp, pg, psize, indx) - HKEYDATA_SIZE(0))
442
* Page space required to add a new HKEYDATA item to the page, with and
443
* without the index value.
445
#define HKEYDATA_SIZE(len) \
446
((len) + SSZA(HKEYDATA, data))
447
#define HKEYDATA_PSIZE(len) \
448
(HKEYDATA_SIZE(len) + sizeof(db_indx_t))
450
/* Put a HKEYDATA item at the location referenced by a page entry. */
451
#define PUT_HKEYDATA(pe, kd, len, type) { \
452
((HKEYDATA *)pe)->type = type; \
453
memcpy((u_int8_t *)pe + sizeof(u_int8_t), kd, len); \
457
* Macros the describe the page layout in terms of key-data pairs.
459
#define H_NUMPAIRS(pg) (NUM_ENT(pg) / 2)
460
#define H_KEYINDEX(indx) (indx)
461
#define H_DATAINDEX(indx) ((indx) + 1)
462
#define H_PAIRKEY(dbp, pg, indx) P_ENTRY(dbp, pg, H_KEYINDEX(indx))
463
#define H_PAIRDATA(dbp, pg, indx) P_ENTRY(dbp, pg, H_DATAINDEX(indx))
464
#define H_PAIRSIZE(dbp, pg, psize, indx) \
465
(LEN_HITEM(dbp, pg, psize, H_KEYINDEX(indx)) + \
466
LEN_HITEM(dbp, pg, psize, H_DATAINDEX(indx)))
467
#define LEN_HDATA(dbp, p, psize, indx) \
468
LEN_HKEYDATA(dbp, p, psize, H_DATAINDEX(indx))
469
#define LEN_HKEY(dbp, p, psize, indx) \
470
LEN_HKEYDATA(dbp, p, psize, H_KEYINDEX(indx))
473
* The third type is the H_OFFPAGE, represented by the HOFFPAGE structure:
475
typedef struct _hoffpage {
476
u_int8_t type; /* 00: Page type and delete flag. */
477
u_int8_t unused[3]; /* 01-03: Padding, unused. */
478
db_pgno_t pgno; /* 04-07: Offpage page number. */
479
u_int32_t tlen; /* 08-11: Total length of item. */
482
#define HOFFPAGE_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, pgno))
483
#define HOFFPAGE_TLEN(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, tlen))
486
* Page space required to add a new HOFFPAGE item to the page, with and
487
* without the index value.
489
#define HOFFPAGE_SIZE (sizeof(HOFFPAGE))
490
#define HOFFPAGE_PSIZE (HOFFPAGE_SIZE + sizeof(db_indx_t))
493
* The fourth type is H_OFFDUP represented by the HOFFDUP structure:
495
typedef struct _hoffdup {
496
u_int8_t type; /* 00: Page type and delete flag. */
497
u_int8_t unused[3]; /* 01-03: Padding, unused. */
498
db_pgno_t pgno; /* 04-07: Offpage page number. */
500
#define HOFFDUP_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFDUP, pgno))
503
* Page space required to add a new HOFFDUP item to the page, with and
504
* without the index value.
506
#define HOFFDUP_SIZE (sizeof(HOFFDUP))
508
/************************************************************************
510
************************************************************************/
512
/* Each index references a group of bytes on the page. */
513
#define B_KEYDATA 1 /* Key/data item. */
514
#define B_DUPLICATE 2 /* Duplicate key/data item. */
515
#define B_OVERFLOW 3 /* Overflow key/data item. */
518
* We have to store a deleted entry flag in the page. The reason is complex,
519
* but the simple version is that we can't delete on-page items referenced by
520
* a cursor -- the return order of subsequent insertions might be wrong. The
521
* delete flag is an overload of the top bit of the type byte.
523
#define B_DELETE (0x80)
524
#define B_DCLR(t) (t) &= ~B_DELETE
525
#define B_DSET(t) (t) |= B_DELETE
526
#define B_DISSET(t) ((t) & B_DELETE)
528
#define B_TYPE(t) ((t) & ~B_DELETE)
529
#define B_TSET(t, type, deleted) { \
536
* The first type is B_KEYDATA, represented by the BKEYDATA structure:
538
typedef struct _bkeydata {
539
db_indx_t len; /* 00-01: Key/data item length. */
540
u_int8_t type; /* 02: Page type AND DELETE FLAG. */
541
u_int8_t data[1]; /* Variable length key/data item. */
544
/* Get a BKEYDATA item for a specific index. */
545
#define GET_BKEYDATA(dbp, pg, indx) \
546
((BKEYDATA *)P_ENTRY(dbp, pg, indx))
549
* Page space required to add a new BKEYDATA item to the page, with and
550
* without the index value.
552
#define BKEYDATA_SIZE(len) \
553
ALIGN((len) + SSZA(BKEYDATA, data), sizeof(u_int32_t))
554
#define BKEYDATA_PSIZE(len) \
555
(BKEYDATA_SIZE(len) + sizeof(db_indx_t))
558
* The second and third types are B_DUPLICATE and B_OVERFLOW, represented
559
* by the BOVERFLOW structure.
561
typedef struct _boverflow {
562
db_indx_t unused1; /* 00-01: Padding, unused. */
563
u_int8_t type; /* 02: Page type AND DELETE FLAG. */
564
u_int8_t unused2; /* 03: Padding, unused. */
565
db_pgno_t pgno; /* 04-07: Next page number. */
566
u_int32_t tlen; /* 08-11: Total length of item. */
569
/* Get a BOVERFLOW item for a specific index. */
570
#define GET_BOVERFLOW(dbp, pg, indx) \
571
((BOVERFLOW *)P_ENTRY(dbp, pg, indx))
574
* Page space required to add a new BOVERFLOW item to the page, with and
575
* without the index value. The (u_int16_t) cast avoids warnings: ALIGN
576
* casts to db_align_t, the cast converts it to a small integral type so
577
* we don't get complaints when we assign the final result to an integral
578
* type smaller than db_align_t.
580
#define BOVERFLOW_SIZE \
581
((u_int16_t)ALIGN(sizeof(BOVERFLOW), sizeof(u_int32_t)))
582
#define BOVERFLOW_PSIZE \
583
(BOVERFLOW_SIZE + sizeof(db_indx_t))
586
* Btree leaf and hash page layouts group indices in sets of two, one for the
587
* key and one for the data. Everything else does it in sets of one to save
588
* space. Use the following macros so that it's real obvious what's going on.
593
/************************************************************************
594
BTREE INTERNAL PAGE LAYOUT
595
************************************************************************/
598
* Btree internal entry.
600
typedef struct _binternal {
601
db_indx_t len; /* 00-01: Key/data item length. */
602
u_int8_t type; /* 02: Page type AND DELETE FLAG. */
603
u_int8_t unused; /* 03: Padding, unused. */
604
db_pgno_t pgno; /* 04-07: Page number of referenced page. */
605
db_recno_t nrecs; /* 08-11: Subtree record count. */
606
u_int8_t data[1]; /* Variable length key item. */
609
/* Get a BINTERNAL item for a specific index. */
610
#define GET_BINTERNAL(dbp, pg, indx) \
611
((BINTERNAL *)P_ENTRY(dbp, pg, indx))
614
* Page space required to add a new BINTERNAL item to the page, with and
615
* without the index value.
617
#define BINTERNAL_SIZE(len) \
618
ALIGN((len) + SSZA(BINTERNAL, data), sizeof(u_int32_t))
619
#define BINTERNAL_PSIZE(len) \
620
(BINTERNAL_SIZE(len) + sizeof(db_indx_t))
622
/************************************************************************
623
RECNO INTERNAL PAGE LAYOUT
624
************************************************************************/
627
* The recno internal entry.
629
typedef struct _rinternal {
630
db_pgno_t pgno; /* 00-03: Page number of referenced page. */
631
db_recno_t nrecs; /* 04-07: Subtree record count. */
634
/* Get a RINTERNAL item for a specific index. */
635
#define GET_RINTERNAL(dbp, pg, indx) \
636
((RINTERNAL *)P_ENTRY(dbp, pg, indx))
639
* Page space required to add a new RINTERNAL item to the page, with and
640
* without the index value.
642
#define RINTERNAL_SIZE \
643
ALIGN(sizeof(RINTERNAL), sizeof(u_int32_t))
644
#define RINTERNAL_PSIZE \
645
(RINTERNAL_SIZE + sizeof(db_indx_t))
647
#if defined(__cplusplus)
651
#endif /* !_DB_PAGE_H_ */
added
removed
libdb/dbinc/db_page.h
