/* ----------------------------------------------------------------
 *   FILE
 *	hash.h
 *
 *   DESCRIPTION
 *	header file for postgres hash access method implementation 
 *
 *   NOTES
 *	modeled after Margo Seltzer's hash implementation for unix. 
 *
 *   IDENTIFICATION
 *	/usr/local/devel/postgres-4.2-devel/src/backend/access/RCS/hash.h,v 1.3 1994/02/07 11:28:39 aoki Exp
 * ----------------------------------------------------------------
 */

#ifndef hashIncluded		/* include this file only once */
#define hashIncluded	1

/* 
 * An overflow page is a spare page allocated for storing data whose 
 * bucket doesn't have room to store it. We use overflow pages rather
 * than just splitting the bucket because there is a linear order in
 * the way we split buckets. In other words, if there isn't enough space
 * in the bucket itself, put it in an overflow page. 
 *
 * Overflow page addresses are stored in form: (Splitnumber, Page offset).
 *
 * A splitnumber is the number of the generation where the table doubles
 * in size. The ovflpage's offset within the splitnumber; offsets start
 * at 1. 
 * 
 * We convert the stored bitmap address into a page address with the
 * macro OADDR_OF(S, O) where S is the splitnumber and O is the page 
 * offset. 
 */
typedef uint32 	Bucket;
typedef bits16	OverflowPageAddress;
typedef uint32	SplitNumber;
typedef uint32  PageOffset;

/* A valid overflow address will always have a page offset >= 1 */
#define InvalidOvflAddress	0	
					   
#define SPLITSHIFT	11
#define SPLITMASK	0x7FF
#define SPLITNUM(N)	((SplitNumber)(((u_int)(N)) >> SPLITSHIFT))
#define OPAGENUM(N)	((PageOffset)((N) & SPLITMASK))
#define	OADDR_OF(S,O)	((OverflowPageAddress)((u_int)((u_int)(S) << SPLITSHIFT) + (O)))

#define BUCKET_TO_BLKNO(B) \
	((Bucket) ((B) + ((B) ? metap->SPARES[_hash_log2((B)+1)-1] : 0)) + 1)
#define OADDR_TO_BLKNO(B) 	 \
	((BlockNumber) \
	 (BUCKET_TO_BLKNO ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B))));

/* 
 * OVERFLOW_PAGE and BUCKET_PAGE are used to flag which type of
 * page we're looking at. This is necessary information when you're 
 * deleting tuples from a page. If all the tuples are deleted from
 * an overflow page, the overflow is made available to other buckets
 * by calling _hash_freeovflpage(). If all the tuples are deleted from
 * a bucket page, no additional action is necessary.
 */

#define OVERFLOW_PAGE	0x1
#define BUCKET_PAGE	0x2

typedef struct HashPageOpaqueData {
    bits16 hasho_flag;			/* is this page a bucket or ovfl */
    Bucket hasho_bucket;		/* bucket number this pg belongs to */
    OverflowPageAddress hasho_oaddr;	/* ovfl address of this ovfl pg */
    BlockNumber hasho_nextblkno;	/* next ovfl blkno */
    BlockNumber	hasho_prevblkno;	/* previous ovfl (or bucket) blkno */
} HashPageOpaqueData;

typedef HashPageOpaqueData        *HashPageOpaque;

/*
 *  ScanOpaqueData is used to remember which buffers we're currently
 *  examining in the scan.  We keep these buffers locked and pinned and
 *  recorded in the opaque entry of the scan in order to avoid doing a
 *  ReadBuffer() for every tuple in the index.  This avoids semop() calls,
 *  which are expensive.
 */

typedef struct HashScanOpaqueData {
    Buffer      hashso_curbuf;
    Buffer      hashso_mrkbuf;
} HashScanOpaqueData;

typedef HashScanOpaqueData        *HashScanOpaque;

/* 
 * Definitions for metapage.
 */

#define HASH_METAPAGE	0
#define HASH_MAGIC	0x6440640
#define HASH_VERSION	0

/*
 * NCACHED is used to set the array sizeof spares[] & bitmaps[].
 *
 * Spares[] is used to hold the number overflow pages currently
 * allocated at a certain splitpoint. For example, if spares[3] = 7
 * then there are a maximum of 7 ovflpages available at splitpoint 3.
 * The value in spares[] will change as ovflpages are added within
 * a splitpoint. 
 * 
 * Within a splitpoint, one can find which ovflpages are available and
 * which are used by looking at a bitmaps that are stored on the ovfl
 * pages themselves. There is at least one bitmap for every splitpoint's
 * ovflpages. Bitmaps[] contains the ovflpage addresses of the ovflpages 
 * that hold the ovflpage bitmaps. 
 *
 * The reason that the size is restricted to NCACHED (32) is because
 * the bitmaps are 16 bits: upper 5 represent the splitpoint, lower 11
 * indicate the page number within the splitpoint. Since there are 
 * only 5 bits to store the splitpoint, there can only be 32 splitpoints. 
 * Both spares[] and bitmaps[] use splitpoints as there indices, so there
 * can only be 32 of them. 
 */

#define	NCACHED		32	


typedef struct HashMetaPageData {
    uint32	hashm_magic;		/* magic no. for hash tables */
    uint32	hashm_version;		/* version ID */
    uint32	hashm_nkeys;		/* number of keys stored in the table */
    uint32	hashm_ffactor;		/* fill factor */
    uint16	hashm_bsize;		/* bucket size */
    uint16	hashm_bshift;		/* bucket shift */
    uint32 	hashm_maxbucket;	/* ID of maximum bucket in use */
    uint32	hashm_highmask;		/* mask to modulo into entire table */
    uint32	hashm_lowmask;		/* mask to modulo into lower half of table */
    uint32	hashm_ovflpoint;	/* pageno. from which ovflpgs being allocated */
    uint32	hashm_lastfreed;	/* last ovflpage freed */
    uint32	hashm_nmaps;		/* Initial number of bitmaps */
    uint32	hashm_spares[NCACHED];	/* spare pages available at splitpoints */
    bits16	hashm_bitmaps[NCACHED];	/* ovflpage address of ovflpage bitmaps */
    BlockNumber	hashm_mapp[NCACHED];	/* blknumbers of ovfl page maps */
    RegProcedure  hashm_procid;		/* hash procedure id from pg_proc */
} HashMetaPageData;

typedef HashMetaPageData *HashMetaPage;

/* Short hands for accessing structure */
#define BSIZE		hashm_bsize
#define BSHIFT		hashm_bshift
#define OVFL_POINT	hashm_ovflpoint
#define	LAST_FREED	hashm_lastfreed
#define MAX_BUCKET	hashm_maxbucket
#define FFACTOR		hashm_ffactor
#define HIGH_MASK	hashm_highmask
#define LOW_MASK	hashm_lowmask
#define NKEYS		hashm_nkeys
#define SPARES		hashm_spares
#define BITMAPS		hashm_bitmaps
#define VERSION		hashm_version
#define MAGIC		hashm_magic

extern bool	BuildingHash;

/*
 *  HashItems are what we store in the btree. They don't really need to have 
 *  the oids, and those should be taken out. 
 */

typedef struct HashItemData {
        OID                     hash_oid;
        IndexTupleData          hash_itup;
} HashItemData;

typedef HashItemData      *HashItem;

/*
 * Constants
 */
#define DEFAULT_BUCKET_SIZE	BLCKSZ		/* 8 K */ 
#define DEFAULT_BUCKET_SHIFT	13		/* log2(BUCKET) */
#define DEFAULT_FFACTOR		300
#define SPLITMAX		8
#define BYTE_SHIFT		3
#define INT_TO_BYTE		2
#define INT_BYTE_SHIFT		5
#define ALL_SET			((u_int)0xFFFFFFFF)
#define ALL_CLEAR		0

/*
 * The number of bits in an ovflpage bitmap which
 * tells which ovflpages are empty versus in use (NOT the number of
 * bits in an overflow page *address* bitmap). 
 */
#define BITS_PER_MAP	32	/* Number of bits in ovflpage bitmap */

/* Given the address of the beginning of a big map, clear/set the nth bit */
#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
#define ISSET(A, N)	((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))


#define	HASH_READ	0
#define	HASH_WRITE	1

#define HASH_INSERTION	0
#define HASH_DESCENT	1

#define OVFLPAGE	0

/*  
 *  In general, the hash code tries to localize its knowledge about page
 *  layout to a couple of routines.  However, we need a special value to
 *  indicate "no page number" in those places where we expect page numbers.
 */

#define P_NONE		0

/*
 *  Strategy number. There's only one valid strategy for hashing: equality.
 */

#define HTEqualStrategyNumber		1
#define HTMaxStrategyNumber		1

/*
 *  When a new operator class is declared, we require that the user supply
 *  us with an amproc procudure for hashing a key of the new type.
 *  Since we only have one such proc in amproc, it's number 1.
 */

#define HASHPROC	1

/* public routines */

extern void hashbuild();
extern InsertIndexResult hashinsert();
extern char *hashgettuple();
extern char *hashbeginscan();
extern void hashrescan();
extern void hashendscan();
extern void hashmarkpos();
extern void hashrestrpos();
extern void hashdelete();

/* private routines */

/* hashinsert.c */
extern InsertIndexResult _hash_doinsert();
extern InsertIndexResult _hash_insertonpg();
extern OffsetIndex _hash_pgaddtup();

/* hashovfl.c */
extern Buffer _hash_addovflpage();
extern OverflowPageAddress _hash_getovfladdr();
extern uint32 _hash_firstfreebit();
extern Buffer _hash_freeovflpage();
extern int32 _hash_initbitmap();
extern void _hash_squeezebucket();

/* hashpage.c */
extern int _hash_metapinit();
extern int _hash_checkmeta();
extern Buffer _hash_getbuf();
extern void _hash_relbuf();
extern void _hash_wrtbuf();
extern void _hash_wrtnorelbuf();
extern Page _hash_chgbufaccess();
extern int _hash_pageinit();
extern int _hash_setpagelock();
extern int _hash_unsetpagelock();
extern void _hash_pagedel();
extern void _hash_expandtable();
extern void _hash_splitpage();

/* hashscan.c */
extern void _hash_regscan();
extern void _hash_dropscan();
extern void _hash_adjscans();
extern void _hash_scandel();
extern bool _hash_scantouched();

/* hashsearch.c */
extern void _hash_search();
extern RetrieveIndexResult _hash_next();
extern RetrieveIndexResult _hash_first();
extern bool _hash_step();

/* hashstrat.c */
extern StrategyNumber _hash_getstrat();
extern bool _hash_invokestrat();

/* hashutil.c */
extern ScanKey _hash_mkscankey();
extern void _hash_freeskey();
extern bool _hash_checkqual();
extern HashItem _hash_formitem();
extern Bucket _hash_call();
extern uint32 _hash_log2();

#endif /* hashIncluded */
