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