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.4 (Berkeley) 11/2/95 37 */ 38 39 #include "mpool.h" 40 #include "db-queue.h" 41 42 /* Operations */ 43 typedef enum { 44 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 45 } ACTION; 46 47 /* cursor structure */ 48 typedef struct cursor_t { 49 TAILQ_ENTRY(cursor_t) queue; 50 int (*get) __P((const DB *, struct cursor_t *, DBT *, DBT *, \ 51 u_int32_t)); 52 int (*delete) __P((const DB *, struct cursor_t *, u_int32_t)); 53 db_pgno_t bucket; 54 db_pgno_t pgno; 55 indx_t ndx; 56 indx_t pgndx; 57 u_int16_t *pagep; 58 void *internal; 59 } CURSOR; 60 61 62 #define IS_BUCKET(X) ((X) & BUF_BUCKET) 63 #define IS_VALID(X) (!((X) & BUF_INVALID)) 64 65 /* Hash Table Information */ 66 typedef struct hashhdr { /* Disk resident portion */ 67 int32_t magic; /* Magic NO for hash tables */ 68 int32_t version; /* Version ID */ 69 int32_t lorder; /* Byte Order */ 70 u_int32_t bsize; /* Bucket/Page Size */ 71 int32_t bshift; /* Bucket shift */ 72 int32_t ovfl_point; /* Where overflow pages are being allocated */ 73 u_int32_t last_freed; /* Last overflow page freed */ 74 u_int32_t max_bucket; /* ID of Maximum bucket in use */ 75 u_int32_t high_mask; /* Mask to modulo into entire table */ 76 u_int32_t low_mask; /* Mask to modulo into lower half of table */ 77 u_int32_t ffactor; /* Fill factor */ 78 int32_t nkeys; /* Number of keys in hash table */ 79 u_int32_t hdrpages; /* Size of table header */ 80 u_int32_t h_charkey; /* value of hash(CHARKEY) */ 81 #define NCACHED 32 /* number of bit maps and spare points */ 82 u_int32_t spares[NCACHED];/* spare pages for overflow */ 83 u_int16_t bitmaps[NCACHED]; /* address of overflow page bitmaps */ 84 } HASHHDR; 85 86 typedef struct htab { /* Memory resident data structure */ 87 TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue; 88 HASHHDR hdr; /* Header */ 89 u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */ 90 int32_t flags; /* Flag values */ 91 int32_t fp; /* File pointer */ 92 const char *fname; /* File path */ 93 u_int8_t *bigdata_buf; /* Temporary Buffer for BIG data */ 94 u_int8_t *bigkey_buf; /* Temporary Buffer for BIG keys */ 95 u_int16_t *split_buf; /* Temporary buffer for splits */ 96 CURSOR *seq_cursor; /* Cursor used for hash_seq */ 97 int32_t local_errno; /* Error Number -- for DBM compatibility */ 98 int32_t new_file; /* Indicates if fd is backing store or no */ 99 int32_t save_file; /* Indicates whether we need to flush file at 100 * exit */ 101 u_int32_t *mapp[NCACHED];/* Pointers to page maps */ 102 int32_t nmaps; /* Initial number of bitmaps */ 103 MPOOL *mp; /* mpool for buffer management */ 104 } HTAB; 105 106 /* 107 * Constants 108 */ 109 #define MAX_BSIZE 65536 /* 2^16 */ 110 #define MIN_BUFFERS 6 111 #define MINHDRSIZE 512 112 #define DEF_CACHESIZE 65536 113 #define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ 114 #define DEF_BUCKET_SIZE (1<<DEF_BUCKET_SHIFT) 115 #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 116 #define DEF_SEGSIZE (1<<DEF_SEGSIZE_SHIFT) 117 #define DEF_DIRSIZE 256 118 #define DEF_FFACTOR 65536 119 #define MIN_FFACTOR 4 120 #define SPLTMAX 8 121 #define CHARKEY "%$sniglet^&" 122 #define NUMKEY 1038583 123 #define BYTE_SHIFT 3 124 #define INT32_T_TO_BYTE 2 125 #define INT32_T_BYTE_SHIFT 5 126 #define ALL_SET ((u_int32_t)0xFFFFFFFF) 127 #define ALL_CLEAR 0 128 129 #define PTROF(X) ((BUFHEAD *)((ptr_t)(X)&~0x3)) 130 #define ISMOD(X) ((ptr_t)(X)&0x1) 131 #define DOMOD(X) ((X) = (int8_t *)((ptr_t)(X)|0x1)) 132 #define ISDISK(X) ((ptr_t)(X)&0x2) 133 #define DODISK(X) ((X) = (int8_t *)((ptr_t)(X)|0x2)) 134 135 #define BITS_PER_MAP 32 136 137 /* Given the address of the beginning of a big map, clear/set the nth bit */ 138 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 139 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 140 #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 141 142 /* Overflow management */ 143 /* 144 * Overflow page numbers are allocated per split point. At each doubling of 145 * the table, we can allocate extra pages. So, an overflow page number has 146 * the top 5 bits indicate which split point and the lower 11 bits indicate 147 * which page at that split point is indicated (pages within split points are 148 * numberered starting with 1). 149 */ 150 151 #define SPLITSHIFT 11 152 #define SPLITMASK 0x7FF 153 #define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT) 154 #define OPAGENUM(N) ((N) & SPLITMASK) 155 #define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O)) 156 157 #define BUCKET_TO_PAGE(B) \ 158 ((B) + hashp->hdr.hdrpages + ((B) \ 159 ? hashp->hdr.spares[__log2((B)+1)-1] : 0)) 160 #define OADDR_TO_PAGE(B) \ 161 (BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B))) 162 163 #define POW2(N) (1 << (N)) 164 165 #define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize) 166 167 /* Shorthands for accessing structure */ 168 #define METADATA_PGNO 0 169 #define SPLIT_PGNO 0xFFFF 170 171 typedef struct item_info { 172 db_pgno_t pgno; 173 db_pgno_t bucket; 174 indx_t ndx; 175 indx_t pgndx; 176 u_int8_t status; 177 u_int32_t seek_size; 178 db_pgno_t seek_found_page; 179 indx_t key_off; 180 indx_t data_off; 181 u_int8_t caused_expand; 182 } ITEM_INFO; 183 184 185 #define ITEM_ERROR 0 186 #define ITEM_OK 1 187 #define ITEM_NO_MORE 2 188 189 #define ITEM_GET_FIRST 0 190 #define ITEM_GET_NEXT 1 191 #define ITEM_GET_RESET 2 192 #define ITEM_GET_DONE 3 193 #define ITEM_GET_N 4 194 195 #define UNKNOWN 0xffffffff /* for num_items */ 196 #define NO_EXPAND 0xfffffffe 197