17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * Copyright (c) 1997-2000 by Sun Microsystems, Inc. 37c478bd9Sstevel@tonic-gate * All rights reserved. 47c478bd9Sstevel@tonic-gate */ 57c478bd9Sstevel@tonic-gate 67c478bd9Sstevel@tonic-gate #ifndef _KRB5_DB2_PAGE_H 77c478bd9Sstevel@tonic-gate #define _KRB5_DB2_PAGE_H 87c478bd9Sstevel@tonic-gate 97c478bd9Sstevel@tonic-gate #ifdef __cplusplus 107c478bd9Sstevel@tonic-gate extern "C" { 117c478bd9Sstevel@tonic-gate #endif 127c478bd9Sstevel@tonic-gate 137c478bd9Sstevel@tonic-gate /*- 147c478bd9Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994 157c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved. 167c478bd9Sstevel@tonic-gate * 177c478bd9Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by 187c478bd9Sstevel@tonic-gate * Margo Seltzer. 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 217c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions 227c478bd9Sstevel@tonic-gate * are met: 237c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 247c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 257c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 267c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 277c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 287c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software 297c478bd9Sstevel@tonic-gate * must display the following acknowledgement: 307c478bd9Sstevel@tonic-gate * This product includes software developed by the University of 317c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors. 327c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors 337c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software 347c478bd9Sstevel@tonic-gate * without specific prior written permission. 357c478bd9Sstevel@tonic-gate * 367c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 377c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 387c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 397c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 407c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 417c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 427c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 437c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 447c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 457c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 467c478bd9Sstevel@tonic-gate * SUCH DAMAGE. 477c478bd9Sstevel@tonic-gate * 487c478bd9Sstevel@tonic-gate * @(#)page.h 8.4 (Berkeley) 11/7/95 497c478bd9Sstevel@tonic-gate */ 507c478bd9Sstevel@tonic-gate 517c478bd9Sstevel@tonic-gate #define HI_MASK 0xFFFF0000 527c478bd9Sstevel@tonic-gate #define LO_MASK (~HI_MASK) 537c478bd9Sstevel@tonic-gate 547c478bd9Sstevel@tonic-gate #define HI(N) ((u_int16_t)(((N) & HI_MASK) >> 16)) 557c478bd9Sstevel@tonic-gate #define LO(N) ((u_int16_t)((N) & LO_MASK)) 567c478bd9Sstevel@tonic-gate 577c478bd9Sstevel@tonic-gate /* Constants for big key page overhead information. */ 587c478bd9Sstevel@tonic-gate #define NUMSHORTS 0 597c478bd9Sstevel@tonic-gate #define KEYLEN 1 607c478bd9Sstevel@tonic-gate #define DATALEN 2 617c478bd9Sstevel@tonic-gate #define NEXTPAGE 3 627c478bd9Sstevel@tonic-gate 637c478bd9Sstevel@tonic-gate /* 647c478bd9Sstevel@tonic-gate * Hash pages store meta-data beginning at the top of the page (offset 0) 657c478bd9Sstevel@tonic-gate * and key/data values beginning at the bottom of the page (offset pagesize). 667c478bd9Sstevel@tonic-gate * Fields are always accessed via macros so that we can change the page 677c478bd9Sstevel@tonic-gate * format without too much pain. The only changes that will require massive 687c478bd9Sstevel@tonic-gate * code changes are if we no longer store key/data offsets next to each 697c478bd9Sstevel@tonic-gate * other (since we use that fact to compute key lengths). In the accessor 707c478bd9Sstevel@tonic-gate * macros below, P means a pointer to the page, I means an index of the 717c478bd9Sstevel@tonic-gate * particular entry being accessed. 72*1da57d55SToomas Soome * 737c478bd9Sstevel@tonic-gate * Hash base page format 747c478bd9Sstevel@tonic-gate * BYTE ITEM NBYTES TYPE ACCESSOR MACRO 757c478bd9Sstevel@tonic-gate * ---- ------------------ ------ -------- -------------- 767c478bd9Sstevel@tonic-gate * 0 previous page number 4 db_pgno_t PREV_PGNO(P) 777c478bd9Sstevel@tonic-gate * 4 next page number 4 db_pgno_t NEXT_PGNO(P) 787c478bd9Sstevel@tonic-gate * 8 # pairs on page 2 indx_t NUM_ENT(P) 797c478bd9Sstevel@tonic-gate * 10 page type 1 u_int8_t TYPE(P) 807c478bd9Sstevel@tonic-gate * 11 padding 1 u_int8_t none 817c478bd9Sstevel@tonic-gate * 12 highest free byte 2 indx_t OFFSET(P) 827c478bd9Sstevel@tonic-gate * 14 key offset 0 2 indx_t KEY_OFF(P, I) 837c478bd9Sstevel@tonic-gate * 16 data offset 0 2 indx_t DATA_OFF(P, I) 847c478bd9Sstevel@tonic-gate * 18 key offset 1 2 indx_t KEY_OFF(P, I) 857c478bd9Sstevel@tonic-gate * 20 data offset 1 2 indx_t DATA_OFF(P, I) 867c478bd9Sstevel@tonic-gate * ...etc... 877c478bd9Sstevel@tonic-gate */ 887c478bd9Sstevel@tonic-gate 897c478bd9Sstevel@tonic-gate /* Indices (in bytes) of the beginning of each of these entries */ 907c478bd9Sstevel@tonic-gate #define I_PREV_PGNO 0 917c478bd9Sstevel@tonic-gate #define I_NEXT_PGNO 4 927c478bd9Sstevel@tonic-gate #define I_ENTRIES 8 937c478bd9Sstevel@tonic-gate #define I_TYPE 10 947c478bd9Sstevel@tonic-gate #define I_HF_OFFSET 12 957c478bd9Sstevel@tonic-gate 967c478bd9Sstevel@tonic-gate /* Overhead is everything prior to the first key/data pair. */ 977c478bd9Sstevel@tonic-gate #define PAGE_OVERHEAD (I_HF_OFFSET + sizeof(indx_t)) 987c478bd9Sstevel@tonic-gate 997c478bd9Sstevel@tonic-gate /* To allocate a pair, we need room for one key offset and one data offset. */ 1007c478bd9Sstevel@tonic-gate #define PAIR_OVERHEAD ((sizeof(indx_t) << 1)) 1017c478bd9Sstevel@tonic-gate 1027c478bd9Sstevel@tonic-gate /* Use this macro to extract a value of type T from page P at offset O. */ 1037c478bd9Sstevel@tonic-gate #define REFERENCE(P, T, O) (((T *)((u_int8_t *)(P) + O))[0]) 1047c478bd9Sstevel@tonic-gate 1057c478bd9Sstevel@tonic-gate /* 1067c478bd9Sstevel@tonic-gate * Use these macros to access fields on a page; P is a PAGE16 *. 1077c478bd9Sstevel@tonic-gate */ 1087c478bd9Sstevel@tonic-gate #define NUM_ENT(P) (REFERENCE((P), indx_t, I_ENTRIES)) 1097c478bd9Sstevel@tonic-gate #define PREV_PGNO(P) (REFERENCE((P), db_pgno_t, I_PREV_PGNO)) 1107c478bd9Sstevel@tonic-gate #define NEXT_PGNO(P) (REFERENCE((P), db_pgno_t, I_NEXT_PGNO)) 1117c478bd9Sstevel@tonic-gate #define TYPE(P) (REFERENCE((P), u_int8_t, I_TYPE)) 1127c478bd9Sstevel@tonic-gate #define OFFSET(P) (REFERENCE((P), indx_t, I_HF_OFFSET)) 1137c478bd9Sstevel@tonic-gate /* 1147c478bd9Sstevel@tonic-gate * We need to store a page's own address on each page (unlike the Btree 1157c478bd9Sstevel@tonic-gate * access method which needs the previous page). We use the PREV_PGNO 1167c478bd9Sstevel@tonic-gate * field to store our own page number. 1177c478bd9Sstevel@tonic-gate */ 1187c478bd9Sstevel@tonic-gate #define ADDR(P) (PREV_PGNO((P))) 1197c478bd9Sstevel@tonic-gate 1207c478bd9Sstevel@tonic-gate /* Extract key/data offsets and data for a given index. */ 1217c478bd9Sstevel@tonic-gate #define DATA_OFF(P, N) \ 1227c478bd9Sstevel@tonic-gate REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD + sizeof(indx_t)) 1237c478bd9Sstevel@tonic-gate #define KEY_OFF(P, N) \ 1247c478bd9Sstevel@tonic-gate REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD) 1257c478bd9Sstevel@tonic-gate 1267c478bd9Sstevel@tonic-gate #define KEY(P, N) (((PAGE8 *)(P)) + KEY_OFF((P), (N))) 1277c478bd9Sstevel@tonic-gate #define DATA(P, N) (((PAGE8 *)(P)) + DATA_OFF((P), (N))) 1287c478bd9Sstevel@tonic-gate 1297c478bd9Sstevel@tonic-gate /* 1307c478bd9Sstevel@tonic-gate * Macros used to compute various sizes on a page. 1317c478bd9Sstevel@tonic-gate */ 1327c478bd9Sstevel@tonic-gate #define PAIRSIZE(K, D) (PAIR_OVERHEAD + (K)->size + (D)->size) 1337c478bd9Sstevel@tonic-gate #define BIGOVERHEAD (4 * sizeof(u_int16_t)) 1347c478bd9Sstevel@tonic-gate #define KEYSIZE(K) (4 * sizeof(u_int16_t) + (K)->size); 1357c478bd9Sstevel@tonic-gate #define OVFLSIZE (2 * sizeof(u_int16_t)) 1367c478bd9Sstevel@tonic-gate #define BIGPAGEOVERHEAD (4 * sizeof(u_int16_t)) 1377c478bd9Sstevel@tonic-gate #define BIGPAGEOFFSET 4 1387c478bd9Sstevel@tonic-gate #define BIGPAGESIZE(P) ((P)->BSIZE - BIGPAGEOVERHEAD) 1397c478bd9Sstevel@tonic-gate 1407c478bd9Sstevel@tonic-gate #define PAGE_META(N) (((N) + 3) * sizeof(u_int16_t)) 1417c478bd9Sstevel@tonic-gate #define MINFILL 0.75 1427c478bd9Sstevel@tonic-gate #define ISBIG(N, P) (((N) > ((P)->hdr.bsize * MINFILL)) ? 1 : 0) 1437c478bd9Sstevel@tonic-gate 1447c478bd9Sstevel@tonic-gate #define ITEMSIZE(I) (sizeof(u_int16_t) + (I)->size) 1457c478bd9Sstevel@tonic-gate 1467c478bd9Sstevel@tonic-gate /* 1477c478bd9Sstevel@tonic-gate * Big key/data pages use a different page format. They have a single 1487c478bd9Sstevel@tonic-gate * key/data "pair" containing the length of the key and data instead 1497c478bd9Sstevel@tonic-gate * of offsets. 1507c478bd9Sstevel@tonic-gate */ 1517c478bd9Sstevel@tonic-gate #define BIGKEYLEN(P) (KEY_OFF((P), 0)) 1527c478bd9Sstevel@tonic-gate #define BIGDATALEN(P) (DATA_OFF((P), 0)) 1537c478bd9Sstevel@tonic-gate #define BIGKEY(P) (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD) 1547c478bd9Sstevel@tonic-gate #define BIGDATA(P) \ 1557c478bd9Sstevel@tonic-gate (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD + KEY_OFF((P), 0)) 1567c478bd9Sstevel@tonic-gate 1577c478bd9Sstevel@tonic-gate 1587c478bd9Sstevel@tonic-gate #define OVFLPAGE 0 1597c478bd9Sstevel@tonic-gate #define BIGPAIR 0 1607c478bd9Sstevel@tonic-gate #define INVALID_PGNO 0xFFFFFFFF 1617c478bd9Sstevel@tonic-gate 1627c478bd9Sstevel@tonic-gate typedef unsigned short PAGE16; 1637c478bd9Sstevel@tonic-gate typedef unsigned char PAGE8; 1647c478bd9Sstevel@tonic-gate 1657c478bd9Sstevel@tonic-gate #define A_BUCKET 0 1667c478bd9Sstevel@tonic-gate #define A_OVFL 1 1677c478bd9Sstevel@tonic-gate #define A_BITMAP 2 1687c478bd9Sstevel@tonic-gate #define A_RAW 4 1697c478bd9Sstevel@tonic-gate #define A_HEADER 5 1707c478bd9Sstevel@tonic-gate 1717c478bd9Sstevel@tonic-gate #define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) 1727c478bd9Sstevel@tonic-gate #define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) 1737c478bd9Sstevel@tonic-gate /* 1747c478bd9Sstevel@tonic-gate * Since these are all unsigned, we need to guarantee that we never go 1757c478bd9Sstevel@tonic-gate * negative. Offset values are 0-based and overheads are one based (i.e. 1767c478bd9Sstevel@tonic-gate * one byte of overhead is 1, not 0), so we need to convert OFFSETs to 1777c478bd9Sstevel@tonic-gate * 1-based counting before subtraction. 1787c478bd9Sstevel@tonic-gate */ 1797c478bd9Sstevel@tonic-gate #define FREESPACE(P) \ 1807c478bd9Sstevel@tonic-gate ((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) 1817c478bd9Sstevel@tonic-gate 182*1da57d55SToomas Soome /* 1837c478bd9Sstevel@tonic-gate * Overhead on header pages is just one word -- the length of the 1847c478bd9Sstevel@tonic-gate * header info stored on that page. 1857c478bd9Sstevel@tonic-gate */ 1867c478bd9Sstevel@tonic-gate #define HEADER_OVERHEAD 4 1877c478bd9Sstevel@tonic-gate 1887c478bd9Sstevel@tonic-gate #define HASH_PAGE 2 1897c478bd9Sstevel@tonic-gate #define HASH_BIGPAGE 3 1907c478bd9Sstevel@tonic-gate #define HASH_OVFLPAGE 4 1917c478bd9Sstevel@tonic-gate 1927c478bd9Sstevel@tonic-gate #ifdef __cplusplus 1937c478bd9Sstevel@tonic-gate } 1947c478bd9Sstevel@tonic-gate #endif 1957c478bd9Sstevel@tonic-gate 1967c478bd9Sstevel@tonic-gate #endif /* !_KRB5_DB2_PAGE_H */ 197