home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / dbm / include / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  12.1 KB  |  335 lines
  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. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  *
  36.  *    @(#)hash.h    8.3 (Berkeley) 5/31/94
  37.  */
  38.  
  39. /* Operations */
  40.  
  41. #include <stdio.h>
  42. #include "mcom_db.h"
  43. typedef enum {
  44.     HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
  45. } ACTION;
  46.  
  47. /* Buffer Management structures */
  48. typedef struct _bufhead BUFHEAD;
  49.  
  50. struct _bufhead {
  51.     BUFHEAD        *prev;        /* LRU links */
  52.     BUFHEAD        *next;        /* LRU links */
  53.     BUFHEAD        *ovfl;        /* Overflow page buffer header */
  54.     uint32     addr;        /* Address of this page */
  55.     char        *page;        /* Actual page data */
  56.     char        is_disk;
  57.     char         flags;
  58. #define    BUF_MOD        0x0001
  59. #define BUF_DISK    0x0002
  60. #define    BUF_BUCKET    0x0004
  61. #define    BUF_PIN        0x0008
  62. };
  63.  
  64. #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
  65.  
  66. typedef BUFHEAD **SEGMENT;
  67.  
  68. typedef int DBFILE_PTR;
  69. #define NO_FILE -1
  70. #ifdef macintosh
  71. #define DBFILE_OPEN(path, flag,mode) open((path), flag)
  72. #define EXISTS(path)
  73. #else
  74. #define DBFILE_OPEN(path, flag,mode) open((path), (flag), (mode))
  75. #endif
  76. /* Hash Table Information */
  77. typedef struct hashhdr {        /* Disk resident portion */
  78.     int32        magic;        /* Magic NO for hash tables */
  79.     int32        version;    /* Version ID */
  80.     uint32    lorder;        /* Byte Order */
  81.     int32        bsize;        /* Bucket/Page Size */
  82.     int32        bshift;        /* Bucket shift */
  83.     int32        dsize;        /* Directory Size */
  84.     int32        ssize;        /* Segment Size */
  85.     int32        sshift;        /* Segment shift */
  86.     int32        ovfl_point;    /* Where overflow pages are being 
  87.                      * allocated */
  88.     int32        last_freed;    /* Last overflow page freed */
  89.     int32        max_bucket;    /* ID of Maximum bucket in use */
  90.     int32        high_mask;    /* Mask to modulo into entire table */
  91.     int32        low_mask;    /* Mask to modulo into lower half of 
  92.                      * table */
  93.     int32        ffactor;    /* Fill factor */
  94.     int32        nkeys;        /* Number of keys in hash table */
  95.     int32        hdrpages;    /* Size of table header */
  96.     int32        h_charkey;    /* value of hash(CHARKEY) */
  97. #define NCACHED    32            /* number of bit maps and spare 
  98.                      * points */
  99.     int32        spares[NCACHED];/* spare pages for overflow */
  100.     uint16    bitmaps[NCACHED];    /* address of overflow page 
  101.                          * bitmaps */
  102. } HASHHDR;
  103.  
  104. typedef struct htab     {        /* Memory resident data structure */
  105.     HASHHDR     hdr;        /* Header */
  106.     int        nsegs;        /* Number of allocated segments */
  107.     int        exsegs;        /* Number of extra allocated 
  108.                      * segments */
  109.     uint32            /* Hash function */
  110.         (*hash)(const void *, size_t);
  111.     int        flags;        /* Flag values */
  112.     DBFILE_PTR    fp;        /* File pointer */
  113.     char            *filename;
  114.     char        *tmp_buf;    /* Temporary Buffer for BIG data */
  115.     char        *tmp_key;    /* Temporary Buffer for BIG keys */
  116.     BUFHEAD     *cpage;        /* Current page */
  117.     int        cbucket;    /* Current bucket */
  118.     int        cndx;        /* Index of next item on cpage */
  119.     int        dbmerrno;        /* Error Number -- for DBM 
  120.                      * compatability */
  121.     int        new_file;    /* Indicates if fd is backing store 
  122.                      * or no */
  123.     int        save_file;    /* Indicates whether we need to flush 
  124.                      * file at
  125.                      * exit */
  126.     uint32    *mapp[NCACHED];    /* Pointers to page maps */
  127.     int        nmaps;        /* Initial number of bitmaps */
  128.     int        nbufs;        /* Number of buffers left to 
  129.                      * allocate */
  130.     BUFHEAD     bufhead;    /* Header of buffer lru list */
  131.     SEGMENT     *dir;        /* Hash Bucket directory */
  132. } HTAB;
  133.  
  134. /*
  135.  * Constants
  136.  */
  137. #define DATABASE_CORRUPTED_ERROR -999   /* big ugly abort, delete database */
  138. #define    OLD_MAX_BSIZE        65536        /* 2^16 */
  139. #define MAX_BSIZE           32l*1024l         /* 2^15 */
  140. #define MIN_BUFFERS        6
  141. #define MINHDRSIZE        512
  142. #define DEF_BUFSIZE        65536l        /* 64 K */
  143. #define DEF_BUCKET_SIZE        4096
  144. #define DEF_BUCKET_SHIFT    12        /* log2(BUCKET) */
  145. #define DEF_SEGSIZE        256
  146. #define DEF_SEGSIZE_SHIFT    8        /* log2(SEGSIZE)     */
  147. #define DEF_DIRSIZE        256
  148. #define DEF_FFACTOR        65536l
  149. #define MIN_FFACTOR        4
  150. #define SPLTMAX            8
  151. #define CHARKEY            "%$sniglet^&"
  152. #define NUMKEY            1038583l
  153. #define BYTE_SHIFT        3
  154. #define INT_TO_BYTE        2
  155. #define INT_BYTE_SHIFT        5
  156. #define ALL_SET            ((uint32)0xFFFFFFFF)
  157. #define ALL_CLEAR        0
  158.  
  159. #define PTROF(X)    ((ptrdiff_t)(X) == BUF_DISK ? 0 : (X))
  160. #define ISDISK(X)    ((X) ? ((ptrdiff_t)(X) == BUF_DISK ? BUF_DISK \
  161.                 : (X)->is_disk) : 0)
  162.  
  163. #define BITS_PER_MAP    32
  164.  
  165. /* Given the address of the beginning of a big map, clear/set the nth bit */
  166. #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
  167. #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
  168. #define ISSET(A, N)    ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
  169.  
  170. /* Overflow management */
  171. /*
  172.  * Overflow page numbers are allocated per split point.  At each doubling of
  173.  * the table, we can allocate extra pages.  So, an overflow page number has
  174.  * the top 5 bits indicate which split point and the lower 11 bits indicate
  175.  * which page at that split point is indicated (pages within split points are
  176.  * numberered starting with 1).
  177.  */
  178.  
  179. #define SPLITSHIFT    11
  180. #define SPLITMASK    0x7FF
  181. #define SPLITNUM(N)    (((uint32)(N)) >> SPLITSHIFT)
  182. #define OPAGENUM(N)    ((N) & SPLITMASK)
  183. #define    OADDR_OF(S,O)    ((uint32)((uint32)(S) << SPLITSHIFT) + (O))
  184.  
  185. #define BUCKET_TO_PAGE(B) \
  186.     (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
  187. #define OADDR_TO_PAGE(B)     \
  188.     BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
  189.  
  190. /*
  191.  * page.h contains a detailed description of the page format.
  192.  *
  193.  * Normally, keys and data are accessed from offset tables in the top of
  194.  * each page which point to the beginning of the key and data.  There are
  195.  * four flag values which may be stored in these offset tables which indicate
  196.  * the following:
  197.  *
  198.  *
  199.  * OVFLPAGE    Rather than a key data pair, this pair contains
  200.  *        the address of an overflow page.  The format of
  201.  *        the pair is:
  202.  *            OVERFLOW_PAGE_NUMBER OVFLPAGE
  203.  *
  204.  * PARTIAL_KEY    This must be the first key/data pair on a page
  205.  *        and implies that page contains only a partial key.
  206.  *        That is, the key is too big to fit on a single page
  207.  *        so it starts on this page and continues on the next.
  208.  *        The format of the page is:
  209.  *            KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  210.  *        
  211.  *            KEY_OFF -- offset of the beginning of the key
  212.  *            PARTIAL_KEY -- 1
  213.  *            OVFL_PAGENO - page number of the next overflow page
  214.  *            OVFLPAGE -- 0
  215.  *
  216.  * FULL_KEY    This must be the first key/data pair on the page.  It
  217.  *        is used in two cases.
  218.  *
  219.  *        Case 1:
  220.  *            There is a complete key on the page but no data
  221.  *            (because it wouldn't fit).  The next page contains
  222.  *            the data.
  223.  *
  224.  *            Page format it:
  225.  *            KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  226.  *
  227.  *            KEY_OFF -- offset of the beginning of the key
  228.  *            FULL_KEY -- 2
  229.  *            OVFL_PAGENO - page number of the next overflow page
  230.  *            OVFLPAGE -- 0
  231.  *
  232.  *        Case 2:
  233.  *            This page contains no key, but part of a large
  234.  *            data field, which is continued on the next page.
  235.  *
  236.  *            Page format it:
  237.  *            DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  238.  *
  239.  *            KEY_OFF -- offset of the beginning of the data on
  240.  *                this page
  241.  *            FULL_KEY -- 2
  242.  *            OVFL_PAGENO - page number of the next overflow page
  243.  *            OVFLPAGE -- 0
  244.  *
  245.  * FULL_KEY_DATA 
  246.  *        This must be the first key/data pair on the page.
  247.  *        There are two cases:
  248.  *
  249.  *        Case 1:
  250.  *            This page contains a key and the beginning of the
  251.  *            data field, but the data field is continued on the
  252.  *            next page.
  253.  *
  254.  *            Page format is:
  255.  *            KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  256.  *
  257.  *            KEY_OFF -- offset of the beginning of the key
  258.  *            FULL_KEY_DATA -- 3
  259.  *            OVFL_PAGENO - page number of the next overflow page
  260.  *            DATA_OFF -- offset of the beginning of the data
  261.  *
  262.  *        Case 2:
  263.  *            This page contains the last page of a big data pair.
  264.  *            There is no key, only the  tail end of the data
  265.  *            on this page.
  266.  *
  267.  *            Page format is:
  268.  *            DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  269.  *
  270.  *            DATA_OFF -- offset of the beginning of the data on
  271.  *                this page
  272.  *            FULL_KEY_DATA -- 3
  273.  *            OVFL_PAGENO - page number of the next overflow page
  274.  *            OVFLPAGE -- 0
  275.  *
  276.  *            OVFL_PAGENO and OVFLPAGE are optional (they are
  277.  *            not present if there is no next page).
  278.  */
  279.  
  280. #define OVFLPAGE    0
  281. #define PARTIAL_KEY    1
  282. #define FULL_KEY    2
  283. #define FULL_KEY_DATA    3
  284. #define    REAL_KEY    4
  285.  
  286. /* Short hands for accessing structure */
  287. #undef BSIZE
  288. #define BSIZE        hdr.bsize
  289. #undef BSHIFT
  290. #define BSHIFT        hdr.bshift
  291. #define DSIZE        hdr.dsize
  292. #define SGSIZE        hdr.ssize
  293. #define SSHIFT        hdr.sshift
  294. #define LORDER        hdr.lorder
  295. #define OVFL_POINT    hdr.ovfl_point
  296. #define    LAST_FREED    hdr.last_freed
  297. #define MAX_BUCKET    hdr.max_bucket
  298. #define FFACTOR        hdr.ffactor
  299. #define HIGH_MASK    hdr.high_mask
  300. #define LOW_MASK    hdr.low_mask
  301. #define NKEYS        hdr.nkeys
  302. #define HDRPAGES    hdr.hdrpages
  303. #define SPARES        hdr.spares
  304. #define BITMAPS        hdr.bitmaps
  305. #define VERSION        hdr.version
  306. #define MAGIC        hdr.magic
  307. #define NEXT_FREE    hdr.next_free
  308. #define H_CHARKEY    hdr.h_charkey
  309.  
  310. extern uint32 (*__default_hash) (const void *, size_t);
  311. void __buf_init(HTAB *hashp, int32 nbytes);
  312. int __big_delete(HTAB *hashp, BUFHEAD *bufp);
  313. BUFHEAD * __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage);
  314. uint32 __call_hash(HTAB *hashp, char *k, int len);
  315. #include "page.h"
  316. extern int __big_split(HTAB *hashp, BUFHEAD *op,BUFHEAD *np,
  317. BUFHEAD *big_keyp,int addr,uint32   obucket, SPLIT_RETURN *ret);
  318. void __free_ovflpage(HTAB *hashp, BUFHEAD *obufp);
  319. BUFHEAD * __add_ovflpage(HTAB *hashp, BUFHEAD *bufp);
  320. int __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val);
  321. int __expand_table(HTAB *hashp);
  322. uint32 __log2(uint32 num);
  323. void __reclaim_buf(HTAB *hashp, BUFHEAD *bp);
  324. int __get_page(HTAB *hashp, char * p, uint32 bucket, int is_bucket, int is_disk, int is_bitmap);
  325. int __put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap);
  326. int __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx);
  327. int __buf_free(HTAB *hashp, int do_free, int to_disk);
  328. int __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size);
  329. uint16 __find_last_page(HTAB *hashp, BUFHEAD **bpp);
  330. int __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT * val);
  331. int __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current);
  332. int __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx);
  333. int __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set);
  334. int __split_page(HTAB *hashp, uint32 obucket, uint32 nbucket);
  335.