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