src/include/lib/sort_template.h - cloudberry - Git at Google

 /*-------------------------------------------------------------------------
  *
  * sort_template.h
  *
  *	  A template for a sort algorithm that supports varying degrees of
  *	  specialization.
  *
  * Copyright (c) 2021, PostgreSQL Global Development Group
  * Portions Copyright (c) 1992-1994, Regents of the University of California
  *
  * Usage notes:
  *
  *	  To generate functions specialized for a type, the following parameter
  *	  macros should be #define'd before this file is included.
  *
  *	  - ST_SORT - the name of a sort function to be generated
  *	  - ST_ELEMENT_TYPE - type of the referenced elements
  *	  - ST_DECLARE - if defined the functions and types are declared
  *	  - ST_DEFINE - if defined the functions and types are defined
  *	  - ST_SCOPE - scope (e.g. extern, static inline) for functions
  *	  - ST_CHECK_FOR_INTERRUPTS - if defined the sort is interruptible
  *
  *	  Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined.  Then
  *	  the generated functions will automatically gain an "element_size"
  *	  parameter.  This allows us to generate a traditional qsort function.
  *
  *	  One of the following macros must be defined, to show how to compare
  *	  elements.  The first two options are arbitrary expressions depending
  *	  on whether an extra pass-through argument is desired, and the third
  *	  option should be defined if the sort function should receive a
  *	  function pointer at runtime.
  *
  *	  - ST_COMPARE(a, b) - a simple comparison expression
  *	  - ST_COMPARE(a, b, arg) - variant that takes an extra argument
  *	  - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
  *
  *	  To say that the comparator and therefore also sort function should
  *	  receive an extra pass-through argument, specify the type of the
  *	  argument.
  *
  *	  - ST_COMPARE_ARG_TYPE - type of extra argument
  *
  *	  The prototype of the generated sort function is:
  *
  *	  void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,
  *				   [size_t element_size,]
  *				   [ST_SORT_compare_function compare,]
  *				   [ST_COMPARE_ARG_TYPE *arg]);
  *
  *	  ST_SORT_compare_function is a function pointer of the following type:
  *
  *	  int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b,
  *			  [ST_COMPARE_ARG_TYPE *arg])
  *
  * HISTORY
  *
  *	  Modifications from vanilla NetBSD source:
  *	  - Add do ... while() macro fix
  *	  - Remove __inline, _DIAGASSERTs, __P
  *	  - Remove ill-considered "swap_cnt" switch to insertion sort, in favor
  *		of a simple check for presorted input.
  *	  - Take care to recurse on the smaller partition, to bound stack usage
  *	  - Convert into a header that can generate specialized functions
  *
  * IDENTIFICATION
  *		src/include/lib/sort_template.h
  *
  *-------------------------------------------------------------------------
  */

 /*	  $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */

 /*-
  * Copyright (c) 1992, 1993
  *	  The Regents of the University of California.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *	  notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *	  notice, this list of conditions and the following disclaimer in the
  *	  documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the University nor the names of its contributors
  *	  may be used to endorse or promote products derived from this software
  *	  without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */

 /*
  * Qsort routine based on J. L. Bentley and M. D. McIlroy,
  * "Engineering a sort function",
  * Software--Practice and Experience 23 (1993) 1249-1265.
  *
  * We have modified their original by adding a check for already-sorted
  * input, which seems to be a win per discussions on pgsql-hackers around
  * 2006-03-21.
  *
  * Also, we recurse on the smaller partition and iterate on the larger one,
  * which ensures we cannot recurse more than log(N) levels (since the
  * partition recursed to is surely no more than half of the input).  Bentley
  * and McIlroy explicitly rejected doing this on the grounds that it's "not
  * worth the effort", but we have seen crashes in the field due to stack
  * overrun, so that judgment seems wrong.
  */

 #define ST_MAKE_PREFIX(a) CppConcat(a,_)
 #define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
 #define ST_MAKE_NAME_(a,b) CppConcat(a,b)

 /*
  * If the element type is void, we'll also need an element_size argument
  * because we don't know the size.
  */
 #ifdef ST_ELEMENT_TYPE_VOID
 #define ST_ELEMENT_TYPE void
 #define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
 #define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
 #else
 #define ST_SORT_PROTO_ELEMENT_SIZE
 #define ST_SORT_INVOKE_ELEMENT_SIZE
 #endif

 /*
  * If the user wants to be able to pass in compare functions at runtime,
  * we'll need to make that an argument of the sort and med3 functions.
  */
 #ifdef ST_COMPARE_RUNTIME_POINTER
 /*
  * The type of the comparator function pointer that ST_SORT will take, unless
  * you've already declared a type name manually and want to use that instead of
  * having a new one defined.
  */
 #ifndef ST_COMPARATOR_TYPE_NAME
 #define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
 #endif
 #define ST_COMPARE compare
 #ifndef ST_COMPARE_ARG_TYPE
 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
 #define ST_SORT_INVOKE_COMPARE , compare
 #else
 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
 #define ST_SORT_INVOKE_COMPARE , compare
 #endif
 #else
 #define ST_SORT_PROTO_COMPARE
 #define ST_SORT_INVOKE_COMPARE
 #endif

 /*
  * If the user wants to use a compare function or expression that takes an
  * extra argument, we'll need to make that an argument of the sort, compare and
  * med3 functions.
  */
 #ifdef ST_COMPARE_ARG_TYPE
 #define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
 #define ST_SORT_INVOKE_ARG , arg
 #else
 #define ST_SORT_PROTO_ARG
 #define ST_SORT_INVOKE_ARG
 #endif

 #ifdef ST_DECLARE

 #ifdef ST_COMPARE_RUNTIME_POINTER
 typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,
 										const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
 #endif

 /* Declare the sort function.  Note optional arguments at end. */
 ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
 					  ST_SORT_PROTO_ELEMENT_SIZE
 					  ST_SORT_PROTO_COMPARE
 					  ST_SORT_PROTO_ARG);

 #endif

 #ifdef ST_DEFINE

 /* sort private helper functions */
 #define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
 #define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
 #define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)

 /* Users expecting to run very large sorts may need them to be interruptible. */
 #ifdef ST_CHECK_FOR_INTERRUPTS
 #define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
 #else
 #define DO_CHECK_FOR_INTERRUPTS()
 #endif

 /*
  * Create wrapper macros that know how to invoke compare, med3 and sort with
  * the right arguments.
  */
 #ifdef ST_COMPARE_RUNTIME_POINTER
 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
 #elif defined(ST_COMPARE_ARG_TYPE)
 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
 #else
 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
 #endif
 #define DO_MED3(a_, b_, c_)												\
 	ST_MED3((a_), (b_), (c_)											\
 			ST_SORT_INVOKE_COMPARE										\
 			ST_SORT_INVOKE_ARG)
 #define DO_SORT(a_, n_)													\
 	ST_SORT((a_), (n_)													\
 			ST_SORT_INVOKE_ELEMENT_SIZE									\
 			ST_SORT_INVOKE_COMPARE										\
 			ST_SORT_INVOKE_ARG)

 /*
  * If we're working with void pointers, we'll use pointer arithmetic based on
  * uint8, and use the runtime element_size to step through the array and swap
  * elements.  Otherwise we'll work with ST_ELEMENT_TYPE.
  */
 #ifndef ST_ELEMENT_TYPE_VOID
 #define ST_POINTER_TYPE ST_ELEMENT_TYPE
 #define ST_POINTER_STEP 1
 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
 #define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
 #else
 #define ST_POINTER_TYPE uint8
 #define ST_POINTER_STEP element_size
 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
 #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
 #endif

 /*
  * Find the median of three values.  Currently, performance seems to be best
  * if the comparator is inlined here, but the med3 function is not inlined
  * in the qsort function.
  */
 static pg_noinline ST_ELEMENT_TYPE *
 ST_MED3(ST_ELEMENT_TYPE * a,
 		ST_ELEMENT_TYPE * b,
 		ST_ELEMENT_TYPE * c
 		ST_SORT_PROTO_COMPARE
 		ST_SORT_PROTO_ARG)
 {
 	return DO_COMPARE(a, b) < 0 ?
 		(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
 		: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
 }

 static inline void
 ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
 {
 	ST_POINTER_TYPE tmp = *a;

 	*a = *b;
 	*b = tmp;
 }

 static inline void
 ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
 {
 	for (size_t i = 0; i < n; ++i)
 		ST_SWAP(&a[i], &b[i]);
 }

 /*
  * Sort an array.
  */
 ST_SCOPE void
 ST_SORT(ST_ELEMENT_TYPE * data, size_t n
 		ST_SORT_PROTO_ELEMENT_SIZE
 		ST_SORT_PROTO_COMPARE
 		ST_SORT_PROTO_ARG)
 {
 	ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
 			   *pa,
 			   *pb,
 			   *pc,
 			   *pd,
 			   *pl,
 			   *pm,
 			   *pn;
 	size_t		d1,
 				d2;
 	int			r,
 				presorted;

 loop:
 	DO_CHECK_FOR_INTERRUPTS();
 	if (n < 7)
 	{
 		for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
 			 pm += ST_POINTER_STEP)
 			for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
 				 pl -= ST_POINTER_STEP)
 				DO_SWAP(pl, pl - ST_POINTER_STEP);
 		return;
 	}
 	presorted = 1;
 	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
 		 pm += ST_POINTER_STEP)
 	{
 		DO_CHECK_FOR_INTERRUPTS();
 		if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
 		{
 			presorted = 0;
 			break;
 		}
 	}
 	if (presorted)
 		return;
 	pm = a + (n / 2) * ST_POINTER_STEP;
 	if (n > 7)
 	{
 		pl = a;
 		pn = a + (n - 1) * ST_POINTER_STEP;
 		if (n > 40)
 		{
 			size_t		d = (n / 8) * ST_POINTER_STEP;

 			pl = DO_MED3(pl, pl + d, pl + 2 * d);
 			pm = DO_MED3(pm - d, pm, pm + d);
 			pn = DO_MED3(pn - 2 * d, pn - d, pn);
 		}
 		pm = DO_MED3(pl, pm, pn);
 	}
 	DO_SWAP(a, pm);
 	pa = pb = a + ST_POINTER_STEP;
 	pc = pd = a + (n - 1) * ST_POINTER_STEP;
 	for (;;)
 	{
 		while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
 		{
 			if (r == 0)
 			{
 				DO_SWAP(pa, pb);
 				pa += ST_POINTER_STEP;
 			}
 			pb += ST_POINTER_STEP;
 			DO_CHECK_FOR_INTERRUPTS();
 		}
 		while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
 		{
 			if (r == 0)
 			{
 				DO_SWAP(pc, pd);
 				pd -= ST_POINTER_STEP;
 			}
 			pc -= ST_POINTER_STEP;
 			DO_CHECK_FOR_INTERRUPTS();
 		}
 		if (pb > pc)
 			break;
 		DO_SWAP(pb, pc);
 		pb += ST_POINTER_STEP;
 		pc -= ST_POINTER_STEP;
 	}
 	pn = a + n * ST_POINTER_STEP;
 	d1 = Min(pa - a, pb - pa);
 	DO_SWAPN(a, pb - d1, d1);
 	d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
 	DO_SWAPN(pb, pn - d1, d1);
 	d1 = pb - pa;
 	d2 = pd - pc;
 	if (d1 <= d2)
 	{
 		/* Recurse on left partition, then iterate on right partition */
 		if (d1 > ST_POINTER_STEP)
 			DO_SORT(a, d1 / ST_POINTER_STEP);
 		if (d2 > ST_POINTER_STEP)
 		{
 			/* Iterate rather than recurse to save stack space */
 			/* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */
 			a = pn - d2;
 			n = d2 / ST_POINTER_STEP;
 			goto loop;
 		}
 	}
 	else
 	{
 		/* Recurse on right partition, then iterate on left partition */
 		if (d2 > ST_POINTER_STEP)
 			DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
 		if (d1 > ST_POINTER_STEP)
 		{
 			/* Iterate rather than recurse to save stack space */
 			/* DO_SORT(a, d1 / ST_POINTER_STEP) */
 			n = d1 / ST_POINTER_STEP;
 			goto loop;
 		}
 	}
 }
 #endif

 #undef DO_CHECK_FOR_INTERRUPTS
 #undef DO_COMPARE
 #undef DO_MED3
 #undef DO_SORT
 #undef DO_SWAP
 #undef DO_SWAPN
 #undef ST_COMPARATOR_TYPE_NAME
 #undef ST_COMPARE
 #undef ST_COMPARE_ARG_TYPE
 #undef ST_COMPARE_RUNTIME_POINTER
 #undef ST_ELEMENT_TYPE
 #undef ST_ELEMENT_TYPE_VOID
 #undef ST_MAKE_NAME
 #undef ST_MAKE_NAME_
 #undef ST_MAKE_PREFIX
 #undef ST_MED3
 #undef ST_POINTER_STEP
 #undef ST_POINTER_TYPE
 #undef ST_SCOPE
 #undef ST_SORT
 #undef ST_SORT_INVOKE_ARG
 #undef ST_SORT_INVOKE_COMPARE
 #undef ST_SORT_INVOKE_ELEMENT_SIZE
 #undef ST_SORT_PROTO_ARG
 #undef ST_SORT_PROTO_COMPARE
 #undef ST_SORT_PROTO_ELEMENT_SIZE
 #undef ST_SWAP
 #undef ST_SWAPN
	/*-------------------------------------------------------------------------
	*
	* sort_template.h
	*
	* A template for a sort algorithm that supports varying degrees of
	* specialization.
	*
	* Copyright (c) 2021, PostgreSQL Global Development Group
	* Portions Copyright (c) 1992-1994, Regents of the University of California
	*
	* Usage notes:
	*
	* To generate functions specialized for a type, the following parameter
	* macros should be #define'd before this file is included.
	*
	* - ST_SORT - the name of a sort function to be generated
	* - ST_ELEMENT_TYPE - type of the referenced elements
	* - ST_DECLARE - if defined the functions and types are declared
	* - ST_DEFINE - if defined the functions and types are defined
	* - ST_SCOPE - scope (e.g. extern, static inline) for functions
	* - ST_CHECK_FOR_INTERRUPTS - if defined the sort is interruptible
	*
	* Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined. Then
	* the generated functions will automatically gain an "element_size"
	* parameter. This allows us to generate a traditional qsort function.
	*
	* One of the following macros must be defined, to show how to compare
	* elements. The first two options are arbitrary expressions depending
	* on whether an extra pass-through argument is desired, and the third
	* option should be defined if the sort function should receive a
	* function pointer at runtime.
	*
	* - ST_COMPARE(a, b) - a simple comparison expression
	* - ST_COMPARE(a, b, arg) - variant that takes an extra argument
	* - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
	*
	* To say that the comparator and therefore also sort function should
	* receive an extra pass-through argument, specify the type of the
	* argument.
	*
	* - ST_COMPARE_ARG_TYPE - type of extra argument
	*
	* The prototype of the generated sort function is:
	*
	* void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,
	* [size_t element_size,]
	* [ST_SORT_compare_function compare,]
	* [ST_COMPARE_ARG_TYPE *arg]);
	*
	* ST_SORT_compare_function is a function pointer of the following type:
	*
	* int ()(const ST_ELEMENT_TYPE a, const ST_ELEMENT_TYPE *b,
	* [ST_COMPARE_ARG_TYPE *arg])
	*
	* HISTORY
	*
	* Modifications from vanilla NetBSD source:
	* - Add do ... while() macro fix
	* - Remove __inline, _DIAGASSERTs, __P
	* - Remove ill-considered "swap_cnt" switch to insertion sort, in favor
	* of a simple check for presorted input.
	* - Take care to recurse on the smaller partition, to bound stack usage
	* - Convert into a header that can generate specialized functions
	*
	* IDENTIFICATION
	* src/include/lib/sort_template.h
	*
	*-------------------------------------------------------------------------
	*/

	/* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */

	/*-
	* Copyright (c) 1992, 1993
	* The Regents of the University of California. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of the University nor the names of its contributors
	* may be used to endorse or promote products derived from this software
	* without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	* SUCH DAMAGE.
	*/

	/*
	* Qsort routine based on J. L. Bentley and M. D. McIlroy,
	* "Engineering a sort function",
	* Software--Practice and Experience 23 (1993) 1249-1265.
	*
	* We have modified their original by adding a check for already-sorted
	* input, which seems to be a win per discussions on pgsql-hackers around
	* 2006-03-21.
	*
	* Also, we recurse on the smaller partition and iterate on the larger one,
	* which ensures we cannot recurse more than log(N) levels (since the
	* partition recursed to is surely no more than half of the input). Bentley
	* and McIlroy explicitly rejected doing this on the grounds that it's "not
	* worth the effort", but we have seen crashes in the field due to stack
	* overrun, so that judgment seems wrong.
	*/

	#define ST_MAKE_PREFIX(a) CppConcat(a,_)
	#define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
	#define ST_MAKE_NAME_(a,b) CppConcat(a,b)

	/*
	* If the element type is void, we'll also need an element_size argument
	* because we don't know the size.
	*/
	#ifdef ST_ELEMENT_TYPE_VOID
	#define ST_ELEMENT_TYPE void
	#define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
	#define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
	#else
	#define ST_SORT_PROTO_ELEMENT_SIZE
	#define ST_SORT_INVOKE_ELEMENT_SIZE
	#endif

	/*
	* If the user wants to be able to pass in compare functions at runtime,
	* we'll need to make that an argument of the sort and med3 functions.
	*/
	#ifdef ST_COMPARE_RUNTIME_POINTER
	/*
	* The type of the comparator function pointer that ST_SORT will take, unless
	* you've already declared a type name manually and want to use that instead of
	* having a new one defined.
	*/
	#ifndef ST_COMPARATOR_TYPE_NAME
	#define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
	#endif
	#define ST_COMPARE compare
	#ifndef ST_COMPARE_ARG_TYPE
	#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
	#define ST_SORT_INVOKE_COMPARE , compare
	#else
	#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
	#define ST_SORT_INVOKE_COMPARE , compare
	#endif
	#else
	#define ST_SORT_PROTO_COMPARE
	#define ST_SORT_INVOKE_COMPARE
	#endif

	/*
	* If the user wants to use a compare function or expression that takes an
	* extra argument, we'll need to make that an argument of the sort, compare and
	* med3 functions.
	*/
	#ifdef ST_COMPARE_ARG_TYPE
	#define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
	#define ST_SORT_INVOKE_ARG , arg
	#else
	#define ST_SORT_PROTO_ARG
	#define ST_SORT_INVOKE_ARG
	#endif

	#ifdef ST_DECLARE

	#ifdef ST_COMPARE_RUNTIME_POINTER
	typedef int (ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE ,
	const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
	#endif

	/* Declare the sort function. Note optional arguments at end. */
	ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
	ST_SORT_PROTO_ELEMENT_SIZE
	ST_SORT_PROTO_COMPARE
	ST_SORT_PROTO_ARG);

	#endif

	#ifdef ST_DEFINE

	/* sort private helper functions */
	#define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
	#define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
	#define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)

	/* Users expecting to run very large sorts may need them to be interruptible. */
	#ifdef ST_CHECK_FOR_INTERRUPTS
	#define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
	#else
	#define DO_CHECK_FOR_INTERRUPTS()
	#endif

	/*
	* Create wrapper macros that know how to invoke compare, med3 and sort with
	* the right arguments.
	*/
	#ifdef ST_COMPARE_RUNTIME_POINTER
	#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
	#elif defined(ST_COMPARE_ARG_TYPE)
	#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
	#else
	#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
	#endif
	#define DO_MED3(a_, b_, c_) \
	ST_MED3((a_), (b_), (c_) \
	ST_SORT_INVOKE_COMPARE \
	ST_SORT_INVOKE_ARG)
	#define DO_SORT(a_, n_) \
	ST_SORT((a_), (n_) \
	ST_SORT_INVOKE_ELEMENT_SIZE \
	ST_SORT_INVOKE_COMPARE \
	ST_SORT_INVOKE_ARG)

	/*
	* If we're working with void pointers, we'll use pointer arithmetic based on
	* uint8, and use the runtime element_size to step through the array and swap
	* elements. Otherwise we'll work with ST_ELEMENT_TYPE.
	*/
	#ifndef ST_ELEMENT_TYPE_VOID
	#define ST_POINTER_TYPE ST_ELEMENT_TYPE
	#define ST_POINTER_STEP 1
	#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
	#define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
	#else
	#define ST_POINTER_TYPE uint8
	#define ST_POINTER_STEP element_size
	#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
	#define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
	#endif

	/*
	* Find the median of three values. Currently, performance seems to be best
	* if the comparator is inlined here, but the med3 function is not inlined
	* in the qsort function.
	*/
	static pg_noinline ST_ELEMENT_TYPE *
	ST_MED3(ST_ELEMENT_TYPE * a,
	ST_ELEMENT_TYPE * b,
	ST_ELEMENT_TYPE * c
	ST_SORT_PROTO_COMPARE
	ST_SORT_PROTO_ARG)
	{
	return DO_COMPARE(a, b) < 0 ?
	(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
	: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
	}

	static inline void
	ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
	{
	ST_POINTER_TYPE tmp = *a;

	a = b;
	*b = tmp;
	}

	static inline void
	ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
	{
	for (size_t i = 0; i < n; ++i)
	ST_SWAP(&a[i], &b[i]);
	}

	/*
	* Sort an array.
	*/
	ST_SCOPE void
	ST_SORT(ST_ELEMENT_TYPE * data, size_t n
	ST_SORT_PROTO_ELEMENT_SIZE
	ST_SORT_PROTO_COMPARE
	ST_SORT_PROTO_ARG)
	{
	ST_POINTER_TYPE a = (ST_POINTER_TYPE ) data,
	*pa,
	*pb,
	*pc,
	*pd,
	*pl,
	*pm,
	*pn;
	size_t d1,
	d2;
	int r,
	presorted;

	loop:
	DO_CHECK_FOR_INTERRUPTS();
	if (n < 7)
	{
	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
	pm += ST_POINTER_STEP)
	for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
	pl -= ST_POINTER_STEP)
	DO_SWAP(pl, pl - ST_POINTER_STEP);
	return;
	}
	presorted = 1;
	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
	pm += ST_POINTER_STEP)
	{
	DO_CHECK_FOR_INTERRUPTS();
	if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
	{
	presorted = 0;
	break;
	}
	}
	if (presorted)
	return;
	pm = a + (n / 2) * ST_POINTER_STEP;
	if (n > 7)
	{
	pl = a;
	pn = a + (n - 1) * ST_POINTER_STEP;
	if (n > 40)
	{
	size_t d = (n / 8) * ST_POINTER_STEP;

	pl = DO_MED3(pl, pl + d, pl + 2 * d);
	pm = DO_MED3(pm - d, pm, pm + d);
	pn = DO_MED3(pn - 2 * d, pn - d, pn);
	}
	pm = DO_MED3(pl, pm, pn);
	}
	DO_SWAP(a, pm);
	pa = pb = a + ST_POINTER_STEP;
	pc = pd = a + (n - 1) * ST_POINTER_STEP;
	for (;;)
	{
	while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
	{
	if (r == 0)
	{
	DO_SWAP(pa, pb);
	pa += ST_POINTER_STEP;
	}
	pb += ST_POINTER_STEP;
	DO_CHECK_FOR_INTERRUPTS();
	}
	while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
	{
	if (r == 0)
	{
	DO_SWAP(pc, pd);
	pd -= ST_POINTER_STEP;
	}
	pc -= ST_POINTER_STEP;
	DO_CHECK_FOR_INTERRUPTS();
	}
	if (pb > pc)
	break;
	DO_SWAP(pb, pc);
	pb += ST_POINTER_STEP;
	pc -= ST_POINTER_STEP;
	}
	pn = a + n * ST_POINTER_STEP;
	d1 = Min(pa - a, pb - pa);
	DO_SWAPN(a, pb - d1, d1);
	d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
	DO_SWAPN(pb, pn - d1, d1);
	d1 = pb - pa;
	d2 = pd - pc;
	if (d1 <= d2)
	{
	/* Recurse on left partition, then iterate on right partition */
	if (d1 > ST_POINTER_STEP)
	DO_SORT(a, d1 / ST_POINTER_STEP);
	if (d2 > ST_POINTER_STEP)
	{
	/* Iterate rather than recurse to save stack space */
	/* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */
	a = pn - d2;
	n = d2 / ST_POINTER_STEP;
	goto loop;
	}
	}
	else
	{
	/* Recurse on right partition, then iterate on left partition */
	if (d2 > ST_POINTER_STEP)
	DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
	if (d1 > ST_POINTER_STEP)
	{
	/* Iterate rather than recurse to save stack space */
	/* DO_SORT(a, d1 / ST_POINTER_STEP) */
	n = d1 / ST_POINTER_STEP;
	goto loop;
	}
	}
	}
	#endif

	#undef DO_CHECK_FOR_INTERRUPTS
	#undef DO_COMPARE
	#undef DO_MED3
	#undef DO_SORT
	#undef DO_SWAP
	#undef DO_SWAPN
	#undef ST_COMPARATOR_TYPE_NAME
	#undef ST_COMPARE
	#undef ST_COMPARE_ARG_TYPE
	#undef ST_COMPARE_RUNTIME_POINTER
	#undef ST_ELEMENT_TYPE
	#undef ST_ELEMENT_TYPE_VOID
	#undef ST_MAKE_NAME
	#undef ST_MAKE_NAME_
	#undef ST_MAKE_PREFIX
	#undef ST_MED3
	#undef ST_POINTER_STEP
	#undef ST_POINTER_TYPE
	#undef ST_SCOPE
	#undef ST_SORT
	#undef ST_SORT_INVOKE_ARG
	#undef ST_SORT_INVOKE_COMPARE
	#undef ST_SORT_INVOKE_ELEMENT_SIZE
	#undef ST_SORT_PROTO_ARG
	#undef ST_SORT_PROTO_COMPARE
	#undef ST_SORT_PROTO_ELEMENT_SIZE
	#undef ST_SWAP
	#undef ST_SWAPN