Debian Codegraph @

src/backend/utils/adt/multirangetypes.c

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