/*-------------------------------------------------------------------------
 *
 * sort_template.h
 *
 *   A template for a sort algorithm that supports varying degrees of
 *   specialization.
 *
 * Copyright (c) 2021-2025, 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
 *
 *   NB: If the comparator function is inlined, some compilers may produce
 *   worse code with the optimized comparison routines in common/int.h than
 *   with code with the following form:
 *
 *       if (a < b)
 *           return -1;
 *       if (a > b)
 *           return 1;
 *       return 0;
 *
 *   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.
 *
 * Refer to the comment at the top of this file for known caveats to consider
 * when writing inlined comparator functions.
 */
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_CHECK_FOR_INTERRUPTS
#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