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  elog(ERROR, "type %u does not match constructor type", rngtypid);
977 
978  /*
979  * Be careful: we can still be called with zero ranges, like this:
980  * `int4multirange(variadic '{}'::int4range[])
981  */
982  if (dims == 0)
983  {
984  range_count = 0;
985  ranges = NULL;
986  }
987  else
988  {
989  deconstruct_array(rangeArray, rngtypid, rangetyp->typlen, rangetyp->typbyval,
990  rangetyp->typalign, &elements, &nulls, &range_count);
991 
992  ranges = palloc0(range_count * sizeof(RangeType *));
993  for (i = 0; i < range_count; i++)
994  {
995  if (nulls[i])
996  ereport(ERROR,
997  (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
998  errmsg("multirange values cannot contain null members")));
999 
1000  /* make_multirange will do its own copy */
1001  ranges[i] = DatumGetRangeTypeP(elements[i]);
1002  }
1003  }
1004 
1005  PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, range_count, ranges));
1006 }
1007 
1008 /*
1009  * Construct multirange value from a single range. It'd be nice if we could
1010  * just use multirange_constructor2 for this case, but we need a non-variadic
1011  * single-arg function to let us define a CAST from a range to its multirange.
1012  */
1013 Datum
1014 multirange_constructor1(PG_FUNCTION_ARGS)
1015 {
1016  Oid mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
1017  Oid rngtypid;
1018  TypeCacheEntry *typcache;
1019  TypeCacheEntry *rangetyp;
1020  RangeType *range;
1021 
1022  typcache = multirange_get_typcache(fcinfo, mltrngtypid);
1023  rangetyp = typcache->rngtype;
1024 
1025  /*
1026  * This check should be guaranteed by our signature, but let's do it just
1027  * in case.
1028  */
1029 
1030  if (PG_ARGISNULL(0))
1031  elog(ERROR,
1032  "multirange values cannot contain null members");
1033 
1034  range = PG_GETARG_RANGE_P(0);
1035 
1036  /* Make sure the range type matches. */
1037  rngtypid = RangeTypeGetOid(range);
1038  if (rngtypid != rangetyp->type_id)
1039  elog(ERROR, "type %u does not match constructor type", rngtypid);
1040 
1041  PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 1, &range));
1042 }
1043 
1044 /*
1045  * Constructor just like multirange_constructor1, but opr_sanity gets angry
1046  * if the same internal function handles multiple functions with different arg
1047  * counts.
1048  */
1049 Datum
1050 multirange_constructor0(PG_FUNCTION_ARGS)
1051 {
1052  Oid mltrngtypid;
1053  TypeCacheEntry *typcache;
1054  TypeCacheEntry *rangetyp;
1055 
1056  /* This should always be called without arguments */
1057  if (PG_NARGS() != 0)
1058  elog(ERROR,
1059  "niladic multirange constructor must not receive arguments");
1060 
1061  mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
1062  typcache = multirange_get_typcache(fcinfo, mltrngtypid);
1063  rangetyp = typcache->rngtype;
1064 
1065  PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL));
1066 }
1067 
1068 
1069 /* multirange, multirange -> multirange type functions */
1070 
1071 /* multirange union */
1072 Datum
1073 multirange_union(PG_FUNCTION_ARGS)
1074 {
1075  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1076  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1077  TypeCacheEntry *typcache;
1078  int32 range_count1;
1079  int32 range_count2;
1080  int32 range_count3;
1081  RangeType **ranges1;
1082  RangeType **ranges2;
1083  RangeType **ranges3;
1084 
1085  if (MultirangeIsEmpty(mr1))
1086  PG_RETURN_MULTIRANGE_P(mr2);
1087  if (MultirangeIsEmpty(mr2))
1088  PG_RETURN_MULTIRANGE_P(mr1);
1089 
1090  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
1091 
1092  multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
1093  multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
1094 
1095  range_count3 = range_count1 + range_count2;
1096  ranges3 = palloc0(range_count3 * sizeof(RangeType *));
1097  memcpy(ranges3, ranges1, range_count1 * sizeof(RangeType *));
1098  memcpy(ranges3 + range_count1, ranges2, range_count2 * sizeof(RangeType *));
1099  PG_RETURN_MULTIRANGE_P(make_multirange(typcache->type_id, typcache->rngtype,
1100  range_count3, ranges3));
1101 }
1102 
1103 /* multirange minus */
1104 Datum
1105 multirange_minus(PG_FUNCTION_ARGS)
1106 {
1107  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1108  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1109  Oid mltrngtypoid = MultirangeTypeGetOid(mr1);
1110  TypeCacheEntry *typcache;
1111  TypeCacheEntry *rangetyp;
1112  int32 range_count1;
1113  int32 range_count2;
1114  RangeType **ranges1;
1115  RangeType **ranges2;
1116 
1117  typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1118  rangetyp = typcache->rngtype;
1119 
1120  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
1121  PG_RETURN_MULTIRANGE_P(mr1);
1122 
1123  multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
1124  multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
1125 
1126  PG_RETURN_MULTIRANGE_P(multirange_minus_internal(mltrngtypoid,
1127  rangetyp,
1128  range_count1,
1129  ranges1,
1130  range_count2,
1131  ranges2));
1132 }
1133 
1134 MultirangeType *
1135 multirange_minus_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
1136  int32 range_count1, RangeType **ranges1,
1137  int32 range_count2, RangeType **ranges2)
1138 {
1139  RangeType *r1;
1140  RangeType *r2;
1141  RangeType **ranges3;
1142  int32 range_count3;
1143  int32 i1;
1144  int32 i2;
1145 
1146  /*
1147  * Worst case: every range in ranges1 makes a different cut to some range
1148  * in ranges2.
1149  */
1150  ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
1151  range_count3 = 0;
1152 
1153  /*
1154  * For each range in mr1, keep subtracting until it's gone or the ranges
1155  * in mr2 have passed it. After a subtraction we assign what's left back
1156  * to r1. The parallel progress through mr1 and mr2 is similar to
1157  * multirange_overlaps_multirange_internal.
1158  */
1159  r2 = ranges2[0];
1160  for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
1161  {
1162  r1 = ranges1[i1];
1163 
1164  /* Discard r2s while r2 << r1 */
1165  while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
1166  {
1167  r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1168  }
1169 
1170  while (r2 != NULL)
1171  {
1172  if (range_split_internal(rangetyp, r1, r2, &ranges3[range_count3], &r1))
1173  {
1174  /*
1175  * If r2 takes a bite out of the middle of r1, we need two
1176  * outputs
1177  */
1178  range_count3++;
1179  r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1180 
1181  }
1182  else if (range_overlaps_internal(rangetyp, r1, r2))
1183  {
1184  /*
1185  * If r2 overlaps r1, replace r1 with r1 - r2.
1186  */
1187  r1 = range_minus_internal(rangetyp, r1, r2);
1188 
1189  /*
1190  * If r2 goes past r1, then we need to stay with it, in case
1191  * it hits future r1s. Otherwise we need to keep r1, in case
1192  * future r2s hit it. Since we already subtracted, there's no
1193  * point in using the overright/overleft calls.
1194  */
1195  if (RangeIsEmpty(r1) || range_before_internal(rangetyp, r1, r2))
1196  break;
1197  else
1198  r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1199 
1200  }
1201  else
1202  {
1203  /*
1204  * This and all future r2s are past r1, so keep them. Also
1205  * assign whatever is left of r1 to the result.
1206  */
1207  break;
1208  }
1209  }
1210 
1211  /*
1212  * Nothing else can remove anything from r1, so keep it. Even if r1 is
1213  * empty here, make_multirange will remove it.
1214  */
1215  ranges3[range_count3++] = r1;
1216  }
1217 
1218  return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
1219 }
1220 
1221 /* multirange intersection */
1222 Datum
1223 multirange_intersect(PG_FUNCTION_ARGS)
1224 {
1225  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1226  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1227  Oid mltrngtypoid = MultirangeTypeGetOid(mr1);
1228  TypeCacheEntry *typcache;
1229  TypeCacheEntry *rangetyp;
1230  int32 range_count1;
1231  int32 range_count2;
1232  RangeType **ranges1;
1233  RangeType **ranges2;
1234 
1235  typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1236  rangetyp = typcache->rngtype;
1237 
1238  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
1239  PG_RETURN_MULTIRANGE_P(make_empty_multirange(mltrngtypoid, rangetyp));
1240 
1241  multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1);
1242  multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2);
1243 
1244  PG_RETURN_MULTIRANGE_P(multirange_intersect_internal(mltrngtypoid,
1245  rangetyp,
1246  range_count1,
1247  ranges1,
1248  range_count2,
1249  ranges2));
1250 }
1251 
1252 MultirangeType *
1253 multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
1254  int32 range_count1, RangeType **ranges1,
1255  int32 range_count2, RangeType **ranges2)
1256 {
1257  RangeType *r1;
1258  RangeType *r2;
1259  RangeType **ranges3;
1260  int32 range_count3;
1261  int32 i1;
1262  int32 i2;
1263 
1264  if (range_count1 == 0 || range_count2 == 0)
1265  return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
1266 
1267  /*-----------------------------------------------
1268  * Worst case is a stitching pattern like this:
1269  *
1270  * mr1: --- --- --- ---
1271  * mr2: --- --- ---
1272  * mr3: - - - - - -
1273  *
1274  * That seems to be range_count1 + range_count2 - 1,
1275  * but one extra won't hurt.
1276  *-----------------------------------------------
1277  */
1278  ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
1279  range_count3 = 0;
1280 
1281  /*
1282  * For each range in mr1, keep intersecting until the ranges in mr2 have
1283  * passed it. The parallel progress through mr1 and mr2 is similar to
1284  * multirange_minus_multirange_internal, but we don't have to assign back
1285  * to r1.
1286  */
1287  r2 = ranges2[0];
1288  for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
1289  {
1290  r1 = ranges1[i1];
1291 
1292  /* Discard r2s while r2 << r1 */
1293  while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
1294  {
1295  r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1296  }
1297 
1298  while (r2 != NULL)
1299  {
1300  if (range_overlaps_internal(rangetyp, r1, r2))
1301  {
1302  /* Keep the overlapping part */
1303  ranges3[range_count3++] = range_intersect_internal(rangetyp, r1, r2);
1304 
1305  /* If we "used up" all of r2, go to the next one... */
1306  if (range_overleft_internal(rangetyp, r2, r1))
1307  r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1308 
1309  /* ...otherwise go to the next r1 */
1310  else
1311  break;
1312  }
1313  else
1314  /* We're past r1, so move to the next one */
1315  break;
1316  }
1317 
1318  /* If we're out of r2s, there can be no more intersections */
1319  if (r2 == NULL)
1320  break;
1321  }
1322 
1323  return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
1324 }
1325 
1326 /*
1327  * range_agg_transfn: combine adjacent/overlapping ranges.
1328  *
1329  * All we do here is gather the input ranges into an array
1330  * so that the finalfn can sort and combine them.
1331  */
1332 Datum
1333 range_agg_transfn(PG_FUNCTION_ARGS)
1334 {
1335  MemoryContext aggContext;
1336  Oid rngtypoid;
1337  ArrayBuildState *state;
1338 
1339  if (!AggCheckCallContext(fcinfo, &aggContext))
1340  elog(ERROR, "range_agg_transfn called in non-aggregate context");
1341 
1342  rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
1343  if (!type_is_range(rngtypoid))
1344  ereport(ERROR,
1345  (errcode(ERRCODE_DATATYPE_MISMATCH),
1346  errmsg("range_agg must be called with a range")));
1347 
1348  if (PG_ARGISNULL(0))
1349  state = initArrayResult(rngtypoid, aggContext, false);
1350  else
1351  state = (ArrayBuildState *) PG_GETARG_POINTER(0);
1352 
1353  /* skip NULLs */
1354  if (!PG_ARGISNULL(1))
1355  accumArrayResult(state, PG_GETARG_DATUM(1), false, rngtypoid, aggContext);
1356 
1357  PG_RETURN_POINTER(state);
1358 }
1359 
1360 /*
1361  * range_agg_finalfn: use our internal array to merge touching ranges.
1362  */
1363 Datum
1364 range_agg_finalfn(PG_FUNCTION_ARGS)
1365 {
1366  MemoryContext aggContext;
1367  Oid mltrngtypoid;
1368  TypeCacheEntry *typcache;
1369  ArrayBuildState *state;
1370  int32 range_count;
1371  RangeType **ranges;
1372  int i;
1373 
1374  if (!AggCheckCallContext(fcinfo, &aggContext))
1375  elog(ERROR, "range_agg_finalfn called in non-aggregate context");
1376 
1377  state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
1378  if (state == NULL)
1379  /* This shouldn't be possible, but just in case.... */
1380  PG_RETURN_NULL();
1381 
1382  /* Also return NULL if we had zero inputs, like other aggregates */
1383  range_count = state->nelems;
1384  if (range_count == 0)
1385  PG_RETURN_NULL();
1386 
1387  mltrngtypoid = get_fn_expr_rettype(fcinfo->flinfo);
1388  typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1389 
1390  ranges = palloc0(range_count * sizeof(RangeType *));
1391  for (i = 0; i < range_count; i++)
1392  ranges[i] = DatumGetRangeTypeP(state->dvalues[i]);
1393 
1394  PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypoid, typcache->rngtype, range_count, ranges));
1395 }
1396 
1397 Datum
1398 multirange_intersect_agg_transfn(PG_FUNCTION_ARGS)
1399 {
1400  MemoryContext aggContext;
1401  Oid mltrngtypoid;
1402  TypeCacheEntry *typcache;
1403  MultirangeType *result;
1404  MultirangeType *current;
1405  int32 range_count1;
1406  int32 range_count2;
1407  RangeType **ranges1;
1408  RangeType **ranges2;
1409 
1410  if (!AggCheckCallContext(fcinfo, &aggContext))
1411  elog(ERROR, "multirange_intersect_agg_transfn called in non-aggregate context");
1412 
1413  mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
1414  if (!type_is_multirange(mltrngtypoid))
1415  ereport(ERROR,
1416  (errcode(ERRCODE_DATATYPE_MISMATCH),
1417  errmsg("range_intersect_agg must be called with a multirange")));
1418 
1419  typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1420 
1421  /* strictness ensures these are non-null */
1422  result = PG_GETARG_MULTIRANGE_P(0);
1423  current = PG_GETARG_MULTIRANGE_P(1);
1424 
1425  multirange_deserialize(typcache->rngtype, result, &range_count1, &ranges1);
1426  multirange_deserialize(typcache->rngtype, current, &range_count2, &ranges2);
1427 
1428  result = multirange_intersect_internal(mltrngtypoid,
1429  typcache->rngtype,
1430  range_count1,
1431  ranges1,
1432  range_count2,
1433  ranges2);
1434  PG_RETURN_RANGE_P(result);
1435 }
1436 
1437 
1438 /* multirange -> element type functions */
1439 
1440 /* extract lower bound value */
1441 Datum
1442 multirange_lower(PG_FUNCTION_ARGS)
1443 {
1444  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1445  TypeCacheEntry *typcache;
1446  RangeBound lower;
1447  RangeBound upper;
1448 
1449  if (MultirangeIsEmpty(mr))
1450  PG_RETURN_NULL();
1451 
1452  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1453 
1454  multirange_get_bounds(typcache->rngtype, mr, 0,
1455  &lower, &upper);
1456 
1457  if (!lower.infinite)
1458  PG_RETURN_DATUM(lower.val);
1459  else
1460  PG_RETURN_NULL();
1461 }
1462 
1463 /* extract upper bound value */
1464 Datum
1465 multirange_upper(PG_FUNCTION_ARGS)
1466 {
1467  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1468  TypeCacheEntry *typcache;
1469  RangeBound lower;
1470  RangeBound upper;
1471 
1472  if (MultirangeIsEmpty(mr))
1473  PG_RETURN_NULL();
1474 
1475  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1476 
1477  multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1478  &lower, &upper);
1479 
1480  if (!upper.infinite)
1481  PG_RETURN_DATUM(upper.val);
1482  else
1483  PG_RETURN_NULL();
1484 }
1485 
1486 
1487 /* multirange -> bool functions */
1488 
1489 /* is multirange empty? */
1490 Datum
1491 multirange_empty(PG_FUNCTION_ARGS)
1492 {
1493  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1494 
1495  PG_RETURN_BOOL(MultirangeIsEmpty(mr));
1496 }
1497 
1498 /* is lower bound inclusive? */
1499 Datum
1500 multirange_lower_inc(PG_FUNCTION_ARGS)
1501 {
1502  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1503  TypeCacheEntry *typcache;
1504  RangeBound lower;
1505  RangeBound upper;
1506 
1507  if (MultirangeIsEmpty(mr))
1508  PG_RETURN_BOOL(false);
1509 
1510  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1511  multirange_get_bounds(typcache->rngtype, mr, 0,
1512  &lower, &upper);
1513 
1514  PG_RETURN_BOOL(lower.inclusive);
1515 }
1516 
1517 /* is upper bound inclusive? */
1518 Datum
1519 multirange_upper_inc(PG_FUNCTION_ARGS)
1520 {
1521  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1522  TypeCacheEntry *typcache;
1523  RangeBound lower;
1524  RangeBound upper;
1525 
1526  if (MultirangeIsEmpty(mr))
1527  PG_RETURN_BOOL(false);
1528 
1529  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1530  multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1531  &lower, &upper);
1532 
1533  PG_RETURN_BOOL(upper.inclusive);
1534 }
1535 
1536 /* is lower bound infinite? */
1537 Datum
1538 multirange_lower_inf(PG_FUNCTION_ARGS)
1539 {
1540  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1541  TypeCacheEntry *typcache;
1542  RangeBound lower;
1543  RangeBound upper;
1544 
1545  if (MultirangeIsEmpty(mr))
1546  PG_RETURN_BOOL(false);
1547 
1548  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1549  multirange_get_bounds(typcache->rngtype, mr, 0,
1550  &lower, &upper);
1551 
1552  PG_RETURN_BOOL(lower.infinite);
1553 }
1554 
1555 /* is upper bound infinite? */
1556 Datum
1557 multirange_upper_inf(PG_FUNCTION_ARGS)
1558 {
1559  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1560  TypeCacheEntry *typcache;
1561  RangeBound lower;
1562  RangeBound upper;
1563 
1564  if (MultirangeIsEmpty(mr))
1565  PG_RETURN_BOOL(false);
1566 
1567  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1568  multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1569  &lower, &upper);
1570 
1571  PG_RETURN_BOOL(upper.infinite);
1572 }
1573 
1574 
1575 
1576 /* multirange, element -> bool functions */
1577 
1578 /* contains? */
1579 Datum
1580 multirange_contains_elem(PG_FUNCTION_ARGS)
1581 {
1582  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1583  Datum val = PG_GETARG_DATUM(1);
1584  TypeCacheEntry *typcache;
1585 
1586  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1587 
1588  PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
1589 }
1590 
1591 /* contained by? */
1592 Datum
1593 elem_contained_by_multirange(PG_FUNCTION_ARGS)
1594 {
1595  Datum val = PG_GETARG_DATUM(0);
1596  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1597  TypeCacheEntry *typcache;
1598 
1599  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1600 
1601  PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
1602 }
1603 
1604 /*
1605  * Comparison function for checking if any range of multirange contains given
1606  * key element using binary search.
1607  */
1608 static int
1609 multirange_elem_bsearch_comparison(TypeCacheEntry *typcache,
1610  RangeBound *lower, RangeBound *upper,
1611  void *key, bool *match)
1612 {
1613  Datum val = *((Datum *) key);
1614  int cmp;
1615 
1616  if (!lower->infinite)
1617  {
1618  cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1619  typcache->rng_collation,
1620  lower->val, val));
1621  if (cmp > 0 || (cmp == 0 && !lower->inclusive))
1622  return -1;
1623  }
1624 
1625  if (!upper->infinite)
1626  {
1627  cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1628  typcache->rng_collation,
1629  upper->val, val));
1630  if (cmp < 0 || (cmp == 0 && !upper->inclusive))
1631  return 1;
1632  }
1633 
1634  *match = true;
1635  return 0;
1636 }
1637 
1638 /*
1639  * Test whether multirange mr contains a specific element value.
1640  */
1641 bool
1642 multirange_contains_elem_internal(TypeCacheEntry *rangetyp,
1643  const MultirangeType *mr, Datum val)
1644 {
1645  if (MultirangeIsEmpty(mr))
1646  return false;
1647 
1648  return multirange_bsearch_match(rangetyp, mr, &val,
1649  multirange_elem_bsearch_comparison);
1650 }
1651 
1652 /* multirange, range -> bool functions */
1653 
1654 /* contains? */
1655 Datum
1656 multirange_contains_range(PG_FUNCTION_ARGS)
1657 {
1658  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1659  RangeType *r = PG_GETARG_RANGE_P(1);
1660  TypeCacheEntry *typcache;
1661 
1662  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1663 
1664  PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
1665 }
1666 
1667 Datum
1668 range_contains_multirange(PG_FUNCTION_ARGS)
1669 {
1670  RangeType *r = PG_GETARG_RANGE_P(0);
1671  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1672  TypeCacheEntry *typcache;
1673 
1674  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1675 
1676  PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
1677 }
1678 
1679 /* contained by? */
1680 Datum
1681 range_contained_by_multirange(PG_FUNCTION_ARGS)
1682 {
1683  RangeType *r = PG_GETARG_RANGE_P(0);
1684  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1685  TypeCacheEntry *typcache;
1686 
1687  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1688 
1689  PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
1690 }
1691 
1692 Datum
1693 multirange_contained_by_range(PG_FUNCTION_ARGS)
1694 {
1695  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1696  RangeType *r = PG_GETARG_RANGE_P(1);
1697  TypeCacheEntry *typcache;
1698 
1699  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1700 
1701  PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
1702 }
1703 
1704 /*
1705  * Comparison function for checking if any range of multirange contains given
1706  * key range using binary search.
1707  */
1708 static int
1709 multirange_range_contains_bsearch_comparison(TypeCacheEntry *typcache,
1710  RangeBound *lower, RangeBound *upper,
1711  void *key, bool *match)
1712 {
1713  RangeBound *keyLower = (RangeBound *) key;
1714  RangeBound *keyUpper = (RangeBound *) key + 1;
1715 
1716  /* Check if key range is strictly in the left or in the right */
1717  if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
1718  return -1;
1719  if (range_cmp_bounds(typcache, keyLower, upper) > 0)
1720  return 1;
1721 
1722  /*
1723  * At this point we found overlapping range. But we have to check if it
1724  * really contains the key range. Anyway, we have to stop our search
1725  * here, because multirange contains only non-overlapping ranges.
1726  */
1727  *match = range_bounds_contains(typcache, lower, upper, keyLower, keyUpper);
1728 
1729  return 0;
1730 }
1731 
1732 /*
1733  * Test whether multirange mr contains a specific range r.
1734  */
1735 bool
1736 multirange_contains_range_internal(TypeCacheEntry *rangetyp,
1737  const MultirangeType *mr,
1738  const RangeType *r)
1739 {
1740  RangeBound bounds[2];
1741  bool empty;
1742 
1743  /*
1744  * Every multirange contains an infinite number of empty ranges, even an
1745  * empty one.
1746  */
1747  if (RangeIsEmpty(r))
1748  return true;
1749 
1750  if (MultirangeIsEmpty(mr))
1751  return false;
1752 
1753  range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
1754  Assert(!empty);
1755 
1756  return multirange_bsearch_match(rangetyp, mr, bounds,
1757  multirange_range_contains_bsearch_comparison);
1758 }
1759 
1760 /*
1761  * Test whether range r contains a multirange mr.
1762  */
1763 bool
1764 range_contains_multirange_internal(TypeCacheEntry *rangetyp,
1765  const RangeType *r,
1766  const MultirangeType *mr)
1767 {
1768  RangeBound lower1,
1769  upper1,
1770  lower2,
1771  upper2,
1772  tmp;
1773  bool empty;
1774 
1775  /*
1776  * Every range contains an infinite number of empty multiranges, even an
1777  * empty one.
1778  */
1779  if (MultirangeIsEmpty(mr))
1780  return true;
1781 
1782  if (RangeIsEmpty(r))
1783  return false;
1784 
1785  /* Range contains multirange iff it contains its union range. */
1786  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
1787  Assert(!empty);
1788  multirange_get_bounds(rangetyp, mr, 0, &lower2, &tmp);
1789  multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper2);
1790 
1791  return range_bounds_contains(rangetyp, &lower1, &upper1, &lower2, &upper2);
1792 }
1793 
1794 
1795 /* multirange, multirange -> bool functions */
1796 
1797 /* equality (internal version) */
1798 bool
1799 multirange_eq_internal(TypeCacheEntry *rangetyp,
1800  const MultirangeType *mr1,
1801  const MultirangeType *mr2)
1802 {
1803  int32 range_count_1;
1804  int32 range_count_2;
1805  int32 i;
1806  RangeBound lower1,
1807  upper1,
1808  lower2,
1809  upper2;
1810 
1811  /* Different types should be prevented by ANYMULTIRANGE matching rules */
1812  if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
1813  elog(ERROR, "multirange types do not match");
1814 
1815  range_count_1 = mr1->rangeCount;
1816  range_count_2 = mr2->rangeCount;
1817 
1818  if (range_count_1 != range_count_2)
1819  return false;
1820 
1821  for (i = 0; i < range_count_1; i++)
1822  {
1823  multirange_get_bounds(rangetyp, mr1, i, &lower1, &upper1);
1824  multirange_get_bounds(rangetyp, mr2, i, &lower2, &upper2);
1825 
1826  if (range_cmp_bounds(rangetyp, &lower1, &lower2) != 0 ||
1827  range_cmp_bounds(rangetyp, &upper1, &upper2) != 0)
1828  return false;
1829  }
1830 
1831  return true;
1832 }
1833 
1834 /* equality */
1835 Datum
1836 multirange_eq(PG_FUNCTION_ARGS)
1837 {
1838  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1839  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1840  TypeCacheEntry *typcache;
1841 
1842  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
1843 
1844  PG_RETURN_BOOL(multirange_eq_internal(typcache->rngtype, mr1, mr2));
1845 }
1846 
1847 /* inequality (internal version) */
1848 bool
1849 multirange_ne_internal(TypeCacheEntry *rangetyp,
1850  const MultirangeType *mr1,
1851  const MultirangeType *mr2)
1852 {
1853  return (!multirange_eq_internal(rangetyp, mr1, mr2));
1854 }
1855 
1856 /* inequality */
1857 Datum
1858 multirange_ne(PG_FUNCTION_ARGS)
1859 {
1860  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1861  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1862  TypeCacheEntry *typcache;
1863 
1864  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
1865 
1866  PG_RETURN_BOOL(multirange_ne_internal(typcache->rngtype, mr1, mr2));
1867 }
1868 
1869 /* overlaps? */
1870 Datum
1871 range_overlaps_multirange(PG_FUNCTION_ARGS)
1872 {
1873  RangeType *r = PG_GETARG_RANGE_P(0);
1874  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1875  TypeCacheEntry *typcache;
1876 
1877  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1878 
1879  PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
1880 }
1881 
1882 Datum
1883 multirange_overlaps_range(PG_FUNCTION_ARGS)
1884 {
1885  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1886  RangeType *r = PG_GETARG_RANGE_P(1);
1887  TypeCacheEntry *typcache;
1888 
1889  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1890 
1891  PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
1892 }
1893 
1894 Datum
1895 multirange_overlaps_multirange(PG_FUNCTION_ARGS)
1896 {
1897  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1898  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1899  TypeCacheEntry *typcache;
1900 
1901  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
1902 
1903  PG_RETURN_BOOL(multirange_overlaps_multirange_internal(typcache->rngtype, mr1, mr2));
1904 }
1905 
1906 /*
1907  * Comparison function for checking if any range of multirange overlaps given
1908  * key range using binary search.
1909  */
1910 static int
1911 multirange_range_overlaps_bsearch_comparison(TypeCacheEntry *typcache,
1912  RangeBound *lower, RangeBound *upper,
1913  void *key, bool *match)
1914 {
1915  RangeBound *keyLower = (RangeBound *) key;
1916  RangeBound *keyUpper = (RangeBound *) key + 1;
1917 
1918  if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
1919  return -1;
1920  if (range_cmp_bounds(typcache, keyLower, upper) > 0)
1921  return 1;
1922 
1923  *match = true;
1924  return 0;
1925 }
1926 
1927 bool
1928 range_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
1929  const RangeType *r,
1930  const MultirangeType *mr)
1931 {
1932  RangeBound bounds[2];
1933  bool empty;
1934 
1935  /*
1936  * Empties never overlap, even with empties. (This seems strange since
1937  * they *do* contain each other, but we want to follow how ranges work.)
1938  */
1939  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
1940  return false;
1941 
1942  range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
1943  Assert(!empty);
1944 
1945  return multirange_bsearch_match(rangetyp, mr, bounds,
1946  multirange_range_overlaps_bsearch_comparison);
1947 }
1948 
1949 bool
1950 multirange_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
1951  const MultirangeType *mr1,
1952  const MultirangeType *mr2)
1953 {
1954  int32 range_count1;
1955  int32 range_count2;
1956  int32 i1;
1957  int32 i2;
1958  RangeBound lower1,
1959  upper1,
1960  lower2,
1961  upper2;
1962 
1963  /*
1964  * Empties never overlap, even with empties. (This seems strange since
1965  * they *do* contain each other, but we want to follow how ranges work.)
1966  */
1967  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
1968  return false;
1969 
1970  range_count1 = mr1->rangeCount;
1971  range_count2 = mr2->rangeCount;
1972 
1973  /*
1974  * Every range in mr1 gets a chance to overlap with the ranges in mr2, but
1975  * we can use their ordering to avoid O(n^2). This is similar to
1976  * range_overlaps_multirange where r1 : r2 :: mrr : r, but there if we
1977  * don't find an overlap with r we're done, and here if we don't find an
1978  * overlap with r2 we try the next r2.
1979  */
1980  i1 = 0;
1981  multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
1982  for (i1 = 0, i2 = 0; i2 < range_count2; i2++)
1983  {
1984  multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
1985 
1986  /* Discard r1s while r1 << r2 */
1987  while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
1988  {
1989  if (++i1 >= range_count1)
1990  return false;
1991  multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
1992  }
1993 
1994  /*
1995  * If r1 && r2, we're done, otherwise we failed to find an overlap for
1996  * r2, so go to the next one.
1997  */
1998  if (range_bounds_overlaps(rangetyp, &lower1, &upper1, &lower2, &upper2))
1999  return true;
2000  }
2001 
2002  /* We looked through all of mr2 without finding an overlap */
2003  return false;
2004 }
2005 
2006 /* does not extend to right of? */
2007 bool
2008 range_overleft_multirange_internal(TypeCacheEntry *rangetyp,
2009  const RangeType *r,
2010  const MultirangeType *mr)
2011 {
2012  RangeBound lower1,
2013  upper1,
2014  lower2,
2015  upper2;
2016  bool empty;
2017 
2018  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2019  PG_RETURN_BOOL(false);
2020 
2021 
2022  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2023  Assert(!empty);
2024  multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1,
2025  &lower2, &upper2);
2026 
2027  PG_RETURN_BOOL(range_cmp_bounds(rangetyp, &upper1, &upper2) <= 0);
2028 }
2029 
2030 Datum
2031 range_overleft_multirange(PG_FUNCTION_ARGS)
2032 {
2033  RangeType *r = PG_GETARG_RANGE_P(0);
2034  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2035  TypeCacheEntry *typcache;
2036 
2037  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2038 
2039  PG_RETURN_BOOL(range_overleft_multirange_internal(typcache->rngtype, r, mr));
2040 }
2041 
2042 Datum
2043 multirange_overleft_range(PG_FUNCTION_ARGS)
2044 {
2045  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2046  RangeType *r = PG_GETARG_RANGE_P(1);
2047  TypeCacheEntry *typcache;
2048  RangeBound lower1,
2049  upper1,
2050  lower2,
2051  upper2;
2052  bool empty;
2053 
2054  if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
2055  PG_RETURN_BOOL(false);
2056 
2057  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2058 
2059  multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
2060  &lower1, &upper1);
2061  range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
2062  Assert(!empty);
2063 
2064  PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
2065 }
2066 
2067 Datum
2068 multirange_overleft_multirange(PG_FUNCTION_ARGS)
2069 {
2070  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2071  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2072  TypeCacheEntry *typcache;
2073  RangeBound lower1,
2074  upper1,
2075  lower2,
2076  upper2;
2077 
2078  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2079  PG_RETURN_BOOL(false);
2080 
2081  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2082 
2083  multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1,
2084  &lower1, &upper1);
2085  multirange_get_bounds(typcache->rngtype, mr2, mr2->rangeCount - 1,
2086  &lower2, &upper2);
2087 
2088  PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
2089 }
2090 
2091 /* does not extend to left of? */
2092 bool
2093 range_overright_multirange_internal(TypeCacheEntry *rangetyp,
2094  const RangeType *r,
2095  const MultirangeType *mr)
2096 {
2097  RangeBound lower1,
2098  upper1,
2099  lower2,
2100  upper2;
2101  bool empty;
2102 
2103  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2104  PG_RETURN_BOOL(false);
2105 
2106  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2107  Assert(!empty);
2108  multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
2109 
2110  return (range_cmp_bounds(rangetyp, &lower1, &lower2) >= 0);
2111 }
2112 
2113 Datum
2114 range_overright_multirange(PG_FUNCTION_ARGS)
2115 {
2116  RangeType *r = PG_GETARG_RANGE_P(0);
2117  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2118  TypeCacheEntry *typcache;
2119 
2120  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2121 
2122  PG_RETURN_BOOL(range_overright_multirange_internal(typcache->rngtype, r, mr));
2123 }
2124 
2125 Datum
2126 multirange_overright_range(PG_FUNCTION_ARGS)
2127 {
2128  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2129  RangeType *r = PG_GETARG_RANGE_P(1);
2130  TypeCacheEntry *typcache;
2131  RangeBound lower1,
2132  upper1,
2133  lower2,
2134  upper2;
2135  bool empty;
2136 
2137  if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
2138  PG_RETURN_BOOL(false);
2139 
2140  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2141 
2142  multirange_get_bounds(typcache->rngtype, mr, 0, &lower1, &upper1);
2143  range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
2144  Assert(!empty);
2145 
2146  PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
2147 }
2148 
2149 Datum
2150 multirange_overright_multirange(PG_FUNCTION_ARGS)
2151 {
2152  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2153  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2154  TypeCacheEntry *typcache;
2155  RangeBound lower1,
2156  upper1,
2157  lower2,
2158  upper2;
2159 
2160  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2161  PG_RETURN_BOOL(false);
2162 
2163  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2164 
2165  multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1);
2166  multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2);
2167 
2168  PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
2169 }
2170 
2171 /* contains? */
2172 Datum
2173 multirange_contains_multirange(PG_FUNCTION_ARGS)
2174 {
2175  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2176  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2177  TypeCacheEntry *typcache;
2178 
2179  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2180 
2181  PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr1, mr2));
2182 }
2183 
2184 /* contained by? */
2185 Datum
2186 multirange_contained_by_multirange(PG_FUNCTION_ARGS)
2187 {
2188  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2189  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2190  TypeCacheEntry *typcache;
2191 
2192  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2193 
2194  PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr2, mr1));
2195 }
2196 
2197 /*
2198  * Test whether multirange mr1 contains every range from another multirange mr2.
2199  */
2200 bool
2201 multirange_contains_multirange_internal(TypeCacheEntry *rangetyp,
2202  const MultirangeType *mr1,
2203  const MultirangeType *mr2)
2204 {
2205  int32 range_count1 = mr1->rangeCount;
2206  int32 range_count2 = mr2->rangeCount;
2207  int i1,
2208  i2;
2209  RangeBound lower1,
2210  upper1,
2211  lower2,
2212  upper2;
2213 
2214  /*
2215  * We follow the same logic for empties as ranges: - an empty multirange
2216  * contains an empty range/multirange. - an empty multirange can't contain
2217  * any other range/multirange. - an empty multirange is contained by any
2218  * other range/multirange.
2219  */
2220 
2221  if (range_count2 == 0)
2222  return true;
2223  if (range_count1 == 0)
2224  return false;
2225 
2226  /*
2227  * Every range in mr2 must be contained by some range in mr1. To avoid
2228  * O(n^2) we walk through both ranges in tandem.
2229  */
2230  i1 = 0;
2231  multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2232  for (i2 = 0; i2 < range_count2; i2++)
2233  {
2234  multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
2235 
2236  /* Discard r1s while r1 << r2 */
2237  while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
2238  {
2239  if (++i1 >= range_count1)
2240  return false;
2241  multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2242  }
2243 
2244  /*
2245  * If r1 @> r2, go to the next r2, otherwise return false (since every
2246  * r1[n] and r1[n+1] must have a gap). Note this will give weird
2247  * answers if you don't canonicalize, e.g. with a custom
2248  * int2multirange {[1,1], [2,2]} there is a "gap". But that is
2249  * consistent with other range operators, e.g. '[1,1]'::int2range -|-
2250  * '[2,2]'::int2range is false.
2251  */
2252  if (!range_bounds_contains(rangetyp, &lower1, &upper1,
2253  &lower2, &upper2))
2254  return false;
2255  }
2256 
2257  /* All ranges in mr2 are satisfied */
2258  return true;
2259 }
2260 
2261 /* strictly left of? */
2262 Datum
2263 range_before_multirange(PG_FUNCTION_ARGS)
2264 {
2265  RangeType *r = PG_GETARG_RANGE_P(0);
2266  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2267  TypeCacheEntry *typcache;
2268 
2269  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2270 
2271  PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
2272 }
2273 
2274 Datum
2275 multirange_before_range(PG_FUNCTION_ARGS)
2276 {
2277  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2278  RangeType *r = PG_GETARG_RANGE_P(1);
2279  TypeCacheEntry *typcache;
2280 
2281  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2282 
2283  PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
2284 }
2285 
2286 Datum
2287 multirange_before_multirange(PG_FUNCTION_ARGS)
2288 {
2289  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2290  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2291  TypeCacheEntry *typcache;
2292 
2293  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2294 
2295  PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr1, mr2));
2296 }
2297 
2298 /* strictly right of? */
2299 Datum
2300 range_after_multirange(PG_FUNCTION_ARGS)
2301 {
2302  RangeType *r = PG_GETARG_RANGE_P(0);
2303  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2304  TypeCacheEntry *typcache;
2305 
2306  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2307 
2308  PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
2309 }
2310 
2311 Datum
2312 multirange_after_range(PG_FUNCTION_ARGS)
2313 {
2314  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2315  RangeType *r = PG_GETARG_RANGE_P(1);
2316  TypeCacheEntry *typcache;
2317 
2318  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2319 
2320  PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
2321 }
2322 
2323 Datum
2324 multirange_after_multirange(PG_FUNCTION_ARGS)
2325 {
2326  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2327  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2328  TypeCacheEntry *typcache;
2329 
2330  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2331 
2332  PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr2, mr1));
2333 }
2334 
2335 /* strictly left of? (internal version) */
2336 bool
2337 range_before_multirange_internal(TypeCacheEntry *rangetyp,
2338  const RangeType *r,
2339  const MultirangeType *mr)
2340 {
2341  RangeBound lower1,
2342  upper1,
2343  lower2,
2344  upper2;
2345  bool empty;
2346 
2347  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2348  return false;
2349 
2350  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2351  Assert(!empty);
2352 
2353  multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
2354 
2355  return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
2356 }
2357 
2358 bool
2359 multirange_before_multirange_internal(TypeCacheEntry *rangetyp,
2360  const MultirangeType *mr1,
2361  const MultirangeType *mr2)
2362 {
2363  RangeBound lower1,
2364  upper1,
2365  lower2,
2366  upper2;
2367 
2368  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2369  return false;
2370 
2371  multirange_get_bounds(rangetyp, mr1, mr1->rangeCount - 1,
2372  &lower1, &upper1);
2373  multirange_get_bounds(rangetyp, mr2, 0,
2374  &lower2, &upper2);
2375 
2376  return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
2377 }
2378 
2379 /* strictly right of? (internal version) */
2380 bool
2381 range_after_multirange_internal(TypeCacheEntry *rangetyp,
2382  const RangeType *r,
2383  const MultirangeType *mr)
2384 {
2385  RangeBound lower1,
2386  upper1,
2387  lower2,
2388  upper2;
2389  bool empty;
2390  int32 range_count;
2391 
2392  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2393  return false;
2394 
2395  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2396  Assert(!empty);
2397 
2398  range_count = mr->rangeCount;
2399  multirange_get_bounds(rangetyp, mr, range_count - 1,
2400  &lower2, &upper2);
2401 
2402  return (range_cmp_bounds(rangetyp, &lower1, &upper2) > 0);
2403 }
2404 
2405 bool
2406 range_adjacent_multirange_internal(TypeCacheEntry *rangetyp,
2407  const RangeType *r,
2408  const MultirangeType *mr)
2409 {
2410  RangeBound lower1,
2411  upper1,
2412  lower2,
2413  upper2;
2414  bool empty;
2415  int32 range_count;
2416 
2417  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2418  return false;
2419 
2420  range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2421  Assert(!empty);
2422 
2423  range_count = mr->rangeCount;
2424  multirange_get_bounds(rangetyp, mr, 0,
2425  &lower2, &upper2);
2426 
2427  if (bounds_adjacent(rangetyp, upper1, lower2))
2428  return true;
2429 
2430  if (range_count > 1)
2431  multirange_get_bounds(rangetyp, mr, range_count - 1,
2432  &lower2, &upper2);
2433 
2434  if (bounds_adjacent(rangetyp, upper2, lower1))
2435  return true;
2436 
2437  return false;
2438 }
2439 
2440 /* adjacent to? */
2441 Datum
2442 range_adjacent_multirange(PG_FUNCTION_ARGS)
2443 {
2444  RangeType *r = PG_GETARG_RANGE_P(0);
2445  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2446  TypeCacheEntry *typcache;
2447 
2448  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2449 
2450  PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
2451 }
2452 
2453 Datum
2454 multirange_adjacent_range(PG_FUNCTION_ARGS)
2455 {
2456  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2457  RangeType *r = PG_GETARG_RANGE_P(1);
2458  TypeCacheEntry *typcache;
2459 
2460  if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2461  return false;
2462 
2463  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2464 
2465  PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
2466 }
2467 
2468 Datum
2469 multirange_adjacent_multirange(PG_FUNCTION_ARGS)
2470 {
2471  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2472  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2473  TypeCacheEntry *typcache;
2474  int32 range_count1;
2475  int32 range_count2;
2476  RangeBound lower1,
2477  upper1,
2478  lower2,
2479  upper2;
2480 
2481  if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2482  return false;
2483 
2484  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2485 
2486  range_count1 = mr1->rangeCount;
2487  range_count2 = mr2->rangeCount;
2488  multirange_get_bounds(typcache->rngtype, mr1, range_count1 - 1,
2489  &lower1, &upper1);
2490  multirange_get_bounds(typcache->rngtype, mr2, 0,
2491  &lower2, &upper2);
2492  if (bounds_adjacent(typcache->rngtype, upper1, lower2))
2493  PG_RETURN_BOOL(true);
2494 
2495  if (range_count1 > 1)
2496  multirange_get_bounds(typcache->rngtype, mr1, 0,
2497  &lower1, &upper1);
2498  if (range_count2 > 1)
2499  multirange_get_bounds(typcache->rngtype, mr2, range_count2 - 1,
2500  &lower2, &upper2);
2501  if (bounds_adjacent(typcache->rngtype, upper2, lower1))
2502  PG_RETURN_BOOL(true);
2503  PG_RETURN_BOOL(false);
2504 }
2505 
2506 /* Btree support */
2507 
2508 /* btree comparator */
2509 Datum
2510 multirange_cmp(PG_FUNCTION_ARGS)
2511 {
2512  MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2513  MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2514  int32 range_count_1;
2515  int32 range_count_2;
2516  int32 range_count_max;
2517  int32 i;
2518  TypeCacheEntry *typcache;
2519  int cmp = 0; /* If both are empty we'll use this. */
2520 
2521  /* Different types should be prevented by ANYMULTIRANGE matching rules */
2522  if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
2523  elog(ERROR, "multirange types do not match");
2524 
2525  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2526 
2527  range_count_1 = mr1->rangeCount;
2528  range_count_2 = mr2->rangeCount;
2529 
2530  /* Loop over source data */
2531  range_count_max = Max(range_count_1, range_count_2);
2532  for (i = 0; i < range_count_max; i++)
2533  {
2534  RangeBound lower1,
2535  upper1,
2536  lower2,
2537  upper2;
2538 
2539  /*
2540  * If one multirange is shorter, it's as if it had empty ranges at the
2541  * end to extend its length. An empty range compares earlier than any
2542  * other range, so the shorter multirange comes before the longer.
2543  * This is the same behavior as in other types, e.g. in strings 'aaa'
2544  * < 'aaaaaa'.
2545  */
2546  if (i >= range_count_1)
2547  {
2548  cmp = -1;
2549  break;
2550  }
2551  if (i >= range_count_2)
2552  {
2553  cmp = 1;
2554  break;
2555  }
2556 
2557  multirange_get_bounds(typcache->rngtype, mr1, i, &lower1, &upper1);
2558  multirange_get_bounds(typcache->rngtype, mr2, i, &lower2, &upper2);
2559 
2560  cmp = range_cmp_bounds(typcache->rngtype, &lower1, &lower2);
2561  if (cmp == 0)
2562  cmp = range_cmp_bounds(typcache->rngtype, &upper1, &upper2);
2563  if (cmp != 0)
2564  break;
2565  }
2566 
2567  PG_FREE_IF_COPY(mr1, 0);
2568  PG_FREE_IF_COPY(mr2, 1);
2569 
2570  PG_RETURN_INT32(cmp);
2571 }
2572 
2573 /* inequality operators using the multirange_cmp function */
2574 Datum
2575 multirange_lt(PG_FUNCTION_ARGS)
2576 {
2577  int cmp = multirange_cmp(fcinfo);
2578 
2579  PG_RETURN_BOOL(cmp < 0);
2580 }
2581 
2582 Datum
2583 multirange_le(PG_FUNCTION_ARGS)
2584 {
2585  int cmp = multirange_cmp(fcinfo);
2586 
2587  PG_RETURN_BOOL(cmp <= 0);
2588 }
2589 
2590 Datum
2591 multirange_ge(PG_FUNCTION_ARGS)
2592 {
2593  int cmp = multirange_cmp(fcinfo);
2594 
2595  PG_RETURN_BOOL(cmp >= 0);
2596 }
2597 
2598 Datum
2599 multirange_gt(PG_FUNCTION_ARGS)
2600 {
2601  int cmp = multirange_cmp(fcinfo);
2602 
2603  PG_RETURN_BOOL(cmp > 0);
2604 }
2605 
2606 /* multirange -> range functions */
2607 
2608 /* Find the smallest range that includes everything in the multirange */
2609 Datum
2610 range_merge_from_multirange(PG_FUNCTION_ARGS)
2611 {
2612  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2613  Oid mltrngtypoid = MultirangeTypeGetOid(mr);
2614  TypeCacheEntry *typcache;
2615  RangeType *result;
2616 
2617  typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
2618 
2619  if (MultirangeIsEmpty(mr))
2620  {
2621  result = make_empty_range(typcache->rngtype);
2622  }
2623  else if (mr->rangeCount == 1)
2624  {
2625  result = multirange_get_range(typcache->rngtype, mr, 0);
2626  }
2627  else
2628  {
2629  RangeBound firstLower,
2630  firstUpper,
2631  lastLower,
2632  lastUpper;
2633 
2634  multirange_get_bounds(typcache->rngtype, mr, 0,
2635  &firstLower, &firstUpper);
2636  multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
2637  &lastLower, &lastUpper);
2638 
2639  result = make_range(typcache->rngtype, &firstLower, &lastUpper, false);
2640  }
2641 
2642  PG_RETURN_RANGE_P(result);
2643 }
2644 
2645 /* Turn multirange into a set of ranges */
2646 Datum
2647 multirange_unnest(PG_FUNCTION_ARGS)
2648 {
2649  typedef struct
2650  {
2651  MultirangeType *mr;
2652  TypeCacheEntry *typcache;
2653  int index;
2654  } multirange_unnest_fctx;
2655 
2656  FuncCallContext *funcctx;
2657  multirange_unnest_fctx *fctx;
2658  MemoryContext oldcontext;
2659 
2660  /* stuff done only on the first call of the function */
2661  if (SRF_IS_FIRSTCALL())
2662  {
2663  MultirangeType *mr;
2664 
2665  /* create a function context for cross-call persistence */
2666  funcctx = SRF_FIRSTCALL_INIT();
2667 
2668  /*
2669  * switch to memory context appropriate for multiple function calls
2670  */
2671  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
2672 
2673  /*
2674  * Get the multirange value and detoast if needed. We can't do this
2675  * earlier because if we have to detoast, we want the detoasted copy
2676  * to be in multi_call_memory_ctx, so it will go away when we're done
2677  * and not before. (If no detoast happens, we assume the originally
2678  * passed multirange will stick around till then.)
2679  */
2680  mr = PG_GETARG_MULTIRANGE_P(0);
2681 
2682  /* allocate memory for user context */
2683  fctx = (multirange_unnest_fctx *) palloc(sizeof(multirange_unnest_fctx));
2684 
2685  /* initialize state */
2686  fctx->mr = mr;
2687  fctx->index = 0;
2688  fctx->typcache = lookup_type_cache(MultirangeTypeGetOid(mr),
2689  TYPECACHE_MULTIRANGE_INFO);
2690 
2691  funcctx->user_fctx = fctx;
2692  MemoryContextSwitchTo(oldcontext);
2693  }
2694 
2695  /* stuff done on every call of the function */
2696  funcctx = SRF_PERCALL_SETUP();
2697  fctx = funcctx->user_fctx;
2698 
2699  if (fctx->index < fctx->mr->rangeCount)
2700  {
2701  RangeType *range;
2702 
2703  range = multirange_get_range(fctx->typcache->rngtype,
2704  fctx->mr,
2705  fctx->index);
2706  fctx->index++;
2707 
2708  SRF_RETURN_NEXT(funcctx, RangeTypePGetDatum(range));
2709  }
2710  else
2711  {
2712  /* do when there is no more left */
2713  SRF_RETURN_DONE(funcctx);
2714  }
2715 }
2716 
2717 /* Hash support */
2718 
2719 /* hash a multirange value */
2720 Datum
2721 hash_multirange(PG_FUNCTION_ARGS)
2722 {
2723  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2724  uint32 result = 1;
2725  TypeCacheEntry *typcache,
2726  *scache;
2727  int32 range_count,
2728  i;
2729 
2730  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2731  scache = typcache->rngtype->rngelemtype;
2732  if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
2733  {
2734  scache = lookup_type_cache(scache->type_id,
2735  TYPECACHE_HASH_PROC_FINFO);
2736  if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
2737  ereport(ERROR,
2738  (errcode(ERRCODE_UNDEFINED_FUNCTION),
2739  errmsg("could not identify a hash function for type %s",
2740  format_type_be(scache->type_id))));
2741  }
2742 
2743  range_count = mr->rangeCount;
2744  for (i = 0; i < range_count; i++)
2745  {
2746  RangeBound lower,
2747  upper;
2748  uint8 flags = MultirangeGetFlagsPtr(mr)[i];
2749  uint32 lower_hash;
2750  uint32 upper_hash;
2751  uint32 range_hash;
2752 
2753  multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
2754 
2755  if (RANGE_HAS_LBOUND(flags))
2756  lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
2757  typcache->rngtype->rng_collation,
2758  lower.val));
2759  else
2760  lower_hash = 0;
2761 
2762  if (RANGE_HAS_UBOUND(flags))
2763  upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
2764  typcache->rngtype->rng_collation,
2765  upper.val));
2766  else
2767  upper_hash = 0;
2768 
2769  /* Merge hashes of flags and bounds */
2770  range_hash = hash_uint32((uint32) flags);
2771  range_hash ^= lower_hash;
2772  range_hash = (range_hash << 1) | (range_hash >> 31);
2773  range_hash ^= upper_hash;
2774 
2775  /*
2776  * Use the same approach as hash_array to combine the individual
2777  * elements' hash values:
2778  */
2779  result = (result << 5) - result + range_hash;
2780  }
2781 
2782  PG_FREE_IF_COPY(mr, 0);
2783 
2784  PG_RETURN_UINT32(result);
2785 }
2786 
2787 /*
2788  * Returns 64-bit value by hashing a value to a 64-bit value, with a seed.
2789  * Otherwise, similar to hash_multirange.
2790  */
2791 Datum
2792 hash_multirange_extended(PG_FUNCTION_ARGS)
2793 {
2794  MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2795  Datum seed = PG_GETARG_DATUM(1);
2796  uint64 result = 1;
2797  TypeCacheEntry *typcache,
2798  *scache;
2799  int32 range_count,
2800  i;
2801 
2802  typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2803  scache = typcache->rngtype->rngelemtype;
2804  if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
2805  {
2806  scache = lookup_type_cache(scache->type_id,
2807  TYPECACHE_HASH_EXTENDED_PROC_FINFO);
2808  if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
2809  ereport(ERROR,
2810  (errcode(ERRCODE_UNDEFINED_FUNCTION),
2811  errmsg("could not identify a hash function for type %s",
2812  format_type_be(scache->type_id))));
2813  }
2814 
2815  range_count = mr->rangeCount;
2816  for (i = 0; i < range_count; i++)
2817  {
2818  RangeBound lower,
2819  upper;
2820  uint8 flags = MultirangeGetFlagsPtr(mr)[i];
2821  uint64 lower_hash;
2822  uint64 upper_hash;
2823  uint64 range_hash;
2824 
2825  multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
2826 
2827  if (RANGE_HAS_LBOUND(flags))
2828  lower_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
2829  typcache->rngtype->rng_collation,
2830  lower.val,
2831  seed));
2832  else
2833  lower_hash = 0;
2834 
2835  if (RANGE_HAS_UBOUND(flags))
2836  upper_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
2837  typcache->rngtype->rng_collation,
2838  upper.val,
2839  seed));
2840  else
2841  upper_hash = 0;
2842 
2843  /* Merge hashes of flags and bounds */
2844  range_hash = DatumGetUInt64(hash_uint32_extended((uint32) flags,
2845  DatumGetInt64(seed)));
2846  range_hash ^= lower_hash;
2847  range_hash = ROTATE_HIGH_AND_LOW_32BITS(range_hash);
2848  range_hash ^= upper_hash;
2849 
2850  /*
2851  * Use the same approach as hash_array to combine the individual
2852  * elements' hash values:
2853  */
2854  result = (result << 5) - result + range_hash;
2855  }
2856 
2857  PG_FREE_IF_COPY(mr, 0);
2858 
2859  PG_RETURN_UINT64(result);
2860 }
multirange_overright_multirange
Datum multirange_overright_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2150
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:1538
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:1656
multirange_lt
Datum multirange_lt(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2575
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:1364
multirange_upper_inc
Datum multirange_upper_inc(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1519
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:5083
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:2583
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:2324
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:2510
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:2201
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:2610
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:2114
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:1693
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:1465
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:2186
RangeTypePGetDatum
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:75
range_before_multirange
Datum range_before_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2263
RangeType::rangetypid
Oid rangetypid
Definition: rangetypes.h:28
multirange_gt
Datum multirange_gt(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2599
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:2173
multirange_upper_inf
Datum multirange_upper_inf(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1557
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:1871
multirange_overright_range
Datum multirange_overright_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2126
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:2008
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:2093
multirange_overlaps_multirange
Datum multirange_overlaps_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1895
range_adjacent_multirange
Datum range_adjacent_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2442
range_contains_multirange
Datum range_contains_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1668
DatumGetInt64
#define DatumGetInt64(X)
Definition: postgres.h:651
multirange_intersect
Datum multirange_intersect(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1223
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:1709
range_before_multirange_internal
bool range_before_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2337
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:1883
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:1442
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:2312
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:1764
multirange_ne_internal
bool multirange_ne_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:1849
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:1135
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:2792
range_contained_by_multirange
Datum range_contained_by_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1681
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:1105
multirange_ge
Datum multirange_ge(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2591
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:1050
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:1642
range_agg_transfn
Datum range_agg_transfn(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1333
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:1073
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:2300
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:1580
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:2647
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:1858
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:1736
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:2031
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:1799
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:1253
multirange_adjacent_multirange
Datum multirange_adjacent_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2469
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:1500
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:4495
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:2406
multirange_eq
Datum multirange_eq(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1836
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:2043
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:2068
deconstruct_array
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3491
accumArrayResult
ArrayBuildState * accumArrayResult(ArrayBuildState *astate, Datum dvalue, bool disnull, Oid element_type, MemoryContext rcontext)
Definition: arrayfuncs.c:5122
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:1609
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:1911
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:1491
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:1928
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:1398
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:1950
pq_getmsgend
void pq_getmsgend(StringInfo msg)
Definition: pqformat.c:637
multirange_adjacent_range
Datum multirange_adjacent_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2454
multirange_constructor1
Datum multirange_constructor1(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1014
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:2359
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:2275
range_after_multirange_internal
bool range_after_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2381
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:2287
hash_multirange
Datum hash_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2721
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:1593