text: /*-------------------------------------------------------------------------
   *
   * sortsupport.h
   *	  Framework for accelerated sorting.
   *
   * Traditionally, PostgreSQL has implemented sorting by repeatedly invoking
   * an SQL-callable comparison function "cmp(x, y) returns int" on pairs of
   * values to be compared, where the comparison function is the BTORDER_PROC
   * pg_amproc support function of the appropriate btree index opclass.
   *
   * This file defines alternative APIs that allow sorting to be performed with
   * reduced overhead.  To support lower-overhead sorting, a btree opclass may
   * provide a BTSORTSUPPORT_PROC pg_amproc entry, which must take a single
   * argument of type internal and return void.  The argument is actually a
   * pointer to a SortSupportData struct, which is defined below.
   *
   * If provided, the BTSORTSUPPORT function will be called during sort setup,
   * and it must initialize the provided struct with pointers to function(s)
   * that can be called to perform sorting.  This API is defined to allow
   * multiple acceleration mechanisms to be supported, but no opclass is
   * required to provide all of them.  The BTSORTSUPPORT function should
   * simply not set any function pointers for mechanisms it doesn't support.
   * Opclasses that provide BTSORTSUPPORT and don't provide a comparator
   * function will have a shim set up by sort support automatically.  However,
   * opclasses that support the optional additional abbreviated key capability
   * must always provide an authoritative comparator used to tie-break
   * inconclusive abbreviated comparisons and also used  when aborting
   * abbreviation.  Furthermore, a converter and abort/costing function must be
   * provided.
   *
   * All sort support functions will be passed the address of the
   * SortSupportData struct when called, so they can use it to store
   * additional private data as needed.  In particular, for collation-aware
   * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT
   * and is available to all support functions.  Additional opclass-dependent
   * data can be stored using the ssup_extra field.  Any such data
   * should be allocated in the ssup_cxt memory context.
   *
   * Note: since pg_amproc functions are indexed by (lefttype, righttype)
   * it is possible to associate a BTSORTSUPPORT function with a cross-type
   * comparison.  This could sensibly be used to provide a fast comparator
   * function for such cases, but probably not any other acceleration method.
   *
   *
   * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   * src/include/utils/sortsupport.h
   *
   *-------------------------------------------------------------------------
   */
  #ifndef SORTSUPPORT_H
  #define SORTSUPPORT_H
  
  #include "access/attnum.h"
  #include "utils/relcache.h"
  
  typedef struct SortSupportData *SortSupport;
  
  typedef struct SortSupportData
  {
  	/*
  	 * These fields are initialized before calling the BTSORTSUPPORT function
  	 * and should not be changed later.
  	 */
  	MemoryContext ssup_cxt;		/* Context containing sort info */
  	Oid			ssup_collation; /* Collation to use, or InvalidOid */
  
  	/*
  	 * Additional sorting parameters; but unlike ssup_collation, these can be
  	 * changed after BTSORTSUPPORT is called, so don't use them in selecting
  	 * sort support functions.
  	 */
  	bool		ssup_reverse;	/* descending-order sort? */
  	bool		ssup_nulls_first;		/* sort nulls first? */
  
  	/*
  	 * These fields are workspace for callers, and should not be touched by
  	 * opclass-specific functions.
  	 */
  	AttrNumber	ssup_attno;		/* column number to sort */
  
  	/*
  	 * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
  	 * not touched subsequently by callers.
  	 */
  	void	   *ssup_extra;		/* Workspace for opclass functions */
  
  	/*
  	 * Function pointers are zeroed before calling the BTSORTSUPPORT function,
  	 * and must be set by it for any acceleration methods it wants to supply.
  	 * The comparator pointer must be set, others are optional.
  	 */
  
  	/*
  	 * Comparator function has the same API as the traditional btree
  	 * comparison function, ie, return <0, 0, or >0 according as x is less
  	 * than, equal to, or greater than y.  Note that x and y are guaranteed
  	 * not null, and there is no way to return null either.  Do not return
  	 * INT_MIN, as callers are allowed to negate the result before using it.
  	 *
  	 * This may be either the authoritative comparator, or the abbreviated
  	 * comparator.  Core code may switch this over the initial preference of an
  	 * opclass support function despite originally indicating abbreviation was
  	 * applicable, by assigning the authoritative comparator back.
  	 */
  	int			(*comparator) (Datum x, Datum y, SortSupport ssup);
  
  	/*
  	 * "Abbreviated key" infrastructure follows.
  	 *
  	 * All callbacks must be set by sortsupport opclasses that make use of this
  	 * optional additional infrastructure (unless for whatever reasons the
  	 * opclass doesn't proceed with abbreviation, in which case
  	 * abbrev_converter must not be set).
  	 *
  	 * This allows opclass authors to supply a conversion routine, used to
  	 * create an alternative representation of the underlying type (an
  	 * "abbreviated key").  Typically, this representation is an ad-hoc,
  	 * pass-by-value Datum format that only the opclass has knowledge of.  An
  	 * alternative comparator, used only with this alternative representation
  	 * must also be provided (which is assigned to "comparator").  This
  	 * representation is a simple approximation of the original Datum.  It must
  	 * be possible to compare datums of this representation with each other
  	 * using the supplied alternative comparator, and have any non-zero return
  	 * value be a reliable proxy for what a proper comparison would indicate.
  	 * Returning zero from the alternative comparator does not indicate
  	 * equality, as with a conventional support routine 1, though -- it
  	 * indicates that it wasn't possible to determine how the two abbreviated
  	 * values compared.  A proper comparison, using "abbrev_full_comparator"/
  	 * ApplySortAbbrevFullComparator() is therefore required.  In many cases
  	 * this results in most or all comparisons only using the cheap alternative
  	 * comparison func, which is typically implemented as code that compiles to
  	 * just a few CPU instructions.  CPU cache miss penalties are expensive; to
  	 * get good overall performance, sort infrastructure must heavily weigh
  	 * cache performance.
  	 *
  	 * Opclass authors must consider the final cardinality of abbreviated keys
  	 * when devising an encoding scheme.  It's possible for a strategy to work
  	 * better than an alternative strategy with one usage pattern, while the
  	 * reverse might be true for another usage pattern.  All of these factors
  	 * must be considered.
  	 */
  
  	/*
  	 * "abbreviate" concerns whether or not the abbreviated key optimization is
  	 * applicable in principle (that is, the sortsupport routine needs to know
  	 * if its dealing with a key where an abbreviated representation can
  	 * usefully be packed together.  Conventionally, this is the leading
  	 * attribute key).  Note, however, that in order to determine that
  	 * abbreviation is not in play, the core code always checks whether or not
  	 * the opclass has set abbrev_converter.  This is a one way, one time
  	 * message to the opclass.
  	 */
  	bool			abbreviate;
  
  	/*
  	 * Converter to abbreviated format, from original representation.  Core
  	 * code uses this callback to convert from a pass-by-reference "original"
  	 * Datum to a pass-by-value abbreviated key Datum.  Note that original is
  	 * guaranteed NOT NULL, because it doesn't make sense to factor NULLness
  	 * into ad-hoc cost model.
  	 *
  	 * abbrev_converter is tested to see if abbreviation is in play.  Core code
  	 * may set it to NULL to indicate abbreviation should not be used (which is
  	 * something sortsupport routines need not concern themselves with).
  	 * However, sortsupport routines must not set it when it is immediately
  	 * established that abbreviation should not proceed (e.g., for !abbreviate
  	 * calls, or due to platform-specific impediments to using abbreviation).
  	 */
  	Datum			(*abbrev_converter) (Datum original, SortSupport ssup);
  
  	/*
  	 * abbrev_abort callback allows clients to verify that the current strategy
  	 * is working out, using a sortsupport routine defined ad-hoc cost model.
  	 * If there is a lot of duplicate abbreviated keys in practice, it's useful
  	 * to be able to abandon the strategy before paying too high a cost in
  	 * conversion (perhaps certain opclass-specific adaptations are useful
  	 * too).
  	 */
  	bool			(*abbrev_abort) (int memtupcount, SortSupport ssup);
  
  	/*
  	 * Full, authoritative comparator for key that an abbreviated
  	 * representation was generated for, used when an abbreviated comparison
  	 * was inconclusive (by calling ApplySortComparatorFull()), or used to
  	 * replace "comparator" when core system ultimately decides against
  	 * abbreviation.
  	 */
  	int			(*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
  } SortSupportData;
  
  
  /*
   * ApplySortComparator should be inlined if possible.  See STATIC_IF_INLINE
   * in c.h.
   */
  #ifndef PG_USE_INLINE
  extern int ApplySortComparator(Datum datum1, bool isNull1,
  					Datum datum2, bool isNull2,
  					SortSupport ssup);
  extern int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
  							Datum datum2, bool isNull2,
  							SortSupport ssup);
  #endif   /* !PG_USE_INLINE */
  #if defined(PG_USE_INLINE) || defined(SORTSUPPORT_INCLUDE_DEFINITIONS)
  /*
   * Apply a sort comparator function and return a 3-way comparison result.
   * This takes care of handling reverse-sort and NULLs-ordering properly.
   */
  STATIC_IF_INLINE int
  ApplySortComparator(Datum datum1, bool isNull1,
  					Datum datum2, bool isNull2,
  					SortSupport ssup)
  {
  	int			compare;
  
  	if (isNull1)
  	{
  		if (isNull2)
  			compare = 0;		/* NULL "=" NULL */
  		else if (ssup->ssup_nulls_first)
  			compare = -1;		/* NULL "<" NOT_NULL */
  		else
  			compare = 1;		/* NULL ">" NOT_NULL */
  	}
  	else if (isNull2)
  	{
  		if (ssup->ssup_nulls_first)
  			compare = 1;		/* NOT_NULL ">" NULL */
  		else
  			compare = -1;		/* NOT_NULL "<" NULL */
  	}
  	else
  	{
  		compare = (*ssup->comparator) (datum1, datum2, ssup);
  		if (ssup->ssup_reverse)
  			compare = -compare;
  	}
  
  	return compare;
  }
  
  /*
   * Apply a sort comparator function and return a 3-way comparison using full,
   * authoritative comparator.  This takes care of handling reverse-sort and
   * NULLs-ordering properly.
   */
  STATIC_IF_INLINE int
  ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
  							  Datum datum2, bool isNull2,
  							  SortSupport ssup)
  {
  	int			compare;
  
  	if (isNull1)
  	{
  		if (isNull2)
  			compare = 0;		/* NULL "=" NULL */
  		else if (ssup->ssup_nulls_first)
  			compare = -1;		/* NULL "<" NOT_NULL */
  		else
  			compare = 1;		/* NULL ">" NOT_NULL */
  	}
  	else if (isNull2)
  	{
  		if (ssup->ssup_nulls_first)
  			compare = 1;		/* NOT_NULL ">" NULL */
  		else
  			compare = -1;		/* NOT_NULL "<" NULL */
  	}
  	else
  	{
  		compare = (*ssup->abbrev_full_comparator) (datum1, datum2, ssup);
  		if (ssup->ssup_reverse)
  			compare = -compare;
  	}
  
  	return compare;
  }
  #endif   /*-- PG_USE_INLINE || SORTSUPPORT_INCLUDE_DEFINITIONS */
  
  /* Other functions in utils/sort/sortsupport.c */
  extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
  extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
  extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
  										   SortSupport ssup);
  
  #endif   /* SORTSUPPORT_H */
  