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	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_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 105 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
	)

Definition at line 1173 of file bitmapset.c.

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

References Assert(), bms_hash_value(), and sort-test::key.

Referenced by build_join_rel_hash().

bitmap_match()

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

Definition at line 1183 of file bitmapset.c.

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

References Assert(), and bms_equal().

Referenced by build_join_rel_hash().

bms_add_member()

Bitmapset* bms_add_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 755 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    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 */
        for (i = oldnwords; i < a->nwords; i++)
            a->words[i] = 0;
    }
 
    a->words[wordnum] |= ((bitmapword) 1 << bitnum);
    return a;
}

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

Referenced by _readBitmapset(), add_child_rel_equivalences(), add_row_identity_var(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), AlterPublicationTables(), apply_handle_update(), build_child_join_rel(), build_joinrel_tlist(), build_subplan(), 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(), DecodeTextArrayToBitmapset(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), do_analyze_rel(), DoCopy(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecInitAgg(), ExecInitAppend(), ExecInitStoredGenerated(), 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(), generate_join_implied_equalities(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_eclass_for_sort_expr(), get_matching_partitions(), get_param_path_clause_serials(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), join_is_removable(), load_enum_cache_data(), logicalrep_read_attrs(), make_datum_param(), make_join_rel(), make_modifytable(), make_outerjoininfo(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), mark_rels_nulled_by_join(), markRelsAsNulledBy(), markRTEForSelectPriv(), mbms_add_member(), mbms_overlap_sets(), nodeRead(), offset_relid_set(), PartitionPruneFixSubPlanMap(), preprocess_grouping_sets(), pub_collist_to_bitmapset(), publication_translate_columns(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), reduce_outer_joins_pass2(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_useless_groupby_columns(), remove_useless_joins(), 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(), transformGroupClause(), transformGroupClauseList(), 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
	)

Definition at line 818 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return bms_copy(b);
    if (b == NULL)
        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;
    for (i = 0; i < otherlen; i++)
        result->words[i] |= other->words[i];
    if (result != a)
        pfree(a);
    return result;
}

References a, b, bms_copy(), i, if(), Bitmapset::nwords, pfree(), and Bitmapset::words.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_eq_member(), add_part_relids(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), adjust_standard_join_alias_expression(), build_index_paths(), choose_best_statistics(), choose_bitmap_and(), create_bitmap_and_path(), create_bitmap_or_path(), create_lateral_join_info(), CreatePartitionPruneState(), deconstruct_distribute(), deconstruct_recurse(), DiscreteKnapsack(), ExecFindMatchingSubPlans(), ExecInitAgg(), expand_partitioned_rtentry(), ExplainPreScanNode(), finalize_plan(), find_nonnullable_rels_walker(), foreign_join_ok(), get_eclass_indexes_for_relids(), get_param_path_clause_serials(), 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(), transformOnConflictArbiter(), and try_partitionwise_join().

bms_add_range()

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

Definition at line 859 of file bitmapset.c.

{
    int         lwordnum,
                lbitnum,
                uwordnum,
                ushiftbits,
                wordnum;
 
    /* do nothing if nothing is called for, without further checking */
    if (upper < lower)
        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 */
        for (i = oldnwords; i < a->nwords; i++)
            a->words[i] = 0;
    }
 
    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;
    }
 
    return a;
}

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

Referenced by ExecInitAppend(), ExecInitMergeAppend(), ExecInitPartitionPruning(), 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(), and prune_append_rel_partitions().

bms_compare()

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

Definition at line 147 of file bitmapset.c.

{
    int         shortlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return (b == NULL) ? 0 : -1;
    else if (b == NULL)
        return +1;
    /* Handle cases where one input is longer than the other */
    shortlen = Min(a->nwords, b->nwords);
    for (i = shortlen; i < a->nwords; i++)
    {
        if (a->words[i] != 0)
            return +1;
    }
    for (i = shortlen; i < b->nwords; i++)
    {
        if (b->words[i] != 0)
            return -1;
    }
    /* Process words in common */
    i = shortlen;
    while (--i >= 0)
    {
        bitmapword  aw = a->words[i];
        bitmapword  bw = b->words[i];
 
        if (aw != bw)
            return (aw > bw) ? +1 : -1;
    }
    return 0;
}

References a, b, i, and Min.

Referenced by append_startup_cost_compare(), and append_total_cost_compare().

bms_copy()

Bitmapset* bms_copy

(

const Bitmapset *

a

)

Definition at line 74 of file bitmapset.c.

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

References a, BITMAPSET_SIZE, and palloc().

Referenced by _copyBitmapset(), add_nullingrels_if_needed(), adjust_child_relids(), adjust_relid_set(), bms_add_members(), bms_difference(), bms_intersect(), bms_union(), build_child_join_rel(), build_index_paths(), build_join_rel(), calc_nestloop_required_outer(), choose_bitmap_and(), create_lateral_join_info(), CreatePartitionPruneState(), 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_param_path_clause_serials(), get_relation_statistics_worker(), innerrel_is_unique(), join_is_legal(), join_is_removable(), load_enum_cache_data(), logicalrep_partition_open(), logicalrep_relmap_update(), make_outerjoininfo(), partition_bounds_copy(), perform_pruning_combine_step(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_rel_from_restrictinfo(), and reparameterize_path_by_child().

bms_del_member()

Bitmapset* bms_del_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 792 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    if (x < 0)
        elog(ERROR, "negative bitmapset member not allowed");
    if (a == NULL)
        return NULL;
    wordnum = WORDNUM(x);
    bitnum = BITNUM(x);
    if (wordnum < a->nwords)
        a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
    /* If we computed an empty result, we must return NULL */
    if (bms_is_empty_internal(a))
    {
        pfree(a);
        return NULL;
    }
    return a;
}

References a, BITNUM, bms_is_empty_internal(), elog(), ERROR, pfree(), WORDNUM, and x.

Referenced by add_nullingrels_if_needed(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), build_index_paths(), BuildParameterizedTidPaths(), deconstruct_distribute_oj_quals(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), 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(), substitute_phv_relids_walker(), and TopologicalSort().

bms_del_members()

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

Definition at line 960 of file bitmapset.c.

{
    int         shortlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return NULL;
    if (b == NULL)
        return a;
    /* Remove b's bits from a; we need never copy */
    shortlen = Min(a->nwords, b->nwords);
    for (i = 0; i < shortlen; i++)
        a->words[i] &= ~b->words[i];
    /* If we computed an empty result, we must return NULL */
    if (bms_is_empty_internal(a))
    {
        pfree(a);
        return NULL;
    }
    return a;
}

References a, b, bms_is_empty_internal(), i, if(), Min, and pfree().

Referenced by adjust_group_pathkeys_for_groupagg(), build_join_rel(), calc_nestloop_required_outer(), check_index_predicates(), classify_matching_subplans(), DiscreteKnapsack(), finalize_plan(), get_join_domain_min_rels(), make_outerjoininfo(), make_partition_pruneinfo(), min_join_parameterization(), and NumRelids().

bms_difference()

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

Definition at line 298 of file bitmapset.c.

{
    Bitmapset  *result;
    int         shortlen;
    int         i;
 
    /* 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 */
    shortlen = Min(a->nwords, b->nwords);
    for (i = 0; i < shortlen; i++)
        result->words[i] &= ~b->words[i];
    /* Need not check for empty result, since we handled that case above */
    return result;
}

References a, b, bms_copy(), bms_nonempty_difference(), i, Min, 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(), finalize_plan(), find_placeholder_info(), make_restrictinfo_internal(), pull_varnos_walker(), remove_nulling_relids_mutator(), and remove_useless_groupby_columns().

bms_equal()

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

Definition at line 94 of file bitmapset.c.

{
    const Bitmapset *shorter;
    const Bitmapset *longer;
    int         shortlen;
    int         longlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
    {
        if (b == NULL)
            return true;
        return false;
    }
    else if (b == NULL)
        return false;
    /* Identify shorter and longer input */
    if (a->nwords <= b->nwords)
    {
        shorter = a;
        longer = b;
    }
    else
    {
        shorter = b;
        longer = a;
    }
    /* And process */
    shortlen = shorter->nwords;
    for (i = 0; i < shortlen; i++)
    {
        if (shorter->words[i] != longer->words[i])
            return false;
    }
    longlen = longer->nwords;
    for (; i < longlen; i++)
    {
        if (longer->words[i] != 0)
            return false;
    }
    return true;
}

References a, b, i, Bitmapset::nwords, and Bitmapset::words.

Referenced by _equalBitmapset(), add_path_precheck(), add_paths_to_append_rel(), AlterPublicationTables(), bitmap_match(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_path(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), ExecInitPartitionPruning(), extract_rollup_sets(), fetch_upper_rel(), find_dependent_phvs_walker(), find_join_rel(), find_param_path_info(), generate_implied_equalities_for_column(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), get_join_domain_min_rels(), has_join_restriction(), infer_arbiter_indexes(), is_safe_restriction_clause_for(), join_is_legal(), make_one_rel(), make_partitionedrel_pruneinfo(), 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(), and try_partitionwise_join().

bms_free()

void bms_free

(

Bitmapset *

a

)

Definition at line 209 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(), func_get_detail(), get_rel_sync_entry(), get_relation_statistics(), has_legal_joinclause(), heap_update(), index_unchanged_by_update(), load_enum_cache_data(), logicalrep_rel_open(), logicalrep_relmap_free_entry(), logicalrep_write_attrs(), make_join_rel(), make_restrictinfo_internal(), NumRelids(), PartitionPruneFixSubPlanMap(), pgoutput_column_list_init(), pub_collist_contains_invalid_column(), publication_translate_columns(), reduce_outer_joins_pass2(), RelationDestroyRelation(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), reparameterize_path_by_child(), statext_mcv_clauselist_selectivity(), try_hashjoin_path(), try_mergejoin_path(), and try_nestloop_path().

bms_get_singleton_member()

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

Definition at line 634 of file bitmapset.c.

{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    if (a == NULL)
        return false;
    nwords = a->nwords;
    for (wordnum = 0; wordnum < nwords; wordnum++)
    {
        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);
        }
    }
    if (result < 0)
        return false;
    *member = result;
    return true;
}

References a, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, and HAS_MULTIPLE_ONES.

Referenced by add_placeholders_to_base_rels(), create_lateral_join_info(), find_single_rel_for_clauses(), generate_base_implied_equalities_no_const(), get_common_eclass_indexes(), join_is_removable(), reduce_unique_semijoins(), set_base_rel_consider_startup(), and statext_is_compatible_clause().

bms_hash_value()

uint32 bms_hash_value

(

const Bitmapset *

a

)

Definition at line 1150 of file bitmapset.c.

{
    int         lastword;
 
    if (a == NULL)
        return 0;               /* All empty sets hash to 0 */
    for (lastword = a->nwords; --lastword >= 0;)
    {
        if (a->words[lastword] != 0)
            break;
    }
    if (lastword < 0)
        return 0;               /* All empty sets hash to 0 */
    return DatumGetUInt32(hash_any((const unsigned char *) a->words,
                                   (lastword + 1) * sizeof(bitmapword)));
}

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

Referenced by bitmap_hash().

bms_int_members()

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

Definition at line 928 of file bitmapset.c.

{
    int         shortlen;
    int         i;
 
    /* 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);
    for (i = 0; i < shortlen; i++)
        a->words[i] &= b->words[i];
    for (; i < a->nwords; i++)
        a->words[i] = 0;
    /* If we computed an empty result, we must return NULL */
    if (bms_is_empty_internal(a))
    {
        pfree(a);
        return NULL;
    }
    return a;
}

References a, b, bms_is_empty_internal(), i, if(), 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(), and relation_is_updatable().

bms_intersect()

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

Definition at line 260 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         resultlen;
    int         i;
 
    /* 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;
    for (i = 0; i < resultlen; i++)
        result->words[i] &= other->words[i];
    /* If we computed an empty result, we must return NULL */
    if (bms_is_empty_internal(result))
    {
        pfree(result);
        return NULL;
    }
    return result;
}

References a, b, bms_copy(), bms_is_empty_internal(), i, if(), Bitmapset::nwords, pfree(), and Bitmapset::words.

Referenced by build_joinrel_tlist(), classify_matching_subplans(), deconstruct_distribute_oj_quals(), distribute_qual_to_rels(), get_matching_part_pairs(), make_outerjoininfo(), match_eclasses_to_foreign_key_col(), set_param_references(), and UpdateChangedParamSet().

bms_is_member()

bool bms_is_member	(	int	x,
		const Bitmapset *	a
	)

Definition at line 444 of file bitmapset.c.

{
    int         wordnum,
                bitnum;
 
    /* 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, BITNUM, elog(), ERROR, WORDNUM, and x.

Referenced by add_nulling_relids_mutator(), 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_is_computable_at(), clause_selectivity_ext(), clauselist_selectivity_ext(), clauselist_selectivity_or(), column_in_column_list(), 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(), deconstruct_distribute_oj_quals(), DefineIndex(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), do_analyze_rel(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecBuildUpdateProjection(), ExecEvalGroupingFunc(), ExecInitModifyTable(), execute_attr_map_cols(), expand_indexqual_rowcompare(), expand_single_inheritance_child(), ExplainSubPlans(), 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_foreign_key_join_selectivity(), get_join_domain_min_rels(), get_matching_hash_bounds(), get_tablefunc(), get_translated_update_targetlist(), get_variable(), has_partition_attrs(), hashagg_spill_tuple(), HeapDetermineColumnsInfo(), identify_current_nestloop_params(), index_expression_changed_walker(), index_unchanged_by_update(), InitPlan(), is_foreign_param(), is_pseudo_constant_for_index(), is_subquery_var(), IsBinaryTidClause(), isPlainForeignVar(), IsTidEqualAnyClause(), join_clause_is_movable_to(), join_is_removable(), lo_manage(), logicalrep_rel_mark_updatable(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_invalid_subplans_as_finished(), mark_rels_nulled_by_join(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), mbms_is_member(), partitions_are_ordered(), perform_pruning_base_step(), plpgsql_param_fetch(), postgresExplainForeignScan(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pub_collist_contains_invalid_column(), publication_translate_columns(), pullup_replace_vars_callback(), rangeTableEntry_used_walker(), remove_nulling_relids_mutator(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), rewriteTargetListIU(), rewriteValuesRTE(), send_relation_and_attrs(), set_join_column_names(), set_rtable_names(), statext_mcv_clauselist_selectivity(), substitute_phv_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), tsvector_update_trigger(), use_physical_tlist(), and view_cols_are_auto_updatable().

bms_is_subset()

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

Definition at line 332 of file bitmapset.c.

{
    int         shortlen;
    int         longlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return true;            /* empty set is a subset of anything */
    if (b == NULL)
        return false;
    /* Check common words */
    shortlen = Min(a->nwords, b->nwords);
    for (i = 0; i < shortlen; i++)
    {
        if ((a->words[i] & ~b->words[i]) != 0)
            return false;
    }
    /* Check extra words */
    if (a->nwords > b->nwords)
    {
        longlen = a->nwords;
        for (; i < longlen; i++)
        {
            if (a->words[i] != 0)
                return false;
        }
    }
    return true;
}

References a, b, i, and Min.

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), 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_index_paths(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), 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_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), identify_current_nestloop_params(), initial_cost_mergejoin(), innerrel_is_unique(), is_simple_subquery(), join_clause_is_movable_into(), join_is_legal(), join_is_removable(), jointree_contains_lateral_outer_refs(), make_outerjoininfo(), pg_get_expr_worker(), populate_joinrel_with_paths(), process_implied_equality(), process_subquery_nestloop_params(), 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(), try_partial_nestloop_path(), and use_physical_tlist().

bms_join()

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

Definition at line 987 of file bitmapset.c.

{
    Bitmapset  *result;
    Bitmapset  *other;
    int         otherlen;
    int         i;
 
    /* Handle cases where either input is NULL */
    if (a == NULL)
        return b;
    if (b == NULL)
        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;
    for (i = 0; i < otherlen; i++)
        result->words[i] |= other->words[i];
    if (other != result)        /* pure paranoia */
        pfree(other);
    return result;
}

References a, b, i, if(), 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(), and UpdateChangedParamSet().

bms_make_singleton()

Bitmapset* bms_make_singleton

(

int

x

)

Definition at line 186 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, 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(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseReturningList(), DiscreteKnapsack(), 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(), pg_column_is_updatable(), pg_get_expr_worker(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), reconsider_full_join_clause(), reduce_outer_joins(), reduce_outer_joins_pass1(), and subquery_planner().

bms_member_index()

int bms_member_index	(	Bitmapset *	a,
		int	x
	)

Definition at line 470 of file bitmapset.c.

{
    int         i;
    int         bitnum;
    int         wordnum;
    int         result = 0;
    bitmapword  mask;
 
    /* 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 */
    for (i = 0; i < wordnum; i++)
    {
        bitmapword  w = a->words[i];
 
        /* No need to count the bits in a zero word */
        if (w != 0)
            result += bmw_popcount(w);
    }
 
    /*
     * 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, BITNUM, bms_is_member(), bmw_popcount, i, WORDNUM, and x.

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

bms_membership()

BMS_Membership bms_membership

(

const Bitmapset *

a

)

Definition at line 691 of file bitmapset.c.

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

References a, BMS_EMPTY_SET, BMS_MULTIPLE, BMS_SINGLETON, and HAS_MULTIPLE_ONES.

Referenced by add_child_join_rel_equivalences(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_compatible_clause(), dependency_is_compatible_expression(), distribute_qual_to_rels(), distribute_restrictinfo_to_rels(), examine_variable(), find_join_input_rel(), find_nonnullable_rels_walker(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), get_foreign_key_join_selectivity(), grouping_planner(), process_implied_equality(), remove_useless_groupby_columns(), set_tablesample_rel_pathlist(), and statext_mcv_clauselist_selectivity().

bms_next_member()

int bms_next_member	(	const Bitmapset *	a,
		int	prevbit
	)

Definition at line 1039 of file bitmapset.c.

{
    int         nwords;
    int         wordnum;
    bitmapword  mask;
 
    if (a == NULL)
        return -2;
    nwords = a->nwords;
    prevbit++;
    mask = (~(bitmapword) 0) << BITNUM(prevbit);
    for (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, BITNUM, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, 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(), apply_scanjoin_target_to_paths(), approximate_joinrel_size(), 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(), CreateStatistics(), deparseLockingClause(), dependencies_clauselist_selectivity(), 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(), grouping_planner(), has_relevant_eclass_joinclause(), have_relevant_eclass_joinclause(), HeapDetermineColumnsInfo(), logicalrep_rel_mark_updatable(), logicalrep_report_missing_attrs(), 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(), outBitmapset(), PartitionPruneFixSubPlanMap(), postgresBeginForeignScan(), postgresExplainForeignScan(), postgresPlanForeignModify(), pub_collist_contains_invalid_column(), remove_join_clause_from_rels(), remove_useless_results_recurse(), SerializeParamExecParams(), show_eval_params(), and statext_is_compatible_clause().

bms_nonempty_difference()

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

Definition at line 564 of file bitmapset.c.

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

References a, b, i, and Min.

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

bms_num_members()

int bms_num_members

(

const Bitmapset *

a

)

Definition at line 665 of file bitmapset.c.

{
    int         result = 0;
    int         nwords;
    int         wordnum;
 
    if (a == NULL)
        return 0;
    nwords = a->nwords;
    for (wordnum = 0; wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];
 
        /* No need to count the bits in a zero word */
        if (w != 0)
            result += bmw_popcount(w);
    }
    return result;
}

References a, and bmw_popcount.

Referenced by adjust_group_pathkeys_for_groupagg(), build_attnums_array(), build_join_rel(), BuildRelationExtStatistics(), choose_best_statistics(), clauselist_apply_dependencies(), ComputeExtStatisticsRows(), estimate_multivariate_ndistinct(), ExecAppendAsyncBegin(), ExecInitAppend(), ExecInitMergeAppend(), ExecInitPartitionPruning(), 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(), lookup_var_attr_stats(), make_build_data(), make_partition_pruneinfo(), make_restrictinfo_internal(), mark_invalid_subplans_as_finished(), mcv_match_expression(), NumRelids(), pgoutput_column_list_init(), and SerializeParamExecParams().

bms_overlap()

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

Definition at line 511 of file bitmapset.c.

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

References a, b, 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(), clause_is_computable_at(), compute_semijoin_info(), create_nestloop_path(), deconstruct_distribute_oj_quals(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecInitStoredGenerated(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), 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_partition_attrs(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), 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_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo_internal(), mbms_overlap_sets(), partitions_are_ordered(), reduce_outer_joins_pass2(), remove_nulling_relids_mutator(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), set_append_rel_size(), 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
	)

bms_prev_member()

int bms_prev_member	(	const Bitmapset *	a,
		int	prevbit
	)

Definition at line 1098 of file bitmapset.c.

{
    int         wordnum;
    int         ushiftbits;
    bitmapword  mask;
 
    /*
     * 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;
 
    /* 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 (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, BITNUM, BITS_PER_BITMAPWORD, bmw_leftmost_one_pos, and WORDNUM.

Referenced by choose_next_subplan_locally().

bms_singleton_member()

int bms_singleton_member

(

const Bitmapset *

a

)

Definition at line 596 of file bitmapset.c.

{
    int         result = -1;
    int         nwords;
    int         wordnum;
 
    if (a == NULL)
        elog(ERROR, "bitmapset is empty");
    nwords = a->nwords;
    for (wordnum = 0; wordnum < nwords; wordnum++)
    {
        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);
        }
    }
    if (result < 0)
        elog(ERROR, "bitmapset is empty");
    return result;
}

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

Referenced by distribute_restrictinfo_to_rels(), examine_variable(), find_join_input_rel(), fix_append_rel_relids(), get_matching_part_pairs(), and remove_useless_joins().

bms_subset_compare()

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

Definition at line 369 of file bitmapset.c.

{
    BMS_Comparison result;
    int         shortlen;
    int         longlen;
    int         i;
 
    /* 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);
    for (i = 0; i < shortlen; i++)
    {
        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;
        }
    }
    /* Check extra words */
    if (a->nwords > b->nwords)
    {
        longlen = a->nwords;
        for (; i < longlen; i++)
        {
            if (a->words[i] != 0)
            {
                /* a is not a subset of b */
                if (result == BMS_SUBSET1)
                    return BMS_DIFFERENT;
                result = BMS_SUBSET2;
            }
        }
    }
    else if (a->nwords < b->nwords)
    {
        longlen = b->nwords;
        for (; i < longlen; i++)
        {
            if (b->words[i] != 0)
            {
                /* b is not a subset of a */
                if (result == BMS_SUBSET2)
                    return BMS_DIFFERENT;
                result = BMS_SUBSET1;
            }
        }
    }
    return result;
}

References a, b, BMS_DIFFERENT, BMS_EQUAL, BMS_SUBSET1, BMS_SUBSET2, i, and Min.

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

bms_union()

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

Definition at line 226 of file bitmapset.c.

{
    Bitmapset  *result;
    const Bitmapset *other;
    int         otherlen;
    int         i;
 
    /* 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;
    for (i = 0; i < otherlen; i++)
        result->words[i] |= other->words[i];
    return result;
}

References a, b, bms_copy(), i, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_nulling_relids_mutator(), build_child_join_rel(), 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(), generate_union_paths(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), get_rel_all_updated_cols(), has_legal_joinclause(), index_unchanged_by_update(), join_is_removable(), make_join_rel(), make_outerjoininfo(), make_restrictinfo_internal(), markNullableIfNeeded(), min_join_parameterization(), postgresGetForeignPaths(), pull_up_sublinks_jointree_recurse(), reduce_unique_semijoins(), remove_useless_joins(), resolve_special_varno(), substitute_phv_relids_walker(), and try_partitionwise_join().