codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * sort_template.h4 *5 *	  A template for a sort algorithm that supports varying degrees of6 *	  specialization.7 *8 * Copyright (c) 2021-2023, PostgreSQL Global Development Group9 * Portions Copyright (c) 1992-1994, Regents of the University of California10 *11 * Usage notes:12 *13 *	  To generate functions specialized for a type, the following parameter14 *	  macros should be #define'd before this file is included.15 *16 *	  - ST_SORT - the name of a sort function to be generated17 *	  - ST_ELEMENT_TYPE - type of the referenced elements18 *	  - ST_DECLARE - if defined the functions and types are declared19 *	  - ST_DEFINE - if defined the functions and types are defined20 *	  - ST_SCOPE - scope (e.g. extern, static inline) for functions21 *	  - ST_CHECK_FOR_INTERRUPTS - if defined the sort is interruptible22 *23 *	  Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined.  Then24 *	  the generated functions will automatically gain an "element_size"25 *	  parameter.  This allows us to generate a traditional qsort function.26 *27 *	  One of the following macros must be defined, to show how to compare28 *	  elements.  The first two options are arbitrary expressions depending29 *	  on whether an extra pass-through argument is desired, and the third30 *	  option should be defined if the sort function should receive a31 *	  function pointer at runtime.32 *33 *	  - ST_COMPARE(a, b) - a simple comparison expression34 *	  - ST_COMPARE(a, b, arg) - variant that takes an extra argument35 *	  - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer36 *37 *	  To say that the comparator and therefore also sort function should38 *	  receive an extra pass-through argument, specify the type of the39 *	  argument.40 *41 *	  - ST_COMPARE_ARG_TYPE - type of extra argument42 *43 *	  The prototype of the generated sort function is:44 *45 *	  void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,46 *				   [size_t element_size,]47 *				   [ST_SORT_compare_function compare,]48 *				   [ST_COMPARE_ARG_TYPE *arg]);49 *50 *	  ST_SORT_compare_function is a function pointer of the following type:51 *52 *	  int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b,53 *			  [ST_COMPARE_ARG_TYPE *arg])54 *55 * HISTORY56 *57 *	  Modifications from vanilla NetBSD source:58 *	  - Add do ... while() macro fix59 *	  - Remove __inline, _DIAGASSERTs, __P60 *	  - Remove ill-considered "swap_cnt" switch to insertion sort, in favor61 *		of a simple check for presorted input.62 *	  - Take care to recurse on the smaller partition, to bound stack usage63 *	  - Convert into a header that can generate specialized functions64 *65 * IDENTIFICATION66 *		src/include/lib/sort_template.h67 *68 *-------------------------------------------------------------------------69 */70 71/*	  $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */72 73/*-74 * Copyright (c) 1992, 199375 *	  The Regents of the University of California.  All rights reserved.76 *77 * Redistribution and use in source and binary forms, with or without78 * modification, are permitted provided that the following conditions79 * are met:80 * 1. Redistributions of source code must retain the above copyright81 *	  notice, this list of conditions and the following disclaimer.82 * 2. Redistributions in binary form must reproduce the above copyright83 *	  notice, this list of conditions and the following disclaimer in the84 *	  documentation and/or other materials provided with the distribution.85 * 3. Neither the name of the University nor the names of its contributors86 *	  may be used to endorse or promote products derived from this software87 *	  without specific prior written permission.88 *89 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND90 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE91 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE92 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE93 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL94 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS95 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)96 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT97 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY98 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF99 * SUCH DAMAGE.100 */101 102/*103 * Qsort routine based on J. L. Bentley and M. D. McIlroy,104 * "Engineering a sort function",105 * Software--Practice and Experience 23 (1993) 1249-1265.106 *107 * We have modified their original by adding a check for already-sorted108 * input, which seems to be a win per discussions on pgsql-hackers around109 * 2006-03-21.110 *111 * Also, we recurse on the smaller partition and iterate on the larger one,112 * which ensures we cannot recurse more than log(N) levels (since the113 * partition recursed to is surely no more than half of the input).  Bentley114 * and McIlroy explicitly rejected doing this on the grounds that it's "not115 * worth the effort", but we have seen crashes in the field due to stack116 * overrun, so that judgment seems wrong.117 */118 119#define ST_MAKE_PREFIX(a) CppConcat(a,_)120#define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)121#define ST_MAKE_NAME_(a,b) CppConcat(a,b)122 123/*124 * If the element type is void, we'll also need an element_size argument125 * because we don't know the size.126 */127#ifdef ST_ELEMENT_TYPE_VOID128#define ST_ELEMENT_TYPE void129#define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size130#define ST_SORT_INVOKE_ELEMENT_SIZE , element_size131#else132#define ST_SORT_PROTO_ELEMENT_SIZE133#define ST_SORT_INVOKE_ELEMENT_SIZE134#endif135 136/*137 * If the user wants to be able to pass in compare functions at runtime,138 * we'll need to make that an argument of the sort and med3 functions.139 */140#ifdef ST_COMPARE_RUNTIME_POINTER141/*142 * The type of the comparator function pointer that ST_SORT will take, unless143 * you've already declared a type name manually and want to use that instead of144 * having a new one defined.145 */146#ifndef ST_COMPARATOR_TYPE_NAME147#define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)148#endif149#define ST_COMPARE compare150#ifndef ST_COMPARE_ARG_TYPE151#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare152#define ST_SORT_INVOKE_COMPARE , compare153#else154#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare155#define ST_SORT_INVOKE_COMPARE , compare156#endif157#else158#define ST_SORT_PROTO_COMPARE159#define ST_SORT_INVOKE_COMPARE160#endif161 162/*163 * If the user wants to use a compare function or expression that takes an164 * extra argument, we'll need to make that an argument of the sort, compare and165 * med3 functions.166 */167#ifdef ST_COMPARE_ARG_TYPE168#define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg169#define ST_SORT_INVOKE_ARG , arg170#else171#define ST_SORT_PROTO_ARG172#define ST_SORT_INVOKE_ARG173#endif174 175#ifdef ST_DECLARE176 177#ifdef ST_COMPARE_RUNTIME_POINTER178typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,179										const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);180#endif181 182/* Declare the sort function.  Note optional arguments at end. */183ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n184					  ST_SORT_PROTO_ELEMENT_SIZE185					  ST_SORT_PROTO_COMPARE186					  ST_SORT_PROTO_ARG);187 188#endif189 190#ifdef ST_DEFINE191 192/* sort private helper functions */193#define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)194#define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)195#define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)196 197/* Users expecting to run very large sorts may need them to be interruptible. */198#ifdef ST_CHECK_FOR_INTERRUPTS199#define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()200#else201#define DO_CHECK_FOR_INTERRUPTS()202#endif203 204/*205 * Create wrapper macros that know how to invoke compare, med3 and sort with206 * the right arguments.207 */208#ifdef ST_COMPARE_RUNTIME_POINTER209#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)210#elif defined(ST_COMPARE_ARG_TYPE)211#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)212#else213#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))214#endif215#define DO_MED3(a_, b_, c_)												\216	ST_MED3((a_), (b_), (c_)											\217			ST_SORT_INVOKE_COMPARE										\218			ST_SORT_INVOKE_ARG)219#define DO_SORT(a_, n_)													\220	ST_SORT((a_), (n_)													\221			ST_SORT_INVOKE_ELEMENT_SIZE									\222			ST_SORT_INVOKE_COMPARE										\223			ST_SORT_INVOKE_ARG)224 225/*226 * If we're working with void pointers, we'll use pointer arithmetic based on227 * uint8, and use the runtime element_size to step through the array and swap228 * elements.  Otherwise we'll work with ST_ELEMENT_TYPE.229 */230#ifndef ST_ELEMENT_TYPE_VOID231#define ST_POINTER_TYPE ST_ELEMENT_TYPE232#define ST_POINTER_STEP 1233#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))234#define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))235#else236#define ST_POINTER_TYPE uint8237#define ST_POINTER_STEP element_size238#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))239#define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)240#endif241 242/*243 * Find the median of three values.  Currently, performance seems to be best244 * if the comparator is inlined here, but the med3 function is not inlined245 * in the qsort function.246 */247static pg_noinline ST_ELEMENT_TYPE *248ST_MED3(ST_ELEMENT_TYPE * a,249		ST_ELEMENT_TYPE * b,250		ST_ELEMENT_TYPE * c251		ST_SORT_PROTO_COMPARE252		ST_SORT_PROTO_ARG)253{254	return DO_COMPARE(a, b) < 0 ?255		(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))256		: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));257}258 259static inline void260ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)261{262	ST_POINTER_TYPE tmp = *a;263 264	*a = *b;265	*b = tmp;266}267 268static inline void269ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)270{271	for (size_t i = 0; i < n; ++i)272		ST_SWAP(&a[i], &b[i]);273}274 275/*276 * Sort an array.277 */278ST_SCOPE void279ST_SORT(ST_ELEMENT_TYPE * data, size_t n280		ST_SORT_PROTO_ELEMENT_SIZE281		ST_SORT_PROTO_COMPARE282		ST_SORT_PROTO_ARG)283{284	ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,285			   *pa,286			   *pb,287			   *pc,288			   *pd,289			   *pl,290			   *pm,291			   *pn;292	size_t		d1,293				d2;294	int			r,295				presorted;296 297loop:298	DO_CHECK_FOR_INTERRUPTS();299	if (n < 7)300	{301		for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;302			 pm += ST_POINTER_STEP)303			for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;304				 pl -= ST_POINTER_STEP)305				DO_SWAP(pl, pl - ST_POINTER_STEP);306		return;307	}308	presorted = 1;309	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;310		 pm += ST_POINTER_STEP)311	{312		DO_CHECK_FOR_INTERRUPTS();313		if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)314		{315			presorted = 0;316			break;317		}318	}319	if (presorted)320		return;321	pm = a + (n / 2) * ST_POINTER_STEP;322	if (n > 7)323	{324		pl = a;325		pn = a + (n - 1) * ST_POINTER_STEP;326		if (n > 40)327		{328			size_t		d = (n / 8) * ST_POINTER_STEP;329 330			pl = DO_MED3(pl, pl + d, pl + 2 * d);331			pm = DO_MED3(pm - d, pm, pm + d);332			pn = DO_MED3(pn - 2 * d, pn - d, pn);333		}334		pm = DO_MED3(pl, pm, pn);335	}336	DO_SWAP(a, pm);337	pa = pb = a + ST_POINTER_STEP;338	pc = pd = a + (n - 1) * ST_POINTER_STEP;339	for (;;)340	{341		while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)342		{343			if (r == 0)344			{345				DO_SWAP(pa, pb);346				pa += ST_POINTER_STEP;347			}348			pb += ST_POINTER_STEP;349			DO_CHECK_FOR_INTERRUPTS();350		}351		while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)352		{353			if (r == 0)354			{355				DO_SWAP(pc, pd);356				pd -= ST_POINTER_STEP;357			}358			pc -= ST_POINTER_STEP;359			DO_CHECK_FOR_INTERRUPTS();360		}361		if (pb > pc)362			break;363		DO_SWAP(pb, pc);364		pb += ST_POINTER_STEP;365		pc -= ST_POINTER_STEP;366	}367	pn = a + n * ST_POINTER_STEP;368	d1 = Min(pa - a, pb - pa);369	DO_SWAPN(a, pb - d1, d1);370	d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);371	DO_SWAPN(pb, pn - d1, d1);372	d1 = pb - pa;373	d2 = pd - pc;374	if (d1 <= d2)375	{376		/* Recurse on left partition, then iterate on right partition */377		if (d1 > ST_POINTER_STEP)378			DO_SORT(a, d1 / ST_POINTER_STEP);379		if (d2 > ST_POINTER_STEP)380		{381			/* Iterate rather than recurse to save stack space */382			/* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */383			a = pn - d2;384			n = d2 / ST_POINTER_STEP;385			goto loop;386		}387	}388	else389	{390		/* Recurse on right partition, then iterate on left partition */391		if (d2 > ST_POINTER_STEP)392			DO_SORT(pn - d2, d2 / ST_POINTER_STEP);393		if (d1 > ST_POINTER_STEP)394		{395			/* Iterate rather than recurse to save stack space */396			/* DO_SORT(a, d1 / ST_POINTER_STEP) */397			n = d1 / ST_POINTER_STEP;398			goto loop;399		}400	}401}402#endif403 404#undef DO_CHECK_FOR_INTERRUPTS405#undef DO_COMPARE406#undef DO_MED3407#undef DO_SORT408#undef DO_SWAP409#undef DO_SWAPN410#undef ST_CHECK_FOR_INTERRUPTS411#undef ST_COMPARATOR_TYPE_NAME412#undef ST_COMPARE413#undef ST_COMPARE_ARG_TYPE414#undef ST_COMPARE_RUNTIME_POINTER415#undef ST_ELEMENT_TYPE416#undef ST_ELEMENT_TYPE_VOID417#undef ST_MAKE_NAME418#undef ST_MAKE_NAME_419#undef ST_MAKE_PREFIX420#undef ST_MED3421#undef ST_POINTER_STEP422#undef ST_POINTER_TYPE423#undef ST_SCOPE424#undef ST_SORT425#undef ST_SORT_INVOKE_ARG426#undef ST_SORT_INVOKE_COMPARE427#undef ST_SORT_INVOKE_ELEMENT_SIZE428#undef ST_SORT_PROTO_ARG429#undef ST_SORT_PROTO_COMPARE430#undef ST_SORT_PROTO_ELEMENT_SIZE431#undef ST_SWAP432#undef ST_SWAPN433