Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6b80394

Browse files
Introduce overflow-safe integer comparison functions.
This commit adds integer comparison functions that are designed tobe as efficient as possible while avoiding overflow. A follow-upcommit will make use of these functions in many of the in-treeqsort() comparators. The new functions are not better in all cases(e.g., when the comparator function is inlined), so it is importantto consider the context before using them.Author: Mats KindahlReviewed-by: Tom Lane, Heikki Linnakangas, Andres Freund, Thomas Munro, Andrey Borodin, Fabrízio de Royes MelloDiscussion:https://postgr.es/m/CA%2B14426g2Wa9QuUpmakwPxXFWG_1FaY0AsApkvcTBy-YfS6uaw%40mail.gmail.com
1 parent73f0a13 commit6b80394

File tree

2 files changed

+86
-2
lines changed

2 files changed

+86
-2
lines changed

‎src/include/common/int.h

Lines changed: 73 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
/*-------------------------------------------------------------------------
22
*
33
* int.h
4-
*Routines to performinteger math, while checking for overflows.
4+
*Overflow-awareinteger math and integer comparison routines.
55
*
66
* The routines in this file are intended to be well defined C, without
77
* relying on compiler flags like -fwrapv.
@@ -22,7 +22,7 @@
2222

2323

2424
/*---------
25-
* The following guidelines apply to all the routines:
25+
* The following guidelines apply to all theoverflowroutines:
2626
* - If a + b overflows, return true, otherwise store the result of a + b
2727
* into *result. The content of *result is implementation defined in case of
2828
* overflow.
@@ -438,4 +438,75 @@ pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
438438
#endif
439439
}
440440

441+
/*------------------------------------------------------------------------
442+
*
443+
* Comparison routines for integer types.
444+
*
445+
* These routines are primarily intended for use in qsort() comparator
446+
* functions and therefore return a positive integer, 0, or a negative
447+
* integer depending on whether "a" is greater than, equal to, or less
448+
* than "b", respectively. These functions are written to be as efficient
449+
* as possible without introducing overflow risks, thereby helping ensure
450+
* the comparators that use them are transitive.
451+
*
452+
* Types with fewer than 32 bits are cast to signed integers and
453+
* subtracted. Other types are compared using > and <, and the results of
454+
* those comparisons (which are either (int) 0 or (int) 1 per the C
455+
* standard) are subtracted.
456+
*
457+
* NB: If the comparator function is inlined, some compilers may produce
458+
* worse code with these helper functions than with code with the
459+
* following form:
460+
*
461+
* if (a < b)
462+
* return -1;
463+
* if (a > b)
464+
* return 1;
465+
* return 0;
466+
*
467+
*------------------------------------------------------------------------
468+
*/
469+
470+
staticinlineint
471+
pg_cmp_s16(int16a,int16b)
472+
{
473+
return (int32)a- (int32)b;
474+
}
475+
476+
staticinlineint
477+
pg_cmp_u16(uint16a,uint16b)
478+
{
479+
return (int32)a- (int32)b;
480+
}
481+
482+
staticinlineint
483+
pg_cmp_s32(int32a,int32b)
484+
{
485+
return (a>b)- (a<b);
486+
}
487+
488+
staticinlineint
489+
pg_cmp_u32(uint32a,uint32b)
490+
{
491+
return (a>b)- (a<b);
492+
}
493+
494+
staticinlineint
495+
pg_cmp_s64(int64a,int64b)
496+
{
497+
return (a>b)- (a<b);
498+
}
499+
500+
staticinlineint
501+
pg_cmp_u64(uint64a,uint64b)
502+
{
503+
return (a>b)- (a<b);
504+
}
505+
506+
staticinlineint
507+
pg_cmp_size(size_ta,size_tb)
508+
{
509+
return (a>b)- (a<b);
510+
}
511+
441512
#endif/* COMMON_INT_H */

‎src/include/lib/sort_template.h

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,16 @@
3434
* - ST_COMPARE(a, b, arg) - variant that takes an extra argument
3535
* - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
3636
*
37+
* NB: If the comparator function is inlined, some compilers may produce
38+
* worse code with the optimized comparison routines in common/int.h than
39+
* with code with the following form:
40+
*
41+
* if (a < b)
42+
* return -1;
43+
* if (a > b)
44+
* return 1;
45+
* return 0;
46+
*
3747
* To say that the comparator and therefore also sort function should
3848
* receive an extra pass-through argument, specify the type of the
3949
* argument.
@@ -243,6 +253,9 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
243253
* Find the median of three values. Currently, performance seems to be best
244254
* if the comparator is inlined here, but the med3 function is not inlined
245255
* in the qsort function.
256+
*
257+
* Refer to the comment at the top of this file for known caveats to consider
258+
* when writing inlined comparator functions.
246259
*/
247260
staticpg_noinlineST_ELEMENT_TYPE*
248261
ST_MED3(ST_ELEMENT_TYPE*a,

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp