PostgreSQL Source Code git master
Macros | Functions
bitmapset.c File Reference
#include "postgres.h"
#include "common/hashfn.h"
#include "nodes/bitmapset.h"
#include "nodes/pg_list.h"
#include "port/pg_bitutils.h"
Include dependency graph for bitmapset.c:

Go to the source code of this file.

Macros

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

Functions

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

Macro Definition Documentation

◆ BITMAPSET_SIZE

#define BITMAPSET_SIZE (   nwords )     (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))

Definition at line 50 of file bitmapset.c.

◆ BITNUM

#define BITNUM (   x )    ((x) % BITS_PER_BITMAPWORD)

Definition at line 48 of file bitmapset.c.

◆ HAS_MULTIPLE_ONES

#define HAS_MULTIPLE_ONES (   x )    ((bitmapword) RIGHTMOST_ONE(x) != (x))

Definition at line 72 of file bitmapset.c.

◆ RIGHTMOST_ONE

#define RIGHTMOST_ONE (   x )    ((signedbitmapword) (x) & -((signedbitmapword) (x)))

Definition at line 70 of file bitmapset.c.

◆ WORDNUM

#define WORDNUM (   x )    ((x) / BITS_PER_BITMAPWORD)

Definition at line 47 of file bitmapset.c.

Function Documentation

◆ bitmap_hash()

uint32 bitmap_hash ( const void *  key,
Size  keysize 
)

Definition at line 1436 of file bitmapset.c.

1437{
1438 Assert(keysize == sizeof(Bitmapset *));
1439 return bms_hash_value(*((const Bitmapset *const *) key));
1440}
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1420
Assert(PointerIsAligned(start, uint64))

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

Referenced by build_join_rel_hash(), and test_bitmap_hash().

◆ bitmap_match()

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

Definition at line 1446 of file bitmapset.c.

1447{
1448 Assert(keysize == sizeof(Bitmapset *));
1449 return !bms_equal(*((const Bitmapset *const *) key1),
1450 *((const Bitmapset *const *) key2));
1451}
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142

References Assert(), and bms_equal().

Referenced by build_join_rel_hash(), and test_bitmap_match().

◆ bms_add_member()

Bitmapset * bms_add_member ( Bitmapset *  a,
int  x 
)

Definition at line 815 of file bitmapset.c.

816{
817 int wordnum,
818 bitnum;
819
820 Assert(bms_is_valid_set(a));
821
822 if (x < 0)
823 elog(ERROR, "negative bitmapset member not allowed");
824 if (a == NULL)
825 return bms_make_singleton(x);
826
827 wordnum = WORDNUM(x);
828 bitnum = BITNUM(x);
829
830 /* enlarge the set if necessary */
831 if (wordnum >= a->nwords)
832 {
833 int oldnwords = a->nwords;
834 int i;
835
836 a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
837 a->nwords = wordnum + 1;
838 /* zero out the enlarged portion */
839 i = oldnwords;
840 do
841 {
842 a->words[i] = 0;
843 } while (++i < a->nwords);
844 }
845
846 a->words[wordnum] |= ((bitmapword) 1 << bitnum);
847
848#ifdef REALLOCATE_BITMAPSETS
849
850 /*
851 * There's no guarantee that the repalloc returned a new pointer, so copy
852 * and free unconditionally here.
853 */
854 a = bms_copy_and_free(a);
855#endif
856
857 return a;
858}
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:50
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
#define WORDNUM(x)
Definition: bitmapset.c:47
#define BITNUM(x)
Definition: bitmapset.c:48
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
x
int x
Definition: isn.c:75
a
int a
Definition: isn.c:73
i
int i
Definition: isn.c:77
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1610

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

Referenced by _readBitmapset(), add_child_eq_member(), add_outer_joins_to_relids(), add_row_identity_var(), add_rte_to_flat_rtable(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), all_rows_selectable(), apply_handle_update(), build_joinrel_tlist(), build_subplan(), buildGroupedVar(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), clauselist_apply_dependencies(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_list_bounds(), CreatePartitionPruneState(), DecodeTextArrayToBitmapset(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), do_analyze_rel(), DoCopy(), dropconstraint_internal(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecInitAgg(), ExecInitAppend(), ExecInitGenerated(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanGather(), ExecReScanGatherMerge(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), execute_attr_map_cols(), expand_single_inheritance_child(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), extractRemainingColumns(), fetch_remote_table_info(), fetch_statentries_for_relation(), finalize_plan(), finalize_primnode(), find_childrel_parents(), find_cols(), find_cols_walker(), find_hash_columns(), find_matching_subplans_recurse(), find_window_run_conditions(), findDefaultOnlyColumns(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), gen_partprune_steps_internal(), generate_base_implied_equalities(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_eclass_for_sort_expr(), get_matching_partitions(), get_nullingrels_recurse(), get_param_path_clause_serials(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_notnullatts(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), InitExecPartitionPruneContexts(), join_is_removable(), load_enum_cache_data(), logicalrep_read_attrs(), logicalrep_rel_open(), make_datum_param(), make_modifytable(), make_outerjoininfo(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), mark_rels_nulled_by_join(), mark_stmt(), markRelsAsNulledBy(), markRTEForSelectPriv(), mbms_add_member(), mbms_overlap_sets(), MergeAttributes(), nodeRead(), offset_relid_set(), plpgsql_mark_local_assignment_targets(), preprocess_grouping_sets(), pub_collist_to_bitmapset(), pub_collist_validate(), pub_form_cols_map(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), rebuild_joinclause_attr_needed(), reduce_outer_joins_pass2(), register_partpruneinfo(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_leftjoinrel_from_query(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_groupby_columns(), remove_useless_results_recurse(), rewriteTargetListIU(), rewriteTargetView(), RI_Initial_Check(), set_join_column_names(), set_param_references(), SS_identify_outer_params(), stat_covers_expressions(), statext_is_compatible_clause(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), test_bms_add_member(), test_random_operations(), transformGroupClause(), transformGroupClauseList(), 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 917 of file bitmapset.c.

918{
919 Bitmapset *result;
920 const Bitmapset *other;
921 int otherlen;
922 int i;
923
924 Assert(bms_is_valid_set(a));
925 Assert(bms_is_valid_set(b));
926
927 /* Handle cases where either input is NULL */
928 if (a == NULL)
929 return bms_copy(b);
930 if (b == NULL)
931 {
932#ifdef REALLOCATE_BITMAPSETS
933 a = bms_copy_and_free(a);
934#endif
935
936 return a;
937 }
938 /* Identify shorter and longer input; copy the longer one if needed */
939 if (a->nwords < b->nwords)
940 {
941 result = bms_copy(b);
942 other = a;
943 }
944 else
945 {
946 result = a;
947 other = b;
948 }
949 /* And union the shorter input into the result */
950 otherlen = other->nwords;
951 i = 0;
952 do
953 {
954 result->words[i] |= other->words[i];
955 } while (++i < otherlen);
956 if (result != a)
957 pfree(a);
958#ifdef REALLOCATE_BITMAPSETS
959 else
960 result = bms_copy_and_free(result);
961#endif
962
963 return result;
964}
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
b
int b
Definition: isn.c:74
void pfree(void *pointer)
Definition: mcxt.c:1594
int nwords
Definition: bitmapset.h:54
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:55

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

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

◆ bms_add_range()

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

Definition at line 1019 of file bitmapset.c.

1020{
1021 int lwordnum,
1022 lbitnum,
1023 uwordnum,
1024 ushiftbits,
1025 wordnum;
1026
1027 Assert(bms_is_valid_set(a));
1028
1029 /* do nothing if nothing is called for, without further checking */
1030 if (upper < lower)
1031 {
1032#ifdef REALLOCATE_BITMAPSETS
1033 a = bms_copy_and_free(a);
1034#endif
1035
1036 return a;
1037 }
1038
1039 if (lower < 0)
1040 elog(ERROR, "negative bitmapset member not allowed");
1041 uwordnum = WORDNUM(upper);
1042
1043 if (a == NULL)
1044 {
1045 a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1046 a->type = T_Bitmapset;
1047 a->nwords = uwordnum + 1;
1048 }
1049 else if (uwordnum >= a->nwords)
1050 {
1051 int oldnwords = a->nwords;
1052 int i;
1053
1054 /* ensure we have enough words to store the upper bit */
1055 a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1056 a->nwords = uwordnum + 1;
1057 /* zero out the enlarged portion */
1058 i = oldnwords;
1059 do
1060 {
1061 a->words[i] = 0;
1062 } while (++i < a->nwords);
1063 }
1064
1065 wordnum = lwordnum = WORDNUM(lower);
1066
1067 lbitnum = BITNUM(lower);
1068 ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
1069
1070 /*
1071 * Special case when lwordnum is the same as uwordnum we must perform the
1072 * upper and lower masking on the word.
1073 */
1074 if (lwordnum == uwordnum)
1075 {
1076 a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
1077 & (~(bitmapword) 0) >> ushiftbits;
1078 }
1079 else
1080 {
1081 /* turn on lbitnum and all bits left of it */
1082 a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1083
1084 /* turn on all bits for any intermediate words */
1085 while (wordnum < uwordnum)
1086 a->words[wordnum++] = ~(bitmapword) 0;
1087
1088 /* turn on upper's bit and all bits right of it. */
1089 a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
1090 }
1091
1092#ifdef REALLOCATE_BITMAPSETS
1093
1094 /*
1095 * There's no guarantee that the repalloc returned a new pointer, so copy
1096 * and free unconditionally here.
1097 */
1098 a = bms_copy_and_free(a);
1099#endif
1100
1101 return a;
1102}
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
void * palloc0(Size size)
Definition: mcxt.c:1395
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80

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

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

◆ bms_compare()

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

Definition at line 183 of file bitmapset.c.

184{
185 int i;
186
187 Assert(bms_is_valid_set(a));
188 Assert(bms_is_valid_set(b));
189
190 /* Handle cases where either input is NULL */
191 if (a == NULL)
192 return (b == NULL) ? 0 : -1;
193 else if (b == NULL)
194 return +1;
195
196 /* the set with the most words must be greater */
197 if (a->nwords != b->nwords)
198 return (a->nwords > b->nwords) ? +1 : -1;
199
200 i = a->nwords - 1;
201 do
202 {
203 bitmapword aw = a->words[i];
204 bitmapword bw = b->words[i];
205
206 if (aw != bw)
207 return (aw > bw) ? +1 : -1;
208 } while (--i >= 0);
209 return 0;
210}

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

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

◆ bms_copy()

Bitmapset * bms_copy ( const Bitmapset *  a )

Definition at line 122 of file bitmapset.c.

123{
124 Bitmapset *result;
125 size_t size;
126
127 Assert(bms_is_valid_set(a));
128
129 if (a == NULL)
130 return NULL;
131
132 size = BITMAPSET_SIZE(a->nwords);
133 result = (Bitmapset *) palloc(size);
134 memcpy(result, a, size);
135 return result;
136}
void * palloc(Size size)
Definition: mcxt.c:1365

References a, Assert(), BITMAPSET_SIZE, and palloc().

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

◆ bms_del_member()

Bitmapset * bms_del_member ( Bitmapset *  a,
int  x 
)

Definition at line 868 of file bitmapset.c.

869{
870 int wordnum,
871 bitnum;
872
873 Assert(bms_is_valid_set(a));
874
875 if (x < 0)
876 elog(ERROR, "negative bitmapset member not allowed");
877 if (a == NULL)
878 return NULL;
879
880 wordnum = WORDNUM(x);
881 bitnum = BITNUM(x);
882
883#ifdef REALLOCATE_BITMAPSETS
884 a = bms_copy_and_free(a);
885#endif
886
887 /* member can't exist. Return 'a' unmodified */
888 if (unlikely(wordnum >= a->nwords))
889 return a;
890
891 a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
892
893 /* when last word becomes empty, trim off all trailing empty words */
894 if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
895 {
896 /* find the last non-empty word and make that the new final word */
897 for (int i = wordnum - 1; i >= 0; i--)
898 {
899 if (a->words[i] != 0)
900 {
901 a->nwords = i + 1;
902 return a;
903 }
904 }
905
906 /* the set is now empty */
907 pfree(a);
908 return NULL;
909 }
910 return a;
911}
#define unlikely(x)
Definition: c.h:402

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

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

◆ bms_del_members()

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

Definition at line 1161 of file bitmapset.c.

1162{
1163 int i;
1164
1165 Assert(bms_is_valid_set(a));
1166 Assert(bms_is_valid_set(b));
1167
1168 /* Handle cases where either input is NULL */
1169 if (a == NULL)
1170 return NULL;
1171 if (b == NULL)
1172 {
1173#ifdef REALLOCATE_BITMAPSETS
1174 a = bms_copy_and_free(a);
1175#endif
1176
1177 return a;
1178 }
1179
1180 /* Remove b's bits from a; we need never copy */
1181 if (a->nwords > b->nwords)
1182 {
1183 /*
1184 * We'll never need to remove trailing zero words when 'a' has more
1185 * words than 'b'.
1186 */
1187 i = 0;
1188 do
1189 {
1190 a->words[i] &= ~b->words[i];
1191 } while (++i < b->nwords);
1192 }
1193 else
1194 {
1195 int lastnonzero = -1;
1196
1197 /* we may need to remove trailing zero words from the result. */
1198 i = 0;
1199 do
1200 {
1201 a->words[i] &= ~b->words[i];
1202
1203 /* remember the last non-zero word */
1204 if (a->words[i] != 0)
1205 lastnonzero = i;
1206 } while (++i < a->nwords);
1207
1208 /* check if 'a' has become empty */
1209 if (lastnonzero == -1)
1210 {
1211 pfree(a);
1212 return NULL;
1213 }
1214
1215 /* trim off any trailing zero words */
1216 a->nwords = lastnonzero + 1;
1217 }
1218
1219#ifdef REALLOCATE_BITMAPSETS
1220 a = bms_copy_and_free(a);
1221#endif
1222
1223 return a;
1224}

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

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

◆ bms_difference()

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

Definition at line 346 of file bitmapset.c.

347{
348 Bitmapset *result;
349 int i;
350
351 Assert(bms_is_valid_set(a));
352 Assert(bms_is_valid_set(b));
353
354 /* Handle cases where either input is NULL */
355 if (a == NULL)
356 return NULL;
357 if (b == NULL)
358 return bms_copy(a);
359
360 /*
361 * In Postgres' usage, an empty result is a very common case, so it's
362 * worth optimizing for that by testing bms_nonempty_difference(). This
363 * saves us a palloc/pfree cycle compared to checking after-the-fact.
364 */
366 return NULL;
367
368 /* Copy the left input */
369 result = bms_copy(a);
370
371 /* And remove b's bits from result */
372 if (result->nwords > b->nwords)
373 {
374 /*
375 * We'll never need to remove trailing zero words when 'a' has more
376 * words than 'b' as the additional words must be non-zero.
377 */
378 i = 0;
379 do
380 {
381 result->words[i] &= ~b->words[i];
382 } while (++i < b->nwords);
383 }
384 else
385 {
386 int lastnonzero = -1;
387
388 /* we may need to remove trailing zero words from the result. */
389 i = 0;
390 do
391 {
392 result->words[i] &= ~b->words[i];
393
394 /* remember the last non-zero word */
395 if (result->words[i] != 0)
396 lastnonzero = i;
397 } while (++i < result->nwords);
398
399 /* trim off trailing zero words */
400 result->nwords = lastnonzero + 1;
401 }
402 Assert(result->nwords != 0);
403
404 /* Need not check for empty result, since we handled that case above */
405 return result;
406}
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641

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

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

◆ bms_equal()

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

Definition at line 142 of file bitmapset.c.

143{
144 int i;
145
146 Assert(bms_is_valid_set(a));
147 Assert(bms_is_valid_set(b));
148
149 /* Handle cases where either input is NULL */
150 if (a == NULL)
151 {
152 if (b == NULL)
153 return true;
154 return false;
155 }
156 else if (b == NULL)
157 return false;
158
159 /* can't be equal if the word counts don't match */
160 if (a->nwords != b->nwords)
161 return false;
162
163 /* check each word matches */
164 i = 0;
165 do
166 {
167 if (a->words[i] != b->words[i])
168 return false;
169 } while (++i < a->nwords);
170
171 return true;
172}

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

Referenced by _equalBitmapset(), add_non_redundant_clauses(), add_path_precheck(), add_paths_to_append_rel(), afterTriggerAddEvent(), AlterPublicationTables(), assign_param_for_var(), bitmap_match(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_paths(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), ExecInitPartitionExecPruning(), extract_lateral_vars_from_PHVs(), extract_rollup_sets(), fetch_upper_rel(), find_dependent_phvs_walker(), find_join_rel(), find_param_path_info(), generate_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(), innerrel_is_unique_ext(), is_safe_restriction_clause_for(), join_is_legal(), make_one_rel(), make_partitionedrel_pruneinfo(), mark_nullable_by_grouping(), match_orclause_to_indexcol(), match_pathkeys_to_index(), merge_clump(), pgoutput_column_list_init(), populate_joinrel_with_paths(), pull_varnos_walker(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), set_rel_pathlist(), standard_join_search(), test_bms_equal(), and try_partitionwise_join().

◆ bms_free()

void bms_free ( Bitmapset *  a )

Definition at line 239 of file bitmapset.c.

240{
241 if (a)
242 pfree(a);
243}

References a, and pfree().

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

◆ bms_get_singleton_member()

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

Definition at line 715 of file bitmapset.c.

716{
717 int result = -1;
718 int nwords;
719 int wordnum;
720
721 Assert(bms_is_valid_set(a));
722
723 if (a == NULL)
724 return false;
725
726 nwords = a->nwords;
727 wordnum = 0;
728 do
729 {
730 bitmapword w = a->words[wordnum];
731
732 if (w != 0)
733 {
734 if (result >= 0 || HAS_MULTIPLE_ONES(w))
735 return false;
736 result = wordnum * BITS_PER_BITMAPWORD;
737 result += bmw_rightmost_one_pos(w);
738 }
739 } while (++wordnum < nwords);
740
741 /* we don't expect non-NULL sets to be empty */
742 Assert(result >= 0);
743 *member = result;
744 return true;
745}
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:72
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.h:79

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

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

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset *  a )

Definition at line 1420 of file bitmapset.c.

1421{
1422 Assert(bms_is_valid_set(a));
1423
1424 if (a == NULL)
1425 return 0; /* All empty sets hash to 0 */
1426 return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1427 a->nwords * sizeof(bitmapword)));
1428}
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:232

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

Referenced by bitmap_hash(), and test_bms_hash_value().

◆ bms_int_members()

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

Definition at line 1109 of file bitmapset.c.

1110{
1111 int lastnonzero;
1112 int shortlen;
1113 int i;
1114
1115 Assert(bms_is_valid_set(a));
1116 Assert(bms_is_valid_set(b));
1117
1118 /* Handle cases where either input is NULL */
1119 if (a == NULL)
1120 return NULL;
1121 if (b == NULL)
1122 {
1123 pfree(a);
1124 return NULL;
1125 }
1126
1127 /* Intersect b into a; we need never copy */
1128 shortlen = Min(a->nwords, b->nwords);
1129 lastnonzero = -1;
1130 i = 0;
1131 do
1132 {
1133 a->words[i] &= b->words[i];
1134
1135 if (a->words[i] != 0)
1136 lastnonzero = i;
1137 } while (++i < shortlen);
1138
1139 /* If we computed an empty result, we must return NULL */
1140 if (lastnonzero == -1)
1141 {
1142 pfree(a);
1143 return NULL;
1144 }
1145
1146 /* get rid of trailing zero words */
1147 a->nwords = lastnonzero + 1;
1148
1149#ifdef REALLOCATE_BITMAPSETS
1150 a = bms_copy_and_free(a);
1151#endif
1152
1153 return a;
1154}
#define Min(x, y)
Definition: c.h:1003

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

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

◆ bms_intersect()

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

Definition at line 292 of file bitmapset.c.

293{
294 Bitmapset *result;
295 const Bitmapset *other;
296 int lastnonzero;
297 int resultlen;
298 int i;
299
300 Assert(bms_is_valid_set(a));
301 Assert(bms_is_valid_set(b));
302
303 /* Handle cases where either input is NULL */
304 if (a == NULL || b == NULL)
305 return NULL;
306
307 /* Identify shorter and longer input; copy the shorter one */
308 if (a->nwords <= b->nwords)
309 {
310 result = bms_copy(a);
311 other = b;
312 }
313 else
314 {
315 result = bms_copy(b);
316 other = a;
317 }
318 /* And intersect the longer input with the result */
319 resultlen = result->nwords;
320 lastnonzero = -1;
321 i = 0;
322 do
323 {
324 result->words[i] &= other->words[i];
325
326 if (result->words[i] != 0)
327 lastnonzero = i;
328 } while (++i < resultlen);
329 /* If we computed an empty result, we must return NULL */
330 if (lastnonzero == -1)
331 {
332 pfree(result);
333 return NULL;
334 }
335
336 /* get rid of trailing zero words */
337 result->nwords = lastnonzero + 1;
338 return result;
339}

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

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

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset *  a 
)

Definition at line 510 of file bitmapset.c.

511{
512 int wordnum,
513 bitnum;
514
515 Assert(bms_is_valid_set(a));
516
517 /* XXX better to just return false for x<0 ? */
518 if (x < 0)
519 elog(ERROR, "negative bitmapset member not allowed");
520 if (a == NULL)
521 return false;
522
523 wordnum = WORDNUM(x);
524 bitnum = BITNUM(x);
525 if (wordnum >= a->nwords)
526 return false;
527 if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528 return true;
529 return false;
530}

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

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

◆ bms_is_subset()

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

Definition at line 412 of file bitmapset.c.

413{
414 int i;
415
416 Assert(bms_is_valid_set(a));
417 Assert(bms_is_valid_set(b));
418
419 /* Handle cases where either input is NULL */
420 if (a == NULL)
421 return true; /* empty set is a subset of anything */
422 if (b == NULL)
423 return false;
424
425 /* 'a' can't be a subset of 'b' if it contains more words */
426 if (a->nwords > b->nwords)
427 return false;
428
429 /* Check all 'a' members are set in 'b' */
430 i = 0;
431 do
432 {
433 if ((a->words[i] & ~b->words[i]) != 0)
434 return false;
435 } while (++i < a->nwords);
436 return true;
437}

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

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

◆ bms_join()

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

Definition at line 1230 of file bitmapset.c.

1231{
1232 Bitmapset *result;
1233 Bitmapset *other;
1234 int otherlen;
1235 int i;
1236
1237 Assert(bms_is_valid_set(a));
1238 Assert(bms_is_valid_set(b));
1239
1240 /* Handle cases where either input is NULL */
1241 if (a == NULL)
1242 {
1243#ifdef REALLOCATE_BITMAPSETS
1244 b = bms_copy_and_free(b);
1245#endif
1246
1247 return b;
1248 }
1249 if (b == NULL)
1250 {
1251#ifdef REALLOCATE_BITMAPSETS
1252 a = bms_copy_and_free(a);
1253#endif
1254
1255 return a;
1256 }
1257
1258 /* Identify shorter and longer input; use longer one as result */
1259 if (a->nwords < b->nwords)
1260 {
1261 result = b;
1262 other = a;
1263 }
1264 else
1265 {
1266 result = a;
1267 other = b;
1268 }
1269 /* And union the shorter input into the result */
1270 otherlen = other->nwords;
1271 i = 0;
1272 do
1273 {
1274 result->words[i] |= other->words[i];
1275 } while (++i < otherlen);
1276 if (other != result) /* pure paranoia */
1277 pfree(other);
1278
1279#ifdef REALLOCATE_BITMAPSETS
1280 result = bms_copy_and_free(result);
1281#endif
1282
1283 return result;
1284}

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

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

◆ bms_make_singleton()

Bitmapset * bms_make_singleton ( int  x )

Definition at line 216 of file bitmapset.c.

217{
218 Bitmapset *result;
219 int wordnum,
220 bitnum;
221
222 if (x < 0)
223 elog(ERROR, "negative bitmapset member not allowed");
224 wordnum = WORDNUM(x);
225 bitnum = BITNUM(x);
226 result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
227 result->type = T_Bitmapset;
228 result->nwords = wordnum + 1;
229 result->words[wordnum] = ((bitmapword) 1 << bitnum);
230 return result;
231}

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(), CopyFrom(), create_edata_for_relation(), create_estate_for_relation(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseReturningList(), DiscreteKnapsack(), examine_simple_variable(), expand_inherited_rtentry(), extract_lateral_references(), find_dependent_phvs(), find_dependent_phvs_in_jointree(), find_nonnullable_rels_walker(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_range_bounds(), get_relids_in_jointree(), load_enum_cache_data(), make_group_input_target(), make_pathkeys_for_sortclauses_extended(), mark_nullable_by_grouping(), pg_column_is_updatable(), pg_get_expr_worker(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), rebuild_lateral_attr_needed(), reconsider_full_join_clause(), reduce_outer_joins(), reduce_outer_joins_pass1(), remove_rel_from_query(), set_upper_references(), subquery_planner(), test_bms_make_singleton(), and transform_MERGE_to_join().

◆ bms_member_index()

int bms_member_index ( Bitmapset *  a,
int  x 
)

Definition at line 539 of file bitmapset.c.

540{
541 int i;
542 int bitnum;
543 int wordnum;
544 int result = 0;
545 bitmapword mask;
546
547 Assert(bms_is_valid_set(a));
548
549 /* return -1 if not a member of the bitmap */
550 if (!bms_is_member(x, a))
551 return -1;
552
553 wordnum = WORDNUM(x);
554 bitnum = BITNUM(x);
555
556 /* count bits in preceding words */
557 for (i = 0; i < wordnum; i++)
558 {
559 bitmapword w = a->words[i];
560
561 /* No need to count the bits in a zero word */
562 if (w != 0)
563 result += bmw_popcount(w);
564 }
565
566 /*
567 * Now add bits of the last word, but only those before the item. We can
568 * do that by applying a mask and then using popcount again. To get
569 * 0-based index, we want to count only preceding bits, not the item
570 * itself, so we subtract 1.
571 */
572 mask = ((bitmapword) 1 << bitnum) - 1;
573 result += bmw_popcount(a->words[wordnum] & mask);
574
575 return result;
576}
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
#define bmw_popcount(w)
Definition: bitmapset.h:80

References a, Assert(), BITNUM, bms_is_member(), bmw_popcount, i, WORDNUM, and x.

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

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset *  a )

Definition at line 781 of file bitmapset.c.

782{
784 int nwords;
785 int wordnum;
786
787 Assert(bms_is_valid_set(a));
788
789 if (a == NULL)
790 return BMS_EMPTY_SET;
791
792 nwords = a->nwords;
793 wordnum = 0;
794 do
795 {
796 bitmapword w = a->words[wordnum];
797
798 if (w != 0)
799 {
800 if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
801 return BMS_MULTIPLE;
802 result = BMS_SINGLETON;
803 }
804 } while (++wordnum < nwords);
805 return result;
806}
BMS_Membership
Definition: bitmapset.h:70
@ BMS_SINGLETON
Definition: bitmapset.h:72
@ BMS_EMPTY_SET
Definition: bitmapset.h:71
@ BMS_MULTIPLE
Definition: bitmapset.h:73

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

Referenced by add_base_clause_to_rel(), add_child_join_rel_equivalences(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_compatible_clause(), dependency_is_compatible_expression(), distribute_qual_to_rels(), extract_lateral_vars_from_PHVs(), find_nonnullable_rels_walker(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), get_foreign_key_join_selectivity(), grouping_planner(), process_implied_equality(), rebuild_joinclause_attr_needed(), relation_has_unique_index_for(), remove_self_join_rel(), remove_self_joins_recurse(), remove_useless_groupby_columns(), replace_relid_callback(), set_subquery_pathlist(), set_tablesample_rel_pathlist(), split_selfjoin_quals(), statext_mcv_clauselist_selectivity(), and test_bms_membership().

◆ bms_next_member()

int bms_next_member ( const Bitmapset *  a,
int  prevbit 
)

Definition at line 1306 of file bitmapset.c.

1307{
1308 int nwords;
1309 int wordnum;
1310 bitmapword mask;
1311
1312 Assert(bms_is_valid_set(a));
1313
1314 if (a == NULL)
1315 return -2;
1316 nwords = a->nwords;
1317 prevbit++;
1318 mask = (~(bitmapword) 0) << BITNUM(prevbit);
1319 for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1320 {
1321 bitmapword w = a->words[wordnum];
1322
1323 /* ignore bits before prevbit */
1324 w &= mask;
1325
1326 if (w != 0)
1327 {
1328 int result;
1329
1330 result = wordnum * BITS_PER_BITMAPWORD;
1331 result += bmw_rightmost_one_pos(w);
1332 return result;
1333 }
1334
1335 /* in subsequent words, consider all bits */
1336 mask = (~(bitmapword) 0);
1337 }
1338 return -2;
1339}

References a, Assert(), 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(), all_rows_selectable(), apply_scanjoin_target_to_paths(), approximate_joinrel_size(), attnumstoint2vector(), build_attnums_array(), check_relation_privileges(), check_selective_binary_conversion(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), clauselist_apply_dependencies(), ComputePartitionAttrs(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_partitionwise_grouping_paths(), CreatePartitionPruneState(), CreateStatistics(), DefineIndex(), deparseLockingClause(), dependencies_clauselist_selectivity(), eclass_member_iterator_next(), EstimateParamExecSpace(), ExecAppendAsyncBegin(), ExecAppendAsyncEventWait(), ExecAppendAsyncRequest(), ExecCheckOneRelPerms(), ExecCheckPermissionsModified(), ExecInitAgg(), ExecInitAppend(), ExecInitMergeAppend(), ExecMergeAppend(), ExecReScanAppend(), ExecScanReScan(), ExecSetParamPlanMulti(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_dependent_phvs_in_jointree(), find_hash_columns(), find_matching_subplans_recurse(), fixup_inherited_columns(), format_expr_params(), generate_base_implied_equalities(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_loop_count(), get_matching_partitions(), get_placeholder_nulling_relids(), grouping_planner(), has_relevant_eclass_joinclause(), have_relevant_eclass_joinclause(), HeapDetermineColumnsInfo(), InitExecPartitionPruneContexts(), logicalrep_get_attrs_str(), logicalrep_rel_mark_updatable(), lookup_var_attr_stats(), make_build_data(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), mark_rels_nulled_by_join(), match_eclasses_to_foreign_key_col(), offset_relid_set(), outBitmapset(), overexplain_bitmapset(), postgresBeginForeignScan(), postgresExplainForeignScan(), postgresPlanForeignModify(), pub_contains_invalid_column(), publication_add_relation(), pullup_replace_vars_callback(), remove_join_clause_from_rels(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_results_recurse(), remove_useless_self_joins(), SerializeParamExecParams(), show_result_replacement_info(), statext_is_compatible_clause(), test_bms_next_member(), and test_random_operations().

◆ bms_nonempty_difference()

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

Definition at line 641 of file bitmapset.c.

642{
643 int i;
644
645 Assert(bms_is_valid_set(a));
646 Assert(bms_is_valid_set(b));
647
648 /* Handle cases where either input is NULL */
649 if (a == NULL)
650 return false;
651 if (b == NULL)
652 return true;
653 /* if 'a' has more words then it must contain additional members */
654 if (a->nwords > b->nwords)
655 return true;
656 /* Check all 'a' members are set in 'b' */
657 i = 0;
658 do
659 {
660 if ((a->words[i] & ~b->words[i]) != 0)
661 return true;
662 } while (++i < a->nwords);
663 return false;
664}

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

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

◆ bms_num_members()

int bms_num_members ( const Bitmapset *  a )

Definition at line 751 of file bitmapset.c.

752{
753 int result = 0;
754 int nwords;
755 int wordnum;
756
757 Assert(bms_is_valid_set(a));
758
759 if (a == NULL)
760 return 0;
761
762 nwords = a->nwords;
763 wordnum = 0;
764 do
765 {
766 bitmapword w = a->words[wordnum];
767
768 /* No need to count the bits in a zero word */
769 if (w != 0)
770 result += bmw_popcount(w);
771 } while (++wordnum < nwords);
772 return result;
773}

References a, Assert(), and bmw_popcount.

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

◆ bms_overlap()

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

Definition at line 582 of file bitmapset.c.

583{
584 int shortlen;
585 int i;
586
587 Assert(bms_is_valid_set(a));
588 Assert(bms_is_valid_set(b));
589
590 /* Handle cases where either input is NULL */
591 if (a == NULL || b == NULL)
592 return false;
593 /* Check words in common */
594 shortlen = Min(a->nwords, b->nwords);
595 i = 0;
596 do
597 {
598 if ((a->words[i] & b->words[i]) != 0)
599 return true;
600 } while (++i < shortlen);
601 return false;
602}

References a, Assert(), 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(), compute_semijoin_info(), create_nestloop_path(), distribute_qual_to_rels(), eclass_useful_for_merging(), examine_variable(), ExecInitGenerated(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), extract_lateral_vars_from_PHVs(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_partition_attrs(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), identify_current_nestloop_params(), join_clause_is_movable_into(), join_clause_is_movable_to(), join_is_legal(), join_is_removable(), join_search_one_level(), make_join_rel(), make_outerjoininfo(), make_plain_restrictinfo(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), mbms_overlap_sets(), partitions_are_ordered(), path_is_reparameterizable_by_child(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), remove_nulling_relids_mutator(), remove_self_joins_recurse(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), set_append_rel_size(), subbuild_joinrel_restrictlist(), test_bms_overlap(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and try_partitionwise_join().

◆ bms_overlap_list()

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

Definition at line 608 of file bitmapset.c.

609{
610 ListCell *lc;
611 int wordnum,
612 bitnum;
613
614 Assert(bms_is_valid_set(a));
615
616 if (a == NULL || b == NIL)
617 return false;
618
619 foreach(lc, b)
620 {
621 int x = lfirst_int(lc);
622
623 if (x < 0)
624 elog(ERROR, "negative bitmapset member not allowed");
625 wordnum = WORDNUM(x);
626 bitnum = BITNUM(x);
627 if (wordnum < a->nwords)
628 if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
629 return true;
630 }
631
632 return false;
633}
#define NIL
Definition: pg_list.h:68
#define lfirst_int(lc)
Definition: pg_list.h:173
Definition: pg_list.h:46

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

Referenced by preprocess_grouping_sets(), and test_bms_overlap_list().

◆ bms_prev_member()

int bms_prev_member ( const Bitmapset *  a,
int  prevbit 
)

Definition at line 1367 of file bitmapset.c.

1368{
1369 int wordnum;
1370 int ushiftbits;
1371 bitmapword mask;
1372
1373 Assert(bms_is_valid_set(a));
1374
1375 /*
1376 * If set is NULL or if there are no more bits to the right then we've
1377 * nothing to do.
1378 */
1379 if (a == NULL || prevbit == 0)
1380 return -2;
1381
1382 /* Validate callers didn't give us something out of range */
1383 Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
1384 Assert(prevbit >= -1);
1385
1386 /* transform -1 to the highest possible bit we could have set */
1387 if (prevbit == -1)
1388 prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1389 else
1390 prevbit--;
1391
1392 ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1393 mask = (~(bitmapword) 0) >> ushiftbits;
1394 for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1395 {
1396 bitmapword w = a->words[wordnum];
1397
1398 /* mask out bits left of prevbit */
1399 w &= mask;
1400
1401 if (w != 0)
1402 {
1403 int result;
1404
1405 result = wordnum * BITS_PER_BITMAPWORD;
1406 result += bmw_leftmost_one_pos(w);
1407 return result;
1408 }
1409
1410 /* in subsequent words, consider all bits */
1411 mask = (~(bitmapword) 0);
1412 }
1413 return -2;
1414}
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.h:78

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

Referenced by choose_next_subplan_locally(), and test_bms_prev_member().

◆ bms_replace_members()

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

Definition at line 972 of file bitmapset.c.

973{
974 int i;
975
976 Assert(bms_is_valid_set(a));
977 Assert(bms_is_valid_set(b));
978
979 if (a == NULL)
980 return bms_copy(b);
981 if (b == NULL)
982 {
983 pfree(a);
984 return NULL;
985 }
986
987 if (a->nwords < b->nwords)
988 a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
989
990 i = 0;
991 do
992 {
993 a->words[i] = b->words[i];
994 } while (++i < b->nwords);
995
996 a->nwords = b->nwords;
997
998#ifdef REALLOCATE_BITMAPSETS
999
1000 /*
1001 * There's no guarantee that the repalloc returned a new pointer, so copy
1002 * and free unconditionally here.
1003 */
1004 a = bms_copy_and_free(a);
1005#endif
1006
1007 return a;
1008}

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

Referenced by DiscreteKnapsack(), and test_bms_replace_members().

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset *  a )

Definition at line 672 of file bitmapset.c.

673{
674 int result = -1;
675 int nwords;
676 int wordnum;
677
678 Assert(bms_is_valid_set(a));
679
680 if (a == NULL)
681 elog(ERROR, "bitmapset is empty");
682
683 nwords = a->nwords;
684 wordnum = 0;
685 do
686 {
687 bitmapword w = a->words[wordnum];
688
689 if (w != 0)
690 {
691 if (result >= 0 || HAS_MULTIPLE_ONES(w))
692 elog(ERROR, "bitmapset has multiple members");
693 result = wordnum * BITS_PER_BITMAPWORD;
694 result += bmw_rightmost_one_pos(w);
695 }
696 } while (++wordnum < nwords);
697
698 /* we don't expect non-NULL sets to be empty */
699 Assert(result >= 0);
700 return result;
701}

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

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

◆ bms_subset_compare()

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

Definition at line 445 of file bitmapset.c.

446{
447 BMS_Comparison result;
448 int shortlen;
449 int i;
450
451 Assert(bms_is_valid_set(a));
452 Assert(bms_is_valid_set(b));
453
454 /* Handle cases where either input is NULL */
455 if (a == NULL)
456 {
457 if (b == NULL)
458 return BMS_EQUAL;
459 return BMS_SUBSET1;
460 }
461 if (b == NULL)
462 return BMS_SUBSET2;
463
464 /* Check common words */
465 result = BMS_EQUAL; /* status so far */
466 shortlen = Min(a->nwords, b->nwords);
467 i = 0;
468 do
469 {
470 bitmapword aword = a->words[i];
471 bitmapword bword = b->words[i];
472
473 if ((aword & ~bword) != 0)
474 {
475 /* a is not a subset of b */
476 if (result == BMS_SUBSET1)
477 return BMS_DIFFERENT;
478 result = BMS_SUBSET2;
479 }
480 if ((bword & ~aword) != 0)
481 {
482 /* b is not a subset of a */
483 if (result == BMS_SUBSET2)
484 return BMS_DIFFERENT;
485 result = BMS_SUBSET1;
486 }
487 } while (++i < shortlen);
488 /* Check extra words */
489 if (a->nwords > b->nwords)
490 {
491 /* if a has more words then a is not a subset of b */
492 if (result == BMS_SUBSET1)
493 return BMS_DIFFERENT;
494 return BMS_SUBSET2;
495 }
496 else if (a->nwords < b->nwords)
497 {
498 /* if b has more words then b is not a subset of a */
499 if (result == BMS_SUBSET2)
500 return BMS_DIFFERENT;
501 return BMS_SUBSET1;
502 }
503 return result;
504}
BMS_Comparison
Definition: bitmapset.h:61
@ BMS_DIFFERENT
Definition: bitmapset.h:65
@ BMS_SUBSET1
Definition: bitmapset.h:63
@ BMS_EQUAL
Definition: bitmapset.h:62
@ BMS_SUBSET2
Definition: bitmapset.h:64

References a, Assert(), 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(), set_cheapest(), and test_bms_subset_compare().

◆ bms_union()

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

Definition at line 251 of file bitmapset.c.

252{
253 Bitmapset *result;
254 const Bitmapset *other;
255 int otherlen;
256 int i;
257
258 Assert(bms_is_valid_set(a));
259 Assert(bms_is_valid_set(b));
260
261 /* Handle cases where either input is NULL */
262 if (a == NULL)
263 return bms_copy(b);
264 if (b == NULL)
265 return bms_copy(a);
266 /* Identify shorter and longer input; copy the longer one */
267 if (a->nwords <= b->nwords)
268 {
269 result = bms_copy(b);
270 other = a;
271 }
272 else
273 {
274 result = bms_copy(a);
275 other = b;
276 }
277 /* And union the shorter input into the result */
278 otherlen = other->nwords;
279 i = 0;
280 do
281 {
282 result->words[i] |= other->words[i];
283 } while (++i < otherlen);
284 return result;
285}

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

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

AltStyle によって変換されたページ (->オリジナル) /