bitmapset.c File Reference

#include "postgres.h"
#include "common/hashfn.h"
#include "common/int.h"
#include "nodes/bitmapset.h"
#include "nodes/pg_list.h"
#include "port/pg_bitutils.h"

Include dependency graph for bitmapset.c:

Go to the source code of this file.

Macros
#define	WORDNUM(x)   ((x) / BITS_PER_BITMAPWORD)
#define	BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
#define	BITMAPSET_SIZE(nwords)    (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
#define	RIGHTMOST_ONE(x)   ((signedbitmapword) (x) & -((signedbitmapword) (x)))
#define	HAS_MULTIPLE_ONES(x)   ((bitmapword) RIGHTMOST_ONE(x) != (x))

Functions
Bitmapset *	bms_copy (const Bitmapset *a)
bool	bms_equal (const Bitmapset *a, const Bitmapset *b)
int	bms_compare (const Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_make_singleton (int x)
void	bms_free (Bitmapset *a)
Bitmapset *	bms_union (const Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_intersect (const Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_difference (const Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_offset_members (const Bitmapset *a, int offset)
bool	bms_is_subset (const Bitmapset *a, const Bitmapset *b)
BMS_Comparison	bms_subset_compare (const Bitmapset *a, const Bitmapset *b)
bool	bms_is_member (int x, const Bitmapset *a)
int	bms_member_index (Bitmapset *a, int x)
bool	bms_overlap (const Bitmapset *a, const Bitmapset *b)
bool	bms_overlap_list (const Bitmapset *a, const List *b)
bool	bms_nonempty_difference (const Bitmapset *a, const Bitmapset *b)
int	bms_singleton_member (const Bitmapset *a)
bool	bms_get_singleton_member (const Bitmapset *a, int *member)
int	bms_num_members (const Bitmapset *a)
BMS_Membership	bms_membership (const Bitmapset *a)
Bitmapset *	bms_add_member (Bitmapset *a, int x)
Bitmapset *	bms_del_member (Bitmapset *a, int x)
Bitmapset *	bms_add_members (Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_replace_members (Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_add_range (Bitmapset *a, int lower, int upper)
Bitmapset *	bms_int_members (Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_del_members (Bitmapset *a, const Bitmapset *b)
Bitmapset *	bms_join (Bitmapset *a, Bitmapset *b)
int	bms_next_member (const Bitmapset *a, int prevbit)
int	bms_prev_member (const Bitmapset *a, int prevbit)
uint32	bms_hash_value (const Bitmapset *a)
uint32	bitmap_hash (const void *key, Size keysize)
int	bitmap_match (const void *key1, const void *key2, Size keysize)

Macro Definition Documentation

BITMAPSET_SIZE

#define BITMAPSET_SIZE

(

nwords

)

(offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))

Definition at line 51 of file bitmapset.c.

{
    /* NULL is the correct representation of an empty set */
    if (a == NULL)
        return true;
 
    /* check the node tag is set correctly.  pfree'd pointer, maybe? */
    if (!IsA(a, Bitmapset))
        return false;
 
    /* trailing zero words are not allowed */
    if (a->words[a->nwords - 1] == 0)
        return false;
 
    return true;
}
#endif
 
#ifdef REALLOCATE_BITMAPSETS
/*
 * bms_copy_and_free
 *      Only required in REALLOCATE_BITMAPSETS builds.  Provide a simple way
 *      to return a freshly allocated set and pfree the original.
 *
 * Note: callers which accept multiple sets must be careful when calling this
 * function to clone one parameter as other parameters may point to the same
 * set.  A good option is to call this just before returning the resulting
 * set.
 */
static Bitmapset *
bms_copy_and_free(Bitmapset *a)
{
    Bitmapset  *c = bms_copy(a);
 
    bms_free(a);
    return c;
}
#endif
 
/*
 * bms_copy - make a palloc'd copy of a bitmapset
 */
Bitmapset *
bms_copy(const Bitmapset *a)
{
    Bitmapset  *result;
    size_t      size;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return NULL;
 
    size = BITMAPSET_SIZE(a->nwords);
    result = (Bitmapset *) palloc(size);
    memcpy(result, a, size);
    return result;
}
 
/*
 * bms_equal - are two bitmapsets equal? or both NULL?
 */
bool
bms_equal(const Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
        if (b == NULL)
            return true;
        return false;
    }
    else if (b == NULL)
        return false;
 
    /* can't be equal if the word counts don't match */
    if (a->nwords != b->nwords)
        return false;
 
    /* check each word matches */
    i = 0;
    do
    {
        if (a->words[i] != b->words[i])
            return false;
    } while (++i < a->nwords);
 
    return true;
}
 
/*
 * bms_compare - qsort-style comparator for bitmapsets
 *
 * This guarantees to report values as equal iff bms_equal would say they are
 * equal.  Otherwise, the highest-numbered bit that is set in one value but
 * not the other determines the result.  (This rule means that, for example,
 * {6} is greater than {5}, which seems plausible.)
 */
int
bms_compare(const Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return (b == NULL) ? 0 : -1;
    else if (b == NULL)
        return +1;
 
    /* the set with the most words must be greater */
    if (a->nwords != b->nwords)
        return (a->nwords > b->nwords) ? +1 : -1;
 
    i = a->nwords - 1;
    do
    {
        bitmapword  aw = a->words[i];
        bitmapword  bw = b->words[i];
 
        if (aw != bw)
            return (aw > bw) ? +1 : -1;
    } while (--i >= 0);
    return 0;
}
 
/*
 * bms_make_singleton - build a bitmapset containing a single member
 */
Bitmapset *
bms_make_singleton(int x)
{
    Bitmapset  *result;
    int         wordnum,
                bitnum;
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
    result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
    result->type = T_Bitmapset;
    result->nwords = wordnum + 1;
    result->words[wordnum] = ((bitmapword) 1 << bitnum);
    return result;
}
 
/*
 * bms_free - free a bitmapset
 *
 * Same as pfree except for allowing NULL input
 */
void
bms_free(Bitmapset *a)
{
    if (a)
        pfree(a);
}
 
 
/*
 * bms_union - create and return a new set containing all members from both
 * input sets.  Both inputs are left unmodified.
 */
Bitmapset *
bms_union(const Bitmapset *a, const Bitmapset *b)
{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
        return bms_copy(a);
    /* Identify shorter and longer input; copy the longer one */
    if (a->nwords <= b->nwords)
    {
        result = bms_copy(b);
        other = a;
    }
    else
    {
        result = bms_copy(a);
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    return result;
}
 
/*
 * bms_intersect - create and return a new set containing members which both
 * input sets have in common.  Both inputs are left unmodified.
 */
Bitmapset *
bms_intersect(const Bitmapset *a, const Bitmapset *b)
{
    Bitmapset  *result;
    const Bitmapset *other;
    int         lastnonzero;
    int         resultlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL || b == NULL)
        return NULL;
 
    /* Identify shorter and longer input; copy the shorter one */
    if (a->nwords <= b->nwords)
    {
        result = bms_copy(a);
        other = b;
    }
    else
    {
        result = bms_copy(b);
        other = a;
    }
    /* And intersect the longer input with the result */
    resultlen = result->nwords;
    lastnonzero = -1;
    i = 0;
    do
    {
        result->words[i] &= other->words[i];
 
        if (result->words[i] != 0)
            lastnonzero = i;
    } while (++i < resultlen);
    /* If we computed an empty result, we must return NULL */
    if (lastnonzero == -1)
    {
        pfree(result);
        return NULL;
    }
 
    /* get rid of trailing zero words */
    result->nwords = lastnonzero + 1;
    return result;
}
 
/*
 * bms_difference - create and return a new set containing all the members of
 * 'a' without the members of 'b'.
 */
Bitmapset *
bms_difference(const Bitmapset *a, const Bitmapset *b)
{
    Bitmapset  *result;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
        return bms_copy(a);
 
    /*
     * In Postgres' usage, an empty result is a very common case, so it's
     * worth optimizing for that by testing bms_nonempty_difference().  This
     * saves us a palloc/pfree cycle compared to checking after-the-fact.
     */
    if (!bms_nonempty_difference(a, b))
        return NULL;
 
    /* Copy the left input */
    result = bms_copy(a);
 
    /* And remove b's bits from result */
    if (result->nwords > b->nwords)
    {
        /*
         * We'll never need to remove trailing zero words when 'a' has more
         * words than 'b' as the additional words must be non-zero.
         */
        i = 0;
        do
        {
            result->words[i] &= ~b->words[i];
        } while (++i < b->nwords);
    }
    else
    {
        int         lastnonzero = -1;
 
        /* we may need to remove trailing zero words from the result. */
        i = 0;
        do
        {
            result->words[i] &= ~b->words[i];
 
            /* remember the last non-zero word */
            if (result->words[i] != 0)
                lastnonzero = i;
        } while (++i < result->nwords);
 
        /* trim off trailing zero words */
        result->nwords = lastnonzero + 1;
    }
    Assert(result->nwords != 0);
 
    /* Need not check for empty result, since we handled that case above */
    return result;
}
 
/*
 * bms_offset_members
 *      Creates a new Bitmapset with all members of 'a' adjusted to add the
 *      value of 'offset' to each member.
 *
 * Members that would become negative as a result of a negative offset will
 * be removed from the set, whereas too large an offset, which would result in
 * a member going > INT_MAX, will result in an ERROR.
 */
Bitmapset *
bms_offset_members(const Bitmapset *a, int offset)
{
    Bitmapset  *result;
    int         offset_words;
    int         offset_bits;
    int         new_nwords;
    int         old_nwords;
    int32       high_bit;
    int         old_highest;
    int         new_highest;
 
    Assert(bms_is_valid_set(a));
 
    /* nothing to do for empty sets */
    if (a == NULL)
        return NULL;
 
    old_nwords = a->nwords;
    offset_words = WORDNUM(offset);
    offset_bits = BITNUM(offset);
    high_bit = bmw_leftmost_one_pos(a->words[a->nwords - 1]);
    old_highest = (old_nwords - 1) * BITS_PER_BITMAPWORD + high_bit;
 
    /* don't create a set with a member that doesn't fit into an int32 */
    if (pg_add_s32_overflow(old_highest, offset, &new_highest))
        elog(ERROR, "bitmapset overflow");
    /* return NULL if the new set would be empty */
    else if (new_highest < 0)
        return NULL;
 
    new_nwords = WORDNUM(new_highest) + 1;
    result = (Bitmapset *) palloc0(BITMAPSET_SIZE(new_nwords));
    result->type = T_Bitmapset;
    result->nwords = new_nwords;
 
    /* handle zero and positive offsets (bitshift left) */
    if (offset >= 0)
    {
        /*
         * We special-case offsetting only by whole words, so we don't have to
         * special-case bitshifting by BITS_PER_BITMAPWORD places, which has
         * an undefined behavior.
         */
        if (offset_bits == 0)
        {
            int         i = 0;
 
            /*
             * The old set is guaranteed to have at least 1 word, so use
             * do/while to save the redundant initial loop bounds check.
             */
            do
            {
                Assert(i + offset_words < new_nwords);
                result->words[i + offset_words] = a->words[i];
            } while (++i < old_nwords);
        }
        else
        {
            int         carry_bits = BITS_PER_BITMAPWORD - offset_bits;
            bitmapword  prev_carry = 0;
            int         i = 0;
 
            do
            {
                bitmapword  carry = (a->words[i] >> carry_bits);
 
                Assert(i + offset_words < new_nwords);
                /* shift bits up and carry bits from the previous word */
                result->words[i + offset_words] = (a->words[i] << offset_bits) | prev_carry;
                prev_carry = carry;
            } while (++i < old_nwords);
            result->words[new_nwords - 1] |= prev_carry;
        }
    }
 
    /* handle negative offset (bitshift right) */
    else
    {
        /* make the negative offset_words and offset_bits positive */
        offset_words = 0 - offset_words;
        offset_bits = 0 - offset_bits;
 
        /* as above, special case shifting only by whole words */
        if (offset_bits == 0)
        {
            int         i = 0;
 
            do
            {
                Assert(i + offset_words < old_nwords);
                result->words[i] = a->words[i + offset_words];
            } while (++i < new_nwords);
        }
        else
        {
            int         carry_bits = BITS_PER_BITMAPWORD - offset_bits;
            bitmapword  prev_carry = 0;
            int         i = new_nwords - 1;
 
            /* carry bits from any word just above where the loop starts */
            if (old_nwords > new_nwords + offset_words)
                prev_carry = (a->words[new_nwords + offset_words] << carry_bits);
 
            /*
             * We loop backward over the array so we correctly carry bits from
             * higher words.
             */
            do
            {
                bitmapword  carry = (a->words[i + offset_words] << carry_bits);
 
                Assert(i + offset_words < old_nwords);
 
                /* shift bits down and carry bits from the previous word */
                result->words[i] = (a->words[i + offset_words] >> offset_bits) | prev_carry;
                prev_carry = carry;
            } while (--i >= 0);
        }
    }
 
    return result;
}
 
/*
 * bms_is_subset - is A a subset of B?
 */
bool
bms_is_subset(const Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return true;            /* empty set is a subset of anything */
    if (b == NULL)
        return false;
 
    /* 'a' can't be a subset of 'b' if it contains more words */
    if (a->nwords > b->nwords)
        return false;
 
    /* Check all 'a' members are set in 'b' */
    i = 0;
    do
    {
        if ((a->words[i] & ~b->words[i]) != 0)
            return false;
    } while (++i < a->nwords);
    return true;
}
 
/*
 * bms_subset_compare - compare A and B for equality/subset relationships
 *
 * This is more efficient than testing bms_is_subset in both directions.
 */
BMS_Comparison
bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
    BMS_Comparison result;
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
        if (b == NULL)
            return BMS_EQUAL;
        return BMS_SUBSET1;
    }
    if (b == NULL)
        return BMS_SUBSET2;
 
    /* Check common words */
    result = BMS_EQUAL;         /* status so far */
    shortlen = Min(a->nwords, b->nwords);
    i = 0;
    do
    {
        bitmapword  aword = a->words[i];
        bitmapword  bword = b->words[i];
 
        if ((aword & ~bword) != 0)
        {
            /* a is not a subset of b */
            if (result == BMS_SUBSET1)
                return BMS_DIFFERENT;
            result = BMS_SUBSET2;
        }
        if ((bword & ~aword) != 0)
        {
            /* b is not a subset of a */
            if (result == BMS_SUBSET2)
                return BMS_DIFFERENT;
            result = BMS_SUBSET1;
        }
    } while (++i < shortlen);
    /* Check extra words */
    if (a->nwords > b->nwords)
    {
        /* if a has more words then a is not a subset of b */
        if (result == BMS_SUBSET1)
            return BMS_DIFFERENT;
        return BMS_SUBSET2;
    }
    else if (a->nwords < b->nwords)
    {
        /* if b has more words then b is not a subset of a */
        if (result == BMS_SUBSET2)
            return BMS_DIFFERENT;
        return BMS_SUBSET1;
    }
    return result;
}
 
/*
 * bms_is_member - is X a member of A?
 */
bool
bms_is_member(int x, const Bitmapset *a)
{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    /* XXX better to just return false for x<0 ? */
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return false;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
    if (wordnum >= a->nwords)
        return false;
    if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
        return true;
    return false;
}
 
/*
 * bms_member_index
 *      determine 0-based index of member x in the bitmap
 *
 * Returns (-1) when x is not a member.
 */
int
bms_member_index(Bitmapset *a, int x)
{
    int         bitnum;
    int         wordnum;
    int         result = 0;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    /* return -1 if not a member of the bitmap */
    if (!bms_is_member(x, a))
        return -1;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
    /* count bits in preceding words */
    result += pg_popcount((const char *) a->words,
                          wordnum * sizeof(bitmapword));
 
    /*
     * Now add bits of the last word, but only those before the item. We can
     * do that by applying a mask and then using popcount again. To get
     * 0-based index, we want to count only preceding bits, not the item
     * itself, so we subtract 1.
     */
    mask = ((bitmapword) 1 << bitnum) - 1;
    result += bmw_popcount(a->words[wordnum] & mask);
 
    return result;
}
 
/*
 * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
 */
bool
bms_overlap(const Bitmapset *a, const Bitmapset *b)
{
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL || b == NULL)
        return false;
    /* Check words in common */
    shortlen = Min(a->nwords, b->nwords);
    i = 0;
    do
    {
        if ((a->words[i] & b->words[i]) != 0)
            return true;
    } while (++i < shortlen);
    return false;
}
 
/*
 * bms_overlap_list - does a set overlap an integer list?
 */
bool
bms_overlap_list(const Bitmapset *a, const List *b)
{
    ListCell   *lc;
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL || b == NIL)
        return false;
 
    foreach(lc, b)
    {
        int         x = lfirst_int(lc);
 
        if (x < 0)
            elog(ERROR, "negative bitmapset member not allowed");
        wordnum = WORDNUM(x);
        bitnum = BITNUM(x);
        if (wordnum < a->nwords)
            if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
                return true;
    }
 
    return false;
}
 
/*
 * bms_nonempty_difference - do sets have a nonempty difference?
 *
 * i.e., are any members set in 'a' that are not also set in 'b'.
 */
bool
bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return false;
    if (b == NULL)
        return true;
    /* if 'a' has more words then it must contain additional members */
    if (a->nwords > b->nwords)
        return true;
    /* Check all 'a' members are set in 'b' */
    i = 0;
    do
    {
        if ((a->words[i] & ~b->words[i]) != 0)
            return true;
    } while (++i < a->nwords);
    return false;
}
 
/*
 * bms_singleton_member - return the sole integer member of set
 *
 * Raises error if |a| is not 1.
 */
int
bms_singleton_member(const Bitmapset *a)
{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        elog(ERROR, "bitmapset is empty");
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result >= 0 || HAS_MULTIPLE_ONES(w))
                elog(ERROR, "bitmapset has multiple members");
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
        }
    } while (++wordnum < nwords);
 
    /* we don't expect non-NULL sets to be empty */
    Assert(result >= 0);
    return result;
}
 
/*
 * bms_get_singleton_member
 *
 * Test whether the given set is a singleton.
 * If so, set *member to the value of its sole member, and return true.
 * If not, return false, without changing *member.
 *
 * This is more convenient and faster than calling bms_membership() and then
 * bms_singleton_member(), if we don't care about distinguishing empty sets
 * from multiple-member sets.
 */
bool
bms_get_singleton_member(const Bitmapset *a, int *member)
{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return false;
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result >= 0 || HAS_MULTIPLE_ONES(w))
                return false;
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
        }
    } while (++wordnum < nwords);
 
    /* we don't expect non-NULL sets to be empty */
    Assert(result >= 0);
    *member = result;
    return true;
}
 
/*
 * bms_num_members - count members of set
 */
int
bms_num_members(const Bitmapset *a)
{
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return 0;
 
    /* fast-path for common case */
    if (a->nwords == 1)
        return bmw_popcount(a->words[0]);
 
    return pg_popcount((const char *) a->words,
                       a->nwords * sizeof(bitmapword));
}
 
/*
 * bms_membership - does a set have zero, one, or multiple members?
 *
 * This is faster than making an exact count with bms_num_members().
 */
BMS_Membership
bms_membership(const Bitmapset *a)
{
    BMS_Membership result = BMS_EMPTY_SET;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return BMS_EMPTY_SET;
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
                return BMS_MULTIPLE;
            result = BMS_SINGLETON;
        }
    } while (++wordnum < nwords);
    return result;
}
 
 
/*
 * bms_add_member - add a specified member to set
 *
 * 'a' is recycled when possible.
 */
Bitmapset *
bms_add_member(Bitmapset *a, int x)
{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return bms_make_singleton(x);
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
    /* enlarge the set if necessary */
    if (wordnum >= a->nwords)
    {
        int         oldnwords = a->nwords;
        int         i;
 
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
        a->nwords = wordnum + 1;
        /* zero out the enlarged portion */
        i = oldnwords;
        do
        {
            a->words[i] = 0;
        } while (++i < a->nwords);
    }
 
    a->words[wordnum] |= ((bitmapword) 1 << bitnum);
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}
 
/*
 * bms_del_member - remove a specified member from set
 *
 * No error if x is not currently a member of set
 *
 * 'a' is recycled when possible.
 */
Bitmapset *
bms_del_member(Bitmapset *a, int x)
{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return NULL;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    /* member can't exist.  Return 'a' unmodified */
    if (unlikely(wordnum >= a->nwords))
        return a;
 
    a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
 
    /* when last word becomes empty, trim off all trailing empty words */
    if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
    {
        /* find the last non-empty word and make that the new final word */
        for (int i = wordnum - 1; i >= 0; i--)
        {
            if (a->words[i] != 0)
            {
                a->nwords = i + 1;
                return a;
            }
        }
 
        /* the set is now empty */
        pfree(a);
        return NULL;
    }
    return a;
}
 
/*
 * bms_add_members - like bms_union, but left input is recycled when possible
 */
Bitmapset *
bms_add_members(Bitmapset *a, const Bitmapset *b)
{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
    /* Identify shorter and longer input; copy the longer one if needed */
    if (a->nwords < b->nwords)
    {
        result = bms_copy(b);
        other = a;
    }
    else
    {
        result = a;
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    if (result != a)
        pfree(a);
#ifdef REALLOCATE_BITMAPSETS
    else
        result = bms_copy_and_free(result);
#endif
 
    return result;
}
 
/*
 * bms_replace_members
 *      Remove all existing members from 'a' and repopulate the set with members
 *      from 'b', recycling 'a', when possible.
 */
Bitmapset *
bms_replace_members(Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
    {
        pfree(a);
        return NULL;
    }
 
    if (a->nwords < b->nwords)
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
 
    i = 0;
    do
    {
        a->words[i] = b->words[i];
    } while (++i < b->nwords);
 
    a->nwords = b->nwords;
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}
 
/*
 * bms_add_range
 *      Add members in the range of 'lower' to 'upper' to the set.
 *
 * Note this could also be done by calling bms_add_member in a loop, however,
 * using this function will be faster when the range is large as we work at
 * the bitmapword level rather than at bit level.
 */
Bitmapset *
bms_add_range(Bitmapset *a, int lower, int upper)
{
    int         lwordnum,
                lbitnum,
                uwordnum,
                ushiftbits,
                wordnum;
 
    Assert(bms_is_valid_set(a));
 
    /* do nothing if nothing is called for, without further checking */
    if (upper < lower)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    if (lower < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    uwordnum = WORDNUM(upper);
 
    if (a == NULL)
    {
        a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
        a->type = T_Bitmapset;
        a->nwords = uwordnum + 1;
    }
    else if (uwordnum >= a->nwords)
    {
        int         oldnwords = a->nwords;
        int         i;
 
        /* ensure we have enough words to store the upper bit */
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
        a->nwords = uwordnum + 1;
        /* zero out the enlarged portion */
        i = oldnwords;
        do
        {
            a->words[i] = 0;
        } while (++i < a->nwords);
    }
 
    wordnum = lwordnum = WORDNUM(lower);
 
    lbitnum = BITNUM(lower);
    ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
 
    /*
     * Special case when lwordnum is the same as uwordnum we must perform the
     * upper and lower masking on the word.
     */
    if (lwordnum == uwordnum)
    {
        a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
            & (~(bitmapword) 0) >> ushiftbits;
    }
    else
    {
        /* turn on lbitnum and all bits left of it */
        a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
 
        /* turn on all bits for any intermediate words */
        while (wordnum < uwordnum)
            a->words[wordnum++] = ~(bitmapword) 0;
 
        /* turn on upper's bit and all bits right of it. */
        a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
    }
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}
 
/*
 * bms_int_members - like bms_intersect, but left input is recycled when
 * possible
 */
Bitmapset *
bms_int_members(Bitmapset *a, const Bitmapset *b)
{
    int         lastnonzero;
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
    {
        pfree(a);
        return NULL;
    }
 
    /* Intersect b into a; we need never copy */
    shortlen = Min(a->nwords, b->nwords);
    lastnonzero = -1;
    i = 0;
    do
    {
        a->words[i] &= b->words[i];
 
        if (a->words[i] != 0)
            lastnonzero = i;
    } while (++i < shortlen);
 
    /* If we computed an empty result, we must return NULL */
    if (lastnonzero == -1)
    {
        pfree(a);
        return NULL;
    }
 
    /* get rid of trailing zero words */
    a->nwords = lastnonzero + 1;
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    return a;
}
 
/*
 * bms_del_members - delete members in 'a' that are set in 'b'.  'a' is
 * recycled when possible.
 */
Bitmapset *
bms_del_members(Bitmapset *a, const Bitmapset *b)
{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    /* Remove b's bits from a; we need never copy */
    if (a->nwords > b->nwords)
    {
        /*
         * We'll never need to remove trailing zero words when 'a' has more
         * words than 'b'.
         */
        i = 0;
        do
        {
            a->words[i] &= ~b->words[i];
        } while (++i < b->nwords);
    }
    else
    {
        int         lastnonzero = -1;
 
        /* we may need to remove trailing zero words from the result. */
        i = 0;
        do
        {
            a->words[i] &= ~b->words[i];
 
            /* remember the last non-zero word */
            if (a->words[i] != 0)
                lastnonzero = i;
        } while (++i < a->nwords);
 
        /* check if 'a' has become empty */
        if (lastnonzero == -1)
        {
            pfree(a);
            return NULL;
        }
 
        /* trim off any trailing zero words */
        a->nwords = lastnonzero + 1;
    }
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    return a;
}
 
/*
 * bms_join - like bms_union, but *either* input *may* be recycled
 */
Bitmapset *
bms_join(Bitmapset *a, Bitmapset *b)
{
    Bitmapset  *result;
    Bitmapset  *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        b = bms_copy_and_free(b);
#endif
 
        return b;
    }
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    /* Identify shorter and longer input; use longer one as result */
    if (a->nwords < b->nwords)
    {
        result = b;
        other = a;
    }
    else
    {
        result = a;
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    if (other != result)        /* pure paranoia */
        pfree(other);
 
#ifdef REALLOCATE_BITMAPSETS
    result = bms_copy_and_free(result);
#endif
 
    return result;
}
 
/*
 * bms_next_member - find next member of a set
 *
 * Returns smallest member greater than "prevbit", or -2 if there is none.
 * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
 *
 * This is intended as support for iterating through the members of a set.
 * The typical pattern is
 *
 *          x = -1;
 *          while ((x = bms_next_member(inputset, x)) >= 0)
 *              process member x;
 *
 * Notice that when there are no more members, we return -2, not -1 as you
 * might expect.  The rationale for that is to allow distinguishing the
 * loop-not-started state (x == -1) from the loop-completed state (x == -2).
 * It makes no difference in simple loop usage, but complex iteration logic
 * might need such an ability.
 */
int
bms_next_member(const Bitmapset *a, int prevbit)
{
    unsigned int currbit = prevbit;
    int         nwords;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return -2;
    nwords = a->nwords;
 
    /* use an unsigned int to avoid the risk that int overflows */
    currbit++;
    mask = (~(bitmapword) 0) << BITNUM(currbit);
    for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];
 
        /* ignore bits before currbit */
        w &= mask;
 
        if (w != 0)
        {
            int         result;
 
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
            return result;
        }
 
        /* in subsequent words, consider all bits */
        mask = (~(bitmapword) 0);
    }
    return -2;
}
 
/*
 * bms_prev_member - find prev member of a set
 *
 * Returns largest member less than "prevbit", or -2 if there is none.
 * "prevbit" must NOT be more than one above the highest possible bit that can
 * be set in the Bitmapset at its current size.
 *
 * To ease finding the highest set bit for the initial loop, the special
 * prevbit value of -1 can be passed to have the function find the highest
 * valued member in the set.
 *
 * This is intended as support for iterating through the members of a set in
 * reverse.  The typical pattern is
 *
 *          x = -1;
 *          while ((x = bms_prev_member(inputset, x)) >= 0)
 *              process member x;
 *
 * Notice that when there are no more members, we return -2, not -1 as you
 * might expect.  The rationale for that is to allow distinguishing the
 * loop-not-started state (x == -1) from the loop-completed state (x == -2).
 * It makes no difference in simple loop usage, but complex iteration logic
 * might need such an ability.
 */
int
bms_prev_member(const Bitmapset *a, int prevbit)
{
    unsigned int currbit;
    int         ushiftbits;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    /*
     * If set is NULL or if there are no more bits to the right then we've
     * nothing to do.
     */
    if (a == NULL || prevbit == 0)
        return -2;
 
    /* Validate callers didn't give us something out of range */
    Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD));
 
    /*
     * Transform -1 (or any negative number) to the highest possible bit we
     * could have set.  We do this in unsigned math to avoid the risk of
     * overflowing a signed int.
     */
    if (prevbit < 0)
        currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
    else
        currbit = prevbit - 1;
 
    ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
    mask = (~(bitmapword) 0) >> ushiftbits;
    for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
    {
        bitmapword  w = a->words[wordnum];
 
        /* mask out bits left of currbit */
        w &= mask;
 
        if (w != 0)
        {
            int         result;
 
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_leftmost_one_pos(w);
            return result;
        }
 
        /* in subsequent words, consider all bits */
        mask = (~(bitmapword) 0);
    }
    return -2;
}
 
/*
 * bms_hash_value - compute a hash key for a Bitmapset
 */
uint32
bms_hash_value(const Bitmapset *a)
{
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return 0;               /* All empty sets hash to 0 */
    return DatumGetUInt32(hash_any((const unsigned char *) a->words,
                                   a->nwords * sizeof(bitmapword)));
}
 
/*
 * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
 *
 * Note: don't forget to specify bitmap_match as the match function!
 */
uint32
bitmap_hash(const void *key, Size keysize)
{
    Assert(keysize == sizeof(Bitmapset *));
    return bms_hash_value(*((const Bitmapset *const *) key));
}
 
/*
 * bitmap_match - match function to use with bitmap_hash
 */
int
bitmap_match(const void *key1, const void *key2, Size keysize)
{
    Assert(keysize == sizeof(Bitmapset *));
    return !bms_equal(*((const Bitmapset *const *) key1),
                      *((const Bitmapset *const *) key2));
}

BITNUM

#define BITNUM

(

x

)

((x) % BITS_PER_BITMAPWORD)

Definition at line 49 of file bitmapset.c.

HAS_MULTIPLE_ONES

#define HAS_MULTIPLE_ONES

(

x

)

((bitmapword) RIGHTMOST_ONE(x) != (x))

Definition at line 73 of file bitmapset.c.

RIGHTMOST_ONE

#define RIGHTMOST_ONE

(

x

)

((signedbitmapword) (x) & -((signedbitmapword) (x)))

Definition at line 71 of file bitmapset.c.

WORDNUM

#define WORDNUM

(

x

)

((x) / BITS_PER_BITMAPWORD)

Definition at line 48 of file bitmapset.c.

Function Documentation

bitmap_hash()

uint32 bitmap_hash	(	const void *	key,
		Size	keysize
	)

Definition at line 1559 of file bitmapset.c.

{
    Assert(keysize == sizeof(Bitmapset *));
    return bms_hash_value(*((const Bitmapset *const *) key));
}

References Assert, and bms_hash_value().

Referenced by build_join_rel_hash(), and test_bitmap_hash().

bitmap_match()

int bitmap_match	(	const void *	key1,
		const void *	key2,
		Size	keysize
	)

Definition at line 1569 of file bitmapset.c.

{
    Assert(keysize == sizeof(Bitmapset *));
    return !bms_equal(*((const Bitmapset *const *) key1),
                      *((const Bitmapset *const *) key2));
}

References Assert, bms_equal(), and fb().

Referenced by build_join_rel_hash(), and test_bitmap_match().

bms_add_member()

Bitmapset * bms_add_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 934 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return bms_make_singleton(x);
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
    /* enlarge the set if necessary */
    if (wordnum >= a->nwords)
    {
        int         oldnwords = a->nwords;
        int         i;
 
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
        a->nwords = wordnum + 1;
        /* zero out the enlarged portion */
        i = oldnwords;
        do
        {
            a->words[i] = 0;
        } while (++i < a->nwords);
    }
 
    a->words[wordnum] |= ((bitmapword) 1 << bitnum);
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}

References a, Assert, BITMAPSET_SIZE, BITNUM, bms_make_singleton(), elog, ERROR, fb(), i, repalloc(), WORDNUM, and x.

Referenced by _readBitmapset(), add_child_eq_member(), add_outer_joins_to_relids(), add_row_identity_var(), add_rte_to_flat_rtable(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), all_rows_selectable(), apply_handle_update(), build_joinrel_tlist(), build_subplan(), buildGroupedVar(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), clauselist_apply_dependencies(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_list_bounds(), CreatePartitionPruneState(), DecodeTextArrayToBitmapset(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), DoCopy(), dropconstraint_internal(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecInitAgg(), ExecInitAppend(), ExecInitGenerated(), ExecInitModifyTable(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanGather(), ExecReScanGatherMerge(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), execute_attr_map_cols(), expand_single_inheritance_child(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), extractRemainingColumns(), fetch_remote_table_info(), fetch_statentries_for_relation(), finalize_plan(), finalize_primnode(), find_childrel_parents(), find_cols(), find_cols_walker(), find_hash_columns(), find_having_conflicts(), find_matching_subplans_recurse(), find_window_run_conditions(), findDefaultOnlyColumns(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), gen_partprune_steps_internal(), generate_base_implied_equalities(), generate_query_for_graph_path(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_eclass_for_sort_expr(), get_matching_partitions(), get_nullingrels_recurse(), get_param_path_clause_serials(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_notnullatts(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), InitExecPartitionPruneContexts(), initialize_change_context(), is_var_needed_by_join(), join_is_removable(), load_enum_cache_data(), logicalrep_read_attrs(), logicalrep_rel_open(), make_datum_param(), make_modifytable(), make_outerjoininfo(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), mark_rels_nulled_by_join(), mark_stmt(), markRelsAsNulledBy(), markRTEForSelectPriv(), mbms_add_member(), mbms_overlap_sets(), MergeAttributes(), nodeRead(), pgpa_filter_out_join_relids(), pgpa_plan_walker(), pgpa_planner_apply_join_path_advice(), pgpa_planner_apply_joinrel_advice(), pgpa_planner_apply_scan_advice(), pgpa_qf_add_rti(), pgpa_trove_add_to_hash(), pgpa_trove_slice_lookup(), pgpa_walker_join_order_matches_member(), pgpa_walker_would_advise(), plpgsql_mark_local_assignment_targets(), preprocess_grouping_sets(), pub_collist_to_bitmapset(), pub_collist_validate(), pub_form_cols_map(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), rebuild_joinclause_attr_needed(), reduce_outer_joins_pass2(), register_partpruneinfo(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_leftjoinrel_from_query(), remove_rel_from_phvs(), remove_rel_from_query(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_groupby_columns(), remove_useless_results_recurse(), rewriteTargetListIU(), rewriteTargetView(), RI_Initial_Check(), set_join_column_names(), set_param_references(), SS_identify_outer_params(), standard_planner(), stat_covers_expressions(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), test_bms_add_member(), test_random_offset_operations(), test_random_operations(), transformForPortionOfClause(), transformGroupClause(), transformGroupClauseList(), transformInsertStmt(), transformMergeStmt(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), try_partitionwise_join(), use_physical_tlist(), validate_va_cols_list(), and view_cols_are_auto_updatable().

bms_add_members()

Bitmapset * bms_add_members	(	Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 1036 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
    /* Identify shorter and longer input; copy the longer one if needed */
    if (a->nwords < b->nwords)
    {
        result = bms_copy(b);
        other = a;
    }
    else
    {
        result = a;
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    if (result != a)
        pfree(a);
#ifdef REALLOCATE_BITMAPSETS
    else
        result = bms_copy_and_free(result);
#endif
 
    return result;
}

References a, Assert, b, bms_copy(), fb(), i, pfree(), and result.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_eq_member(), add_outer_joins_to_relids(), add_part_relids(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_attr_needed(), add_vars_to_targetlist(), adjust_appendrel_attrs_mutator(), adjust_standard_join_alias_expression(), build_index_paths(), choose_best_statistics(), choose_bitmap_and(), create_agg_clause_infos(), create_bitmap_and_path(), create_bitmap_or_path(), create_join_clause(), create_lateral_join_info(), CreatePartitionPruneState(), deconstruct_distribute(), deconstruct_recurse(), ExecDoInitialPruning(), ExecFindMatchingSubPlans(), ExecInitAgg(), expand_partitioned_rtentry(), ExplainPreScanNode(), finalize_plan(), find_nonnullable_rels_walker(), foreign_join_ok(), generate_union_paths(), get_eclass_indexes_for_relids(), get_param_path_clause_serials(), get_placeholder_nulling_relids(), heap_update(), join_is_legal(), make_outerjoininfo(), mbms_add_members(), perform_pruning_combine_step(), pgpa_build_scan(), pgpa_classify_alternative_subplans(), pgpa_process_unrolled_join(), pgpa_qf_add_rtis(), pull_varnos_walker(), pullup_replace_vars_callback(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), remove_leftjoinrel_from_query(), remove_self_join_rel(), remove_self_joins_recurse(), test_bms_add_members(), transformOnConflictArbiter(), and try_partitionwise_join().

bms_add_range()

Bitmapset * bms_add_range	(	Bitmapset *	a,
		int	lower,
		int	upper
	)

Definition at line 1138 of file bitmapset.c.

{
    int         lwordnum,
                lbitnum,
                uwordnum,
                ushiftbits,
                wordnum;
 
    Assert(bms_is_valid_set(a));
 
    /* do nothing if nothing is called for, without further checking */
    if (upper < lower)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    if (lower < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    uwordnum = WORDNUM(upper);
 
    if (a == NULL)
    {
        a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
        a->type = T_Bitmapset;
        a->nwords = uwordnum + 1;
    }
    else if (uwordnum >= a->nwords)
    {
        int         oldnwords = a->nwords;
        int         i;
 
        /* ensure we have enough words to store the upper bit */
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
        a->nwords = uwordnum + 1;
        /* zero out the enlarged portion */
        i = oldnwords;
        do
        {
            a->words[i] = 0;
        } while (++i < a->nwords);
    }
 
    wordnum = lwordnum = WORDNUM(lower);
 
    lbitnum = BITNUM(lower);
    ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
 
    /*
     * Special case when lwordnum is the same as uwordnum we must perform the
     * upper and lower masking on the word.
     */
    if (lwordnum == uwordnum)
    {
        a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
            & (~(bitmapword) 0) >> ushiftbits;
    }
    else
    {
        /* turn on lbitnum and all bits left of it */
        a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
 
        /* turn on all bits for any intermediate words */
        while (wordnum < uwordnum)
            a->words[wordnum++] = ~(bitmapword) 0;
 
        /* turn on upper's bit and all bits right of it. */
        a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
    }
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}

References a, Assert, BITMAPSET_SIZE, BITNUM, BITS_PER_BITMAPWORD, elog, ERROR, fb(), i, lower(), palloc0(), repalloc(), upper(), and WORDNUM.

Referenced by add_setop_child_rel_equivalences(), ComputePartitionAttrs(), DoCopy(), ExecInitAppend(), ExecInitMergeAppend(), ExecInitPartitionExecPruning(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_partitions(), get_matching_range_bounds(), logicalrep_rel_open(), make_partition_pruneinfo(), perform_pruning_combine_step(), prune_append_rel_partitions(), test_bms_add_range(), and test_random_operations().

bms_compare()

int bms_compare	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 184 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return (b == NULL) ? 0 : -1;
    else if (b == NULL)
        return +1;
 
    /* the set with the most words must be greater */
    if (a->nwords != b->nwords)
        return (a->nwords > b->nwords) ? +1 : -1;
 
    i = a->nwords - 1;
    do
    {
        bitmapword  aw = a->words[i];
        bitmapword  bw = b->words[i];
 
        if (aw != bw)
            return (aw > bw) ? +1 : -1;
    } while (--i >= 0);
    return 0;
}

References a, Assert, b, fb(), and i.

Referenced by append_startup_cost_compare(), append_total_cost_compare(), and test_bms_compare().

bms_copy()

Bitmapset * bms_copy

(

const Bitmapset *

a

)

Definition at line 123 of file bitmapset.c.

{
    Bitmapset  *result;
    size_t      size;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return NULL;
 
    size = BITMAPSET_SIZE(a->nwords);
    result = (Bitmapset *) palloc(size);
    memcpy(result, a, size);
    return result;
}

References a, Assert, BITMAPSET_SIZE, fb(), memcpy(), palloc(), and result.

Referenced by _copyBitmapset(), add_nullingrels_if_needed(), add_outer_joins_to_relids(), adjust_child_relids(), adjust_relid_set(), afterTriggerCopyBitmap(), bms_add_members(), bms_difference(), bms_intersect(), bms_replace_members(), bms_union(), build_child_join_rel(), build_index_paths(), build_join_rel(), build_simple_grouped_rel(), calc_nestloop_required_outer(), choose_bitmap_and(), create_lateral_join_info(), CreatePartitionPruneState(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), DiscreteKnapsack(), distribute_qual_to_rels(), ExecFindMatchingSubPlans(), fetch_upper_rel(), finalize_plan(), finalize_primnode(), find_hash_columns(), find_placeholder_info(), fixup_whole_row_references(), get_join_domain_min_rels(), get_nullingrels_recurse(), get_param_path_clause_serials(), get_relation_statistics_worker(), InitPlan(), innerrel_is_unique_ext(), is_var_needed_by_join(), join_is_legal(), join_is_removable(), load_enum_cache_data(), logicalrep_partition_open(), logicalrep_relmap_update(), make_grouped_join_rel(), make_outerjoininfo(), make_partition_pruneinfo(), mark_nullable_by_grouping(), mark_stmt(), partition_bounds_copy(), perform_pruning_combine_step(), pgpa_process_unrolled_join(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_rel_from_eclass(), remove_rel_from_query(), remove_rel_from_restrictinfo(), reparameterize_path_by_child(), and test_bms_copy().

bms_del_member()

Bitmapset * bms_del_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 987 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return NULL;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    /* member can't exist.  Return 'a' unmodified */
    if (unlikely(wordnum >= a->nwords))
        return a;
 
    a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
 
    /* when last word becomes empty, trim off all trailing empty words */
    if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
    {
        /* find the last non-empty word and make that the new final word */
        for (int i = wordnum - 1; i >= 0; i--)
        {
            if (a->words[i] != 0)
            {
                a->nwords = i + 1;
                return a;
            }
        }
 
        /* the set is now empty */
        pfree(a);
        return NULL;
    }
    return a;
}

References a, Assert, BITNUM, elog, ERROR, fb(), i, pfree(), unlikely, WORDNUM, and x.

Referenced by add_nullingrels_if_needed(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), build_index_paths(), BuildParameterizedTidPaths(), ComputePartitionAttrs(), deconstruct_distribute_oj_quals(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), DoCopy(), expand_partitioned_rtentry(), finalize_plan(), finalize_primnode(), find_hash_columns(), findDefaultOnlyColumns(), fixup_whole_row_references(), get_join_domain_min_rels(), get_matching_list_bounds(), logicalrep_rel_open(), make_outerjoininfo(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_eclass(), remove_rel_from_query(), remove_rel_from_restrictinfo(), remove_self_joins_recurse(), substitute_phv_relids_walker(), test_bms_del_member(), test_random_operations(), and TopologicalSort().

bms_del_members()

Bitmapset * bms_del_members	(	Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 1280 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    /* Remove b's bits from a; we need never copy */
    if (a->nwords > b->nwords)
    {
        /*
         * We'll never need to remove trailing zero words when 'a' has more
         * words than 'b'.
         */
        i = 0;
        do
        {
            a->words[i] &= ~b->words[i];
        } while (++i < b->nwords);
    }
    else
    {
        int         lastnonzero = -1;
 
        /* we may need to remove trailing zero words from the result. */
        i = 0;
        do
        {
            a->words[i] &= ~b->words[i];
 
            /* remember the last non-zero word */
            if (a->words[i] != 0)
                lastnonzero = i;
        } while (++i < a->nwords);
 
        /* check if 'a' has become empty */
        if (lastnonzero == -1)
        {
            pfree(a);
            return NULL;
        }
 
        /* trim off any trailing zero words */
        a->nwords = lastnonzero + 1;
    }
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    return a;
}

References a, Assert, b, fb(), i, and pfree().

Referenced by adjust_group_pathkeys_for_groupagg(), build_join_rel(), calc_nestloop_required_outer(), check_index_predicates(), classify_matching_subplans(), finalize_plan(), get_join_domain_min_rels(), get_placeholder_nulling_relids(), make_outerjoininfo(), make_partition_pruneinfo(), min_join_parameterization(), NumRelids(), pullup_replace_vars_callback(), remove_self_joins_recurse(), and test_bms_del_members().

bms_difference()

Bitmapset * bms_difference	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 347 of file bitmapset.c.

{
    Bitmapset  *result;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
        return bms_copy(a);
 
    /*
     * In Postgres' usage, an empty result is a very common case, so it's
     * worth optimizing for that by testing bms_nonempty_difference().  This
     * saves us a palloc/pfree cycle compared to checking after-the-fact.
     */
    if (!bms_nonempty_difference(a, b))
        return NULL;
 
    /* Copy the left input */
    result = bms_copy(a);
 
    /* And remove b's bits from result */
    if (result->nwords > b->nwords)
    {
        /*
         * We'll never need to remove trailing zero words when 'a' has more
         * words than 'b' as the additional words must be non-zero.
         */
        i = 0;
        do
        {
            result->words[i] &= ~b->words[i];
        } while (++i < b->nwords);
    }
    else
    {
        int         lastnonzero = -1;
 
        /* we may need to remove trailing zero words from the result. */
        i = 0;
        do
        {
            result->words[i] &= ~b->words[i];
 
            /* remember the last non-zero word */
            if (result->words[i] != 0)
                lastnonzero = i;
        } while (++i < result->nwords);
 
        /* trim off trailing zero words */
        result->nwords = lastnonzero + 1;
    }
    Assert(result->nwords != 0);
 
    /* Need not check for empty result, since we handled that case above */
    return result;
}

References a, Assert, b, bms_copy(), bms_nonempty_difference(), fb(), i, and result.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_paths_to_joinrel(), check_index_predicates(), consider_new_or_clause(), create_foreignscan_plan(), create_hashjoin_plan(), create_mergejoin_plan(), create_nestloop_plan(), examine_variable(), finalize_plan(), find_placeholder_info(), make_plain_restrictinfo(), pull_varnos_walker(), remove_nulling_relids_mutator(), remove_rel_from_phvs_mutator(), remove_rel_from_query(), remove_useless_groupby_columns(), standard_planner(), and test_bms_difference().

bms_equal()

bool bms_equal	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 143 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
        if (b == NULL)
            return true;
        return false;
    }
    else if (b == NULL)
        return false;
 
    /* can't be equal if the word counts don't match */
    if (a->nwords != b->nwords)
        return false;
 
    /* check each word matches */
    i = 0;
    do
    {
        if (a->words[i] != b->words[i])
            return false;
    } while (++i < a->nwords);
 
    return true;
}

References a, Assert, b, fb(), and i.

Referenced by _equalBitmapset(), add_non_redundant_clauses(), add_path_precheck(), add_paths_to_append_rel(), afterTriggerAddEvent(), AlterPublicationTables(), assign_param_for_var(), bitmap_match(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_paths(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), ExecInitPartitionExecPruning(), extract_lateral_vars_from_PHVs(), extract_rollup_sets(), fetch_upper_rel(), find_dependent_phvs_walker(), find_join_rel(), find_param_path_info(), generate_grouped_paths(), generate_implied_equalities_for_column(), generate_partitionwise_join_paths(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), get_join_domain_min_rels(), has_join_restriction(), infer_arbiter_indexes(), innerrel_is_unique_ext(), is_safe_restriction_clause_for(), join_is_legal(), make_grouped_join_rel(), make_one_rel(), make_partitionedrel_pruneinfo(), mark_nullable_by_grouping(), match_pathkeys_to_index(), merge_clump(), pgoutput_column_list_init(), pgpa_walker_contains_feature(), pgpa_walker_contains_join(), pgpa_walker_find_scan(), pgpa_walker_join_order_matches_member(), populate_joinrel_with_paths(), pull_varnos_walker(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), set_rel_pathlist(), standard_join_search(), test_bms_equal(), test_random_offset_operations(), and try_partitionwise_join().

bms_free()

void bms_free

(

Bitmapset *

a

)

Definition at line 240 of file bitmapset.c.

{
    if (a)
        pfree(a);
}

References a, and pfree().

Referenced by check_index_only(), choose_best_statistics(), clauselist_apply_dependencies(), convert_EXISTS_sublink_to_join(), create_foreignscan_plan(), create_nestloop_plan(), deparseColumnRef(), dependencies_clauselist_selectivity(), examine_variable(), ExecAppendAsyncRequest(), ExecEndNode(), ExecReScan(), ExecReScanAppend(), ExecReScanMergeAppend(), extract_rollup_sets(), ExtractReplicaIdentity(), finalize_plan(), find_dependent_phvs_walker(), find_hash_columns(), free_child_join_sjinfo(), func_get_detail(), get_rel_sync_entry(), get_relation_statistics(), has_legal_joinclause(), has_notnull_forced_var(), heap_update(), index_unchanged_by_update(), InitExecPartitionPruneContexts(), load_enum_cache_data(), logicalrep_rel_open(), logicalrep_relmap_free_entry(), logicalrep_write_attrs(), make_join_rel(), make_plain_restrictinfo(), mark_stmt(), NumRelids(), pgpa_join_path_setup(), plpgsql_mark_local_assignment_targets(), pub_contains_invalid_column(), reduce_outer_joins_pass2(), RelationDestroyRelation(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_self_joins_recurse(), reparameterize_path_by_child(), statext_mcv_clauselist_selectivity(), test_random_offset_operations(), test_random_operations(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and try_partitionwise_join().

bms_get_singleton_member()

bool bms_get_singleton_member	(	const Bitmapset *	a,
		int *	member
	)

Definition at line 843 of file bitmapset.c.

{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return false;
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result >= 0 || HAS_MULTIPLE_ONES(w))
                return false;
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
        }
    } while (++wordnum < nwords);
 
    /* we don't expect non-NULL sets to be empty */
    Assert(result >= 0);
    *member = result;
    return true;
}

References a, Assert, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, fb(), HAS_MULTIPLE_ONES, and result.

Referenced by add_placeholders_to_base_rels(), create_lateral_join_info(), distribute_restrictinfo_to_rels(), estimate_multivariate_bucketsize(), examine_variable(), find_join_input_rel(), find_single_rel_for_clauses(), generate_base_implied_equalities_no_const(), get_common_eclass_indexes(), join_is_removable(), reduce_unique_semijoins(), replace_relid_callback(), set_base_rel_consider_startup(), statext_is_compatible_clause(), and test_bms_get_singleton_member().

bms_hash_value()

uint32 bms_hash_value

(

const Bitmapset *

a

)

Definition at line 1543 of file bitmapset.c.

{
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return 0;               /* All empty sets hash to 0 */
    return DatumGetUInt32(hash_any((const unsigned char *) a->words,
                                   a->nwords * sizeof(bitmapword)));
}

References a, Assert, DatumGetUInt32(), fb(), and hash_any().

Referenced by bitmap_hash(), and test_bms_hash_value().

bms_int_members()

Bitmapset * bms_int_members	(	Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 1228 of file bitmapset.c.

{
    int         lastnonzero;
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
    {
        pfree(a);
        return NULL;
    }
 
    /* Intersect b into a; we need never copy */
    shortlen = Min(a->nwords, b->nwords);
    lastnonzero = -1;
    i = 0;
    do
    {
        a->words[i] &= b->words[i];
 
        if (a->words[i] != 0)
            lastnonzero = i;
    } while (++i < shortlen);
 
    /* If we computed an empty result, we must return NULL */
    if (lastnonzero == -1)
    {
        pfree(a);
        return NULL;
    }
 
    /* get rid of trailing zero words */
    a->nwords = lastnonzero + 1;
 
#ifdef REALLOCATE_BITMAPSETS
    a = bms_copy_and_free(a);
#endif
 
    return a;
}

References a, Assert, b, fb(), i, Min, and pfree().

Referenced by find_nonnullable_rels_walker(), find_placeholder_info(), get_common_eclass_indexes(), get_param_path_clause_serials(), make_outerjoininfo(), make_row_comparison_op(), mbms_int_members(), perform_pruning_combine_step(), relation_is_updatable(), and test_bms_int_members().

bms_intersect()

Bitmapset * bms_intersect	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 293 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         lastnonzero;
    int         resultlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL || b == NULL)
        return NULL;
 
    /* Identify shorter and longer input; copy the shorter one */
    if (a->nwords <= b->nwords)
    {
        result = bms_copy(a);
        other = b;
    }
    else
    {
        result = bms_copy(b);
        other = a;
    }
    /* And intersect the longer input with the result */
    resultlen = result->nwords;
    lastnonzero = -1;
    i = 0;
    do
    {
        result->words[i] &= other->words[i];
 
        if (result->words[i] != 0)
            lastnonzero = i;
    } while (++i < resultlen);
    /* If we computed an empty result, we must return NULL */
    if (lastnonzero == -1)
    {
        pfree(result);
        return NULL;
    }
 
    /* get rid of trailing zero words */
    result->nwords = lastnonzero + 1;
    return result;
}

References a, Assert, b, bms_copy(), fb(), i, pfree(), and result.

Referenced by build_joinrel_tlist(), classify_matching_subplans(), create_lateral_join_info(), distribute_qual_to_rels(), find_dependent_phvs_walker(), find_em_for_rel(), get_matching_part_pairs(), identify_current_nestloop_params(), make_outerjoininfo(), match_eclasses_to_foreign_key_col(), pullup_replace_vars_callback(), rebuild_joinclause_attr_needed(), set_param_references(), test_bms_intersect(), test_random_operations(), and UpdateChangedParamSet().

bms_is_member()

bool bms_is_member	(	int	x,
		const Bitmapset *	a
	)

Definition at line 645 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    /* XXX better to just return false for x<0 ? */
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return false;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
    if (wordnum >= a->nwords)
        return false;
    if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
        return true;
    return false;
}

References a, Assert, BITNUM, elog, ERROR, fb(), WORDNUM, and x.

Referenced by add_non_redundant_clauses(), add_nulling_relids_mutator(), add_outer_joins_to_relids(), add_row_identity_var(), adjust_appendrel_attrs_mutator(), adjust_child_relids(), adjust_relid_set(), adjust_rowcount_for_semijoins(), bms_member_index(), build_joinrel_tlist(), check_index_predicates(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clause_selectivity_ext(), clauselist_selectivity_ext(), clauselist_selectivity_or(), ComputePartitionAttrs(), consider_groupingsets_paths(), contain_invalid_rfcolumn_walker(), contain_placeholder_references_walker(), cost_incremental_sort(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_path(), createTableConstraints(), deconstruct_distribute_oj_quals(), DefineIndex(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), DoCopy(), dropconstraint_internal(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), ExecBuildSlotValueDescription(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecEvalGroupingFunc(), ExecGetRangeTableRelation(), ExecInitLockRows(), ExecInitModifyTable(), ExecRelationIsTargetRelation(), ExecScanFetch(), execute_attr_map_cols(), expand_indexqual_rowcompare(), expand_single_inheritance_child(), ExplainSubPlans(), extract_lateral_vars_from_PHVs(), extractRemainingColumns(), ExtractReplicaIdentity(), fetch_remote_table_info(), filter_event_trigger(), find_hash_columns(), find_modifytable_subplan(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), gen_partprune_steps_internal(), gen_prune_steps_from_opexps(), generate_base_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_expression_sortgroupref(), get_foreign_key_join_selectivity(), get_join_domain_min_rels(), get_matching_hash_bounds(), get_memoize_path(), get_placeholder_nulling_relids(), get_translated_update_targetlist(), get_variable(), get_xmltable(), group_similar_or_args(), has_notnull_forced_var(), has_partition_attrs(), hashagg_spill_tuple(), HeapDetermineColumnsInfo(), identify_current_nestloop_params(), index_expression_changed_walker(), index_unchanged_by_update(), InitPartitionPruneContext(), InitPlan(), is_foreign_param(), is_pseudo_constant_for_index(), is_subquery_var(), is_var_in_aggref_only(), IsBinaryTidClause(), isPlainForeignVar(), IsTidEqualAnyClause(), join_clause_is_movable_to(), join_is_removable(), lo_manage(), logicalrep_rel_mark_updatable(), logicalrep_should_publish_column(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_expr(), mark_invalid_subplans_as_finished(), mark_rels_nulled_by_join(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), mbms_is_member(), MergeAttributes(), partitions_are_ordered(), perform_pruning_base_step(), pgpa_classify_alternative_subplans(), plpgsql_param_fetch(), postgresExplainForeignScan(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pub_collist_validate(), pub_contains_invalid_column(), pullup_replace_vars_callback(), rangeTableEntry_used_walker(), rebuild_joinclause_attr_needed(), RememberWholeRowDependentForRebuilding(), remove_leftjoinrel_from_query(), remove_nulling_relids_mutator(), remove_rel_from_eclass(), remove_rel_from_query(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), replace_relid_callback(), rewriteTargetListIU(), rewriteValuesRTE(), ScanRelIsReadOnly(), semijoin_target_ok(), set_join_column_names(), set_rtable_names(), show_modifytable_info(), statext_mcv_clauselist_selectivity(), subquery_planner(), substitute_phv_relids_walker(), test_bms_is_member(), test_random_operations(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), tsvector_update_trigger(), tuples_equal(), update_eclasses(), use_physical_tlist(), validate_va_cols_list(), var_is_nonnullable(), and view_cols_are_auto_updatable().

bms_is_subset()

bool bms_is_subset	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 547 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return true;            /* empty set is a subset of anything */
    if (b == NULL)
        return false;
 
    /* 'a' can't be a subset of 'b' if it contains more words */
    if (a->nwords > b->nwords)
        return false;
 
    /* Check all 'a' members are set in 'b' */
    i = 0;
    do
    {
        if ((a->words[i] & ~b->words[i]) != 0)
            return false;
    } while (++i < a->nwords);
    return true;
}

References a, Assert, b, fb(), and i.

Referenced by add_child_rel_equivalences(), add_outer_joins_to_relids(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_attr_needed(), add_vars_to_targetlist(), build_joinrel_tlist(), check_functional_grouping(), check_index_only(), choose_best_statistics(), clause_sides_match_join(), compute_semijoin_info(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_agg_clause_infos(), create_index_paths(), distribute_qual_to_rels(), eager_aggregation_possible_for_relation(), eclass_already_used(), eclass_useful_for_merging(), extract_lateral_vars_from_PHVs(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), find_join_domain(), foreign_join_ok(), generate_implied_equalities_for_column(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_joinrel_parampathinfo(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_join_order_restriction(), have_partkey_equi_join(), identify_current_nestloop_params(), initial_cost_mergejoin(), innerrel_is_unique_ext(), is_simple_subquery(), join_clause_is_movable_into(), join_is_legal(), join_is_removable(), jointree_contains_lateral_outer_refs(), make_grouped_join_rel(), make_outerjoininfo(), pg_get_expr_worker(), pgpa_walker_contains_no_gather(), populate_joinrel_with_paths(), process_implied_equality(), process_subquery_nestloop_params(), pullup_replace_vars_callback(), remove_rel_from_query(), reparameterize_path(), replace_nestloop_params_mutator(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), statext_mcv_clauselist_selectivity(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), test_bms_is_subset(), try_partial_nestloop_path(), and use_physical_tlist().

bms_join()

Bitmapset * bms_join	(	Bitmapset *	a,
		Bitmapset *	b
	)

Definition at line 1349 of file bitmapset.c.

{
    Bitmapset  *result;
    Bitmapset  *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        b = bms_copy_and_free(b);
#endif
 
        return b;
    }
    if (b == NULL)
    {
#ifdef REALLOCATE_BITMAPSETS
        a = bms_copy_and_free(a);
#endif
 
        return a;
    }
 
    /* Identify shorter and longer input; use longer one as result */
    if (a->nwords < b->nwords)
    {
        result = b;
        other = a;
    }
    else
    {
        result = a;
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    if (other != result)        /* pure paranoia */
        pfree(other);
 
#ifdef REALLOCATE_BITMAPSETS
    result = bms_copy_and_free(result);
#endif
 
    return result;
}

References a, Assert, b, fb(), i, pfree(), and result.

Referenced by add_paths_to_joinrel(), alias_relid_set(), build_joinrel_tlist(), finalize_primnode(), find_nonnullable_rels_walker(), get_partkey_exec_paramids(), get_relids_in_jointree(), make_partition_pruneinfo(), process_equivalence(), pull_up_sublinks_jointree_recurse(), pull_varnos_walker(), test_bms_join(), and UpdateChangedParamSet().

bms_make_singleton()

Bitmapset * bms_make_singleton

(

int

x

)

Definition at line 217 of file bitmapset.c.

{
    Bitmapset  *result;
    int         wordnum,
                bitnum;
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
    result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
    result->type = T_Bitmapset;
    result->nwords = wordnum + 1;
    result->words[wordnum] = ((bitmapword) 1 << bitnum);
    return result;
}

References BITMAPSET_SIZE, BITNUM, elog, ERROR, fb(), palloc0(), result, WORDNUM, and x.

Referenced by add_row_identity_var(), ATExecDropColumn(), ATPrepAlterColumnType(), bms_add_member(), build_base_rel_tlists(), build_simple_rel(), CopyFrom(), create_edata_for_relation(), create_estate_for_relation(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseReturningList(), DiscreteKnapsack(), examine_simple_variable(), expand_inherited_rtentry(), extract_lateral_references(), find_dependent_phvs(), find_dependent_phvs_in_jointree(), find_nonnullable_rels_walker(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_range_bounds(), get_relids_in_jointree(), initialize_change_context(), load_enum_cache_data(), make_group_input_target(), make_pathkeys_for_sortclauses_extended(), mark_nullable_by_grouping(), pg_column_is_updatable(), pg_get_expr_worker(), pgpa_build_scan(), pgpa_walker_join_order_matches_member(), pgpa_walker_would_advise(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), rebuild_lateral_attr_needed(), reconsider_full_join_clause(), reduce_outer_joins(), reduce_outer_joins_pass1(), remove_rel_from_phvs(), remove_rel_from_query(), rewriteTargetView(), set_subqueryscan_references(), set_upper_references(), split_pathtarget_walker(), subquery_planner(), test_bms_make_singleton(), and transform_MERGE_to_join().

bms_member_index()

int bms_member_index	(	Bitmapset *	a,
		int	x
	)

Definition at line 674 of file bitmapset.c.

{
    int         bitnum;
    int         wordnum;
    int         result = 0;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    /* return -1 if not a member of the bitmap */
    if (!bms_is_member(x, a))
        return -1;
 
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
 
    /* count bits in preceding words */
    result += pg_popcount((const char *) a->words,
                          wordnum * sizeof(bitmapword));
 
    /*
     * Now add bits of the last word, but only those before the item. We can
     * do that by applying a mask and then using popcount again. To get
     * 0-based index, we want to count only preceding bits, not the item
     * itself, so we subtract 1.
     */
    mask = ((bitmapword) 1 << bitnum) - 1;
    result += bmw_popcount(a->words[wordnum] & mask);
 
    return result;
}

References a, Assert, BITNUM, bms_is_member(), bmw_popcount, fb(), pg_popcount(), result, WORDNUM, and x.

Referenced by clauselist_apply_dependencies(), mcv_get_match_bitmap(), mcv_match_expression(), and test_bms_member_index().

bms_membership()

BMS_Membership bms_membership

(

const Bitmapset *

a

)

Definition at line 900 of file bitmapset.c.

{
    BMS_Membership result = BMS_EMPTY_SET;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return BMS_EMPTY_SET;
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
                return BMS_MULTIPLE;
            result = BMS_SINGLETON;
        }
    } while (++wordnum < nwords);
    return result;
}

References a, Assert, BMS_EMPTY_SET, BMS_MULTIPLE, BMS_SINGLETON, fb(), HAS_MULTIPLE_ONES, and result.

Referenced by add_base_clause_to_rel(), add_child_join_rel_equivalences(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_compatible_clause(), dependency_is_compatible_expression(), distribute_qual_to_rels(), extract_lateral_vars_from_PHVs(), find_nonnullable_rels_walker(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), get_foreign_key_join_selectivity(), grouping_planner(), overexplain_bitmapset_list(), pgpa_build_scan(), pgpa_join_path_setup(), pgpa_joinrel_setup(), pgpa_output_join_member(), pgpa_output_query_feature(), pgpa_output_scan_strategy(), pgpa_output_simple_strategy(), process_implied_equality(), rebuild_joinclause_attr_needed(), relation_has_unique_index_for(), remove_self_join_rel(), remove_self_joins_recurse(), remove_useless_groupby_columns(), replace_relid_callback(), set_subquery_pathlist(), set_tablesample_rel_pathlist(), setup_eager_aggregation(), split_selfjoin_quals(), statext_mcv_clauselist_selectivity(), and test_bms_membership().

bms_next_member()

int bms_next_member	(	const Bitmapset *	a,
		int	prevbit
	)

Definition at line 1425 of file bitmapset.c.

{
    unsigned int currbit = prevbit;
    int         nwords;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return -2;
    nwords = a->nwords;
 
    /* use an unsigned int to avoid the risk that int overflows */
    currbit++;
    mask = (~(bitmapword) 0) << BITNUM(currbit);
    for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];
 
        /* ignore bits before currbit */
        w &= mask;
 
        if (w != 0)
        {
            int         result;
 
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
            return result;
        }
 
        /* in subsequent words, consider all bits */
        mask = (~(bitmapword) 0);
    }
    return -2;
}

References a, Assert, BITNUM, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, fb(), result, and WORDNUM.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_join_clause_to_rels(), add_part_relids(), adjust_group_pathkeys_for_groupagg(), adjust_view_column_set(), alias_relid_set(), all_rows_selectable(), apply_scanjoin_target_to_paths(), approximate_joinrel_size(), attnumstoint2vector(), build_attnums_array(), check_relation_privileges(), check_selective_binary_conversion(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), clauselist_apply_dependencies(), ComputePartitionAttrs(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_partitionwise_grouping_paths(), CreatePartitionPruneState(), CreateStatistics(), DefineIndex(), deparseLockingClause(), dependencies_clauselist_selectivity(), DoCopy(), eager_aggregation_possible_for_relation(), eclass_member_iterator_next(), EstimateParamExecSpace(), ExecAppendAsyncBegin(), ExecAppendAsyncEventWait(), ExecAppendAsyncRequest(), ExecCheckOneRelPerms(), ExecCheckPermissionsModified(), ExecInitAgg(), ExecInitAppend(), ExecInitMergeAppend(), ExecMergeAppend(), ExecReScanAppend(), ExecScanReScan(), ExecSetParamPlanMulti(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_dependent_phvs_in_jointree(), find_hash_columns(), find_matching_subplans_recurse(), fixup_inherited_columns(), format_expr_params(), generate_base_implied_equalities(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_loop_count(), get_matching_partitions(), get_placeholder_nulling_relids(), grouping_planner(), has_notnull_forced_var(), has_relevant_eclass_joinclause(), have_relevant_eclass_joinclause(), HeapDetermineColumnsInfo(), InitExecPartitionPruneContexts(), logicalrep_get_attrs_str(), logicalrep_rel_mark_updatable(), lookup_var_attr_stats(), make_build_data(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), mark_rels_nulled_by_join(), match_eclasses_to_foreign_key_col(), outBitmapset(), overexplain_bitmapset(), overexplain_bitmapset_list(), pgpa_bms_to_cstring(), pgpa_compute_identifiers_by_relids(), pgpa_filter_out_join_relids(), pgpa_output_relations(), pgpa_plan_walker(), pgpa_planner_apply_join_path_advice(), pgpa_planner_apply_joinrel_advice(), pgpa_planner_apply_scan_advice(), pgpa_trove_set_flags(), pgpa_trove_slice_lookup(), postgresBeginForeignScan(), postgresExplainForeignScan(), postgresPlanForeignModify(), pub_contains_invalid_column(), publication_add_relation(), pullup_replace_vars_callback(), remove_join_clause_from_rels(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_results_recurse(), remove_useless_self_joins(), SerializeParamExecParams(), show_result_replacement_info(), test_bms_next_member(), test_random_offset_operations(), test_random_operations(), and unique_nonjoin_rtekind().

bms_nonempty_difference()

bool bms_nonempty_difference	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 769 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return false;
    if (b == NULL)
        return true;
    /* if 'a' has more words then it must contain additional members */
    if (a->nwords > b->nwords)
        return true;
    /* Check all 'a' members are set in 'b' */
    i = 0;
    do
    {
        if ((a->words[i] & ~b->words[i]) != 0)
            return true;
    } while (++i < a->nwords);
    return false;
}

References a, Assert, b, fb(), and i.

Referenced by add_placeholders_to_base_rels(), add_placeholders_to_joinrel(), allow_star_schema_join(), bms_difference(), build_joinrel_tlist(), ExecReScanMemoize(), foreign_join_ok(), is_var_needed_by_join(), test_bms_nonempty_difference(), and use_physical_tlist().

bms_num_members()

int bms_num_members

(

const Bitmapset *

a

)

Definition at line 879 of file bitmapset.c.

{
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return 0;
 
    /* fast-path for common case */
    if (a->nwords == 1)
        return bmw_popcount(a->words[0]);
 
    return pg_popcount((const char *) a->words,
                       a->nwords * sizeof(bitmapword));
}

References a, Assert, bmw_popcount, fb(), and pg_popcount().

Referenced by adjust_group_pathkeys_for_groupagg(), attnumstoint2vector(), build_attnums_array(), build_join_rel(), BuildRelationExtStatistics(), choose_best_statistics(), clauselist_apply_dependencies(), ComputeExtStatisticsRows(), estimate_multivariate_ndistinct(), ExecAppendAsyncBegin(), ExecCheckPermissions(), ExecInitAppend(), ExecInitMergeAppend(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_hash_columns(), find_strongest_dependency(), gen_partprune_steps_internal(), get_matching_hash_bounds(), get_matching_part_pairs(), get_steps_using_prefix_recurse(), InitExecPartitionPruneContexts(), logicalrep_report_missing_or_gen_attrs(), lookup_var_attr_stats(), make_build_data(), make_partition_pruneinfo(), make_plain_restrictinfo(), mark_invalid_subplans_as_finished(), mcv_match_expression(), NumRelids(), pgpa_get_join_state(), remove_self_joins_recurse(), replace_relid_callback(), SerializeParamExecParams(), split_selfjoin_quals(), test_bms_num_members(), and test_random_operations().

bms_offset_members()

Bitmapset * bms_offset_members	(	const Bitmapset *	a,
		int	offset
	)

Definition at line 419 of file bitmapset.c.

{
    Bitmapset  *result;
    int         offset_words;
    int         offset_bits;
    int         new_nwords;
    int         old_nwords;
    int32       high_bit;
    int         old_highest;
    int         new_highest;
 
    Assert(bms_is_valid_set(a));
 
    /* nothing to do for empty sets */
    if (a == NULL)
        return NULL;
 
    old_nwords = a->nwords;
    offset_words = WORDNUM(offset);
    offset_bits = BITNUM(offset);
    high_bit = bmw_leftmost_one_pos(a->words[a->nwords - 1]);
    old_highest = (old_nwords - 1) * BITS_PER_BITMAPWORD + high_bit;
 
    /* don't create a set with a member that doesn't fit into an int32 */
    if (pg_add_s32_overflow(old_highest, offset, &new_highest))
        elog(ERROR, "bitmapset overflow");
    /* return NULL if the new set would be empty */
    else if (new_highest < 0)
        return NULL;
 
    new_nwords = WORDNUM(new_highest) + 1;
    result = (Bitmapset *) palloc0(BITMAPSET_SIZE(new_nwords));
    result->type = T_Bitmapset;
    result->nwords = new_nwords;
 
    /* handle zero and positive offsets (bitshift left) */
    if (offset >= 0)
    {
        /*
         * We special-case offsetting only by whole words, so we don't have to
         * special-case bitshifting by BITS_PER_BITMAPWORD places, which has
         * an undefined behavior.
         */
        if (offset_bits == 0)
        {
            int         i = 0;
 
            /*
             * The old set is guaranteed to have at least 1 word, so use
             * do/while to save the redundant initial loop bounds check.
             */
            do
            {
                Assert(i + offset_words < new_nwords);
                result->words[i + offset_words] = a->words[i];
            } while (++i < old_nwords);
        }
        else
        {
            int         carry_bits = BITS_PER_BITMAPWORD - offset_bits;
            bitmapword  prev_carry = 0;
            int         i = 0;
 
            do
            {
                bitmapword  carry = (a->words[i] >> carry_bits);
 
                Assert(i + offset_words < new_nwords);
                /* shift bits up and carry bits from the previous word */
                result->words[i + offset_words] = (a->words[i] << offset_bits) | prev_carry;
                prev_carry = carry;
            } while (++i < old_nwords);
            result->words[new_nwords - 1] |= prev_carry;
        }
    }
 
    /* handle negative offset (bitshift right) */
    else
    {
        /* make the negative offset_words and offset_bits positive */
        offset_words = 0 - offset_words;
        offset_bits = 0 - offset_bits;
 
        /* as above, special case shifting only by whole words */
        if (offset_bits == 0)
        {
            int         i = 0;
 
            do
            {
                Assert(i + offset_words < old_nwords);
                result->words[i] = a->words[i + offset_words];
            } while (++i < new_nwords);
        }
        else
        {
            int         carry_bits = BITS_PER_BITMAPWORD - offset_bits;
            bitmapword  prev_carry = 0;
            int         i = new_nwords - 1;
 
            /* carry bits from any word just above where the loop starts */
            if (old_nwords > new_nwords + offset_words)
                prev_carry = (a->words[new_nwords + offset_words] << carry_bits);
 
            /*
             * We loop backward over the array so we correctly carry bits from
             * higher words.
             */
            do
            {
                bitmapword  carry = (a->words[i + offset_words] << carry_bits);
 
                Assert(i + offset_words < old_nwords);
 
                /* shift bits down and carry bits from the previous word */
                result->words[i] = (a->words[i + offset_words] >> offset_bits) | prev_carry;
                prev_carry = carry;
            } while (--i >= 0);
        }
    }
 
    return result;
}

References a, Assert, BITMAPSET_SIZE, BITNUM, BITS_PER_BITMAPWORD, bmw_leftmost_one_pos, elog, ERROR, fb(), i, palloc0(), pg_add_s32_overflow(), result, and WORDNUM.

Referenced by has_notnull_forced_var(), offset_relid_set(), OffsetVarNodes_walker(), statext_is_compatible_clause(), test_bms_offset_members(), and test_random_offset_operations().

bms_overlap()

bool bms_overlap	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 710 of file bitmapset.c.

{
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL || b == NULL)
        return false;
    /* Check words in common */
    shortlen = Min(a->nwords, b->nwords);
    i = 0;
    do
    {
        if ((a->words[i] & b->words[i]) != 0)
            return true;
    } while (++i < shortlen);
    return false;
}

References a, Assert, b, fb(), i, and Min.

Referenced by add_child_join_rel_equivalences(), add_nulling_relids_mutator(), add_paths_to_joinrel(), adjust_child_relids_multilevel(), allow_star_schema_join(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), choose_bitmap_and(), classify_matching_subplans(), compute_semijoin_info(), create_nestloop_path(), distribute_qual_to_rels(), eager_aggregation_possible_for_relation(), eclass_useful_for_merging(), examine_variable(), ExecInitGenerated(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), extract_lateral_vars_from_PHVs(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_notnull_forced_var(), has_partition_attrs(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), identify_current_nestloop_params(), join_clause_is_movable_into(), join_clause_is_movable_to(), join_is_legal(), join_is_removable(), join_search_one_level(), make_join_rel(), make_outerjoininfo(), make_plain_restrictinfo(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), mbms_overlap_sets(), partitions_are_ordered(), path_is_reparameterizable_by_child(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), remove_nulling_relids_mutator(), remove_self_joins_recurse(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), set_append_rel_size(), subbuild_joinrel_restrictlist(), test_bms_overlap(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and try_partitionwise_join().

bms_overlap_list()

bool bms_overlap_list	(	const Bitmapset *	a,
		const List *	b
	)

Definition at line 736 of file bitmapset.c.

{
    ListCell   *lc;
    int         wordnum,
                bitnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL || b == NIL)
        return false;
 
    foreach(lc, b)
    {
        int         x = lfirst_int(lc);
 
        if (x < 0)
            elog(ERROR, "negative bitmapset member not allowed");
        wordnum = WORDNUM(x);
        bitnum = BITNUM(x);
        if (wordnum < a->nwords)
            if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
                return true;
    }
 
    return false;
}

References a, Assert, b, BITNUM, elog, ERROR, fb(), lfirst_int, NIL, WORDNUM, and x.

Referenced by preprocess_grouping_sets(), and test_bms_overlap_list().

bms_prev_member()

int bms_prev_member	(	const Bitmapset *	a,
		int	prevbit
	)

Definition at line 1487 of file bitmapset.c.

{
    unsigned int currbit;
    int         ushiftbits;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    /*
     * If set is NULL or if there are no more bits to the right then we've
     * nothing to do.
     */
    if (a == NULL || prevbit == 0)
        return -2;
 
    /* Validate callers didn't give us something out of range */
    Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD));
 
    /*
     * Transform -1 (or any negative number) to the highest possible bit we
     * could have set.  We do this in unsigned math to avoid the risk of
     * overflowing a signed int.
     */
    if (prevbit < 0)
        currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
    else
        currbit = prevbit - 1;
 
    ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
    mask = (~(bitmapword) 0) >> ushiftbits;
    for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
    {
        bitmapword  w = a->words[wordnum];
 
        /* mask out bits left of currbit */
        w &= mask;
 
        if (w != 0)
        {
            int         result;
 
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_leftmost_one_pos(w);
            return result;
        }
 
        /* in subsequent words, consider all bits */
        mask = (~(bitmapword) 0);
    }
    return -2;
}

References a, Assert, BITNUM, BITS_PER_BITMAPWORD, bmw_leftmost_one_pos, fb(), result, and WORDNUM.

Referenced by choose_next_subplan_locally(), and test_bms_prev_member().

bms_replace_members()

Bitmapset * bms_replace_members	(	Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 1091 of file bitmapset.c.

{
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
    {
        pfree(a);
        return NULL;
    }
 
    if (a->nwords < b->nwords)
        a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
 
    i = 0;
    do
    {
        a->words[i] = b->words[i];
    } while (++i < b->nwords);
 
    a->nwords = b->nwords;
 
#ifdef REALLOCATE_BITMAPSETS
 
    /*
     * There's no guarantee that the repalloc returned a new pointer, so copy
     * and free unconditionally here.
     */
    a = bms_copy_and_free(a);
#endif
 
    return a;
}

References a, Assert, b, BITMAPSET_SIZE, bms_copy(), fb(), i, pfree(), and repalloc().

Referenced by DiscreteKnapsack(), and test_bms_replace_members().

bms_singleton_member()

int bms_singleton_member

(

const Bitmapset *

a

)

Definition at line 800 of file bitmapset.c.

{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        elog(ERROR, "bitmapset is empty");
 
    nwords = a->nwords;
    wordnum = 0;
    do
    {
        bitmapword  w = a->words[wordnum];
 
        if (w != 0)
        {
            if (result >= 0 || HAS_MULTIPLE_ONES(w))
                elog(ERROR, "bitmapset has multiple members");
            result = wordnum * BITS_PER_BITMAPWORD;
            result += bmw_rightmost_one_pos(w);
        }
    } while (++wordnum < nwords);
 
    /* we don't expect non-NULL sets to be empty */
    Assert(result >= 0);
    return result;
}

References a, Assert, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, elog, ERROR, fb(), HAS_MULTIPLE_ONES, and result.

Referenced by fix_append_rel_relids(), get_matching_part_pairs(), overexplain_bitmapset_list(), remove_useless_joins(), split_selfjoin_quals(), and test_bms_singleton_member().

bms_subset_compare()

BMS_Comparison bms_subset_compare	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 580 of file bitmapset.c.

{
    BMS_Comparison result;
    int         shortlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
        if (b == NULL)
            return BMS_EQUAL;
        return BMS_SUBSET1;
    }
    if (b == NULL)
        return BMS_SUBSET2;
 
    /* Check common words */
    result = BMS_EQUAL;         /* status so far */
    shortlen = Min(a->nwords, b->nwords);
    i = 0;
    do
    {
        bitmapword  aword = a->words[i];
        bitmapword  bword = b->words[i];
 
        if ((aword & ~bword) != 0)
        {
            /* a is not a subset of b */
            if (result == BMS_SUBSET1)
                return BMS_DIFFERENT;
            result = BMS_SUBSET2;
        }
        if ((bword & ~aword) != 0)
        {
            /* b is not a subset of a */
            if (result == BMS_SUBSET2)
                return BMS_DIFFERENT;
            result = BMS_SUBSET1;
        }
    } while (++i < shortlen);
    /* Check extra words */
    if (a->nwords > b->nwords)
    {
        /* if a has more words then a is not a subset of b */
        if (result == BMS_SUBSET1)
            return BMS_DIFFERENT;
        return BMS_SUBSET2;
    }
    else if (a->nwords < b->nwords)
    {
        /* if b has more words then b is not a subset of a */
        if (result == BMS_SUBSET2)
            return BMS_DIFFERENT;
        return BMS_SUBSET1;
    }
    return result;
}

References a, Assert, b, BMS_DIFFERENT, BMS_EQUAL, BMS_SUBSET1, BMS_SUBSET2, fb(), i, Min, and result.

Referenced by add_path(), consider_index_join_outer_rels(), remove_useless_groupby_columns(), set_cheapest(), and test_bms_subset_compare().

bms_union()

Bitmapset * bms_union	(	const Bitmapset *	a,
		const Bitmapset *	b
	)

Definition at line 252 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    Assert(bms_is_valid_set(a));
    Assert(bms_is_valid_set(b));
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
        return bms_copy(a);
    /* Identify shorter and longer input; copy the longer one */
    if (a->nwords <= b->nwords)
    {
        result = bms_copy(b);
        other = a;
    }
    else
    {
        result = bms_copy(a);
        other = b;
    }
    /* And union the shorter input into the result */
    otherlen = other->nwords;
    i = 0;
    do
    {
        result->words[i] |= other->words[i];
    } while (++i < otherlen);
    return result;
}

References a, Assert, b, bms_copy(), fb(), i, and result.

Referenced by add_nulling_relids_mutator(), build_join_rel(), build_joinrel_restrictlist(), BuildParameterizedTidPaths(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), check_index_predicates(), check_relation_privileges(), compute_semijoin_info(), consider_index_join_outer_rels(), create_hashjoin_plan(), create_join_clause(), create_mergejoin_plan(), create_nestloop_plan(), deconstruct_distribute(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), deconstruct_recurse(), ExecConstraints(), ExecGetAllUpdatedCols(), ExecPartitionCheckEmitError(), ExecWithCheckOptions(), finalize_plan(), find_hash_columns(), foreign_join_ok(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), generate_nonunion_paths(), generate_recursion_path(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), get_rel_all_updated_cols(), get_tuple_desc(), has_legal_joinclause(), identify_current_nestloop_params(), index_unchanged_by_update(), join_is_removable(), make_join_rel(), make_outerjoininfo(), make_plain_restrictinfo(), markNullableIfNeeded(), min_join_parameterization(), pgpa_trove_lookup(), postgresGetForeignPaths(), pull_up_sublinks_jointree_recurse(), reduce_outer_joins_pass1(), reduce_unique_semijoins(), remove_leftjoinrel_from_query(), ReportNotNullViolationError(), resolve_special_varno(), rewriteTargetView(), substitute_phv_relids_walker(), test_bms_union(), test_random_operations(), and try_partitionwise_join().