1*40b37a3bSjoerg /* $NetBSD: page.h,v 1.8 2008/08/26 21:18:38 joerg Exp $ */ 2402f19d1Scgd 361f28255Scgd /*- 4a6d14e36Scgd * Copyright (c) 1990, 1993, 1994 59f0aa214Scgd * The Regents of the University of California. All rights reserved. 661f28255Scgd * 761f28255Scgd * This code is derived from software contributed to Berkeley by 861f28255Scgd * Margo Seltzer. 961f28255Scgd * 1061f28255Scgd * Redistribution and use in source and binary forms, with or without 1161f28255Scgd * modification, are permitted provided that the following conditions 1261f28255Scgd * are met: 1361f28255Scgd * 1. Redistributions of source code must retain the above copyright 1461f28255Scgd * notice, this list of conditions and the following disclaimer. 1561f28255Scgd * 2. Redistributions in binary form must reproduce the above copyright 1661f28255Scgd * notice, this list of conditions and the following disclaimer in the 1761f28255Scgd * documentation and/or other materials provided with the distribution. 18eb7c1594Sagc * 3. Neither the name of the University nor the names of its contributors 1961f28255Scgd * may be used to endorse or promote products derived from this software 2061f28255Scgd * without specific prior written permission. 2161f28255Scgd * 2261f28255Scgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2361f28255Scgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2461f28255Scgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2561f28255Scgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2661f28255Scgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2761f28255Scgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2861f28255Scgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2961f28255Scgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3061f28255Scgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3161f28255Scgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3261f28255Scgd * SUCH DAMAGE. 3361f28255Scgd * 34a6d14e36Scgd * @(#)page.h 8.2 (Berkeley) 5/31/94 3561f28255Scgd */ 3661f28255Scgd 3761f28255Scgd /* 389f0aa214Scgd * Definitions for hashing page file format. 3961f28255Scgd */ 409f0aa214Scgd 4161f28255Scgd /* 4261f28255Scgd * routines dealing with a data page 4361f28255Scgd * 4461f28255Scgd * page format: 4561f28255Scgd * +------------------------------+ 4661f28255Scgd * p | n | keyoff | datoff | keyoff | 4761f28255Scgd * +------------+--------+--------+ 4861f28255Scgd * | datoff | free | ptr | --> | 4961f28255Scgd * +--------+---------------------+ 5061f28255Scgd * | F R E E A R E A | 5161f28255Scgd * +--------------+---------------+ 5261f28255Scgd * | <---- - - - | data | 5361f28255Scgd * +--------+-----+----+----------+ 5461f28255Scgd * | key | data | key | 5561f28255Scgd * +--------+----------+----------+ 5661f28255Scgd * 5761f28255Scgd * Pointer to the free space is always: p[p[0] + 2] 5861f28255Scgd * Amount of free space on the page is: p[p[0] + 1] 5961f28255Scgd */ 6061f28255Scgd 6161f28255Scgd /* 629f0aa214Scgd * How many bytes required for this pair? 639f0aa214Scgd * 2 shorts in the table at the top of the page + room for the 649f0aa214Scgd * key and room for the data 659f0aa214Scgd * 669f0aa214Scgd * We prohibit entering a pair on a page unless there is also room to append 679f0aa214Scgd * an overflow page. The reason for this it that you can get in a situation 689f0aa214Scgd * where a single key/data pair fits on a page, but you can't append an 699f0aa214Scgd * overflow page and later you'd have to split the key/data and handle like 709f0aa214Scgd * a big pair. 719f0aa214Scgd * You might as well do this up front. 7261f28255Scgd */ 739f0aa214Scgd 74*40b37a3bSjoerg #define PAIRSIZE(K,D) (2*sizeof(uint16_t) + (K)->size + (D)->size) 75*40b37a3bSjoerg #define BIGOVERHEAD (4*sizeof(uint16_t)) 76*40b37a3bSjoerg #define KEYSIZE(K) (4*sizeof(uint16_t) + (K)->size); 77*40b37a3bSjoerg #define OVFLSIZE (2*sizeof(uint16_t)) 789f0aa214Scgd #define FREESPACE(P) ((P)[(P)[0]+1]) 799f0aa214Scgd #define OFFSET(P) ((P)[(P)[0]+2]) 809f0aa214Scgd #define PAIRFITS(P,K,D) \ 819f0aa214Scgd (((P)[2] >= REAL_KEY) && \ 829f0aa214Scgd (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) 83*40b37a3bSjoerg #define PAGE_META(N) (((N)+3) * sizeof(uint16_t)) 8461f28255Scgd 8561f28255Scgd typedef struct { 8661f28255Scgd BUFHEAD *newp; 8761f28255Scgd BUFHEAD *oldp; 8861f28255Scgd BUFHEAD *nextp; 89*40b37a3bSjoerg uint16_t next_addr; 9061f28255Scgd } SPLIT_RETURN; 91