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