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