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