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