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