#include "utils/rangetypes.h"
#include "utils/typcache.h"

Include dependency graph for multirangetypes.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	MultirangeType

Macros
#define	MultirangeTypeGetOid(mr) ((mr)->multirangetypid)

#define	MultirangeIsEmpty(mr) ((mr)->rangeCount == 0)

#define	PG_GETARG_MULTIRANGE_P(n) DatumGetMultirangeTypeP(PG_GETARG_DATUM(n))

#define	PG_GETARG_MULTIRANGE_P_COPY(n) DatumGetMultirangeTypePCopy(PG_GETARG_DATUM(n))

#define	PG_RETURN_MULTIRANGE_P(x) return MultirangeTypePGetDatum(x)

Functions
static MultirangeType *	DatumGetMultirangeTypeP (Datum X)

static MultirangeType *	DatumGetMultirangeTypePCopy (Datum X)

static Datum	MultirangeTypePGetDatum (const MultirangeType *X)

bool	multirange_eq_internal (TypeCacheEntry rangetyp, const MultirangeType mr1, const MultirangeType *mr2)

bool	multirange_ne_internal (TypeCacheEntry rangetyp, const MultirangeType mr1, const MultirangeType *mr2)

bool	multirange_contains_elem_internal (TypeCacheEntry rangetyp, const MultirangeType mr, Datum val)

bool	multirange_contains_range_internal (TypeCacheEntry rangetyp, const MultirangeType mr, const RangeType *r)

bool	range_contains_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	multirange_contains_multirange_internal (TypeCacheEntry rangetyp, const MultirangeType mr1, const MultirangeType *mr2)

bool	range_overlaps_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	multirange_overlaps_multirange_internal (TypeCacheEntry rangetyp, const MultirangeType mr1, const MultirangeType *mr2)

bool	range_overleft_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	range_overright_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	range_before_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	range_after_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	range_adjacent_multirange_internal (TypeCacheEntry rangetyp, const RangeType r, const MultirangeType *mr)

bool	multirange_before_multirange_internal (TypeCacheEntry rangetyp, const MultirangeType mr1, const MultirangeType *mr2)

MultirangeType *	multirange_minus_internal (Oid mltrngtypoid, TypeCacheEntry rangetyp, int32 range_count1, RangeType ranges1, int32 range_count2, RangeType *ranges2)

MultirangeType *	multirange_intersect_internal (Oid mltrngtypoid, TypeCacheEntry rangetyp, int32 range_count1, RangeType ranges1, int32 range_count2, RangeType *ranges2)

TypeCacheEntry *	multirange_get_typcache (FunctionCallInfo fcinfo, Oid mltrngtypid)

void	multirange_deserialize (TypeCacheEntry rangetyp, const MultirangeType multirange, int32 range_count, RangeType **ranges)

MultirangeType *	make_multirange (Oid mltrngtypoid, TypeCacheEntry rangetyp, int32 range_count, RangeType *ranges)

MultirangeType *	make_empty_multirange (Oid mltrngtypoid, TypeCacheEntry *rangetyp)

void	multirange_get_bounds (TypeCacheEntry rangetyp, const MultirangeType multirange, uint32 i, RangeBound lower, RangeBound upper)

RangeType *	multirange_get_range (TypeCacheEntry rangetyp, const MultirangeType multirange, int i)

RangeType *	multirange_get_union_range (TypeCacheEntry rangetyp, const MultirangeType mr)

Macro Definition Documentation

◆ MultirangeIsEmpty

#define MultirangeIsEmpty ( mr ) ((mr)->rangeCount == 0)

Definition at line 42 of file multirangetypes.h.

◆ MultirangeTypeGetOid

#define MultirangeTypeGetOid ( mr ) ((mr)->multirangetypid)

Definition at line 41 of file multirangetypes.h.

◆ PG_GETARG_MULTIRANGE_P

#define PG_GETARG_MULTIRANGE_P ( n ) DatumGetMultirangeTypeP(PG_GETARG_DATUM(n))

Definition at line 65 of file multirangetypes.h.

◆ PG_GETARG_MULTIRANGE_P_COPY

#define PG_GETARG_MULTIRANGE_P_COPY ( n ) DatumGetMultirangeTypePCopy(PG_GETARG_DATUM(n))

Definition at line 66 of file multirangetypes.h.

◆ PG_RETURN_MULTIRANGE_P

#define PG_RETURN_MULTIRANGE_P ( x ) return MultirangeTypePGetDatum(x)

Definition at line 67 of file multirangetypes.h.

Function Documentation

◆ DatumGetMultirangeTypeP()

static MultirangeType * DatumGetMultirangeTypeP ( Datum X )

inlinestatic

Definition at line 48 of file multirangetypes.h.

{
    return (MultirangeType *) PG_DETOAST_DATUM(X);
}

References PG_DETOAST_DATUM.

Referenced by compute_range_stats(), ExecWithoutOverlapsNotEmpty(), multirange_gist_compress(), multirange_gist_consistent(), multirangesel(), and range_gist_consistent().

◆ DatumGetMultirangeTypePCopy()

static MultirangeType * DatumGetMultirangeTypePCopy ( Datum X )

inlinestatic

Definition at line 54 of file multirangetypes.h.

{
    return (MultirangeType *) PG_DETOAST_DATUM_COPY(X);
}

References PG_DETOAST_DATUM_COPY.

◆ make_empty_multirange()

MultirangeType * make_empty_multirange	(	Oid	mltrngtypoid,
		TypeCacheEntry *	rangetyp
	)

Definition at line 850 of file multirangetypes.c.

{
    return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
}

References make_multirange().

Referenced by multirange_intersect().

◆ make_multirange()

MultirangeType * make_multirange	(	Oid	mltrngtypoid,
		TypeCacheEntry *	rangetyp,
		int32	range_count,
		RangeType **	ranges
	)

Definition at line 648 of file multirangetypes.c.

{
    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;
}

References multirange_canonicalize(), multirange_size_estimate(), MultirangeType::multirangetypid, palloc0(), MultirangeType::rangeCount, SET_VARSIZE(), and write_multirange_data().

Referenced by make_empty_multirange(), multirange_constructor0(), multirange_constructor1(), multirange_constructor2(), multirange_in(), multirange_intersect_internal(), multirange_minus_internal(), multirange_recv(), multirange_union(), multirangesel(), and range_agg_finalfn().

◆ multirange_before_multirange_internal()

bool multirange_before_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr1,
		const MultirangeType *	mr2
	)

Definition at line 2425 of file multirangetypes.c.

{
    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);
}

References multirange_get_bounds(), MultirangeIsEmpty, range_cmp_bounds(), and MultirangeType::rangeCount.

Referenced by multirange_after_multirange(), and multirange_before_multirange().

◆ multirange_contains_elem_internal()

bool multirange_contains_elem_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr,
		Datum	val
	)

Definition at line 1709 of file multirangetypes.c.

{
    if (MultirangeIsEmpty(mr))
        return false;
 
    return multirange_bsearch_match(rangetyp, mr, &val,
                                    multirange_elem_bsearch_comparison);
}

References multirange_bsearch_match(), multirange_elem_bsearch_comparison(), MultirangeIsEmpty, and val.

Referenced by elem_contained_by_multirange(), and multirange_contains_elem().

◆ multirange_contains_multirange_internal()

bool multirange_contains_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr1,
		const MultirangeType *	mr2
	)

Definition at line 2267 of file multirangetypes.c.

{
    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;
}

References multirange_get_bounds(), range_bounds_contains(), range_cmp_bounds(), and MultirangeType::rangeCount.

Referenced by multirange_contained_by_multirange(), and multirange_contains_multirange().

◆ multirange_contains_range_internal()

bool multirange_contains_range_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr,
		const RangeType *	r
	)

Definition at line 1803 of file multirangetypes.c.

{
    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);
}

References Assert(), multirange_bsearch_match(), multirange_range_contains_bsearch_comparison(), MultirangeIsEmpty, range_deserialize(), and RangeIsEmpty.

Referenced by multirange_contains_range(), range_contained_by_multirange(), and range_gist_consistent_leaf_multirange().

◆ multirange_deserialize()

void multirange_deserialize	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	multirange,
		int32 *	range_count,
		RangeType ***	ranges
	)

Definition at line 828 of file multirangetypes.c.

{
    *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;
    }
}

References i, multirange_get_range(), palloc(), and MultirangeType::rangeCount.

Referenced by multirange_agg_transfn(), multirange_intersect(), multirange_intersect_agg_transfn(), multirange_minus(), multirange_out(), multirange_send(), and multirange_union().

◆ multirange_eq_internal()

bool multirange_eq_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr1,
		const MultirangeType *	mr2
	)

Definition at line 1866 of file multirangetypes.c.

{
    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;
}

References elog, ERROR, i, multirange_get_bounds(), MultirangeTypeGetOid, range_cmp_bounds(), and MultirangeType::rangeCount.

Referenced by multirange_eq(), and multirange_ne_internal().

◆ multirange_get_bounds()

void multirange_get_bounds	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	multirange,
		uint32	i,
		RangeBound *	lower,
		RangeBound *	upper
	)

Definition at line 746 of file multirangetypes.c.

{
    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;
}

References Assert(), att_addlength_pointer, att_align_pointer, fetch_att(), i, lower(), multirange_get_bounds_offset(), MultirangeGetBoundariesPtr, MultirangeGetFlagsPtr, RANGE_EMPTY, RANGE_HAS_LBOUND, RANGE_HAS_UBOUND, RANGE_LB_INC, RANGE_LB_INF, RANGE_UB_INC, RANGE_UB_INF, TypeCacheEntry::rngelemtype, typalign, TypeCacheEntry::typalign, TypeCacheEntry::typbyval, TypeCacheEntry::typlen, and upper().

Referenced by calc_hist_selectivity(), compute_range_stats(), hash_multirange(), hash_multirange_extended(), multirange_adjacent_multirange(), multirange_before_multirange_internal(), multirange_bsearch_match(), multirange_cmp(), multirange_contains_multirange_internal(), multirange_eq_internal(), multirange_get_union_range(), multirange_lower(), multirange_lower_inc(), multirange_lower_inf(), multirange_overlaps_multirange_internal(), multirange_overleft_multirange(), multirange_overleft_range(), multirange_overright_multirange(), multirange_overright_range(), multirange_union_range_equal(), multirange_upper(), multirange_upper_inc(), multirange_upper_inf(), range_adjacent_multirange_internal(), range_after_multirange_internal(), range_before_multirange_internal(), range_contains_multirange_internal(), range_merge_from_multirange(), range_overleft_multirange_internal(), and range_overright_multirange_internal().

◆ multirange_get_range()

RangeType * multirange_get_range	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	multirange,
		int	i
	)

Definition at line 697 of file multirangetypes.c.

{
    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;
}

References Assert(), att_addlength_pointer, att_align_pointer, i, len, multirange_get_bounds_offset(), MultirangeGetBoundariesPtr, MultirangeGetFlagsPtr, palloc0(), range(), RANGE_HAS_LBOUND, RANGE_HAS_UBOUND, TypeCacheEntry::rngelemtype, SET_VARSIZE(), typalign, TypeCacheEntry::typalign, TypeCacheEntry::type_id, and TypeCacheEntry::typlen.

Referenced by multirange_deserialize(), multirange_unnest(), and range_merge_from_multirange().

◆ multirange_get_typcache()

TypeCacheEntry * multirange_get_typcache	(	FunctionCallInfo	fcinfo,
		Oid	mltrngtypid
	)

Definition at line 550 of file multirangetypes.c.

{
    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;
}

References elog, ERROR, FunctionCallInfoBaseData::flinfo, FmgrInfo::fn_extra, if(), lookup_type_cache(), TypeCacheEntry::rngtype, TypeCacheEntry::type_id, and TYPECACHE_MULTIRANGE_INFO.

◆ multirange_get_union_range()

RangeType * multirange_get_union_range	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr
	)

Definition at line 804 of file multirangetypes.c.

{
    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);
}

References lower(), make_empty_range(), make_range(), multirange_get_bounds(), MultirangeIsEmpty, MultirangeType::rangeCount, and upper().

Referenced by multirange_gist_compress().

◆ multirange_intersect_internal()

MultirangeType * multirange_intersect_internal	(	Oid	mltrngtypoid,
		TypeCacheEntry *	rangetyp,
		int32	range_count1,
		RangeType **	ranges1,
		int32	range_count2,
		RangeType **	ranges2
	)

Definition at line 1262 of file multirangetypes.c.

{
    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);
}

References make_multirange(), palloc0(), range_before_internal(), range_intersect_internal(), range_overlaps_internal(), and range_overleft_internal().

Referenced by multirange_intersect(), and multirange_intersect_agg_transfn().

◆ multirange_minus_internal()

MultirangeType * multirange_minus_internal	(	Oid	mltrngtypoid,
		TypeCacheEntry *	rangetyp,
		int32	range_count1,
		RangeType **	ranges1,
		int32	range_count2,
		RangeType **	ranges2
	)

Definition at line 1146 of file multirangetypes.c.

{
    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);
}

References make_multirange(), palloc0(), range_before_internal(), range_minus_internal(), range_overlaps_internal(), range_split_internal(), and RangeIsEmpty.

Referenced by multirange_minus().

◆ multirange_ne_internal()

bool multirange_ne_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr1,
		const MultirangeType *	mr2
	)

Definition at line 1916 of file multirangetypes.c.

{
    return (!multirange_eq_internal(rangetyp, mr1, mr2));
}

References multirange_eq_internal().

Referenced by multirange_ne().

◆ multirange_overlaps_multirange_internal()

bool multirange_overlaps_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const MultirangeType *	mr1,
		const MultirangeType *	mr2
	)

Definition at line 2017 of file multirangetypes.c.

{
    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;
}

References multirange_get_bounds(), MultirangeIsEmpty, range_bounds_overlaps(), range_cmp_bounds(), and MultirangeType::rangeCount.

Referenced by multirange_overlaps_multirange().

◆ MultirangeTypePGetDatum()

static Datum MultirangeTypePGetDatum ( const MultirangeType * X )

inlinestatic

Definition at line 60 of file multirangetypes.h.

{
    return PointerGetDatum(X);
}

References PointerGetDatum().

◆ range_adjacent_multirange_internal()

bool range_adjacent_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 2472 of file multirangetypes.c.

{
    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;
}

References Assert(), bounds_adjacent(), multirange_get_bounds(), MultirangeIsEmpty, range_deserialize(), MultirangeType::rangeCount, and RangeIsEmpty.

Referenced by multirange_adjacent_range(), range_adjacent_multirange(), range_gist_consistent_int_multirange(), and range_gist_consistent_leaf_multirange().

◆ range_after_multirange_internal()

bool range_after_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 2447 of file multirangetypes.c.

{
    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);
}

References Assert(), multirange_get_bounds(), MultirangeIsEmpty, range_cmp_bounds(), range_deserialize(), MultirangeType::rangeCount, and RangeIsEmpty.

Referenced by multirange_before_range(), range_after_multirange(), range_gist_consistent_int_multirange(), and range_gist_consistent_leaf_multirange().

◆ range_before_multirange_internal()

bool range_before_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 2403 of file multirangetypes.c.

{
    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);
}

References Assert(), multirange_get_bounds(), MultirangeIsEmpty, range_cmp_bounds(), range_deserialize(), and RangeIsEmpty.

Referenced by multirange_after_range(), range_before_multirange(), range_gist_consistent_int_multirange(), and range_gist_consistent_leaf_multirange().

◆ range_contains_multirange_internal()

bool range_contains_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 1831 of file multirangetypes.c.

{
    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);
}

References Assert(), multirange_get_bounds(), MultirangeIsEmpty, range_bounds_contains(), range_deserialize(), MultirangeType::rangeCount, and RangeIsEmpty.

Referenced by multirange_contained_by_range(), range_contains_multirange(), range_gist_consistent_int_multirange(), and range_gist_consistent_leaf_multirange().

◆ range_overlaps_multirange_internal()

bool range_overlaps_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 1995 of file multirangetypes.c.

{
    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);
}

References Assert(), multirange_bsearch_match(), multirange_range_overlaps_bsearch_comparison(), MultirangeIsEmpty, range_deserialize(), and RangeIsEmpty.

Referenced by multirange_overlaps_range(), range_gist_consistent_int_multirange(), range_gist_consistent_leaf_multirange(), and range_overlaps_multirange().

◆ range_overleft_multirange_internal()

bool range_overleft_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 2075 of file multirangetypes.c.

{
    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, mr->rangeCount - 1,
                          &lower2, &upper2);
 
    return (range_cmp_bounds(rangetyp, &upper1, &upper2) <= 0);
}

References Assert(), multirange_get_bounds(), MultirangeIsEmpty, range_cmp_bounds(), range_deserialize(), MultirangeType::rangeCount, and RangeIsEmpty.

Referenced by range_gist_consistent_int_multirange(), range_gist_consistent_leaf_multirange(), and range_overleft_multirange().

◆ range_overright_multirange_internal()

bool range_overright_multirange_internal	(	TypeCacheEntry *	rangetyp,
		const RangeType *	r,
		const MultirangeType *	mr
	)

Definition at line 2159 of file multirangetypes.c.

{
    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, &lower1, &lower2) >= 0);
}

References Assert(), multirange_get_bounds(), MultirangeIsEmpty, range_cmp_bounds(), range_deserialize(), and RangeIsEmpty.

Referenced by range_gist_consistent_int_multirange(), range_gist_consistent_leaf_multirange(), and range_overright_multirange().

Data Structures

Macros

Functions

Macro Definition Documentation

◆ MultirangeIsEmpty

◆ MultirangeTypeGetOid

◆ PG_GETARG_MULTIRANGE_P

◆ PG_GETARG_MULTIRANGE_P_COPY

◆ PG_RETURN_MULTIRANGE_P

Function Documentation

◆ DatumGetMultirangeTypeP()

◆ DatumGetMultirangeTypePCopy()

◆ make_empty_multirange()

◆ make_multirange()

◆ multirange_before_multirange_internal()

◆ multirange_contains_elem_internal()

◆ multirange_contains_multirange_internal()

◆ multirange_contains_range_internal()

◆ multirange_deserialize()

◆ multirange_eq_internal()

◆ multirange_get_bounds()

◆ multirange_get_range()

◆ multirange_get_typcache()

◆ multirange_get_union_range()

◆ multirange_intersect_internal()

◆ multirange_minus_internal()

◆ multirange_ne_internal()

◆ multirange_overlaps_multirange_internal()

◆ MultirangeTypePGetDatum()

◆ range_adjacent_multirange_internal()

◆ range_after_multirange_internal()

◆ range_before_multirange_internal()

◆ range_contains_multirange_internal()

◆ range_overlaps_multirange_internal()

◆ range_overleft_multirange_internal()

◆ range_overright_multirange_internal()