1 /*- 2 * Copyright (c) 1990, 1993 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 * %sccs.include.redist.c% 9 * 10 * @(#)hash.h 8.2 (Berkeley) 02/21/94 11 */ 12 13 /* Operations */ 14 typedef enum { 15 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 16 } ACTION; 17 18 /* Buffer Management structures */ 19 typedef struct _bufhead BUFHEAD; 20 21 struct _bufhead { 22 BUFHEAD *prev; /* LRU links */ 23 BUFHEAD *next; /* LRU links */ 24 BUFHEAD *ovfl; /* Overflow page buffer header */ 25 u_int addr; /* Address of this page */ 26 char *page; /* Actual page data */ 27 char flags; 28 #define BUF_MOD 0x0001 29 #define BUF_DISK 0x0002 30 #define BUF_BUCKET 0x0004 31 #define BUF_PIN 0x0008 32 }; 33 34 #define IS_BUCKET(X) ((X) & BUF_BUCKET) 35 36 typedef BUFHEAD **SEGMENT; 37 38 /* Hash Table Information */ 39 typedef struct hashhdr { /* Disk resident portion */ 40 int magic; /* Magic NO for hash tables */ 41 int version; /* Version ID */ 42 long lorder; /* Byte Order */ 43 int bsize; /* Bucket/Page Size */ 44 int bshift; /* Bucket shift */ 45 int dsize; /* Directory Size */ 46 int ssize; /* Segment Size */ 47 int sshift; /* Segment shift */ 48 int ovfl_point; /* Where overflow pages are being allocated */ 49 int last_freed; /* Last overflow page freed */ 50 int max_bucket; /* ID of Maximum bucket in use */ 51 int high_mask; /* Mask to modulo into entire table */ 52 int low_mask; /* Mask to modulo into lower half of table */ 53 int ffactor; /* Fill factor */ 54 int nkeys; /* Number of keys in hash table */ 55 int hdrpages; /* Size of table header */ 56 int h_charkey; /* value of hash(CHARKEY) */ 57 #define NCACHED 32 /* number of bit maps and spare points */ 58 int spares[NCACHED];/* spare pages for overflow */ 59 u_short bitmaps[NCACHED]; /* address of overflow page bitmaps */ 60 } HASHHDR; 61 62 typedef struct htab { /* Memory resident data structure */ 63 HASHHDR hdr; /* Header */ 64 int nsegs; /* Number of allocated segments */ 65 int exsegs; /* Number of extra allocated segments */ 66 u_int32_t /* Hash function */ 67 (*hash)__P((const void *, size_t)); 68 int flags; /* Flag values */ 69 int fp; /* File pointer */ 70 char *tmp_buf; /* Temporary Buffer for BIG data */ 71 char *tmp_key; /* Temporary Buffer for BIG keys */ 72 BUFHEAD *cpage; /* Current page */ 73 int cbucket; /* Current bucket */ 74 int cndx; /* Index of next item on cpage */ 75 int errno; /* Error Number -- for DBM compatability */ 76 int new_file; /* Indicates if fd is backing store or no */ 77 int save_file; /* Indicates whether we need to flush file at 78 * exit */ 79 u_long *mapp[NCACHED]; /* Pointers to page maps */ 80 int nmaps; /* Initial number of bitmaps */ 81 int nbufs; /* Number of buffers left to allocate */ 82 BUFHEAD bufhead; /* Header of buffer lru list */ 83 SEGMENT *dir; /* Hash Bucket directory */ 84 } HTAB; 85 86 /* 87 * Constants 88 */ 89 #define MAX_BSIZE 65536 /* 2^16 */ 90 #define MIN_BUFFERS 6 91 #define MINHDRSIZE 512 92 #define DEF_BUFSIZE 65536 /* 64 K */ 93 #define DEF_BUCKET_SIZE 4096 94 #define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ 95 #define DEF_SEGSIZE 256 96 #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 97 #define DEF_DIRSIZE 256 98 #define DEF_FFACTOR 65536 99 #define MIN_FFACTOR 4 100 #define SPLTMAX 8 101 #define CHARKEY "%$sniglet^&" 102 #define NUMKEY 1038583 103 #define BYTE_SHIFT 3 104 #define INT_TO_BYTE 2 105 #define INT_BYTE_SHIFT 5 106 #define ALL_SET ((u_int)0xFFFFFFFF) 107 #define ALL_CLEAR 0 108 109 #define PTROF(X) ((BUFHEAD *)((u_int)(X)&~0x3)) 110 #define ISMOD(X) ((u_int)(X)&0x1) 111 #define DOMOD(X) ((X) = (char *)((u_int)(X)|0x1)) 112 #define ISDISK(X) ((u_int)(X)&0x2) 113 #define DODISK(X) ((X) = (char *)((u_int)(X)|0x2)) 114 115 #define BITS_PER_MAP 32 116 117 /* Given the address of the beginning of a big map, clear/set the nth bit */ 118 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 119 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 120 #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 121 122 /* Overflow management */ 123 /* 124 * Overflow page numbers are allocated per split point. At each doubling of 125 * the table, we can allocate extra pages. So, an overflow page number has 126 * the top 5 bits indicate which split point and the lower 11 bits indicate 127 * which page at that split point is indicated (pages within split points are 128 * numberered starting with 1). 129 */ 130 131 #define SPLITSHIFT 11 132 #define SPLITMASK 0x7FF 133 #define SPLITNUM(N) (((u_int)(N)) >> SPLITSHIFT) 134 #define OPAGENUM(N) ((N) & SPLITMASK) 135 #define OADDR_OF(S,O) ((u_int)((u_int)(S) << SPLITSHIFT) + (O)) 136 137 #define BUCKET_TO_PAGE(B) \ 138 (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0) 139 #define OADDR_TO_PAGE(B) \ 140 BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); 141 142 /* 143 * page.h contains a detailed description of the page format. 144 * 145 * Normally, keys and data are accessed from offset tables in the top of 146 * each page which point to the beginning of the key and data. There are 147 * four flag values which may be stored in these offset tables which indicate 148 * the following: 149 * 150 * 151 * OVFLPAGE Rather than a key data pair, this pair contains 152 * the address of an overflow page. The format of 153 * the pair is: 154 * OVERFLOW_PAGE_NUMBER OVFLPAGE 155 * 156 * PARTIAL_KEY This must be the first key/data pair on a page 157 * and implies that page contains only a partial key. 158 * That is, the key is too big to fit on a single page 159 * so it starts on this page and continues on the next. 160 * The format of the page is: 161 * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE 162 * 163 * KEY_OFF -- offset of the beginning of the key 164 * PARTIAL_KEY -- 1 165 * OVFL_PAGENO - page number of the next overflow page 166 * OVFLPAGE -- 0 167 * 168 * FULL_KEY This must be the first key/data pair on the page. It 169 * is used in two cases. 170 * 171 * Case 1: 172 * There is a complete key on the page but no data 173 * (because it wouldn't fit). The next page contains 174 * the data. 175 * 176 * Page format it: 177 * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 178 * 179 * KEY_OFF -- offset of the beginning of the key 180 * FULL_KEY -- 2 181 * OVFL_PAGENO - page number of the next overflow page 182 * OVFLPAGE -- 0 183 * 184 * Case 2: 185 * This page contains no key, but part of a large 186 * data field, which is continued on the next page. 187 * 188 * Page format it: 189 * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 190 * 191 * KEY_OFF -- offset of the beginning of the data on 192 * this page 193 * FULL_KEY -- 2 194 * OVFL_PAGENO - page number of the next overflow page 195 * OVFLPAGE -- 0 196 * 197 * FULL_KEY_DATA 198 * This must be the first key/data pair on the page. 199 * There are two cases: 200 * 201 * Case 1: 202 * This page contains a key and the beginning of the 203 * data field, but the data field is continued on the 204 * next page. 205 * 206 * Page format is: 207 * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF 208 * 209 * KEY_OFF -- offset of the beginning of the key 210 * FULL_KEY_DATA -- 3 211 * OVFL_PAGENO - page number of the next overflow page 212 * DATA_OFF -- offset of the beginning of the data 213 * 214 * Case 2: 215 * This page contains the last page of a big data pair. 216 * There is no key, only the tail end of the data 217 * on this page. 218 * 219 * Page format is: 220 * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> 221 * 222 * DATA_OFF -- offset of the beginning of the data on 223 * this page 224 * FULL_KEY_DATA -- 3 225 * OVFL_PAGENO - page number of the next overflow page 226 * OVFLPAGE -- 0 227 * 228 * OVFL_PAGENO and OVFLPAGE are optional (they are 229 * not present if there is no next page). 230 */ 231 232 #define OVFLPAGE 0 233 #define PARTIAL_KEY 1 234 #define FULL_KEY 2 235 #define FULL_KEY_DATA 3 236 #define REAL_KEY 4 237 238 /* Short hands for accessing structure */ 239 #define BSIZE hdr.bsize 240 #define BSHIFT hdr.bshift 241 #define DSIZE hdr.dsize 242 #define SGSIZE hdr.ssize 243 #define SSHIFT hdr.sshift 244 #define LORDER hdr.lorder 245 #define OVFL_POINT hdr.ovfl_point 246 #define LAST_FREED hdr.last_freed 247 #define MAX_BUCKET hdr.max_bucket 248 #define FFACTOR hdr.ffactor 249 #define HIGH_MASK hdr.high_mask 250 #define LOW_MASK hdr.low_mask 251 #define NKEYS hdr.nkeys 252 #define HDRPAGES hdr.hdrpages 253 #define SPARES hdr.spares 254 #define BITMAPS hdr.bitmaps 255 #define VERSION hdr.version 256 #define MAGIC hdr.magic 257 #define NEXT_FREE hdr.next_free 258 #define H_CHARKEY hdr.h_charkey 259