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