LCOV - code coverage report
Current view: top level - src/backend/access/nbtree - nbtcompare.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 156 249 62.7 %
Date: 2025-04-22 09:15:55 Functions: 25 37 67.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nbtcompare.c
       4             :  *    Comparison functions for btree access method.
       5             :  *
       6             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/access/nbtree/nbtcompare.c
      12             :  *
      13             :  * NOTES
      14             :  *
      15             :  *  These functions are stored in pg_amproc.  For each operator class
      16             :  *  defined on btrees, they compute
      17             :  *
      18             :  *              compare(a, b):
      19             :  *                      < 0 if a < b,
      20             :  *                      = 0 if a == b,
      21             :  *                      > 0 if a > b.
      22             :  *
      23             :  *  The result is always an int32 regardless of the input datatype.
      24             :  *
      25             :  *  Although any negative int32 is acceptable for reporting "<",
      26             :  *  and any positive int32 is acceptable for reporting ">", routines
      27             :  *  that work on 32-bit or wider datatypes can't just return "a - b".
      28             :  *  That could overflow and give the wrong answer.
      29             :  *
      30             :  *  NOTE: it is critical that the comparison function impose a total order
      31             :  *  on all non-NULL values of the data type, and that the datatype's
      32             :  *  boolean comparison operators (= < >= etc) yield results consistent
      33             :  *  with the comparison routine.  Otherwise bad behavior may ensue.
      34             :  *  (For example, the comparison operators must NOT punt when faced with
      35             :  *  NAN or other funny values; you must devise some collation sequence for
      36             :  *  all such values.)  If the datatype is not trivial, this is most
      37             :  *  reliably done by having the boolean operators invoke the same
      38             :  *  three-way comparison code that the btree function does.  Therefore,
      39             :  *  this file contains only btree support for "trivial" datatypes ---
      40             :  *  all others are in the /utils/adt/ files that implement their datatypes.
      41             :  *
      42             :  *  NOTE: these routines must not leak memory, since memory allocated
      43             :  *  during an index access won't be recovered till end of query.  This
      44             :  *  primarily affects comparison routines for toastable datatypes;
      45             :  *  they have to be careful to free any detoasted copy of an input datum.
      46             :  *
      47             :  *  NOTE: we used to forbid comparison functions from returning INT_MIN,
      48             :  *  but that proves to be too error-prone because some platforms' versions
      49             :  *  of memcmp() etc can return INT_MIN.  As a means of stress-testing
      50             :  *  callers, this file can be compiled with STRESS_SORT_INT_MIN defined
      51             :  *  to cause many of these functions to return INT_MIN or INT_MAX instead of
      52             :  *  their customary -1/+1.  For production, though, that's not a good idea
      53             :  *  since users or third-party code might expect the traditional results.
      54             :  *-------------------------------------------------------------------------
      55             :  */
      56             : #include "postgres.h"
      57             : 
      58             : #include <limits.h>
      59             : 
      60             : #include "utils/fmgrprotos.h"
      61             : #include "utils/skipsupport.h"
      62             : #include "utils/sortsupport.h"
      63             : 
      64             : #ifdef STRESS_SORT_INT_MIN
      65             : #define A_LESS_THAN_B       INT_MIN
      66             : #define A_GREATER_THAN_B    INT_MAX
      67             : #else
      68             : #define A_LESS_THAN_B       (-1)
      69             : #define A_GREATER_THAN_B    1
      70             : #endif
      71             : 
      72             : 
      73             : Datum
      74    55806946 : btboolcmp(PG_FUNCTION_ARGS)
      75             : {
      76    55806946 :     bool        a = PG_GETARG_BOOL(0);
      77    55806946 :     bool        b = PG_GETARG_BOOL(1);
      78             : 
      79    55806946 :     PG_RETURN_INT32((int32) a - (int32) b);
      80             : }
      81             : 
      82             : static Datum
      83           0 : bool_decrement(Relation rel, Datum existing, bool *underflow)
      84             : {
      85           0 :     bool        bexisting = DatumGetBool(existing);
      86             : 
      87           0 :     if (bexisting == false)
      88             :     {
      89             :         /* return value is undefined */
      90           0 :         *underflow = true;
      91           0 :         return (Datum) 0;
      92             :     }
      93             : 
      94           0 :     *underflow = false;
      95           0 :     return BoolGetDatum(bexisting - 1);
      96             : }
      97             : 
      98             : static Datum
      99           0 : bool_increment(Relation rel, Datum existing, bool *overflow)
     100             : {
     101           0 :     bool        bexisting = DatumGetBool(existing);
     102             : 
     103           0 :     if (bexisting == true)
     104             :     {
     105             :         /* return value is undefined */
     106           0 :         *overflow = true;
     107           0 :         return (Datum) 0;
     108             :     }
     109             : 
     110           0 :     *overflow = false;
     111           0 :     return BoolGetDatum(bexisting + 1);
     112             : }
     113             : 
     114             : Datum
     115           0 : btboolskipsupport(PG_FUNCTION_ARGS)
     116             : {
     117           0 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     118             : 
     119           0 :     sksup->decrement = bool_decrement;
     120           0 :     sksup->increment = bool_increment;
     121           0 :     sksup->low_elem = BoolGetDatum(false);
     122           0 :     sksup->high_elem = BoolGetDatum(true);
     123             : 
     124           0 :     PG_RETURN_VOID();
     125             : }
     126             : 
     127             : Datum
     128    12067654 : btint2cmp(PG_FUNCTION_ARGS)
     129             : {
     130    12067654 :     int16       a = PG_GETARG_INT16(0);
     131    12067654 :     int16       b = PG_GETARG_INT16(1);
     132             : 
     133    12067654 :     PG_RETURN_INT32((int32) a - (int32) b);
     134             : }
     135             : 
     136             : static int
     137    41001826 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
     138             : {
     139    41001826 :     int16       a = DatumGetInt16(x);
     140    41001826 :     int16       b = DatumGetInt16(y);
     141             : 
     142    41001826 :     return (int) a - (int) b;
     143             : }
     144             : 
     145             : Datum
     146       12134 : btint2sortsupport(PG_FUNCTION_ARGS)
     147             : {
     148       12134 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     149             : 
     150       12134 :     ssup->comparator = btint2fastcmp;
     151       12134 :     PG_RETURN_VOID();
     152             : }
     153             : 
     154             : static Datum
     155           0 : int2_decrement(Relation rel, Datum existing, bool *underflow)
     156             : {
     157           0 :     int16       iexisting = DatumGetInt16(existing);
     158             : 
     159           0 :     if (iexisting == PG_INT16_MIN)
     160             :     {
     161             :         /* return value is undefined */
     162           0 :         *underflow = true;
     163           0 :         return (Datum) 0;
     164             :     }
     165             : 
     166           0 :     *underflow = false;
     167           0 :     return Int16GetDatum(iexisting - 1);
     168             : }
     169             : 
     170             : static Datum
     171           4 : int2_increment(Relation rel, Datum existing, bool *overflow)
     172             : {
     173           4 :     int16       iexisting = DatumGetInt16(existing);
     174             : 
     175           4 :     if (iexisting == PG_INT16_MAX)
     176             :     {
     177             :         /* return value is undefined */
     178           0 :         *overflow = true;
     179           0 :         return (Datum) 0;
     180             :     }
     181             : 
     182           4 :     *overflow = false;
     183           4 :     return Int16GetDatum(iexisting + 1);
     184             : }
     185             : 
     186             : Datum
     187         184 : btint2skipsupport(PG_FUNCTION_ARGS)
     188             : {
     189         184 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     190             : 
     191         184 :     sksup->decrement = int2_decrement;
     192         184 :     sksup->increment = int2_increment;
     193         184 :     sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
     194         184 :     sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
     195             : 
     196         184 :     PG_RETURN_VOID();
     197             : }
     198             : 
     199             : Datum
     200    98787666 : btint4cmp(PG_FUNCTION_ARGS)
     201             : {
     202    98787666 :     int32       a = PG_GETARG_INT32(0);
     203    98787666 :     int32       b = PG_GETARG_INT32(1);
     204             : 
     205    98787666 :     if (a > b)
     206    37992818 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     207    60794848 :     else if (a == b)
     208    20415552 :         PG_RETURN_INT32(0);
     209             :     else
     210    40379296 :         PG_RETURN_INT32(A_LESS_THAN_B);
     211             : }
     212             : 
     213             : Datum
     214      173436 : btint4sortsupport(PG_FUNCTION_ARGS)
     215             : {
     216      173436 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     217             : 
     218      173436 :     ssup->comparator = ssup_datum_int32_cmp;
     219      173436 :     PG_RETURN_VOID();
     220             : }
     221             : 
     222             : static Datum
     223        3966 : int4_decrement(Relation rel, Datum existing, bool *underflow)
     224             : {
     225        3966 :     int32       iexisting = DatumGetInt32(existing);
     226             : 
     227        3966 :     if (iexisting == PG_INT32_MIN)
     228             :     {
     229             :         /* return value is undefined */
     230           0 :         *underflow = true;
     231           0 :         return (Datum) 0;
     232             :     }
     233             : 
     234        3966 :     *underflow = false;
     235        3966 :     return Int32GetDatum(iexisting - 1);
     236             : }
     237             : 
     238             : static Datum
     239        3822 : int4_increment(Relation rel, Datum existing, bool *overflow)
     240             : {
     241        3822 :     int32       iexisting = DatumGetInt32(existing);
     242             : 
     243        3822 :     if (iexisting == PG_INT32_MAX)
     244             :     {
     245             :         /* return value is undefined */
     246          30 :         *overflow = true;
     247          30 :         return (Datum) 0;
     248             :     }
     249             : 
     250        3792 :     *overflow = false;
     251        3792 :     return Int32GetDatum(iexisting + 1);
     252             : }
     253             : 
     254             : Datum
     255         246 : btint4skipsupport(PG_FUNCTION_ARGS)
     256             : {
     257         246 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     258             : 
     259         246 :     sksup->decrement = int4_decrement;
     260         246 :     sksup->increment = int4_increment;
     261         246 :     sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
     262         246 :     sksup->high_elem = Int32GetDatum(PG_INT32_MAX);
     263             : 
     264         246 :     PG_RETURN_VOID();
     265             : }
     266             : 
     267             : Datum
     268    16636422 : btint8cmp(PG_FUNCTION_ARGS)
     269             : {
     270    16636422 :     int64       a = PG_GETARG_INT64(0);
     271    16636422 :     int64       b = PG_GETARG_INT64(1);
     272             : 
     273    16636422 :     if (a > b)
     274     9721434 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     275     6914988 :     else if (a == b)
     276      844934 :         PG_RETURN_INT32(0);
     277             :     else
     278     6070054 :         PG_RETURN_INT32(A_LESS_THAN_B);
     279             : }
     280             : 
     281             : #if SIZEOF_DATUM < 8
     282             : static int
     283             : btint8fastcmp(Datum x, Datum y, SortSupport ssup)
     284             : {
     285             :     int64       a = DatumGetInt64(x);
     286             :     int64       b = DatumGetInt64(y);
     287             : 
     288             :     if (a > b)
     289             :         return A_GREATER_THAN_B;
     290             :     else if (a == b)
     291             :         return 0;
     292             :     else
     293             :         return A_LESS_THAN_B;
     294             : }
     295             : #endif
     296             : 
     297             : Datum
     298        3786 : btint8sortsupport(PG_FUNCTION_ARGS)
     299             : {
     300        3786 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     301             : 
     302             : #if SIZEOF_DATUM >= 8
     303        3786 :     ssup->comparator = ssup_datum_signed_cmp;
     304             : #else
     305             :     ssup->comparator = btint8fastcmp;
     306             : #endif
     307        3786 :     PG_RETURN_VOID();
     308             : }
     309             : 
     310             : static Datum
     311           0 : int8_decrement(Relation rel, Datum existing, bool *underflow)
     312             : {
     313           0 :     int64       iexisting = DatumGetInt64(existing);
     314             : 
     315           0 :     if (iexisting == PG_INT64_MIN)
     316             :     {
     317             :         /* return value is undefined */
     318           0 :         *underflow = true;
     319           0 :         return (Datum) 0;
     320             :     }
     321             : 
     322           0 :     *underflow = false;
     323           0 :     return Int64GetDatum(iexisting - 1);
     324             : }
     325             : 
     326             : static Datum
     327           0 : int8_increment(Relation rel, Datum existing, bool *overflow)
     328             : {
     329           0 :     int64       iexisting = DatumGetInt64(existing);
     330             : 
     331           0 :     if (iexisting == PG_INT64_MAX)
     332             :     {
     333             :         /* return value is undefined */
     334           0 :         *overflow = true;
     335           0 :         return (Datum) 0;
     336             :     }
     337             : 
     338           0 :     *overflow = false;
     339           0 :     return Int64GetDatum(iexisting + 1);
     340             : }
     341             : 
     342             : Datum
     343           0 : btint8skipsupport(PG_FUNCTION_ARGS)
     344             : {
     345           0 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     346             : 
     347           0 :     sksup->decrement = int8_decrement;
     348           0 :     sksup->increment = int8_increment;
     349           0 :     sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
     350           0 :     sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
     351             : 
     352           0 :     PG_RETURN_VOID();
     353             : }
     354             : 
     355             : Datum
     356        1452 : btint48cmp(PG_FUNCTION_ARGS)
     357             : {
     358        1452 :     int32       a = PG_GETARG_INT32(0);
     359        1452 :     int64       b = PG_GETARG_INT64(1);
     360             : 
     361        1452 :     if (a > b)
     362         498 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     363         954 :     else if (a == b)
     364          66 :         PG_RETURN_INT32(0);
     365             :     else
     366         888 :         PG_RETURN_INT32(A_LESS_THAN_B);
     367             : }
     368             : 
     369             : Datum
     370         102 : btint84cmp(PG_FUNCTION_ARGS)
     371             : {
     372         102 :     int64       a = PG_GETARG_INT64(0);
     373         102 :     int32       b = PG_GETARG_INT32(1);
     374             : 
     375         102 :     if (a > b)
     376          30 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     377          72 :     else if (a == b)
     378          30 :         PG_RETURN_INT32(0);
     379             :     else
     380          42 :         PG_RETURN_INT32(A_LESS_THAN_B);
     381             : }
     382             : 
     383             : Datum
     384       52180 : btint24cmp(PG_FUNCTION_ARGS)
     385             : {
     386       52180 :     int16       a = PG_GETARG_INT16(0);
     387       52180 :     int32       b = PG_GETARG_INT32(1);
     388             : 
     389       52180 :     if (a > b)
     390       28242 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     391       23938 :     else if (a == b)
     392        8060 :         PG_RETURN_INT32(0);
     393             :     else
     394       15878 :         PG_RETURN_INT32(A_LESS_THAN_B);
     395             : }
     396             : 
     397             : Datum
     398        1352 : btint42cmp(PG_FUNCTION_ARGS)
     399             : {
     400        1352 :     int32       a = PG_GETARG_INT32(0);
     401        1352 :     int16       b = PG_GETARG_INT16(1);
     402             : 
     403        1352 :     if (a > b)
     404          82 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     405        1270 :     else if (a == b)
     406         300 :         PG_RETURN_INT32(0);
     407             :     else
     408         970 :         PG_RETURN_INT32(A_LESS_THAN_B);
     409             : }
     410             : 
     411             : Datum
     412          36 : btint28cmp(PG_FUNCTION_ARGS)
     413             : {
     414          36 :     int16       a = PG_GETARG_INT16(0);
     415          36 :     int64       b = PG_GETARG_INT64(1);
     416             : 
     417          36 :     if (a > b)
     418           0 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     419          36 :     else if (a == b)
     420           0 :         PG_RETURN_INT32(0);
     421             :     else
     422          36 :         PG_RETURN_INT32(A_LESS_THAN_B);
     423             : }
     424             : 
     425             : Datum
     426           0 : btint82cmp(PG_FUNCTION_ARGS)
     427             : {
     428           0 :     int64       a = PG_GETARG_INT64(0);
     429           0 :     int16       b = PG_GETARG_INT16(1);
     430             : 
     431           0 :     if (a > b)
     432           0 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     433           0 :     else if (a == b)
     434           0 :         PG_RETURN_INT32(0);
     435             :     else
     436           0 :         PG_RETURN_INT32(A_LESS_THAN_B);
     437             : }
     438             : 
     439             : Datum
     440   217207336 : btoidcmp(PG_FUNCTION_ARGS)
     441             : {
     442   217207336 :     Oid         a = PG_GETARG_OID(0);
     443   217207336 :     Oid         b = PG_GETARG_OID(1);
     444             : 
     445   217207336 :     if (a > b)
     446    58014898 :         PG_RETURN_INT32(A_GREATER_THAN_B);
     447   159192438 :     else if (a == b)
     448    51628762 :         PG_RETURN_INT32(0);
     449             :     else
     450   107563676 :         PG_RETURN_INT32(A_LESS_THAN_B);
     451             : }
     452             : 
     453             : static int
     454   267712030 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
     455             : {
     456   267712030 :     Oid         a = DatumGetObjectId(x);
     457   267712030 :     Oid         b = DatumGetObjectId(y);
     458             : 
     459   267712030 :     if (a > b)
     460    67427412 :         return A_GREATER_THAN_B;
     461   200284618 :     else if (a == b)
     462   135527190 :         return 0;
     463             :     else
     464    64757428 :         return A_LESS_THAN_B;
     465             : }
     466             : 
     467             : Datum
     468      125082 : btoidsortsupport(PG_FUNCTION_ARGS)
     469             : {
     470      125082 :     SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
     471             : 
     472      125082 :     ssup->comparator = btoidfastcmp;
     473      125082 :     PG_RETURN_VOID();
     474             : }
     475             : 
     476             : static Datum
     477           0 : oid_decrement(Relation rel, Datum existing, bool *underflow)
     478             : {
     479           0 :     Oid         oexisting = DatumGetObjectId(existing);
     480             : 
     481           0 :     if (oexisting == InvalidOid)
     482             :     {
     483             :         /* return value is undefined */
     484           0 :         *underflow = true;
     485           0 :         return (Datum) 0;
     486             :     }
     487             : 
     488           0 :     *underflow = false;
     489           0 :     return ObjectIdGetDatum(oexisting - 1);
     490             : }
     491             : 
     492             : static Datum
     493         358 : oid_increment(Relation rel, Datum existing, bool *overflow)
     494             : {
     495         358 :     Oid         oexisting = DatumGetObjectId(existing);
     496             : 
     497         358 :     if (oexisting == OID_MAX)
     498             :     {
     499             :         /* return value is undefined */
     500           0 :         *overflow = true;
     501           0 :         return (Datum) 0;
     502             :     }
     503             : 
     504         358 :     *overflow = false;
     505         358 :     return ObjectIdGetDatum(oexisting + 1);
     506             : }
     507             : 
     508             : Datum
     509        2828 : btoidskipsupport(PG_FUNCTION_ARGS)
     510             : {
     511        2828 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     512             : 
     513        2828 :     sksup->decrement = oid_decrement;
     514        2828 :     sksup->increment = oid_increment;
     515        2828 :     sksup->low_elem = ObjectIdGetDatum(InvalidOid);
     516        2828 :     sksup->high_elem = ObjectIdGetDatum(OID_MAX);
     517             : 
     518        2828 :     PG_RETURN_VOID();
     519             : }
     520             : 
     521             : Datum
     522     7565046 : btoidvectorcmp(PG_FUNCTION_ARGS)
     523             : {
     524     7565046 :     oidvector  *a = (oidvector *) PG_GETARG_POINTER(0);
     525     7565046 :     oidvector  *b = (oidvector *) PG_GETARG_POINTER(1);
     526             :     int         i;
     527             : 
     528             :     /* We arbitrarily choose to sort first by vector length */
     529     7565046 :     if (a->dim1 != b->dim1)
     530     1276952 :         PG_RETURN_INT32(a->dim1 - b->dim1);
     531             : 
     532    11035144 :     for (i = 0; i < a->dim1; i++)
     533             :     {
     534     8410402 :         if (a->values[i] != b->values[i])
     535             :         {
     536     3663352 :             if (a->values[i] > b->values[i])
     537     1847652 :                 PG_RETURN_INT32(A_GREATER_THAN_B);
     538             :             else
     539     1815700 :                 PG_RETURN_INT32(A_LESS_THAN_B);
     540             :         }
     541             :     }
     542     2624742 :     PG_RETURN_INT32(0);
     543             : }
     544             : 
     545             : Datum
     546    57561274 : btcharcmp(PG_FUNCTION_ARGS)
     547             : {
     548    57561274 :     char        a = PG_GETARG_CHAR(0);
     549    57561274 :     char        b = PG_GETARG_CHAR(1);
     550             : 
     551             :     /* Be careful to compare chars as unsigned */
     552    57561274 :     PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
     553             : }
     554             : 
     555             : static Datum
     556           0 : char_decrement(Relation rel, Datum existing, bool *underflow)
     557             : {
     558           0 :     uint8       cexisting = UInt8GetDatum(existing);
     559             : 
     560           0 :     if (cexisting == 0)
     561             :     {
     562             :         /* return value is undefined */
     563           0 :         *underflow = true;
     564           0 :         return (Datum) 0;
     565             :     }
     566             : 
     567           0 :     *underflow = false;
     568           0 :     return CharGetDatum((uint8) cexisting - 1);
     569             : }
     570             : 
     571             : static Datum
     572           0 : char_increment(Relation rel, Datum existing, bool *overflow)
     573             : {
     574           0 :     uint8       cexisting = UInt8GetDatum(existing);
     575             : 
     576           0 :     if (cexisting == UCHAR_MAX)
     577             :     {
     578             :         /* return value is undefined */
     579           0 :         *overflow = true;
     580           0 :         return (Datum) 0;
     581             :     }
     582             : 
     583           0 :     *overflow = false;
     584           0 :     return CharGetDatum((uint8) cexisting + 1);
     585             : }
     586             : 
     587             : Datum
     588           0 : btcharskipsupport(PG_FUNCTION_ARGS)
     589             : {
     590           0 :     SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
     591             : 
     592           0 :     sksup->decrement = char_decrement;
     593           0 :     sksup->increment = char_increment;
     594             : 
     595             :     /* btcharcmp compares chars as unsigned */
     596           0 :     sksup->low_elem = UInt8GetDatum(0);
     597           0 :     sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
     598             : 
     599           0 :     PG_RETURN_VOID();
     600             : }

Generated by: LCOV version 1.14