Back to index

lightning-sunbird  0.9+nobinonly
hash.h
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Margo Seltzer.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. ***REMOVED*** - see 
00017  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00018  * 4. Neither the name of the University nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  *
00034  *     @(#)hash.h    8.3 (Berkeley) 5/31/94
00035  */
00036 
00037 /* Operations */
00038 
00039 #include <stdio.h>
00040 #include "mcom_db.h"
00041 typedef enum {
00042        HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
00043 } ACTION;
00044 
00045 /* Buffer Management structures */
00046 typedef struct _bufhead BUFHEAD;
00047 
00048 struct _bufhead {
00049        BUFHEAD              *prev;        /* LRU links */
00050        BUFHEAD              *next;        /* LRU links */
00051        BUFHEAD              *ovfl;        /* Overflow page buffer header */
00052        uint32        addr;         /* Address of this page */
00053        char          *page;        /* Actual page data */
00054        char          is_disk;
00055        char          flags;
00056 #define       BUF_MOD              0x0001
00057 #define BUF_DISK     0x0002
00058 #define       BUF_BUCKET    0x0004
00059 #define       BUF_PIN              0x0008
00060 };
00061 
00062 #define IS_BUCKET(X) ((X) & BUF_BUCKET)
00063 
00064 typedef BUFHEAD **SEGMENT;
00065 
00066 typedef int DBFILE_PTR;
00067 #define NO_FILE -1
00068 #ifdef macintosh
00069 #define DBFILE_OPEN(path, flag,mode) open((path), flag)
00070 #define EXISTS(path)
00071 #else
00072 #define DBFILE_OPEN(path, flag,mode) open((path), (flag), (mode))
00073 #endif
00074 /* Hash Table Information */
00075 typedef struct hashhdr {           /* Disk resident portion */
00076        int32         magic;        /* Magic NO for hash tables */
00077        int32         version;      /* Version ID */
00078        uint32        lorder;              /* Byte Order */
00079        int32         bsize;        /* Bucket/Page Size */
00080        int32         bshift;              /* Bucket shift */
00081        int32         dsize;        /* Directory Size */
00082        int32         ssize;        /* Segment Size */
00083        int32         sshift;              /* Segment shift */
00084        int32         ovfl_point;   /* Where overflow pages are being 
00085                                     * allocated */
00086        int32         last_freed;   /* Last overflow page freed */
00087        int32         max_bucket;   /* ID of Maximum bucket in use */
00088        int32         high_mask;    /* Mask to modulo into entire table */
00089        int32         low_mask;     /* Mask to modulo into lower half of 
00090                                     * table */
00091        int32         ffactor;      /* Fill factor */
00092        int32         nkeys;        /* Number of keys in hash table */
00093        int32         hdrpages;     /* Size of table header */
00094        uint32        h_charkey;    /* value of hash(CHARKEY) */
00095 #define NCACHED      32                   /* number of bit maps and spare 
00096                                     * points */
00097        int32         spares[NCACHED];/* spare pages for overflow */
00098        uint16        bitmaps[NCACHED];    /* address of overflow page 
00099                                            * bitmaps */
00100 } HASHHDR;
00101 
00102 typedef struct htab   {            /* Memory resident data structure */
00103        HASHHDR       hdr;          /* Header */
00104        int           nsegs;        /* Number of allocated segments */
00105        int           exsegs;              /* Number of extra allocated 
00106                                     * segments */
00107        uint32               /* Hash function */
00108            (*hash)(const void *, size_t);
00109        int           flags;        /* Flag values */
00110        DBFILE_PTR    fp;           /* File pointer */
00111        char            *filename;
00112        char          *tmp_buf;     /* Temporary Buffer for BIG data */
00113        char          *tmp_key;     /* Temporary Buffer for BIG keys */
00114        BUFHEAD       *cpage;              /* Current page */
00115        int           cbucket;      /* Current bucket */
00116        int           cndx;         /* Index of next item on cpage */
00117        int           dbmerrno;            /* Error Number -- for DBM 
00118                                     * compatability */
00119        int           new_file;     /* Indicates if fd is backing store 
00120                                     * or no */
00121        int           save_file;    /* Indicates whether we need to flush 
00122                                     * file at
00123                                     * exit */
00124        uint32        *mapp[NCACHED];      /* Pointers to page maps */
00125        int           nmaps;        /* Initial number of bitmaps */
00126        int           nbufs;        /* Number of buffers left to 
00127                                     * allocate */
00128        BUFHEAD       bufhead;      /* Header of buffer lru list */
00129        SEGMENT       *dir;         /* Hash Bucket directory */
00130        off_t         file_size;    /* in bytes */
00131        char          is_temp;      /* unlink file on close */
00132        char          updateEOF;    /* force EOF update on flush */
00133 } HTAB;
00134 
00135 /*
00136  * Constants
00137  */
00138 #define DATABASE_CORRUPTED_ERROR -999   /* big ugly abort, delete database */
00139 #define       OLD_MAX_BSIZE        65536         /* 2^16 */
00140 #define MAX_BSIZE           32l*1024l         /* 2^15 */
00141 #define MIN_BUFFERS         6
00142 #define MINHDRSIZE          512
00143 #define DEF_BUFSIZE         65536l        /* 64 K */
00144 #define DEF_BUCKET_SIZE            4096
00145 #define DEF_BUCKET_SHIFT    12            /* log2(BUCKET) */
00146 #define DEF_SEGSIZE         256
00147 #define DEF_SEGSIZE_SHIFT   8             /* log2(SEGSIZE)      */
00148 #define DEF_DIRSIZE         256
00149 #define DEF_FFACTOR         65536l
00150 #define MIN_FFACTOR         4
00151 #define SPLTMAX                    8
00152 #define CHARKEY                    "%$sniglet^&"
00153 #define NUMKEY                     1038583l
00154 #define BYTE_SHIFT          3
00155 #define INT_TO_BYTE         2
00156 #define INT_BYTE_SHIFT             5
00157 #define ALL_SET                    ((uint32)0xFFFFFFFF)
00158 #define ALL_CLEAR           0
00159 
00160 #define PTROF(X)     ((ptrdiff_t)(X) == BUF_DISK ? 0 : (X))
00161 #define ISDISK(X)    ((X) ? ((ptrdiff_t)(X) == BUF_DISK ? BUF_DISK \
00162                             : (X)->is_disk) : 0)
00163 
00164 #define BITS_PER_MAP 32
00165 
00166 /* Given the address of the beginning of a big map, clear/set the nth bit */
00167 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
00168 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
00169 #define ISSET(A, N)  ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
00170 
00171 /* Overflow management */
00172 /*
00173  * Overflow page numbers are allocated per split point.  At each doubling of
00174  * the table, we can allocate extra pages.  So, an overflow page number has
00175  * the top 5 bits indicate which split point and the lower 11 bits indicate
00176  * which page at that split point is indicated (pages within split points are
00177  * numberered starting with 1).
00178  */
00179 
00180 #define SPLITSHIFT   11
00181 #define SPLITMASK    0x7FF
00182 #define SPLITNUM(N)  (((uint32)(N)) >> SPLITSHIFT)
00183 #define OPAGENUM(N)  ((N) & SPLITMASK)
00184 #define       OADDR_OF(S,O) ((uint32)((uint32)(S) << SPLITSHIFT) + (O))
00185 
00186 #define BUCKET_TO_PAGE(B) \
00187        (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((uint32)((B)+1))-1] : 0)
00188 #define OADDR_TO_PAGE(B)    \
00189        BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
00190 
00191 /*
00192  * page.h contains a detailed description of the page format.
00193  *
00194  * Normally, keys and data are accessed from offset tables in the top of
00195  * each page which point to the beginning of the key and data.  There are
00196  * four flag values which may be stored in these offset tables which indicate
00197  * the following:
00198  *
00199  *
00200  * OVFLPAGE   Rather than a key data pair, this pair contains
00201  *            the address of an overflow page.  The format of
00202  *            the pair is:
00203  *                OVERFLOW_PAGE_NUMBER OVFLPAGE
00204  *
00205  * PARTIAL_KEY       This must be the first key/data pair on a page
00206  *            and implies that page contains only a partial key.
00207  *            That is, the key is too big to fit on a single page
00208  *            so it starts on this page and continues on the next.
00209  *            The format of the page is:
00210  *                KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
00211  *            
00212  *                KEY_OFF -- offset of the beginning of the key
00213  *                PARTIAL_KEY -- 1
00214  *                OVFL_PAGENO - page number of the next overflow page
00215  *                OVFLPAGE -- 0
00216  *
00217  * FULL_KEY   This must be the first key/data pair on the page.  It
00218  *            is used in two cases.
00219  *
00220  *            Case 1:
00221  *                There is a complete key on the page but no data
00222  *                (because it wouldn't fit).  The next page contains
00223  *                the data.
00224  *
00225  *                Page format it:
00226  *                KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
00227  *
00228  *                KEY_OFF -- offset of the beginning of the key
00229  *                FULL_KEY -- 2
00230  *                OVFL_PAGENO - page number of the next overflow page
00231  *                OVFLPAGE -- 0
00232  *
00233  *            Case 2:
00234  *                This page contains no key, but part of a large
00235  *                data field, which is continued on the next page.
00236  *
00237  *                Page format it:
00238  *                DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
00239  *
00240  *                KEY_OFF -- offset of the beginning of the data on
00241  *                          this page
00242  *                FULL_KEY -- 2
00243  *                OVFL_PAGENO - page number of the next overflow page
00244  *                OVFLPAGE -- 0
00245  *
00246  * FULL_KEY_DATA 
00247  *            This must be the first key/data pair on the page.
00248  *            There are two cases:
00249  *
00250  *            Case 1:
00251  *                This page contains a key and the beginning of the
00252  *                data field, but the data field is continued on the
00253  *                next page.
00254  *
00255  *                Page format is:
00256  *                KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
00257  *
00258  *                KEY_OFF -- offset of the beginning of the key
00259  *                FULL_KEY_DATA -- 3
00260  *                OVFL_PAGENO - page number of the next overflow page
00261  *                DATA_OFF -- offset of the beginning of the data
00262  *
00263  *            Case 2:
00264  *                This page contains the last page of a big data pair.
00265  *                There is no key, only the  tail end of the data
00266  *                on this page.
00267  *
00268  *                Page format is:
00269  *                DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
00270  *
00271  *                DATA_OFF -- offset of the beginning of the data on
00272  *                          this page
00273  *                FULL_KEY_DATA -- 3
00274  *                OVFL_PAGENO - page number of the next overflow page
00275  *                OVFLPAGE -- 0
00276  *
00277  *                OVFL_PAGENO and OVFLPAGE are optional (they are
00278  *                not present if there is no next page).
00279  */
00280 
00281 #define OVFLPAGE     0
00282 #define PARTIAL_KEY  1
00283 #define FULL_KEY     2
00284 #define FULL_KEY_DATA       3
00285 #define       REAL_KEY      4
00286 
00287 /* Short hands for accessing structure */
00288 #undef BSIZE
00289 #define BSIZE        hdr.bsize
00290 #undef BSHIFT
00291 #define BSHIFT              hdr.bshift
00292 #define DSIZE        hdr.dsize
00293 #define SGSIZE              hdr.ssize
00294 #define SSHIFT              hdr.sshift
00295 #define LORDER              hdr.lorder
00296 #define OVFL_POINT   hdr.ovfl_point
00297 #define       LAST_FREED    hdr.last_freed
00298 #define MAX_BUCKET   hdr.max_bucket
00299 #define FFACTOR             hdr.ffactor
00300 #define HIGH_MASK    hdr.high_mask
00301 #define LOW_MASK     hdr.low_mask
00302 #define NKEYS        hdr.nkeys
00303 #define HDRPAGES     hdr.hdrpages
00304 #define SPARES              hdr.spares
00305 #define BITMAPS             hdr.bitmaps
00306 #define VERSION             hdr.version
00307 #define MAGIC        hdr.magic
00308 #define NEXT_FREE    hdr.next_free
00309 #define H_CHARKEY    hdr.h_charkey
00310 
00311 extern uint32 (*__default_hash) (const void *, size_t);
00312 void __buf_init(HTAB *hashp, int32 nbytes);
00313 int __big_delete(HTAB *hashp, BUFHEAD *bufp);
00314 BUFHEAD * __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage);
00315 uint32 __call_hash(HTAB *hashp, char *k, size_t len);
00316 #include "page.h"
00317 extern int __big_split(HTAB *hashp, BUFHEAD *op,BUFHEAD *np,
00318 BUFHEAD *big_keyp,uint32 addr,uint32   obucket, SPLIT_RETURN *ret);
00319 void __free_ovflpage(HTAB *hashp, BUFHEAD *obufp);
00320 BUFHEAD * __add_ovflpage(HTAB *hashp, BUFHEAD *bufp);
00321 int __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val);
00322 int __expand_table(HTAB *hashp);
00323 uint32 __log2(uint32 num);
00324 void __reclaim_buf(HTAB *hashp, BUFHEAD *bp);
00325 int __get_page(HTAB *hashp, char * p, uint32 bucket, int is_bucket, int is_disk, int is_bitmap);
00326 int __put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap);
00327 int __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx);
00328 int __buf_free(HTAB *hashp, int do_free, int to_disk);
00329 int __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size);
00330 uint16 __find_last_page(HTAB *hashp, BUFHEAD **bpp);
00331 int __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT * val);
00332 int __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current);
00333 int __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx);
00334 int __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set);
00335 int __split_page(HTAB *hashp, uint32 obucket, uint32 nbucket);