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