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 12extern "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 */ 57typedef enum { 58 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 59} ACTION; 60 61/* cursor structure */ 62typedef 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 */ 80typedef 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 100typedef 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 185typedef 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