diff options
| -rw-r--r-- | src/include/common/int.h | 75 | ||||
| -rw-r--r-- | src/include/lib/sort_template.h | 13 |
2 files changed, 86 insertions, 2 deletions
diff --git a/src/include/common/int.h b/src/include/common/int.h index fedf7b39992..7fc046e78af 100644 --- a/src/include/common/int.h +++ b/src/include/common/int.h @@ -1,7 +1,7 @@ /*------------------------------------------------------------------------- * * int.h - * Routines to perform integer math, while checking for overflows. + * Overflow-aware integer math and integer comparison routines. * * The routines in this file are intended to be well defined C, without * relying on compiler flags like -fwrapv. @@ -22,7 +22,7 @@ /*--------- - * The following guidelines apply to all the routines: + * The following guidelines apply to all the overflow routines: * - If a + b overflows, return true, otherwise store the result of a + b * into *result. The content of *result is implementation defined in case of * overflow. @@ -438,4 +438,75 @@ pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result) #endif } +/*------------------------------------------------------------------------ + * + * Comparison routines for integer types. + * + * These routines are primarily intended for use in qsort() comparator + * functions and therefore return a positive integer, 0, or a negative + * integer depending on whether "a" is greater than, equal to, or less + * than "b", respectively. These functions are written to be as efficient + * as possible without introducing overflow risks, thereby helping ensure + * the comparators that use them are transitive. + * + * Types with fewer than 32 bits are cast to signed integers and + * subtracted. Other types are compared using > and <, and the results of + * those comparisons (which are either (int) 0 or (int) 1 per the C + * standard) are subtracted. + * + * NB: If the comparator function is inlined, some compilers may produce + * worse code with these helper functions than with code with the + * following form: + * + * if (a < b) + * return -1; + * if (a > b) + * return 1; + * return 0; + * + *------------------------------------------------------------------------ + */ + +static inline int +pg_cmp_s16(int16 a, int16 b) +{ + return (int32) a - (int32) b; +} + +static inline int +pg_cmp_u16(uint16 a, uint16 b) +{ + return (int32) a - (int32) b; +} + +static inline int +pg_cmp_s32(int32 a, int32 b) +{ + return (a > b) - (a < b); +} + +static inline int +pg_cmp_u32(uint32 a, uint32 b) +{ + return (a > b) - (a < b); +} + +static inline int +pg_cmp_s64(int64 a, int64 b) +{ + return (a > b) - (a < b); +} + +static inline int +pg_cmp_u64(uint64 a, uint64 b) +{ + return (a > b) - (a < b); +} + +static inline int +pg_cmp_size(size_t a, size_t b) +{ + return (a > b) - (a < b); +} + #endif /* COMMON_INT_H */ diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h index a470fa11038..00a04a6da48 100644 --- a/src/include/lib/sort_template.h +++ b/src/include/lib/sort_template.h @@ -34,6 +34,16 @@ * - 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. @@ -243,6 +253,9 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n * 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, |