cde/programs/dtinfo/DtMmdb/btree_berkeley/btree.h

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-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 /* $XConsortium: btree.h /main/5 1996/07/18 16:31:58 drk $ */
  24 /*-
  25  * Copyright (c) 1991, 1993
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * This code is derived from software contributed to Berkeley by
  29  * Mike Olson.
  30  *
  31  * Redistribution and use in source and binary forms, with or without
  32  * modification, are permitted provided that the following conditions
  33  * are met:
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in the
  38  *    documentation and/or other materials provided with the distribution.
  39  * 3. All advertising materials mentioning features or use of this software
  40  *    must display the following acknowledgement:
  41  *      This product includes software developed by the University of
  42  *      California, Berkeley and its contributors.
  43  * 4. Neither the name of the University nor the names of its contributors
  44  *    may be used to endorse or promote products derived from this software
  45  *    without specific prior written permission.
  46  *
  47  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57  * SUCH DAMAGE.
  58  *
  59  *      @(#)btree.h     8.2 (Berkeley) 9/7/93
  60  */
  61
  62 #include <mpool.h>
  63
  64 #define DEFMINKEYPAGE   (2)             /* Minimum keys per page */
  65 #define MINCACHE        (5)             /* Minimum cached pages */
  66 #define MINPSIZE        (512)           /* Minimum page size */
  67
  68 /*
  69  * Page 0 of a btree file contains a copy of the meta-data.  This page is also
  70  * used as an out-of-band page, i.e. page pointers that point to nowhere point
  71  * to page 0.  Page 1 is the root of the btree.
  72  */
  73 #define P_INVALID        0              /* Invalid tree page number. */
  74 #define P_META           0              /* Tree metadata page number. */
  75 #define P_ROOT           1              /* Tree root page number. */
  76
  77 /*
  78  * There are five page layouts in the btree: btree internal pages (BINTERNAL),
  79  * btree leaf pages (BLEAF), recno internal pages (RINTERNAL), recno leaf pages
  80  * (RLEAF) and overflow pages.  All five page types have a page header (PAGE).
  81  * This implementation requires that longs within structures are NOT padded.
  82  * (ANSI C permits random padding.)  If your compiler pads randomly you'll have
  83  * to do some work to get this package to run.
  84  */
  85 typedef struct _page {
  86         pgno_t  pgno;                   /* this page's page number */
  87         pgno_t  prevpg;                 /* left sibling */
  88         pgno_t  nextpg;                 /* right sibling */
  89
  90 #define P_BINTERNAL     0x01            /* btree internal page */
  91 #define P_BLEAF         0x02            /* leaf page */
  92 #define P_OVERFLOW      0x04            /* overflow page */
  93 #define P_RINTERNAL     0x08            /* recno internal page */
  94 #define P_RLEAF         0x10            /* leaf page */
  95 #define P_TYPE          0x1f            /* type mask */
  96
  97 #define P_PRESERVE      0x20            /* never delete this chain of pages */
  98         u_long  flags;
  99
 100         indx_t  lower;                  /* lower bound of free space on page */
 101         indx_t  upper;                  /* upper bound of free space on page */
 102         indx_t  linp[1];                /* long-aligned VARIABLE LENGTH DATA */
 103 } PAGE;
 104
 105 /* First and next index. */
 106 #define BTDATAOFF       (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \
 107                             sizeof(u_long) + sizeof(indx_t) + sizeof(indx_t))
 108 #define NEXTINDEX(p)    (((p)->lower - BTDATAOFF) / sizeof(indx_t))
 109
 110 /*
 111  * For pages other than overflow pages, there is an array of offsets into the
 112  * rest of the page immediately following the page header.  Each offset is to
 113  * an item which is unique to the type of page.  The h_lower offset is just
 114  * past the last filled-in index.  The h_upper offset is the first item on the
 115  * page.  Offsets are from the beginning of the page.
 116  *
 117  * If an item is too big to store on a single page, a flag is set and the item
 118  * is a { page, size } pair such that the page is the first page of an overflow
 119  * chain with size bytes of item.  Overflow pages are simply bytes without any
 120  * external structure.
 121  *
 122  * The size and page number fields in the items are long aligned so they can be
 123  * manipulated without copying.
 124  */
 125 #define LALIGN(n)       (((n) + sizeof(u_long) - 1) & ~(sizeof(u_long) - 1))
 126 #define NOVFLSIZE       (sizeof(pgno_t) + sizeof(size_t))
 127
 128 /*
 129  * For the btree internal pages, the item is a key.  BINTERNALs are {key, pgno}
 130  * pairs, such that the key compares less than or equal to all of the records
 131  * on that page.  For a tree without duplicate keys, an internal page with two
 132  * consecutive keys, a and b, will have all records greater than or equal to a
 133  * and less than b stored on the page associated with a.  Duplicate keys are
 134  * somewhat special and can cause duplicate internal and leaf page records and
 135  * some minor modifications of the above rule.
 136  */
 137 typedef struct _binternal {
 138         size_t  ksize;                  /* key size */
 139         pgno_t  pgno;                   /* page number stored on */
 140 #define P_BIGDATA       0x01            /* overflow data */
 141 #define P_BIGKEY        0x02            /* overflow key */
 142         u_char  flags;
 143         char    bytes[1];               /* data */
 144 } BINTERNAL;
 145
 146 /* Get the page's BINTERNAL structure at index indx. */
 147 #define GETBINTERNAL(pg, indx) \
 148         ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 149
 150 /* Get the number of bytes in the entry. */
 151 #define NBINTERNAL(len) \
 152         LALIGN(sizeof(size_t) + sizeof(pgno_t) + sizeof(u_char) + (len))
 153
 154 /* Copy a BINTERNAL entry to the page. */
 155 #define WR_BINTERNAL(p, size, pgno, flags) { \
 156         *(size_t *)p = size; \
 157         p += sizeof(size_t); \
 158         *(pgno_t *)p = pgno; \
 159         p += sizeof(pgno_t); \
 160         *(u_char *)p = flags; \
 161         p += sizeof(u_char); \
 162 }
 163
 164 /*
 165  * For the recno internal pages, the item is a page number with the number of
 166  * keys found on that page and below.
 167  */
 168 typedef struct _rinternal {
 169         recno_t nrecs;                  /* number of records */
 170         pgno_t  pgno;                   /* page number stored below */
 171 } RINTERNAL;
 172
 173 /* Get the page's RINTERNAL structure at index indx. */
 174 #define GETRINTERNAL(pg, indx) \
 175         ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 176
 177 /* Get the number of bytes in the entry. */
 178 #define NRINTERNAL \
 179         LALIGN(sizeof(recno_t) + sizeof(pgno_t))
 180
 181 /* Copy a RINTERAL entry to the page. */
 182 #define WR_RINTERNAL(p, nrecs, pgno) { \
 183         *(recno_t *)p = nrecs; \
 184         p += sizeof(recno_t); \
 185         *(pgno_t *)p = pgno; \
 186 }
 187
 188 /* For the btree leaf pages, the item is a key and data pair. */
 189 typedef struct _bleaf {
 190         size_t  ksize;                  /* size of key */
 191         size_t  dsize;                  /* size of data */
 192         u_char  flags;                  /* P_BIGDATA, P_BIGKEY */
 193         char    bytes[1];               /* data */
 194 } BLEAF;
 195
 196 /* Get the page's BLEAF structure at index indx. */
 197 #define GETBLEAF(pg, indx) \
 198         ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
 199
 200 /* Get the number of bytes in the entry. */
 201 #define NBLEAF(p)       NBLEAFDBT((p)->ksize, (p)->dsize)
 202
 203 /* Get the number of bytes in the user's key/data pair. */
 204 #define NBLEAFDBT(ksize, dsize) \
 205         LALIGN(sizeof(size_t) + sizeof(size_t) + sizeof(u_char) + \
 206             (ksize) + (dsize))
 207
 208 /* Copy a BLEAF entry to the page. */
 209 #define WR_BLEAF(p, key, data, flags) { \
 210         *(size_t *)p = key->size; \
 211         p += sizeof(size_t); \
 212         *(size_t *)p = data->size; \
 213         p += sizeof(size_t); \
 214         *(u_char *)p = flags; \
 215         p += sizeof(u_char); \
 216         memmove(p, key->data, key->size); \
 217         p += key->size; \
 218         memmove(p, data->data, data->size); \
 219 }
 220
 221 /* For the recno leaf pages, the item is a data entry. */
 222 typedef struct _rleaf {
 223         size_t  dsize;                  /* size of data */
 224         u_char  flags;                  /* P_BIGDATA */
 225         char    bytes[1];
 226 } RLEAF;
 227
 228 /* Get the page's RLEAF structure at index indx. */
 229 #define GETRLEAF(pg, indx) \
 230         ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
 231
 232 /* Get the number of bytes in the entry. */
 233 #define NRLEAF(p)       NRLEAFDBT((p)->dsize)
 234
 235 /* Get the number of bytes from the user's data. */
 236 #define NRLEAFDBT(dsize) \
 237         LALIGN(sizeof(size_t) + sizeof(u_char) + (dsize))
 238
 239 /* Copy a RLEAF entry to the page. */
 240 #define WR_RLEAF(p, data, flags) { \
 241         *(size_t *)p = data->size; \
 242         p += sizeof(size_t); \
 243         *(u_char *)p = flags; \
 244         p += sizeof(u_char); \
 245         memmove(p, data->data, data->size); \
 246 }
 247
 248 /*
 249  * A record in the tree is either a pointer to a page and an index in the page
 250  * or a page number and an index.  These structures are used as a cursor, stack
 251  * entry and search returns as well as to pass records to other routines.
 252  *
 253  * One comment about searches.  Internal page searches must find the largest
 254  * record less than key in the tree so that descents work.  Leaf page searches
 255  * must find the smallest record greater than key so that the returned index
 256  * is the record's correct position for insertion.
 257  *
 258  * One comment about cursors.  The cursor key is never removed from the tree,
 259  * even if deleted.  This is because it is quite difficult to decide where the
 260  * cursor should be when other keys have been inserted/deleted in the tree;
 261  * duplicate keys make it impossible.  This scheme does require extra work
 262  * though, to make sure that we don't perform an operation on a deleted key.
 263  */
 264 typedef struct _epgno {
 265         pgno_t  pgno;                   /* the page number */
 266         indx_t  index;                  /* the index on the page */
 267 } EPGNO;
 268
 269 typedef struct _epg {
 270         PAGE    *page;                  /* the (pinned) page */
 271         indx_t   index;                 /* the index on the page */
 272 } EPG;
 273
 274 /*
 275  * The metadata of the tree.  The m_nrecs field is used only by the RECNO code.
 276  * This is because the btree doesn't really need it and it requires that every
 277  * put or delete call modify the metadata.
 278  */
 279 typedef struct _btmeta {
 280         u_long  m_magic;                /* magic number */
 281         u_long  m_version;              /* version */
 282         u_long  m_psize;                /* page size */
 283         u_long  m_free;                 /* page number of first free page */
 284         u_long  m_nrecs;                /* R: number of records */
 285 #define SAVEMETA        (B_NODUPS | R_RECNO)
 286         u_long  m_flags;                /* bt_flags & SAVEMETA */
 287         u_long  m_unused;               /* unused */
 288 } BTMETA;
 289
 290 /* The in-memory btree/recno data structure. */
 291 typedef struct _btree {
 292         MPOOL   *bt_mp;                 /* memory pool cookie */
 293
 294         DB      *bt_dbp;                /* pointer to enclosing DB */
 295
 296         PAGE    *bt_pinned;             /* page pinned across calls */
 297
 298         EPGNO   bt_bcursor;             /* B: btree cursor */
 299         recno_t bt_rcursor;             /* R: recno cursor (1-based) */
 300
 301 #define BT_POP(t)       (t->bt_sp ? t->bt_stack + --t->bt_sp : NULL)
 302 #define BT_CLR(t)       (t->bt_sp = 0)
 303         EPGNO   *bt_stack;              /* stack of parent pages */
 304         u_int   bt_sp;                  /* current stack pointer */
 305         u_int   bt_maxstack;            /* largest stack */
 306
 307         char    *bt_kbuf;               /* key buffer */
 308         size_t  bt_kbufsz;              /* key buffer size */
 309         char    *bt_dbuf;               /* data buffer */
 310         size_t  bt_dbufsz;              /* data buffer size */
 311
 312         int     bt_fd;                  /* tree file descriptor */
 313
 314         pgno_t  bt_free;                /* next free page */
 315         u_long  bt_psize;               /* page size */
 316         indx_t  bt_ovflsize;            /* cut-off for key/data overflow */
 317         int     bt_lorder;              /* byte order */
 318                                         /* sorted order */
 319         enum { NOT, BACK, FORWARD } bt_order;
 320         EPGNO   bt_last;                /* last insert */
 321
 322                                         /* B: key comparison function */
 323         int     (*bt_cmp) __P((const DBT *, const DBT *));
 324                                         /* B: prefix comparison function */
 325         int     (*bt_pfx) __P((const DBT *, const DBT *));
 326                                         /* R: recno input function */
 327         int     (*bt_irec) __P((struct _btree *, recno_t));
 328
 329         FILE    *bt_rfp;                /* R: record FILE pointer */
 330         int     bt_rfd;                 /* R: record file descriptor */
 331
 332         caddr_t bt_cmap;                /* R: current point in mapped space */
 333         caddr_t bt_smap;                /* R: start of mapped space */
 334         caddr_t bt_emap;                /* R: end of mapped space */
 335         size_t  bt_msize;               /* R: size of mapped region. */
 336
 337         recno_t bt_nrecs;               /* R: number of records */
 338         size_t  bt_reclen;              /* R: fixed record length */
 339         u_char  bt_bval;                /* R: delimiting byte/pad character */
 340
 341 /*
 342  * NB:
 343  * B_NODUPS and R_RECNO are stored on disk, and may not be changed.
 344  */
 345 #define B_DELCRSR       0x00001         /* cursor has been deleted */
 346 #define B_INMEM         0x00002         /* in-memory tree */
 347 #define B_METADIRTY     0x00004         /* need to write metadata */
 348 #define B_MODIFIED      0x00008         /* tree modified */
 349 #define B_NEEDSWAP      0x00010         /* if byte order requires swapping */
 350 #define B_NODUPS        0x00020         /* no duplicate keys permitted */
 351 #define B_RDONLY        0x00040         /* read-only tree */
 352 #define R_RECNO         0x00080         /* record oriented tree */
 353 #define B_SEQINIT       0x00100         /* sequential scan initialized */
 354
 355 #define R_CLOSEFP       0x00200         /* opened a file pointer */
 356 #define R_EOF           0x00400         /* end of input file reached. */
 357 #define R_FIXLEN        0x00800         /* fixed length records */
 358 #define R_MEMMAPPED     0x01000         /* memory mapped file. */
 359 #define R_INMEM         0x02000         /* in-memory file */
 360 #define R_MODIFIED      0x04000         /* modified file */
 361 #define R_RDONLY        0x08000         /* read-only file */
 362
 363 #define B_DB_LOCK       0x10000         /* DB_LOCK specified. */
 364 #define B_DB_SHMEM      0x20000         /* DB_SHMEM specified. */
 365 #define B_DB_TXN        0x40000         /* DB_TXN specified. */
 366
 367         u_long          bt_flags;       /* btree state */
 368 } BTREE;
 369
 370 #define SET(t, f)       ((t)->bt_flags |= (f))
 371 #define CLR(t, f)       ((t)->bt_flags &= ~(f))
 372 #define ISSET(t, f)     ((t)->bt_flags & (f))
 373
 374 #include "extern.h"