db2/include/hash.h

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997
   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.6 (Sleepycat) 8/18/97
  47  */
  48
  49 /* Cursor structure definitions. */
  50 typedef struct cursor_t {
  51         DBC             *db_cursor;
  52         db_pgno_t       bucket;         /* Bucket we are traversing. */
  53         DB_LOCK         lock;           /* Lock held on the current bucket. */
  54         PAGE            *pagep;         /* The current page. */
  55         db_pgno_t       pgno;           /* Current page number. */
  56         db_indx_t       bndx;           /* Index within the current page. */
  57         PAGE            *dpagep;        /* Duplicate page pointer. */
  58         db_pgno_t       dpgno;          /* Duplicate page number. */
  59         db_indx_t       dndx;           /* Index within a duplicate set. */
  60         db_indx_t       dup_off;        /* Offset within a duplicate set. */
  61         db_indx_t       dup_len;        /* Length of current duplicate. */
  62         db_indx_t       dup_tlen;       /* Total length of duplicate entry. */
  63         u_int32_t       seek_size;      /* Number of bytes we need for add. */
  64         db_pgno_t       seek_found_page;/* Page on which we can insert. */
  65         u_int32_t       big_keylen;     /* Length of big_key buffer. */
  66         void            *big_key;       /* Temporary buffer for big keys. */
  67         u_int32_t       big_datalen;    /* Length of big_data buffer. */
  68         void            *big_data;      /* Temporary buffer for big data. */
  69 #define H_OK            0x0001
  70 #define H_NOMORE        0x0002
  71 #define H_DELETED       0x0004
  72 #define H_ISDUP         0x0008
  73 #define H_EXPAND        0x0020
  74         u_int32_t       flags;          /* Is cursor inside a dup set. */
  75 } HASH_CURSOR;
  76
  77 #define IS_VALID(C) ((C)->bucket != BUCKET_INVALID)
  78
  79
  80 typedef struct htab {           /* Memory resident data structure. */
  81         DB *dbp;                /* Pointer to parent db structure. */
  82         DB_LOCK hlock;          /* Metadata page lock. */
  83         HASHHDR *hdr;           /* Pointer to meta-data page. */
  84         u_int32_t (*hash) __P((const void *, u_int32_t)); /* Hash Function */
  85         PAGE *split_buf;        /* Temporary buffer for splits. */
  86         int local_errno;        /* Error Number -- for DBM compatability */
  87         u_long hash_accesses;   /* Number of accesses to this table. */
  88         u_long hash_collisions; /* Number of collisions on search. */
  89         u_long hash_expansions; /* Number of times we added a bucket. */
  90         u_long hash_overflows;  /* Number of overflow pages. */
  91         u_long hash_bigpages;   /* Number of big key/data pages. */
  92 } HTAB;
  93
  94 /*
  95  * Macro used for interface functions to set the txnid in the DBP.
  96  */
  97 #define SET_LOCKER(D, T) ((D)->txn = (T))
  98
  99 /*
 100  * More interface macros used to get/release the meta data page.
 101  */
 102 #define GET_META(D, H) {                                                \
 103         int _r;                                                         \
 104         if (F_ISSET(D, DB_AM_LOCKING) && !F_ISSET(D, DB_AM_RECOVER)) {  \
 105                 (D)->lock.pgno = BUCKET_INVALID;                        \
 106                 if ((_r = lock_get((D)->dbenv->lk_info,                 \
 107                     (D)->txn == NULL ? (D)->locker : (D)->txn->txnid,   \
 108                     0, &(D)->lock_dbt, DB_LOCK_READ,                    \
 109                     &(H)->hlock)) != 0)                                 \
 110                         return (_r < 0 ? EAGAIN : _r);                  \
 111         }                                                               \
 112         if ((_r = __ham_get_page(D, 0, (PAGE **)&((H)->hdr))) != 0) {   \
 113                 if ((H)->hlock) {                                       \
 114                         (void)lock_put((D)->dbenv->lk_info, (H)->hlock);\
 115                         (H)->hlock = 0;                                 \
 116                 }                                                       \
 117                 return (_r);                                            \
 118         }                                                               \
 119 }
 120
 121 #define RELEASE_META(D, H) {                                            \
 122         if (!F_ISSET(D, DB_AM_RECOVER) &&                               \
 123             (D)->txn == NULL && (H)->hlock)                             \
 124                 (void)lock_put((H)->dbp->dbenv->lk_info, (H)->hlock);   \
 125         (H)->hlock = 0;                                                 \
 126         if ((H)->hdr)                                                   \
 127                 (void)__ham_put_page(D, (PAGE *)(H)->hdr,               \
 128                     F_ISSET(D, DB_HS_DIRTYMETA) ? 1 : 0);               \
 129         (H)->hdr = NULL;                                                \
 130         F_CLR(D, DB_HS_DIRTYMETA);                                      \
 131 }
 132
 133 #define DIRTY_META(H, R) {                                              \
 134         if (F_ISSET((H)->dbp, DB_AM_LOCKING) &&                         \
 135             !F_ISSET((H)->dbp, DB_AM_RECOVER)) {                        \
 136                 DB_LOCK _tmp;                                           \
 137                 (H)->dbp->lock.pgno = BUCKET_INVALID;                   \
 138                 if (((R) = lock_get((H)->dbp->dbenv->lk_info,           \
 139                     (H)->dbp->txn ? (H)->dbp->txn->txnid :              \
 140                     (H)->dbp->locker, 0, &(H)->dbp->lock_dbt,           \
 141                     DB_LOCK_WRITE, &_tmp)) == 0)                        \
 142                         (R) = lock_put((H)->dbp->dbenv->lk_info,        \
 143                             (H)->hlock);                                \
 144                 else if ((R) < 0)                                       \
 145                         (R) = EAGAIN;                                   \
 146                 (H)->hlock = _tmp;                                      \
 147         }                                                               \
 148         F_SET((H)->dbp, DB_HS_DIRTYMETA);                               \
 149 }
 150
 151 /* Allocate and discard thread structures. */
 152 #define H_GETHANDLE(dbp, dbpp, ret)                                     \
 153         if (F_ISSET(dbp, DB_AM_THREAD))                                 \
 154                 ret = __db_gethandle(dbp, __ham_hdup, dbpp);            \
 155         else {                                                          \
 156                 ret = 0;                                                \
 157                 *dbpp = dbp;                                            \
 158         }
 159
 160 #define H_PUTHANDLE(dbp) {                                              \
 161         if (F_ISSET(dbp, DB_AM_THREAD))                                 \
 162                 __db_puthandle(dbp);                                    \
 163 }
 164
 165 /* Test string. */
 166 #define CHARKEY                 "%$sniglet^&"
 167
 168 /* Overflow management */
 169 /*
 170  * Overflow page numbers are allocated per split point.  At each doubling of
 171  * the table, we can allocate extra pages.  We keep track of how many pages
 172  * we've allocated at each point to calculate bucket to page number mapping.
 173  */
 174 #define BUCKET_TO_PAGE(H, B) \
 175         ((B) + 1 + ((B) ? (H)->hdr->spares[__db_log2((B)+1)-1] : 0))
 176
 177 #define PGNO_OF(H, S, O) (BUCKET_TO_PAGE((H), (1 << (S)) - 1) + (O))
 178
 179 /* Constraints about number of pages and how much data goes on a page. */
 180
 181 #define MAX_PAGES(H)    UINT32_T_MAX
 182 #define MINFILL         0.25
 183 #define ISBIG(H, N)     (((N) > ((H)->hdr->pagesize * MINFILL)) ? 1 : 0)
 184
 185 /* Shorthands for accessing structure */
 186 #define NDX_INVALID     0xFFFF
 187 #define BUCKET_INVALID  0xFFFFFFFF
 188
 189 /* On page duplicates are stored as a string of size-data-size triples. */
 190 #define DUP_SIZE(len)   ((len) + 2 * sizeof(db_indx_t))
 191
 192 /* Log messages types (these are subtypes within a record type) */
 193 #define PAIR_KEYMASK            0x1
 194 #define PAIR_DATAMASK           0x2
 195 #define PAIR_ISKEYBIG(N)        (N & PAIR_KEYMASK)
 196 #define PAIR_ISDATABIG(N)       (N & PAIR_DATAMASK)
 197 #define OPCODE_OF(N)            (N & ~(PAIR_KEYMASK | PAIR_DATAMASK))
 198
 199 #define PUTPAIR         0x20
 200 #define DELPAIR         0x30
 201 #define PUTOVFL         0x40
 202 #define DELOVFL         0x50
 203 #define ALLOCPGNO       0x60
 204 #define DELPGNO         0x70
 205 #define SPLITOLD        0x80
 206 #define SPLITNEW        0x90
 207
 208 #include "hash_auto.h"
 209 #include "hash_ext.h"
 210 #include "db_am.h"
 211 #include "common_ext.h"