/*------------------------------------------------------------------------- * * multirangetypes.c * I/O functions, operators, and support functions for multirange types. * * The stored (serialized) format of a multirange value is: * * 12 bytes: MultirangeType struct including varlena header, multirange * type's OID and the number of ranges in the multirange. * 4 * (rangesCount - 1) bytes: 32-bit items pointing to the each range * in the multirange starting from * the second one. * 1 * rangesCount bytes : 8-bit flags for each range in the multirange * The rest of the multirange are range bound values pointed by multirange * items. * * Majority of items contain lengths of corresponding range bound values. * Thanks to that items are typically low numbers. This makes multiranges * compression-friendly. Every MULTIRANGE_ITEM_OFFSET_STRIDE item contains * an offset of the corresponding range bound values. That allows fast lookups * for a particular range index. Offsets are counted starting from the end of * flags aligned to the bound type. * * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION * src/backend/utils/adt/multirangetypes.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include "access/tupmacs.h" #include "common/hashfn.h" #include "funcapi.h" #include "lib/stringinfo.h" #include "libpq/pqformat.h" #include "nodes/nodes.h" #include "port/pg_bitutils.h" #include "utils/array.h" #include "utils/builtins.h" #include "utils/lsyscache.h" #include "utils/multirangetypes.h" #include "utils/rangetypes.h" /* fn_extra cache entry for one of the range I/O functions */ typedef struct MultirangeIOData { TypeCacheEntry *typcache; /* multirange type's typcache entry */ FmgrInfo typioproc; /* range type's I/O proc */ Oid typioparam; /* range type's I/O parameter */ } MultirangeIOData; typedef enum { MULTIRANGE_BEFORE_RANGE, MULTIRANGE_IN_RANGE, MULTIRANGE_IN_RANGE_ESCAPED, MULTIRANGE_IN_RANGE_QUOTED, MULTIRANGE_IN_RANGE_QUOTED_ESCAPED, MULTIRANGE_AFTER_RANGE, MULTIRANGE_FINISHED, } MultirangeParseState; /* * Macros for accessing past MultirangeType parts of multirange: items, flags * and boundaries. */ #define MultirangeGetItemsPtr(mr) ((uint32 *) ((Pointer) (mr) + \ sizeof(MultirangeType))) #define MultirangeGetFlagsPtr(mr) ((uint8 *) ((Pointer) (mr) + \ sizeof(MultirangeType) + ((mr)->rangeCount - 1) * sizeof(uint32))) #define MultirangeGetBoundariesPtr(mr, align) ((Pointer) (mr) + \ att_align_nominal(sizeof(MultirangeType) + \ ((mr)->rangeCount - 1) * sizeof(uint32) + \ (mr)->rangeCount * sizeof(uint8), (align))) #define MULTIRANGE_ITEM_OFF_BIT 0x80000000 #define MULTIRANGE_ITEM_GET_OFFLEN(item) ((item) & 0x7FFFFFFF) #define MULTIRANGE_ITEM_HAS_OFF(item) ((item) & MULTIRANGE_ITEM_OFF_BIT) #define MULTIRANGE_ITEM_OFFSET_STRIDE 4 typedef int (*multirange_bsearch_comparison) (TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, void *key, bool *match); static MultirangeIOData *get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func); static int32 multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count, RangeType **ranges); /* *---------------------------------------------------------- * I/O FUNCTIONS *---------------------------------------------------------- */ /* * Converts string to multirange. * * We expect curly brackets to bound the list, with zero or more ranges * separated by commas. We accept whitespace anywhere: before/after our * brackets and around the commas. Ranges can be the empty literal or some * stuff inside parens/brackets. Mostly we delegate parsing the individual * range contents to range_in, but we have to detect quoting and * backslash-escaping which can happen for range bounds. Backslashes can * escape something inside or outside a quoted string, and a quoted string * can escape quote marks with either backslashes or double double-quotes. */ Datum multirange_in(PG_FUNCTION_ARGS) { char *input_str = PG_GETARG_CSTRING(0); Oid mltrngtypoid = PG_GETARG_OID(1); Oid typmod = PG_GETARG_INT32(2); Node *escontext = fcinfo->context; TypeCacheEntry *rangetyp; int32 ranges_seen = 0; int32 range_count = 0; int32 range_capacity = 8; RangeType *range; RangeType **ranges = palloc(range_capacity * sizeof(RangeType *)); MultirangeIOData *cache; MultirangeType *ret; MultirangeParseState parse_state; const char *ptr = input_str; const char *range_str_begin = NULL; int32 range_str_len; char *range_str; Datum range_datum; cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_input); rangetyp = cache->typcache->rngtype; /* consume whitespace */ while (*ptr != '\0' && isspace((unsigned char) *ptr)) ptr++; if (*ptr == '{') ptr++; else ereturn(escontext, (Datum) 0, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg("malformed multirange literal: \"%s\"", input_str), errdetail("Missing left brace."))); /* consume ranges */ parse_state = MULTIRANGE_BEFORE_RANGE; for (; parse_state != MULTIRANGE_FINISHED; ptr++) { char ch = *ptr; if (ch == '\0') ereturn(escontext, (Datum) 0, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg("malformed multirange literal: \"%s\"", input_str), errdetail("Unexpected end of input."))); /* skip whitespace */ if (isspace((unsigned char) ch)) continue; switch (parse_state) { case MULTIRANGE_BEFORE_RANGE: if (ch == '[' || ch == '(') { range_str_begin = ptr; parse_state = MULTIRANGE_IN_RANGE; } else if (ch == '}' && ranges_seen == 0) parse_state = MULTIRANGE_FINISHED; else if (pg_strncasecmp(ptr, RANGE_EMPTY_LITERAL, strlen(RANGE_EMPTY_LITERAL)) == 0) { ranges_seen++; /* nothing to do with an empty range */ ptr += strlen(RANGE_EMPTY_LITERAL) - 1; parse_state = MULTIRANGE_AFTER_RANGE; } else ereturn(escontext, (Datum) 0, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg("malformed multirange literal: \"%s\"", input_str), errdetail("Expected range start."))); break; case MULTIRANGE_IN_RANGE: if (ch == ']' || ch == ')') { range_str_len = ptr - range_str_begin + 1; range_str = pnstrdup(range_str_begin, range_str_len); if (range_capacity == range_count) { range_capacity *= 2; ranges = (RangeType **) repalloc(ranges, range_capacity * sizeof(RangeType *)); } ranges_seen++; if (!InputFunctionCallSafe(&cache->typioproc, range_str, cache->typioparam, typmod, escontext, &range_datum)) PG_RETURN_NULL(); range = DatumGetRangeTypeP(range_datum); if (!RangeIsEmpty(range)) ranges[range_count++] = range; parse_state = MULTIRANGE_AFTER_RANGE; } else { if (ch == '"') parse_state = MULTIRANGE_IN_RANGE_QUOTED; else if (ch == '\\') parse_state = MULTIRANGE_IN_RANGE_ESCAPED; /* * We will include this character into range_str once we * find the end of the range value. */ } break; case MULTIRANGE_IN_RANGE_ESCAPED: /* * We will include this character into range_str once we find * the end of the range value. */ parse_state = MULTIRANGE_IN_RANGE; break; case MULTIRANGE_IN_RANGE_QUOTED: if (ch == '"') if (*(ptr + 1) == '"') { /* two quote marks means an escaped quote mark */ ptr++; } else parse_state = MULTIRANGE_IN_RANGE; else if (ch == '\\') parse_state = MULTIRANGE_IN_RANGE_QUOTED_ESCAPED; /* * We will include this character into range_str once we find * the end of the range value. */ break; case MULTIRANGE_AFTER_RANGE: if (ch == ',') parse_state = MULTIRANGE_BEFORE_RANGE; else if (ch == '}') parse_state = MULTIRANGE_FINISHED; else ereturn(escontext, (Datum) 0, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg("malformed multirange literal: \"%s\"", input_str), errdetail("Expected comma or end of multirange."))); break; case MULTIRANGE_IN_RANGE_QUOTED_ESCAPED: /* * We will include this character into range_str once we find * the end of the range value. */ parse_state = MULTIRANGE_IN_RANGE_QUOTED; break; default: elog(ERROR, "unknown parse state: %d", parse_state); } } /* consume whitespace */ while (*ptr != '\0' && isspace((unsigned char) *ptr)) ptr++; if (*ptr != '\0') ereturn(escontext, (Datum) 0, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg("malformed multirange literal: \"%s\"", input_str), errdetail("Junk after closing right brace."))); ret = make_multirange(mltrngtypoid, rangetyp, range_count, ranges); PG_RETURN_MULTIRANGE_P(ret); } Datum multirange_out(PG_FUNCTION_ARGS) { MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0); Oid mltrngtypoid = MultirangeTypeGetOid(multirange); MultirangeIOData *cache; StringInfoData buf; RangeType *range; char *rangeStr; int32 range_count; int32 i; RangeType **ranges; cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_output); initStringInfo(&buf); appendStringInfoChar(&buf, '{'); multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges); for (i = 0; i < range_count; i++) { if (i > 0) appendStringInfoChar(&buf, ','); range = ranges[i]; rangeStr = OutputFunctionCall(&cache->typioproc, RangeTypePGetDatum(range)); appendStringInfoString(&buf, rangeStr); } appendStringInfoChar(&buf, '}'); PG_RETURN_CSTRING(buf.data); } /* * Binary representation: First an int32-sized count of ranges, followed by * ranges in their native binary representation. */ Datum multirange_recv(PG_FUNCTION_ARGS) { StringInfo buf = (StringInfo) PG_GETARG_POINTER(0); Oid mltrngtypoid = PG_GETARG_OID(1); int32 typmod = PG_GETARG_INT32(2); MultirangeIOData *cache; uint32 range_count; RangeType **ranges; MultirangeType *ret; StringInfoData tmpbuf; cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_receive); range_count = pq_getmsgint(buf, 4); ranges = palloc(range_count * sizeof(RangeType *)); initStringInfo(&tmpbuf); for (int i = 0; i < range_count; i++) { uint32 range_len = pq_getmsgint(buf, 4); const char *range_data = pq_getmsgbytes(buf, range_len); resetStringInfo(&tmpbuf); appendBinaryStringInfo(&tmpbuf, range_data, range_len); ranges[i] = DatumGetRangeTypeP(ReceiveFunctionCall(&cache->typioproc, &tmpbuf, cache->typioparam, typmod)); } pfree(tmpbuf.data); pq_getmsgend(buf); ret = make_multirange(mltrngtypoid, cache->typcache->rngtype, range_count, ranges); PG_RETURN_MULTIRANGE_P(ret); } Datum multirange_send(PG_FUNCTION_ARGS) { MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0); Oid mltrngtypoid = MultirangeTypeGetOid(multirange); StringInfo buf = makeStringInfo(); RangeType **ranges; int32 range_count; MultirangeIOData *cache; cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_send); /* construct output */ pq_begintypsend(buf); pq_sendint32(buf, multirange->rangeCount); multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges); for (int i = 0; i < range_count; i++) { Datum range; range = RangeTypePGetDatum(ranges[i]); range = PointerGetDatum(SendFunctionCall(&cache->typioproc, range)); pq_sendint32(buf, VARSIZE(range) - VARHDRSZ); pq_sendbytes(buf, VARDATA(range), VARSIZE(range) - VARHDRSZ); } PG_RETURN_BYTEA_P(pq_endtypsend(buf)); } /* * get_multirange_io_data: get cached information needed for multirange type I/O * * The multirange I/O functions need a bit more cached info than other multirange * functions, so they store a MultirangeIOData struct in fn_extra, not just a * pointer to a type cache entry. */ static MultirangeIOData * get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func) { MultirangeIOData *cache = (MultirangeIOData *) fcinfo->flinfo->fn_extra; if (cache == NULL || cache->typcache->type_id != mltrngtypid) { Oid typiofunc; int16 typlen; bool typbyval; char typalign; char typdelim; cache = (MultirangeIOData *) MemoryContextAlloc(fcinfo->flinfo->fn_mcxt, sizeof(MultirangeIOData)); cache->typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO); if (cache->typcache->rngtype == NULL) elog(ERROR, "type %u is not a multirange type", mltrngtypid); /* get_type_io_data does more than we need, but is convenient */ get_type_io_data(cache->typcache->rngtype->type_id, func, &typlen, &typbyval, &typalign, &typdelim, &cache->typioparam, &typiofunc); if (!OidIsValid(typiofunc)) { /* this could only happen for receive or send */ if (func == IOFunc_receive) ereport(ERROR, (errcode(ERRCODE_UNDEFINED_FUNCTION), errmsg("no binary input function available for type %s", format_type_be(cache->typcache->rngtype->type_id)))); else ereport(ERROR, (errcode(ERRCODE_UNDEFINED_FUNCTION), errmsg("no binary output function available for type %s", format_type_be(cache->typcache->rngtype->type_id)))); } fmgr_info_cxt(typiofunc, &cache->typioproc, fcinfo->flinfo->fn_mcxt); fcinfo->flinfo->fn_extra = cache; } return cache; } /* * Converts a list of arbitrary ranges into a list that is sorted and merged. * Changes the contents of `ranges`. * * Returns the number of slots actually used, which may be less than * input_range_count but never more. * * We assume that no input ranges are null, but empties are okay. */ static int32 multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count, RangeType **ranges) { RangeType *lastRange = NULL; RangeType *currentRange; int32 i; int32 output_range_count = 0; /* Sort the ranges so we can find the ones that overlap/meet. */ qsort_arg(ranges, input_range_count, sizeof(RangeType *), range_compare, rangetyp); /* Now merge where possible: */ for (i = 0; i < input_range_count; i++) { currentRange = ranges[i]; if (RangeIsEmpty(currentRange)) continue; if (lastRange == NULL) { ranges[output_range_count++] = lastRange = currentRange; continue; } /* * range_adjacent_internal gives true if *either* A meets B or B meets * A, which is not quite want we want, but we rely on the sorting * above to rule out B meets A ever happening. */ if (range_adjacent_internal(rangetyp, lastRange, currentRange)) { /* The two ranges touch (without overlap), so merge them: */ ranges[output_range_count - 1] = lastRange = range_union_internal(rangetyp, lastRange, currentRange, false); } else if (range_before_internal(rangetyp, lastRange, currentRange)) { /* There's a gap, so make a new entry: */ lastRange = ranges[output_range_count] = currentRange; output_range_count++; } else { /* They must overlap, so merge them: */ ranges[output_range_count - 1] = lastRange = range_union_internal(rangetyp, lastRange, currentRange, true); } } return output_range_count; } /* *---------------------------------------------------------- * SUPPORT FUNCTIONS * * These functions aren't in pg_proc, but are useful for * defining new generic multirange functions in C. *---------------------------------------------------------- */ /* * multirange_get_typcache: get cached information about a multirange type * * This is for use by multirange-related functions that follow the convention * of using the fn_extra field as a pointer to the type cache entry for * the multirange type. Functions that need to cache more information than * that must fend for themselves. */ TypeCacheEntry * multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid) { TypeCacheEntry *typcache = (TypeCacheEntry *) fcinfo->flinfo->fn_extra; if (typcache == NULL || typcache->type_id != mltrngtypid) { typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO); if (typcache->rngtype == NULL) elog(ERROR, "type %u is not a multirange type", mltrngtypid); fcinfo->flinfo->fn_extra = typcache; } return typcache; } /* * Estimate size occupied by serialized multirange. */ static Size multirange_size_estimate(TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges) { char elemalign = rangetyp->rngelemtype->typalign; Size size; int32 i; /* * Count space for MultirangeType struct, items and flags. */ size = att_align_nominal(sizeof(MultirangeType) + Max(range_count - 1, 0) * sizeof(uint32) + range_count * sizeof(uint8), elemalign); /* Count space for range bounds */ for (i = 0; i < range_count; i++) size += att_align_nominal(VARSIZE(ranges[i]) - sizeof(RangeType) - sizeof(char), elemalign); return size; } /* * Write multirange data into pre-allocated space. */ static void write_multirange_data(MultirangeType *multirange, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges) { uint32 *items; uint32 prev_offset = 0; uint8 *flags; int32 i; Pointer begin, ptr; char elemalign = rangetyp->rngelemtype->typalign; items = MultirangeGetItemsPtr(multirange); flags = MultirangeGetFlagsPtr(multirange); ptr = begin = MultirangeGetBoundariesPtr(multirange, elemalign); for (i = 0; i < range_count; i++) { uint32 len; if (i > 0) { /* * Every range, except the first one, has an item. Every * MULTIRANGE_ITEM_OFFSET_STRIDE item contains an offset, others * contain lengths. */ items[i - 1] = ptr - begin; if ((i % MULTIRANGE_ITEM_OFFSET_STRIDE) != 0) items[i - 1] -= prev_offset; else items[i - 1] |= MULTIRANGE_ITEM_OFF_BIT; prev_offset = ptr - begin; } flags[i] = *((Pointer) ranges[i] + VARSIZE(ranges[i]) - sizeof(char)); len = VARSIZE(ranges[i]) - sizeof(RangeType) - sizeof(char); memcpy(ptr, (Pointer) (ranges[i] + 1), len); ptr += att_align_nominal(len, elemalign); } } /* * This serializes the multirange from a list of non-null ranges. It also * sorts the ranges and merges any that touch. The ranges should already be * detoasted, and there should be no NULLs. This should be used by most * callers. * * Note that we may change the `ranges` parameter (the pointers, but not * any already-existing RangeType contents). */ MultirangeType * make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges) { MultirangeType *multirange; Size size; /* Sort and merge input ranges. */ range_count = multirange_canonicalize(rangetyp, range_count, ranges); /* Note: zero-fill is required here, just as in heap tuples */ size = multirange_size_estimate(rangetyp, range_count, ranges); multirange = palloc0(size); SET_VARSIZE(multirange, size); /* Now fill in the datum */ multirange->multirangetypid = mltrngtypoid; multirange->rangeCount = range_count; write_multirange_data(multirange, rangetyp, range_count, ranges); return multirange; } /* * Get offset of bounds values of the i'th range in the multirange. */ static uint32 multirange_get_bounds_offset(const MultirangeType *multirange, int32 i) { uint32 *items = MultirangeGetItemsPtr(multirange); uint32 offset = 0; /* * Summarize lengths till we meet an offset. */ while (i > 0) { offset += MULTIRANGE_ITEM_GET_OFFLEN(items[i - 1]); if (MULTIRANGE_ITEM_HAS_OFF(items[i - 1])) break; i--; } return offset; } /* * Fetch the i'th range from the multirange. */ RangeType * multirange_get_range(TypeCacheEntry *rangetyp, const MultirangeType *multirange, int i) { uint32 offset; uint8 flags; Pointer begin, ptr; int16 typlen = rangetyp->rngelemtype->typlen; char typalign = rangetyp->rngelemtype->typalign; uint32 len; RangeType *range; Assert(i < multirange->rangeCount); offset = multirange_get_bounds_offset(multirange, i); flags = MultirangeGetFlagsPtr(multirange)[i]; ptr = begin = MultirangeGetBoundariesPtr(multirange, typalign) + offset; /* * Calculate the size of bound values. In principle, we could get offset * of the next range bound values and calculate accordingly. But range * bound values are aligned, so we have to walk the values to get the * exact size. */ if (RANGE_HAS_LBOUND(flags)) ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); if (RANGE_HAS_UBOUND(flags)) { ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); } len = (ptr - begin) + sizeof(RangeType) + sizeof(uint8); range = palloc0(len); SET_VARSIZE(range, len); range->rangetypid = rangetyp->type_id; memcpy(range + 1, begin, ptr - begin); *((uint8 *) (range + 1) + (ptr - begin)) = flags; return range; } /* * Fetch bounds from the i'th range of the multirange. This is the shortcut for * doing the same thing as multirange_get_range() + range_deserialize(), but * performing fewer operations. */ void multirange_get_bounds(TypeCacheEntry *rangetyp, const MultirangeType *multirange, uint32 i, RangeBound *lower, RangeBound *upper) { uint32 offset; uint8 flags; Pointer ptr; int16 typlen = rangetyp->rngelemtype->typlen; char typalign = rangetyp->rngelemtype->typalign; bool typbyval = rangetyp->rngelemtype->typbyval; Datum lbound; Datum ubound; Assert(i < multirange->rangeCount); offset = multirange_get_bounds_offset(multirange, i); flags = MultirangeGetFlagsPtr(multirange)[i]; ptr = MultirangeGetBoundariesPtr(multirange, typalign) + offset; /* multirange can't contain empty ranges */ Assert((flags & RANGE_EMPTY) == 0); /* fetch lower bound, if any */ if (RANGE_HAS_LBOUND(flags)) { /* att_align_pointer cannot be necessary here */ lbound = fetch_att(ptr, typbyval, typlen); ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); } else lbound = (Datum) 0; /* fetch upper bound, if any */ if (RANGE_HAS_UBOUND(flags)) { ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); ubound = fetch_att(ptr, typbyval, typlen); /* no need for att_addlength_pointer */ } else ubound = (Datum) 0; /* emit results */ lower->val = lbound; lower->infinite = (flags & RANGE_LB_INF) != 0; lower->inclusive = (flags & RANGE_LB_INC) != 0; lower->lower = true; upper->val = ubound; upper->infinite = (flags & RANGE_UB_INF) != 0; upper->inclusive = (flags & RANGE_UB_INC) != 0; upper->lower = false; } /* * Construct union range from the multirange. */ RangeType * multirange_get_union_range(TypeCacheEntry *rangetyp, const MultirangeType *mr) { RangeBound lower, upper, tmp; if (MultirangeIsEmpty(mr)) return make_empty_range(rangetyp); multirange_get_bounds(rangetyp, mr, 0, &lower, &tmp); multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper); return make_range(rangetyp, &lower, &upper, false, NULL); } /* * multirange_deserialize: deconstruct a multirange value * * NB: the given multirange object must be fully detoasted; it cannot have a * short varlena header. */ void multirange_deserialize(TypeCacheEntry *rangetyp, const MultirangeType *multirange, int32 *range_count, RangeType ***ranges) { *range_count = multirange->rangeCount; /* Convert each ShortRangeType into a RangeType */ if (*range_count > 0) { int i; *ranges = palloc(*range_count * sizeof(RangeType *)); for (i = 0; i < *range_count; i++) (*ranges)[i] = multirange_get_range(rangetyp, multirange, i); } else { *ranges = NULL; } } MultirangeType * make_empty_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp) { return make_multirange(mltrngtypoid, rangetyp, 0, NULL); } /* * Similar to range_overlaps_internal(), but takes range bounds instead of * ranges as arguments. */ static bool range_bounds_overlaps(TypeCacheEntry *typcache, RangeBound *lower1, RangeBound *upper1, RangeBound *lower2, RangeBound *upper2) { if (range_cmp_bounds(typcache, lower1, lower2) >= 0 && range_cmp_bounds(typcache, lower1, upper2) <= 0) return true; if (range_cmp_bounds(typcache, lower2, lower1) >= 0 && range_cmp_bounds(typcache, lower2, upper1) <= 0) return true; return false; } /* * Similar to range_contains_internal(), but takes range bounds instead of * ranges as arguments. */ static bool range_bounds_contains(TypeCacheEntry *typcache, RangeBound *lower1, RangeBound *upper1, RangeBound *lower2, RangeBound *upper2) { if (range_cmp_bounds(typcache, lower1, lower2) <= 0 && range_cmp_bounds(typcache, upper1, upper2) >= 0) return true; return false; } /* * Check if the given key matches any range in multirange using binary search. * If the required range isn't found, that counts as a mismatch. When the * required range is found, the comparison function can still report this as * either match or mismatch. For instance, if we search for containment, we can * found a range, which is overlapping but not containing the key range, and * that would count as a mismatch. */ static bool multirange_bsearch_match(TypeCacheEntry *typcache, const MultirangeType *mr, void *key, multirange_bsearch_comparison cmp_func) { uint32 l, u, idx; int comparison; bool match = false; l = 0; u = mr->rangeCount; while (l < u) { RangeBound lower, upper; idx = (l + u) / 2; multirange_get_bounds(typcache, mr, idx, &lower, &upper); comparison = (*cmp_func) (typcache, &lower, &upper, key, &match); if (comparison < 0) u = idx; else if (comparison > 0) l = idx + 1; else return match; } return false; } /* *---------------------------------------------------------- * GENERIC FUNCTIONS *---------------------------------------------------------- */ /* * Construct multirange value from zero or more ranges. Since this is a * variadic function we get passed an array. The array must contain ranges * that match our return value, and there must be no NULLs. */ Datum multirange_constructor2(PG_FUNCTION_ARGS) { Oid mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo); Oid rngtypid; TypeCacheEntry *typcache; TypeCacheEntry *rangetyp; ArrayType *rangeArray; int range_count; Datum *elements; bool *nulls; RangeType **ranges; int dims; int i; typcache = multirange_get_typcache(fcinfo, mltrngtypid); rangetyp = typcache->rngtype; /* * A no-arg invocation should call multirange_constructor0 instead, but * returning an empty range is what that does. */ if (PG_NARGS() == 0) PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL)); /* * This check should be guaranteed by our signature, but let's do it just * in case. */ if (PG_ARGISNULL(0)) elog(ERROR, "multirange values cannot contain null members"); rangeArray = PG_GETARG_ARRAYTYPE_P(0); dims = ARR_NDIM(rangeArray); if (dims > 1) ereport(ERROR, (errcode(ERRCODE_CARDINALITY_VIOLATION), errmsg("multiranges cannot be constructed from multidimensional arrays"))); rngtypid = ARR_ELEMTYPE(rangeArray); if (rngtypid != rangetyp->type_id) elog(ERROR, "type %u does not match constructor type", rngtypid); /* * Be careful: we can still be called with zero ranges, like this: * `int4multirange(variadic '{}'::int4range[]) */ if (dims == 0) { range_count = 0; ranges = NULL; } else { deconstruct_array(rangeArray, rngtypid, rangetyp->typlen, rangetyp->typbyval, rangetyp->typalign, &elements, &nulls, &range_count); ranges = palloc0(range_count * sizeof(RangeType *)); for (i = 0; i < range_count; i++) { if (nulls[i]) ereport(ERROR, (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED), errmsg("multirange values cannot contain null members"))); /* make_multirange will do its own copy */ ranges[i] = DatumGetRangeTypeP(elements[i]); } } PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, range_count, ranges)); } /* * Construct multirange value from a single range. It'd be nice if we could * just use multirange_constructor2 for this case, but we need a non-variadic * single-arg function to let us define a CAST from a range to its multirange. */ Datum multirange_constructor1(PG_FUNCTION_ARGS) { Oid mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo); Oid rngtypid; TypeCacheEntry *typcache; TypeCacheEntry *rangetyp; RangeType *range; typcache = multirange_get_typcache(fcinfo, mltrngtypid); rangetyp = typcache->rngtype; /* * This check should be guaranteed by our signature, but let's do it just * in case. */ if (PG_ARGISNULL(0)) elog(ERROR, "multirange values cannot contain null members"); range = PG_GETARG_RANGE_P(0); /* Make sure the range type matches. */ rngtypid = RangeTypeGetOid(range); if (rngtypid != rangetyp->type_id) elog(ERROR, "type %u does not match constructor type", rngtypid); PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 1, &range)); } /* * Constructor just like multirange_constructor1, but opr_sanity gets angry * if the same internal function handles multiple functions with different arg * counts. */ Datum multirange_constructor0(PG_FUNCTION_ARGS) { Oid mltrngtypid; TypeCacheEntry *typcache; TypeCacheEntry *rangetyp; /* This should always be called without arguments */ if (PG_NARGS() != 0) elog(ERROR, "niladic multirange constructor must not receive arguments"); mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo); typcache = multirange_get_typcache(fcinfo, mltrngtypid); rangetyp = typcache->rngtype; PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL)); } /* multirange, multirange -> multirange type functions */ /* multirange union */ Datum multirange_union(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; int32 range_count1; int32 range_count2; int32 range_count3; RangeType **ranges1; RangeType **ranges2; RangeType **ranges3; if (MultirangeIsEmpty(mr1)) PG_RETURN_MULTIRANGE_P(mr2); if (MultirangeIsEmpty(mr2)) PG_RETURN_MULTIRANGE_P(mr1); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1); multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2); range_count3 = range_count1 + range_count2; ranges3 = palloc0(range_count3 * sizeof(RangeType *)); memcpy(ranges3, ranges1, range_count1 * sizeof(RangeType *)); memcpy(ranges3 + range_count1, ranges2, range_count2 * sizeof(RangeType *)); PG_RETURN_MULTIRANGE_P(make_multirange(typcache->type_id, typcache->rngtype, range_count3, ranges3)); } /* multirange minus */ Datum multirange_minus(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); Oid mltrngtypoid = MultirangeTypeGetOid(mr1); TypeCacheEntry *typcache; TypeCacheEntry *rangetyp; int32 range_count1; int32 range_count2; RangeType **ranges1; RangeType **ranges2; typcache = multirange_get_typcache(fcinfo, mltrngtypoid); rangetyp = typcache->rngtype; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) PG_RETURN_MULTIRANGE_P(mr1); multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1); multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2); PG_RETURN_MULTIRANGE_P(multirange_minus_internal(mltrngtypoid, rangetyp, range_count1, ranges1, range_count2, ranges2)); } MultirangeType * multirange_minus_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count1, RangeType **ranges1, int32 range_count2, RangeType **ranges2) { RangeType *r1; RangeType *r2; RangeType **ranges3; int32 range_count3; int32 i1; int32 i2; /* * Worst case: every range in ranges1 makes a different cut to some range * in ranges2. */ ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *)); range_count3 = 0; /* * For each range in mr1, keep subtracting until it's gone or the ranges * in mr2 have passed it. After a subtraction we assign what's left back * to r1. The parallel progress through mr1 and mr2 is similar to * multirange_overlaps_multirange_internal. */ r2 = ranges2[0]; for (i1 = 0, i2 = 0; i1 < range_count1; i1++) { r1 = ranges1[i1]; /* Discard r2s while r2 << r1 */ while (r2 != NULL && range_before_internal(rangetyp, r2, r1)) { r2 = ++i2 >= range_count2 ? NULL : ranges2[i2]; } while (r2 != NULL) { if (range_split_internal(rangetyp, r1, r2, &ranges3[range_count3], &r1)) { /* * If r2 takes a bite out of the middle of r1, we need two * outputs */ range_count3++; r2 = ++i2 >= range_count2 ? NULL : ranges2[i2]; } else if (range_overlaps_internal(rangetyp, r1, r2)) { /* * If r2 overlaps r1, replace r1 with r1 - r2. */ r1 = range_minus_internal(rangetyp, r1, r2); /* * If r2 goes past r1, then we need to stay with it, in case * it hits future r1s. Otherwise we need to keep r1, in case * future r2s hit it. Since we already subtracted, there's no * point in using the overright/overleft calls. */ if (RangeIsEmpty(r1) || range_before_internal(rangetyp, r1, r2)) break; else r2 = ++i2 >= range_count2 ? NULL : ranges2[i2]; } else { /* * This and all future r2s are past r1, so keep them. Also * assign whatever is left of r1 to the result. */ break; } } /* * Nothing else can remove anything from r1, so keep it. Even if r1 is * empty here, make_multirange will remove it. */ ranges3[range_count3++] = r1; } return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3); } /* multirange intersection */ Datum multirange_intersect(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); Oid mltrngtypoid = MultirangeTypeGetOid(mr1); TypeCacheEntry *typcache; TypeCacheEntry *rangetyp; int32 range_count1; int32 range_count2; RangeType **ranges1; RangeType **ranges2; typcache = multirange_get_typcache(fcinfo, mltrngtypoid); rangetyp = typcache->rngtype; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) PG_RETURN_MULTIRANGE_P(make_empty_multirange(mltrngtypoid, rangetyp)); multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1); multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2); PG_RETURN_MULTIRANGE_P(multirange_intersect_internal(mltrngtypoid, rangetyp, range_count1, ranges1, range_count2, ranges2)); } MultirangeType * multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count1, RangeType **ranges1, int32 range_count2, RangeType **ranges2) { RangeType *r1; RangeType *r2; RangeType **ranges3; int32 range_count3; int32 i1; int32 i2; if (range_count1 == 0 || range_count2 == 0) return make_multirange(mltrngtypoid, rangetyp, 0, NULL); /*----------------------------------------------- * Worst case is a stitching pattern like this: * * mr1: --- --- --- --- * mr2: --- --- --- * mr3: - - - - - - * * That seems to be range_count1 + range_count2 - 1, * but one extra won't hurt. *----------------------------------------------- */ ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *)); range_count3 = 0; /* * For each range in mr1, keep intersecting until the ranges in mr2 have * passed it. The parallel progress through mr1 and mr2 is similar to * multirange_minus_multirange_internal, but we don't have to assign back * to r1. */ r2 = ranges2[0]; for (i1 = 0, i2 = 0; i1 < range_count1; i1++) { r1 = ranges1[i1]; /* Discard r2s while r2 << r1 */ while (r2 != NULL && range_before_internal(rangetyp, r2, r1)) { r2 = ++i2 >= range_count2 ? NULL : ranges2[i2]; } while (r2 != NULL) { if (range_overlaps_internal(rangetyp, r1, r2)) { /* Keep the overlapping part */ ranges3[range_count3++] = range_intersect_internal(rangetyp, r1, r2); /* If we "used up" all of r2, go to the next one... */ if (range_overleft_internal(rangetyp, r2, r1)) r2 = ++i2 >= range_count2 ? NULL : ranges2[i2]; /* ...otherwise go to the next r1 */ else break; } else /* We're past r1, so move to the next one */ break; } /* If we're out of r2s, there can be no more intersections */ if (r2 == NULL) break; } return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3); } /* * range_agg_transfn: combine adjacent/overlapping ranges. * * All we do here is gather the input ranges into an array * so that the finalfn can sort and combine them. */ Datum range_agg_transfn(PG_FUNCTION_ARGS) { MemoryContext aggContext; Oid rngtypoid; ArrayBuildState *state; if (!AggCheckCallContext(fcinfo, &aggContext)) elog(ERROR, "range_agg_transfn called in non-aggregate context"); rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1); if (!type_is_range(rngtypoid)) elog(ERROR, "range_agg must be called with a range"); if (PG_ARGISNULL(0)) state = initArrayResult(rngtypoid, aggContext, false); else state = (ArrayBuildState *) PG_GETARG_POINTER(0); /* skip NULLs */ if (!PG_ARGISNULL(1)) accumArrayResult(state, PG_GETARG_DATUM(1), false, rngtypoid, aggContext); PG_RETURN_POINTER(state); } /* * range_agg_finalfn: use our internal array to merge touching ranges. * * Shared by range_agg_finalfn(anyrange) and * multirange_agg_finalfn(anymultirange). */ Datum range_agg_finalfn(PG_FUNCTION_ARGS) { MemoryContext aggContext; Oid mltrngtypoid; TypeCacheEntry *typcache; ArrayBuildState *state; int32 range_count; RangeType **ranges; int i; if (!AggCheckCallContext(fcinfo, &aggContext)) elog(ERROR, "range_agg_finalfn called in non-aggregate context"); state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0); if (state == NULL) /* This shouldn't be possible, but just in case.... */ PG_RETURN_NULL(); /* Also return NULL if we had zero inputs, like other aggregates */ range_count = state->nelems; if (range_count == 0) PG_RETURN_NULL(); mltrngtypoid = get_fn_expr_rettype(fcinfo->flinfo); typcache = multirange_get_typcache(fcinfo, mltrngtypoid); ranges = palloc0(range_count * sizeof(RangeType *)); for (i = 0; i < range_count; i++) ranges[i] = DatumGetRangeTypeP(state->dvalues[i]); PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypoid, typcache->rngtype, range_count, ranges)); } /* * multirange_agg_transfn: combine adjacent/overlapping multiranges. * * All we do here is gather the input multiranges' ranges into an array so * that the finalfn can sort and combine them. */ Datum multirange_agg_transfn(PG_FUNCTION_ARGS) { MemoryContext aggContext; Oid mltrngtypoid; TypeCacheEntry *typcache; TypeCacheEntry *rngtypcache; ArrayBuildState *state; if (!AggCheckCallContext(fcinfo, &aggContext)) elog(ERROR, "multirange_agg_transfn called in non-aggregate context"); mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1); if (!type_is_multirange(mltrngtypoid)) elog(ERROR, "range_agg must be called with a multirange"); typcache = multirange_get_typcache(fcinfo, mltrngtypoid); rngtypcache = typcache->rngtype; if (PG_ARGISNULL(0)) state = initArrayResult(rngtypcache->type_id, aggContext, false); else state = (ArrayBuildState *) PG_GETARG_POINTER(0); /* skip NULLs */ if (!PG_ARGISNULL(1)) { MultirangeType *current; int32 range_count; RangeType **ranges; current = PG_GETARG_MULTIRANGE_P(1); multirange_deserialize(rngtypcache, current, &range_count, &ranges); if (range_count == 0) { /* * Add an empty range so we get an empty result (not a null * result). */ accumArrayResult(state, RangeTypePGetDatum(make_empty_range(rngtypcache)), false, rngtypcache->type_id, aggContext); } else { for (int32 i = 0; i < range_count; i++) accumArrayResult(state, RangeTypePGetDatum(ranges[i]), false, rngtypcache->type_id, aggContext); } } PG_RETURN_POINTER(state); } Datum multirange_intersect_agg_transfn(PG_FUNCTION_ARGS) { MemoryContext aggContext; Oid mltrngtypoid; TypeCacheEntry *typcache; MultirangeType *result; MultirangeType *current; int32 range_count1; int32 range_count2; RangeType **ranges1; RangeType **ranges2; if (!AggCheckCallContext(fcinfo, &aggContext)) elog(ERROR, "multirange_intersect_agg_transfn called in non-aggregate context"); mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1); if (!type_is_multirange(mltrngtypoid)) elog(ERROR, "range_intersect_agg must be called with a multirange"); typcache = multirange_get_typcache(fcinfo, mltrngtypoid); /* strictness ensures these are non-null */ result = PG_GETARG_MULTIRANGE_P(0); current = PG_GETARG_MULTIRANGE_P(1); multirange_deserialize(typcache->rngtype, result, &range_count1, &ranges1); multirange_deserialize(typcache->rngtype, current, &range_count2, &ranges2); result = multirange_intersect_internal(mltrngtypoid, typcache->rngtype, range_count1, ranges1, range_count2, ranges2); PG_RETURN_MULTIRANGE_P(result); } /* multirange -> element type functions */ /* extract lower bound value */ Datum multirange_lower(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_NULL(); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, 0, &lower, &upper); if (!lower.infinite) PG_RETURN_DATUM(lower.val); else PG_RETURN_NULL(); } /* extract upper bound value */ Datum multirange_upper(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_NULL(); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1, &lower, &upper); if (!upper.infinite) PG_RETURN_DATUM(upper.val); else PG_RETURN_NULL(); } /* multirange -> bool functions */ /* is multirange empty? */ Datum multirange_empty(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); PG_RETURN_BOOL(MultirangeIsEmpty(mr)); } /* is lower bound inclusive? */ Datum multirange_lower_inc(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, 0, &lower, &upper); PG_RETURN_BOOL(lower.inclusive); } /* is upper bound inclusive? */ Datum multirange_upper_inc(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1, &lower, &upper); PG_RETURN_BOOL(upper.inclusive); } /* is lower bound infinite? */ Datum multirange_lower_inf(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, 0, &lower, &upper); PG_RETURN_BOOL(lower.infinite); } /* is upper bound infinite? */ Datum multirange_upper_inf(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); TypeCacheEntry *typcache; RangeBound lower; RangeBound upper; if (MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1, &lower, &upper); PG_RETURN_BOOL(upper.infinite); } /* multirange, element -> bool functions */ /* contains? */ Datum multirange_contains_elem(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); Datum val = PG_GETARG_DATUM(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val)); } /* contained by? */ Datum elem_contained_by_multirange(PG_FUNCTION_ARGS) { Datum val = PG_GETARG_DATUM(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(multirange_contains_elem_internal(typcache->rngtype, mr, val)); } /* * Comparison function for checking if any range of multirange contains given * key element using binary search. */ static int multirange_elem_bsearch_comparison(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, void *key, bool *match) { Datum val = *((Datum *) key); int cmp; if (!lower->infinite) { cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, typcache->rng_collation, lower->val, val)); if (cmp > 0 || (cmp == 0 && !lower->inclusive)) return -1; } if (!upper->infinite) { cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, typcache->rng_collation, upper->val, val)); if (cmp < 0 || (cmp == 0 && !upper->inclusive)) return 1; } *match = true; return 0; } /* * Test whether multirange mr contains a specific element value. */ bool multirange_contains_elem_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr, Datum val) { if (MultirangeIsEmpty(mr)) return false; return multirange_bsearch_match(rangetyp, mr, &val, multirange_elem_bsearch_comparison); } /* multirange, range -> bool functions */ /* contains? */ Datum multirange_contains_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r)); } Datum range_contains_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr)); } /* contained by? */ Datum range_contained_by_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(multirange_contains_range_internal(typcache->rngtype, mr, r)); } Datum multirange_contained_by_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_contains_multirange_internal(typcache->rngtype, r, mr)); } /* * Comparison function for checking if any range of multirange contains given * key range using binary search. */ static int multirange_range_contains_bsearch_comparison(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, void *key, bool *match) { RangeBound *keyLower = (RangeBound *) key; RangeBound *keyUpper = (RangeBound *) key + 1; /* Check if key range is strictly in the left or in the right */ if (range_cmp_bounds(typcache, keyUpper, lower) < 0) return -1; if (range_cmp_bounds(typcache, keyLower, upper) > 0) return 1; /* * At this point we found overlapping range. But we have to check if it * really contains the key range. Anyway, we have to stop our search * here, because multirange contains only non-overlapping ranges. */ *match = range_bounds_contains(typcache, lower, upper, keyLower, keyUpper); return 0; } /* * Test whether multirange mr contains a specific range r. */ bool multirange_contains_range_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr, const RangeType *r) { RangeBound bounds[2]; bool empty; /* * Every multirange contains an infinite number of empty ranges, even an * empty one. */ if (RangeIsEmpty(r)) return true; if (MultirangeIsEmpty(mr)) return false; range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty); Assert(!empty); return multirange_bsearch_match(rangetyp, mr, bounds, multirange_range_contains_bsearch_comparison); } /* * Test whether range r contains a multirange mr. */ bool range_contains_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2, tmp; bool empty; /* * Every range contains an infinite number of empty multiranges, even an * empty one. */ if (MultirangeIsEmpty(mr)) return true; if (RangeIsEmpty(r)) return false; /* Range contains multirange iff it contains its union range. */ range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); multirange_get_bounds(rangetyp, mr, 0, &lower2, &tmp); multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &tmp, &upper2); return range_bounds_contains(rangetyp, &lower1, &upper1, &lower2, &upper2); } /* multirange, multirange -> bool functions */ /* equality (internal version) */ bool multirange_eq_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2) { int32 range_count_1; int32 range_count_2; int32 i; RangeBound lower1, upper1, lower2, upper2; /* Different types should be prevented by ANYMULTIRANGE matching rules */ if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2)) elog(ERROR, "multirange types do not match"); range_count_1 = mr1->rangeCount; range_count_2 = mr2->rangeCount; if (range_count_1 != range_count_2) return false; for (i = 0; i < range_count_1; i++) { multirange_get_bounds(rangetyp, mr1, i, &lower1, &upper1); multirange_get_bounds(rangetyp, mr2, i, &lower2, &upper2); if (range_cmp_bounds(rangetyp, &lower1, &lower2) != 0 || range_cmp_bounds(rangetyp, &upper1, &upper2) != 0) return false; } return true; } /* equality */ Datum multirange_eq(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_eq_internal(typcache->rngtype, mr1, mr2)); } /* inequality (internal version) */ bool multirange_ne_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2) { return (!multirange_eq_internal(rangetyp, mr1, mr2)); } /* inequality */ Datum multirange_ne(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_ne_internal(typcache->rngtype, mr1, mr2)); } /* overlaps? */ Datum range_overlaps_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_overlaps_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_overlaps_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_overlaps_multirange_internal(typcache->rngtype, mr1, mr2)); } /* * Comparison function for checking if any range of multirange overlaps given * key range using binary search. */ static int multirange_range_overlaps_bsearch_comparison(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, void *key, bool *match) { RangeBound *keyLower = (RangeBound *) key; RangeBound *keyUpper = (RangeBound *) key + 1; if (range_cmp_bounds(typcache, keyUpper, lower) < 0) return -1; if (range_cmp_bounds(typcache, keyLower, upper) > 0) return 1; *match = true; return 0; } bool range_overlaps_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound bounds[2]; bool empty; /* * Empties never overlap, even with empties. (This seems strange since * they *do* contain each other, but we want to follow how ranges work.) */ if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) return false; range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty); Assert(!empty); return multirange_bsearch_match(rangetyp, mr, bounds, multirange_range_overlaps_bsearch_comparison); } bool multirange_overlaps_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2) { int32 range_count1; int32 range_count2; int32 i1; int32 i2; RangeBound lower1, upper1, lower2, upper2; /* * Empties never overlap, even with empties. (This seems strange since * they *do* contain each other, but we want to follow how ranges work.) */ if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) return false; range_count1 = mr1->rangeCount; range_count2 = mr2->rangeCount; /* * Every range in mr1 gets a chance to overlap with the ranges in mr2, but * we can use their ordering to avoid O(n^2). This is similar to * range_overlaps_multirange where r1 : r2 :: mrr : r, but there if we * don't find an overlap with r we're done, and here if we don't find an * overlap with r2 we try the next r2. */ i1 = 0; multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1); for (i1 = 0, i2 = 0; i2 < range_count2; i2++) { multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2); /* Discard r1s while r1 << r2 */ while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0) { if (++i1 >= range_count1) return false; multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1); } /* * If r1 && r2, we're done, otherwise we failed to find an overlap for * r2, so go to the next one. */ if (range_bounds_overlaps(rangetyp, &lower1, &upper1, &lower2, &upper2)) return true; } /* We looked through all of mr2 without finding an overlap */ return false; } /* does not extend to right of? */ bool range_overleft_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2; bool empty; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); multirange_get_bounds(rangetyp, mr, mr->rangeCount - 1, &lower2, &upper2); PG_RETURN_BOOL(range_cmp_bounds(rangetyp, &upper1, &upper2) <= 0); } Datum range_overleft_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_overleft_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_overleft_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; RangeBound lower1, upper1, lower2, upper2; bool empty; if (MultirangeIsEmpty(mr) || RangeIsEmpty(r)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1, &lower1, &upper1); range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty); Assert(!empty); PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0); } Datum multirange_overleft_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; RangeBound lower1, upper1, lower2, upper2; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1, &lower1, &upper1); multirange_get_bounds(typcache->rngtype, mr2, mr2->rangeCount - 1, &lower2, &upper2); PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0); } /* does not extend to left of? */ bool range_overright_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2; bool empty; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) PG_RETURN_BOOL(false); range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2); return (range_cmp_bounds(rangetyp, &lower1, &lower2) >= 0); } Datum range_overright_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_overright_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_overright_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; RangeBound lower1, upper1, lower2, upper2; bool empty; if (MultirangeIsEmpty(mr) || RangeIsEmpty(r)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); multirange_get_bounds(typcache->rngtype, mr, 0, &lower1, &upper1); range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty); Assert(!empty); PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0); } Datum multirange_overright_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; RangeBound lower1, upper1, lower2, upper2; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) PG_RETURN_BOOL(false); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1); multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2); PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0); } /* contains? */ Datum multirange_contains_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr1, mr2)); } /* contained by? */ Datum multirange_contained_by_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache->rngtype, mr2, mr1)); } /* * Test whether multirange mr1 contains every range from another multirange mr2. */ bool multirange_contains_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2) { int32 range_count1 = mr1->rangeCount; int32 range_count2 = mr2->rangeCount; int i1, i2; RangeBound lower1, upper1, lower2, upper2; /* * We follow the same logic for empties as ranges: - an empty multirange * contains an empty range/multirange. - an empty multirange can't contain * any other range/multirange. - an empty multirange is contained by any * other range/multirange. */ if (range_count2 == 0) return true; if (range_count1 == 0) return false; /* * Every range in mr2 must be contained by some range in mr1. To avoid * O(n^2) we walk through both ranges in tandem. */ i1 = 0; multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1); for (i2 = 0; i2 < range_count2; i2++) { multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2); /* Discard r1s while r1 << r2 */ while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0) { if (++i1 >= range_count1) return false; multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1); } /* * If r1 @> r2, go to the next r2, otherwise return false (since every * r1[n] and r1[n+1] must have a gap). Note this will give weird * answers if you don't canonicalize, e.g. with a custom * int2multirange {[1,1], [2,2]} there is a "gap". But that is * consistent with other range operators, e.g. '[1,1]'::int2range -|- * '[2,2]'::int2range is false. */ if (!range_bounds_contains(rangetyp, &lower1, &upper1, &lower2, &upper2)) return false; } /* All ranges in mr2 are satisfied */ return true; } /* strictly left of? */ Datum range_before_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_before_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_before_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr1, mr2)); } /* strictly right of? */ Datum range_after_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_after_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_after_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_before_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_after_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); PG_RETURN_BOOL(multirange_before_multirange_internal(typcache->rngtype, mr2, mr1)); } /* strictly left of? (internal version) */ bool range_before_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2; bool empty; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) return false; range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2); return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0); } bool multirange_before_multirange_internal(TypeCacheEntry *rangetyp, const MultirangeType *mr1, const MultirangeType *mr2) { RangeBound lower1, upper1, lower2, upper2; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) return false; multirange_get_bounds(rangetyp, mr1, mr1->rangeCount - 1, &lower1, &upper1); multirange_get_bounds(rangetyp, mr2, 0, &lower2, &upper2); return (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0); } /* strictly right of? (internal version) */ bool range_after_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2; bool empty; int32 range_count; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) return false; range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); range_count = mr->rangeCount; multirange_get_bounds(rangetyp, mr, range_count - 1, &lower2, &upper2); return (range_cmp_bounds(rangetyp, &lower1, &upper2) > 0); } bool range_adjacent_multirange_internal(TypeCacheEntry *rangetyp, const RangeType *r, const MultirangeType *mr) { RangeBound lower1, upper1, lower2, upper2; bool empty; int32 range_count; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) return false; range_deserialize(rangetyp, r, &lower1, &upper1, &empty); Assert(!empty); range_count = mr->rangeCount; multirange_get_bounds(rangetyp, mr, 0, &lower2, &upper2); if (bounds_adjacent(rangetyp, upper1, lower2)) return true; if (range_count > 1) multirange_get_bounds(rangetyp, mr, range_count - 1, &lower2, &upper2); if (bounds_adjacent(rangetyp, upper2, lower1)) return true; return false; } /* adjacent to? */ Datum range_adjacent_multirange(PG_FUNCTION_ARGS) { RangeType *r = PG_GETARG_RANGE_P(0); MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_adjacent_range(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); RangeType *r = PG_GETARG_RANGE_P(1); TypeCacheEntry *typcache; if (RangeIsEmpty(r) || MultirangeIsEmpty(mr)) return false; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache->rngtype, r, mr)); } Datum multirange_adjacent_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); TypeCacheEntry *typcache; int32 range_count1; int32 range_count2; RangeBound lower1, upper1, lower2, upper2; if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2)) return false; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); range_count1 = mr1->rangeCount; range_count2 = mr2->rangeCount; multirange_get_bounds(typcache->rngtype, mr1, range_count1 - 1, &lower1, &upper1); multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2); if (bounds_adjacent(typcache->rngtype, upper1, lower2)) PG_RETURN_BOOL(true); if (range_count1 > 1) multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1); if (range_count2 > 1) multirange_get_bounds(typcache->rngtype, mr2, range_count2 - 1, &lower2, &upper2); if (bounds_adjacent(typcache->rngtype, upper2, lower1)) PG_RETURN_BOOL(true); PG_RETURN_BOOL(false); } /* Btree support */ /* btree comparator */ Datum multirange_cmp(PG_FUNCTION_ARGS) { MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0); MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1); int32 range_count_1; int32 range_count_2; int32 range_count_max; int32 i; TypeCacheEntry *typcache; int cmp = 0; /* If both are empty we'll use this. */ /* Different types should be prevented by ANYMULTIRANGE matching rules */ if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2)) elog(ERROR, "multirange types do not match"); typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1)); range_count_1 = mr1->rangeCount; range_count_2 = mr2->rangeCount; /* Loop over source data */ range_count_max = Max(range_count_1, range_count_2); for (i = 0; i < range_count_max; i++) { RangeBound lower1, upper1, lower2, upper2; /* * If one multirange is shorter, it's as if it had empty ranges at the * end to extend its length. An empty range compares earlier than any * other range, so the shorter multirange comes before the longer. * This is the same behavior as in other types, e.g. in strings 'aaa' * < 'aaaaaa'. */ if (i >= range_count_1) { cmp = -1; break; } if (i >= range_count_2) { cmp = 1; break; } multirange_get_bounds(typcache->rngtype, mr1, i, &lower1, &upper1); multirange_get_bounds(typcache->rngtype, mr2, i, &lower2, &upper2); cmp = range_cmp_bounds(typcache->rngtype, &lower1, &lower2); if (cmp == 0) cmp = range_cmp_bounds(typcache->rngtype, &upper1, &upper2); if (cmp != 0) break; } PG_FREE_IF_COPY(mr1, 0); PG_FREE_IF_COPY(mr2, 1); PG_RETURN_INT32(cmp); } /* inequality operators using the multirange_cmp function */ Datum multirange_lt(PG_FUNCTION_ARGS) { int cmp = multirange_cmp(fcinfo); PG_RETURN_BOOL(cmp < 0); } Datum multirange_le(PG_FUNCTION_ARGS) { int cmp = multirange_cmp(fcinfo); PG_RETURN_BOOL(cmp <= 0); } Datum multirange_ge(PG_FUNCTION_ARGS) { int cmp = multirange_cmp(fcinfo); PG_RETURN_BOOL(cmp >= 0); } Datum multirange_gt(PG_FUNCTION_ARGS) { int cmp = multirange_cmp(fcinfo); PG_RETURN_BOOL(cmp > 0); } /* multirange -> range functions */ /* Find the smallest range that includes everything in the multirange */ Datum range_merge_from_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); Oid mltrngtypoid = MultirangeTypeGetOid(mr); TypeCacheEntry *typcache; RangeType *result; typcache = multirange_get_typcache(fcinfo, mltrngtypoid); if (MultirangeIsEmpty(mr)) { result = make_empty_range(typcache->rngtype); } else if (mr->rangeCount == 1) { result = multirange_get_range(typcache->rngtype, mr, 0); } else { RangeBound firstLower, firstUpper, lastLower, lastUpper; multirange_get_bounds(typcache->rngtype, mr, 0, &firstLower, &firstUpper); multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1, &lastLower, &lastUpper); result = make_range(typcache->rngtype, &firstLower, &lastUpper, false, NULL); } PG_RETURN_RANGE_P(result); } /* Turn multirange into a set of ranges */ Datum multirange_unnest(PG_FUNCTION_ARGS) { typedef struct { MultirangeType *mr; TypeCacheEntry *typcache; int index; } multirange_unnest_fctx; FuncCallContext *funcctx; multirange_unnest_fctx *fctx; MemoryContext oldcontext; /* stuff done only on the first call of the function */ if (SRF_IS_FIRSTCALL()) { MultirangeType *mr; /* create a function context for cross-call persistence */ funcctx = SRF_FIRSTCALL_INIT(); /* * switch to memory context appropriate for multiple function calls */ oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx); /* * Get the multirange value and detoast if needed. We can't do this * earlier because if we have to detoast, we want the detoasted copy * to be in multi_call_memory_ctx, so it will go away when we're done * and not before. (If no detoast happens, we assume the originally * passed multirange will stick around till then.) */ mr = PG_GETARG_MULTIRANGE_P(0); /* allocate memory for user context */ fctx = (multirange_unnest_fctx *) palloc(sizeof(multirange_unnest_fctx)); /* initialize state */ fctx->mr = mr; fctx->index = 0; fctx->typcache = lookup_type_cache(MultirangeTypeGetOid(mr), TYPECACHE_MULTIRANGE_INFO); funcctx->user_fctx = fctx; MemoryContextSwitchTo(oldcontext); } /* stuff done on every call of the function */ funcctx = SRF_PERCALL_SETUP(); fctx = funcctx->user_fctx; if (fctx->index < fctx->mr->rangeCount) { RangeType *range; range = multirange_get_range(fctx->typcache->rngtype, fctx->mr, fctx->index); fctx->index++; SRF_RETURN_NEXT(funcctx, RangeTypePGetDatum(range)); } else { /* do when there is no more left */ SRF_RETURN_DONE(funcctx); } } /* Hash support */ /* hash a multirange value */ Datum hash_multirange(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); uint32 result = 1; TypeCacheEntry *typcache, *scache; int32 range_count, i; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); scache = typcache->rngtype->rngelemtype; if (!OidIsValid(scache->hash_proc_finfo.fn_oid)) { scache = lookup_type_cache(scache->type_id, TYPECACHE_HASH_PROC_FINFO); if (!OidIsValid(scache->hash_proc_finfo.fn_oid)) ereport(ERROR, (errcode(ERRCODE_UNDEFINED_FUNCTION), errmsg("could not identify a hash function for type %s", format_type_be(scache->type_id)))); } range_count = mr->rangeCount; for (i = 0; i < range_count; i++) { RangeBound lower, upper; uint8 flags = MultirangeGetFlagsPtr(mr)[i]; uint32 lower_hash; uint32 upper_hash; uint32 range_hash; multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper); if (RANGE_HAS_LBOUND(flags)) lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo, typcache->rngtype->rng_collation, lower.val)); else lower_hash = 0; if (RANGE_HAS_UBOUND(flags)) upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo, typcache->rngtype->rng_collation, upper.val)); else upper_hash = 0; /* Merge hashes of flags and bounds */ range_hash = hash_uint32((uint32) flags); range_hash ^= lower_hash; range_hash = pg_rotate_left32(range_hash, 1); range_hash ^= upper_hash; /* * Use the same approach as hash_array to combine the individual * elements' hash values: */ result = (result << 5) - result + range_hash; } PG_FREE_IF_COPY(mr, 0); PG_RETURN_UINT32(result); } /* * Returns 64-bit value by hashing a value to a 64-bit value, with a seed. * Otherwise, similar to hash_multirange. */ Datum hash_multirange_extended(PG_FUNCTION_ARGS) { MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0); Datum seed = PG_GETARG_DATUM(1); uint64 result = 1; TypeCacheEntry *typcache, *scache; int32 range_count, i; typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr)); scache = typcache->rngtype->rngelemtype; if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid)) { scache = lookup_type_cache(scache->type_id, TYPECACHE_HASH_EXTENDED_PROC_FINFO); if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid)) ereport(ERROR, (errcode(ERRCODE_UNDEFINED_FUNCTION), errmsg("could not identify a hash function for type %s", format_type_be(scache->type_id)))); } range_count = mr->rangeCount; for (i = 0; i < range_count; i++) { RangeBound lower, upper; uint8 flags = MultirangeGetFlagsPtr(mr)[i]; uint64 lower_hash; uint64 upper_hash; uint64 range_hash; multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper); if (RANGE_HAS_LBOUND(flags)) lower_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo, typcache->rngtype->rng_collation, lower.val, seed)); else lower_hash = 0; if (RANGE_HAS_UBOUND(flags)) upper_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo, typcache->rngtype->rng_collation, upper.val, seed)); else upper_hash = 0; /* Merge hashes of flags and bounds */ range_hash = DatumGetUInt64(hash_uint32_extended((uint32) flags, DatumGetInt64(seed))); range_hash ^= lower_hash; range_hash = ROTATE_HIGH_AND_LOW_32BITS(range_hash); range_hash ^= upper_hash; /* * Use the same approach as hash_array to combine the individual * elements' hash values: */ result = (result << 5) - result + range_hash; } PG_FREE_IF_COPY(mr, 0); PG_RETURN_UINT64(result); }