db_page.h

Go to the documentation of this file.
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_ */

Generated on Sun Jun 8 10:56:36 2008 for GNUmifluz by  doxygen 1.5.5