bitmapset.h File Reference

#include "nodes/nodes.h"

Include dependency graph for bitmapset.h:

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

Go to the source code of this file.

Data Structures
struct	Bitmapset

Macros
#define	BITS_PER_BITMAPWORD   32
#define	bmw_leftmost_one_pos(w)   pg_leftmost_one_pos32(w)
#define	bmw_rightmost_one_pos(w)   pg_rightmost_one_pos32(w)
#define	bmw_popcount(w)   pg_popcount32(w)
#define	bms_is_empty(a)   ((a) == NULL)

Typedefs
typedef uint32	bitmapword
typedef int32	signedbitmapword
typedef struct Bitmapset	Bitmapset

Enumerations
enum	BMS_Comparison { BMS_EQUAL , BMS_SUBSET1 , BMS_SUBSET2 , BMS_DIFFERENT }
enum	BMS_Membership { BMS_EMPTY_SET , BMS_SINGLETON , BMS_MULTIPLE }

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)
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 struct 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

BITS_PER_BITMAPWORD

#define BITS_PER_BITMAPWORD   32

Definition at line 43 of file bitmapset.h.

bms_is_empty

#define bms_is_empty

(

a

)

((a) == NULL)

Definition at line 118 of file bitmapset.h.

bmw_leftmost_one_pos

#define bmw_leftmost_one_pos

(

w

)

pg_leftmost_one_pos32(w)

Definition at line 78 of file bitmapset.h.

bmw_popcount

#define bmw_popcount

(

w

)

pg_popcount32(w)

Definition at line 80 of file bitmapset.h.

bmw_rightmost_one_pos

#define bmw_rightmost_one_pos

(

w

)

pg_rightmost_one_pos32(w)

Definition at line 79 of file bitmapset.h.

Typedef Documentation

Bitmapset

typedef struct Bitmapset Bitmapset

bitmapword

typedef uint32 bitmapword

Definition at line 44 of file bitmapset.h.

signedbitmapword

typedef int32 signedbitmapword

Definition at line 45 of file bitmapset.h.

Enumeration Type Documentation

BMS_Comparison

enum BMS_Comparison

Enumerator
BMS_EQUAL
BMS_SUBSET1
BMS_SUBSET2
BMS_DIFFERENT

Definition at line 60 of file bitmapset.h.

{
    BMS_EQUAL,                  /* sets are equal */
    BMS_SUBSET1,                /* first set is a subset of the second */
    BMS_SUBSET2,                /* second set is a subset of the first */
    BMS_DIFFERENT,              /* neither set is a subset of the other */
} BMS_Comparison;

BMS_Membership

enum BMS_Membership

Enumerator
BMS_EMPTY_SET
BMS_SINGLETON
BMS_MULTIPLE

Definition at line 69 of file bitmapset.h.

{
    BMS_EMPTY_SET,              /* 0 members */
    BMS_SINGLETON,              /* 1 member */
    BMS_MULTIPLE,               /* >1 member */
} BMS_Membership;

Function Documentation

bitmap_hash()

uint32 bitmap_hash ( const void *  key, Size  keysize  )

extern

Definition at line 1418 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  )

extern

Definition at line 1428 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  )

extern

Definition at line 799 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(), do_analyze_rel(), DoCopy(), dropconstraint_internal(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecInitAgg(), ExecInitAppend(), ExecInitGenerated(), 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_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(), 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(), has_notnull_forced_var(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), InitExecPartitionPruneContexts(), 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(), offset_relid_set(), offset_relid_set(), 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_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(), stat_covers_expressions(), statext_is_compatible_clause(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), test_bms_add_member(), test_random_operations(), transformGroupClause(), transformGroupClauseList(), transformInsertStmt(), transformMergeStmt(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), try_partitionwise_join(), use_physical_tlist(), and view_cols_are_auto_updatable().

bms_add_members()

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

extern

Definition at line 901 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, Bitmapset::nwords, pfree(), and Bitmapset::words.

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(), 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  )

extern

Definition at line 1003 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  )

extern

Definition at line 183 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 )

extern

Definition at line 122 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(), and palloc().

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(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), 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  )

extern

Definition at line 852 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_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  )

extern

Definition at line 1145 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  )

extern

Definition at line 346 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, Bitmapset::nwords, and Bitmapset::words.

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(), examine_variable(), finalize_plan(), find_placeholder_info(), make_plain_restrictinfo(), pull_varnos_walker(), remove_nulling_relids_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  )

extern

Definition at line 142 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(), 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(), and try_partitionwise_join().

bms_free()

void bms_free ( Bitmapset *  a )

extern

Definition at line 239 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_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(), 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_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  )

extern

Definition at line 708 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(), and HAS_MULTIPLE_ONES.

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 )

extern

Definition at line 1402 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  )

extern

Definition at line 1093 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  )

extern

Definition at line 292 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, Bitmapset::nwords, pfree(), and Bitmapset::words.

Referenced by build_joinrel_tlist(), classify_matching_subplans(), create_lateral_join_info(), distribute_qual_to_rels(), 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  )

extern

Definition at line 510 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(), do_analyze_rel(), DoCopy(), dropconstraint_internal(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), ExecBuildSlotValueDescription(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecEvalGroupingFunc(), ExecGetRangeTableRelation(), ExecInitLockRows(), ExecInitModifyTable(), 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(), 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(), remove_leftjoinrel_from_query(), remove_nulling_relids_mutator(), remove_rel_from_eclass(), remove_rel_from_query(), 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(), 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(), var_is_nonnullable(), and view_cols_are_auto_updatable().

bms_is_subset()

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

extern

Definition at line 412 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(), 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  )

extern

Definition at line 1214 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, Bitmapset::nwords, pfree(), and Bitmapset::words.

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 )

extern

Definition at line 216 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(), Bitmapset::nwords, palloc0(), WORDNUM, Bitmapset::words, 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(), 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(), 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_query(), 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  )

extern

Definition at line 539 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(), 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 )

extern

Definition at line 765 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(), and HAS_MULTIPLE_ONES.

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(), 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  )

extern

Definition at line 1290 of file bitmapset.c.

{
    int         nwords;
    bitmapword  mask;
 
    Assert(bms_is_valid_set(a));
 
    if (a == NULL)
        return -2;
    nwords = a->nwords;
    prevbit++;
    mask = (~(bitmapword) 0) << BITNUM(prevbit);
    for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];
 
        /* ignore bits before prevbit */
        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(), 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(), offset_relid_set(), offset_relid_set(), outBitmapset(), overexplain_bitmapset(), overexplain_bitmapset_list(), 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(), statext_is_compatible_clause(), test_bms_next_member(), and test_random_operations().

bms_nonempty_difference()

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

extern

Definition at line 634 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 )

extern

Definition at line 744 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(), remove_self_joins_recurse(), replace_relid_callback(), SerializeParamExecParams(), split_selfjoin_quals(), test_bms_num_members(), and test_random_operations().

bms_overlap()

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

extern

Definition at line 575 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(), 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 struct List *  b  )

extern

bms_prev_member()

int bms_prev_member ( const Bitmapset *  a, int  prevbit  )

extern

Definition at line 1350 of file bitmapset.c.

{
    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 <= a->nwords * BITS_PER_BITMAPWORD);
    Assert(prevbit >= -1);
 
    /* transform -1 to the highest possible bit we could have set */
    if (prevbit == -1)
        prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
    else
        prevbit--;
 
    ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
    mask = (~(bitmapword) 0) >> ushiftbits;
    for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
    {
        bitmapword  w = a->words[wordnum];
 
        /* mask out bits left of prevbit */
        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(), 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  )

extern

Definition at line 956 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 )

extern

Definition at line 665 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(), and HAS_MULTIPLE_ONES.

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  )

extern

Definition at line 445 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, and Min.

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  )

extern

Definition at line 251 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 Bitmapset::words.

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_join_clause(), 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(), 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().