lib/libc/db/hash/hash.h

   1 /*      $NetBSD: hash.h,v 1.15 2008/08/26 21:18:38 joerg Exp $  */
   2
   3 /*-
   4  * Copyright (c) 1990, 1993, 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Margo Seltzer.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  *      @(#)hash.h      8.3 (Berkeley) 5/31/94
  35  */
  36
  37 #if HAVE_NBTOOL_CONFIG_H
  38 #include "nbtool_config.h"
  39 #endif
  40
  41 /* Operations */
  42 typedef enum {
  43         HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
  44 } ACTION;
  45
  46 /* Buffer Management structures */
  47 typedef struct _bufhead BUFHEAD;
  48
  49 struct _bufhead {
  50         BUFHEAD         *prev;          /* LRU links */
  51         BUFHEAD         *next;          /* LRU links */
  52         BUFHEAD         *ovfl;          /* Overflow page buffer header */
  53         uint32_t         addr;          /* Address of this page */
  54         char            *page;          /* Actual page data */
  55         char            flags;
  56 #define BUF_MOD         0x0001
  57 #define BUF_DISK        0x0002
  58 #define BUF_BUCKET      0x0004
  59 #define BUF_PIN         0x0008
  60 };
  61
  62 #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
  63
  64 typedef BUFHEAD **SEGMENT;
  65
  66 /* Hash Table Information */
  67 typedef struct hashhdr {                /* Disk resident portion */
  68         int32_t         magic;          /* Magic NO for hash tables */
  69         int32_t         version;        /* Version ID */
  70         uint32_t        lorder;         /* Byte Order */
  71         int32_t         bsize;          /* Bucket/Page Size */
  72         int32_t         bshift;         /* Bucket shift */
  73         int32_t         dsize;          /* Directory Size */
  74         int32_t         ssize;          /* Segment Size */
  75         int32_t         sshift;         /* Segment shift */
  76         int32_t         ovfl_point;     /* Where overflow pages are being
  77                                          * allocated */
  78         int32_t         last_freed;     /* Last overflow page freed */
  79         int32_t         max_bucket;     /* ID of Maximum bucket in use */
  80         int32_t         high_mask;      /* Mask to modulo into entire table */
  81         int32_t         low_mask;       /* Mask to modulo into lower half of
  82                                          * table */
  83         int32_t         ffactor;        /* Fill factor */
  84         int32_t         nkeys;          /* Number of keys in hash table */
  85         int32_t         hdrpages;       /* Size of table header */
  86         int32_t         h_charkey;      /* value of hash(CHARKEY) */
  87 #define NCACHED 32                      /* number of bit maps and spare
  88                                          * points */
  89         int32_t         spares[NCACHED];/* spare pages for overflow */
  90         uint16_t        bitmaps[NCACHED];       /* address of overflow page
  91                                                  * bitmaps */
  92 } HASHHDR;
  93
  94 typedef struct htab      {              /* Memory resident data structure */
  95         HASHHDR         hdr;            /* Header */
  96         int             nsegs;          /* Number of allocated segments */
  97         int             exsegs;         /* Number of extra allocated
  98                                          * segments */
  99         uint32_t        (*hash)(const void *, size_t);  /* Hash function */
 100         int             flags;          /* Flag values */
 101         int             fp;             /* File pointer */
 102         char            *tmp_buf;       /* Temporary Buffer for BIG data */
 103         char            *tmp_key;       /* Temporary Buffer for BIG keys */
 104         BUFHEAD         *cpage;         /* Current page */
 105         int             cbucket;        /* Current bucket */
 106         int             cndx;           /* Index of next item on cpage */
 107         int             err;            /* Error Number -- for DBM
 108                                          * compatibility */
 109         int             new_file;       /* Indicates if fd is backing store
 110                                          * or no */
 111         int             save_file;      /* Indicates whether we need to flush
 112                                          * file at
 113                                          * exit */
 114         uint32_t        *mapp[NCACHED]; /* Pointers to page maps */
 115         int             nmaps;          /* Initial number of bitmaps */
 116         int             nbufs;          /* Number of buffers left to
 117                                          * allocate */
 118         BUFHEAD         bufhead;        /* Header of buffer lru list */
 119         SEGMENT         *dir;           /* Hash Bucket directory */
 120 } HTAB;
 121
 122 /*
 123  * Constants
 124  */
 125 #define MAX_BSIZE               65536           /* 2^16 */
 126 #define MIN_BUFFERS             6
 127 #define MINHDRSIZE              512
 128 #define DEF_BUFSIZE             65536           /* 64 K */
 129 #define DEF_BUCKET_SIZE         4096
 130 #define DEF_BUCKET_SHIFT        12              /* log2(BUCKET) */
 131 #define DEF_SEGSIZE             256
 132 #define DEF_SEGSIZE_SHIFT       8               /* log2(SEGSIZE)         */
 133 #define DEF_DIRSIZE             256
 134 #define DEF_FFACTOR             65536
 135 #define MIN_FFACTOR             4
 136 #define SPLTMAX                 8
 137 #define CHARKEY                 "%$sniglet^&"
 138 #define NUMKEY                  1038583
 139 #define BYTE_SHIFT              3
 140 #define INT_TO_BYTE             2
 141 #define INT_BYTE_SHIFT          5
 142 #define ALL_SET                 ((uint32_t)0xFFFFFFFF)
 143 #define ALL_CLEAR               0
 144
 145 #define PTROF(X)        ((BUFHEAD *)(void *)((u_long)(X)&~0x3))
 146 #define ISMOD(X)        ((uint32_t)(u_long)(X)&0x1)
 147 #define DOMOD(X)        ((X) = (char *)(void *)((u_long)(X)|0x1))
 148 #define ISDISK(X)       ((uint32_t)(u_long)(X)&0x2)
 149 #define DODISK(X)       ((X) = (char *)(void *)((u_long)(X)|0x2))
 150
 151 #define BITS_PER_MAP    32
 152
 153 /* Given the address of the beginning of a big map, clear/set the nth bit */
 154 #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
 155 #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
 156 #define ISSET(A, N)     ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
 157
 158 /* Overflow management */
 159 /*
 160  * Overflow page numbers are allocated per split point.  At each doubling of
 161  * the table, we can allocate extra pages.  So, an overflow page number has
 162  * the top 5 bits indicate which split point and the lower 11 bits indicate
 163  * which page at that split point is indicated (pages within split points are
 164  * numberered starting with 1).
 165  */
 166
 167 #define SPLITSHIFT      11
 168 #define SPLITMASK       0x7FF
 169 #define SPLITNUM(N)     (((uint32_t)(N)) >> SPLITSHIFT)
 170 #define OPAGENUM(N)     ((N) & SPLITMASK)
 171 #define OADDR_OF(S,O)   ((uint32_t)((uint32_t)(S) << SPLITSHIFT) + (O))
 172
 173 #define BUCKET_TO_PAGE(B) \
 174         (B) + hashp->HDRPAGES + \
 175         ((B) ? hashp->SPARES[__log2((uint32_t)((B)+1))-1] : 0)
 176 #define OADDR_TO_PAGE(B)        \
 177         BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
 178
 179 /*
 180  * page.h contains a detailed description of the page format.
 181  *
 182  * Normally, keys and data are accessed from offset tables in the top of
 183  * each page which point to the beginning of the key and data.  There are
 184  * four flag values which may be stored in these offset tables which indicate
 185  * the following:
 186  *
 187  *
 188  * OVFLPAGE     Rather than a key data pair, this pair contains
 189  *              the address of an overflow page.  The format of
 190  *              the pair is:
 191  *                  OVERFLOW_PAGE_NUMBER OVFLPAGE
 192  *
 193  * PARTIAL_KEY  This must be the first key/data pair on a page
 194  *              and implies that page contains only a partial key.
 195  *              That is, the key is too big to fit on a single page
 196  *              so it starts on this page and continues on the next.
 197  *              The format of the page is:
 198  *                  KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
 199  *
 200  *                  KEY_OFF -- offset of the beginning of the key
 201  *                  PARTIAL_KEY -- 1
 202  *                  OVFL_PAGENO - page number of the next overflow page
 203  *                  OVFLPAGE -- 0
 204  *
 205  * FULL_KEY     This must be the first key/data pair on the page.  It
 206  *              is used in two cases.
 207  *
 208  *              Case 1:
 209  *                  There is a complete key on the page but no data
 210  *                  (because it wouldn't fit).  The next page contains
 211  *                  the data.
 212  *
 213  *                  Page format it:
 214  *                  KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
 215  *
 216  *                  KEY_OFF -- offset of the beginning of the key
 217  *                  FULL_KEY -- 2
 218  *                  OVFL_PAGENO - page number of the next overflow page
 219  *                  OVFLPAGE -- 0
 220  *
 221  *              Case 2:
 222  *                  This page contains no key, but part of a large
 223  *                  data field, which is continued on the next page.
 224  *
 225  *                  Page format it:
 226  *                  DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
 227  *
 228  *                  KEY_OFF -- offset of the beginning of the data on
 229  *                              this page
 230  *                  FULL_KEY -- 2
 231  *                  OVFL_PAGENO - page number of the next overflow page
 232  *                  OVFLPAGE -- 0
 233  *
 234  * FULL_KEY_DATA
 235  *              This must be the first key/data pair on the page.
 236  *              There are two cases:
 237  *
 238  *              Case 1:
 239  *                  This page contains a key and the beginning of the
 240  *                  data field, but the data field is continued on the
 241  *                  next page.
 242  *
 243  *                  Page format is:
 244  *                  KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
 245  *
 246  *                  KEY_OFF -- offset of the beginning of the key
 247  *                  FULL_KEY_DATA -- 3
 248  *                  OVFL_PAGENO - page number of the next overflow page
 249  *                  DATA_OFF -- offset of the beginning of the data
 250  *
 251  *              Case 2:
 252  *                  This page contains the last page of a big data pair.
 253  *                  There is no key, only the  tail end of the data
 254  *                  on this page.
 255  *
 256  *                  Page format is:
 257  *                  DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
 258  *
 259  *                  DATA_OFF -- offset of the beginning of the data on
 260  *                              this page
 261  *                  FULL_KEY_DATA -- 3
 262  *                  OVFL_PAGENO - page number of the next overflow page
 263  *                  OVFLPAGE -- 0
 264  *
 265  *                  OVFL_PAGENO and OVFLPAGE are optional (they are
 266  *                  not present if there is no next page).
 267  */
 268
 269 #define OVFLPAGE        0
 270 #define PARTIAL_KEY     1
 271 #define FULL_KEY        2
 272 #define FULL_KEY_DATA   3
 273 #define REAL_KEY        4
 274
 275 /* Short hands for accessing structure */
 276 #define BSIZE           hdr.bsize
 277 #define BSHIFT          hdr.bshift
 278 #define DSIZE           hdr.dsize
 279 #define SGSIZE          hdr.ssize
 280 #define SSHIFT          hdr.sshift
 281 #define LORDER          hdr.lorder
 282 #define OVFL_POINT      hdr.ovfl_point
 283 #define LAST_FREED      hdr.last_freed
 284 #define MAX_BUCKET      hdr.max_bucket
 285 #define FFACTOR         hdr.ffactor
 286 #define HIGH_MASK       hdr.high_mask
 287 #define LOW_MASK        hdr.low_mask
 288 #define NKEYS           hdr.nkeys
 289 #define HDRPAGES        hdr.hdrpages
 290 #define SPARES          hdr.spares
 291 #define BITMAPS         hdr.bitmaps
 292 #define VERSION         hdr.version
 293 #define MAGIC           hdr.magic
 294 #define NEXT_FREE       hdr.next_free
 295 #define H_CHARKEY       hdr.h_charkey