bitmapset.c File Reference

#include "postgres.h"
#include "access/hash.h"
#include "nodes/pg_list.h"

Include dependency graph for bitmapset.c:

Go to the source code of this file.

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

Functions
Bitmapset *	bms_copy (const Bitmapset *a)
bool	bms_equal (const Bitmapset *a, const Bitmapset *b)
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)
bool	bms_overlap (const Bitmapset *a, const Bitmapset *b)
bool	bms_overlap_list (const Bitmapset *a, const List *b)
bool	bms_nonempty_difference (const Bitmapset *a, const Bitmapset *b)
int	bms_singleton_member (const Bitmapset *a)
bool	bms_get_singleton_member (const Bitmapset *a, int *member)
int	bms_num_members (const Bitmapset *a)
BMS_Membership	bms_membership (const Bitmapset *a)
bool	bms_is_empty (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_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_first_member (Bitmapset *a)
int	bms_next_member (const Bitmapset *a, int prevbit)
uint32	bms_hash_value (const Bitmapset *a)

Variables
static const uint8	rightmost_one_pos [256]
static const uint8	number_of_ones [256]

Macro Definition Documentation

#define BITMAPSET_SIZE

(

nwords

)

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

Definition at line 30 of file bitmapset.c.

Referenced by bms_add_member(), bms_copy(), and bms_make_singleton().

#define BITNUM

(

x

)

((x) % BITS_PER_BITMAPWORD)

Definition at line 28 of file bitmapset.c.

Referenced by bms_add_member(), bms_del_member(), bms_is_member(), bms_make_singleton(), bms_next_member(), and bms_overlap_list().

#define HAS_MULTIPLE_ONES

(

x

)

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

Definition at line 52 of file bitmapset.c.

Referenced by bms_get_singleton_member(), bms_membership(), and bms_singleton_member().

#define RIGHTMOST_ONE

(

x

)

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

Definition at line 50 of file bitmapset.c.

Referenced by bms_first_member().

#define WORDNUM

(

x

)

((x) / BITS_PER_BITMAPWORD)

Definition at line 27 of file bitmapset.c.

Referenced by bms_add_member(), bms_del_member(), bms_is_member(), bms_make_singleton(), bms_next_member(), and bms_overlap_list().

Function Documentation

Bitmapset* bms_add_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 698 of file bitmapset.c.

References BITMAPSET_SIZE, BITNUM, bms_make_singleton(), elog, ERROR, i, NULL, Bitmapset::nwords, repalloc(), WORDNUM, and Bitmapset::words.

Referenced by _readBitmapset(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), build_subplan(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), DoCopy(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecInitAgg(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), ExecSetParamPlan(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), fetch_remote_table_info(), fetch_statentries_for_relation(), finalize_plan(), finalize_primnode(), find_childrel_parents(), find_hash_columns(), find_unaggregated_cols_walker(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), get_primary_key_attnos(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineModifiedColumns(), infer_arbiter_indexes(), inheritance_planner(), intorel_startup(), load_enum_cache_data(), logicalrep_read_attrs(), make_datum_param(), make_modifytable(), make_one_rel(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), markRTEForSelectPriv(), offset_relid_set(), plpgsql_finish_datums(), preprocess_grouping_sets(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), RelationGetIndexAttrBitmap(), RememberFsyncRequest(), remove_useless_groupby_columns(), rewriteTargetView(), RI_Initial_Check(), set_customscan_references(), set_foreignscan_references(), set_join_column_names(), SS_identify_outer_params(), statext_ndistinct_build(), statext_ndistinct_deserialize(), transformGroupClause(), transformGroupClauseList(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), use_physical_tlist(), and view_cols_are_auto_updatable().

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

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

Definition at line 755 of file bitmapset.c.

References bms_copy(), i, NULL, Bitmapset::nwords, pfree(), result, and Bitmapset::words.

Referenced by add_child_rel_equivalences(), add_eq_member(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), build_index_paths(), check_outerjoin_delay(), choose_bitmap_and(), create_lateral_join_info(), deconstruct_recurse(), DiscreteKnapsack(), ExecInitAgg(), ExplainPreScanNode(), finalize_plan(), foreign_join_ok(), heap_update(), join_is_legal(), make_outerjoininfo(), pull_varnos_walker(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), and update_placeholder_eval_levels().

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

Bitmapset* bms_copy

(

const Bitmapset *

a

)

Definition at line 111 of file bitmapset.c.

References BITMAPSET_SIZE, NULL, Bitmapset::nwords, palloc(), and result.

Referenced by adjust_relid_set(), bms_add_members(), bms_difference(), bms_intersect(), bms_union(), build_index_paths(), build_join_rel(), build_simple_rel(), calc_nestloop_required_outer(), check_equivalence_delay(), check_outerjoin_delay(), choose_bitmap_and(), create_lateral_join_info(), DiscreteKnapsack(), distribute_qual_to_rels(), fetch_upper_rel(), finalize_plan(), finalize_primnode(), find_hash_columns(), find_placeholder_info(), fixup_whole_row_references(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), get_bitmap_tree_required_outer(), get_relation_statistics(), innerrel_is_unique(), join_is_legal(), load_enum_cache_data(), logicalrep_relmap_update(), make_outerjoininfo(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIndexAttrBitmap(), and remove_rel_from_query().

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

Bitmapset* bms_del_member	(	Bitmapset *	a,
		int	x
	)

Definition at line 735 of file bitmapset.c.

References BITNUM, elog, ERROR, NULL, WORDNUM, and Bitmapset::words.

Referenced by adjust_relid_set(), build_index_paths(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), finalize_plan(), finalize_primnode(), find_hash_columns(), fixup_whole_row_references(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_query(), substitute_multiple_relids_walker(), and TopologicalSort().

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

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

Definition at line 817 of file bitmapset.c.

References i, Min, NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by build_join_rel(), calc_nestloop_required_outer(), DiscreteKnapsack(), finalize_plan(), and min_join_parameterization().

{
    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];
    return a;
}

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

Definition at line 284 of file bitmapset.c.

References bms_copy(), i, Min, NULL, Bitmapset::nwords, result, and Bitmapset::words.

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), check_index_predicates(), consider_new_or_clause(), finalize_plan(), find_placeholder_info(), and remove_useless_groupby_columns().

{
    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);
    /* 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];
    return result;
}

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

Definition at line 131 of file bitmapset.c.

References bms_is_empty(), i, NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_path_precheck(), add_paths_to_append_rel(), bitmap_match(), bms_equal_any(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_path(), extract_rollup_sets(), fetch_upper_rel(), find_ec_member_for_tle(), find_join_rel(), fix_indexqual_references(), generate_implied_equalities_for_column(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), get_joinrel_parampathinfo(), has_join_restriction(), infer_arbiter_indexes(), is_safe_restriction_clause_for(), join_is_legal(), join_is_removable(), make_one_rel(), match_pathkeys_to_index(), populate_joinrel_with_paths(), prepare_sort_from_pathkeys(), and remove_rel_from_query().

{
    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 bms_is_empty(b);
    }
    else if (b == NULL)
        return bms_is_empty(a);
    /* 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;
}

int bms_first_member

(

Bitmapset *

a

)

Definition at line 885 of file bitmapset.c.

References BITS_PER_BITMAPWORD, NULL, Bitmapset::nwords, result, RIGHTMOST_ONE, rightmost_one_pos, and Bitmapset::words.

Referenced by check_relation_privileges(), check_selective_binary_conversion(), convert_EXISTS_sublink_to_join(), find_hash_columns(), HeapDetermineModifiedColumns(), make_row_comparison_op(), and mdsync().

{
    int         nwords;
    int         wordnum;

    if (a == NULL)
        return -1;
    nwords = a->nwords;
    for (wordnum = 0; wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];

        if (w != 0)
        {
            int         result;

            w = RIGHTMOST_ONE(w);
            a->words[wordnum] &= ~w;

            result = wordnum * BITS_PER_BITMAPWORD;
            while ((w & 255) == 0)
            {
                w >>= 8;
                result += 8;
            }
            result += rightmost_one_pos[w & 255];
            return result;
        }
    }
    return -1;
}

void bms_free

(

Bitmapset *

a

)

Definition at line 201 of file bitmapset.c.

References pfree().

Referenced by calc_nestloop_required_outer(), check_index_only(), check_outerjoin_delay(), choose_best_statistics(), convert_EXISTS_sublink_to_join(), create_foreignscan_plan(), create_nestloop_plan(), deparseColumnRef(), examine_variable(), ExecEndNode(), ExecReScan(), extract_rollup_sets(), finalize_plan(), find_hash_columns(), func_get_detail(), get_relation_statistics(), has_legal_joinclause(), heap_update(), load_enum_cache_data(), logicalrep_relmap_free_entry(), logicalrep_write_attrs(), make_join_rel(), mdsync(), NumRelids(), reduce_outer_joins_pass2(), RelationDestroyRelation(), RelationGetIndexAttrBitmap(), RememberFsyncRequest(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and UpdateChangedParamSet().

{
    if (a)
        pfree(a);
}

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

Definition at line 569 of file bitmapset.c.

References BITS_PER_BITMAPWORD, HAS_MULTIPLE_ONES, NULL, Bitmapset::nwords, result, rightmost_one_pos, and Bitmapset::words.

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

{
    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;
            while ((w & 255) == 0)
            {
                w >>= 8;
                result += 8;
            }
            result += rightmost_one_pos[w & 255];
        }
    }
    if (result < 0)
        return false;
    *member = result;
    return true;
}

uint32 bms_hash_value

(

const Bitmapset *

a

)

Definition at line 984 of file bitmapset.c.

References DatumGetUInt32, hash_any(), NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by bitmap_hash().

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

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

Definition at line 791 of file bitmapset.c.

References i, Min, NULL, Bitmapset::nwords, pfree(), and Bitmapset::words.

Referenced by check_outerjoin_delay(), find_nonnullable_rels_walker(), find_placeholder_info(), make_outerjoininfo(), make_row_comparison_op(), pull_varnos_walker(), and relation_is_updatable().

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

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

Definition at line 252 of file bitmapset.c.

References bms_copy(), i, NULL, Bitmapset::nwords, result, and Bitmapset::words.

Referenced by choose_best_statistics(), estimate_multivariate_ndistinct(), get_eclass_for_sort_expr(), make_outerjoininfo(), process_equivalence(), reconsider_full_join_clause(), reconsider_outer_join_clause(), and UpdateChangedParamSet().

{
    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];
    return result;
}

bool bms_is_empty

(

const Bitmapset *

a

)

Definition at line 663 of file bitmapset.c.

References NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_eq_member(), add_vars_to_targetlist(), bms_equal(), bms_is_subset(), bms_nonempty_difference(), bms_subset_compare(), build_index_paths(), build_join_rel(), calc_nestloop_required_outer(), check_index_predicates(), compute_semijoin_info(), consider_groupingsets_paths(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecReScanSetParamPlan(), finalize_plan(), find_nonnullable_rels_walker(), find_placeholder_info(), find_single_rel_for_clauses(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parallel_safe_total_inner(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), hash_inner_and_outer(), is_pseudo_constant_clause_relids(), make_outerjoininfo(), make_restrictinfo_internal(), match_unsorted_outer(), min_join_parameterization(), postgresGetForeignPaths(), preprocess_grouping_sets(), process_equivalence(), pull_varnos_walker(), relation_has_unique_index_for(), relation_is_updatable(), remove_rel_from_query(), rewriteTargetView(), sepgsql_dml_privileges(), sort_inner_and_outer(), TopologicalSort(), try_partial_hashjoin_path(), try_partial_mergejoin_path(), try_partial_nestloop_path(), UpdateChangedParamSet(), and use_physical_tlist().

{
    int         nwords;
    int         wordnum;

    if (a == NULL)
        return true;
    nwords = a->nwords;
    for (wordnum = 0; wordnum < nwords; wordnum++)
    {
        bitmapword  w = a->words[wordnum];

        if (w != 0)
            return false;
    }
    return true;
}

bool bms_is_member	(	int	x,
		const Bitmapset *	a
	)

Definition at line 420 of file bitmapset.c.

References BITNUM, elog, ERROR, NULL, Bitmapset::nwords, WORDNUM, and Bitmapset::words.

Referenced by adjust_relid_set(), adjust_rowcompare_for_index(), adjust_rowcount_for_semijoins(), bms_is_subset_singleton(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clauselist_selectivity(), ComputePartitionAttrs(), consider_groupingsets_paths(), copyParamList(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_plan(), DefineIndex(), deparseLockingClause(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), enum_known_sorted(), estimate_multivariate_ndistinct(), EstimateParamListSpace(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecEvalGroupingFunc(), ExecInitModifyTable(), ExplainSubPlans(), find_hash_columns(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), get_foreign_key_join_selectivity(), get_tablefunc(), inheritance_planner(), InitPlan(), is_partition_attr(), is_subquery_var(), join_clause_is_movable_to(), join_is_removable(), logicalrep_rel_open(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), match_clause_to_indexcol(), match_rowcompare_to_indexcol(), plpgsql_param_fetch(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pullup_replace_vars_callback(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), SerializeParamList(), set_join_column_names(), set_rtable_names(), substitute_multiple_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), use_physical_tlist(), and view_cols_are_auto_updatable().

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

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

Definition at line 308 of file bitmapset.c.

References bms_is_empty(), i, Min, NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), check_functional_grouping(), check_index_only(), check_outerjoin_delay(), clause_sides_match_join(), compute_semijoin_info(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_index_paths(), create_nestloop_plan(), deconstruct_recurse(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_em_expr_for_rel(), foreign_join_ok(), generate_implied_equalities_for_column(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), 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(), populate_joinrel_with_paths(), process_subquery_nestloop_params(), remove_rel_from_query(), reparameterize_path(), replace_nestloop_params_mutator(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), try_partial_nestloop_path(), update_placeholder_eval_levels(), and use_physical_tlist().

{
    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 bms_is_empty(a);
    /* 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;
}

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

Definition at line 838 of file bitmapset.c.

References i, NULL, Bitmapset::nwords, pfree(), result, and Bitmapset::words.

Referenced by add_paths_to_joinrel(), alias_relid_set(), finalize_primnode(), find_nonnullable_rels_walker(), get_bitmap_tree_required_outer(), get_relids_in_jointree(), process_equivalence(), pull_up_sublinks_jointree_recurse(), pull_varnos_walker(), and UpdateChangedParamSet().

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

Bitmapset* bms_make_singleton

(

int

x

)

Definition at line 179 of file bitmapset.c.

References BITMAPSET_SIZE, BITNUM, elog, ERROR, Bitmapset::nwords, palloc0(), result, WORDNUM, and Bitmapset::words.

Referenced by bms_add_member(), build_base_rel_tlists(), build_simple_rel(), deconstruct_recurse(), deparseReturningList(), DiscreteKnapsack(), extract_lateral_references(), find_nonnullable_rels_walker(), get_relids_in_jointree(), load_enum_cache_data(), pg_column_is_updatable(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), and reduce_outer_joins_pass1().

{
    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->nwords = wordnum + 1;
    result->words[wordnum] = ((bitmapword) 1 << bitnum);
    return result;
}

BMS_Membership bms_membership

(

const Bitmapset *

a

)

Definition at line 634 of file bitmapset.c.

References BMS_EMPTY_SET, BMS_MULTIPLE, BMS_SINGLETON, HAS_MULTIPLE_ONES, NULL, Bitmapset::nwords, result, and Bitmapset::words.

Referenced by bms_is_subset_singleton(), clauselist_selectivity(), dependency_is_compatible_clause(), distribute_qual_to_rels(), distribute_restrictinfo_to_rels(), examine_variable(), find_join_input_rel(), generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), get_foreign_key_join_selectivity(), remove_useless_groupby_columns(), set_tablesample_rel_pathlist(), and treat_as_join_clause().

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

int bms_next_member	(	const Bitmapset *	a,
		int	prevbit
	)

Definition at line 937 of file bitmapset.c.

References BITNUM, BITS_PER_BITMAPWORD, NULL, Bitmapset::nwords, result, rightmost_one_pos, WORDNUM, and Bitmapset::words.

Referenced by add_join_clause_to_rels(), adjust_view_column_set(), alias_relid_set(), approximate_joinrel_size(), create_lateral_join_info(), deparseLockingClause(), dependency_degree(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecInitAgg(), ExecScanReScan(), fixup_inherited_columns(), format_expr_params(), get_loop_count(), logicalrep_rel_open(), lookup_var_attr_stats(), offset_relid_set(), outBitmapset(), pg_ndistinct_out(), postgresBeginForeignScan(), postgresPlanDirectModify(), postgresPlanForeignModify(), remove_join_clause_from_rels(), set_customscan_references(), set_foreignscan_references(), setup_param_list(), setup_unshared_param_list(), statext_dependencies_build(), and statext_ndistinct_serialize().

{
    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;
            while ((w & 255) == 0)
            {
                w >>= 8;
                result += 8;
            }
            result += rightmost_one_pos[w & 255];
            return result;
        }

        /* in subsequent words, consider all bits */
        mask = (~(bitmapword) 0);
    }
    return -2;
}

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

Definition at line 494 of file bitmapset.c.

References bms_is_empty(), i, Min, NULL, Bitmapset::nwords, and Bitmapset::words.

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

{
    int         shortlen;
    int         i;

    /* Handle cases where either input is NULL */
    if (a == NULL)
        return false;
    if (b == NULL)
        return !bms_is_empty(a);
    /* 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;
}

int bms_num_members

(

const Bitmapset *

a

)

Definition at line 605 of file bitmapset.c.

References NULL, number_of_ones, Bitmapset::nwords, result, and Bitmapset::words.

Referenced by build_join_rel(), BuildRelationExtStatistics(), choose_best_statistics(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependencies_clauselist_selectivity(), dependency_degree(), estimate_multivariate_ndistinct(), find_hash_columns(), find_strongest_dependency(), lookup_var_attr_stats(), NumRelids(), statext_dependencies_build(), statext_ndistinct_build(), and statext_ndistinct_serialize().

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

        /* we assume here that bitmapword is an unsigned type */
        while (w != 0)
        {
            result += number_of_ones[w & 255];
            w >>= 8;
        }
    }
    return result;
}

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

Definition at line 443 of file bitmapset.c.

References i, Min, NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), allow_star_schema_join(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), check_outerjoin_delay(), choose_bitmap_and(), compute_semijoin_info(), create_nestloop_path(), create_nestloop_plan(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecReScanAgg(), ExecReScanFunctionScan(), ExecUpdateLockMode(), generate_implied_equalities_for_column(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), inheritance_planner(), 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(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), replace_nestloop_params_mutator(), select_outer_pathkeys_for_merge(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and update_placeholder_eval_levels().

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

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

Definition at line 465 of file bitmapset.c.

References BITNUM, elog, ERROR, lfirst_int, NIL, NULL, WORDNUM, and Bitmapset::words.

Referenced by preprocess_grouping_sets().

{
    ListCell   *lc;
    int         wordnum,
                bitnum;

    if (a == NULL || b == NIL)
        return false;

    foreach(lc, b)
    {
        int         x = lfirst_int(lc);

        if (x < 0)
            elog(ERROR, "negative bitmapset member not allowed");
        wordnum = WORDNUM(x);
        bitnum = BITNUM(x);
        if (wordnum < a->nwords)
            if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
                return true;
    }

    return false;
}

int bms_singleton_member

(

const Bitmapset *

a

)

Definition at line 526 of file bitmapset.c.

References BITS_PER_BITMAPWORD, elog, ERROR, HAS_MULTIPLE_ONES, NULL, Bitmapset::nwords, result, rightmost_one_pos, and Bitmapset::words.

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

{
    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;
            while ((w & 255) == 0)
            {
                w >>= 8;
                result += 8;
            }
            result += rightmost_one_pos[w & 255];
        }
    }
    if (result < 0)
        elog(ERROR, "bitmapset is empty");
    return result;
}

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

Definition at line 345 of file bitmapset.c.

References BMS_DIFFERENT, BMS_EQUAL, bms_is_empty(), BMS_SUBSET1, BMS_SUBSET2, i, Min, NULL, Bitmapset::nwords, result, and Bitmapset::words.

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

{
    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_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
    }
    if (b == NULL)
        return bms_is_empty(a) ? BMS_EQUAL : 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;
}

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

Definition at line 218 of file bitmapset.c.

References bms_copy(), i, NULL, Bitmapset::nwords, result, and Bitmapset::words.

Referenced by build_join_rel(), 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_path(), create_nestloop_plan(), deconstruct_recurse(), ExecConstraints(), ExecPartitionCheck(), ExecWithCheckOptions(), finalize_plan(), foreign_join_ok(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), generate_join_implied_equalities_for_ecs(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), has_legal_joinclause(), join_is_removable(), make_join_rel(), make_outerjoininfo(), make_restrictinfo_internal(), min_join_parameterization(), postgresGetForeignPaths(), pull_up_sublinks_jointree_recurse(), reduce_unique_semijoins(), remove_useless_joins(), and substitute_multiple_relids_walker().

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

Variable Documentation

const uint8 number_of_ones[256]

static

Initial value:

= {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 87 of file bitmapset.c.

Referenced by bms_num_members().

const uint8 rightmost_one_pos[256]

static

Initial value:

= {
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}

Definition at line 68 of file bitmapset.c.

Referenced by bms_first_member(), bms_get_singleton_member(), bms_next_member(), and bms_singleton_member().