dbm/include/hash.h

   1 /*-
   2  * Copyright (c) 1990, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Margo Seltzer.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. ***REMOVED*** - see
  17  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
  18  * 4. 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 /* Operations */
  38
  39 #include <stdio.h>
  40 #include "mcom_db.h"
  41 typedef enum {
  42         HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
  43 } ACTION;
  44
  45 /* Buffer Management structures */
  46 typedef struct _bufhead BUFHEAD;
  47
  48 struct _bufhead {
  49         BUFHEAD         *prev;          /* LRU links */
  50         BUFHEAD         *next;          /* LRU links */
  51         BUFHEAD         *ovfl;          /* Overflow page buffer header */
  52         uint32          addr;           /* Address of this page */
  53         char            *page;          /* Actual page data */
  54         char            is_disk;
  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 typedef int DBFILE_PTR;
  67 #define NO_FILE -1
  68 #ifdef macintosh
  69 #define DBFILE_OPEN(path, flag,mode) open((path), flag)
  70 #define EXISTS(path)
  71 #else
  72 #define DBFILE_OPEN(path, flag,mode) open((path), (flag), (mode))
  73 #endif
  74 /* Hash Table Information */
  75 typedef struct hashhdr {                /* Disk resident portion */
  76         int32           magic;          /* Magic NO for hash tables */
  77         int32           version;        /* Version ID */
  78         uint32          lorder;         /* Byte Order */
  79         int32           bsize;          /* Bucket/Page Size */
  80         int32           bshift;         /* Bucket shift */
  81         int32           dsize;          /* Directory Size */
  82         int32           ssize;          /* Segment Size */
  83         int32           sshift;         /* Segment shift */
  84         int32           ovfl_point;     /* Where overflow pages are being
  85                                          * allocated */
  86         int32           last_freed;     /* Last overflow page freed */
  87         int32           max_bucket;     /* ID of Maximum bucket in use */
  88         int32           high_mask;      /* Mask to modulo into entire table */
  89         int32           low_mask;       /* Mask to modulo into lower half of
  90                                          * table */
  91         int32           ffactor;        /* Fill factor */
  92         int32           nkeys;          /* Number of keys in hash table */
  93         int32           hdrpages;       /* Size of table header */
  94         uint32          h_charkey;      /* value of hash(CHARKEY) */
  95 #define NCACHED 32                      /* number of bit maps and spare
  96                                          * points */
  97         int32           spares[NCACHED];/* spare pages for overflow */
  98         uint16          bitmaps[NCACHED];       /* address of overflow page
  99                                                  * bitmaps */
 100 } HASHHDR;
 101
 102 typedef struct htab      {              /* Memory resident data structure */
 103         HASHHDR         hdr;            /* Header */
 104         int             nsegs;          /* Number of allocated segments */
 105         int             exsegs;         /* Number of extra allocated
 106                                          * segments */
 107         uint32                  /* Hash function */
 108             (*hash)(const void *, size_t);
 109         int             flags;          /* Flag values */
 110         DBFILE_PTR      fp;             /* File pointer */
 111         char            *filename;
 112         char            *tmp_buf;       /* Temporary Buffer for BIG data */
 113         char            *tmp_key;       /* Temporary Buffer for BIG keys */
 114         BUFHEAD         *cpage;         /* Current page */
 115         int             cbucket;        /* Current bucket */
 116         int             cndx;           /* Index of next item on cpage */
 117         int             dbmerrno;               /* Error Number -- for DBM
 118                                          * compatability */
 119         int             new_file;       /* Indicates if fd is backing store
 120                                          * or no */
 121         int             save_file;      /* Indicates whether we need to flush
 122                                          * file at
 123                                          * exit */
 124         uint32          *mapp[NCACHED]; /* Pointers to page maps */
 125         int             nmaps;          /* Initial number of bitmaps */
 126         int             nbufs;          /* Number of buffers left to
 127                                          * allocate */
 128         BUFHEAD         bufhead;        /* Header of buffer lru list */
 129         SEGMENT         *dir;           /* Hash Bucket directory */
 130         off_t           file_size;      /* in bytes */
 131         char            is_temp;        /* unlink file on close */
 132         char            updateEOF;      /* force EOF update on flush */
 133 } HTAB;
 134
 135 /*
 136  * Constants
 137  */
 138 #define DATABASE_CORRUPTED_ERROR -999   /* big ugly abort, delete database */
 139 #define OLD_MAX_BSIZE           65536           /* 2^16 */
 140 #define MAX_BSIZE               32l*1024l         /* 2^15 */
 141 #define MIN_BUFFERS             6
 142 #define MINHDRSIZE              512
 143 #define DEF_BUFSIZE             65536l          /* 64 K */
 144 #define DEF_BUCKET_SIZE         4096
 145 #define DEF_BUCKET_SHIFT        12              /* log2(BUCKET) */
 146 #define DEF_SEGSIZE             256
 147 #define DEF_SEGSIZE_SHIFT       8               /* log2(SEGSIZE)         */
 148 #define DEF_DIRSIZE             256
 149 #define DEF_FFACTOR             65536l
 150 #define MIN_FFACTOR             4
 151 #define SPLTMAX                 8
 152 #define CHARKEY                 "%$sniglet^&"
 153 #define NUMKEY                  1038583l
 154 #define BYTE_SHIFT              3
 155 #define INT_TO_BYTE             2
 156 #define INT_BYTE_SHIFT          5
 157 #define ALL_SET                 ((uint32)0xFFFFFFFF)
 158 #define ALL_CLEAR               0
 159
 160 #define PTROF(X)        ((ptrdiff_t)(X) == BUF_DISK ? 0 : (X))
 161 #define ISDISK(X)       ((X) ? ((ptrdiff_t)(X) == BUF_DISK ? BUF_DISK \
 162                                 : (X)->is_disk) : 0)
 163
 164 #define BITS_PER_MAP    32
 165
 166 /* Given the address of the beginning of a big map, clear/set the nth bit */
 167 #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
 168 #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
 169 #define ISSET(A, N)     ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
 170
 171 /* Overflow management */
 172 /*
 173  * Overflow page numbers are allocated per split point.  At each doubling of
 174  * the table, we can allocate extra pages.  So, an overflow page number has
 175  * the top 5 bits indicate which split point and the lower 11 bits indicate
 176  * which page at that split point is indicated (pages within split points are
 177  * numberered starting with 1).
 178  */
 179
 180 #define SPLITSHIFT      11
 181 #define SPLITMASK       0x7FF
 182 #define SPLITNUM(N)     (((uint32)(N)) >> SPLITSHIFT)
 183 #define OPAGENUM(N)     ((N) & SPLITMASK)
 184 #define OADDR_OF(S,O)   ((uint32)((uint32)(S) << SPLITSHIFT) + (O))
 185
 186 #define BUCKET_TO_PAGE(B) \
 187         (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((uint32)((B)+1))-1] : 0)
 188 #define OADDR_TO_PAGE(B)        \
 189         BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
 190
 191 /*
 192  * page.h contains a detailed description of the page format.
 193  *
 194  * Normally, keys and data are accessed from offset tables in the top of
 195  * each page which point to the beginning of the key and data.  There are
 196  * four flag values which may be stored in these offset tables which indicate
 197  * the following:
 198  *
 199  *
 200  * OVFLPAGE     Rather than a key data pair, this pair contains
 201  *              the address of an overflow page.  The format of
 202  *              the pair is:
 203  *                  OVERFLOW_PAGE_NUMBER OVFLPAGE
 204  *
 205  * PARTIAL_KEY  This must be the first key/data pair on a page
 206  *              and implies that page contains only a partial key.
 207  *              That is, the key is too big to fit on a single page
 208  *              so it starts on this page and continues on the next.
 209  *              The format of the page is:
 210  *                  KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
 211  *
 212  *                  KEY_OFF -- offset of the beginning of the key
 213  *                  PARTIAL_KEY -- 1
 214  *                  OVFL_PAGENO - page number of the next overflow page
 215  *                  OVFLPAGE -- 0
 216  *
 217  * FULL_KEY     This must be the first key/data pair on the page.  It
 218  *              is used in two cases.
 219  *
 220  *              Case 1:
 221  *                  There is a complete key on the page but no data
 222  *                  (because it wouldn't fit).  The next page contains
 223  *                  the data.
 224  *
 225  *                  Page format it:
 226  *                  KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
 227  *
 228  *                  KEY_OFF -- offset of the beginning of the key
 229  *                  FULL_KEY -- 2
 230  *                  OVFL_PAGENO - page number of the next overflow page
 231  *                  OVFLPAGE -- 0
 232  *
 233  *              Case 2:
 234  *                  This page contains no key, but part of a large
 235  *                  data field, which is continued on the next page.
 236  *
 237  *                  Page format it:
 238  *                  DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
 239  *
 240  *                  KEY_OFF -- offset of the beginning of the data on
 241  *                              this page
 242  *                  FULL_KEY -- 2
 243  *                  OVFL_PAGENO - page number of the next overflow page
 244  *                  OVFLPAGE -- 0
 245  *
 246  * FULL_KEY_DATA
 247  *              This must be the first key/data pair on the page.
 248  *              There are two cases:
 249  *
 250  *              Case 1:
 251  *                  This page contains a key and the beginning of the
 252  *                  data field, but the data field is continued on the
 253  *                  next page.
 254  *
 255  *                  Page format is:
 256  *                  KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
 257  *
 258  *                  KEY_OFF -- offset of the beginning of the key
 259  *                  FULL_KEY_DATA -- 3
 260  *                  OVFL_PAGENO - page number of the next overflow page
 261  *                  DATA_OFF -- offset of the beginning of the data
 262  *
 263  *              Case 2:
 264  *                  This page contains the last page of a big data pair.
 265  *                  There is no key, only the  tail end of the data
 266  *                  on this page.
 267  *
 268  *                  Page format is:
 269  *                  DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
 270  *
 271  *                  DATA_OFF -- offset of the beginning of the data on
 272  *                              this page
 273  *                  FULL_KEY_DATA -- 3
 274  *                  OVFL_PAGENO - page number of the next overflow page
 275  *                  OVFLPAGE -- 0
 276  *
 277  *                  OVFL_PAGENO and OVFLPAGE are optional (they are
 278  *                  not present if there is no next page).
 279  */
 280
 281 #define OVFLPAGE        0
 282 #define PARTIAL_KEY     1
 283 #define FULL_KEY        2
 284 #define FULL_KEY_DATA   3
 285 #define REAL_KEY        4
 286
 287 /* Short hands for accessing structure */
 288 #undef BSIZE
 289 #define BSIZE           hdr.bsize
 290 #undef BSHIFT
 291 #define BSHIFT          hdr.bshift
 292 #define DSIZE           hdr.dsize
 293 #define SGSIZE          hdr.ssize
 294 #define SSHIFT          hdr.sshift
 295 #define LORDER          hdr.lorder
 296 #define OVFL_POINT      hdr.ovfl_point
 297 #define LAST_FREED      hdr.last_freed
 298 #define MAX_BUCKET      hdr.max_bucket
 299 #define FFACTOR         hdr.ffactor
 300 #define HIGH_MASK       hdr.high_mask
 301 #define LOW_MASK        hdr.low_mask
 302 #define NKEYS           hdr.nkeys
 303 #define HDRPAGES        hdr.hdrpages
 304 #define SPARES          hdr.spares
 305 #define BITMAPS         hdr.bitmaps
 306 #define VERSION         hdr.version
 307 #define MAGIC           hdr.magic
 308 #define NEXT_FREE       hdr.next_free
 309 #define H_CHARKEY       hdr.h_charkey
 310
 311 extern uint32 (*__default_hash) (const void *, size_t);
 312 void __buf_init(HTAB *hashp, int32 nbytes);
 313 int __big_delete(HTAB *hashp, BUFHEAD *bufp);
 314 BUFHEAD * __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage);
 315 uint32 __call_hash(HTAB *hashp, char *k, size_t len);
 316 #include "page.h"
 317 extern int __big_split(HTAB *hashp, BUFHEAD *op,BUFHEAD *np,
 318 BUFHEAD *big_keyp,uint32 addr,uint32   obucket, SPLIT_RETURN *ret);
 319 void __free_ovflpage(HTAB *hashp, BUFHEAD *obufp);
 320 BUFHEAD * __add_ovflpage(HTAB *hashp, BUFHEAD *bufp);
 321 int __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val);
 322 int __expand_table(HTAB *hashp);
 323 uint32 __log2(uint32 num);
 324 void __reclaim_buf(HTAB *hashp, BUFHEAD *bp);
 325 int __get_page(HTAB *hashp, char * p, uint32 bucket, int is_bucket, int is_disk, int is_bitmap);
 326 int __put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap);
 327 int __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx);
 328 int __buf_free(HTAB *hashp, int do_free, int to_disk);
 329 int __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size);
 330 uint16 __find_last_page(HTAB *hashp, BUFHEAD **bpp);
 331 int __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT * val);
 332 int __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current);
 333 int __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx);
 334 int __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set);
 335 int __split_page(HTAB *hashp, uint32 obucket, uint32 nbucket);