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

Generated by: LCOV version 1.14