LCOV - code coverage report
Current view: top level - src/backend/utils/adt - multirangetypes.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 918 984 93.3 %
Date: 2024-10-07 02:11:23 Functions: 90 92 97.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * multirangetypes.c
       4             :  *    I/O functions, operators, and support functions for multirange types.
       5             :  *
       6             :  * The stored (serialized) format of a multirange value is:
       7             :  *
       8             :  *  12 bytes: MultirangeType struct including varlena header, multirange
       9             :  *            type's OID and the number of ranges in the multirange.
      10             :  *  4 * (rangesCount - 1) bytes: 32-bit items pointing to the each range
      11             :  *                               in the multirange starting from
      12             :  *                               the second one.
      13             :  *  1 * rangesCount bytes : 8-bit flags for each range in the multirange
      14             :  *  The rest of the multirange are range bound values pointed by multirange
      15             :  *  items.
      16             :  *
      17             :  *  Majority of items contain lengths of corresponding range bound values.
      18             :  *  Thanks to that items are typically low numbers.  This makes multiranges
      19             :  *  compression-friendly.  Every MULTIRANGE_ITEM_OFFSET_STRIDE item contains
      20             :  *  an offset of the corresponding range bound values.  That allows fast lookups
      21             :  *  for a particular range index.  Offsets are counted starting from the end of
      22             :  *  flags aligned to the bound type.
      23             :  *
      24             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
      25             :  * Portions Copyright (c) 1994, Regents of the University of California
      26             :  *
      27             :  *
      28             :  * IDENTIFICATION
      29             :  *    src/backend/utils/adt/multirangetypes.c
      30             :  *
      31             :  *-------------------------------------------------------------------------
      32             :  */
      33             : #include "postgres.h"
      34             : 
      35             : #include "access/tupmacs.h"
      36             : #include "common/hashfn.h"
      37             : #include "funcapi.h"
      38             : #include "lib/stringinfo.h"
      39             : #include "libpq/pqformat.h"
      40             : #include "nodes/nodes.h"
      41             : #include "port/pg_bitutils.h"
      42             : #include "utils/array.h"
      43             : #include "utils/builtins.h"
      44             : #include "utils/lsyscache.h"
      45             : #include "utils/multirangetypes.h"
      46             : #include "utils/rangetypes.h"
      47             : 
      48             : /* fn_extra cache entry for one of the range I/O functions */
      49             : typedef struct MultirangeIOData
      50             : {
      51             :     TypeCacheEntry *typcache;   /* multirange type's typcache entry */
      52             :     FmgrInfo    typioproc;      /* range type's I/O proc */
      53             :     Oid         typioparam;     /* range type's I/O parameter */
      54             : } MultirangeIOData;
      55             : 
      56             : typedef enum
      57             : {
      58             :     MULTIRANGE_BEFORE_RANGE,
      59             :     MULTIRANGE_IN_RANGE,
      60             :     MULTIRANGE_IN_RANGE_ESCAPED,
      61             :     MULTIRANGE_IN_RANGE_QUOTED,
      62             :     MULTIRANGE_IN_RANGE_QUOTED_ESCAPED,
      63             :     MULTIRANGE_AFTER_RANGE,
      64             :     MULTIRANGE_FINISHED,
      65             : } MultirangeParseState;
      66             : 
      67             : /*
      68             :  * Macros for accessing past MultirangeType parts of multirange: items, flags
      69             :  * and boundaries.
      70             :  */
      71             : #define MultirangeGetItemsPtr(mr) ((uint32 *) ((Pointer) (mr) + \
      72             :     sizeof(MultirangeType)))
      73             : #define MultirangeGetFlagsPtr(mr) ((uint8 *) ((Pointer) (mr) + \
      74             :     sizeof(MultirangeType) + ((mr)->rangeCount - 1) * sizeof(uint32)))
      75             : #define MultirangeGetBoundariesPtr(mr, align) ((Pointer) (mr) + \
      76             :     att_align_nominal(sizeof(MultirangeType) + \
      77             :         ((mr)->rangeCount - 1) * sizeof(uint32) + \
      78             :         (mr)->rangeCount * sizeof(uint8), (align)))
      79             : 
      80             : #define MULTIRANGE_ITEM_OFF_BIT 0x80000000
      81             : #define MULTIRANGE_ITEM_GET_OFFLEN(item) ((item) & 0x7FFFFFFF)
      82             : #define MULTIRANGE_ITEM_HAS_OFF(item) ((item) & MULTIRANGE_ITEM_OFF_BIT)
      83             : #define MULTIRANGE_ITEM_OFFSET_STRIDE 4
      84             : 
      85             : typedef int (*multirange_bsearch_comparison) (TypeCacheEntry *typcache,
      86             :                                               RangeBound *lower,
      87             :                                               RangeBound *upper,
      88             :                                               void *key,
      89             :                                               bool *match);
      90             : 
      91             : static MultirangeIOData *get_multirange_io_data(FunctionCallInfo fcinfo,
      92             :                                                 Oid mltrngtypid,
      93             :                                                 IOFuncSelector func);
      94             : static int32 multirange_canonicalize(TypeCacheEntry *rangetyp,
      95             :                                      int32 input_range_count,
      96             :                                      RangeType **ranges);
      97             : 
      98             : /*
      99             :  *----------------------------------------------------------
     100             :  * I/O FUNCTIONS
     101             :  *----------------------------------------------------------
     102             :  */
     103             : 
     104             : /*
     105             :  * Converts string to multirange.
     106             :  *
     107             :  * We expect curly brackets to bound the list, with zero or more ranges
     108             :  * separated by commas.  We accept whitespace anywhere: before/after our
     109             :  * brackets and around the commas.  Ranges can be the empty literal or some
     110             :  * stuff inside parens/brackets.  Mostly we delegate parsing the individual
     111             :  * range contents to range_in, but we have to detect quoting and
     112             :  * backslash-escaping which can happen for range bounds.  Backslashes can
     113             :  * escape something inside or outside a quoted string, and a quoted string
     114             :  * can escape quote marks with either backslashes or double double-quotes.
     115             :  */
     116             : Datum
     117        1380 : multirange_in(PG_FUNCTION_ARGS)
     118             : {
     119        1380 :     char       *input_str = PG_GETARG_CSTRING(0);
     120        1380 :     Oid         mltrngtypoid = PG_GETARG_OID(1);
     121        1380 :     Oid         typmod = PG_GETARG_INT32(2);
     122        1380 :     Node       *escontext = fcinfo->context;
     123             :     TypeCacheEntry *rangetyp;
     124        1380 :     int32       ranges_seen = 0;
     125        1380 :     int32       range_count = 0;
     126        1380 :     int32       range_capacity = 8;
     127             :     RangeType  *range;
     128        1380 :     RangeType **ranges = palloc(range_capacity * sizeof(RangeType *));
     129             :     MultirangeIOData *cache;
     130             :     MultirangeType *ret;
     131             :     MultirangeParseState parse_state;
     132        1380 :     const char *ptr = input_str;
     133        1380 :     const char *range_str_begin = NULL;
     134             :     int32       range_str_len;
     135             :     char       *range_str;
     136             :     Datum       range_datum;
     137             : 
     138        1380 :     cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_input);
     139        1380 :     rangetyp = cache->typcache->rngtype;
     140             : 
     141             :     /* consume whitespace */
     142        1404 :     while (*ptr != '\0' && isspace((unsigned char) *ptr))
     143          24 :         ptr++;
     144             : 
     145        1380 :     if (*ptr == '{')
     146        1374 :         ptr++;
     147             :     else
     148           6 :         ereturn(escontext, (Datum) 0,
     149             :                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
     150             :                  errmsg("malformed multirange literal: \"%s\"",
     151             :                         input_str),
     152             :                  errdetail("Missing left brace.")));
     153             : 
     154             :     /* consume ranges */
     155        1374 :     parse_state = MULTIRANGE_BEFORE_RANGE;
     156       13764 :     for (; parse_state != MULTIRANGE_FINISHED; ptr++)
     157             :     {
     158       12486 :         char        ch = *ptr;
     159             : 
     160       12486 :         if (ch == '\0')
     161          18 :             ereturn(escontext, (Datum) 0,
     162             :                     (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
     163             :                      errmsg("malformed multirange literal: \"%s\"",
     164             :                             input_str),
     165             :                      errdetail("Unexpected end of input.")));
     166             : 
     167             :         /* skip whitespace */
     168       12468 :         if (isspace((unsigned char) ch))
     169         576 :             continue;
     170             : 
     171       11892 :         switch (parse_state)
     172             :         {
     173        1854 :             case MULTIRANGE_BEFORE_RANGE:
     174        1854 :                 if (ch == '[' || ch == '(')
     175             :                 {
     176        1524 :                     range_str_begin = ptr;
     177        1524 :                     parse_state = MULTIRANGE_IN_RANGE;
     178             :                 }
     179         330 :                 else if (ch == '}' && ranges_seen == 0)
     180         288 :                     parse_state = MULTIRANGE_FINISHED;
     181          42 :                 else if (pg_strncasecmp(ptr, RANGE_EMPTY_LITERAL,
     182             :                                         strlen(RANGE_EMPTY_LITERAL)) == 0)
     183             :                 {
     184          18 :                     ranges_seen++;
     185             :                     /* nothing to do with an empty range */
     186          18 :                     ptr += strlen(RANGE_EMPTY_LITERAL) - 1;
     187          18 :                     parse_state = MULTIRANGE_AFTER_RANGE;
     188             :                 }
     189             :                 else
     190          24 :                     ereturn(escontext, (Datum) 0,
     191             :                             (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
     192             :                              errmsg("malformed multirange literal: \"%s\"",
     193             :                                     input_str),
     194             :                              errdetail("Expected range start.")));
     195        1830 :                 break;
     196        8370 :             case MULTIRANGE_IN_RANGE:
     197        8370 :                 if (ch == ']' || ch == ')')
     198             :                 {
     199        1518 :                     range_str_len = ptr - range_str_begin + 1;
     200        1518 :                     range_str = pnstrdup(range_str_begin, range_str_len);
     201        1518 :                     if (range_capacity == range_count)
     202             :                     {
     203           0 :                         range_capacity *= 2;
     204             :                         ranges = (RangeType **)
     205           0 :                             repalloc(ranges, range_capacity * sizeof(RangeType *));
     206             :                     }
     207        1518 :                     ranges_seen++;
     208        1518 :                     if (!InputFunctionCallSafe(&cache->typioproc,
     209             :                                                range_str,
     210             :                                                cache->typioparam,
     211             :                                                typmod,
     212             :                                                escontext,
     213             :                                                &range_datum))
     214          12 :                         PG_RETURN_NULL();
     215        1482 :                     range = DatumGetRangeTypeP(range_datum);
     216        1482 :                     if (!RangeIsEmpty(range))
     217        1452 :                         ranges[range_count++] = range;
     218        1482 :                     parse_state = MULTIRANGE_AFTER_RANGE;
     219             :                 }
     220             :                 else
     221             :                 {
     222        6852 :                     if (ch == '"')
     223          78 :                         parse_state = MULTIRANGE_IN_RANGE_QUOTED;
     224        6774 :                     else if (ch == '\\')
     225           6 :                         parse_state = MULTIRANGE_IN_RANGE_ESCAPED;
     226             : 
     227             :                     /*
     228             :                      * We will include this character into range_str once we
     229             :                      * find the end of the range value.
     230             :                      */
     231             :                 }
     232        8334 :                 break;
     233           6 :             case MULTIRANGE_IN_RANGE_ESCAPED:
     234             : 
     235             :                 /*
     236             :                  * We will include this character into range_str once we find
     237             :                  * the end of the range value.
     238             :                  */
     239           6 :                 parse_state = MULTIRANGE_IN_RANGE;
     240           6 :                 break;
     241         156 :             case MULTIRANGE_IN_RANGE_QUOTED:
     242         156 :                 if (ch == '"')
     243          78 :                     if (*(ptr + 1) == '"')
     244             :                     {
     245             :                         /* two quote marks means an escaped quote mark */
     246           6 :                         ptr++;
     247             :                     }
     248             :                     else
     249          72 :                         parse_state = MULTIRANGE_IN_RANGE;
     250          78 :                 else if (ch == '\\')
     251          18 :                     parse_state = MULTIRANGE_IN_RANGE_QUOTED_ESCAPED;
     252             : 
     253             :                 /*
     254             :                  * We will include this character into range_str once we find
     255             :                  * the end of the range value.
     256             :                  */
     257         156 :                 break;
     258        1488 :             case MULTIRANGE_AFTER_RANGE:
     259        1488 :                 if (ch == ',')
     260         480 :                     parse_state = MULTIRANGE_BEFORE_RANGE;
     261        1008 :                 else if (ch == '}')
     262         990 :                     parse_state = MULTIRANGE_FINISHED;
     263             :                 else
     264          18 :                     ereturn(escontext, (Datum) 0,
     265             :                             (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
     266             :                              errmsg("malformed multirange literal: \"%s\"",
     267             :                                     input_str),
     268             :                              errdetail("Expected comma or end of multirange.")));
     269        1470 :                 break;
     270          18 :             case MULTIRANGE_IN_RANGE_QUOTED_ESCAPED:
     271             : 
     272             :                 /*
     273             :                  * We will include this character into range_str once we find
     274             :                  * the end of the range value.
     275             :                  */
     276          18 :                 parse_state = MULTIRANGE_IN_RANGE_QUOTED;
     277          18 :                 break;
     278           0 :             default:
     279           0 :                 elog(ERROR, "unknown parse state: %d", parse_state);
     280             :         }
     281             :     }
     282             : 
     283             :     /* consume whitespace */
     284        1302 :     while (*ptr != '\0' && isspace((unsigned char) *ptr))
     285          24 :         ptr++;
     286             : 
     287        1278 :     if (*ptr != '\0')
     288           6 :         ereturn(escontext, (Datum) 0,
     289             :                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
     290             :                  errmsg("malformed multirange literal: \"%s\"",
     291             :                         input_str),
     292             :                  errdetail("Junk after closing right brace.")));
     293             : 
     294        1272 :     ret = make_multirange(mltrngtypoid, rangetyp, range_count, ranges);
     295        1272 :     PG_RETURN_MULTIRANGE_P(ret);
     296             : }
     297             : 
     298             : Datum
     299        2690 : multirange_out(PG_FUNCTION_ARGS)
     300             : {
     301        2690 :     MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0);
     302        2690 :     Oid         mltrngtypoid = MultirangeTypeGetOid(multirange);
     303             :     MultirangeIOData *cache;
     304             :     StringInfoData buf;
     305             :     RangeType  *range;
     306             :     char       *rangeStr;
     307             :     int32       range_count;
     308             :     int32       i;
     309             :     RangeType **ranges;
     310             : 
     311        2690 :     cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_output);
     312             : 
     313        2690 :     initStringInfo(&buf);
     314             : 
     315        2690 :     appendStringInfoChar(&buf, '{');
     316             : 
     317        2690 :     multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges);
     318        5136 :     for (i = 0; i < range_count; i++)
     319             :     {
     320        2446 :         if (i > 0)
     321         266 :             appendStringInfoChar(&buf, ',');
     322        2446 :         range = ranges[i];
     323        2446 :         rangeStr = OutputFunctionCall(&cache->typioproc, RangeTypePGetDatum(range));
     324        2446 :         appendStringInfoString(&buf, rangeStr);
     325             :     }
     326             : 
     327        2690 :     appendStringInfoChar(&buf, '}');
     328             : 
     329        2690 :     PG_RETURN_CSTRING(buf.data);
     330             : }
     331             : 
     332             : /*
     333             :  * Binary representation: First an int32-sized count of ranges, followed by
     334             :  * ranges in their native binary representation.
     335             :  */
     336             : Datum
     337           0 : multirange_recv(PG_FUNCTION_ARGS)
     338             : {
     339           0 :     StringInfo  buf = (StringInfo) PG_GETARG_POINTER(0);
     340           0 :     Oid         mltrngtypoid = PG_GETARG_OID(1);
     341           0 :     int32       typmod = PG_GETARG_INT32(2);
     342             :     MultirangeIOData *cache;
     343             :     uint32      range_count;
     344             :     RangeType **ranges;
     345             :     MultirangeType *ret;
     346             :     StringInfoData tmpbuf;
     347             : 
     348           0 :     cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_receive);
     349             : 
     350           0 :     range_count = pq_getmsgint(buf, 4);
     351           0 :     ranges = palloc(range_count * sizeof(RangeType *));
     352             : 
     353           0 :     initStringInfo(&tmpbuf);
     354           0 :     for (int i = 0; i < range_count; i++)
     355             :     {
     356           0 :         uint32      range_len = pq_getmsgint(buf, 4);
     357           0 :         const char *range_data = pq_getmsgbytes(buf, range_len);
     358             : 
     359           0 :         resetStringInfo(&tmpbuf);
     360           0 :         appendBinaryStringInfo(&tmpbuf, range_data, range_len);
     361             : 
     362           0 :         ranges[i] = DatumGetRangeTypeP(ReceiveFunctionCall(&cache->typioproc,
     363             :                                                            &tmpbuf,
     364             :                                                            cache->typioparam,
     365             :                                                            typmod));
     366             :     }
     367           0 :     pfree(tmpbuf.data);
     368             : 
     369           0 :     pq_getmsgend(buf);
     370             : 
     371           0 :     ret = make_multirange(mltrngtypoid, cache->typcache->rngtype,
     372             :                           range_count, ranges);
     373           0 :     PG_RETURN_MULTIRANGE_P(ret);
     374             : }
     375             : 
     376             : Datum
     377           0 : multirange_send(PG_FUNCTION_ARGS)
     378             : {
     379           0 :     MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0);
     380           0 :     Oid         mltrngtypoid = MultirangeTypeGetOid(multirange);
     381           0 :     StringInfo  buf = makeStringInfo();
     382             :     RangeType **ranges;
     383             :     int32       range_count;
     384             :     MultirangeIOData *cache;
     385             : 
     386           0 :     cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_send);
     387             : 
     388             :     /* construct output */
     389           0 :     pq_begintypsend(buf);
     390             : 
     391           0 :     pq_sendint32(buf, multirange->rangeCount);
     392             : 
     393           0 :     multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges);
     394           0 :     for (int i = 0; i < range_count; i++)
     395             :     {
     396             :         Datum       range;
     397             : 
     398           0 :         range = RangeTypePGetDatum(ranges[i]);
     399           0 :         range = PointerGetDatum(SendFunctionCall(&cache->typioproc, range));
     400             : 
     401           0 :         pq_sendint32(buf, VARSIZE(range) - VARHDRSZ);
     402           0 :         pq_sendbytes(buf, VARDATA(range), VARSIZE(range) - VARHDRSZ);
     403             :     }
     404             : 
     405           0 :     PG_RETURN_BYTEA_P(pq_endtypsend(buf));
     406             : }
     407             : 
     408             : /*
     409             :  * get_multirange_io_data: get cached information needed for multirange type I/O
     410             :  *
     411             :  * The multirange I/O functions need a bit more cached info than other multirange
     412             :  * functions, so they store a MultirangeIOData struct in fn_extra, not just a
     413             :  * pointer to a type cache entry.
     414             :  */
     415             : static MultirangeIOData *
     416        4070 : get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func)
     417             : {
     418        4070 :     MultirangeIOData *cache = (MultirangeIOData *) fcinfo->flinfo->fn_extra;
     419             : 
     420        4070 :     if (cache == NULL || cache->typcache->type_id != mltrngtypid)
     421             :     {
     422             :         Oid         typiofunc;
     423             :         int16       typlen;
     424             :         bool        typbyval;
     425             :         char        typalign;
     426             :         char        typdelim;
     427             : 
     428        2772 :         cache = (MultirangeIOData *) MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
     429             :                                                         sizeof(MultirangeIOData));
     430        2772 :         cache->typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO);
     431        2772 :         if (cache->typcache->rngtype == NULL)
     432           0 :             elog(ERROR, "type %u is not a multirange type", mltrngtypid);
     433             : 
     434             :         /* get_type_io_data does more than we need, but is convenient */
     435        2772 :         get_type_io_data(cache->typcache->rngtype->type_id,
     436             :                          func,
     437             :                          &typlen,
     438             :                          &typbyval,
     439             :                          &typalign,
     440             :                          &typdelim,
     441             :                          &cache->typioparam,
     442             :                          &typiofunc);
     443             : 
     444        2772 :         if (!OidIsValid(typiofunc))
     445             :         {
     446             :             /* this could only happen for receive or send */
     447           0 :             if (func == IOFunc_receive)
     448           0 :                 ereport(ERROR,
     449             :                         (errcode(ERRCODE_UNDEFINED_FUNCTION),
     450             :                          errmsg("no binary input function available for type %s",
     451             :                                 format_type_be(cache->typcache->rngtype->type_id))));
     452             :             else
     453           0 :                 ereport(ERROR,
     454             :                         (errcode(ERRCODE_UNDEFINED_FUNCTION),
     455             :                          errmsg("no binary output function available for type %s",
     456             :                                 format_type_be(cache->typcache->rngtype->type_id))));
     457             :         }
     458        2772 :         fmgr_info_cxt(typiofunc, &cache->typioproc,
     459        2772 :                       fcinfo->flinfo->fn_mcxt);
     460             : 
     461        2772 :         fcinfo->flinfo->fn_extra = (void *) cache;
     462             :     }
     463             : 
     464        4070 :     return cache;
     465             : }
     466             : 
     467             : /*
     468             :  * Converts a list of arbitrary ranges into a list that is sorted and merged.
     469             :  * Changes the contents of `ranges`.
     470             :  *
     471             :  * Returns the number of slots actually used, which may be less than
     472             :  * input_range_count but never more.
     473             :  *
     474             :  * We assume that no input ranges are null, but empties are okay.
     475             :  */
     476             : static int32
     477       25126 : multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count,
     478             :                         RangeType **ranges)
     479             : {
     480       25126 :     RangeType  *lastRange = NULL;
     481             :     RangeType  *currentRange;
     482             :     int32       i;
     483       25126 :     int32       output_range_count = 0;
     484             : 
     485             :     /* Sort the ranges so we can find the ones that overlap/meet. */
     486       25126 :     qsort_arg(ranges, input_range_count, sizeof(RangeType *), range_compare,
     487             :               rangetyp);
     488             : 
     489             :     /* Now merge where possible: */
     490       76198 :     for (i = 0; i < input_range_count; i++)
     491             :     {
     492       51072 :         currentRange = ranges[i];
     493       51072 :         if (RangeIsEmpty(currentRange))
     494         186 :             continue;
     495             : 
     496       50886 :         if (lastRange == NULL)
     497             :         {
     498       24196 :             ranges[output_range_count++] = lastRange = currentRange;
     499       24196 :             continue;
     500             :         }
     501             : 
     502             :         /*
     503             :          * range_adjacent_internal gives true if *either* A meets B or B meets
     504             :          * A, which is not quite want we want, but we rely on the sorting
     505             :          * above to rule out B meets A ever happening.
     506             :          */
     507       26690 :         if (range_adjacent_internal(rangetyp, lastRange, currentRange))
     508             :         {
     509             :             /* The two ranges touch (without overlap), so merge them: */
     510        1406 :             ranges[output_range_count - 1] = lastRange =
     511        1406 :                 range_union_internal(rangetyp, lastRange, currentRange, false);
     512             :         }
     513       25284 :         else if (range_before_internal(rangetyp, lastRange, currentRange))
     514             :         {
     515             :             /* There's a gap, so make a new entry: */
     516       25164 :             lastRange = ranges[output_range_count] = currentRange;
     517       25164 :             output_range_count++;
     518             :         }
     519             :         else
     520             :         {
     521             :             /* They must overlap, so merge them: */
     522         120 :             ranges[output_range_count - 1] = lastRange =
     523         120 :                 range_union_internal(rangetyp, lastRange, currentRange, true);
     524             :         }
     525             :     }
     526             : 
     527       25126 :     return output_range_count;
     528             : }
     529             : 
     530             : /*
     531             :  *----------------------------------------------------------
     532             :  * SUPPORT FUNCTIONS
     533             :  *
     534             :  *   These functions aren't in pg_proc, but are useful for
     535             :  *   defining new generic multirange functions in C.
     536             :  *----------------------------------------------------------
     537             :  */
     538             : 
     539             : /*
     540             :  * multirange_get_typcache: get cached information about a multirange type
     541             :  *
     542             :  * This is for use by multirange-related functions that follow the convention
     543             :  * of using the fn_extra field as a pointer to the type cache entry for
     544             :  * the multirange type.  Functions that need to cache more information than
     545             :  * that must fend for themselves.
     546             :  */
     547             : TypeCacheEntry *
     548     1255312 : multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid)
     549             : {
     550     1255312 :     TypeCacheEntry *typcache = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
     551             : 
     552     1255312 :     if (typcache == NULL ||
     553     1245666 :         typcache->type_id != mltrngtypid)
     554             :     {
     555        9646 :         typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO);
     556        9646 :         if (typcache->rngtype == NULL)
     557           0 :             elog(ERROR, "type %u is not a multirange type", mltrngtypid);
     558        9646 :         fcinfo->flinfo->fn_extra = (void *) typcache;
     559             :     }
     560             : 
     561     1255312 :     return typcache;
     562             : }
     563             : 
     564             : 
     565             : /*
     566             :  * Estimate size occupied by serialized multirange.
     567             :  */
     568             : static Size
     569       25126 : multirange_size_estimate(TypeCacheEntry *rangetyp, int32 range_count,
     570             :                          RangeType **ranges)
     571             : {
     572       25126 :     char        elemalign = rangetyp->rngelemtype->typalign;
     573             :     Size        size;
     574             :     int32       i;
     575             : 
     576             :     /*
     577             :      * Count space for MultirangeType struct, items and flags.
     578             :      */
     579       25126 :     size = att_align_nominal(sizeof(MultirangeType) +
     580             :                              Max(range_count - 1, 0) * sizeof(uint32) +
     581             :                              range_count * sizeof(uint8), elemalign);
     582             : 
     583             :     /* Count space for range bounds */
     584       74486 :     for (i = 0; i < range_count; i++)
     585       49360 :         size += att_align_nominal(VARSIZE(ranges[i]) -
     586             :                                   sizeof(RangeType) -
     587             :                                   sizeof(char), elemalign);
     588             : 
     589       25126 :     return size;
     590             : }
     591             : 
     592             : /*
     593             :  * Write multirange data into pre-allocated space.
     594             :  */
     595             : static void
     596       25126 : write_multirange_data(MultirangeType *multirange, TypeCacheEntry *rangetyp,
     597             :                       int32 range_count, RangeType **ranges)
     598             : {
     599             :     uint32     *items;
     600       25126 :     uint32      prev_offset = 0;
     601             :     uint8      *flags;
     602             :     int32       i;
     603             :     Pointer     begin,
     604             :                 ptr;
     605       25126 :     char        elemalign = rangetyp->rngelemtype->typalign;
     606             : 
     607       25126 :     items = MultirangeGetItemsPtr(multirange);
     608       25126 :     flags = MultirangeGetFlagsPtr(multirange);
     609       25126 :     ptr = begin = MultirangeGetBoundariesPtr(multirange, elemalign);
     610       74486 :     for (i = 0; i < range_count; i++)
     611             :     {
     612             :         uint32      len;
     613             : 
     614       49360 :         if (i > 0)
     615             :         {
     616             :             /*
     617             :              * Every range, except the first one, has an item.  Every
     618             :              * MULTIRANGE_ITEM_OFFSET_STRIDE item contains an offset, others
     619             :              * contain lengths.
     620             :              */
     621       25164 :             items[i - 1] = ptr - begin;
     622       25164 :             if ((i % MULTIRANGE_ITEM_OFFSET_STRIDE) != 0)
     623       25164 :                 items[i - 1] -= prev_offset;
     624             :             else
     625           0 :                 items[i - 1] |= MULTIRANGE_ITEM_OFF_BIT;
     626       25164 :             prev_offset = ptr - begin;
     627             :         }
     628       49360 :         flags[i] = *((Pointer) ranges[i] + VARSIZE(ranges[i]) - sizeof(char));
     629       49360 :         len = VARSIZE(ranges[i]) - sizeof(RangeType) - sizeof(char);
     630       49360 :         memcpy(ptr, (Pointer) (ranges[i] + 1), len);
     631       49360 :         ptr += att_align_nominal(len, elemalign);
     632             :     }
     633       25126 : }
     634             : 
     635             : 
     636             : /*
     637             :  * This serializes the multirange from a list of non-null ranges.  It also
     638             :  * sorts the ranges and merges any that touch.  The ranges should already be
     639             :  * detoasted, and there should be no NULLs.  This should be used by most
     640             :  * callers.
     641             :  *
     642             :  * Note that we may change the `ranges` parameter (the pointers, but not
     643             :  * any already-existing RangeType contents).
     644             :  */
     645             : MultirangeType *
     646       25126 : make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count,
     647             :                 RangeType **ranges)
     648             : {
     649             :     MultirangeType *multirange;
     650             :     Size        size;
     651             : 
     652             :     /* Sort and merge input ranges. */
     653       25126 :     range_count = multirange_canonicalize(rangetyp, range_count, ranges);
     654             : 
     655             :     /* Note: zero-fill is required here, just as in heap tuples */
     656       25126 :     size = multirange_size_estimate(rangetyp, range_count, ranges);
     657       25126 :     multirange = palloc0(size);
     658       25126 :     SET_VARSIZE(multirange, size);
     659             : 
     660             :     /* Now fill in the datum */
     661       25126 :     multirange->multirangetypid = mltrngtypoid;
     662       25126 :     multirange->rangeCount = range_count;
     663             : 
     664       25126 :     write_multirange_data(multirange, rangetyp, range_count, ranges);
     665             : 
     666       25126 :     return multirange;
     667             : }
     668             : 
     669             : /*
     670             :  * Get offset of bounds values of the i'th range in the multirange.
     671             :  */
     672             : static uint32
     673     1621520 : multirange_get_bounds_offset(const MultirangeType *multirange, int32 i)
     674             : {
     675     1621520 :     uint32     *items = MultirangeGetItemsPtr(multirange);
     676     1621520 :     uint32      offset = 0;
     677             : 
     678             :     /*
     679             :      * Summarize lengths till we meet an offset.
     680             :      */
     681     2624118 :     while (i > 0)
     682             :     {
     683     1002598 :         offset += MULTIRANGE_ITEM_GET_OFFLEN(items[i - 1]);
     684     1002598 :         if (MULTIRANGE_ITEM_HAS_OFF(items[i - 1]))
     685           0 :             break;
     686     1002598 :         i--;
     687             :     }
     688     1621520 :     return offset;
     689             : }
     690             : 
     691             : /*
     692             :  * Fetch the i'th range from the multirange.
     693             :  */
     694             : RangeType *
     695        3532 : multirange_get_range(TypeCacheEntry *rangetyp,
     696             :                      const MultirangeType *multirange, int i)
     697             : {
     698             :     uint32      offset;
     699             :     uint8       flags;
     700             :     Pointer     begin,
     701             :                 ptr;
     702        3532 :     int16       typlen = rangetyp->rngelemtype->typlen;
     703        3532 :     char        typalign = rangetyp->rngelemtype->typalign;
     704             :     uint32      len;
     705             :     RangeType  *range;
     706             : 
     707             :     Assert(i < multirange->rangeCount);
     708             : 
     709        3532 :     offset = multirange_get_bounds_offset(multirange, i);
     710        3532 :     flags = MultirangeGetFlagsPtr(multirange)[i];
     711        3532 :     ptr = begin = MultirangeGetBoundariesPtr(multirange, typalign) + offset;
     712             : 
     713             :     /*
     714             :      * Calculate the size of bound values.  In principle, we could get offset
     715             :      * of the next range bound values and calculate accordingly.  But range
     716             :      * bound values are aligned, so we have to walk the values to get the
     717             :      * exact size.
     718             :      */
     719        3532 :     if (RANGE_HAS_LBOUND(flags))
     720        2884 :         ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
     721        3532 :     if (RANGE_HAS_UBOUND(flags))
     722             :     {
     723        2812 :         ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
     724        2812 :         ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
     725             :     }
     726        3532 :     len = (ptr - begin) + sizeof(RangeType) + sizeof(uint8);
     727             : 
     728        3532 :     range = palloc0(len);
     729        3532 :     SET_VARSIZE(range, len);
     730        3532 :     range->rangetypid = rangetyp->type_id;
     731             : 
     732        3532 :     memcpy(range + 1, begin, ptr - begin);
     733        3532 :     *((uint8 *) (range + 1) + (ptr - begin)) = flags;
     734             : 
     735        3532 :     return range;
     736             : }
     737             : 
     738             : /*
     739             :  * Fetch bounds from the i'th range of the multirange.  This is the shortcut for
     740             :  * doing the same thing as multirange_get_range() + range_deserialize(), but
     741             :  * performing fewer operations.
     742             :  */
     743             : void
     744     1617988 : multirange_get_bounds(TypeCacheEntry *rangetyp,
     745             :                       const MultirangeType *multirange,
     746             :                       uint32 i, RangeBound *lower, RangeBound *upper)
     747             : {
     748             :     uint32      offset;
     749             :     uint8       flags;
     750             :     Pointer     ptr;
     751     1617988 :     int16       typlen = rangetyp->rngelemtype->typlen;
     752     1617988 :     char        typalign = rangetyp->rngelemtype->typalign;
     753     1617988 :     bool        typbyval = rangetyp->rngelemtype->typbyval;
     754             :     Datum       lbound;
     755             :     Datum       ubound;
     756             : 
     757             :     Assert(i < multirange->rangeCount);
     758             : 
     759     1617988 :     offset = multirange_get_bounds_offset(multirange, i);
     760     1617988 :     flags = MultirangeGetFlagsPtr(multirange)[i];
     761     1617988 :     ptr = MultirangeGetBoundariesPtr(multirange, typalign) + offset;
     762             : 
     763             :     /* multirange can't contain empty ranges */
     764             :     Assert((flags & RANGE_EMPTY) == 0);
     765             : 
     766             :     /* fetch lower bound, if any */
     767     1617988 :     if (RANGE_HAS_LBOUND(flags))
     768             :     {
     769             :         /* att_align_pointer cannot be necessary here */
     770     1600384 :         lbound = fetch_att(ptr, typbyval, typlen);
     771     1600384 :         ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
     772             :     }
     773             :     else
     774       17604 :         lbound = (Datum) 0;
     775             : 
     776             :     /* fetch upper bound, if any */
     777     1617988 :     if (RANGE_HAS_UBOUND(flags))
     778             :     {
     779     1601758 :         ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
     780     1601758 :         ubound = fetch_att(ptr, typbyval, typlen);
     781             :         /* no need for att_addlength_pointer */
     782             :     }
     783             :     else
     784       16230 :         ubound = (Datum) 0;
     785             : 
     786             :     /* emit results */
     787     1617988 :     lower->val = lbound;
     788     1617988 :     lower->infinite = (flags & RANGE_LB_INF) != 0;
     789     1617988 :     lower->inclusive = (flags & RANGE_LB_INC) != 0;
     790     1617988 :     lower->lower = true;
     791             : 
     792     1617988 :     upper->val = ubound;
     793     1617988 :     upper->infinite = (flags & RANGE_UB_INF) != 0;
     794     1617988 :     upper->inclusive = (flags & RANGE_UB_INC) != 0;
     795     1617988 :     upper->lower = false;
     796     1617988 : }
     797             : 
     798             : /*
     799             :  * Construct union range from the multirange.
     800             :  */
     801             : RangeType *
     802       23196 : multirange_get_union_range(TypeCacheEntry *rangetyp,
     803             :                            const MultirangeType *mr)
     804             : {
     805             :     RangeBound  lower,
     806             :                 upper,
     807             :                 tmp;
     808             : 
     809       23196 :     if (MultirangeIsEmpty(mr))
     810        3042 :         return make_empty_range(rangetyp);
     811             : 
     812       20154 :     multirange_get_bounds(rangetyp, mr, 0, &lower, &tmp);
     813       20154 :     multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper);
     814             : 
     815       20154 :     return make_range(rangetyp, &lower, &upper, false, NULL);
     816             : }
     817             : 
     818             : 
     819             : /*
     820             :  * multirange_deserialize: deconstruct a multirange value
     821             :  *
     822             :  * NB: the given multirange object must be fully detoasted; it cannot have a
     823             :  * short varlena header.
     824             :  */
     825             : void
     826        3656 : multirange_deserialize(TypeCacheEntry *rangetyp,
     827             :                        const MultirangeType *multirange, int32 *range_count,
     828             :                        RangeType ***ranges)
     829             : {
     830        3656 :     *range_count = multirange->rangeCount;
     831             : 
     832             :     /* Convert each ShortRangeType into a RangeType */
     833        3656 :     if (*range_count > 0)
     834             :     {
     835             :         int         i;
     836             : 
     837        3026 :         *ranges = palloc(*range_count * sizeof(RangeType *));
     838        6498 :         for (i = 0; i < *range_count; i++)
     839        3472 :             (*ranges)[i] = multirange_get_range(rangetyp, multirange, i);
     840             :     }
     841             :     else
     842             :     {
     843         630 :         *ranges = NULL;
     844             :     }
     845        3656 : }
     846             : 
     847             : MultirangeType *
     848          18 : make_empty_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp)
     849             : {
     850          18 :     return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
     851             : }
     852             : 
     853             : /*
     854             :  * Similar to range_overlaps_internal(), but takes range bounds instead of
     855             :  * ranges as arguments.
     856             :  */
     857             : static bool
     858       58344 : range_bounds_overlaps(TypeCacheEntry *typcache,
     859             :                       RangeBound *lower1, RangeBound *upper1,
     860             :                       RangeBound *lower2, RangeBound *upper2)
     861             : {
     862      114432 :     if (range_cmp_bounds(typcache, lower1, lower2) >= 0 &&
     863       56088 :         range_cmp_bounds(typcache, lower1, upper2) <= 0)
     864         876 :         return true;
     865             : 
     866       59724 :     if (range_cmp_bounds(typcache, lower2, lower1) >= 0 &&
     867        2256 :         range_cmp_bounds(typcache, lower2, upper1) <= 0)
     868        2256 :         return true;
     869             : 
     870       55212 :     return false;
     871             : }
     872             : 
     873             : /*
     874             :  * Similar to range_contains_internal(), but takes range bounds instead of
     875             :  * ranges as arguments.
     876             :  */
     877             : static bool
     878       96492 : range_bounds_contains(TypeCacheEntry *typcache,
     879             :                       RangeBound *lower1, RangeBound *upper1,
     880             :                       RangeBound *lower2, RangeBound *upper2)
     881             : {
     882      127398 :     if (range_cmp_bounds(typcache, lower1, lower2) <= 0 &&
     883       30906 :         range_cmp_bounds(typcache, upper1, upper2) >= 0)
     884        8902 :         return true;
     885             : 
     886       87590 :     return false;
     887             : }
     888             : 
     889             : /*
     890             :  * Check if the given key matches any range in multirange using binary search.
     891             :  * If the required range isn't found, that counts as a mismatch.  When the
     892             :  * required range is found, the comparison function can still report this as
     893             :  * either match or mismatch.  For instance, if we search for containment, we can
     894             :  * found a range, which is overlapping but not containing the key range, and
     895             :  * that would count as a mismatch.
     896             :  */
     897             : static bool
     898      159516 : multirange_bsearch_match(TypeCacheEntry *typcache, const MultirangeType *mr,
     899             :                          void *key, multirange_bsearch_comparison cmp_func)
     900             : {
     901             :     uint32      l,
     902             :                 u,
     903             :                 idx;
     904             :     int         comparison;
     905      159516 :     bool        match = false;
     906             : 
     907      159516 :     l = 0;
     908      159516 :     u = mr->rangeCount;
     909      418680 :     while (l < u)
     910             :     {
     911             :         RangeBound  lower,
     912             :                     upper;
     913             : 
     914      281286 :         idx = (l + u) / 2;
     915      281286 :         multirange_get_bounds(typcache, mr, idx, &lower, &upper);
     916      281286 :         comparison = (*cmp_func) (typcache, &lower, &upper, key, &match);
     917             : 
     918      281286 :         if (comparison < 0)
     919       94456 :             u = idx;
     920      186830 :         else if (comparison > 0)
     921      164708 :             l = idx + 1;
     922             :         else
     923       22122 :             return match;
     924             :     }
     925             : 
     926      137394 :     return false;
     927             : }
     928             : 
     929             : /*
     930             :  *----------------------------------------------------------
     931             :  * GENERIC FUNCTIONS
     932             :  *----------------------------------------------------------
     933             :  */
     934             : 
     935             : /*
     936             :  * Construct multirange value from zero or more ranges.  Since this is a
     937             :  * variadic function we get passed an array.  The array must contain ranges
     938             :  * that match our return value, and there must be no NULLs.
     939             :  */
     940             : Datum
     941       13806 : multirange_constructor2(PG_FUNCTION_ARGS)
     942             : {
     943       13806 :     Oid         mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
     944             :     Oid         rngtypid;
     945             :     TypeCacheEntry *typcache;
     946             :     TypeCacheEntry *rangetyp;
     947             :     ArrayType  *rangeArray;
     948             :     int         range_count;
     949             :     Datum      *elements;
     950             :     bool       *nulls;
     951             :     RangeType **ranges;
     952             :     int         dims;
     953             :     int         i;
     954             : 
     955       13806 :     typcache = multirange_get_typcache(fcinfo, mltrngtypid);
     956       13806 :     rangetyp = typcache->rngtype;
     957             : 
     958             :     /*
     959             :      * A no-arg invocation should call multirange_constructor0 instead, but
     960             :      * returning an empty range is what that does.
     961             :      */
     962             : 
     963       13806 :     if (PG_NARGS() == 0)
     964           0 :         PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL));
     965             : 
     966             :     /*
     967             :      * This check should be guaranteed by our signature, but let's do it just
     968             :      * in case.
     969             :      */
     970             : 
     971       13806 :     if (PG_ARGISNULL(0))
     972           0 :         elog(ERROR,
     973             :              "multirange values cannot contain null members");
     974             : 
     975       13806 :     rangeArray = PG_GETARG_ARRAYTYPE_P(0);
     976             : 
     977       13806 :     dims = ARR_NDIM(rangeArray);
     978       13806 :     if (dims > 1)
     979           0 :         ereport(ERROR,
     980             :                 (errcode(ERRCODE_CARDINALITY_VIOLATION),
     981             :                  errmsg("multiranges cannot be constructed from multidimensional arrays")));
     982             : 
     983       13806 :     rngtypid = ARR_ELEMTYPE(rangeArray);
     984       13806 :     if (rngtypid != rangetyp->type_id)
     985           0 :         elog(ERROR, "type %u does not match constructor type", rngtypid);
     986             : 
     987             :     /*
     988             :      * Be careful: we can still be called with zero ranges, like this:
     989             :      * `int4multirange(variadic '{}'::int4range[])
     990             :      */
     991       13806 :     if (dims == 0)
     992             :     {
     993           6 :         range_count = 0;
     994           6 :         ranges = NULL;
     995             :     }
     996             :     else
     997             :     {
     998       13800 :         deconstruct_array(rangeArray, rngtypid, rangetyp->typlen, rangetyp->typbyval,
     999       13800 :                           rangetyp->typalign, &elements, &nulls, &range_count);
    1000             : 
    1001       13800 :         ranges = palloc0(range_count * sizeof(RangeType *));
    1002       53412 :         for (i = 0; i < range_count; i++)
    1003             :         {
    1004       39612 :             if (nulls[i])
    1005           0 :                 ereport(ERROR,
    1006             :                         (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
    1007             :                          errmsg("multirange values cannot contain null members")));
    1008             : 
    1009             :             /* make_multirange will do its own copy */
    1010       39612 :             ranges[i] = DatumGetRangeTypeP(elements[i]);
    1011             :         }
    1012             :     }
    1013             : 
    1014       13806 :     PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, range_count, ranges));
    1015             : }
    1016             : 
    1017             : /*
    1018             :  * Construct multirange value from a single range.  It'd be nice if we could
    1019             :  * just use multirange_constructor2 for this case, but we need a non-variadic
    1020             :  * single-arg function to let us define a CAST from a range to its multirange.
    1021             :  */
    1022             : Datum
    1023        8352 : multirange_constructor1(PG_FUNCTION_ARGS)
    1024             : {
    1025        8352 :     Oid         mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
    1026             :     Oid         rngtypid;
    1027             :     TypeCacheEntry *typcache;
    1028             :     TypeCacheEntry *rangetyp;
    1029             :     RangeType  *range;
    1030             : 
    1031        8352 :     typcache = multirange_get_typcache(fcinfo, mltrngtypid);
    1032        8352 :     rangetyp = typcache->rngtype;
    1033             : 
    1034             :     /*
    1035             :      * This check should be guaranteed by our signature, but let's do it just
    1036             :      * in case.
    1037             :      */
    1038             : 
    1039        8352 :     if (PG_ARGISNULL(0))
    1040           0 :         elog(ERROR,
    1041             :              "multirange values cannot contain null members");
    1042             : 
    1043        8352 :     range = PG_GETARG_RANGE_P(0);
    1044             : 
    1045             :     /* Make sure the range type matches. */
    1046        8352 :     rngtypid = RangeTypeGetOid(range);
    1047        8352 :     if (rngtypid != rangetyp->type_id)
    1048           0 :         elog(ERROR, "type %u does not match constructor type", rngtypid);
    1049             : 
    1050        8352 :     PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 1, &range));
    1051             : }
    1052             : 
    1053             : /*
    1054             :  * Constructor just like multirange_constructor1, but opr_sanity gets angry
    1055             :  * if the same internal function handles multiple functions with different arg
    1056             :  * counts.
    1057             :  */
    1058             : Datum
    1059         372 : multirange_constructor0(PG_FUNCTION_ARGS)
    1060             : {
    1061             :     Oid         mltrngtypid;
    1062             :     TypeCacheEntry *typcache;
    1063             :     TypeCacheEntry *rangetyp;
    1064             : 
    1065             :     /* This should always be called without arguments */
    1066         372 :     if (PG_NARGS() != 0)
    1067           0 :         elog(ERROR,
    1068             :              "niladic multirange constructor must not receive arguments");
    1069             : 
    1070         372 :     mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
    1071         372 :     typcache = multirange_get_typcache(fcinfo, mltrngtypid);
    1072         372 :     rangetyp = typcache->rngtype;
    1073             : 
    1074         372 :     PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL));
    1075             : }
    1076             : 
    1077             : 
    1078             : /* multirange, multirange -> multirange type functions */
    1079             : 
    1080             : /* multirange union */
    1081             : Datum
    1082          54 : multirange_union(PG_FUNCTION_ARGS)
    1083             : {
    1084          54 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1085          54 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1086             :     TypeCacheEntry *typcache;
    1087             :     int32       range_count1;
    1088             :     int32       range_count2;
    1089             :     int32       range_count3;
    1090             :     RangeType **ranges1;
    1091             :     RangeType **ranges2;
    1092             :     RangeType **ranges3;
    1093             : 
    1094          54 :     if (MultirangeIsEmpty(mr1))
    1095          12 :         PG_RETURN_MULTIRANGE_P(mr2);
    1096          42 :     if (MultirangeIsEmpty(mr2))
    1097           6 :         PG_RETURN_MULTIRANGE_P(mr1);
    1098             : 
    1099          36 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    1100             : 
    1101          36 :     multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
    1102          36 :     multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
    1103             : 
    1104          36 :     range_count3 = range_count1 + range_count2;
    1105          36 :     ranges3 = palloc0(range_count3 * sizeof(RangeType *));
    1106          36 :     memcpy(ranges3, ranges1, range_count1 * sizeof(RangeType *));
    1107          36 :     memcpy(ranges3 + range_count1, ranges2, range_count2 * sizeof(RangeType *));
    1108          36 :     PG_RETURN_MULTIRANGE_P(make_multirange(typcache->type_id, typcache->rngtype,
    1109             :                                            range_count3, ranges3));
    1110             : }
    1111             : 
    1112             : /* multirange minus */
    1113             : Datum
    1114         120 : multirange_minus(PG_FUNCTION_ARGS)
    1115             : {
    1116         120 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1117         120 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1118         120 :     Oid         mltrngtypoid = MultirangeTypeGetOid(mr1);
    1119             :     TypeCacheEntry *typcache;
    1120             :     TypeCacheEntry *rangetyp;
    1121             :     int32       range_count1;
    1122             :     int32       range_count2;
    1123             :     RangeType **ranges1;
    1124             :     RangeType **ranges2;
    1125             : 
    1126         120 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    1127         120 :     rangetyp = typcache->rngtype;
    1128             : 
    1129         120 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    1130          24 :         PG_RETURN_MULTIRANGE_P(mr1);
    1131             : 
    1132          96 :     multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
    1133          96 :     multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
    1134             : 
    1135          96 :     PG_RETURN_MULTIRANGE_P(multirange_minus_internal(mltrngtypoid,
    1136             :                                                      rangetyp,
    1137             :                                                      range_count1,
    1138             :                                                      ranges1,
    1139             :                                                      range_count2,
    1140             :                                                      ranges2));
    1141             : }
    1142             : 
    1143             : MultirangeType *
    1144          96 : multirange_minus_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
    1145             :                           int32 range_count1, RangeType **ranges1,
    1146             :                           int32 range_count2, RangeType **ranges2)
    1147             : {
    1148             :     RangeType  *r1;
    1149             :     RangeType  *r2;
    1150             :     RangeType **ranges3;
    1151             :     int32       range_count3;
    1152             :     int32       i1;
    1153             :     int32       i2;
    1154             : 
    1155             :     /*
    1156             :      * Worst case: every range in ranges1 makes a different cut to some range
    1157             :      * in ranges2.
    1158             :      */
    1159          96 :     ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
    1160          96 :     range_count3 = 0;
    1161             : 
    1162             :     /*
    1163             :      * For each range in mr1, keep subtracting until it's gone or the ranges
    1164             :      * in mr2 have passed it. After a subtraction we assign what's left back
    1165             :      * to r1. The parallel progress through mr1 and mr2 is similar to
    1166             :      * multirange_overlaps_multirange_internal.
    1167             :      */
    1168          96 :     r2 = ranges2[0];
    1169         234 :     for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
    1170             :     {
    1171         138 :         r1 = ranges1[i1];
    1172             : 
    1173             :         /* Discard r2s while r2 << r1 */
    1174         156 :         while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
    1175             :         {
    1176          18 :             r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
    1177             :         }
    1178             : 
    1179         174 :         while (r2 != NULL)
    1180             :         {
    1181         132 :             if (range_split_internal(rangetyp, r1, r2, &ranges3[range_count3], &r1))
    1182             :             {
    1183             :                 /*
    1184             :                  * If r2 takes a bite out of the middle of r1, we need two
    1185             :                  * outputs
    1186             :                  */
    1187          18 :                 range_count3++;
    1188          18 :                 r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
    1189             :             }
    1190         114 :             else if (range_overlaps_internal(rangetyp, r1, r2))
    1191             :             {
    1192             :                 /*
    1193             :                  * If r2 overlaps r1, replace r1 with r1 - r2.
    1194             :                  */
    1195          66 :                 r1 = range_minus_internal(rangetyp, r1, r2);
    1196             : 
    1197             :                 /*
    1198             :                  * If r2 goes past r1, then we need to stay with it, in case
    1199             :                  * it hits future r1s. Otherwise we need to keep r1, in case
    1200             :                  * future r2s hit it. Since we already subtracted, there's no
    1201             :                  * point in using the overright/overleft calls.
    1202             :                  */
    1203          66 :                 if (RangeIsEmpty(r1) || range_before_internal(rangetyp, r1, r2))
    1204             :                     break;
    1205             :                 else
    1206          18 :                     r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
    1207             :             }
    1208             :             else
    1209             :             {
    1210             :                 /*
    1211             :                  * This and all future r2s are past r1, so keep them. Also
    1212             :                  * assign whatever is left of r1 to the result.
    1213             :                  */
    1214          48 :                 break;
    1215             :             }
    1216             :         }
    1217             : 
    1218             :         /*
    1219             :          * Nothing else can remove anything from r1, so keep it. Even if r1 is
    1220             :          * empty here, make_multirange will remove it.
    1221             :          */
    1222         138 :         ranges3[range_count3++] = r1;
    1223             :     }
    1224             : 
    1225          96 :     return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
    1226             : }
    1227             : 
    1228             : /* multirange intersection */
    1229             : Datum
    1230          84 : multirange_intersect(PG_FUNCTION_ARGS)
    1231             : {
    1232          84 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1233          84 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1234          84 :     Oid         mltrngtypoid = MultirangeTypeGetOid(mr1);
    1235             :     TypeCacheEntry *typcache;
    1236             :     TypeCacheEntry *rangetyp;
    1237             :     int32       range_count1;
    1238             :     int32       range_count2;
    1239             :     RangeType **ranges1;
    1240             :     RangeType **ranges2;
    1241             : 
    1242          84 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    1243          84 :     rangetyp = typcache->rngtype;
    1244             : 
    1245          84 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    1246          18 :         PG_RETURN_MULTIRANGE_P(make_empty_multirange(mltrngtypoid, rangetyp));
    1247             : 
    1248          66 :     multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1);
    1249          66 :     multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2);
    1250             : 
    1251          66 :     PG_RETURN_MULTIRANGE_P(multirange_intersect_internal(mltrngtypoid,
    1252             :                                                          rangetyp,
    1253             :                                                          range_count1,
    1254             :                                                          ranges1,
    1255             :                                                          range_count2,
    1256             :                                                          ranges2));
    1257             : }
    1258             : 
    1259             : MultirangeType *
    1260         162 : multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
    1261             :                               int32 range_count1, RangeType **ranges1,
    1262             :                               int32 range_count2, RangeType **ranges2)
    1263             : {
    1264             :     RangeType  *r1;
    1265             :     RangeType  *r2;
    1266             :     RangeType **ranges3;
    1267             :     int32       range_count3;
    1268             :     int32       i1;
    1269             :     int32       i2;
    1270             : 
    1271         162 :     if (range_count1 == 0 || range_count2 == 0)
    1272          60 :         return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
    1273             : 
    1274             :     /*-----------------------------------------------
    1275             :      * Worst case is a stitching pattern like this:
    1276             :      *
    1277             :      * mr1: --- --- --- ---
    1278             :      * mr2:   --- --- ---
    1279             :      * mr3:   - - - - - -
    1280             :      *
    1281             :      * That seems to be range_count1 + range_count2 - 1,
    1282             :      * but one extra won't hurt.
    1283             :      *-----------------------------------------------
    1284             :      */
    1285         102 :     ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
    1286         102 :     range_count3 = 0;
    1287             : 
    1288             :     /*
    1289             :      * For each range in mr1, keep intersecting until the ranges in mr2 have
    1290             :      * passed it. The parallel progress through mr1 and mr2 is similar to
    1291             :      * multirange_minus_multirange_internal, but we don't have to assign back
    1292             :      * to r1.
    1293             :      */
    1294         102 :     r2 = ranges2[0];
    1295         228 :     for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
    1296             :     {
    1297         138 :         r1 = ranges1[i1];
    1298             : 
    1299             :         /* Discard r2s while r2 << r1 */
    1300         150 :         while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
    1301             :         {
    1302          12 :             r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
    1303             :         }
    1304             : 
    1305         186 :         while (r2 != NULL)
    1306             :         {
    1307         174 :             if (range_overlaps_internal(rangetyp, r1, r2))
    1308             :             {
    1309             :                 /* Keep the overlapping part */
    1310         156 :                 ranges3[range_count3++] = range_intersect_internal(rangetyp, r1, r2);
    1311             : 
    1312             :                 /* If we "used up" all of r2, go to the next one... */
    1313         156 :                 if (range_overleft_internal(rangetyp, r2, r1))
    1314          48 :                     r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
    1315             : 
    1316             :                 /* ...otherwise go to the next r1 */
    1317             :                 else
    1318         108 :                     break;
    1319             :             }
    1320             :             else
    1321             :                 /* We're past r1, so move to the next one */
    1322          18 :                 break;
    1323             :         }
    1324             : 
    1325             :         /* If we're out of r2s, there can be no more intersections */
    1326         138 :         if (r2 == NULL)
    1327          12 :             break;
    1328             :     }
    1329             : 
    1330         102 :     return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
    1331             : }
    1332             : 
    1333             : /*
    1334             :  * range_agg_transfn: combine adjacent/overlapping ranges.
    1335             :  *
    1336             :  * All we do here is gather the input ranges into an array
    1337             :  * so that the finalfn can sort and combine them.
    1338             :  */
    1339             : Datum
    1340         392 : range_agg_transfn(PG_FUNCTION_ARGS)
    1341             : {
    1342             :     MemoryContext aggContext;
    1343             :     Oid         rngtypoid;
    1344             :     ArrayBuildState *state;
    1345             : 
    1346         392 :     if (!AggCheckCallContext(fcinfo, &aggContext))
    1347           0 :         elog(ERROR, "range_agg_transfn called in non-aggregate context");
    1348             : 
    1349         392 :     rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
    1350         392 :     if (!type_is_range(rngtypoid))
    1351           0 :         elog(ERROR, "range_agg must be called with a range");
    1352             : 
    1353         392 :     if (PG_ARGISNULL(0))
    1354         246 :         state = initArrayResult(rngtypoid, aggContext, false);
    1355             :     else
    1356         146 :         state = (ArrayBuildState *) PG_GETARG_POINTER(0);
    1357             : 
    1358             :     /* skip NULLs */
    1359         392 :     if (!PG_ARGISNULL(1))
    1360         368 :         accumArrayResult(state, PG_GETARG_DATUM(1), false, rngtypoid, aggContext);
    1361             : 
    1362         392 :     PG_RETURN_POINTER(state);
    1363             : }
    1364             : 
    1365             : /*
    1366             :  * range_agg_finalfn: use our internal array to merge touching ranges.
    1367             :  *
    1368             :  * Shared by range_agg_finalfn(anyrange) and
    1369             :  * multirange_agg_finalfn(anymultirange).
    1370             :  */
    1371             : Datum
    1372         766 : range_agg_finalfn(PG_FUNCTION_ARGS)
    1373             : {
    1374             :     MemoryContext aggContext;
    1375             :     Oid         mltrngtypoid;
    1376             :     TypeCacheEntry *typcache;
    1377             :     ArrayBuildState *state;
    1378             :     int32       range_count;
    1379             :     RangeType **ranges;
    1380             :     int         i;
    1381             : 
    1382         766 :     if (!AggCheckCallContext(fcinfo, &aggContext))
    1383           0 :         elog(ERROR, "range_agg_finalfn called in non-aggregate context");
    1384             : 
    1385         766 :     state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
    1386         766 :     if (state == NULL)
    1387             :         /* This shouldn't be possible, but just in case.... */
    1388         298 :         PG_RETURN_NULL();
    1389             : 
    1390             :     /* Also return NULL if we had zero inputs, like other aggregates */
    1391         468 :     range_count = state->nelems;
    1392         468 :     if (range_count == 0)
    1393          18 :         PG_RETURN_NULL();
    1394             : 
    1395         450 :     mltrngtypoid = get_fn_expr_rettype(fcinfo->flinfo);
    1396         450 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    1397             : 
    1398         450 :     ranges = palloc0(range_count * sizeof(RangeType *));
    1399        1208 :     for (i = 0; i < range_count; i++)
    1400         758 :         ranges[i] = DatumGetRangeTypeP(state->dvalues[i]);
    1401             : 
    1402         450 :     PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypoid, typcache->rngtype, range_count, ranges));
    1403             : }
    1404             : 
    1405             : /*
    1406             :  * multirange_agg_transfn: combine adjacent/overlapping multiranges.
    1407             :  *
    1408             :  * All we do here is gather the input multiranges' ranges into an array so
    1409             :  * that the finalfn can sort and combine them.
    1410             :  */
    1411             : Datum
    1412         444 : multirange_agg_transfn(PG_FUNCTION_ARGS)
    1413             : {
    1414             :     MemoryContext aggContext;
    1415             :     Oid         mltrngtypoid;
    1416             :     TypeCacheEntry *typcache;
    1417             :     TypeCacheEntry *rngtypcache;
    1418             :     ArrayBuildState *state;
    1419             : 
    1420         444 :     if (!AggCheckCallContext(fcinfo, &aggContext))
    1421           0 :         elog(ERROR, "multirange_agg_transfn called in non-aggregate context");
    1422             : 
    1423         444 :     mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
    1424         444 :     if (!type_is_multirange(mltrngtypoid))
    1425           0 :         elog(ERROR, "range_agg must be called with a multirange");
    1426             : 
    1427         444 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    1428         444 :     rngtypcache = typcache->rngtype;
    1429             : 
    1430         444 :     if (PG_ARGISNULL(0))
    1431         222 :         state = initArrayResult(rngtypcache->type_id, aggContext, false);
    1432             :     else
    1433         222 :         state = (ArrayBuildState *) PG_GETARG_POINTER(0);
    1434             : 
    1435             :     /* skip NULLs */
    1436         444 :     if (!PG_ARGISNULL(1))
    1437             :     {
    1438             :         MultirangeType *current;
    1439             :         int32       range_count;
    1440             :         RangeType **ranges;
    1441             : 
    1442         378 :         current = PG_GETARG_MULTIRANGE_P(1);
    1443         378 :         multirange_deserialize(rngtypcache, current, &range_count, &ranges);
    1444         378 :         if (range_count == 0)
    1445             :         {
    1446             :             /*
    1447             :              * Add an empty range so we get an empty result (not a null
    1448             :              * result).
    1449             :              */
    1450          42 :             accumArrayResult(state,
    1451          42 :                              RangeTypePGetDatum(make_empty_range(rngtypcache)),
    1452             :                              false, rngtypcache->type_id, aggContext);
    1453             :         }
    1454             :         else
    1455             :         {
    1456         684 :             for (int32 i = 0; i < range_count; i++)
    1457         348 :                 accumArrayResult(state, RangeTypePGetDatum(ranges[i]), false, rngtypcache->type_id, aggContext);
    1458             :         }
    1459             :     }
    1460             : 
    1461         444 :     PG_RETURN_POINTER(state);
    1462             : }
    1463             : 
    1464             : Datum
    1465          96 : multirange_intersect_agg_transfn(PG_FUNCTION_ARGS)
    1466             : {
    1467             :     MemoryContext aggContext;
    1468             :     Oid         mltrngtypoid;
    1469             :     TypeCacheEntry *typcache;
    1470             :     MultirangeType *result;
    1471             :     MultirangeType *current;
    1472             :     int32       range_count1;
    1473             :     int32       range_count2;
    1474             :     RangeType **ranges1;
    1475             :     RangeType **ranges2;
    1476             : 
    1477          96 :     if (!AggCheckCallContext(fcinfo, &aggContext))
    1478           0 :         elog(ERROR, "multirange_intersect_agg_transfn called in non-aggregate context");
    1479             : 
    1480          96 :     mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
    1481          96 :     if (!type_is_multirange(mltrngtypoid))
    1482           0 :         elog(ERROR, "range_intersect_agg must be called with a multirange");
    1483             : 
    1484          96 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    1485             : 
    1486             :     /* strictness ensures these are non-null */
    1487          96 :     result = PG_GETARG_MULTIRANGE_P(0);
    1488          96 :     current = PG_GETARG_MULTIRANGE_P(1);
    1489             : 
    1490          96 :     multirange_deserialize(typcache->rngtype, result, &range_count1, &ranges1);
    1491          96 :     multirange_deserialize(typcache->rngtype, current, &range_count2, &ranges2);
    1492             : 
    1493          96 :     result = multirange_intersect_internal(mltrngtypoid,
    1494          96 :                                            typcache->rngtype,
    1495             :                                            range_count1,
    1496             :                                            ranges1,
    1497             :                                            range_count2,
    1498             :                                            ranges2);
    1499          96 :     PG_RETURN_MULTIRANGE_P(result);
    1500             : }
    1501             : 
    1502             : 
    1503             : /* multirange -> element type functions */
    1504             : 
    1505             : /* extract lower bound value */
    1506             : Datum
    1507         168 : multirange_lower(PG_FUNCTION_ARGS)
    1508             : {
    1509         168 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1510             :     TypeCacheEntry *typcache;
    1511             :     RangeBound  lower;
    1512             :     RangeBound  upper;
    1513             : 
    1514         168 :     if (MultirangeIsEmpty(mr))
    1515          24 :         PG_RETURN_NULL();
    1516             : 
    1517         144 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1518             : 
    1519         144 :     multirange_get_bounds(typcache->rngtype, mr, 0,
    1520             :                           &lower, &upper);
    1521             : 
    1522         144 :     if (!lower.infinite)
    1523         126 :         PG_RETURN_DATUM(lower.val);
    1524             :     else
    1525          18 :         PG_RETURN_NULL();
    1526             : }
    1527             : 
    1528             : /* extract upper bound value */
    1529             : Datum
    1530         138 : multirange_upper(PG_FUNCTION_ARGS)
    1531             : {
    1532         138 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1533             :     TypeCacheEntry *typcache;
    1534             :     RangeBound  lower;
    1535             :     RangeBound  upper;
    1536             : 
    1537         138 :     if (MultirangeIsEmpty(mr))
    1538          24 :         PG_RETURN_NULL();
    1539             : 
    1540         114 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1541             : 
    1542         114 :     multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
    1543             :                           &lower, &upper);
    1544             : 
    1545         114 :     if (!upper.infinite)
    1546          96 :         PG_RETURN_DATUM(upper.val);
    1547             :     else
    1548          18 :         PG_RETURN_NULL();
    1549             : }
    1550             : 
    1551             : 
    1552             : /* multirange -> bool functions */
    1553             : 
    1554             : /* is multirange empty? */
    1555             : Datum
    1556          66 : multirange_empty(PG_FUNCTION_ARGS)
    1557             : {
    1558          66 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1559             : 
    1560          66 :     PG_RETURN_BOOL(MultirangeIsEmpty(mr));
    1561             : }
    1562             : 
    1563             : /* is lower bound inclusive? */
    1564             : Datum
    1565          66 : multirange_lower_inc(PG_FUNCTION_ARGS)
    1566             : {
    1567          66 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1568             :     TypeCacheEntry *typcache;
    1569             :     RangeBound  lower;
    1570             :     RangeBound  upper;
    1571             : 
    1572          66 :     if (MultirangeIsEmpty(mr))
    1573          24 :         PG_RETURN_BOOL(false);
    1574             : 
    1575          42 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1576          42 :     multirange_get_bounds(typcache->rngtype, mr, 0,
    1577             :                           &lower, &upper);
    1578             : 
    1579          42 :     PG_RETURN_BOOL(lower.inclusive);
    1580             : }
    1581             : 
    1582             : /* is upper bound inclusive? */
    1583             : Datum
    1584          66 : multirange_upper_inc(PG_FUNCTION_ARGS)
    1585             : {
    1586          66 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1587             :     TypeCacheEntry *typcache;
    1588             :     RangeBound  lower;
    1589             :     RangeBound  upper;
    1590             : 
    1591          66 :     if (MultirangeIsEmpty(mr))
    1592          24 :         PG_RETURN_BOOL(false);
    1593             : 
    1594          42 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1595          42 :     multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
    1596             :                           &lower, &upper);
    1597             : 
    1598          42 :     PG_RETURN_BOOL(upper.inclusive);
    1599             : }
    1600             : 
    1601             : /* is lower bound infinite? */
    1602             : Datum
    1603          66 : multirange_lower_inf(PG_FUNCTION_ARGS)
    1604             : {
    1605          66 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1606             :     TypeCacheEntry *typcache;
    1607             :     RangeBound  lower;
    1608             :     RangeBound  upper;
    1609             : 
    1610          66 :     if (MultirangeIsEmpty(mr))
    1611          24 :         PG_RETURN_BOOL(false);
    1612             : 
    1613          42 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1614          42 :     multirange_get_bounds(typcache->rngtype, mr, 0,
    1615             :                           &lower, &upper);
    1616             : 
    1617          42 :     PG_RETURN_BOOL(lower.infinite);
    1618             : }
    1619             : 
    1620             : /* is upper bound infinite? */
    1621             : Datum
    1622          66 : multirange_upper_inf(PG_FUNCTION_ARGS)
    1623             : {
    1624          66 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1625             :     TypeCacheEntry *typcache;
    1626             :     RangeBound  lower;
    1627             :     RangeBound  upper;
    1628             : 
    1629          66 :     if (MultirangeIsEmpty(mr))
    1630          24 :         PG_RETURN_BOOL(false);
    1631             : 
    1632          42 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1633          42 :     multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
    1634             :                           &lower, &upper);
    1635             : 
    1636          42 :     PG_RETURN_BOOL(upper.infinite);
    1637             : }
    1638             : 
    1639             : 
    1640             : 
    1641             : /* multirange, element -> bool functions */
    1642             : 
    1643             : /* contains? */
    1644             : Datum
    1645       23316 : multirange_contains_elem(PG_FUNCTION_ARGS)
    1646             : {
    1647       23316 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1648       23316 :     Datum       val = PG_GETARG_DATUM(1);
    1649             :     TypeCacheEntry *typcache;
    1650             : 
    1651       23316 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1652             : 
    1653       23316 :     PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
    1654             : }
    1655             : 
    1656             : /* contained by? */
    1657             : Datum
    1658         144 : elem_contained_by_multirange(PG_FUNCTION_ARGS)
    1659             : {
    1660         144 :     Datum       val = PG_GETARG_DATUM(0);
    1661         144 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    1662             :     TypeCacheEntry *typcache;
    1663             : 
    1664         144 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1665             : 
    1666         144 :     PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
    1667             : }
    1668             : 
    1669             : /*
    1670             :  * Comparison function for checking if any range of multirange contains given
    1671             :  * key element using binary search.
    1672             :  */
    1673             : static int
    1674       32400 : multirange_elem_bsearch_comparison(TypeCacheEntry *typcache,
    1675             :                                    RangeBound *lower, RangeBound *upper,
    1676             :                                    void *key, bool *match)
    1677             : {
    1678       32400 :     Datum       val = *((Datum *) key);
    1679             :     int         cmp;
    1680             : 
    1681       32400 :     if (!lower->infinite)
    1682             :     {
    1683       31110 :         cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
    1684             :                                               typcache->rng_collation,
    1685             :                                               lower->val, val));
    1686       31110 :         if (cmp > 0 || (cmp == 0 && !lower->inclusive))
    1687       30570 :             return -1;
    1688             :     }
    1689             : 
    1690        1830 :     if (!upper->infinite)
    1691             :     {
    1692        1704 :         cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
    1693             :                                               typcache->rng_collation,
    1694             :                                               upper->val, val));
    1695        1704 :         if (cmp < 0 || (cmp == 0 && !upper->inclusive))
    1696         168 :             return 1;
    1697             :     }
    1698             : 
    1699        1662 :     *match = true;
    1700        1662 :     return 0;
    1701             : }
    1702             : 
    1703             : /*
    1704             :  * Test whether multirange mr contains a specific element value.
    1705             :  */
    1706             : bool
    1707       23460 : multirange_contains_elem_internal(TypeCacheEntry *rangetyp,
    1708             :                                   const MultirangeType *mr, Datum val)
    1709             : {
    1710       23460 :     if (MultirangeIsEmpty(mr))
    1711        3120 :         return false;
    1712             : 
    1713       20340 :     return multirange_bsearch_match(rangetyp, mr, &val,
    1714             :                                     multirange_elem_bsearch_comparison);
    1715             : }
    1716             : 
    1717             : /* multirange, range -> bool functions */
    1718             : 
    1719             : /* contains? */
    1720             : Datum
    1721       89754 : multirange_contains_range(PG_FUNCTION_ARGS)
    1722             : {
    1723       89754 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1724       89754 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    1725             :     TypeCacheEntry *typcache;
    1726             : 
    1727       89754 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1728             : 
    1729       89754 :     PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
    1730             : }
    1731             : 
    1732             : Datum
    1733       74490 : range_contains_multirange(PG_FUNCTION_ARGS)
    1734             : {
    1735       74490 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    1736       74490 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    1737             :     TypeCacheEntry *typcache;
    1738             : 
    1739       74490 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1740             : 
    1741       74490 :     PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
    1742             : }
    1743             : 
    1744             : /* contained by? */
    1745             : Datum
    1746       37620 : range_contained_by_multirange(PG_FUNCTION_ARGS)
    1747             : {
    1748       37620 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    1749       37620 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    1750             :     TypeCacheEntry *typcache;
    1751             : 
    1752       37620 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1753             : 
    1754       37620 :     PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
    1755             : }
    1756             : 
    1757             : Datum
    1758       50490 : multirange_contained_by_range(PG_FUNCTION_ARGS)
    1759             : {
    1760       50490 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1761       50490 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    1762             :     TypeCacheEntry *typcache;
    1763             : 
    1764       50490 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1765             : 
    1766       50490 :     PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
    1767             : }
    1768             : 
    1769             : /*
    1770             :  * Comparison function for checking if any range of multirange contains given
    1771             :  * key range using binary search.
    1772             :  */
    1773             : static int
    1774      122178 : multirange_range_contains_bsearch_comparison(TypeCacheEntry *typcache,
    1775             :                                              RangeBound *lower, RangeBound *upper,
    1776             :                                              void *key, bool *match)
    1777             : {
    1778      122178 :     RangeBound *keyLower = (RangeBound *) key;
    1779      122178 :     RangeBound *keyUpper = (RangeBound *) key + 1;
    1780             : 
    1781             :     /* Check if key range is strictly in the left or in the right */
    1782      122178 :     if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
    1783       31776 :         return -1;
    1784       90402 :     if (range_cmp_bounds(typcache, keyLower, upper) > 0)
    1785       80130 :         return 1;
    1786             : 
    1787             :     /*
    1788             :      * At this point we found overlapping range.  But we have to check if it
    1789             :      * really contains the key range.  Anyway, we have to stop our search
    1790             :      * here, because multirange contains only non-overlapping ranges.
    1791             :      */
    1792       10272 :     *match = range_bounds_contains(typcache, lower, upper, keyLower, keyUpper);
    1793             : 
    1794       10272 :     return 0;
    1795             : }
    1796             : 
    1797             : /*
    1798             :  * Test whether multirange mr contains a specific range r.
    1799             :  */
    1800             : bool
    1801      161592 : multirange_contains_range_internal(TypeCacheEntry *rangetyp,
    1802             :                                    const MultirangeType *mr,
    1803             :                                    const RangeType *r)
    1804             : {
    1805             :     RangeBound  bounds[2];
    1806             :     bool        empty;
    1807             : 
    1808             :     /*
    1809             :      * Every multirange contains an infinite number of empty ranges, even an
    1810             :      * empty one.
    1811             :      */
    1812      161592 :     if (RangeIsEmpty(r))
    1813       90612 :         return true;
    1814             : 
    1815       70980 :     if (MultirangeIsEmpty(mr))
    1816        3096 :         return false;
    1817             : 
    1818       67884 :     range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
    1819             :     Assert(!empty);
    1820             : 
    1821       67884 :     return multirange_bsearch_match(rangetyp, mr, bounds,
    1822             :                                     multirange_range_contains_bsearch_comparison);
    1823             : }
    1824             : 
    1825             : /*
    1826             :  * Test whether range r contains a multirange mr.
    1827             :  */
    1828             : bool
    1829      279002 : range_contains_multirange_internal(TypeCacheEntry *rangetyp,
    1830             :                                    const RangeType *r,
    1831             :                                    const MultirangeType *mr)
    1832             : {
    1833             :     RangeBound  lower1,
    1834             :                 upper1,
    1835             :                 lower2,
    1836             :                 upper2,
    1837             :                 tmp;
    1838             :     bool        empty;
    1839             : 
    1840             :     /*
    1841             :      * Every range contains an infinite number of empty multiranges, even an
    1842             :      * empty one.
    1843             :      */
    1844      279002 :     if (MultirangeIsEmpty(mr))
    1845      191096 :         return true;
    1846             : 
    1847       87906 :     if (RangeIsEmpty(r))
    1848       25272 :         return false;
    1849             : 
    1850             :     /* Range contains multirange iff it contains its union range. */
    1851       62634 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    1852             :     Assert(!empty);
    1853       62634 :     multirange_get_bounds(rangetyp, mr, 0, &lower2, &tmp);
    1854       62634 :     multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper2);
    1855             : 
    1856       62634 :     return range_bounds_contains(rangetyp, &lower1, &upper1, &lower2, &upper2);
    1857             : }
    1858             : 
    1859             : 
    1860             : /* multirange, multirange -> bool functions */
    1861             : 
    1862             : /* equality (internal version) */
    1863             : bool
    1864       47874 : multirange_eq_internal(TypeCacheEntry *rangetyp,
    1865             :                        const MultirangeType *mr1,
    1866             :                        const MultirangeType *mr2)
    1867             : {
    1868             :     int32       range_count_1;
    1869             :     int32       range_count_2;
    1870             :     int32       i;
    1871             :     RangeBound  lower1,
    1872             :                 upper1,
    1873             :                 lower2,
    1874             :                 upper2;
    1875             : 
    1876             :     /* Different types should be prevented by ANYMULTIRANGE matching rules */
    1877       47874 :     if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
    1878           0 :         elog(ERROR, "multirange types do not match");
    1879             : 
    1880       47874 :     range_count_1 = mr1->rangeCount;
    1881       47874 :     range_count_2 = mr2->rangeCount;
    1882             : 
    1883       47874 :     if (range_count_1 != range_count_2)
    1884       29490 :         return false;
    1885             : 
    1886       18636 :     for (i = 0; i < range_count_1; i++)
    1887             :     {
    1888       12288 :         multirange_get_bounds(rangetyp, mr1, i, &lower1, &upper1);
    1889       12288 :         multirange_get_bounds(rangetyp, mr2, i, &lower2, &upper2);
    1890             : 
    1891       12558 :         if (range_cmp_bounds(rangetyp, &lower1, &lower2) != 0 ||
    1892         270 :             range_cmp_bounds(rangetyp, &upper1, &upper2) != 0)
    1893       12036 :             return false;
    1894             :     }
    1895             : 
    1896        6348 :     return true;
    1897             : }
    1898             : 
    1899             : /* equality */
    1900             : Datum
    1901       47742 : multirange_eq(PG_FUNCTION_ARGS)
    1902             : {
    1903       47742 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1904       47742 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1905             :     TypeCacheEntry *typcache;
    1906             : 
    1907       47742 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    1908             : 
    1909       47742 :     PG_RETURN_BOOL(multirange_eq_internal(typcache->rngtype, mr1, mr2));
    1910             : }
    1911             : 
    1912             : /* inequality (internal version) */
    1913             : bool
    1914         132 : multirange_ne_internal(TypeCacheEntry *rangetyp,
    1915             :                        const MultirangeType *mr1,
    1916             :                        const MultirangeType *mr2)
    1917             : {
    1918         132 :     return (!multirange_eq_internal(rangetyp, mr1, mr2));
    1919             : }
    1920             : 
    1921             : /* inequality */
    1922             : Datum
    1923         132 : multirange_ne(PG_FUNCTION_ARGS)
    1924             : {
    1925         132 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1926         132 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1927             :     TypeCacheEntry *typcache;
    1928             : 
    1929         132 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    1930             : 
    1931         132 :     PG_RETURN_BOOL(multirange_ne_internal(typcache->rngtype, mr1, mr2));
    1932             : }
    1933             : 
    1934             : /* overlaps? */
    1935             : Datum
    1936       37344 : range_overlaps_multirange(PG_FUNCTION_ARGS)
    1937             : {
    1938       37344 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    1939       37344 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    1940             :     TypeCacheEntry *typcache;
    1941             : 
    1942       37344 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1943             : 
    1944       37344 :     PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
    1945             : }
    1946             : 
    1947             : Datum
    1948       45390 : multirange_overlaps_range(PG_FUNCTION_ARGS)
    1949             : {
    1950       45390 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    1951       45390 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    1952             :     TypeCacheEntry *typcache;
    1953             : 
    1954       45390 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    1955             : 
    1956       45390 :     PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
    1957             : }
    1958             : 
    1959             : Datum
    1960       46464 : multirange_overlaps_multirange(PG_FUNCTION_ARGS)
    1961             : {
    1962       46464 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    1963       46464 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    1964             :     TypeCacheEntry *typcache;
    1965             : 
    1966       46464 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    1967             : 
    1968       46464 :     PG_RETURN_BOOL(multirange_overlaps_multirange_internal(typcache->rngtype, mr1, mr2));
    1969             : }
    1970             : 
    1971             : /*
    1972             :  * Comparison function for checking if any range of multirange overlaps given
    1973             :  * key range using binary search.
    1974             :  */
    1975             : static int
    1976      126708 : multirange_range_overlaps_bsearch_comparison(TypeCacheEntry *typcache,
    1977             :                                              RangeBound *lower, RangeBound *upper,
    1978             :                                              void *key, bool *match)
    1979             : {
    1980      126708 :     RangeBound *keyLower = (RangeBound *) key;
    1981      126708 :     RangeBound *keyUpper = (RangeBound *) key + 1;
    1982             : 
    1983      126708 :     if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
    1984       32110 :         return -1;
    1985       94598 :     if (range_cmp_bounds(typcache, keyLower, upper) > 0)
    1986       84410 :         return 1;
    1987             : 
    1988       10188 :     *match = true;
    1989       10188 :     return 0;
    1990             : }
    1991             : 
    1992             : bool
    1993      103004 : range_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
    1994             :                                    const RangeType *r,
    1995             :                                    const MultirangeType *mr)
    1996             : {
    1997             :     RangeBound  bounds[2];
    1998             :     bool        empty;
    1999             : 
    2000             :     /*
    2001             :      * Empties never overlap, even with empties. (This seems strange since
    2002             :      * they *do* contain each other, but we want to follow how ranges work.)
    2003             :      */
    2004      103004 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2005       31712 :         return false;
    2006             : 
    2007       71292 :     range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
    2008             :     Assert(!empty);
    2009             : 
    2010       71292 :     return multirange_bsearch_match(rangetyp, mr, bounds,
    2011             :                                     multirange_range_overlaps_bsearch_comparison);
    2012             : }
    2013             : 
    2014             : bool
    2015       46464 : multirange_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
    2016             :                                         const MultirangeType *mr1,
    2017             :                                         const MultirangeType *mr2)
    2018             : {
    2019             :     int32       range_count1;
    2020             :     int32       range_count2;
    2021             :     int32       i1;
    2022             :     int32       i2;
    2023             :     RangeBound  lower1,
    2024             :                 upper1,
    2025             :                 lower2,
    2026             :                 upper2;
    2027             : 
    2028             :     /*
    2029             :      * Empties never overlap, even with empties. (This seems strange since
    2030             :      * they *do* contain each other, but we want to follow how ranges work.)
    2031             :      */
    2032       46464 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    2033       25314 :         return false;
    2034             : 
    2035       21150 :     range_count1 = mr1->rangeCount;
    2036       21150 :     range_count2 = mr2->rangeCount;
    2037             : 
    2038             :     /*
    2039             :      * Every range in mr1 gets a chance to overlap with the ranges in mr2, but
    2040             :      * we can use their ordering to avoid O(n^2). This is similar to
    2041             :      * range_overlaps_multirange where r1 : r2 :: mrr : r, but there if we
    2042             :      * don't find an overlap with r we're done, and here if we don't find an
    2043             :      * overlap with r2 we try the next r2.
    2044             :      */
    2045       21150 :     i1 = 0;
    2046       21150 :     multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
    2047       76362 :     for (i1 = 0, i2 = 0; i2 < range_count2; i2++)
    2048             :     {
    2049       58446 :         multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
    2050             : 
    2051             :         /* Discard r1s while r1 << r2 */
    2052       58578 :         while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
    2053             :         {
    2054         234 :             if (++i1 >= range_count1)
    2055         102 :                 return false;
    2056         132 :             multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
    2057             :         }
    2058             : 
    2059             :         /*
    2060             :          * If r1 && r2, we're done, otherwise we failed to find an overlap for
    2061             :          * r2, so go to the next one.
    2062             :          */
    2063       58344 :         if (range_bounds_overlaps(rangetyp, &lower1, &upper1, &lower2, &upper2))
    2064        3132 :             return true;
    2065             :     }
    2066             : 
    2067             :     /* We looked through all of mr2 without finding an overlap */
    2068       17916 :     return false;
    2069             : }
    2070             : 
    2071             : /* does not extend to right of? */
    2072             : bool
    2073       74342 : range_overleft_multirange_internal(TypeCacheEntry *rangetyp,
    2074             :                                    const RangeType *r,
    2075             :                                    const MultirangeType *mr)
    2076             : {
    2077             :     RangeBound  lower1,
    2078             :                 upper1,
    2079             :                 lower2,
    2080             :                 upper2;
    2081             :     bool        empty;
    2082             : 
    2083       74342 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2084        6012 :         PG_RETURN_BOOL(false);
    2085             : 
    2086             : 
    2087       68330 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    2088             :     Assert(!empty);
    2089       68330 :     multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1,
    2090             :                           &lower2, &upper2);
    2091             : 
    2092       68330 :     PG_RETURN_BOOL(range_cmp_bounds(rangetyp, &upper1, &upper2) <= 0);
    2093             : }
    2094             : 
    2095             : Datum
    2096       37242 : range_overleft_multirange(PG_FUNCTION_ARGS)
    2097             : {
    2098       37242 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    2099       37242 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    2100             :     TypeCacheEntry *typcache;
    2101             : 
    2102       37242 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2103             : 
    2104       37242 :     PG_RETURN_BOOL(range_overleft_multirange_internal(typcache->rngtype, r, mr));
    2105             : }
    2106             : 
    2107             : Datum
    2108       47286 : multirange_overleft_range(PG_FUNCTION_ARGS)
    2109             : {
    2110       47286 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2111       47286 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    2112             :     TypeCacheEntry *typcache;
    2113             :     RangeBound  lower1,
    2114             :                 upper1,
    2115             :                 lower2,
    2116             :                 upper2;
    2117             :     bool        empty;
    2118             : 
    2119       47286 :     if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
    2120       25212 :         PG_RETURN_BOOL(false);
    2121             : 
    2122       22074 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2123             : 
    2124       22074 :     multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
    2125             :                           &lower1, &upper1);
    2126       22074 :     range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
    2127             :     Assert(!empty);
    2128             : 
    2129       22074 :     PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
    2130             : }
    2131             : 
    2132             : Datum
    2133       47292 : multirange_overleft_multirange(PG_FUNCTION_ARGS)
    2134             : {
    2135       47292 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2136       47292 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2137             :     TypeCacheEntry *typcache;
    2138             :     RangeBound  lower1,
    2139             :                 upper1,
    2140             :                 lower2,
    2141             :                 upper2;
    2142             : 
    2143       47292 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    2144       25218 :         PG_RETURN_BOOL(false);
    2145             : 
    2146       22074 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2147             : 
    2148       22074 :     multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1,
    2149             :                           &lower1, &upper1);
    2150       22074 :     multirange_get_bounds(typcache->rngtype, mr2, mr2->rangeCount - 1,
    2151             :                           &lower2, &upper2);
    2152             : 
    2153       22074 :     PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
    2154             : }
    2155             : 
    2156             : /* does not extend to left of? */
    2157             : bool
    2158      119346 : range_overright_multirange_internal(TypeCacheEntry *rangetyp,
    2159             :                                     const RangeType *r,
    2160             :                                     const MultirangeType *mr)
    2161             : {
    2162             :     RangeBound  lower1,
    2163             :                 upper1,
    2164             :                 lower2,
    2165             :                 upper2;
    2166             :     bool        empty;
    2167             : 
    2168      119346 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2169        6012 :         PG_RETURN_BOOL(false);
    2170             : 
    2171      113334 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    2172             :     Assert(!empty);
    2173      113334 :     multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
    2174             : 
    2175      113334 :     return (range_cmp_bounds(rangetyp, &lower1, &lower2) >= 0);
    2176             : }
    2177             : 
    2178             : Datum
    2179       37242 : range_overright_multirange(PG_FUNCTION_ARGS)
    2180             : {
    2181       37242 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    2182       37242 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    2183             :     TypeCacheEntry *typcache;
    2184             : 
    2185       37242 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2186             : 
    2187       37242 :     PG_RETURN_BOOL(range_overright_multirange_internal(typcache->rngtype, r, mr));
    2188             : }
    2189             : 
    2190             : Datum
    2191       61800 : multirange_overright_range(PG_FUNCTION_ARGS)
    2192             : {
    2193       61800 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2194       61800 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    2195             :     TypeCacheEntry *typcache;
    2196             :     RangeBound  lower1,
    2197             :                 upper1,
    2198             :                 lower2,
    2199             :                 upper2;
    2200             :     bool        empty;
    2201             : 
    2202       61800 :     if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
    2203       25212 :         PG_RETURN_BOOL(false);
    2204             : 
    2205       36588 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2206             : 
    2207       36588 :     multirange_get_bounds(typcache->rngtype, mr, 0, &lower1, &upper1);
    2208       36588 :     range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
    2209             :     Assert(!empty);
    2210             : 
    2211       36588 :     PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
    2212             : }
    2213             : 
    2214             : Datum
    2215       61806 : multirange_overright_multirange(PG_FUNCTION_ARGS)
    2216             : {
    2217       61806 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2218       61806 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2219             :     TypeCacheEntry *typcache;
    2220             :     RangeBound  lower1,
    2221             :                 upper1,
    2222             :                 lower2,
    2223             :                 upper2;
    2224             : 
    2225       61806 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    2226       25218 :         PG_RETURN_BOOL(false);
    2227             : 
    2228       36588 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2229             : 
    2230       36588 :     multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1);
    2231       36588 :     multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2);
    2232             : 
    2233       36588 :     PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
    2234             : }
    2235             : 
    2236             : /* contains? */
    2237             : Datum
    2238      156312 : multirange_contains_multirange(PG_FUNCTION_ARGS)
    2239             : {
    2240      156312 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2241      156312 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2242             :     TypeCacheEntry *typcache;
    2243             : 
    2244      156312 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2245             : 
    2246      156312 :     PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr1, mr2));
    2247             : }
    2248             : 
    2249             : /* contained by? */
    2250             : Datum
    2251       50790 : multirange_contained_by_multirange(PG_FUNCTION_ARGS)
    2252             : {
    2253       50790 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2254       50790 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2255             :     TypeCacheEntry *typcache;
    2256             : 
    2257       50790 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2258             : 
    2259       50790 :     PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr2, mr1));
    2260             : }
    2261             : 
    2262             : /*
    2263             :  * Test whether multirange mr1 contains every range from another multirange mr2.
    2264             :  */
    2265             : bool
    2266      207102 : multirange_contains_multirange_internal(TypeCacheEntry *rangetyp,
    2267             :                                         const MultirangeType *mr1,
    2268             :                                         const MultirangeType *mr2)
    2269             : {
    2270      207102 :     int32       range_count1 = mr1->rangeCount;
    2271      207102 :     int32       range_count2 = mr2->rangeCount;
    2272             :     int         i1,
    2273             :                 i2;
    2274             :     RangeBound  lower1,
    2275             :                 upper1,
    2276             :                 lower2,
    2277             :                 upper2;
    2278             : 
    2279             :     /*
    2280             :      * We follow the same logic for empties as ranges: - an empty multirange
    2281             :      * contains an empty range/multirange. - an empty multirange can't contain
    2282             :      * any other range/multirange. - an empty multirange is contained by any
    2283             :      * other range/multirange.
    2284             :      */
    2285             : 
    2286      207102 :     if (range_count2 == 0)
    2287      145212 :         return true;
    2288       61890 :     if (range_count1 == 0)
    2289       22296 :         return false;
    2290             : 
    2291             :     /*
    2292             :      * Every range in mr2 must be contained by some range in mr1. To avoid
    2293             :      * O(n^2) we walk through both ranges in tandem.
    2294             :      */
    2295       39594 :     i1 = 0;
    2296       39594 :     multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
    2297       42864 :     for (i2 = 0; i2 < range_count2; i2++)
    2298             :     {
    2299       41232 :         multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
    2300             : 
    2301             :         /* Discard r1s while r1 << r2 */
    2302       77526 :         while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
    2303             :         {
    2304       53940 :             if (++i1 >= range_count1)
    2305       17646 :                 return false;
    2306       36294 :             multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
    2307             :         }
    2308             : 
    2309             :         /*
    2310             :          * If r1 @> r2, go to the next r2, otherwise return false (since every
    2311             :          * r1[n] and r1[n+1] must have a gap). Note this will give weird
    2312             :          * answers if you don't canonicalize, e.g. with a custom
    2313             :          * int2multirange {[1,1], [2,2]} there is a "gap". But that is
    2314             :          * consistent with other range operators, e.g. '[1,1]'::int2range -|-
    2315             :          * '[2,2]'::int2range is false.
    2316             :          */
    2317       23586 :         if (!range_bounds_contains(rangetyp, &lower1, &upper1,
    2318             :                                    &lower2, &upper2))
    2319       20316 :             return false;
    2320             :     }
    2321             : 
    2322             :     /* All ranges in mr2 are satisfied */
    2323        1632 :     return true;
    2324             : }
    2325             : 
    2326             : /* strictly left of? */
    2327             : Datum
    2328       37230 : range_before_multirange(PG_FUNCTION_ARGS)
    2329             : {
    2330       37230 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    2331       37230 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    2332             :     TypeCacheEntry *typcache;
    2333             : 
    2334       37230 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2335             : 
    2336       37230 :     PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
    2337             : }
    2338             : 
    2339             : Datum
    2340       44760 : multirange_before_range(PG_FUNCTION_ARGS)
    2341             : {
    2342       44760 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2343       44760 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    2344             :     TypeCacheEntry *typcache;
    2345             : 
    2346       44760 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2347             : 
    2348       44760 :     PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
    2349             : }
    2350             : 
    2351             : Datum
    2352       44766 : multirange_before_multirange(PG_FUNCTION_ARGS)
    2353             : {
    2354       44766 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2355       44766 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2356             :     TypeCacheEntry *typcache;
    2357             : 
    2358       44766 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2359             : 
    2360       44766 :     PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr1, mr2));
    2361             : }
    2362             : 
    2363             : /* strictly right of? */
    2364             : Datum
    2365       37236 : range_after_multirange(PG_FUNCTION_ARGS)
    2366             : {
    2367       37236 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    2368       37236 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    2369             :     TypeCacheEntry *typcache;
    2370             : 
    2371       37236 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2372             : 
    2373       37236 :     PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
    2374             : }
    2375             : 
    2376             : Datum
    2377       56748 : multirange_after_range(PG_FUNCTION_ARGS)
    2378             : {
    2379       56748 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2380       56748 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    2381             :     TypeCacheEntry *typcache;
    2382             : 
    2383       56748 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2384             : 
    2385       56748 :     PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
    2386             : }
    2387             : 
    2388             : Datum
    2389       56760 : multirange_after_multirange(PG_FUNCTION_ARGS)
    2390             : {
    2391       56760 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2392       56760 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2393             :     TypeCacheEntry *typcache;
    2394             : 
    2395       56760 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2396             : 
    2397       56760 :     PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr2, mr1));
    2398             : }
    2399             : 
    2400             : /* strictly left of? (internal version) */
    2401             : bool
    2402      112070 : range_before_multirange_internal(TypeCacheEntry *rangetyp,
    2403             :                                  const RangeType *r,
    2404             :                                  const MultirangeType *mr)
    2405             : {
    2406             :     RangeBound  lower1,
    2407             :                 upper1,
    2408             :                 lower2,
    2409             :                 upper2;
    2410             :     bool        empty;
    2411             : 
    2412      112070 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2413       31224 :         return false;
    2414             : 
    2415       80846 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    2416             :     Assert(!empty);
    2417             : 
    2418       80846 :     multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
    2419             : 
    2420       80846 :     return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
    2421             : }
    2422             : 
    2423             : bool
    2424      101526 : multirange_before_multirange_internal(TypeCacheEntry *rangetyp,
    2425             :                                       const MultirangeType *mr1,
    2426             :                                       const MultirangeType *mr2)
    2427             : {
    2428             :     RangeBound  lower1,
    2429             :                 upper1,
    2430             :                 lower2,
    2431             :                 upper2;
    2432             : 
    2433      101526 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    2434       50436 :         return false;
    2435             : 
    2436       51090 :     multirange_get_bounds(rangetyp, mr1, mr1->rangeCount - 1,
    2437             :                           &lower1, &upper1);
    2438       51090 :     multirange_get_bounds(rangetyp, mr2, 0,
    2439             :                           &lower2, &upper2);
    2440             : 
    2441       51090 :     return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
    2442             : }
    2443             : 
    2444             : /* strictly right of? (internal version) */
    2445             : bool
    2446      155466 : range_after_multirange_internal(TypeCacheEntry *rangetyp,
    2447             :                                 const RangeType *r,
    2448             :                                 const MultirangeType *mr)
    2449             : {
    2450             :     RangeBound  lower1,
    2451             :                 upper1,
    2452             :                 lower2,
    2453             :                 upper2;
    2454             :     bool        empty;
    2455             :     int32       range_count;
    2456             : 
    2457      155466 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2458       31224 :         return false;
    2459             : 
    2460      124242 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    2461             :     Assert(!empty);
    2462             : 
    2463      124242 :     range_count = mr->rangeCount;
    2464      124242 :     multirange_get_bounds(rangetyp, mr, range_count - 1,
    2465             :                           &lower2, &upper2);
    2466             : 
    2467      124242 :     return (range_cmp_bounds(rangetyp, &lower1, &upper2) > 0);
    2468             : }
    2469             : 
    2470             : bool
    2471       93554 : range_adjacent_multirange_internal(TypeCacheEntry *rangetyp,
    2472             :                                    const RangeType *r,
    2473             :                                    const MultirangeType *mr)
    2474             : {
    2475             :     RangeBound  lower1,
    2476             :                 upper1,
    2477             :                 lower2,
    2478             :                 upper2;
    2479             :     bool        empty;
    2480             :     int32       range_count;
    2481             : 
    2482       93554 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2483        6012 :         return false;
    2484             : 
    2485       87542 :     range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
    2486             :     Assert(!empty);
    2487             : 
    2488       87542 :     range_count = mr->rangeCount;
    2489       87542 :     multirange_get_bounds(rangetyp, mr, 0,
    2490             :                           &lower2, &upper2);
    2491             : 
    2492       87542 :     if (bounds_adjacent(rangetyp, upper1, lower2))
    2493          72 :         return true;
    2494             : 
    2495       87470 :     if (range_count > 1)
    2496       80258 :         multirange_get_bounds(rangetyp, mr, range_count - 1,
    2497             :                               &lower2, &upper2);
    2498             : 
    2499       87470 :     if (bounds_adjacent(rangetyp, upper2, lower1))
    2500          84 :         return true;
    2501             : 
    2502       87386 :     return false;
    2503             : }
    2504             : 
    2505             : /* adjacent to? */
    2506             : Datum
    2507       37224 : range_adjacent_multirange(PG_FUNCTION_ARGS)
    2508             : {
    2509       37224 :     RangeType  *r = PG_GETARG_RANGE_P(0);
    2510       37224 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
    2511             :     TypeCacheEntry *typcache;
    2512             : 
    2513       37224 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2514             : 
    2515       37224 :     PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
    2516             : }
    2517             : 
    2518             : Datum
    2519       44442 : multirange_adjacent_range(PG_FUNCTION_ARGS)
    2520             : {
    2521       44442 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2522       44442 :     RangeType  *r = PG_GETARG_RANGE_P(1);
    2523             :     TypeCacheEntry *typcache;
    2524             : 
    2525       44442 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
    2526       25212 :         return false;
    2527             : 
    2528       19230 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2529             : 
    2530       19230 :     PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
    2531             : }
    2532             : 
    2533             : Datum
    2534       44472 : multirange_adjacent_multirange(PG_FUNCTION_ARGS)
    2535             : {
    2536       44472 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2537       44472 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2538             :     TypeCacheEntry *typcache;
    2539             :     int32       range_count1;
    2540             :     int32       range_count2;
    2541             :     RangeBound  lower1,
    2542             :                 upper1,
    2543             :                 lower2,
    2544             :                 upper2;
    2545             : 
    2546       44472 :     if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
    2547       25218 :         return false;
    2548             : 
    2549       19254 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2550             : 
    2551       19254 :     range_count1 = mr1->rangeCount;
    2552       19254 :     range_count2 = mr2->rangeCount;
    2553       19254 :     multirange_get_bounds(typcache->rngtype, mr1, range_count1 - 1,
    2554             :                           &lower1, &upper1);
    2555       19254 :     multirange_get_bounds(typcache->rngtype, mr2, 0,
    2556             :                           &lower2, &upper2);
    2557       19254 :     if (bounds_adjacent(typcache->rngtype, upper1, lower2))
    2558          30 :         PG_RETURN_BOOL(true);
    2559             : 
    2560       19224 :     if (range_count1 > 1)
    2561       12012 :         multirange_get_bounds(typcache->rngtype, mr1, 0,
    2562             :                               &lower1, &upper1);
    2563       19224 :     if (range_count2 > 1)
    2564       19206 :         multirange_get_bounds(typcache->rngtype, mr2, range_count2 - 1,
    2565             :                               &lower2, &upper2);
    2566       19224 :     if (bounds_adjacent(typcache->rngtype, upper2, lower1))
    2567          24 :         PG_RETURN_BOOL(true);
    2568       19200 :     PG_RETURN_BOOL(false);
    2569             : }
    2570             : 
    2571             : /* Btree support */
    2572             : 
    2573             : /* btree comparator */
    2574             : Datum
    2575         882 : multirange_cmp(PG_FUNCTION_ARGS)
    2576             : {
    2577         882 :     MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
    2578         882 :     MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
    2579             :     int32       range_count_1;
    2580             :     int32       range_count_2;
    2581             :     int32       range_count_max;
    2582             :     int32       i;
    2583             :     TypeCacheEntry *typcache;
    2584         882 :     int         cmp = 0;        /* If both are empty we'll use this. */
    2585             : 
    2586             :     /* Different types should be prevented by ANYMULTIRANGE matching rules */
    2587         882 :     if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
    2588           0 :         elog(ERROR, "multirange types do not match");
    2589             : 
    2590         882 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
    2591             : 
    2592         882 :     range_count_1 = mr1->rangeCount;
    2593         882 :     range_count_2 = mr2->rangeCount;
    2594             : 
    2595             :     /* Loop over source data */
    2596         882 :     range_count_max = Max(range_count_1, range_count_2);
    2597         948 :     for (i = 0; i < range_count_max; i++)
    2598             :     {
    2599             :         RangeBound  lower1,
    2600             :                     upper1,
    2601             :                     lower2,
    2602             :                     upper2;
    2603             : 
    2604             :         /*
    2605             :          * If one multirange is shorter, it's as if it had empty ranges at the
    2606             :          * end to extend its length. An empty range compares earlier than any
    2607             :          * other range, so the shorter multirange comes before the longer.
    2608             :          * This is the same behavior as in other types, e.g. in strings 'aaa'
    2609             :          * < 'aaaaaa'.
    2610             :          */
    2611         762 :         if (i >= range_count_1)
    2612             :         {
    2613         120 :             cmp = -1;
    2614         696 :             break;
    2615             :         }
    2616         642 :         if (i >= range_count_2)
    2617             :         {
    2618         168 :             cmp = 1;
    2619         168 :             break;
    2620             :         }
    2621             : 
    2622         474 :         multirange_get_bounds(typcache->rngtype, mr1, i, &lower1, &upper1);
    2623         474 :         multirange_get_bounds(typcache->rngtype, mr2, i, &lower2, &upper2);
    2624             : 
    2625         474 :         cmp = range_cmp_bounds(typcache->rngtype, &lower1, &lower2);
    2626         474 :         if (cmp == 0)
    2627          90 :             cmp = range_cmp_bounds(typcache->rngtype, &upper1, &upper2);
    2628         474 :         if (cmp != 0)
    2629         408 :             break;
    2630             :     }
    2631             : 
    2632         882 :     PG_FREE_IF_COPY(mr1, 0);
    2633         882 :     PG_FREE_IF_COPY(mr2, 1);
    2634             : 
    2635         882 :     PG_RETURN_INT32(cmp);
    2636             : }
    2637             : 
    2638             : /* inequality operators using the multirange_cmp function */
    2639             : Datum
    2640         168 : multirange_lt(PG_FUNCTION_ARGS)
    2641             : {
    2642         168 :     int         cmp = multirange_cmp(fcinfo);
    2643             : 
    2644         168 :     PG_RETURN_BOOL(cmp < 0);
    2645             : }
    2646             : 
    2647             : Datum
    2648          96 : multirange_le(PG_FUNCTION_ARGS)
    2649             : {
    2650          96 :     int         cmp = multirange_cmp(fcinfo);
    2651             : 
    2652          96 :     PG_RETURN_BOOL(cmp <= 0);
    2653             : }
    2654             : 
    2655             : Datum
    2656          72 : multirange_ge(PG_FUNCTION_ARGS)
    2657             : {
    2658          72 :     int         cmp = multirange_cmp(fcinfo);
    2659             : 
    2660          72 :     PG_RETURN_BOOL(cmp >= 0);
    2661             : }
    2662             : 
    2663             : Datum
    2664          78 : multirange_gt(PG_FUNCTION_ARGS)
    2665             : {
    2666          78 :     int         cmp = multirange_cmp(fcinfo);
    2667             : 
    2668          78 :     PG_RETURN_BOOL(cmp > 0);
    2669             : }
    2670             : 
    2671             : /* multirange -> range functions */
    2672             : 
    2673             : /* Find the smallest range that includes everything in the multirange */
    2674             : Datum
    2675          36 : range_merge_from_multirange(PG_FUNCTION_ARGS)
    2676             : {
    2677          36 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2678          36 :     Oid         mltrngtypoid = MultirangeTypeGetOid(mr);
    2679             :     TypeCacheEntry *typcache;
    2680             :     RangeType  *result;
    2681             : 
    2682          36 :     typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
    2683             : 
    2684          36 :     if (MultirangeIsEmpty(mr))
    2685             :     {
    2686           6 :         result = make_empty_range(typcache->rngtype);
    2687             :     }
    2688          30 :     else if (mr->rangeCount == 1)
    2689             :     {
    2690          12 :         result = multirange_get_range(typcache->rngtype, mr, 0);
    2691             :     }
    2692             :     else
    2693             :     {
    2694             :         RangeBound  firstLower,
    2695             :                     firstUpper,
    2696             :                     lastLower,
    2697             :                     lastUpper;
    2698             : 
    2699          18 :         multirange_get_bounds(typcache->rngtype, mr, 0,
    2700             :                               &firstLower, &firstUpper);
    2701          18 :         multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
    2702             :                               &lastLower, &lastUpper);
    2703             : 
    2704          18 :         result = make_range(typcache->rngtype, &firstLower, &lastUpper,
    2705             :                             false, NULL);
    2706             :     }
    2707             : 
    2708          36 :     PG_RETURN_RANGE_P(result);
    2709             : }
    2710             : 
    2711             : /* Turn multirange into a set of ranges */
    2712             : Datum
    2713          72 : multirange_unnest(PG_FUNCTION_ARGS)
    2714             : {
    2715             :     typedef struct
    2716             :     {
    2717             :         MultirangeType *mr;
    2718             :         TypeCacheEntry *typcache;
    2719             :         int         index;
    2720             :     } multirange_unnest_fctx;
    2721             : 
    2722             :     FuncCallContext *funcctx;
    2723             :     multirange_unnest_fctx *fctx;
    2724             :     MemoryContext oldcontext;
    2725             : 
    2726             :     /* stuff done only on the first call of the function */
    2727          72 :     if (SRF_IS_FIRSTCALL())
    2728             :     {
    2729             :         MultirangeType *mr;
    2730             : 
    2731             :         /* create a function context for cross-call persistence */
    2732          24 :         funcctx = SRF_FIRSTCALL_INIT();
    2733             : 
    2734             :         /*
    2735             :          * switch to memory context appropriate for multiple function calls
    2736             :          */
    2737          24 :         oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
    2738             : 
    2739             :         /*
    2740             :          * Get the multirange value and detoast if needed.  We can't do this
    2741             :          * earlier because if we have to detoast, we want the detoasted copy
    2742             :          * to be in multi_call_memory_ctx, so it will go away when we're done
    2743             :          * and not before.  (If no detoast happens, we assume the originally
    2744             :          * passed multirange will stick around till then.)
    2745             :          */
    2746          24 :         mr = PG_GETARG_MULTIRANGE_P(0);
    2747             : 
    2748             :         /* allocate memory for user context */
    2749          24 :         fctx = (multirange_unnest_fctx *) palloc(sizeof(multirange_unnest_fctx));
    2750             : 
    2751             :         /* initialize state */
    2752          24 :         fctx->mr = mr;
    2753          24 :         fctx->index = 0;
    2754          24 :         fctx->typcache = lookup_type_cache(MultirangeTypeGetOid(mr),
    2755             :                                            TYPECACHE_MULTIRANGE_INFO);
    2756             : 
    2757          24 :         funcctx->user_fctx = fctx;
    2758          24 :         MemoryContextSwitchTo(oldcontext);
    2759             :     }
    2760             : 
    2761             :     /* stuff done on every call of the function */
    2762          72 :     funcctx = SRF_PERCALL_SETUP();
    2763          72 :     fctx = funcctx->user_fctx;
    2764             : 
    2765          72 :     if (fctx->index < fctx->mr->rangeCount)
    2766             :     {
    2767             :         RangeType  *range;
    2768             : 
    2769          48 :         range = multirange_get_range(fctx->typcache->rngtype,
    2770          48 :                                      fctx->mr,
    2771             :                                      fctx->index);
    2772          48 :         fctx->index++;
    2773             : 
    2774          48 :         SRF_RETURN_NEXT(funcctx, RangeTypePGetDatum(range));
    2775             :     }
    2776             :     else
    2777             :     {
    2778             :         /* do when there is no more left */
    2779          24 :         SRF_RETURN_DONE(funcctx);
    2780             :     }
    2781             : }
    2782             : 
    2783             : /* Hash support */
    2784             : 
    2785             : /* hash a multirange value */
    2786             : Datum
    2787         336 : hash_multirange(PG_FUNCTION_ARGS)
    2788             : {
    2789         336 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2790         336 :     uint32      result = 1;
    2791             :     TypeCacheEntry *typcache,
    2792             :                *scache;
    2793             :     int32       range_count,
    2794             :                 i;
    2795             : 
    2796         336 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2797         336 :     scache = typcache->rngtype->rngelemtype;
    2798         336 :     if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
    2799             :     {
    2800           6 :         scache = lookup_type_cache(scache->type_id,
    2801             :                                    TYPECACHE_HASH_PROC_FINFO);
    2802           6 :         if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
    2803           0 :             ereport(ERROR,
    2804             :                     (errcode(ERRCODE_UNDEFINED_FUNCTION),
    2805             :                      errmsg("could not identify a hash function for type %s",
    2806             :                             format_type_be(scache->type_id))));
    2807             :     }
    2808             : 
    2809         336 :     range_count = mr->rangeCount;
    2810         600 :     for (i = 0; i < range_count; i++)
    2811             :     {
    2812             :         RangeBound  lower,
    2813             :                     upper;
    2814         264 :         uint8       flags = MultirangeGetFlagsPtr(mr)[i];
    2815             :         uint32      lower_hash;
    2816             :         uint32      upper_hash;
    2817             :         uint32      range_hash;
    2818             : 
    2819         264 :         multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
    2820             : 
    2821         264 :         if (RANGE_HAS_LBOUND(flags))
    2822         198 :             lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
    2823         198 :                                                           typcache->rngtype->rng_collation,
    2824             :                                                           lower.val));
    2825             :         else
    2826          66 :             lower_hash = 0;
    2827             : 
    2828         264 :         if (RANGE_HAS_UBOUND(flags))
    2829         210 :             upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
    2830         210 :                                                           typcache->rngtype->rng_collation,
    2831             :                                                           upper.val));
    2832             :         else
    2833          54 :             upper_hash = 0;
    2834             : 
    2835             :         /* Merge hashes of flags and bounds */
    2836         264 :         range_hash = hash_uint32((uint32) flags);
    2837         264 :         range_hash ^= lower_hash;
    2838         264 :         range_hash = pg_rotate_left32(range_hash, 1);
    2839         264 :         range_hash ^= upper_hash;
    2840             : 
    2841             :         /*
    2842             :          * Use the same approach as hash_array to combine the individual
    2843             :          * elements' hash values:
    2844             :          */
    2845         264 :         result = (result << 5) - result + range_hash;
    2846             :     }
    2847             : 
    2848         336 :     PG_FREE_IF_COPY(mr, 0);
    2849             : 
    2850         336 :     PG_RETURN_UINT32(result);
    2851             : }
    2852             : 
    2853             : /*
    2854             :  * Returns 64-bit value by hashing a value to a 64-bit value, with a seed.
    2855             :  * Otherwise, similar to hash_multirange.
    2856             :  */
    2857             : Datum
    2858          60 : hash_multirange_extended(PG_FUNCTION_ARGS)
    2859             : {
    2860          60 :     MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
    2861          60 :     Datum       seed = PG_GETARG_DATUM(1);
    2862          60 :     uint64      result = 1;
    2863             :     TypeCacheEntry *typcache,
    2864             :                *scache;
    2865             :     int32       range_count,
    2866             :                 i;
    2867             : 
    2868          60 :     typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
    2869          60 :     scache = typcache->rngtype->rngelemtype;
    2870          60 :     if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
    2871             :     {
    2872           0 :         scache = lookup_type_cache(scache->type_id,
    2873             :                                    TYPECACHE_HASH_EXTENDED_PROC_FINFO);
    2874           0 :         if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
    2875           0 :             ereport(ERROR,
    2876             :                     (errcode(ERRCODE_UNDEFINED_FUNCTION),
    2877             :                      errmsg("could not identify a hash function for type %s",
    2878             :                             format_type_be(scache->type_id))));
    2879             :     }
    2880             : 
    2881          60 :     range_count = mr->rangeCount;
    2882         120 :     for (i = 0; i < range_count; i++)
    2883             :     {
    2884             :         RangeBound  lower,
    2885             :                     upper;
    2886          60 :         uint8       flags = MultirangeGetFlagsPtr(mr)[i];
    2887             :         uint64      lower_hash;
    2888             :         uint64      upper_hash;
    2889             :         uint64      range_hash;
    2890             : 
    2891          60 :         multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
    2892             : 
    2893          60 :         if (RANGE_HAS_LBOUND(flags))
    2894          60 :             lower_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
    2895          60 :                                                           typcache->rngtype->rng_collation,
    2896             :                                                           lower.val,
    2897             :                                                           seed));
    2898             :         else
    2899           0 :             lower_hash = 0;
    2900             : 
    2901          60 :         if (RANGE_HAS_UBOUND(flags))
    2902          60 :             upper_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
    2903          60 :                                                           typcache->rngtype->rng_collation,
    2904             :                                                           upper.val,
    2905             :                                                           seed));
    2906             :         else
    2907           0 :             upper_hash = 0;
    2908             : 
    2909             :         /* Merge hashes of flags and bounds */
    2910          60 :         range_hash = DatumGetUInt64(hash_uint32_extended((uint32) flags,
    2911          60 :                                                          DatumGetInt64(seed)));
    2912          60 :         range_hash ^= lower_hash;
    2913          60 :         range_hash = ROTATE_HIGH_AND_LOW_32BITS(range_hash);
    2914          60 :         range_hash ^= upper_hash;
    2915             : 
    2916             :         /*
    2917             :          * Use the same approach as hash_array to combine the individual
    2918             :          * elements' hash values:
    2919             :          */
    2920          60 :         result = (result << 5) - result + range_hash;
    2921             :     }
    2922             : 
    2923          60 :     PG_FREE_IF_COPY(mr, 0);
    2924             : 
    2925          60 :     PG_RETURN_UINT64(result);
    2926             : }

Generated by: LCOV version 1.14