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