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