1 /* 2 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 #ifndef _KRB5_DB2_HASH_H 7 #define _KRB5_DB2_HASH_H 8 9 #ifdef __cplusplus 10 extern "C" { 11 #endif 12 13 /*- 14 * Copyright (c) 1990, 1993, 1994 15 * The Regents of the University of California. All rights reserved. 16 * 17 * This code is derived from software contributed to Berkeley by 18 * Margo Seltzer. 19 * 20 * Redistribution and use in source and binary forms, with or without 21 * modification, are permitted provided that the following conditions 22 * are met: 23 * 1. Redistributions of source code must retain the above copyright 24 * notice, this list of conditions and the following disclaimer. 25 * 2. Redistributions in binary form must reproduce the above copyright 26 * notice, this list of conditions and the following disclaimer in the 27 * documentation and/or other materials provided with the distribution. 28 * 3. All advertising materials mentioning features or use of this software 29 * must display the following acknowledgement: 30 * This product includes software developed by the University of 31 * California, Berkeley and its contributors. 32 * 4. Neither the name of the University nor the names of its contributors 33 * may be used to endorse or promote products derived from this software 34 * without specific prior written permission. 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 37 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 39 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 40 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 41 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 42 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 43 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 44 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 45 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 46 * SUCH DAMAGE. 47 * 48 * @(#)hash.h 8.4 (Berkeley) 11/2/95 49 */ 50 51 #include "mpool.h" 52 #include "db-queue.h" 53 54 /* Operations */ 55 typedef enum { 56 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 57 } ACTION; 58 59 /* cursor structure */ 60 typedef struct cursor_t { 61 TAILQ_ENTRY(cursor_t) queue; 62 int (*get) __P((const DB *, struct cursor_t *, DBT *, DBT *, \ 63 u_int32_t)); 64 int (*delete) __P((const DB *, struct cursor_t *, u_int32_t)); 65 db_pgno_t bucket; 66 db_pgno_t pgno; 67 indx_t ndx; 68 indx_t pgndx; 69 u_int16_t *pagep; 70 void *internal; 71 } CURSOR; 72 73 74 #define IS_BUCKET(X) ((X) & BUF_BUCKET) 75 #define IS_VALID(X) (!((X) & BUF_INVALID)) 76 77 /* Hash Table Information */ 78 typedef struct hashhdr { /* Disk resident portion */ 79 int32_t magic; /* Magic NO for hash tables */ 80 int32_t version; /* Version ID */ 81 int32_t lorder; /* Byte Order */ 82 int32_t bsize; /* Bucket/Page Size */ 83 int32_t bshift; /* Bucket shift */ 84 int32_t ovfl_point; /* Where overflow pages are being allocated */ 85 int32_t last_freed; /* Last overflow page freed */ 86 int32_t max_bucket; /* ID of Maximum bucket in use */ 87 int32_t high_mask; /* Mask to modulo into entire table */ 88 int32_t low_mask; /* Mask to modulo into lower half of table */ 89 int32_t ffactor; /* Fill factor */ 90 int32_t nkeys; /* Number of keys in hash table */ 91 int32_t hdrpages; /* Size of table header */ 92 int32_t h_charkey; /* value of hash(CHARKEY) */ 93 #define NCACHED 32 /* number of bit maps and spare points */ 94 int32_t spares[NCACHED];/* spare pages for overflow */ 95 u_int16_t bitmaps[NCACHED]; /* address of overflow page bitmaps */ 96 } HASHHDR; 97 98 typedef struct htab { /* Memory resident data structure */ 99 TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue; 100 HASHHDR hdr; /* Header */ 101 u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */ 102 int32_t flags; /* Flag values */ 103 int32_t fp; /* File pointer */ 104 const char *fname; /* File path */ 105 u_int8_t *bigdata_buf; /* Temporary Buffer for BIG data */ 106 u_int8_t *bigkey_buf; /* Temporary Buffer for BIG keys */ 107 u_int16_t *split_buf; /* Temporary buffer for splits */ 108 CURSOR *seq_cursor; /* Cursor used for hash_seq */ 109 int32_t local_errno; /* Error Number -- for DBM compatability */ 110 int32_t new_file; /* Indicates if fd is backing store or no */ 111 int32_t save_file; /* Indicates whether we need to flush file at 112 * exit */ 113 u_int32_t *mapp[NCACHED];/* Pointers to page maps */ 114 int32_t nmaps; /* Initial number of bitmaps */ 115 MPOOL *mp; /* mpool for buffer management */ 116 } HTAB; 117 118 /* 119 * Constants 120 */ 121 #define MAX_BSIZE 65536 /* 2^16 */ 122 #define MIN_BUFFERS 6 123 #define MINHDRSIZE 512 124 #define DEF_CACHESIZE 65536 125 #define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ 126 #define DEF_BUCKET_SIZE (1<<DEF_BUCKET_SHIFT) 127 #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 128 #define DEF_SEGSIZE (1<<DEF_SEGSIZE_SHIFT) 129 #define DEF_DIRSIZE 256 130 #define DEF_FFACTOR 65536 131 #define MIN_FFACTOR 4 132 #define SPLTMAX 8 133 #define CHARKEY "%$sniglet^&" 134 #define NUMKEY 1038583 135 #define BYTE_SHIFT 3 136 #define INT32_T_TO_BYTE 2 137 #define INT32_T_BYTE_SHIFT 5 138 #define ALL_SET ((u_int32_t)0xFFFFFFFF) 139 #define ALL_CLEAR 0 140 141 #define PTROF(X) ((BUFHEAD *)((ptr_t)(X)&~0x3)) 142 #define ISMOD(X) ((ptr_t)(X)&0x1) 143 #define DOMOD(X) ((X) = (int8_t *)((ptr_t)(X)|0x1)) 144 #define ISDISK(X) ((ptr_t)(X)&0x2) 145 #define DODISK(X) ((X) = (int8_t *)((ptr_t)(X)|0x2)) 146 147 #define BITS_PER_MAP 32 148 149 /* Given the address of the beginning of a big map, clear/set the nth bit */ 150 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 151 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 152 #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 153 154 /* Overflow management */ 155 /* 156 * Overflow page numbers are allocated per split point. At each doubling of 157 * the table, we can allocate extra pages. So, an overflow page number has 158 * the top 5 bits indicate which split point and the lower 11 bits indicate 159 * which page at that split point is indicated (pages within split points are 160 * numberered starting with 1). 161 */ 162 163 #define SPLITSHIFT 11 164 #define SPLITMASK 0x7FF 165 #define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT) 166 #define OPAGENUM(N) ((N) & SPLITMASK) 167 #define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O)) 168 169 #define BUCKET_TO_PAGE(B) \ 170 ((B) + hashp->hdr.hdrpages + ((B) \ 171 ? hashp->hdr.spares[__log2((B)+1)-1] : 0)) 172 #define OADDR_TO_PAGE(B) \ 173 (BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B))) 174 175 #define POW2(N) (1 << (N)) 176 177 #define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize) 178 179 /* Shorthands for accessing structure */ 180 #define METADATA_PGNO 0 181 #define SPLIT_PGNO 0xFFFF 182 183 typedef struct item_info { 184 db_pgno_t pgno; 185 db_pgno_t bucket; 186 indx_t ndx; 187 indx_t pgndx; 188 u_int8_t status; 189 int32_t seek_size; 190 db_pgno_t seek_found_page; 191 indx_t key_off; 192 indx_t data_off; 193 u_int8_t caused_expand; 194 } ITEM_INFO; 195 196 197 #define ITEM_ERROR 0 198 #define ITEM_OK 1 199 #define ITEM_NO_MORE 2 200 201 #define ITEM_GET_FIRST 0 202 #define ITEM_GET_NEXT 1 203 #define ITEM_GET_RESET 2 204 #define ITEM_GET_DONE 3 205 #define ITEM_GET_N 4 206 207 #define UNKNOWN 0xffffffff /* for num_items */ 208 #define NO_EXPAND 0xfffffffe 209 210 #ifdef __cplusplus 211 } 212 #endif 213 214 #endif /* !_KRB5_DB2_HASH_H */ 215