146373Sbostic /*- 2*62489Sbostic * Copyright (c) 1990, 1993 3*62489Sbostic * The Regents of the University of California. All rights reserved. 446373Sbostic * 546373Sbostic * This code is derived from software contributed to Berkeley by 646373Sbostic * Margo Seltzer. 746373Sbostic * 846373Sbostic * %sccs.include.redist.c% 946373Sbostic * 10*62489Sbostic * @(#)page.h 8.1 (Berkeley) 06/06/93 1146373Sbostic */ 1246373Sbostic 1346373Sbostic /* 1450997Sbostic * Definitions for hashing page file format. 1550997Sbostic */ 1650997Sbostic 1746373Sbostic /* 1846373Sbostic * routines dealing with a data page 1946373Sbostic * 2046373Sbostic * page format: 2146373Sbostic * +------------------------------+ 2246373Sbostic * p | n | keyoff | datoff | keyoff | 2346373Sbostic * +------------+--------+--------+ 2446373Sbostic * | datoff | free | ptr | --> | 2546373Sbostic * +--------+---------------------+ 2646373Sbostic * | F R E E A R E A | 2746373Sbostic * +--------------+---------------+ 2846373Sbostic * | <---- - - - | data | 2946373Sbostic * +--------+-----+----+----------+ 3046373Sbostic * | key | data | key | 3146373Sbostic * +--------+----------+----------+ 3246373Sbostic * 3346373Sbostic * Pointer to the free space is always: p[p[0] + 2] 3446373Sbostic * Amount of free space on the page is: p[p[0] + 1] 3546373Sbostic */ 3646373Sbostic 3746373Sbostic /* 3850997Sbostic * How many bytes required for this pair? 3950997Sbostic * 2 shorts in the table at the top of the page + room for the 4050997Sbostic * key and room for the data 4150997Sbostic * 4250997Sbostic * We prohibit entering a pair on a page unless there is also room to append 4350997Sbostic * an overflow page. The reason for this it that you can get in a situation 4450997Sbostic * where a single key/data pair fits on a page, but you can't append an 4550997Sbostic * overflow page and later you'd have to split the key/data and handle like 4650997Sbostic * a big pair. 4750997Sbostic * You might as well do this up front. 4850997Sbostic */ 4946373Sbostic 5050997Sbostic #define PAIRSIZE(K,D) (2*sizeof(u_short) + (K)->size + (D)->size) 5146373Sbostic #define BIGOVERHEAD (4*sizeof(u_short)) 5250997Sbostic #define KEYSIZE(K) (4*sizeof(u_short) + (K)->size); 5346373Sbostic #define OVFLSIZE (2*sizeof(u_short)) 5450997Sbostic #define FREESPACE(P) ((P)[(P)[0]+1]) 5550997Sbostic #define OFFSET(P) ((P)[(P)[0]+2]) 5650997Sbostic #define PAIRFITS(P,K,D) \ 5762486Sbostic (((P)[2] >= REAL_KEY) && \ 5850997Sbostic (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) 5950997Sbostic #define PAGE_META(N) (((N)+3) * sizeof(u_short)) 6046373Sbostic 6146373Sbostic typedef struct { 6250997Sbostic BUFHEAD *newp; 6350997Sbostic BUFHEAD *oldp; 6450997Sbostic BUFHEAD *nextp; 6550997Sbostic u_short next_addr; 6650997Sbostic } SPLIT_RETURN; 67