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