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