1*46373Sbostic /*- 2*46373Sbostic * Copyright (c) 1990 The Regents of the University of California. 3*46373Sbostic * All rights reserved. 4*46373Sbostic * 5*46373Sbostic * This code is derived from software contributed to Berkeley by 6*46373Sbostic * Margo Seltzer. 7*46373Sbostic * 8*46373Sbostic * %sccs.include.redist.c% 9*46373Sbostic * 10*46373Sbostic * @(#)page.h 5.1 (Berkeley) 02/12/91 11*46373Sbostic */ 12*46373Sbostic 13*46373Sbostic /* 14*46373Sbostic Definitions for hashing page file format. 15*46373Sbostic */ 16*46373Sbostic extern HTAB *hashp; 17*46373Sbostic /* 18*46373Sbostic * routines dealing with a data page 19*46373Sbostic * 20*46373Sbostic * page format: 21*46373Sbostic * +------------------------------+ 22*46373Sbostic * p | n | keyoff | datoff | keyoff | 23*46373Sbostic * +------------+--------+--------+ 24*46373Sbostic * | datoff | free | ptr | --> | 25*46373Sbostic * +--------+---------------------+ 26*46373Sbostic * | F R E E A R E A | 27*46373Sbostic * +--------------+---------------+ 28*46373Sbostic * | <---- - - - | data | 29*46373Sbostic * +--------+-----+----+----------+ 30*46373Sbostic * | key | data | key | 31*46373Sbostic * +--------+----------+----------+ 32*46373Sbostic * 33*46373Sbostic * Pointer to the free space is always: p[p[0] + 2] 34*46373Sbostic * Amount of free space on the page is: p[p[0] + 1] 35*46373Sbostic */ 36*46373Sbostic 37*46373Sbostic /* 38*46373Sbostic How many bytes required for this pair? 39*46373Sbostic 2 shorts in the table at the top of the page + 40*46373Sbostic room for the key and room for the data 41*46373Sbostic 42*46373Sbostic We prohibit entering a pair on a page unless there is also 43*46373Sbostic room to append an overflow page. The reason for this it that 44*46373Sbostic you can get in a situation where a single key/data pair fits 45*46373Sbostic on a page, but you can't append an overflow page and later 46*46373Sbostic you'd have to split the key/data and handle like a big pair. 47*46373Sbostic You might as well do this up front. 48*46373Sbostic 49*46373Sbostic */ 50*46373Sbostic #define PAIRSIZE(K,D) (2*sizeof(u_short) + K->size + D->size) 51*46373Sbostic #define BIGOVERHEAD (4*sizeof(u_short)) 52*46373Sbostic #define KEYSIZE(K) (4*sizeof(u_short) + K->size); 53*46373Sbostic #define OVFLSIZE (2*sizeof(u_short)) 54*46373Sbostic #define FREESPACE(P) (P[P[0]+1]) 55*46373Sbostic #define OFFSET(P) (P[P[0]+2]) 56*46373Sbostic #define PAIRFITS(P,K,D) ((P[1] >= REAL_KEY) && \ 57*46373Sbostic (PAIRSIZE(K,D) + OVFLSIZE) <= FREESPACE(P)) 58*46373Sbostic #define PAGE_META(N) ((N+3) * sizeof(u_short)) 59*46373Sbostic 60*46373Sbostic typedef struct { 61*46373Sbostic BUFHEAD *newp; 62*46373Sbostic BUFHEAD *oldp; 63*46373Sbostic BUFHEAD *nextp; 64*46373Sbostic u_short next_addr; 65*46373Sbostic } SPLIT_RETURN; 66*46373Sbostic 67