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