146373Sbostic /*- 246373Sbostic * Copyright (c) 1990 The Regents of the University of California. 346373Sbostic * 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*50997Sbostic * @(#)page.h 5.2 (Berkeley) 09/04/91 1146373Sbostic */ 1246373Sbostic 1346373Sbostic /* 14*50997Sbostic * Definitions for hashing page file format. 15*50997Sbostic */ 16*50997Sbostic 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 /* 38*50997Sbostic * How many bytes required for this pair? 39*50997Sbostic * 2 shorts in the table at the top of the page + room for the 40*50997Sbostic * key and room for the data 41*50997Sbostic * 42*50997Sbostic * We prohibit entering a pair on a page unless there is also room to append 43*50997Sbostic * an overflow page. The reason for this it that you can get in a situation 44*50997Sbostic * where a single key/data pair fits on a page, but you can't append an 45*50997Sbostic * overflow page and later you'd have to split the key/data and handle like 46*50997Sbostic * a big pair. 47*50997Sbostic * You might as well do this up front. 48*50997Sbostic */ 4946373Sbostic 50*50997Sbostic #define PAIRSIZE(K,D) (2*sizeof(u_short) + (K)->size + (D)->size) 5146373Sbostic #define BIGOVERHEAD (4*sizeof(u_short)) 52*50997Sbostic #define KEYSIZE(K) (4*sizeof(u_short) + (K)->size); 5346373Sbostic #define OVFLSIZE (2*sizeof(u_short)) 54*50997Sbostic #define FREESPACE(P) ((P)[(P)[0]+1]) 55*50997Sbostic #define OFFSET(P) ((P)[(P)[0]+2]) 56*50997Sbostic #define PAIRFITS(P,K,D) \ 57*50997Sbostic (((P)[1] >= REAL_KEY) && \ 58*50997Sbostic (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) 59*50997Sbostic #define PAGE_META(N) (((N)+3) * sizeof(u_short)) 6046373Sbostic 6146373Sbostic typedef struct { 62*50997Sbostic BUFHEAD *newp; 63*50997Sbostic BUFHEAD *oldp; 64*50997Sbostic BUFHEAD *nextp; 65*50997Sbostic u_short next_addr; 66*50997Sbostic } SPLIT_RETURN; 67