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