1 /*- 2 * Copyright (c) 1990, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Margo Seltzer. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)page.h 8.4 (Berkeley) 11/7/95 37 */ 38 39 #define HI_MASK 0xFFFF0000 40 #define LO_MASK (~HI_MASK) 41 42 #define HI(N) ((u_int16_t)(((N) & HI_MASK) >> 16)) 43 #define LO(N) ((u_int16_t)((N) & LO_MASK)) 44 45 /* Constants for big key page overhead information. */ 46 #define NUMSHORTS 0 47 #define KEYLEN 1 48 #define DATALEN 2 49 #define NEXTPAGE 3 50 51 /* 52 * Hash pages store meta-data beginning at the top of the page (offset 0) 53 * and key/data values beginning at the bottom of the page (offset pagesize). 54 * Fields are always accessed via macros so that we can change the page 55 * format without too much pain. The only changes that will require massive 56 * code changes are if we no longer store key/data offsets next to each 57 * other (since we use that fact to compute key lengths). In the accessor 58 * macros below, P means a pointer to the page, I means an index of the 59 * particular entry being accessed. 60 * 61 * Hash base page format 62 * BYTE ITEM NBYTES TYPE ACCESSOR MACRO 63 * ---- ------------------ ------ -------- -------------- 64 * 0 previous page number 4 db_pgno_t PREV_PGNO(P) 65 * 4 next page number 4 db_pgno_t NEXT_PGNO(P) 66 * 8 # pairs on page 2 indx_t NUM_ENT(P) 67 * 10 page type 1 u_int8_t TYPE(P) 68 * 11 padding 1 u_int8_t none 69 * 12 highest free byte 2 indx_t OFFSET(P) 70 * 14 key offset 0 2 indx_t KEY_OFF(P, I) 71 * 16 data offset 0 2 indx_t DATA_OFF(P, I) 72 * 18 key offset 1 2 indx_t KEY_OFF(P, I) 73 * 20 data offset 1 2 indx_t DATA_OFF(P, I) 74 * ...etc... 75 */ 76 77 /* Indices (in bytes) of the beginning of each of these entries */ 78 #define I_PREV_PGNO 0 79 #define I_NEXT_PGNO 4 80 #define I_ENTRIES 8 81 #define I_TYPE 10 82 #define I_HF_OFFSET 12 83 84 /* Overhead is everything prior to the first key/data pair. */ 85 #define PAGE_OVERHEAD (I_HF_OFFSET + sizeof(indx_t)) 86 87 /* To allocate a pair, we need room for one key offset and one data offset. */ 88 #define PAIR_OVERHEAD ((sizeof(indx_t) << 1)) 89 90 /* Use this macro to extract a value of type T from page P at offset O. */ 91 #define REFERENCE(P, T, O) (((T *)(void *)((u_int8_t *)(void *)(P) + O))[0]) 92 93 /* 94 * Use these macros to access fields on a page; P is a PAGE16 *. 95 */ 96 #define NUM_ENT(P) (REFERENCE((P), indx_t, I_ENTRIES)) 97 #define PREV_PGNO(P) (REFERENCE((P), db_pgno_t, I_PREV_PGNO)) 98 #define NEXT_PGNO(P) (REFERENCE((P), db_pgno_t, I_NEXT_PGNO)) 99 #define TYPE(P) (REFERENCE((P), u_int8_t, I_TYPE)) 100 #define OFFSET(P) (REFERENCE((P), indx_t, I_HF_OFFSET)) 101 /* 102 * We need to store a page's own address on each page (unlike the Btree 103 * access method which needs the previous page). We use the PREV_PGNO 104 * field to store our own page number. 105 */ 106 #define ADDR(P) (PREV_PGNO((P))) 107 108 /* Extract key/data offsets and data for a given index. */ 109 #define DATA_OFF(P, N) \ 110 REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD + sizeof(indx_t)) 111 #define KEY_OFF(P, N) \ 112 REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD) 113 114 #define KEY(P, N) (((PAGE8 *)(P)) + KEY_OFF((P), (N))) 115 #define DATA(P, N) (((PAGE8 *)(P)) + DATA_OFF((P), (N))) 116 117 /* 118 * Macros used to compute various sizes on a page. 119 */ 120 #define PAIRSIZE(K, D) (PAIR_OVERHEAD + (K)->size + (D)->size) 121 #define BIGOVERHEAD (4 * sizeof(u_int16_t)) 122 #define KEYSIZE(K) (4 * sizeof(u_int16_t) + (K)->size); 123 #define OVFLSIZE (2 * sizeof(u_int16_t)) 124 #define BIGPAGEOVERHEAD (4 * sizeof(u_int16_t)) 125 #define BIGPAGEOFFSET 4 126 #define BIGPAGESIZE(P) ((P)->BSIZE - BIGPAGEOVERHEAD) 127 128 #define PAGE_META(N) (((N) + 3) * sizeof(u_int16_t)) 129 #define MINFILL 0.75 130 #define ISBIG(N, P) (((N) > ((P)->hdr.bsize * MINFILL)) ? 1 : 0) 131 132 #define ITEMSIZE(I) (sizeof(u_int16_t) + (I)->size) 133 134 /* 135 * Big key/data pages use a different page format. They have a single 136 * key/data "pair" containing the length of the key and data instead 137 * of offsets. 138 */ 139 #define BIGKEYLEN(P) (KEY_OFF((P), 0)) 140 #define BIGDATALEN(P) (DATA_OFF((P), 0)) 141 #define BIGKEY(P) (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD) 142 #define BIGDATA(P) \ 143 (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD + KEY_OFF((P), 0)) 144 145 146 #define OVFLPAGE 0 147 #define BIGPAIR 0 148 #define INVALID_PGNO 0xFFFFFFFF 149 150 typedef unsigned short PAGE16; 151 typedef unsigned char PAGE8; 152 153 #define A_BUCKET 0 154 #define A_OVFL 1 155 #define A_BITMAP 2 156 #define A_RAW 4 157 #define A_HEADER 5 158 159 #define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) 160 #define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) 161 /* 162 * Since these are all unsigned, we need to guarantee that we never go 163 * negative. Offset values are 0-based and overheads are one based (i.e. 164 * one byte of overhead is 1, not 0), so we need to convert OFFSETs to 165 * 1-based counting before subtraction. 166 */ 167 #define FREESPACE(P) \ 168 ((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) 169 170 /* 171 * Overhead on header pages is just one word -- the length of the 172 * header info stored on that page. 173 */ 174 #define HEADER_OVERHEAD 4 175 176 #define HASH_PAGE 2 177 #define HASH_BIGPAGE 3 178 #define HASH_OVFLPAGE 4 179