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