db.subproj/hash.subproj/hash.h

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