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