usr/src/cmd/sendmail/db/include/hash.h

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7 /*
   8  * Copyright (c) 1990, 1993, 1994
   9  *      Margo Seltzer.  All rights reserved.
  10  */
  11 /*
  12  * Copyright (c) 1990, 1993, 1994
  13  *      The Regents of the University of California.  All rights reserved.
  14  *
  15  * This code is derived from software contributed to Berkeley by
  16  * Margo Seltzer.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  * 3. All advertising materials mentioning features or use of this software
  27  *    must display the following acknowledgement:
  28  *      This product includes software developed by the University of
  29  *      California, Berkeley and its contributors.
  30  * 4. Neither the name of the University nor the names of its contributors
  31  *    may be used to endorse or promote products derived from this software
  32  *    without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44  * SUCH DAMAGE.
  45  *
  46  *      @(#)hash.h      10.14 (Sleepycat) 10/4/98
  47  */
  48
  49 /* Cursor structure definitions. */
  50 typedef struct cursor_t {
  51         DBC             *dbc;
  52
  53         /* Per-thread information */
  54         DB_LOCK hlock;                  /* Metadata page lock. */
  55         HASHHDR *hdr;                   /* Pointer to meta-data page. */
  56         PAGE *split_buf;                /* Temporary buffer for splits. */
  57         struct __db_h_stat stats;       /* Hash statistics. */
  58
  59         /* Hash cursor information */
  60         db_pgno_t       bucket;         /* Bucket we are traversing. */
  61         db_pgno_t       lbucket;        /* Bucket for which we are locked. */
  62         DB_LOCK         lock;           /* Lock held on the current bucket. */
  63         PAGE            *pagep;         /* The current page. */
  64         db_pgno_t       pgno;           /* Current page number. */
  65         db_indx_t       bndx;           /* Index within the current page. */
  66         PAGE            *dpagep;        /* Duplicate page pointer. */
  67         db_pgno_t       dpgno;          /* Duplicate page number. */
  68         db_indx_t       dndx;           /* Index within a duplicate set. */
  69         db_indx_t       dup_off;        /* Offset within a duplicate set. */
  70         db_indx_t       dup_len;        /* Length of current duplicate. */
  71         db_indx_t       dup_tlen;       /* Total length of duplicate entry. */
  72         u_int32_t       seek_size;      /* Number of bytes we need for add. */
  73         db_pgno_t       seek_found_page;/* Page on which we can insert. */
  74
  75 #define H_DELETED       0x0001          /* Cursor item is deleted. */
  76 #define H_DUPONLY       0x0002          /* Dups only; do not change key. */
  77 #define H_EXPAND        0x0004          /* Table expanded. */
  78 #define H_ISDUP         0x0008          /* Cursor is within duplicate set. */
  79 #define H_NOMORE        0x0010          /* No more entries in bucket. */
  80 #define H_OK            0x0020          /* Request succeeded. */
  81 #define H_DIRTY         0x0040          /* Meta-data page needs to be written */
  82 #define H_ORIGINAL      0x0080          /* Bucket lock existed on entry. */
  83         u_int32_t       flags;
  84 } HASH_CURSOR;
  85
  86 #define IS_VALID(C) ((C)->bucket != BUCKET_INVALID)
  87
  88 #define SAVE_CURSOR(ORIG, COPY) {                                       \
  89         F_SET((ORIG), H_ORIGINAL);                                      \
  90         *(COPY) = *(ORIG);                                              \
  91 }
  92
  93 #define RESTORE_CURSOR(D, ORIG, COPY, RET) {                            \
  94         if ((RET) == 0) {                                               \
  95                 if ((ORIG)->dbc->txn == NULL &&                         \
  96                     (COPY)->lock != 0 && (ORIG)->lock != (COPY)->lock)  \
  97                         (void)lock_put((D)->dbenv->lk_info, (COPY)->lock); \
  98         } else {                                                        \
  99                 if ((ORIG)->dbc->txn == NULL &&                         \
 100                     (ORIG)->lock != 0 && (ORIG)->lock != (COPY)->lock)  \
 101                         (void)lock_put((D)->dbenv->lk_info, (ORIG)->lock); \
 102                 *ORIG = *COPY;                                          \
 103         }                                                               \
 104 }
 105
 106 /*
 107  * More interface macros used to get/release the meta data page.
 108  */
 109 #define GET_META(D, I, R) {                                             \
 110         if (F_ISSET(D, DB_AM_LOCKING) &&                                \
 111             !F_ISSET((I)->dbc, DBC_RECOVER)) {                          \
 112                 (I)->dbc->lock.pgno = BUCKET_INVALID;                   \
 113                 (R) = lock_get((D)->dbenv->lk_info, (I)->dbc->locker,   \
 114                     0, &(I)->dbc->lock_dbt, DB_LOCK_READ, &(I)->hlock); \
 115                 (R) = (R) < 0 ? EAGAIN : (R);                           \
 116         }                                                               \
 117         if ((R) == 0 &&                                                 \
 118             ((R) = __ham_get_page(D, 0, (PAGE **)&((I)->hdr))) != 0 &&  \
 119             (I)->hlock != LOCK_INVALID) {                               \
 120                 (void)lock_put((D)->dbenv->lk_info, (I)->hlock);        \
 121                 (I)->hlock = LOCK_INVALID;                              \
 122         }                                                               \
 123 }
 124
 125 #define RELEASE_META(D, I) {                                            \
 126         if ((I)->hdr)                                                   \
 127                 (void)__ham_put_page(D, (PAGE *)(I)->hdr,               \
 128                     F_ISSET(I, H_DIRTY) ? 1 : 0);                       \
 129         (I)->hdr = NULL;                                                \
 130         if (!F_ISSET((I)->dbc, DBC_RECOVER) &&                          \
 131             (I)->dbc->txn == NULL && (I)->hlock)                        \
 132                 (void)lock_put((D)->dbenv->lk_info, (I)->hlock);        \
 133         (I)->hlock = LOCK_INVALID;                                      \
 134         F_CLR(I, H_DIRTY);                                              \
 135 }
 136
 137 #define DIRTY_META(D, I, R) {                                           \
 138         if (F_ISSET(D, DB_AM_LOCKING) &&                                \
 139             !F_ISSET((I)->dbc, DBC_RECOVER)) {                          \
 140                 DB_LOCK _tmp;                                           \
 141                 (I)->dbc->lock.pgno = BUCKET_INVALID;                   \
 142                 if (((R) = lock_get((D)->dbenv->lk_info,                \
 143                     (I)->dbc->locker, 0, &(I)->dbc->lock_dbt,           \
 144                     DB_LOCK_WRITE, &_tmp)) == 0)                        \
 145                         (R) = lock_put((D)->dbenv->lk_info, (I)->hlock);\
 146                 else if ((R) < 0)                                       \
 147                         (R) = EAGAIN;                                   \
 148                 (I)->hlock = _tmp;                                      \
 149         }                                                               \
 150         F_SET((I), H_DIRTY);                                            \
 151 }
 152
 153 /* Test string. */
 154 #define CHARKEY                 "%$sniglet^&"
 155
 156 /* Overflow management */
 157 /*
 158  * Overflow page numbers are allocated per split point.  At each doubling of
 159  * the table, we can allocate extra pages.  We keep track of how many pages
 160  * we've allocated at each point to calculate bucket to page number mapping.
 161  */
 162 #define BUCKET_TO_PAGE(I, B) \
 163         ((B) + 1 + ((B) ? (I)->hdr->spares[__db_log2((B)+1)-1] : 0))
 164
 165 #define PGNO_OF(I, S, O) (BUCKET_TO_PAGE((I), (1 << (S)) - 1) + (O))
 166
 167 /* Constraints about number of pages and how much data goes on a page. */
 168
 169 #define MAX_PAGES(H)    UINT32_T_MAX
 170 #define MINFILL         4
 171 #define ISBIG(I, N)     (((N) > ((I)->hdr->pagesize / MINFILL)) ? 1 : 0)
 172
 173 /* Shorthands for accessing structure */
 174 #define NDX_INVALID     0xFFFF
 175 #define BUCKET_INVALID  0xFFFFFFFF
 176
 177 /* On page duplicates are stored as a string of size-data-size triples. */
 178 #define DUP_SIZE(len)   ((len) + 2 * sizeof(db_indx_t))
 179
 180 /* Log messages types (these are subtypes within a record type) */
 181 #define PAIR_KEYMASK            0x1
 182 #define PAIR_DATAMASK           0x2
 183 #define PAIR_ISKEYBIG(N)        (N & PAIR_KEYMASK)
 184 #define PAIR_ISDATABIG(N)       (N & PAIR_DATAMASK)
 185 #define OPCODE_OF(N)            (N & ~(PAIR_KEYMASK | PAIR_DATAMASK))
 186
 187 #define PUTPAIR         0x20
 188 #define DELPAIR         0x30
 189 #define PUTOVFL         0x40
 190 #define DELOVFL         0x50
 191 #define ALLOCPGNO       0x60
 192 #define DELPGNO         0x70
 193 #define SPLITOLD        0x80
 194 #define SPLITNEW        0x90
 195
 196 #include "hash_auto.h"
 197 #include "hash_ext.h"
 198 #include "db_am.h"
 199 #include "common_ext.h"