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