1 /*
2  * Copyright (c) 1997-2000 by Sun Microsystems, Inc.
3  * All rights reserved.
4  */
5 
6 #ifndef _KRB5_DB2_PAGE_H
7 #define	_KRB5_DB2_PAGE_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  *	@(#)page.h	8.4 (Berkeley) 11/7/95
49  */
50 
51 #define HI_MASK 0xFFFF0000
52 #define LO_MASK (~HI_MASK)
53 
54 #define HI(N) ((u_int16_t)(((N) & HI_MASK) >> 16))
55 #define LO(N) ((u_int16_t)((N) & LO_MASK))
56 
57 /* Constants for big key page overhead information. */
58 #define NUMSHORTS	0
59 #define KEYLEN		1
60 #define DATALEN 	2
61 #define NEXTPAGE 	3
62 
63 /*
64  * Hash pages store meta-data beginning at the top of the page (offset 0)
65  * and key/data values beginning at the bottom of the page (offset pagesize).
66  * Fields are always accessed via macros so that we can change the page
67  * format without too much pain.  The only changes that will require massive
68  * code changes are if we no longer store key/data offsets next to each
69  * other (since we use that fact to compute key lengths).  In the accessor
70  * macros below, P means a pointer to the page, I means an index of the
71  * particular entry being accessed.
72  *
73  * Hash base page format
74  * BYTE ITEM			NBYTES 	TYPE		ACCESSOR MACRO
75  * ---- ------------------	------	--------	--------------
76  * 0	previous page number 	4	db_pgno_t		PREV_PGNO(P)
77  * 4	next page number	4	db_pgno_t		NEXT_PGNO(P)
78  * 8	# pairs on page		2	indx_t		NUM_ENT(P)
79  * 10	page type		1	u_int8_t	TYPE(P)
80  * 11	padding			1	u_int8_t	none
81  * 12	highest free byte	2	indx_t		OFFSET(P)
82  * 14	key offset 0		2	indx_t		KEY_OFF(P, I)
83  * 16	data offset 0		2	indx_t		DATA_OFF(P, I)
84  * 18	key  offset 1		2	indx_t		KEY_OFF(P, I)
85  * 20	data offset 1		2	indx_t		DATA_OFF(P, I)
86  * ...etc...
87  */
88 
89 /* Indices (in bytes) of the beginning of each of these entries */
90 #define I_PREV_PGNO	 0
91 #define I_NEXT_PGNO	 4
92 #define I_ENTRIES	 8
93 #define I_TYPE		10
94 #define I_HF_OFFSET	12
95 
96 /* Overhead is everything prior to the first key/data pair. */
97 #define PAGE_OVERHEAD	(I_HF_OFFSET + sizeof(indx_t))
98 
99 /* To allocate a pair, we need room for one key offset and one data offset. */
100 #define PAIR_OVERHEAD	((sizeof(indx_t) << 1))
101 
102 /* Use this macro to extract a value of type T from page P at offset O. */
103 #define REFERENCE(P, T, O)  (((T *)((u_int8_t *)(P) + O))[0])
104 
105 /*
106  * Use these macros to access fields on a page; P is a PAGE16 *.
107  */
108 #define NUM_ENT(P)	(REFERENCE((P), indx_t, I_ENTRIES))
109 #define PREV_PGNO(P)	(REFERENCE((P), db_pgno_t, I_PREV_PGNO))
110 #define NEXT_PGNO(P)	(REFERENCE((P), db_pgno_t, I_NEXT_PGNO))
111 #define TYPE(P)		(REFERENCE((P), u_int8_t, I_TYPE))
112 #define OFFSET(P)	(REFERENCE((P), indx_t, I_HF_OFFSET))
113 /*
114  * We need to store a page's own address on each page (unlike the Btree
115  * access method which needs the previous page).  We use the PREV_PGNO
116  * field to store our own page number.
117  */
118 #define ADDR(P)		(PREV_PGNO((P)))
119 
120 /* Extract key/data offsets and data for a given index. */
121 #define DATA_OFF(P, N) \
122 	REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD + sizeof(indx_t))
123 #define KEY_OFF(P, N) \
124 	REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD)
125 
126 #define KEY(P, N)	(((PAGE8 *)(P)) + KEY_OFF((P), (N)))
127 #define DATA(P, N)	(((PAGE8 *)(P)) + DATA_OFF((P), (N)))
128 
129 /*
130  * Macros used to compute various sizes on a page.
131  */
132 #define	PAIRSIZE(K, D)	(PAIR_OVERHEAD + (K)->size + (D)->size)
133 #define BIGOVERHEAD	(4 * sizeof(u_int16_t))
134 #define KEYSIZE(K)	(4 * sizeof(u_int16_t) + (K)->size);
135 #define OVFLSIZE	(2 * sizeof(u_int16_t))
136 #define BIGPAGEOVERHEAD (4 * sizeof(u_int16_t))
137 #define BIGPAGEOFFSET   4
138 #define BIGPAGESIZE(P)	((P)->BSIZE - BIGPAGEOVERHEAD)
139 
140 #define PAGE_META(N)	(((N) + 3) * sizeof(u_int16_t))
141 #define MINFILL 0.75
142 #define ISBIG(N, P)	(((N) > ((P)->hdr.bsize * MINFILL)) ? 1 : 0)
143 
144 #define ITEMSIZE(I)    (sizeof(u_int16_t) + (I)->size)
145 
146 /*
147  * Big key/data pages use a different page format.  They have a single
148  * key/data "pair" containing the length of the key and data instead
149  * of offsets.
150  */
151 #define BIGKEYLEN(P)	(KEY_OFF((P), 0))
152 #define BIGDATALEN(P)	(DATA_OFF((P), 0))
153 #define BIGKEY(P)	(((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD)
154 #define BIGDATA(P) \
155 	(((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD + KEY_OFF((P), 0))
156 
157 
158 #define OVFLPAGE	0
159 #define BIGPAIR		0
160 #define INVALID_PGNO	0xFFFFFFFF
161 
162 typedef unsigned short PAGE16;
163 typedef unsigned char  PAGE8;
164 
165 #define A_BUCKET	0
166 #define A_OVFL		1
167 #define A_BITMAP	2
168 #define A_RAW		4
169 #define A_HEADER	5
170 
171 #define PAIRFITS(P,K,D)	((PAIRSIZE((K),(D))) <= FREESPACE((P)))
172 #define BIGPAIRFITS(P)	((FREESPACE((P)) >= PAIR_OVERHEAD))
173 /*
174  * Since these are all unsigned, we need to guarantee that we never go
175  * negative.  Offset values are 0-based and overheads are one based (i.e.
176  * one byte of overhead is 1, not 0), so we need to convert OFFSETs to
177  * 1-based counting before subtraction.
178  */
179 #define FREESPACE(P) \
180 	((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
181 
182 /*
183  * Overhead on header pages is just one word -- the length of the
184  * header info stored on that page.
185  */
186 #define HEADER_OVERHEAD 4
187 
188 #define HASH_PAGE	2
189 #define HASH_BIGPAGE	3
190 #define HASH_OVFLPAGE	4
191 
192 #ifdef	__cplusplus
193 }
194 #endif
195 
196 #endif	/* !_KRB5_DB2_PAGE_H */
197