page.h revision 1.4.2.2
1 1.4.2.2 cgd /*- 2 1.4.2.2 cgd * Copyright (c) 1990, 1993, 1994 3 1.4.2.2 cgd * The Regents of the University of California. All rights reserved. 4 1.4.2.2 cgd * 5 1.4.2.2 cgd * This code is derived from software contributed to Berkeley by 6 1.4.2.2 cgd * Margo Seltzer. 7 1.4.2.2 cgd * 8 1.4.2.2 cgd * Redistribution and use in source and binary forms, with or without 9 1.4.2.2 cgd * modification, are permitted provided that the following conditions 10 1.4.2.2 cgd * are met: 11 1.4.2.2 cgd * 1. Redistributions of source code must retain the above copyright 12 1.4.2.2 cgd * notice, this list of conditions and the following disclaimer. 13 1.4.2.2 cgd * 2. Redistributions in binary form must reproduce the above copyright 14 1.4.2.2 cgd * notice, this list of conditions and the following disclaimer in the 15 1.4.2.2 cgd * documentation and/or other materials provided with the distribution. 16 1.4.2.2 cgd * 3. All advertising materials mentioning features or use of this software 17 1.4.2.2 cgd * must display the following acknowledgement: 18 1.4.2.2 cgd * This product includes software developed by the University of 19 1.4.2.2 cgd * California, Berkeley and its contributors. 20 1.4.2.2 cgd * 4. Neither the name of the University nor the names of its contributors 21 1.4.2.2 cgd * may be used to endorse or promote products derived from this software 22 1.4.2.2 cgd * without specific prior written permission. 23 1.4.2.2 cgd * 24 1.4.2.2 cgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 1.4.2.2 cgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 1.4.2.2 cgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 1.4.2.2 cgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 1.4.2.2 cgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 1.4.2.2 cgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 1.4.2.2 cgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 1.4.2.2 cgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 1.4.2.2 cgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 1.4.2.2 cgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 1.4.2.2 cgd * SUCH DAMAGE. 35 1.4.2.2 cgd * 36 1.4.2.2 cgd * @(#)page.h 8.2 (Berkeley) 5/31/94 37 1.4.2.2 cgd */ 38 1.4.2.2 cgd 39 1.4.2.2 cgd /* 40 1.4.2.2 cgd * Definitions for hashing page file format. 41 1.4.2.2 cgd */ 42 1.4.2.2 cgd 43 1.4.2.2 cgd /* 44 1.4.2.2 cgd * routines dealing with a data page 45 1.4.2.2 cgd * 46 1.4.2.2 cgd * page format: 47 1.4.2.2 cgd * +------------------------------+ 48 1.4.2.2 cgd * p | n | keyoff | datoff | keyoff | 49 1.4.2.2 cgd * +------------+--------+--------+ 50 1.4.2.2 cgd * | datoff | free | ptr | --> | 51 1.4.2.2 cgd * +--------+---------------------+ 52 1.4.2.2 cgd * | F R E E A R E A | 53 1.4.2.2 cgd * +--------------+---------------+ 54 1.4.2.2 cgd * | <---- - - - | data | 55 1.4.2.2 cgd * +--------+-----+----+----------+ 56 1.4.2.2 cgd * | key | data | key | 57 1.4.2.2 cgd * +--------+----------+----------+ 58 1.4.2.2 cgd * 59 1.4.2.2 cgd * Pointer to the free space is always: p[p[0] + 2] 60 1.4.2.2 cgd * Amount of free space on the page is: p[p[0] + 1] 61 1.4.2.2 cgd */ 62 1.4.2.2 cgd 63 1.4.2.2 cgd /* 64 1.4.2.2 cgd * How many bytes required for this pair? 65 1.4.2.2 cgd * 2 shorts in the table at the top of the page + room for the 66 1.4.2.2 cgd * key and room for the data 67 1.4.2.2 cgd * 68 1.4.2.2 cgd * We prohibit entering a pair on a page unless there is also room to append 69 1.4.2.2 cgd * an overflow page. The reason for this it that you can get in a situation 70 1.4.2.2 cgd * where a single key/data pair fits on a page, but you can't append an 71 1.4.2.2 cgd * overflow page and later you'd have to split the key/data and handle like 72 1.4.2.2 cgd * a big pair. 73 1.4.2.2 cgd * You might as well do this up front. 74 1.4.2.2 cgd */ 75 1.4.2.2 cgd 76 1.4.2.2 cgd #define PAIRSIZE(K,D) (2*sizeof(u_int16_t) + (K)->size + (D)->size) 77 1.4.2.2 cgd #define BIGOVERHEAD (4*sizeof(u_int16_t)) 78 1.4.2.2 cgd #define KEYSIZE(K) (4*sizeof(u_int16_t) + (K)->size); 79 1.4.2.2 cgd #define OVFLSIZE (2*sizeof(u_int16_t)) 80 1.4.2.2 cgd #define FREESPACE(P) ((P)[(P)[0]+1]) 81 1.4.2.2 cgd #define OFFSET(P) ((P)[(P)[0]+2]) 82 1.4.2.2 cgd #define PAIRFITS(P,K,D) \ 83 1.4.2.2 cgd (((P)[2] >= REAL_KEY) && \ 84 1.4.2.2 cgd (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) 85 1.4.2.2 cgd #define PAGE_META(N) (((N)+3) * sizeof(u_int16_t)) 86 1.4.2.2 cgd 87 1.4.2.2 cgd typedef struct { 88 1.4.2.2 cgd BUFHEAD *newp; 89 1.4.2.2 cgd BUFHEAD *oldp; 90 1.4.2.2 cgd BUFHEAD *nextp; 91 1.4.2.2 cgd u_int16_t next_addr; 92 1.4.2.2 cgd } SPLIT_RETURN; 93
Indexes created Mon Oct 27 08:10:08 GMT 2025