text: /*-------------------------------------------------------------------------
   *
   * gist_private.h
   *	  private declarations for GiST -- declarations related to the
   *	  internal implementation of GiST, not the public API
   *
   * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   * src/include/access/gist_private.h
   *
   *-------------------------------------------------------------------------
   */
  #ifndef GIST_PRIVATE_H
  #define GIST_PRIVATE_H
  
  #include "access/genam.h"
  #include "access/gist.h"
  #include "access/itup.h"
  #include "access/xlogreader.h"
  #include "fmgr.h"
  #include "lib/pairingheap.h"
  #include "storage/bufmgr.h"
  #include "storage/buffile.h"
  #include "utils/hsearch.h"
  
  /*
   * Maximum number of "halves" a page can be split into in one operation.
   * Typically a split produces 2 halves, but can be more if keys have very
   * different lengths, or when inserting multiple keys in one operation (as
   * when inserting downlinks to an internal node).  There is no theoretical
   * limit on this, but in practice if you get more than a handful page halves
   * in one split, there's something wrong with the opclass implementation.
   * GIST_MAX_SPLIT_PAGES is an arbitrary limit on that, used to size some
   * local arrays used during split.  Note that there is also a limit on the
   * number of buffers that can be held locked at a time, MAX_SIMUL_LWLOCKS,
   * so if you raise this higher than that limit, you'll just get a different
   * error.
   */
  #define GIST_MAX_SPLIT_PAGES		75
  
  /* Buffer lock modes */
  #define GIST_SHARE	BUFFER_LOCK_SHARE
  #define GIST_EXCLUSIVE	BUFFER_LOCK_EXCLUSIVE
  #define GIST_UNLOCK BUFFER_LOCK_UNLOCK
  
  typedef struct
  {
  	BlockNumber prev;
  	uint32		freespace;
  	char		tupledata[FLEXIBLE_ARRAY_MEMBER];
  } GISTNodeBufferPage;
  
  #define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
  /* Returns free space in node buffer page */
  #define PAGE_FREE_SPACE(nbp) (nbp->freespace)
  /* Checks if node buffer page is empty */
  #define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)
  /* Checks if node buffers page don't contain sufficient space for index tuple */
  #define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \
  										MAXALIGN(IndexTupleSize(itup)))
  
  /*
   * GISTSTATE: information needed for any GiST index operation
   *
   * This struct retains call info for the index's opclass-specific support
   * functions (per index column), plus the index's tuple descriptor.
   *
   * scanCxt holds the GISTSTATE itself as well as any data that lives for the
   * lifetime of the index operation.  We pass this to the support functions
   * via fn_mcxt, so that they can store scan-lifespan data in it.  The
   * functions are invoked in tempCxt, which is typically short-lifespan
   * (that is, it's reset after each tuple).  However, tempCxt can be the same
   * as scanCxt if we're not bothering with per-tuple context resets.
   */
  typedef struct GISTSTATE
  {
  	MemoryContext scanCxt;		/* context for scan-lifespan data */
  	MemoryContext tempCxt;		/* short-term context for calling functions */
  
  	TupleDesc	tupdesc;		/* index's tuple descriptor */
  	TupleDesc	fetchTupdesc;	/* tuple descriptor for tuples returned in an
  								 * index-only scan */
  
  	FmgrInfo	consistentFn[INDEX_MAX_KEYS];
  	FmgrInfo	unionFn[INDEX_MAX_KEYS];
  	FmgrInfo	compressFn[INDEX_MAX_KEYS];
  	FmgrInfo	decompressFn[INDEX_MAX_KEYS];
  	FmgrInfo	penaltyFn[INDEX_MAX_KEYS];
  	FmgrInfo	picksplitFn[INDEX_MAX_KEYS];
  	FmgrInfo	equalFn[INDEX_MAX_KEYS];
  	FmgrInfo	distanceFn[INDEX_MAX_KEYS];
  	FmgrInfo	fetchFn[INDEX_MAX_KEYS];
  
  	/* Collations to pass to the support functions */
  	Oid			supportCollation[INDEX_MAX_KEYS];
  } GISTSTATE;
  
  
  /*
   * During a GiST index search, we must maintain a queue of unvisited items,
   * which can be either individual heap tuples or whole index pages.  If it
   * is an ordered search, the unvisited items should be visited in distance
   * order.  Unvisited items at the same distance should be visited in
   * depth-first order, that is heap items first, then lower index pages, then
   * upper index pages; this rule avoids doing extra work during a search that
   * ends early due to LIMIT.
   *
   * To perform an ordered search, we use a pairing heap to manage the
   * distance-order queue.  In a non-ordered search (no order-by operators),
   * we use it to return heap tuples before unvisited index pages, to
   * ensure depth-first order, but all entries are otherwise considered
   * equal.
   */
  
  /* Individual heap tuple to be visited */
  typedef struct GISTSearchHeapItem
  {
  	ItemPointerData heapPtr;
  	bool		recheck;		/* T if quals must be rechecked */
  	bool		recheckDistances;		/* T if distances must be rechecked */
  	IndexTuple	ftup;			/* data fetched back from the index, used in
  								 * index-only scans */
  } GISTSearchHeapItem;
  
  /* Unvisited item, either index page or heap tuple */
  typedef struct GISTSearchItem
  {
  	pairingheap_node phNode;
  	BlockNumber blkno;			/* index page number, or InvalidBlockNumber */
  	union
  	{
  		GistNSN		parentlsn;	/* parent page's LSN, if index page */
  		/* we must store parentlsn to detect whether a split occurred */
  		GISTSearchHeapItem heap;	/* heap info, if heap tuple */
  	}			data;
  
  	/* numberOfOrderBys entries */
  	IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER];
  } GISTSearchItem;
  
  #define GISTSearchItemIsHeap(item)	((item).blkno == InvalidBlockNumber)
  
  #define SizeOfGISTSearchItem(n_distances) \
  	(offsetof(GISTSearchItem, distances) + \
  	 sizeof(IndexOrderByDistance) * (n_distances))
  
  /*
   * GISTScanOpaqueData: private state for a scan of a GiST index
   */
  typedef struct GISTScanOpaqueData
  {
  	GISTSTATE  *giststate;		/* index information, see above */
  	Oid		   *orderByTypes;	/* datatypes of ORDER BY expressions */
  
  	pairingheap *queue;			/* queue of unvisited items */
  	MemoryContext queueCxt;		/* context holding the queue */
  	bool		qual_ok;		/* false if qual can never be satisfied */
  	bool		firstCall;		/* true until first gistgettuple call */
  
  	/* pre-allocated workspace arrays */
  	IndexOrderByDistance *distances;	/* output area for gistindex_keytest */
  
  	/* In a non-ordered search, returnable heap items are stored here: */
  	GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
  	OffsetNumber nPageData;		/* number of valid items in array */
  	OffsetNumber curPageData;	/* next item to return */
  	MemoryContext pageDataCxt;	/* context holding the fetched tuples, for
  								 * index-only scans */
  } GISTScanOpaqueData;
  
  typedef GISTScanOpaqueData *GISTScanOpaque;
  
  
  /* XLog stuff */
  
  #define XLOG_GIST_PAGE_UPDATE		0x00
   /* #define XLOG_GIST_NEW_ROOT			 0x20 */	/* not used anymore */
  #define XLOG_GIST_PAGE_SPLIT		0x30
   /* #define XLOG_GIST_INSERT_COMPLETE	 0x40 */	/* not used anymore */
  #define XLOG_GIST_CREATE_INDEX		0x50
   /* #define XLOG_GIST_PAGE_DELETE		 0x60 */	/* not used anymore */
  
  /*
   * Backup Blk 0: updated page.
   * Backup Blk 1: If this operation completes a page split, by inserting a
   *				 downlink for the split page, the left half of the split
   */
  typedef struct gistxlogPageUpdate
  {
  	/* number of deleted offsets */
  	uint16		ntodelete;
  	uint16		ntoinsert;
  
  	/*
  	 * In payload of blk 0 : 1. todelete OffsetNumbers 2. tuples to insert
  	 */
  } gistxlogPageUpdate;
  
  /*
   * Backup Blk 0: If this operation completes a page split, by inserting a
   *				 downlink for the split page, the left half of the split
   * Backup Blk 1 - npage: split pages (1 is the original page)
   */
  typedef struct gistxlogPageSplit
  {
  	BlockNumber origrlink;		/* rightlink of the page before split */
  	GistNSN		orignsn;		/* NSN of the page before split */
  	bool		origleaf;		/* was splitted page a leaf page? */
  
  	uint16		npage;			/* # of pages in the split */
  	bool		markfollowright;	/* set F_FOLLOW_RIGHT flags */
  
  	/*
  	 * follow: 1. gistxlogPage and array of IndexTupleData per page
  	 */
  } gistxlogPageSplit;
  
  typedef struct gistxlogPage
  {
  	BlockNumber blkno;
  	int			num;			/* number of index tuples following */
  } gistxlogPage;
  
  /* SplitedPageLayout - gistSplit function result */
  typedef struct SplitedPageLayout
  {
  	gistxlogPage block;
  	IndexTupleData *list;
  	int			lenlist;
  	IndexTuple	itup;			/* union key for page */
  	Page		page;			/* to operate */
  	Buffer		buffer;			/* to write after all proceed */
  
  	struct SplitedPageLayout *next;
  } SplitedPageLayout;
  
  /*
   * GISTInsertStack used for locking buffers and transfer arguments during
   * insertion
   */
  typedef struct GISTInsertStack
  {
  	/* current page */
  	BlockNumber blkno;
  	Buffer		buffer;
  	Page		page;
  
  	/*
  	 * log sequence number from page->lsn to recognize page update and compare
  	 * it with page's nsn to recognize page split
  	 */
  	GistNSN		lsn;
  
  	/* offset of the downlink in the parent page, that points to this page */
  	OffsetNumber downlinkoffnum;
  
  	/* pointer to parent */
  	struct GISTInsertStack *parent;
  } GISTInsertStack;
  
  /* Working state and results for multi-column split logic in gistsplit.c */
  typedef struct GistSplitVector
  {
  	GIST_SPLITVEC splitVector;	/* passed to/from user PickSplit method */
  
  	Datum		spl_lattr[INDEX_MAX_KEYS];		/* Union of subkeys in
  												 * splitVector.spl_left */
  	bool		spl_lisnull[INDEX_MAX_KEYS];
  
  	Datum		spl_rattr[INDEX_MAX_KEYS];		/* Union of subkeys in
  												 * splitVector.spl_right */
  	bool		spl_risnull[INDEX_MAX_KEYS];
  
  	bool	   *spl_dontcare;	/* flags tuples which could go to either side
  								 * of the split for zero penalty */
  } GistSplitVector;
  
  typedef struct
  {
  	Relation	r;
  	Size		freespace;		/* free space to be left */
  
  	GISTInsertStack *stack;
  } GISTInsertState;
  
  /* root page of a gist index */
  #define GIST_ROOT_BLKNO				0
  
  /*
   * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on
   * inner pages to finish crash recovery of incomplete page splits. If a crash
   * happened in the middle of a page split, so that the downlink pointers were
   * not yet inserted, crash recovery inserted a special downlink pointer. The
   * semantics of an invalid tuple was that it if you encounter one in a scan,
   * it must always be followed, because we don't know if the tuples on the
   * child page match or not.
   *
   * We no longer create such invalid tuples, we now mark the left-half of such
   * an incomplete split with the F_FOLLOW_RIGHT flag instead, and finish the
   * split properly the next time we need to insert on that page. To retain
   * on-disk compatibility for the sake of pg_upgrade, we still store 0xffff as
   * the offset number of all inner tuples. If we encounter any invalid tuples
   * with 0xfffe during insertion, we throw an error, though scans still handle
   * them. You should only encounter invalid tuples if you pg_upgrade a pre-9.1
   * gist index which already has invalid tuples in it because of a crash. That
   * should be rare, and you are recommended to REINDEX anyway if you have any
   * invalid tuples in an index, so throwing an error is as far as we go with
   * supporting that.
   */
  #define TUPLE_IS_VALID		0xffff
  #define TUPLE_IS_INVALID	0xfffe
  
  #define  GistTupleIsInvalid(itup)	( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
  #define  GistTupleSetValid(itup)	ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
  
  
  
  
  /*
   * A buffer attached to an internal node, used when building an index in
   * buffering mode.
   */
  typedef struct
  {
  	BlockNumber nodeBlocknum;	/* index block # this buffer is for */
  	int32		blocksCount;	/* current # of blocks occupied by buffer */
  
  	BlockNumber pageBlocknum;	/* temporary file block # */
  	GISTNodeBufferPage *pageBuffer;		/* in-memory buffer page */
  
  	/* is this buffer queued for emptying? */
  	bool		queuedForEmptying;
  
  	/* is this a temporary copy, not in the hash table? */
  	bool		isTemp;
  
  	int			level;			/* 0 == leaf */
  } GISTNodeBuffer;
  
  /*
   * Does specified level have buffers? (Beware of multiple evaluation of
   * arguments.)
   */
  #define LEVEL_HAS_BUFFERS(nlevel, gfbb) \
  	((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \
  	 (nlevel) != (gfbb)->rootlevel)
  
  /* Is specified buffer at least half-filled (should be queued for emptying)? */
  #define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \
  	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)
  
  /*
   * Is specified buffer full? Our buffers can actually grow indefinitely,
   * beyond the "maximum" size, so this just means whether the buffer has grown
   * beyond the nominal maximum size.
   */
  #define BUFFER_OVERFLOWED(nodeBuffer, gfbb) \
  	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)
  
  /*
   * Data structure with general information about build buffers.
   */
  typedef struct GISTBuildBuffers
  {
  	/* Persistent memory context for the buffers and metadata. */
  	MemoryContext context;
  
  	BufFile    *pfile;			/* Temporary file to store buffers in */
  	long		nFileBlocks;	/* Current size of the temporary file */
  
  	/*
  	 * resizable array of free blocks.
  	 */
  	long	   *freeBlocks;
  	int			nFreeBlocks;	/* # of currently free blocks in the array */
  	int			freeBlocksLen;	/* current allocated length of the array */
  
  	/* Hash for buffers by block number */
  	HTAB	   *nodeBuffersTab;
  
  	/* List of buffers scheduled for emptying */
  	List	   *bufferEmptyingQueue;
  
  	/*
  	 * Parameters to the buffering build algorithm. levelStep determines which
  	 * levels in the tree have buffers, and pagesPerBuffer determines how
  	 * large each buffer is.
  	 */
  	int			levelStep;
  	int			pagesPerBuffer;
  
  	/* Array of lists of buffers on each level, for final emptying */
  	List	  **buffersOnLevels;
  	int			buffersOnLevelsLen;
  
  	/*
  	 * Dynamically-sized array of buffers that currently have their last page
  	 * loaded in main memory.
  	 */
  	GISTNodeBuffer **loadedBuffers;
  	int			loadedBuffersCount;		/* # of entries in loadedBuffers */
  	int			loadedBuffersLen;		/* allocated size of loadedBuffers */
  
  	/* Level of the current root node (= height of the index tree - 1) */
  	int			rootlevel;
  } GISTBuildBuffers;
  
  /*
   * Storage type for GiST's reloptions
   */
  typedef struct GiSTOptions
  {
  	int32		vl_len_;		/* varlena header (do not touch directly!) */
  	int			fillfactor;		/* page fill factor in percent (0..100) */
  	int			bufferingModeOffset;	/* use buffering build? */
  } GiSTOptions;
  
  /* gist.c */
  extern Datum gistbuildempty(PG_FUNCTION_ARGS);
  extern Datum gistinsert(PG_FUNCTION_ARGS);
  extern Datum gistcanreturn(PG_FUNCTION_ARGS);
  extern MemoryContext createTempGistContext(void);
  extern GISTSTATE *initGISTstate(Relation index);
  extern void freeGISTstate(GISTSTATE *giststate);
  extern void gistdoinsert(Relation r,
  			 IndexTuple itup,
  			 Size freespace,
  			 GISTSTATE *GISTstate);
  
  /* A List of these is returned from gistplacetopage() in *splitinfo */
  typedef struct
  {
  	Buffer		buf;			/* the split page "half" */
  	IndexTuple	downlink;		/* downlink for this half. */
  } GISTPageSplitInfo;
  
  extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
  				Buffer buffer,
  				IndexTuple *itup, int ntup,
  				OffsetNumber oldoffnum, BlockNumber *newblkno,
  				Buffer leftchildbuf,
  				List **splitinfo,
  				bool markleftchild);
  
  extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
  		  int len, GISTSTATE *giststate);
  
  /* gistxlog.c */
  extern void gist_redo(XLogReaderState *record);
  extern void gist_desc(StringInfo buf, XLogReaderState *record);
  extern const char *gist_identify(uint8 info);
  extern void gist_xlog_startup(void);
  extern void gist_xlog_cleanup(void);
  
  extern XLogRecPtr gistXLogUpdate(RelFileNode node, Buffer buffer,
  			   OffsetNumber *todelete, int ntodelete,
  			   IndexTuple *itup, int ntup,
  			   Buffer leftchild);
  
  extern XLogRecPtr gistXLogSplit(RelFileNode node,
  			  BlockNumber blkno, bool page_is_leaf,
  			  SplitedPageLayout *dist,
  			  BlockNumber origrlink, GistNSN oldnsn,
  			  Buffer leftchild, bool markfollowright);
  
  /* gistget.c */
  extern Datum gistgettuple(PG_FUNCTION_ARGS);
  extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
  
  /* gistutil.c */
  
  #define GiSTPageSize   \
  	( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
  
  #define GIST_MIN_FILLFACTOR			10
  #define GIST_DEFAULT_FILLFACTOR		90
  
  extern Datum gistoptions(PG_FUNCTION_ARGS);
  extern bool gistfitpage(IndexTuple *itvec, int len);
  extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
  extern void gistcheckpage(Relation rel, Buffer buf);
  extern Buffer gistNewBuffer(Relation r);
  extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
  			   OffsetNumber off);
  extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
  extern IndexTuple *gistjoinvector(
  			   IndexTuple *itvec, int *len,
  			   IndexTuple *additvec, int addlen);
  extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
  
  extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
  		  int len, GISTSTATE *giststate);
  extern IndexTuple gistgetadjusted(Relation r,
  				IndexTuple oldtup,
  				IndexTuple addtup,
  				GISTSTATE *giststate);
  extern IndexTuple gistFormTuple(GISTSTATE *giststate,
  			  Relation r, Datum *attdata, bool *isnull, bool isleaf);
  
  extern OffsetNumber gistchoose(Relation r, Page p,
  		   IndexTuple it,
  		   GISTSTATE *giststate);
  
  extern void GISTInitBuffer(Buffer b, uint32 f);
  extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
  			   Datum k, Relation r, Page pg, OffsetNumber o,
  			   bool l, bool isNull);
  
  extern float gistpenalty(GISTSTATE *giststate, int attno,
  			GISTENTRY *key1, bool isNull1,
  			GISTENTRY *key2, bool isNull2);
  extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
  				   Datum *attr, bool *isnull);
  extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
  extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
  				  OffsetNumber o, GISTENTRY *attdata, bool *isnull);
  extern IndexTuple gistFetchTuple(GISTSTATE *giststate, Relation r,
  			   IndexTuple tuple);
  extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
  				 GISTENTRY *entry1, bool isnull1,
  				 GISTENTRY *entry2, bool isnull2,
  				 Datum *dst, bool *dstisnull);
  
  extern XLogRecPtr gistGetFakeLSN(Relation rel);
  
  /* gistvacuum.c */
  extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
  extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
  
  /* gistsplit.c */
  extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
  			   int len, GISTSTATE *giststate,
  			   GistSplitVector *v,
  			   int attno);
  
  /* gistbuild.c */
  extern Datum gistbuild(PG_FUNCTION_ARGS);
  extern void gistValidateBufferingOption(char *value);
  
  /* gistbuildbuffers.c */
  extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,
  					 int maxLevel);
  extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb,
  				  GISTSTATE *giststate,
  				  BlockNumber blkno, int level);
  extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb,
  						 GISTNodeBuffer *nodeBuffer, IndexTuple item);
  extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb,
  						  GISTNodeBuffer *nodeBuffer, IndexTuple *item);
  extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb);
  extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,
  								GISTSTATE *giststate, Relation r,
  								int level, Buffer buffer,
  								List *splitinfo);
  extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);
  
  #endif   /* GIST_PRIVATE_H */
  