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