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.5 (Berkeley) 09/04/91 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 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 if fd is backing store or no */ 74 int save_file; /* Indicates whether we need to flush file at 75 * exit */ 76 u_long *mapp[NCACHED]; /* Pointers to page maps */ 77 int nmaps; /* Initial number of 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 * Constants 85 */ 86 #define MAX_BSIZE 65536 /* 2^16 */ 87 #define MIN_BUFFERS 6 88 #define MINHDRSIZE 512 89 #define DEF_BUFSIZE 65536 /* 64 K */ 90 #define DEF_BUCKET_SIZE 256 91 #define DEF_BUCKET_SHIFT 8 /* log2(BUCKET) */ 92 #define DEF_SEGSIZE 256 93 #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 94 #define DEF_DIRSIZE 256 95 #define DEF_FFACTOR 5 96 #define SPLTMAX 8 97 #define CHARKEY "%$sniglet^&" 98 #define NUMKEY 1038583 99 #define VERSION_NO 3 100 #define BYTE_SHIFT 3 101 #define INT_TO_BYTE 2 102 #define INT_BYTE_SHIFT 5 103 #define ALL_SET ((u_int)0xFFFFFFFF) 104 #define ALL_CLEAR 0 105 106 #define PTROF(X) ((BUFHEAD *)((u_int)(X)&~0x3)) 107 #define ISMOD(X) ((u_int)(X)&0x1) 108 #define DOMOD(X) ((X) = (char *)((u_int)(X)|0x1)) 109 #define ISDISK(X) ((u_int)(X)&0x2) 110 #define DODISK(X) ((X) = (char *)((u_int)(X)|0x2)) 111 112 #define BITS_PER_MAP 32 113 114 /* Given the address of the beginning of a big map, clear/set the nth bit */ 115 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 116 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 117 #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 118 119 /* Overflow management */ 120 /* 121 * Overflow page numbers are allocated per split point. At each doubling of 122 * the table, we can allocate extra pages. So, an overflow page number has 123 * the top 5 bits indicate which split point and the lower 11 bits indicate 124 * which page at that split point is indicated (pages within split points are 125 * numberered starting with 1). 126 */ 127 128 #define SPLITSHIFT 11 129 #define SPLITMASK 0x7FF 130 #define SPLITNUM(N) (((u_int)(N)) >> SPLITSHIFT) 131 #define OPAGENUM(N) ((N) & SPLITMASK) 132 #define OADDR_OF(S,O) ((u_int)((u_int)(S) << SPLITSHIFT) + (O)) 133 134 #define BUCKET_TO_PAGE(B) \ 135 (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0) 136 #define OADDR_TO_PAGE(B) \ 137 BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); 138 139 /* 140 * page.h contains a detailed description of the page format. 141 * 142 * Normally, keys and data are accessed from offset tables in the top of 143 * each page which point to the beginning of the key and data. There are 144 * four flag values which may be stored in these offset tables which indicate 145 * the following: 146 * 147 * 148 * OVFLPAGE Rather than a key data pair, this pair contains 149 * the address of an overflow page. The format of 150 * the pair is: 151 * OVERFLOW_PAGE_NUMBER OVFLPAGE 152 * 153 * PARTIAL_KEY This must be the first key/data pair on a page 154 * and implies that page contains only a partial key. 155 * That is, the key is too big to fit on a single page 156 * so it starts on this page and continues on the next. 157 * The format of the page is: 158 * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE 159 * 160 * KEY_OFF -- offset of the beginning of the key 161 * PARTIAL_KEY -- 1 162 * OVFL_PAGENO - page number of the next overflow page 163 * OVFLPAGE -- 0 164 * 165 * FULL_KEY This must be the first key/data pair on the page. It 166 * is used in two cases. 167 * 168 * Case 1: 169 * There is a complete key on the page but no data 170 * (because it wouldn't fit). The next page contains 171 * the data. 172 * 173 * Page format it: 174 * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 175 * 176 * KEY_OFF -- offset of the beginning of the key 177 * FULL_KEY -- 2 178 * OVFL_PAGENO - page number of the next overflow page 179 * OVFLPAGE -- 0 180 * 181 * Case 2: 182 * This page contains no key, but part of a large 183 * data field, which is continued on the next page. 184 * 185 * Page format it: 186 * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 187 * 188 * KEY_OFF -- offset of the beginning of the data on 189 * this page 190 * FULL_KEY -- 2 191 * OVFL_PAGENO - page number of the next overflow page 192 * OVFLPAGE -- 0 193 * 194 * FULL_KEY_DATA 195 * This must be the first key/data pair on the page. 196 * There are two cases: 197 * 198 * Case 1: 199 * This page contains a key and the beginning of the 200 * data field, but the data field is continued on the 201 * next page. 202 * 203 * Page format is: 204 * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF 205 * 206 * KEY_OFF -- offset of the beginning of the key 207 * FULL_KEY_DATA -- 3 208 * OVFL_PAGENO - page number of the next overflow page 209 * DATA_OFF -- offset of the beginning of the data 210 * 211 * Case 2: 212 * This page contains the last page of a big data pair. 213 * There is no key, only the tail end of the data 214 * on this page. 215 * 216 * Page format is: 217 * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> 218 * 219 * DATA_OFF -- offset of the beginning of the data on 220 * this page 221 * FULL_KEY_DATA -- 3 222 * OVFL_PAGENO - page number of the next overflow page 223 * OVFLPAGE -- 0 224 * 225 * OVFL_PAGENO and OVFLPAGE are optional (they are 226 * not present if there is no next page). 227 */ 228 229 #define OVFLPAGE 0 230 #define PARTIAL_KEY 1 231 #define FULL_KEY 2 232 #define FULL_KEY_DATA 3 233 #define REAL_KEY 4 234 235 /* Short hands for accessing structure */ 236 #define BSIZE hdr.bsize 237 #define BSHIFT hdr.bshift 238 #define DSIZE hdr.dsize 239 #define SGSIZE hdr.ssize 240 #define SSHIFT hdr.sshift 241 #define LORDER hdr.lorder 242 #define MAX_BUCKET hdr.max_bucket 243 #define FFACTOR hdr.ffactor 244 #define HIGH_MASK hdr.high_mask 245 #define LOW_MASK hdr.low_mask 246 #define NKEYS hdr.nkeys 247 #define HDRPAGES hdr.hdrpages 248 #define SPARES hdr.spares 249 #define BITMAPS hdr.bitmaps 250 #define VERSION hdr.version 251 #define MAGIC hdr.magic 252 #define NEXT_FREE hdr.next_free 253 #define H_CHARKEY hdr.h_charkey 254