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