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