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-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 */
49typedef 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
56typedef 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 *) ((char *) (mr) + \
72 sizeof(MultirangeType)))
73#define MultirangeGetFlagsPtr(mr) ((uint8 *) ((char *) (mr) + \
74 sizeof(MultirangeType) + ((mr)->rangeCount - 1) * sizeof(uint32)))
75#define MultirangeGetBoundariesPtr(mr, align) ((char *) (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
85typedef int (*multirange_bsearch_comparison) (TypeCacheEntry *typcache,
86 RangeBound *lower,
87 RangeBound *upper,
88 void *key,
89 bool *match);
90
91static MultirangeIOData *get_multirange_io_data(FunctionCallInfo fcinfo,
92 Oid mltrngtypid,
93 IOFuncSelector func);
94static 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 */
116Datum
117multirange_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
298Datum
299multirange_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 */
336Datum
337multirange_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
376Datum
377multirange_send(PG_FUNCTION_ARGS)
378{
379 MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0);
380 Oid mltrngtypoid = MultirangeTypeGetOid(multirange);
381 StringInfoData buf;
382 RangeType **ranges;
383 int32 range_count;
384 MultirangeIOData *cache;
385
386 initStringInfo(&buf);
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 bytea *outputbytes;
399
400 range = RangeTypePGetDatum(ranges[i]);
401 outputbytes = SendFunctionCall(&cache->typioproc, range);
402
403 pq_sendint32(&buf, VARSIZE(outputbytes) - VARHDRSZ);
404 pq_sendbytes(&buf, VARDATA(outputbytes), VARSIZE(outputbytes) - VARHDRSZ);
405 }
406
407 PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
408}
409
410/*
411 * get_multirange_io_data: get cached information needed for multirange type I/O
412 *
413 * The multirange I/O functions need a bit more cached info than other multirange
414 * functions, so they store a MultirangeIOData struct in fn_extra, not just a
415 * pointer to a type cache entry.
416 */
417static MultirangeIOData *
418get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func)
419{
420 MultirangeIOData *cache = (MultirangeIOData *) fcinfo->flinfo->fn_extra;
421
422 if (cache == NULL || cache->typcache->type_id != mltrngtypid)
423 {
424 Oid typiofunc;
425 int16 typlen;
426 bool typbyval;
427 char typalign;
428 char typdelim;
429
430 cache = (MultirangeIOData *) MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
431 sizeof(MultirangeIOData));
432 cache->typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO);
433 if (cache->typcache->rngtype == NULL)
434 elog(ERROR, "type %u is not a multirange type", mltrngtypid);
435
436 /* get_type_io_data does more than we need, but is convenient */
437 get_type_io_data(cache->typcache->rngtype->type_id,
438 func,
439 &typlen,
440 &typbyval,
441 &typalign,
442 &typdelim,
443 &cache->typioparam,
444 &typiofunc);
445
446 if (!OidIsValid(typiofunc))
447 {
448 /* this could only happen for receive or send */
449 if (func == IOFunc_receive)
450 ereport(ERROR,
451 (errcode(ERRCODE_UNDEFINED_FUNCTION),
452 errmsg("no binary input function available for type %s",
453 format_type_be(cache->typcache->rngtype->type_id))));
454 else
455 ereport(ERROR,
456 (errcode(ERRCODE_UNDEFINED_FUNCTION),
457 errmsg("no binary output function available for type %s",
458 format_type_be(cache->typcache->rngtype->type_id))));
459 }
460 fmgr_info_cxt(typiofunc, &cache->typioproc,
461 fcinfo->flinfo->fn_mcxt);
462
463 fcinfo->flinfo->fn_extra = cache;
464 }
465
466 return cache;
467}
468
469/*
470 * Converts a list of arbitrary ranges into a list that is sorted and merged.
471 * Changes the contents of `ranges`.
472 *
473 * Returns the number of slots actually used, which may be less than
474 * input_range_count but never more.
475 *
476 * We assume that no input ranges are null, but empties are okay.
477 */
478static int32
479multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count,
480 RangeType **ranges)
481{
482 RangeType *lastRange = NULL;
483 RangeType *currentRange;
484 int32 i;
485 int32 output_range_count = 0;
486
487 /* Sort the ranges so we can find the ones that overlap/meet. */
488 qsort_arg(ranges, input_range_count, sizeof(RangeType *), range_compare,
489 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 */
549TypeCacheEntry *
550multirange_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 */
570static Size
571multirange_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 */
597static void
598write_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 const char *begin;
606 char *ptr;
607 char elemalign = rangetyp->rngelemtype->typalign;
608
609 items = MultirangeGetItemsPtr(multirange);
610 flags = MultirangeGetFlagsPtr(multirange);
611 begin = ptr = 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] = *((char *) ranges[i] + VARSIZE(ranges[i]) - sizeof(char));
631 len = VARSIZE(ranges[i]) - sizeof(RangeType) - sizeof(char);
632 memcpy(ptr, 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 */
647MultirangeType *
648make_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 */
674static uint32
675multirange_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 */
696RangeType *
697multirange_get_range(TypeCacheEntry *rangetyp,
698 const MultirangeType *multirange, int i)
699{
700 uint32 offset;
701 uint8 flags;
702 const char *begin;
703 char *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 begin = ptr = 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 = (char *) att_addlength_pointer(ptr, typlen, ptr);
723 if (RANGE_HAS_UBOUND(flags))
724 {
725 ptr = (char *) att_align_pointer(ptr, typalign, typlen, ptr);
726 ptr = (char *) 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 */
745void
746multirange_get_bounds(TypeCacheEntry *rangetyp,
747 const MultirangeType *multirange,
748 uint32 i, RangeBound *lower, RangeBound *upper)
749{
750 uint32 offset;
751 uint8 flags;
752 const char *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 = (char *) 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 = (char *) 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 */
803RangeType *
804multirange_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 */
827void
828multirange_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(*range_count * sizeof(RangeType *));
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
849MultirangeType *
850make_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 */
859static bool
860range_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 */
879static bool
880range_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 */
899static bool
900multirange_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 */
942Datum
943multirange_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 = palloc0(range_count * sizeof(RangeType *));
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 */
1024Datum
1025multirange_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 */
1060Datum
1061multirange_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 */
1083Datum
1084multirange_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 */
1115Datum
1116multirange_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
1145MultirangeType *
1146multirange_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/*
1231 * multirange_minus_multi - like multirange_minus but returning the result as a
1232 * SRF, with no rows if the result would be empty.
1233 */
1234Datum
1235multirange_minus_multi(PG_FUNCTION_ARGS)
1236{
1237 FuncCallContext *funcctx;
1238 MemoryContext oldcontext;
1239
1240 if (!SRF_IS_FIRSTCALL())
1241 {
1242 /* We never have more than one result */
1243 funcctx = SRF_PERCALL_SETUP();
1244 SRF_RETURN_DONE(funcctx);
1245 }
1246 else
1247 {
1248 MultirangeType *mr1;
1249 MultirangeType *mr2;
1250 Oid mltrngtypoid;
1251 TypeCacheEntry *typcache;
1252 TypeCacheEntry *rangetyp;
1253 int32 range_count1;
1254 int32 range_count2;
1255 RangeType **ranges1;
1256 RangeType **ranges2;
1257 MultirangeType *mr;
1258
1259 funcctx = SRF_FIRSTCALL_INIT();
1260
1261 /*
1262 * switch to memory context appropriate for multiple function calls
1263 */
1264 oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
1265
1266 /* get args, detoasting into multi-call memory context */
1267 mr1 = PG_GETARG_MULTIRANGE_P(0);
1268 mr2 = PG_GETARG_MULTIRANGE_P(1);
1269
1270 mltrngtypoid = MultirangeTypeGetOid(mr1);
1271 typcache = lookup_type_cache(mltrngtypoid, TYPECACHE_MULTIRANGE_INFO);
1272 if (typcache->rngtype == NULL)
1273 elog(ERROR, "type %u is not a multirange type", mltrngtypoid);
1274 rangetyp = typcache->rngtype;
1275
1276 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
1277 mr = mr1;
1278 else
1279 {
1280 multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1);
1281 multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2);
1282
1283 mr = multirange_minus_internal(mltrngtypoid,
1284 rangetyp,
1285 range_count1,
1286 ranges1,
1287 range_count2,
1288 ranges2);
1289 }
1290
1291 MemoryContextSwitchTo(oldcontext);
1292
1293 funcctx = SRF_PERCALL_SETUP();
1294 if (MultirangeIsEmpty(mr))
1295 SRF_RETURN_DONE(funcctx);
1296 else
1297 SRF_RETURN_NEXT(funcctx, MultirangeTypePGetDatum(mr));
1298 }
1299}
1300
1301/* multirange intersection */
1302Datum
1303multirange_intersect(PG_FUNCTION_ARGS)
1304{
1305 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1306 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1307 Oid mltrngtypoid = MultirangeTypeGetOid(mr1);
1308 TypeCacheEntry *typcache;
1309 TypeCacheEntry *rangetyp;
1310 int32 range_count1;
1311 int32 range_count2;
1312 RangeType **ranges1;
1313 RangeType **ranges2;
1314
1315 typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1316 rangetyp = typcache->rngtype;
1317
1318 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
1319 PG_RETURN_MULTIRANGE_P(make_empty_multirange(mltrngtypoid, rangetyp));
1320
1321 multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1);
1322 multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2);
1323
1324 PG_RETURN_MULTIRANGE_P(multirange_intersect_internal(mltrngtypoid,
1325 rangetyp,
1326 range_count1,
1327 ranges1,
1328 range_count2,
1329 ranges2));
1330}
1331
1332MultirangeType *
1333multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
1334 int32 range_count1, RangeType **ranges1,
1335 int32 range_count2, RangeType **ranges2)
1336{
1337 RangeType *r1;
1338 RangeType *r2;
1339 RangeType **ranges3;
1340 int32 range_count3;
1341 int32 i1;
1342 int32 i2;
1343
1344 if (range_count1 == 0 || range_count2 == 0)
1345 return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
1346
1347 /*-----------------------------------------------
1348 * Worst case is a stitching pattern like this:
1349 *
1350 * mr1: --- --- --- ---
1351 * mr2: --- --- ---
1352 * mr3: - - - - - -
1353 *
1354 * That seems to be range_count1 + range_count2 - 1,
1355 * but one extra won't hurt.
1356 *-----------------------------------------------
1357 */
1358 ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
1359 range_count3 = 0;
1360
1361 /*
1362 * For each range in mr1, keep intersecting until the ranges in mr2 have
1363 * passed it. The parallel progress through mr1 and mr2 is similar to
1364 * multirange_minus_multirange_internal, but we don't have to assign back
1365 * to r1.
1366 */
1367 r2 = ranges2[0];
1368 for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
1369 {
1370 r1 = ranges1[i1];
1371
1372 /* Discard r2s while r2 << r1 */
1373 while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
1374 {
1375 r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1376 }
1377
1378 while (r2 != NULL)
1379 {
1380 if (range_overlaps_internal(rangetyp, r1, r2))
1381 {
1382 /* Keep the overlapping part */
1383 ranges3[range_count3++] = range_intersect_internal(rangetyp, r1, r2);
1384
1385 /* If we "used up" all of r2, go to the next one... */
1386 if (range_overleft_internal(rangetyp, r2, r1))
1387 r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
1388
1389 /* ...otherwise go to the next r1 */
1390 else
1391 break;
1392 }
1393 else
1394 /* We're past r1, so move to the next one */
1395 break;
1396 }
1397
1398 /* If we're out of r2s, there can be no more intersections */
1399 if (r2 == NULL)
1400 break;
1401 }
1402
1403 return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
1404}
1405
1406/*
1407 * range_agg_transfn: combine adjacent/overlapping ranges.
1408 *
1409 * All we do here is gather the input ranges into an array
1410 * so that the finalfn can sort and combine them.
1411 */
1412Datum
1413range_agg_transfn(PG_FUNCTION_ARGS)
1414{
1415 MemoryContext aggContext;
1416 Oid rngtypoid;
1417 ArrayBuildState *state;
1418
1419 if (!AggCheckCallContext(fcinfo, &aggContext))
1420 elog(ERROR, "range_agg_transfn called in non-aggregate context");
1421
1422 rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
1423 if (!type_is_range(rngtypoid))
1424 elog(ERROR, "range_agg must be called with a range");
1425
1426 if (PG_ARGISNULL(0))
1427 state = initArrayResult(rngtypoid, aggContext, false);
1428 else
1429 state = (ArrayBuildState *) PG_GETARG_POINTER(0);
1430
1431 /* skip NULLs */
1432 if (!PG_ARGISNULL(1))
1433 accumArrayResult(state, PG_GETARG_DATUM(1), false, rngtypoid, aggContext);
1434
1435 PG_RETURN_POINTER(state);
1436}
1437
1438/*
1439 * range_agg_finalfn: use our internal array to merge touching ranges.
1440 *
1441 * Shared by range_agg_finalfn(anyrange) and
1442 * multirange_agg_finalfn(anymultirange).
1443 */
1444Datum
1445range_agg_finalfn(PG_FUNCTION_ARGS)
1446{
1447 MemoryContext aggContext;
1448 Oid mltrngtypoid;
1449 TypeCacheEntry *typcache;
1450 ArrayBuildState *state;
1451 int32 range_count;
1452 RangeType **ranges;
1453 int i;
1454
1455 if (!AggCheckCallContext(fcinfo, &aggContext))
1456 elog(ERROR, "range_agg_finalfn called in non-aggregate context");
1457
1458 state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
1459 if (state == NULL)
1460 /* This shouldn't be possible, but just in case.... */
1461 PG_RETURN_NULL();
1462
1463 /* Also return NULL if we had zero inputs, like other aggregates */
1464 range_count = state->nelems;
1465 if (range_count == 0)
1466 PG_RETURN_NULL();
1467
1468 mltrngtypoid = get_fn_expr_rettype(fcinfo->flinfo);
1469 typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1470
1471 ranges = palloc0(range_count * sizeof(RangeType *));
1472 for (i = 0; i < range_count; i++)
1473 ranges[i] = DatumGetRangeTypeP(state->dvalues[i]);
1474
1475 PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypoid, typcache->rngtype, range_count, ranges));
1476}
1477
1478/*
1479 * multirange_agg_transfn: combine adjacent/overlapping multiranges.
1480 *
1481 * All we do here is gather the input multiranges' ranges into an array so
1482 * that the finalfn can sort and combine them.
1483 */
1484Datum
1485multirange_agg_transfn(PG_FUNCTION_ARGS)
1486{
1487 MemoryContext aggContext;
1488 Oid mltrngtypoid;
1489 TypeCacheEntry *typcache;
1490 TypeCacheEntry *rngtypcache;
1491 ArrayBuildState *state;
1492
1493 if (!AggCheckCallContext(fcinfo, &aggContext))
1494 elog(ERROR, "multirange_agg_transfn called in non-aggregate context");
1495
1496 mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
1497 if (!type_is_multirange(mltrngtypoid))
1498 elog(ERROR, "range_agg must be called with a multirange");
1499
1500 typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1501 rngtypcache = typcache->rngtype;
1502
1503 if (PG_ARGISNULL(0))
1504 state = initArrayResult(rngtypcache->type_id, aggContext, false);
1505 else
1506 state = (ArrayBuildState *) PG_GETARG_POINTER(0);
1507
1508 /* skip NULLs */
1509 if (!PG_ARGISNULL(1))
1510 {
1511 MultirangeType *current;
1512 int32 range_count;
1513 RangeType **ranges;
1514
1515 current = PG_GETARG_MULTIRANGE_P(1);
1516 multirange_deserialize(rngtypcache, current, &range_count, &ranges);
1517 if (range_count == 0)
1518 {
1519 /*
1520 * Add an empty range so we get an empty result (not a null
1521 * result).
1522 */
1523 accumArrayResult(state,
1524 RangeTypePGetDatum(make_empty_range(rngtypcache)),
1525 false, rngtypcache->type_id, aggContext);
1526 }
1527 else
1528 {
1529 for (int32 i = 0; i < range_count; i++)
1530 accumArrayResult(state, RangeTypePGetDatum(ranges[i]), false, rngtypcache->type_id, aggContext);
1531 }
1532 }
1533
1534 PG_RETURN_POINTER(state);
1535}
1536
1537Datum
1538multirange_intersect_agg_transfn(PG_FUNCTION_ARGS)
1539{
1540 MemoryContext aggContext;
1541 Oid mltrngtypoid;
1542 TypeCacheEntry *typcache;
1543 MultirangeType *result;
1544 MultirangeType *current;
1545 int32 range_count1;
1546 int32 range_count2;
1547 RangeType **ranges1;
1548 RangeType **ranges2;
1549
1550 if (!AggCheckCallContext(fcinfo, &aggContext))
1551 elog(ERROR, "multirange_intersect_agg_transfn called in non-aggregate context");
1552
1553 mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
1554 if (!type_is_multirange(mltrngtypoid))
1555 elog(ERROR, "range_intersect_agg must be called with a multirange");
1556
1557 typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
1558
1559 /* strictness ensures these are non-null */
1560 result = PG_GETARG_MULTIRANGE_P(0);
1561 current = PG_GETARG_MULTIRANGE_P(1);
1562
1563 multirange_deserialize(typcache->rngtype, result, &range_count1, &ranges1);
1564 multirange_deserialize(typcache->rngtype, current, &range_count2, &ranges2);
1565
1566 result = multirange_intersect_internal(mltrngtypoid,
1567 typcache->rngtype,
1568 range_count1,
1569 ranges1,
1570 range_count2,
1571 ranges2);
1572 PG_RETURN_MULTIRANGE_P(result);
1573}
1574
1575
1576/* multirange -> element type functions */
1577
1578/* extract lower bound value */
1579Datum
1580multirange_lower(PG_FUNCTION_ARGS)
1581{
1582 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1583 TypeCacheEntry *typcache;
1584 RangeBound lower;
1585 RangeBound upper;
1586
1587 if (MultirangeIsEmpty(mr))
1588 PG_RETURN_NULL();
1589
1590 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1591
1592 multirange_get_bounds(typcache->rngtype, mr, 0,
1593 &lower, &upper);
1594
1595 if (!lower.infinite)
1596 PG_RETURN_DATUM(lower.val);
1597 else
1598 PG_RETURN_NULL();
1599}
1600
1601/* extract upper bound value */
1602Datum
1603multirange_upper(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_NULL();
1612
1613 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1614
1615 multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1616 &lower, &upper);
1617
1618 if (!upper.infinite)
1619 PG_RETURN_DATUM(upper.val);
1620 else
1621 PG_RETURN_NULL();
1622}
1623
1624
1625/* multirange -> bool functions */
1626
1627/* is multirange empty? */
1628Datum
1629multirange_empty(PG_FUNCTION_ARGS)
1630{
1631 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1632
1633 PG_RETURN_BOOL(MultirangeIsEmpty(mr));
1634}
1635
1636/* is lower bound inclusive? */
1637Datum
1638multirange_lower_inc(PG_FUNCTION_ARGS)
1639{
1640 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1641 TypeCacheEntry *typcache;
1642 RangeBound lower;
1643 RangeBound upper;
1644
1645 if (MultirangeIsEmpty(mr))
1646 PG_RETURN_BOOL(false);
1647
1648 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1649 multirange_get_bounds(typcache->rngtype, mr, 0,
1650 &lower, &upper);
1651
1652 PG_RETURN_BOOL(lower.inclusive);
1653}
1654
1655/* is upper bound inclusive? */
1656Datum
1657multirange_upper_inc(PG_FUNCTION_ARGS)
1658{
1659 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1660 TypeCacheEntry *typcache;
1661 RangeBound lower;
1662 RangeBound upper;
1663
1664 if (MultirangeIsEmpty(mr))
1665 PG_RETURN_BOOL(false);
1666
1667 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1668 multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1669 &lower, &upper);
1670
1671 PG_RETURN_BOOL(upper.inclusive);
1672}
1673
1674/* is lower bound infinite? */
1675Datum
1676multirange_lower_inf(PG_FUNCTION_ARGS)
1677{
1678 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1679 TypeCacheEntry *typcache;
1680 RangeBound lower;
1681 RangeBound upper;
1682
1683 if (MultirangeIsEmpty(mr))
1684 PG_RETURN_BOOL(false);
1685
1686 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1687 multirange_get_bounds(typcache->rngtype, mr, 0,
1688 &lower, &upper);
1689
1690 PG_RETURN_BOOL(lower.infinite);
1691}
1692
1693/* is upper bound infinite? */
1694Datum
1695multirange_upper_inf(PG_FUNCTION_ARGS)
1696{
1697 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1698 TypeCacheEntry *typcache;
1699 RangeBound lower;
1700 RangeBound upper;
1701
1702 if (MultirangeIsEmpty(mr))
1703 PG_RETURN_BOOL(false);
1704
1705 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1706 multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
1707 &lower, &upper);
1708
1709 PG_RETURN_BOOL(upper.infinite);
1710}
1711
1712
1713
1714/* multirange, element -> bool functions */
1715
1716/* contains? */
1717Datum
1718multirange_contains_elem(PG_FUNCTION_ARGS)
1719{
1720 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1721 Datum val = PG_GETARG_DATUM(1);
1722 TypeCacheEntry *typcache;
1723
1724 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1725
1726 PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
1727}
1728
1729/* contained by? */
1730Datum
1731elem_contained_by_multirange(PG_FUNCTION_ARGS)
1732{
1733 Datum val = PG_GETARG_DATUM(0);
1734 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1735 TypeCacheEntry *typcache;
1736
1737 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1738
1739 PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val));
1740}
1741
1742/*
1743 * Comparison function for checking if any range of multirange contains given
1744 * key element using binary search.
1745 */
1746static int
1747multirange_elem_bsearch_comparison(TypeCacheEntry *typcache,
1748 RangeBound *lower, RangeBound *upper,
1749 void *key, bool *match)
1750{
1751 Datum val = *((Datum *) key);
1752 int cmp;
1753
1754 if (!lower->infinite)
1755 {
1756 cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1757 typcache->rng_collation,
1758 lower->val, val));
1759 if (cmp > 0 || (cmp == 0 && !lower->inclusive))
1760 return -1;
1761 }
1762
1763 if (!upper->infinite)
1764 {
1765 cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1766 typcache->rng_collation,
1767 upper->val, val));
1768 if (cmp < 0 || (cmp == 0 && !upper->inclusive))
1769 return 1;
1770 }
1771
1772 *match = true;
1773 return 0;
1774}
1775
1776/*
1777 * Test whether multirange mr contains a specific element value.
1778 */
1779bool
1780multirange_contains_elem_internal(TypeCacheEntry *rangetyp,
1781 const MultirangeType *mr, Datum val)
1782{
1783 if (MultirangeIsEmpty(mr))
1784 return false;
1785
1786 return multirange_bsearch_match(rangetyp, mr, &val,
1787 multirange_elem_bsearch_comparison);
1788}
1789
1790/* multirange, range -> bool functions */
1791
1792/* contains? */
1793Datum
1794multirange_contains_range(PG_FUNCTION_ARGS)
1795{
1796 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1797 RangeType *r = PG_GETARG_RANGE_P(1);
1798 TypeCacheEntry *typcache;
1799
1800 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1801
1802 PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
1803}
1804
1805Datum
1806range_contains_multirange(PG_FUNCTION_ARGS)
1807{
1808 RangeType *r = PG_GETARG_RANGE_P(0);
1809 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1810 TypeCacheEntry *typcache;
1811
1812 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1813
1814 PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
1815}
1816
1817/* contained by? */
1818Datum
1819range_contained_by_multirange(PG_FUNCTION_ARGS)
1820{
1821 RangeType *r = PG_GETARG_RANGE_P(0);
1822 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
1823 TypeCacheEntry *typcache;
1824
1825 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1826
1827 PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r));
1828}
1829
1830Datum
1831multirange_contained_by_range(PG_FUNCTION_ARGS)
1832{
1833 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
1834 RangeType *r = PG_GETARG_RANGE_P(1);
1835 TypeCacheEntry *typcache;
1836
1837 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
1838
1839 PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr));
1840}
1841
1842/*
1843 * Comparison function for checking if any range of multirange contains given
1844 * key range using binary search.
1845 */
1846static int
1847multirange_range_contains_bsearch_comparison(TypeCacheEntry *typcache,
1848 RangeBound *lower, RangeBound *upper,
1849 void *key, bool *match)
1850{
1851 RangeBound *keyLower = (RangeBound *) key;
1852 RangeBound *keyUpper = (RangeBound *) key + 1;
1853
1854 /* Check if key range is strictly in the left or in the right */
1855 if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
1856 return -1;
1857 if (range_cmp_bounds(typcache, keyLower, upper) > 0)
1858 return 1;
1859
1860 /*
1861 * At this point we found overlapping range. But we have to check if it
1862 * really contains the key range. Anyway, we have to stop our search
1863 * here, because multirange contains only non-overlapping ranges.
1864 */
1865 *match = range_bounds_contains(typcache, lower, upper, keyLower, keyUpper);
1866
1867 return 0;
1868}
1869
1870/*
1871 * Test whether multirange mr contains a specific range r.
1872 */
1873bool
1874multirange_contains_range_internal(TypeCacheEntry *rangetyp,
1875 const MultirangeType *mr,
1876 const RangeType *r)
1877{
1878 RangeBound bounds[2];
1879 bool empty;
1880
1881 /*
1882 * Every multirange contains an infinite number of empty ranges, even an
1883 * empty one.
1884 */
1885 if (RangeIsEmpty(r))
1886 return true;
1887
1888 if (MultirangeIsEmpty(mr))
1889 return false;
1890
1891 range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
1892 Assert(!empty);
1893
1894 return multirange_bsearch_match(rangetyp, mr, bounds,
1895 multirange_range_contains_bsearch_comparison);
1896}
1897
1898/*
1899 * Test whether range r contains a multirange mr.
1900 */
1901bool
1902range_contains_multirange_internal(TypeCacheEntry *rangetyp,
1903 const RangeType *r,
1904 const MultirangeType *mr)
1905{
1906 RangeBound lower1,
1907 upper1,
1908 lower2,
1909 upper2,
1910 tmp;
1911 bool empty;
1912
1913 /*
1914 * Every range contains an infinite number of empty multiranges, even an
1915 * empty one.
1916 */
1917 if (MultirangeIsEmpty(mr))
1918 return true;
1919
1920 if (RangeIsEmpty(r))
1921 return false;
1922
1923 /* Range contains multirange iff it contains its union range. */
1924 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
1925 Assert(!empty);
1926 multirange_get_bounds(rangetyp, mr, 0, &lower2, &tmp);
1927 multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper2);
1928
1929 return range_bounds_contains(rangetyp, &lower1, &upper1, &lower2, &upper2);
1930}
1931
1932
1933/* multirange, multirange -> bool functions */
1934
1935/* equality (internal version) */
1936bool
1937multirange_eq_internal(TypeCacheEntry *rangetyp,
1938 const MultirangeType *mr1,
1939 const MultirangeType *mr2)
1940{
1941 int32 range_count_1;
1942 int32 range_count_2;
1943 int32 i;
1944 RangeBound lower1,
1945 upper1,
1946 lower2,
1947 upper2;
1948
1949 /* Different types should be prevented by ANYMULTIRANGE matching rules */
1950 if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
1951 elog(ERROR, "multirange types do not match");
1952
1953 range_count_1 = mr1->rangeCount;
1954 range_count_2 = mr2->rangeCount;
1955
1956 if (range_count_1 != range_count_2)
1957 return false;
1958
1959 for (i = 0; i < range_count_1; i++)
1960 {
1961 multirange_get_bounds(rangetyp, mr1, i, &lower1, &upper1);
1962 multirange_get_bounds(rangetyp, mr2, i, &lower2, &upper2);
1963
1964 if (range_cmp_bounds(rangetyp, &lower1, &lower2) != 0 ||
1965 range_cmp_bounds(rangetyp, &upper1, &upper2) != 0)
1966 return false;
1967 }
1968
1969 return true;
1970}
1971
1972/* equality */
1973Datum
1974multirange_eq(PG_FUNCTION_ARGS)
1975{
1976 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1977 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
1978 TypeCacheEntry *typcache;
1979
1980 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
1981
1982 PG_RETURN_BOOL(multirange_eq_internal(typcache->rngtype, mr1, mr2));
1983}
1984
1985/* inequality (internal version) */
1986bool
1987multirange_ne_internal(TypeCacheEntry *rangetyp,
1988 const MultirangeType *mr1,
1989 const MultirangeType *mr2)
1990{
1991 return (!multirange_eq_internal(rangetyp, mr1, mr2));
1992}
1993
1994/* inequality */
1995Datum
1996multirange_ne(PG_FUNCTION_ARGS)
1997{
1998 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
1999 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2000 TypeCacheEntry *typcache;
2001
2002 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2003
2004 PG_RETURN_BOOL(multirange_ne_internal(typcache->rngtype, mr1, mr2));
2005}
2006
2007/* overlaps? */
2008Datum
2009range_overlaps_multirange(PG_FUNCTION_ARGS)
2010{
2011 RangeType *r = PG_GETARG_RANGE_P(0);
2012 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2013 TypeCacheEntry *typcache;
2014
2015 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2016
2017 PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
2018}
2019
2020Datum
2021multirange_overlaps_range(PG_FUNCTION_ARGS)
2022{
2023 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2024 RangeType *r = PG_GETARG_RANGE_P(1);
2025 TypeCacheEntry *typcache;
2026
2027 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2028
2029 PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr));
2030}
2031
2032Datum
2033multirange_overlaps_multirange(PG_FUNCTION_ARGS)
2034{
2035 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2036 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2037 TypeCacheEntry *typcache;
2038
2039 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2040
2041 PG_RETURN_BOOL(multirange_overlaps_multirange_internal(typcache->rngtype, mr1, mr2));
2042}
2043
2044/*
2045 * Comparison function for checking if any range of multirange overlaps given
2046 * key range using binary search.
2047 */
2048static int
2049multirange_range_overlaps_bsearch_comparison(TypeCacheEntry *typcache,
2050 RangeBound *lower, RangeBound *upper,
2051 void *key, bool *match)
2052{
2053 RangeBound *keyLower = (RangeBound *) key;
2054 RangeBound *keyUpper = (RangeBound *) key + 1;
2055
2056 if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
2057 return -1;
2058 if (range_cmp_bounds(typcache, keyLower, upper) > 0)
2059 return 1;
2060
2061 *match = true;
2062 return 0;
2063}
2064
2065bool
2066range_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
2067 const RangeType *r,
2068 const MultirangeType *mr)
2069{
2070 RangeBound bounds[2];
2071 bool empty;
2072
2073 /*
2074 * Empties never overlap, even with empties. (This seems strange since
2075 * they *do* contain each other, but we want to follow how ranges work.)
2076 */
2077 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2078 return false;
2079
2080 range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
2081 Assert(!empty);
2082
2083 return multirange_bsearch_match(rangetyp, mr, bounds,
2084 multirange_range_overlaps_bsearch_comparison);
2085}
2086
2087bool
2088multirange_overlaps_multirange_internal(TypeCacheEntry *rangetyp,
2089 const MultirangeType *mr1,
2090 const MultirangeType *mr2)
2091{
2092 int32 range_count1;
2093 int32 range_count2;
2094 int32 i1;
2095 int32 i2;
2096 RangeBound lower1,
2097 upper1,
2098 lower2,
2099 upper2;
2100
2101 /*
2102 * Empties never overlap, even with empties. (This seems strange since
2103 * they *do* contain each other, but we want to follow how ranges work.)
2104 */
2105 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2106 return false;
2107
2108 range_count1 = mr1->rangeCount;
2109 range_count2 = mr2->rangeCount;
2110
2111 /*
2112 * Every range in mr1 gets a chance to overlap with the ranges in mr2, but
2113 * we can use their ordering to avoid O(n^2). This is similar to
2114 * range_overlaps_multirange where r1 : r2 :: mrr : r, but there if we
2115 * don't find an overlap with r we're done, and here if we don't find an
2116 * overlap with r2 we try the next r2.
2117 */
2118 i1 = 0;
2119 multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2120 for (i1 = 0, i2 = 0; i2 < range_count2; i2++)
2121 {
2122 multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
2123
2124 /* Discard r1s while r1 << r2 */
2125 while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
2126 {
2127 if (++i1 >= range_count1)
2128 return false;
2129 multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2130 }
2131
2132 /*
2133 * If r1 && r2, we're done, otherwise we failed to find an overlap for
2134 * r2, so go to the next one.
2135 */
2136 if (range_bounds_overlaps(rangetyp, &lower1, &upper1, &lower2, &upper2))
2137 return true;
2138 }
2139
2140 /* We looked through all of mr2 without finding an overlap */
2141 return false;
2142}
2143
2144/* does not extend to right of? */
2145bool
2146range_overleft_multirange_internal(TypeCacheEntry *rangetyp,
2147 const RangeType *r,
2148 const MultirangeType *mr)
2149{
2150 RangeBound lower1,
2151 upper1,
2152 lower2,
2153 upper2;
2154 bool empty;
2155
2156 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2157 return false;
2158
2159 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2160 Assert(!empty);
2161 multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1,
2162 &lower2, &upper2);
2163
2164 return (range_cmp_bounds(rangetyp, &upper1, &upper2) <= 0);
2165}
2166
2167Datum
2168range_overleft_multirange(PG_FUNCTION_ARGS)
2169{
2170 RangeType *r = PG_GETARG_RANGE_P(0);
2171 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2172 TypeCacheEntry *typcache;
2173
2174 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2175
2176 PG_RETURN_BOOL(range_overleft_multirange_internal(typcache->rngtype, r, mr));
2177}
2178
2179Datum
2180multirange_overleft_range(PG_FUNCTION_ARGS)
2181{
2182 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2183 RangeType *r = PG_GETARG_RANGE_P(1);
2184 TypeCacheEntry *typcache;
2185 RangeBound lower1,
2186 upper1,
2187 lower2,
2188 upper2;
2189 bool empty;
2190
2191 if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
2192 PG_RETURN_BOOL(false);
2193
2194 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2195
2196 multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
2197 &lower1, &upper1);
2198 range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
2199 Assert(!empty);
2200
2201 PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
2202}
2203
2204Datum
2205multirange_overleft_multirange(PG_FUNCTION_ARGS)
2206{
2207 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2208 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2209 TypeCacheEntry *typcache;
2210 RangeBound lower1,
2211 upper1,
2212 lower2,
2213 upper2;
2214
2215 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2216 PG_RETURN_BOOL(false);
2217
2218 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2219
2220 multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1,
2221 &lower1, &upper1);
2222 multirange_get_bounds(typcache->rngtype, mr2, mr2->rangeCount - 1,
2223 &lower2, &upper2);
2224
2225 PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
2226}
2227
2228/* does not extend to left of? */
2229bool
2230range_overright_multirange_internal(TypeCacheEntry *rangetyp,
2231 const RangeType *r,
2232 const MultirangeType *mr)
2233{
2234 RangeBound lower1,
2235 upper1,
2236 lower2,
2237 upper2;
2238 bool empty;
2239
2240 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2241 return false;
2242
2243 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2244 Assert(!empty);
2245 multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
2246
2247 return (range_cmp_bounds(rangetyp, &lower1, &lower2) >= 0);
2248}
2249
2250Datum
2251range_overright_multirange(PG_FUNCTION_ARGS)
2252{
2253 RangeType *r = PG_GETARG_RANGE_P(0);
2254 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2255 TypeCacheEntry *typcache;
2256
2257 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2258
2259 PG_RETURN_BOOL(range_overright_multirange_internal(typcache->rngtype, r, mr));
2260}
2261
2262Datum
2263multirange_overright_range(PG_FUNCTION_ARGS)
2264{
2265 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2266 RangeType *r = PG_GETARG_RANGE_P(1);
2267 TypeCacheEntry *typcache;
2268 RangeBound lower1,
2269 upper1,
2270 lower2,
2271 upper2;
2272 bool empty;
2273
2274 if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
2275 PG_RETURN_BOOL(false);
2276
2277 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2278
2279 multirange_get_bounds(typcache->rngtype, mr, 0, &lower1, &upper1);
2280 range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
2281 Assert(!empty);
2282
2283 PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
2284}
2285
2286Datum
2287multirange_overright_multirange(PG_FUNCTION_ARGS)
2288{
2289 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2290 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2291 TypeCacheEntry *typcache;
2292 RangeBound lower1,
2293 upper1,
2294 lower2,
2295 upper2;
2296
2297 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2298 PG_RETURN_BOOL(false);
2299
2300 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2301
2302 multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1);
2303 multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2);
2304
2305 PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
2306}
2307
2308/* contains? */
2309Datum
2310multirange_contains_multirange(PG_FUNCTION_ARGS)
2311{
2312 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2313 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2314 TypeCacheEntry *typcache;
2315
2316 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2317
2318 PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr1, mr2));
2319}
2320
2321/* contained by? */
2322Datum
2323multirange_contained_by_multirange(PG_FUNCTION_ARGS)
2324{
2325 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2326 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2327 TypeCacheEntry *typcache;
2328
2329 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2330
2331 PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr2, mr1));
2332}
2333
2334/*
2335 * Test whether multirange mr1 contains every range from another multirange mr2.
2336 */
2337bool
2338multirange_contains_multirange_internal(TypeCacheEntry *rangetyp,
2339 const MultirangeType *mr1,
2340 const MultirangeType *mr2)
2341{
2342 int32 range_count1 = mr1->rangeCount;
2343 int32 range_count2 = mr2->rangeCount;
2344 int i1,
2345 i2;
2346 RangeBound lower1,
2347 upper1,
2348 lower2,
2349 upper2;
2350
2351 /*
2352 * We follow the same logic for empties as ranges: - an empty multirange
2353 * contains an empty range/multirange. - an empty multirange can't contain
2354 * any other range/multirange. - an empty multirange is contained by any
2355 * other range/multirange.
2356 */
2357
2358 if (range_count2 == 0)
2359 return true;
2360 if (range_count1 == 0)
2361 return false;
2362
2363 /*
2364 * Every range in mr2 must be contained by some range in mr1. To avoid
2365 * O(n^2) we walk through both ranges in tandem.
2366 */
2367 i1 = 0;
2368 multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2369 for (i2 = 0; i2 < range_count2; i2++)
2370 {
2371 multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
2372
2373 /* Discard r1s while r1 << r2 */
2374 while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
2375 {
2376 if (++i1 >= range_count1)
2377 return false;
2378 multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
2379 }
2380
2381 /*
2382 * If r1 @> r2, go to the next r2, otherwise return false (since every
2383 * r1[n] and r1[n+1] must have a gap). Note this will give weird
2384 * answers if you don't canonicalize, e.g. with a custom
2385 * int2multirange {[1,1], [2,2]} there is a "gap". But that is
2386 * consistent with other range operators, e.g. '[1,1]'::int2range -|-
2387 * '[2,2]'::int2range is false.
2388 */
2389 if (!range_bounds_contains(rangetyp, &lower1, &upper1,
2390 &lower2, &upper2))
2391 return false;
2392 }
2393
2394 /* All ranges in mr2 are satisfied */
2395 return true;
2396}
2397
2398/* strictly left of? */
2399Datum
2400range_before_multirange(PG_FUNCTION_ARGS)
2401{
2402 RangeType *r = PG_GETARG_RANGE_P(0);
2403 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2404 TypeCacheEntry *typcache;
2405
2406 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2407
2408 PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
2409}
2410
2411Datum
2412multirange_before_range(PG_FUNCTION_ARGS)
2413{
2414 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2415 RangeType *r = PG_GETARG_RANGE_P(1);
2416 TypeCacheEntry *typcache;
2417
2418 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2419
2420 PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
2421}
2422
2423Datum
2424multirange_before_multirange(PG_FUNCTION_ARGS)
2425{
2426 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2427 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2428 TypeCacheEntry *typcache;
2429
2430 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2431
2432 PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr1, mr2));
2433}
2434
2435/* strictly right of? */
2436Datum
2437range_after_multirange(PG_FUNCTION_ARGS)
2438{
2439 RangeType *r = PG_GETARG_RANGE_P(0);
2440 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2441 TypeCacheEntry *typcache;
2442
2443 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2444
2445 PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr));
2446}
2447
2448Datum
2449multirange_after_range(PG_FUNCTION_ARGS)
2450{
2451 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2452 RangeType *r = PG_GETARG_RANGE_P(1);
2453 TypeCacheEntry *typcache;
2454
2455 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2456
2457 PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr));
2458}
2459
2460Datum
2461multirange_after_multirange(PG_FUNCTION_ARGS)
2462{
2463 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2464 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2465 TypeCacheEntry *typcache;
2466
2467 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2468
2469 PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr2, mr1));
2470}
2471
2472/* strictly left of? (internal version) */
2473bool
2474range_before_multirange_internal(TypeCacheEntry *rangetyp,
2475 const RangeType *r,
2476 const MultirangeType *mr)
2477{
2478 RangeBound lower1,
2479 upper1,
2480 lower2,
2481 upper2;
2482 bool empty;
2483
2484 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2485 return false;
2486
2487 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2488 Assert(!empty);
2489
2490 multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2);
2491
2492 return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
2493}
2494
2495bool
2496multirange_before_multirange_internal(TypeCacheEntry *rangetyp,
2497 const MultirangeType *mr1,
2498 const MultirangeType *mr2)
2499{
2500 RangeBound lower1,
2501 upper1,
2502 lower2,
2503 upper2;
2504
2505 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2506 return false;
2507
2508 multirange_get_bounds(rangetyp, mr1, mr1->rangeCount - 1,
2509 &lower1, &upper1);
2510 multirange_get_bounds(rangetyp, mr2, 0,
2511 &lower2, &upper2);
2512
2513 return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0);
2514}
2515
2516/* strictly right of? (internal version) */
2517bool
2518range_after_multirange_internal(TypeCacheEntry *rangetyp,
2519 const RangeType *r,
2520 const MultirangeType *mr)
2521{
2522 RangeBound lower1,
2523 upper1,
2524 lower2,
2525 upper2;
2526 bool empty;
2527 int32 range_count;
2528
2529 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2530 return false;
2531
2532 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2533 Assert(!empty);
2534
2535 range_count = mr->rangeCount;
2536 multirange_get_bounds(rangetyp, mr, range_count - 1,
2537 &lower2, &upper2);
2538
2539 return (range_cmp_bounds(rangetyp, &lower1, &upper2) > 0);
2540}
2541
2542bool
2543range_adjacent_multirange_internal(TypeCacheEntry *rangetyp,
2544 const RangeType *r,
2545 const MultirangeType *mr)
2546{
2547 RangeBound lower1,
2548 upper1,
2549 lower2,
2550 upper2;
2551 bool empty;
2552 int32 range_count;
2553
2554 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2555 return false;
2556
2557 range_deserialize(rangetyp, r, &lower1, &upper1, &empty);
2558 Assert(!empty);
2559
2560 range_count = mr->rangeCount;
2561 multirange_get_bounds(rangetyp, mr, 0,
2562 &lower2, &upper2);
2563
2564 if (bounds_adjacent(rangetyp, upper1, lower2))
2565 return true;
2566
2567 if (range_count > 1)
2568 multirange_get_bounds(rangetyp, mr, range_count - 1,
2569 &lower2, &upper2);
2570
2571 if (bounds_adjacent(rangetyp, upper2, lower1))
2572 return true;
2573
2574 return false;
2575}
2576
2577/* adjacent to? */
2578Datum
2579range_adjacent_multirange(PG_FUNCTION_ARGS)
2580{
2581 RangeType *r = PG_GETARG_RANGE_P(0);
2582 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
2583 TypeCacheEntry *typcache;
2584
2585 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2586
2587 PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
2588}
2589
2590Datum
2591multirange_adjacent_range(PG_FUNCTION_ARGS)
2592{
2593 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2594 RangeType *r = PG_GETARG_RANGE_P(1);
2595 TypeCacheEntry *typcache;
2596
2597 if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
2598 PG_RETURN_BOOL(false);
2599
2600 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2601
2602 PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr));
2603}
2604
2605Datum
2606multirange_adjacent_multirange(PG_FUNCTION_ARGS)
2607{
2608 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2609 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2610 TypeCacheEntry *typcache;
2611 int32 range_count1;
2612 int32 range_count2;
2613 RangeBound lower1,
2614 upper1,
2615 lower2,
2616 upper2;
2617
2618 if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
2619 PG_RETURN_BOOL(false);
2620
2621 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2622
2623 range_count1 = mr1->rangeCount;
2624 range_count2 = mr2->rangeCount;
2625 multirange_get_bounds(typcache->rngtype, mr1, range_count1 - 1,
2626 &lower1, &upper1);
2627 multirange_get_bounds(typcache->rngtype, mr2, 0,
2628 &lower2, &upper2);
2629 if (bounds_adjacent(typcache->rngtype, upper1, lower2))
2630 PG_RETURN_BOOL(true);
2631
2632 if (range_count1 > 1)
2633 multirange_get_bounds(typcache->rngtype, mr1, 0,
2634 &lower1, &upper1);
2635 if (range_count2 > 1)
2636 multirange_get_bounds(typcache->rngtype, mr2, range_count2 - 1,
2637 &lower2, &upper2);
2638 if (bounds_adjacent(typcache->rngtype, upper2, lower1))
2639 PG_RETURN_BOOL(true);
2640 PG_RETURN_BOOL(false);
2641}
2642
2643/* Btree support */
2644
2645/* btree comparator */
2646Datum
2647multirange_cmp(PG_FUNCTION_ARGS)
2648{
2649 MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
2650 MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
2651 int32 range_count_1;
2652 int32 range_count_2;
2653 int32 range_count_max;
2654 int32 i;
2655 TypeCacheEntry *typcache;
2656 int cmp = 0; /* If both are empty we'll use this. */
2657
2658 /* Different types should be prevented by ANYMULTIRANGE matching rules */
2659 if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
2660 elog(ERROR, "multirange types do not match");
2661
2662 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
2663
2664 range_count_1 = mr1->rangeCount;
2665 range_count_2 = mr2->rangeCount;
2666
2667 /* Loop over source data */
2668 range_count_max = Max(range_count_1, range_count_2);
2669 for (i = 0; i < range_count_max; i++)
2670 {
2671 RangeBound lower1,
2672 upper1,
2673 lower2,
2674 upper2;
2675
2676 /*
2677 * If one multirange is shorter, it's as if it had empty ranges at the
2678 * end to extend its length. An empty range compares earlier than any
2679 * other range, so the shorter multirange comes before the longer.
2680 * This is the same behavior as in other types, e.g. in strings 'aaa'
2681 * < 'aaaaaa'.
2682 */
2683 if (i >= range_count_1)
2684 {
2685 cmp = -1;
2686 break;
2687 }
2688 if (i >= range_count_2)
2689 {
2690 cmp = 1;
2691 break;
2692 }
2693
2694 multirange_get_bounds(typcache->rngtype, mr1, i, &lower1, &upper1);
2695 multirange_get_bounds(typcache->rngtype, mr2, i, &lower2, &upper2);
2696
2697 cmp = range_cmp_bounds(typcache->rngtype, &lower1, &lower2);
2698 if (cmp == 0)
2699 cmp = range_cmp_bounds(typcache->rngtype, &upper1, &upper2);
2700 if (cmp != 0)
2701 break;
2702 }
2703
2704 PG_FREE_IF_COPY(mr1, 0);
2705 PG_FREE_IF_COPY(mr2, 1);
2706
2707 PG_RETURN_INT32(cmp);
2708}
2709
2710/* inequality operators using the multirange_cmp function */
2711Datum
2712multirange_lt(PG_FUNCTION_ARGS)
2713{
2714 int cmp = DatumGetInt32(multirange_cmp(fcinfo));
2715
2716 PG_RETURN_BOOL(cmp < 0);
2717}
2718
2719Datum
2720multirange_le(PG_FUNCTION_ARGS)
2721{
2722 int cmp = DatumGetInt32(multirange_cmp(fcinfo));
2723
2724 PG_RETURN_BOOL(cmp <= 0);
2725}
2726
2727Datum
2728multirange_ge(PG_FUNCTION_ARGS)
2729{
2730 int cmp = DatumGetInt32(multirange_cmp(fcinfo));
2731
2732 PG_RETURN_BOOL(cmp >= 0);
2733}
2734
2735Datum
2736multirange_gt(PG_FUNCTION_ARGS)
2737{
2738 int cmp = DatumGetInt32(multirange_cmp(fcinfo));
2739
2740 PG_RETURN_BOOL(cmp > 0);
2741}
2742
2743/* multirange -> range functions */
2744
2745/* Find the smallest range that includes everything in the multirange */
2746Datum
2747range_merge_from_multirange(PG_FUNCTION_ARGS)
2748{
2749 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2750 Oid mltrngtypoid = MultirangeTypeGetOid(mr);
2751 TypeCacheEntry *typcache;
2752 RangeType *result;
2753
2754 typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
2755
2756 if (MultirangeIsEmpty(mr))
2757 {
2758 result = make_empty_range(typcache->rngtype);
2759 }
2760 else if (mr->rangeCount == 1)
2761 {
2762 result = multirange_get_range(typcache->rngtype, mr, 0);
2763 }
2764 else
2765 {
2766 RangeBound firstLower,
2767 firstUpper,
2768 lastLower,
2769 lastUpper;
2770
2771 multirange_get_bounds(typcache->rngtype, mr, 0,
2772 &firstLower, &firstUpper);
2773 multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
2774 &lastLower, &lastUpper);
2775
2776 result = make_range(typcache->rngtype, &firstLower, &lastUpper,
2777 false, NULL);
2778 }
2779
2780 PG_RETURN_RANGE_P(result);
2781}
2782
2783/* Turn multirange into a set of ranges */
2784Datum
2785multirange_unnest(PG_FUNCTION_ARGS)
2786{
2787 typedef struct
2788 {
2789 MultirangeType *mr;
2790 TypeCacheEntry *typcache;
2791 int index;
2792 } multirange_unnest_fctx;
2793
2794 FuncCallContext *funcctx;
2795 multirange_unnest_fctx *fctx;
2796 MemoryContext oldcontext;
2797
2798 /* stuff done only on the first call of the function */
2799 if (SRF_IS_FIRSTCALL())
2800 {
2801 MultirangeType *mr;
2802
2803 /* create a function context for cross-call persistence */
2804 funcctx = SRF_FIRSTCALL_INIT();
2805
2806 /*
2807 * switch to memory context appropriate for multiple function calls
2808 */
2809 oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
2810
2811 /*
2812 * Get the multirange value and detoast if needed. We can't do this
2813 * earlier because if we have to detoast, we want the detoasted copy
2814 * to be in multi_call_memory_ctx, so it will go away when we're done
2815 * and not before. (If no detoast happens, we assume the originally
2816 * passed multirange will stick around till then.)
2817 */
2818 mr = PG_GETARG_MULTIRANGE_P(0);
2819
2820 /* allocate memory for user context */
2821 fctx = (multirange_unnest_fctx *) palloc(sizeof(multirange_unnest_fctx));
2822
2823 /* initialize state */
2824 fctx->mr = mr;
2825 fctx->index = 0;
2826 fctx->typcache = lookup_type_cache(MultirangeTypeGetOid(mr),
2827 TYPECACHE_MULTIRANGE_INFO);
2828
2829 funcctx->user_fctx = fctx;
2830 MemoryContextSwitchTo(oldcontext);
2831 }
2832
2833 /* stuff done on every call of the function */
2834 funcctx = SRF_PERCALL_SETUP();
2835 fctx = funcctx->user_fctx;
2836
2837 if (fctx->index < fctx->mr->rangeCount)
2838 {
2839 RangeType *range;
2840
2841 range = multirange_get_range(fctx->typcache->rngtype,
2842 fctx->mr,
2843 fctx->index);
2844 fctx->index++;
2845
2846 SRF_RETURN_NEXT(funcctx, RangeTypePGetDatum(range));
2847 }
2848 else
2849 {
2850 /* do when there is no more left */
2851 SRF_RETURN_DONE(funcctx);
2852 }
2853}
2854
2855/* Hash support */
2856
2857/* hash a multirange value */
2858Datum
2859hash_multirange(PG_FUNCTION_ARGS)
2860{
2861 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2862 uint32 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_proc_finfo.fn_oid))
2871 {
2872 scache = lookup_type_cache(scache->type_id,
2873 TYPECACHE_HASH_PROC_FINFO);
2874 if (!OidIsValid(scache->hash_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 uint32 lower_hash;
2888 uint32 upper_hash;
2889 uint32 range_hash;
2890
2891 multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
2892
2893 if (RANGE_HAS_LBOUND(flags))
2894 lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
2895 typcache->rngtype->rng_collation,
2896 lower.val));
2897 else
2898 lower_hash = 0;
2899
2900 if (RANGE_HAS_UBOUND(flags))
2901 upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
2902 typcache->rngtype->rng_collation,
2903 upper.val));
2904 else
2905 upper_hash = 0;
2906
2907 /* Merge hashes of flags and bounds */
2908 range_hash = hash_bytes_uint32((uint32) flags);
2909 range_hash ^= lower_hash;
2910 range_hash = pg_rotate_left32(range_hash, 1);
2911 range_hash ^= upper_hash;
2912
2913 /*
2914 * Use the same approach as hash_array to combine the individual
2915 * elements' hash values:
2916 */
2917 result = (result << 5) - result + range_hash;
2918 }
2919
2920 PG_FREE_IF_COPY(mr, 0);
2921
2922 PG_RETURN_UINT32(result);
2923}
2924
2925/*
2926 * Returns 64-bit value by hashing a value to a 64-bit value, with a seed.
2927 * Otherwise, similar to hash_multirange.
2928 */
2929Datum
2930hash_multirange_extended(PG_FUNCTION_ARGS)
2931{
2932 MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
2933 Datum seed = PG_GETARG_DATUM(1);
2934 uint64 result = 1;
2935 TypeCacheEntry *typcache,
2936 *scache;
2937 int32 range_count,
2938 i;
2939
2940 typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
2941 scache = typcache->rngtype->rngelemtype;
2942 if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
2943 {
2944 scache = lookup_type_cache(scache->type_id,
2945 TYPECACHE_HASH_EXTENDED_PROC_FINFO);
2946 if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
2947 ereport(ERROR,
2948 (errcode(ERRCODE_UNDEFINED_FUNCTION),
2949 errmsg("could not identify a hash function for type %s",
2950 format_type_be(scache->type_id))));
2951 }
2952
2953 range_count = mr->rangeCount;
2954 for (i = 0; i < range_count; i++)
2955 {
2956 RangeBound lower,
2957 upper;
2958 uint8 flags = MultirangeGetFlagsPtr(mr)[i];
2959 uint64 lower_hash;
2960 uint64 upper_hash;
2961 uint64 range_hash;
2962
2963 multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
2964
2965 if (RANGE_HAS_LBOUND(flags))
2966 lower_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
2967 typcache->rngtype->rng_collation,
2968 lower.val,
2969 seed));
2970 else
2971 lower_hash = 0;
2972
2973 if (RANGE_HAS_UBOUND(flags))
2974 upper_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
2975 typcache->rngtype->rng_collation,
2976 upper.val,
2977 seed));
2978 else
2979 upper_hash = 0;
2980
2981 /* Merge hashes of flags and bounds */
2982 range_hash = DatumGetUInt64(hash_uint32_extended((uint32) flags,
2983 DatumGetInt64(seed)));
2984 range_hash ^= lower_hash;
2985 range_hash = ROTATE_HIGH_AND_LOW_32BITS(range_hash);
2986 range_hash ^= upper_hash;
2987
2988 /*
2989 * Use the same approach as hash_array to combine the individual
2990 * elements' hash values:
2991 */
2992 result = (result << 5) - result + range_hash;
2993 }
2994
2995 PG_FREE_IF_COPY(mr, 0);
2996
2997 PG_RETURN_UINT64(result);
2998}
idx
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:262
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:5351
initArrayResult
ArrayBuildState * initArrayResult(Oid element_type, MemoryContext rcontext, bool subcontext)
Definition: arrayfuncs.c:5294
deconstruct_array
void deconstruct_array(const ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3632
uint8
uint8_t uint8
Definition: c.h:539
Max
#define Max(x, y)
Definition: c.h:1000
VARHDRSZ
#define VARHDRSZ
Definition: c.h:700
int16
int16_t int16
Definition: c.h:536
int32
int32_t int32
Definition: c.h:537
uint64
uint64_t uint64
Definition: c.h:542
uint32
uint32_t uint32
Definition: c.h:541
OidIsValid
#define OidIsValid(objectId)
Definition: c.h:777
Size
size_t Size
Definition: c.h:613
errdetail
int errdetail(const char *fmt,...)
Definition: elog.c:1216
errcode
int errcode(int sqlerrcode)
Definition: elog.c:863
errmsg
int errmsg(const char *fmt,...)
Definition: elog.c:1080
ereturn
#define ereturn(context, dummy_value,...)
Definition: elog.h:278
ERROR
#define ERROR
Definition: elog.h:39
elog
#define elog(elevel,...)
Definition: elog.h:226
ereport
#define ereport(elevel,...)
Definition: elog.h:150
FunctionCall2Coll
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1150
fmgr_info_cxt
void fmgr_info_cxt(Oid functionId, FmgrInfo *finfo, MemoryContext mcxt)
Definition: fmgr.c:138
SendFunctionCall
bytea * SendFunctionCall(FmgrInfo *flinfo, Datum val)
Definition: fmgr.c:1744
InputFunctionCallSafe
bool InputFunctionCallSafe(FmgrInfo *flinfo, char *str, Oid typioparam, int32 typmod, Node *escontext, Datum *result)
Definition: fmgr.c:1585
OutputFunctionCall
char * OutputFunctionCall(FmgrInfo *flinfo, Datum val)
Definition: fmgr.c:1683
get_fn_expr_argtype
Oid get_fn_expr_argtype(FmgrInfo *flinfo, int argnum)
Definition: fmgr.c:1875
FunctionCall1Coll
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1130
get_fn_expr_rettype
Oid get_fn_expr_rettype(FmgrInfo *flinfo)
Definition: fmgr.c:1853
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
hash_bytes_uint32
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610
ROTATE_HIGH_AND_LOW_32BITS
#define ROTATE_HIGH_AND_LOW_32BITS(v)
Definition: hashfn.h:18
hash_uint32_extended
static Datum hash_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.h:49
Assert
Assert(PointerIsAligned(start, uint64))
val
long val
Definition: informix.c:689
i
int i
Definition: isn.c:77
if
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:81
type_is_range
bool type_is_range(Oid typid)
Definition: lsyscache.c:2855
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:2492
type_is_multirange
bool type_is_multirange(Oid typid)
Definition: lsyscache.c:2865
IOFuncSelector
IOFuncSelector
Definition: lsyscache.h:35
IOFunc_output
@ IOFunc_output
Definition: lsyscache.h:37
IOFunc_input
@ IOFunc_input
Definition: lsyscache.h:36
IOFunc_send
@ IOFunc_send
Definition: lsyscache.h:39
IOFunc_receive
@ IOFunc_receive
Definition: lsyscache.h:38
MemoryContextAlloc
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1229
repalloc
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1610
pfree
void pfree(void *pointer)
Definition: mcxt.c:1594
palloc0
void * palloc0(Size size)
Definition: mcxt.c:1395
palloc
void * palloc(Size size)
Definition: mcxt.c:1365
pnstrdup
char * pnstrdup(const char *in, Size len)
Definition: mcxt.c:1770
MultirangeIOData
struct MultirangeIOData MultirangeIOData
MULTIRANGE_ITEM_GET_OFFLEN
#define MULTIRANGE_ITEM_GET_OFFLEN(item)
Definition: multirangetypes.c:81
multirange_intersect_internal
MultirangeType * multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count1, RangeType **ranges1, int32 range_count2, RangeType **ranges2)
Definition: multirangetypes.c:1333
multirange_minus_internal
MultirangeType * multirange_minus_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count1, RangeType **ranges1, int32 range_count2, RangeType **ranges2)
Definition: multirangetypes.c:1146
multirange_upper
Datum multirange_upper(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1603
multirange_adjacent_range
Datum multirange_adjacent_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2591
multirange_before_range
Datum multirange_before_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2412
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:1485
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:1847
multirange_contains_elem_internal
bool multirange_contains_elem_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr, Datum val)
Definition: multirangetypes.c:1780
multirange_upper_inf
Datum multirange_upper_inf(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1695
multirange_intersect_agg_transfn
Datum multirange_intersect_agg_transfn(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1538
range_overleft_multirange
Datum range_overleft_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2168
multirange_get_range
RangeType * multirange_get_range(TypeCacheEntry *rangetyp, const MultirangeType *multirange, int i)
Definition: multirangetypes.c:697
range_after_multirange
Datum range_after_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2437
multirange_upper_inc
Datum multirange_upper_inc(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1657
elem_contained_by_multirange
Datum elem_contained_by_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1731
multirange_before_multirange_internal
bool multirange_before_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:2496
multirange_lt
Datum multirange_lt(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2712
multirange_overlaps_multirange
Datum multirange_overlaps_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2033
range_contained_by_multirange
Datum range_contained_by_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1819
multirange_overright_range
Datum multirange_overright_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2263
range_overlaps_multirange
Datum range_overlaps_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2009
make_multirange
MultirangeType * make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges)
Definition: multirangetypes.c:648
multirange_eq_internal
bool multirange_eq_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:1937
multirange_ge
Datum multirange_ge(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2728
multirange_contained_by_range
Datum multirange_contained_by_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1831
multirange_canonicalize
static int32 multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count, RangeType **ranges)
Definition: multirangetypes.c:479
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:2736
multirange_intersect
Datum multirange_intersect(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1303
multirange_contains_multirange_internal
bool multirange_contains_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:2338
multirange_lower_inc
Datum multirange_lower_inc(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1638
make_empty_multirange
MultirangeType * make_empty_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp)
Definition: multirangetypes.c:850
multirange_get_bounds
void multirange_get_bounds(TypeCacheEntry *rangetyp, const MultirangeType *multirange, uint32 i, RangeBound *lower, RangeBound *upper)
Definition: multirangetypes.c:746
multirange_overlaps_range
Datum multirange_overlaps_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2021
multirange_overright_multirange
Datum multirange_overright_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2287
range_adjacent_multirange
Datum range_adjacent_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2579
multirange_out
Datum multirange_out(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:299
multirange_constructor1
Datum multirange_constructor1(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1025
multirange_in
Datum multirange_in(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:117
multirange_constructor2
Datum multirange_constructor2(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:943
multirange_size_estimate
static Size multirange_size_estimate(TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges)
Definition: multirangetypes.c:571
write_multirange_data
static void write_multirange_data(MultirangeType *multirange, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges)
Definition: multirangetypes.c:598
multirange_overleft_range
Datum multirange_overleft_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2180
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:900
range_adjacent_multirange_internal
bool range_adjacent_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2543
multirange_after_multirange
Datum multirange_after_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2461
multirange_contains_elem
Datum multirange_contains_elem(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1718
range_agg_finalfn
Datum range_agg_finalfn(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1445
range_after_multirange_internal
bool range_after_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2518
multirange_union
Datum multirange_union(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1084
multirange_adjacent_multirange
Datum multirange_adjacent_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2606
multirange_before_multirange
Datum multirange_before_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2424
get_multirange_io_data
static MultirangeIOData * get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func)
Definition: multirangetypes.c:418
range_overright_multirange
Datum range_overright_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2251
multirange_lower
Datum multirange_lower(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1580
multirange_minus_multi
Datum multirange_minus_multi(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1235
multirange_overleft_multirange
Datum multirange_overleft_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2205
multirange_ne
Datum multirange_ne(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1996
multirange_contains_range_internal
bool multirange_contains_range_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr, const RangeType *r)
Definition: multirangetypes.c:1874
multirange_overlaps_multirange_internal
bool multirange_overlaps_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:2088
multirange_eq
Datum multirange_eq(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1974
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:880
multirange_deserialize
void multirange_deserialize(TypeCacheEntry *rangetyp, const MultirangeType *multirange, int32 *range_count, RangeType ***ranges)
Definition: multirangetypes.c:828
range_bounds_overlaps
static bool range_bounds_overlaps(TypeCacheEntry *typcache, RangeBound *lower1, RangeBound *upper1, RangeBound *lower2, RangeBound *upper2)
Definition: multirangetypes.c:860
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_get_typcache
TypeCacheEntry * multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid)
Definition: multirangetypes.c:550
multirange_minus
Datum multirange_minus(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1116
multirange_contains_multirange
Datum multirange_contains_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2310
MultirangeGetItemsPtr
#define MultirangeGetItemsPtr(mr)
Definition: multirangetypes.c:71
multirange_le
Datum multirange_le(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2720
MultirangeGetFlagsPtr
#define MultirangeGetFlagsPtr(mr)
Definition: multirangetypes.c:73
hash_multirange
Datum hash_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2859
multirange_get_union_range
RangeType * multirange_get_union_range(TypeCacheEntry *rangetyp, const MultirangeType *mr)
Definition: multirangetypes.c:804
hash_multirange_extended
Datum hash_multirange_extended(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2930
multirange_constructor0
Datum multirange_constructor0(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1061
multirange_after_range
Datum multirange_after_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2449
multirange_contained_by_multirange
Datum multirange_contained_by_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2323
multirange_empty
Datum multirange_empty(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1629
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:2049
multirange_elem_bsearch_comparison
static int multirange_elem_bsearch_comparison(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, void *key, bool *match)
Definition: multirangetypes.c:1747
range_before_multirange
Datum range_before_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2400
range_before_multirange_internal
bool range_before_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2474
range_overright_multirange_internal
bool range_overright_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2230
range_contains_multirange_internal
bool range_contains_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:1902
multirange_ne_internal
bool multirange_ne_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2)
Definition: multirangetypes.c:1987
multirange_cmp
Datum multirange_cmp(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2647
multirange_get_bounds_offset
static uint32 multirange_get_bounds_offset(const MultirangeType *multirange, int32 i)
Definition: multirangetypes.c:675
range_overlaps_multirange_internal
bool range_overlaps_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2066
range_merge_from_multirange
Datum range_merge_from_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2747
range_agg_transfn
Datum range_agg_transfn(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1413
range_contains_multirange
Datum range_contains_multirange(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1806
MULTIRANGE_ITEM_OFF_BIT
#define MULTIRANGE_ITEM_OFF_BIT
Definition: multirangetypes.c:80
multirange_unnest
Datum multirange_unnest(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:2785
multirange_contains_range
Datum multirange_contains_range(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1794
range_overleft_multirange_internal
bool range_overleft_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr)
Definition: multirangetypes.c:2146
MultirangeGetBoundariesPtr
#define MultirangeGetBoundariesPtr(mr, align)
Definition: multirangetypes.c:75
multirange_lower_inf
Datum multirange_lower_inf(PG_FUNCTION_ARGS)
Definition: multirangetypes.c:1676
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
MultirangeTypePGetDatum
static Datum MultirangeTypePGetDatum(const MultirangeType *X)
Definition: multirangetypes.h:60
AggCheckCallContext
int AggCheckCallContext(FunctionCallInfo fcinfo, MemoryContext *aggcontext)
Definition: nodeAgg.c:4613
lower
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
upper
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
MemoryContextSwitchTo
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
pg_bitutils.h
pg_rotate_left32
static uint32 pg_rotate_left32(uint32 word, int n)
Definition: pg_bitutils.h:428
len
const void size_t len
Definition: pg_crc32c_sse42.c:28
buf
static char * buf
Definition: pg_test_fsync.c:72
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:65
DatumGetUInt32
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:232
DatumGetUInt64
static uint64 DatumGetUInt64(Datum X)
Definition: postgres.h:413
DatumGetInt64
static int64 DatumGetInt64(Datum X)
Definition: postgres.h:393
Datum
uint64_t Datum
Definition: postgres.h:70
DatumGetInt32
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:212
Oid
unsigned int Oid
Definition: postgres_ext.h:32
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_begintypsend
void pq_begintypsend(StringInfo buf)
Definition: pqformat.c:326
pq_getmsgbytes
const char * pq_getmsgbytes(StringInfo msg, int datalen)
Definition: pqformat.c:508
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
range_cmp_bounds
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:2248
range_split_internal
bool range_split_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2, RangeType **output1, RangeType **output2)
Definition: rangetypes.c:1186
make_range
RangeType * make_range(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty, struct Node *escontext)
Definition: rangetypes.c:2184
bounds_adjacent
bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
Definition: rangetypes.c:761
range_overlaps_internal
bool range_overlaps_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:845
range_before_internal
bool range_before_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:668
range_intersect_internal
RangeType * range_intersect_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:1147
range_minus_internal
RangeType * range_minus_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:997
range_deserialize
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:2088
range_union_internal
RangeType * range_union_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2, bool strict)
Definition: rangetypes.c:1056
range_adjacent_internal
bool range_adjacent_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:802
range_overleft_internal
bool range_overleft_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:891
range_compare
int range_compare(const void *key1, const void *key2, void *arg)
Definition: rangetypes.c:2361
make_empty_range
RangeType * make_empty_range(TypeCacheEntry *typcache)
Definition: rangetypes.c:2397
DatumGetRangeTypeP
static RangeType * DatumGetRangeTypeP(Datum X)
Definition: rangetypes.h:73
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
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
cmp
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
range
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
StringInfo
struct StringInfoData * StringInfo
Definition: string.h:15
resetStringInfo
void resetStringInfo(StringInfo str)
Definition: stringinfo.c:126
appendBinaryStringInfo
void appendBinaryStringInfo(StringInfo str, const void *data, int datalen)
Definition: stringinfo.c:281
appendStringInfoString
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:230
appendStringInfoChar
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:242
initStringInfo
void initStringInfo(StringInfo str)
Definition: stringinfo.c:97
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:135
TypeCacheEntry::hash_proc_finfo
FmgrInfo hash_proc_finfo
Definition: typcache.h:78
TypeCacheEntry::rng_cmp_proc_finfo
FmgrInfo rng_cmp_proc_finfo
Definition: typcache.h:102
TypeCacheEntry::rng_collation
Oid rng_collation
Definition: typcache.h:101
TypeCacheEntry::typalign
char typalign
Definition: typcache.h:41
TypeCacheEntry::rngelemtype
struct TypeCacheEntry * rngelemtype
Definition: typcache.h:99
TypeCacheEntry::hash_extended_proc_finfo
FmgrInfo hash_extended_proc_finfo
Definition: typcache.h:79
TypeCacheEntry::rngtype
struct TypeCacheEntry * rngtype
Definition: typcache.h:109
TypeCacheEntry::typbyval
bool typbyval
Definition: typcache.h:40
TypeCacheEntry::typlen
int16 typlen
Definition: typcache.h:39
index
Definition: type.h:96
state
Definition: regguts.h:323
varlena
Definition: c.h:695
items
static ItemArray items
Definition: test_tidstore.c:48
att_align_pointer
#define att_align_pointer(cur_offset, attalign, attlen, attptr)
Definition: tupmacs.h:113
att_align_nominal
#define att_align_nominal(cur_offset, attalign)
Definition: tupmacs.h:145
att_addlength_pointer
#define att_addlength_pointer(cur_offset, attlen, attptr)
Definition: tupmacs.h:180
fetch_att
static Datum fetch_att(const void *T, bool attbyval, int attlen)
Definition: tupmacs.h:50
lookup_type_cache
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
TYPECACHE_HASH_PROC_FINFO
#define TYPECACHE_HASH_PROC_FINFO
Definition: typcache.h:145
TYPECACHE_MULTIRANGE_INFO
#define TYPECACHE_MULTIRANGE_INFO
Definition: typcache.h:154
TYPECACHE_HASH_EXTENDED_PROC_FINFO
#define TYPECACHE_HASH_EXTENDED_PROC_FINFO
Definition: typcache.h:153
VARSIZE
static Size VARSIZE(const void *PTR)
Definition: varatt.h:298
VARDATA
static char * VARDATA(const void *PTR)
Definition: varatt.h:305
SET_VARSIZE
static void SET_VARSIZE(void *PTR, Size len)
Definition: varatt.h:432
tmpbuf
static StringInfoData tmpbuf
Definition: walsender.c:178