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