BSD 4_4 release

[unix-history] / usr / src / lib / libc / db / btree / btree.h

diff --git a/usr/src/lib/libc/db/btree/btree.h b/usr/src/lib/libc/db/btree/btree.h
index 565f29e..1e39323 100644 (file)
--- a/usr/src/lib/libc/db/btree/btree.h
+++ b/usr/src/lib/libc/db/btree/btree.h
@@ -1,49 +1,63 @@
 /*-
 /*-

- * Copyright (c) 1991 The Regents of the University of California.
- * All rights reserved.
+ * Copyright (c) 1991, 1993
+ *     The Regents of the University of California.  All rights reserved.

  *
  * This code is derived from software contributed to Berkeley by
  * Mike Olson.
  *
  *
  * This code is derived from software contributed to Berkeley by
  * Mike Olson.
  *

- * %sccs.include.redist.c%
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *     This product includes software developed by the University of
+ *     California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.

  *
  *

- *     @(#)btree.h     5.3 (Berkeley) %G%
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *     @(#)btree.h     8.1 (Berkeley) 6/4/93

  */
 
 #include <mpool.h>
 
  */
 
 #include <mpool.h>
 

-#define        DEFMAXKEYPAGE   (0)             /* Maximum keys per page */

 #define        DEFMINKEYPAGE   (2)             /* Minimum keys per page */
 #define        MINCACHE        (5)             /* Minimum cached pages */
 #define        MINPSIZE        (512)           /* Minimum page size */
 
 /*
 #define        DEFMINKEYPAGE   (2)             /* Minimum keys per page */
 #define        MINCACHE        (5)             /* Minimum cached pages */
 #define        MINPSIZE        (512)           /* Minimum page size */
 
 /*

- * Page 0 of a btree file contains a BTMETA structure.  The rest of the first
- * page is empty, so that all disk operations are page-aligned.  This page is
- * also used as an out-of-band page, i.e. page pointers that point to nowhere
- * point to page 0.  The m_nrecs field is used only the RECNO code.  This is 
- * because the btree doesn't really need it and it requires that put or delete
- * calls modify the meta data.
+ * Page 0 of a btree file contains a copy of the meta-data.  This page is also
+ * used as an out-of-band page, i.e. page pointers that point to nowhere point
+ * to page 0.  Page 1 is the root of the btree.

  */
 #define        P_INVALID        0              /* Invalid tree page number. */
  */
 #define        P_INVALID        0              /* Invalid tree page number. */

-#define        P_META           0              /* Tree meta-info page number. */
+#define        P_META           0              /* Tree metadata page number. */

 #define        P_ROOT           1              /* Tree root page number. */
 
 #define        P_ROOT           1              /* Tree root page number. */
 

-typedef struct BTMETA {
-       u_long  m_magic;                /* magic number */
-       u_long  m_version;              /* version */
-       u_long  m_psize;                /* page size */
-       u_long  m_free;                 /* page number of first free page */
-       u_long  m_nrecs;                /* R: number of records */
-#define        SAVEMETA        (BTF_NODUPS | BTF_RECNO)
-       u_long  m_flags;                /* bt_flags & SAVEMETA */
-       u_long  m_lorder;               /* byte order */
-} BTMETA;
-

 /*
 /*

- * There are five page layouts in the btree: btree internal pages, btree leaf
- * pages, recno internal pages, recno leaf pages and overflow pages.  Each type
- * of page starts with a page header as typed by PAGE.
+ * There are five page layouts in the btree: btree internal pages (BINTERNAL),
+ * btree leaf pages (BLEAF), recno internal pages (RINTERNAL), recno leaf pages
+ * (RLEAF) and overflow pages.  All five page types have a page header (PAGE).
+ * This implementation requires that longs within structures are NOT padded.
+ * (ANSI C permits random padding.)  If your compiler pads randomly you'll have
+ * to do some work to get this package to run.

  */
 typedef struct PAGE {
        pgno_t  pgno;                   /* this page's page number */
  */
 typedef struct PAGE {
        pgno_t  pgno;                   /* this page's page number */


@@ -60,14 +74,15 @@ typedef struct PAGE {
 #define        P_PRESERVE      0x20            /* never delete this chain of pages */
        u_long  flags;
 
 #define        P_PRESERVE      0x20            /* never delete this chain of pages */
        u_long  flags;
 

-       index_t lower;                  /* lower bound of free space on page */
-       index_t upper;                  /* upper bound of free space on page */
-       index_t linp[1];                /* long-aligned VARIABLE LENGTH DATA */
+       indx_t  lower;                  /* lower bound of free space on page */
+       indx_t  upper;                  /* upper bound of free space on page */
+       indx_t  linp[1];                /* long-aligned VARIABLE LENGTH DATA */

 } PAGE;
 
 /* First and next index. */
 } PAGE;
 
 /* First and next index. */

-#define        BTDATAOFF       (sizeof(PAGE) - sizeof(index_t))
-#define        NEXTINDEX(p)    (((p)->lower - BTDATAOFF) / sizeof(index_t))
+#define        BTDATAOFF       (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \
+                           sizeof(u_long) + sizeof(indx_t) + sizeof(indx_t))
+#define        NEXTINDEX(p)    (((p)->lower - BTDATAOFF) / sizeof(indx_t))

 
 /*
  * For pages other than overflow pages, there is an array of offsets into the
 
 /*
  * For pages other than overflow pages, there is an array of offsets into the


@@ -84,7 +99,7 @@ typedef struct PAGE {
  * The size and page number fields in the items are long aligned so they can be
  * manipulated without copying.
  */
  * The size and page number fields in the items are long aligned so they can be
  * manipulated without copying.
  */

-#define        LALIGN(l)       (((l) + sizeof(u_long) - 1) & ~(sizeof(u_long) - 1))
+#define        LALIGN(n)       (((n) + sizeof(u_long) - 1) & ~(sizeof(u_long) - 1))

 #define        NOVFLSIZE       (sizeof(pgno_t) + sizeof(size_t))
 
 /*
 #define        NOVFLSIZE       (sizeof(pgno_t) + sizeof(size_t))
 
 /*


@@ -142,7 +157,7 @@ typedef struct RINTERNAL {
 
 /* Copy a RINTERAL entry to the page. */
 #define        WR_RINTERNAL(p, nrecs, pgno) { \
 
 /* Copy a RINTERAL entry to the page. */
 #define        WR_RINTERNAL(p, nrecs, pgno) { \

-       *(size_t *)p = nrecs; \
+       *(recno_t *)p = nrecs; \

        p += sizeof(recno_t); \
        *(pgno_t *)p = pgno; \
 }
        p += sizeof(recno_t); \
        *(pgno_t *)p = pgno; \
 }


@@ -160,9 +175,7 @@ typedef struct BLEAF {
        ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */
        ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */

-#define NBLEAF(p) \
-       LALIGN(sizeof(size_t) + sizeof(size_t) + sizeof(u_char) + \
-           (p)->ksize + (p)->dsize)
+#define NBLEAF(p)      NBLEAFDBT((p)->ksize, (p)->dsize)

 
 /* Get the number of bytes in the user's key/data pair. */
 #define NBLEAFDBT(ksize, dsize) \
 
 /* Get the number of bytes in the user's key/data pair. */
 #define NBLEAFDBT(ksize, dsize) \


@@ -177,9 +190,9 @@ typedef struct BLEAF {
        p += sizeof(size_t); \
        *(u_char *)p = flags; \
        p += sizeof(u_char); \
        p += sizeof(size_t); \
        *(u_char *)p = flags; \
        p += sizeof(u_char); \

-       bcopy(key->data, p, key->size); \
+       memmove(p, key->data, key->size); \

        p += key->size; \
        p += key->size; \

-       bcopy(data->data, p, data->size); \
+       memmove(p, data->data, data->size); \

 }
 
 /* For the recno leaf pages, the item is a data entry. */
 }
 
 /* For the recno leaf pages, the item is a data entry. */


@@ -194,8 +207,7 @@ typedef struct RLEAF {
        ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */
        ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */

-#define NRLEAF(p) \
-       LALIGN(sizeof(size_t) + sizeof(u_char) + (p)->dsize)
+#define NRLEAF(p)      NRLEAFDBT((p)->dsize)

 
 /* Get the number of bytes from the user's data. */
 #define        NRLEAFDBT(dsize) \
 
 /* Get the number of bytes from the user's data. */
 #define        NRLEAFDBT(dsize) \


@@ -207,7 +219,7 @@ typedef struct RLEAF {
        p += sizeof(size_t); \
        *(u_char *)p = flags; \
        p += sizeof(u_char); \
        p += sizeof(size_t); \
        *(u_char *)p = flags; \
        p += sizeof(u_char); \

-       bcopy(data->data, p, data->size); \
+       memmove(p, data->data, data->size); \

 }
 
 /*
 }
 
 /*


@@ -219,25 +231,47 @@ typedef struct RLEAF {
  * record less than key in the tree so that descents work.  Leaf page searches
  * must find the smallest record greater than key so that the returned index
  * is the record's correct position for insertion.
  * record less than key in the tree so that descents work.  Leaf page searches
  * must find the smallest record greater than key so that the returned index
  * is the record's correct position for insertion.

+ *
+ * One comment about cursors.  The cursor key is never removed from the tree,
+ * even if deleted.  This is because it is quite difficult to decide where the
+ * cursor should be when other keys have been inserted/deleted in the tree;
+ * duplicate keys make it impossible.  This scheme does require extra work
+ * though, to make sure that we don't perform an operation on a deleted key.

  */
 typedef struct EPGNO {
        pgno_t  pgno;                   /* the page number */
  */
 typedef struct EPGNO {
        pgno_t  pgno;                   /* the page number */

-       index_t index;                  /* the index on the page */
+       indx_t  index;                  /* the index on the page */

 } EPGNO;
 
 typedef struct EPG {
        PAGE    *page;                  /* the (pinned) page */
 } EPGNO;
 
 typedef struct EPG {
        PAGE    *page;                  /* the (pinned) page */

-       index_t  index;                 /* the index on the page */
+       indx_t   index;                 /* the index on the page */

 } EPG;
 
 } EPG;
 

+/*
+ * The metadata of the tree.  The m_nrecs field is used only by the RECNO code.
+ * This is because the btree doesn't really need it and it requires that every
+ * put or delete call modify the metadata.
+ */
+typedef struct BTMETA {
+       u_long  m_magic;                /* magic number */
+       u_long  m_version;              /* version */
+       u_long  m_psize;                /* page size */
+       u_long  m_free;                 /* page number of first free page */
+       u_long  m_nrecs;                /* R: number of records */
+#define        SAVEMETA        (B_NODUPS | R_RECNO)
+       u_long  m_flags;                /* bt_flags & SAVEMETA */
+       u_long  m_unused;               /* unused */
+} BTMETA;
+

 /* The in-memory btree/recno data structure. */
 typedef struct BTREE {
        MPOOL   *bt_mp;                 /* memory pool cookie */
 
        DB      *bt_dbp;                /* pointer to enclosing DB */
 
 /* The in-memory btree/recno data structure. */
 typedef struct BTREE {
        MPOOL   *bt_mp;                 /* memory pool cookie */
 
        DB      *bt_dbp;                /* pointer to enclosing DB */
 

-       EPGNO   bt_bcursor;             /* btree cursor */
-       recno_t bt_rcursor;             /* R: recno cursor */
+       EPGNO   bt_bcursor;             /* B: btree cursor */
+       recno_t bt_rcursor;             /* R: recno cursor (1-based) */

 
 #define        BT_POP(t)       (t->bt_sp ? t->bt_stack + --t->bt_sp : NULL)
 #define        BT_CLR(t)       (t->bt_sp = 0)
 
 #define        BT_POP(t)       (t->bt_sp ? t->bt_stack + --t->bt_sp : NULL)
 #define        BT_CLR(t)       (t->bt_sp = 0)


@@ -251,15 +285,11 @@ typedef struct BTREE {
        size_t  bt_dbufsz;              /* data buffer size */
 
        int     bt_fd;                  /* tree file descriptor */
        size_t  bt_dbufsz;              /* data buffer size */
 
        int     bt_fd;                  /* tree file descriptor */

-       FILE    *bt_rfp;                /* R: record FILE pointer */
-       int     bt_rfd;                 /* R: record file descriptor */

 
        pgno_t  bt_free;                /* next free page */
 
        pgno_t  bt_free;                /* next free page */

-       size_t  bt_psize;               /* page size */
-       int     bt_maxkeypage;          /* maximum keys per page */
-       size_t  bt_minkeypage;          /* minimum keys per page */
+       u_long  bt_psize;               /* page size */
+       indx_t  bt_ovflsize;            /* cut-off for key/data overflow */

        int     bt_lorder;              /* byte order */
        int     bt_lorder;              /* byte order */

-

                                        /* sorted order */
        enum { NOT, BACK, FORWARD, } bt_order;
        EPGNO   bt_last;                /* last insert */
                                        /* sorted order */
        enum { NOT, BACK, FORWARD, } bt_order;
        EPGNO   bt_last;                /* last insert */


@@ -268,30 +298,48 @@ typedef struct BTREE {
        int     (*bt_cmp) __P((const DBT *, const DBT *));
                                        /* B: prefix comparison function */
        int     (*bt_pfx) __P((const DBT *, const DBT *));
        int     (*bt_cmp) __P((const DBT *, const DBT *));
                                        /* B: prefix comparison function */
        int     (*bt_pfx) __P((const DBT *, const DBT *));

-

                                        /* R: recno input function */
        int     (*bt_irec) __P((struct BTREE *, recno_t));
                                        /* R: recno input function */
        int     (*bt_irec) __P((struct BTREE *, recno_t));

-       recno_t bt_nrecs;               /* R: number of records in the tree */
+
+       FILE    *bt_rfp;                /* R: record FILE pointer */
+       int     bt_rfd;                 /* R: record file descriptor */
+
+       caddr_t bt_cmap;                /* R: current point in mapped space */

        caddr_t bt_smap;                /* R: start of mapped space */
        caddr_t bt_emap;                /* R: end of mapped space */
        caddr_t bt_smap;                /* R: start of mapped space */
        caddr_t bt_emap;                /* R: end of mapped space */

+       size_t  bt_msize;               /* R: size of mapped region. */
+
+       recno_t bt_nrecs;               /* R: number of records */

        size_t  bt_reclen;              /* R: fixed record length */
        u_char  bt_bval;                /* R: delimiting byte/pad character */
 
        size_t  bt_reclen;              /* R: fixed record length */
        u_char  bt_bval;                /* R: delimiting byte/pad character */
 

-#define        BTF_DELCRSR     0x001           /* B: delete cursor when closes/moves */
-#define        BTF_FIXEDLEN    0x002           /* fixed length records */
-#define        BTF_INMEM       0x004           /* in-memory tree */
-#define        BTF_METADIRTY   0x008           /* B: need to write meta-data */
-#define        BTF_MODIFIED    0x010           /* tree modified */
-#define        BTF_NODUPS      0x020           /* no duplicate keys permitted */
-#define        BTF_RDONLY      0x040           /* read-only tree */
-#define        BTF_RECNO       0x080           /* record oriented tree */
-#define        BTF_SEQINIT     0x100           /* sequential scan initialized */
+/*
+ * NB:
+ * B_NODUPS and R_RECNO are stored on disk, and may not be changed.
+ */
+#define        B_DELCRSR       0x00001         /* cursor has been deleted */
+#define        B_INMEM         0x00002         /* in-memory tree */
+#define        B_METADIRTY     0x00004         /* need to write metadata */
+#define        B_MODIFIED      0x00008         /* tree modified */
+#define        B_NEEDSWAP      0x00010         /* if byte order requires swapping */
+#define        B_NODUPS        0x00020         /* no duplicate keys permitted */
+#define        B_RDONLY        0x00040         /* read-only tree */
+#define        B_SEQINIT       0x00100         /* sequential scan initialized */
+
+#define        R_CLOSEFP       0x00200         /* opened a file pointer */
+#define        R_EOF           0x00400         /* end of input file reached. */
+#define        R_FIXLEN        0x00800         /* fixed length records */
+#define        R_MEMMAPPED     0x01000         /* memory mapped file. */
+#define        R_RECNO         0x00080         /* record oriented tree */
+#define        R_INMEM         0x02000         /* in-memory file */
+#define        R_MODIFIED      0x04000         /* modified file */
+#define        R_RDONLY        0x08000         /* read-only file */
+

        u_long          bt_flags;       /* btree state */
 } BTREE;
 
        u_long          bt_flags;       /* btree state */
 } BTREE;
 

-#define        ISSET(t, f)     ((t)->bt_flags & (f))
-#define        NOTSET(t, f)    (!((t)->bt_flags & (f)))

 #define        SET(t, f)       ((t)->bt_flags |= (f))
 #define        SET(t, f)       ((t)->bt_flags |= (f))

-#define        UNSET(t, f)     ((t)->bt_flags &= ~(f))
+#define        CLR(t, f)       ((t)->bt_flags &= ~(f))
+#define        ISSET(t, f)     ((t)->bt_flags & (f))

 
 #include "extern.h"
 
 #include "extern.h"