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