From d0fb306d2720d14be2d46f4ae4198b25a33a95fa Mon Sep 17 00:00:00 2001 From: Thomas Munro Date: Sat, 13 Mar 2021 17:29:44 +1300 Subject: [PATCH 1/9] Add bsearch and unique templates to sort_template.h. Since binary search and uniquify are so closely related to sorting, let's optionally generate compatible functions at the same time. Also, optionally support comparators with wider return types. This will allow us to do more branchless comparators. Also, adjust the ST_SORT template to cope with pointer types. --- src/include/lib/sort_template.h | 142 ++++++++++++++++++++++++++++---- 1 file changed, 124 insertions(+), 18 deletions(-) diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h index 771c789ced..a6097e1ac5 100644 --- a/src/include/lib/sort_template.h +++ b/src/include/lib/sort_template.h @@ -3,7 +3,8 @@ * sort_template.h * * A template for a sort algorithm that supports varying degrees of - * specialization. + * specialization. Also related algorithms for binary search and + * unique, on sorted arrays. * * Copyright (c) 2021, PostgreSQL Global Development Group * Portions Copyright (c) 1992-1994, Regents of the University of California @@ -13,7 +14,9 @@ * 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_SORT - if defined the name of a sort function + * - ST_UNIQUE - if defined the name of a unique function + * - ST_SEARCH - if defined the name of a search function * - 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 @@ -40,6 +43,10 @@ * * - ST_COMPARE_ARG_TYPE - type of extra argument * + * To say that the comparator returns a type other than int, use: + * + * - ST_COMPARE_TYPE - an integer type + * * The prototype of the generated sort function is: * * void ST_SORT(ST_ELEMENT_TYPE *data, size_t n, @@ -179,13 +186,35 @@ typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *, const ST_ELEMENT_TYPE *ST_SORT_PROTO_ARG); #endif +#ifdef ST_SORT /* Declare the sort function. Note optional arguments at end. */ -ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n +ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *array, + size_t n ST_SORT_PROTO_ELEMENT_SIZE ST_SORT_PROTO_COMPARE ST_SORT_PROTO_ARG); +#endif /* ST_SORT */ -#endif +#ifdef ST_SEARCH +/* Declare the search function. */ +ST_SCOPE ST_ELEMENT_TYPE *ST_SEARCH(ST_ELEMENT_TYPE *value, + ST_ELEMENT_TYPE *array, + size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG); +#endif /* ST_SEARCH */ + +#ifdef ST_UNIQUE +ST_SCOPE size_t +ST_UNIQUE(ST_ELEMENT_TYPE *array, + size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG); +#endif /* ST_UNIQUE */ + +#endif /* ST_DECLARE */ #ifdef ST_DEFINE @@ -201,16 +230,20 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n #define DO_CHECK_FOR_INTERRUPTS() #endif +#ifndef ST_COMPARE_TYPE +#define ST_COMPARE_TYPE int +#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) +#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG))) #elif defined(ST_COMPARE_ARG_TYPE) -#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg) +#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_), arg))) #else -#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_)) +#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_)))) #endif #define DO_MED3(a_, b_, c_) \ ST_MED3((a_), (b_), (c_) \ @@ -239,6 +272,8 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size) #endif +#ifdef ST_SORT + /* * Find the median of three values. Currently, performance seems to be best * if the the comparator is inlined here, but the med3 function is not inlined @@ -281,18 +316,18 @@ ST_SORT(ST_ELEMENT_TYPE *data, size_t n ST_SORT_PROTO_COMPARE ST_SORT_PROTO_ARG) { - ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data, - *pa, - *pb, - *pc, - *pd, - *pl, - *pm, - *pn; + ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data; + ST_POINTER_TYPE *pa; + ST_POINTER_TYPE *pb; + ST_POINTER_TYPE *pc; + ST_POINTER_TYPE *pd; + ST_POINTER_TYPE *pl; + ST_POINTER_TYPE *pm; + ST_POINTER_TYPE *pn; size_t d1, d2; - int r, - presorted; + int presorted; + ST_COMPARE_TYPE r; loop: DO_CHECK_FOR_INTERRUPTS(); @@ -399,7 +434,75 @@ loop: } } } -#endif + +#endif /* ST_SORT */ + +#ifdef ST_SEARCH + +/* + * Find an element in the array of sorted values that is equal to a given + * value, in a sorted array. Return NULL if there is none. + */ +ST_SCOPE ST_ELEMENT_TYPE * +ST_SEARCH(ST_ELEMENT_TYPE *value, + ST_ELEMENT_TYPE *array, + size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG) +{ + ssize_t left = 0, + right = n - 1; + + while (left <= right) + { + size_t mid = (left + right) / 2; + ST_ELEMENT_TYPE *element = &array[mid]; + ST_COMPARE_TYPE cmp = DO_COMPARE(element, value); + + if (cmp < 0) + left = mid + 1; + else if (cmp > 0) + right = mid - 1; + else + return element; + } + + return NULL; +} + +#endif /* ST_SEARCH */ + +#ifdef ST_UNIQUE + +/* + * Remove duplicates from an array. Return the new size. + */ +ST_SCOPE size_t +ST_UNIQUE(ST_ELEMENT_TYPE *array, + size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG) +{ + size_t i, + j; + + if (n <= 1) + return n; + + for (i = 1, j = 0; i < n; ++i) + { + if (DO_COMPARE(&array[i], &array[j]) != 0 && ++j != i) + array[j] = array[i]; + } + + return j + 1; +} + +#endif /* ST_UNIQUE */ + +#endif /* ST_DEFINE */ #undef DO_CHECK_FOR_INTERRUPTS #undef DO_COMPARE @@ -411,6 +514,7 @@ loop: #undef ST_COMPARE #undef ST_COMPARE_ARG_TYPE #undef ST_COMPARE_RUNTIME_POINTER +#undef ST_COMPARE_TYPE #undef ST_ELEMENT_TYPE #undef ST_ELEMENT_TYPE_VOID #undef ST_MAKE_NAME @@ -420,6 +524,7 @@ loop: #undef ST_POINTER_STEP #undef ST_POINTER_TYPE #undef ST_SCOPE +#undef ST_SEARCH #undef ST_SORT #undef ST_SORT_INVOKE_ARG #undef ST_SORT_INVOKE_COMPARE @@ -429,3 +534,4 @@ loop: #undef ST_SORT_PROTO_ELEMENT_SIZE #undef ST_SWAP #undef ST_SWAPN +#undef ST_UNIQUE -- 2.30.1