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