PostgreSQL Source Code  git master
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))
 
#define bmw_leftmost_one_pos(w)   pg_leftmost_one_pos32(w)
 
#define bmw_rightmost_one_pos(w)   pg_rightmost_one_pos32(w)
 
#define bmw_popcount(w)   pg_popcount32(w)
 

Functions

Bitmapsetbms_copy (const Bitmapset *a)
 
bool bms_equal (const Bitmapset *a, const Bitmapset *b)
 
int bms_compare (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_make_singleton (int x)
 
void bms_free (Bitmapset *a)
 
Bitmapsetbms_union (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_intersect (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_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)
 
Bitmapsetbms_add_member (Bitmapset *a, int x)
 
Bitmapsetbms_del_member (Bitmapset *a, int x)
 
Bitmapsetbms_add_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_replace_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_add_range (Bitmapset *a, int lower, int upper)
 
Bitmapsetbms_int_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_del_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_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.

◆ bmw_leftmost_one_pos

#define bmw_leftmost_one_pos (   w)    pg_leftmost_one_pos32(w)

Definition at line 76 of file bitmapset.c.

◆ bmw_popcount

#define bmw_popcount (   w)    pg_popcount32(w)

Definition at line 78 of file bitmapset.c.

◆ bmw_rightmost_one_pos

#define bmw_rightmost_one_pos (   w)    pg_rightmost_one_pos32(w)

Definition at line 77 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 1445 of file bitmapset.c.

1446 {
1447  Assert(keysize == sizeof(Bitmapset *));
1448  return bms_hash_value(*((const Bitmapset *const *) key));
1449 }
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1429
Assert(fmt[strlen(fmt) - 1] !='\n')

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

Referenced by build_join_rel_hash().

◆ bitmap_match()

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

Definition at line 1455 of file bitmapset.c.

1456 {
1457  Assert(keysize == sizeof(Bitmapset *));
1458  return !bms_equal(*((const Bitmapset *const *) key1),
1459  *((const Bitmapset *const *) key2));
1460 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:155

References Assert(), and bms_equal().

Referenced by build_join_rel_hash().

◆ bms_add_member()

Bitmapset* bms_add_member ( Bitmapset a,
int  x 
)

Definition at line 828 of file bitmapset.c.

829 {
830  int wordnum,
831  bitnum;
832 
833  Assert(bms_is_valid_set(a));
834 
835  if (x < 0)
836  elog(ERROR, "negative bitmapset member not allowed");
837  if (a == NULL)
838  return bms_make_singleton(x);
839 
840  wordnum = WORDNUM(x);
841  bitnum = BITNUM(x);
842 
843  /* enlarge the set if necessary */
844  if (wordnum >= a->nwords)
845  {
846  int oldnwords = a->nwords;
847  int i;
848 
849  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
850  a->nwords = wordnum + 1;
851  /* zero out the enlarged portion */
852  i = oldnwords;
853  do
854  {
855  a->words[i] = 0;
856  } while (++i < a->nwords);
857  }
858 
859  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
860 
861 #ifdef REALLOCATE_BITMAPSETS
862 
863  /*
864  * There's no guarantee that the repalloc returned a new pointer, so copy
865  * and free unconditionally here.
866  */
867  a = bms_copy_and_free(a);
868 #endif
869 
870  return a;
871 }
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:50
#define WORDNUM(x)
Definition: bitmapset.c:47
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:229
#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:224
int x
Definition: isn.c:71
int a
Definition: isn.c:69
int i
Definition: isn.c:73
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1421

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

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

931 {
932  Bitmapset *result;
933  const Bitmapset *other;
934  int otherlen;
935  int i;
936 
937  Assert(bms_is_valid_set(a));
938  Assert(bms_is_valid_set(b));
939 
940  /* Handle cases where either input is NULL */
941  if (a == NULL)
942  return bms_copy(b);
943  if (b == NULL)
944  {
945 #ifdef REALLOCATE_BITMAPSETS
946  a = bms_copy_and_free(a);
947 #endif
948 
949  return a;
950  }
951  /* Identify shorter and longer input; copy the longer one if needed */
952  if (a->nwords < b->nwords)
953  {
954  result = bms_copy(b);
955  other = a;
956  }
957  else
958  {
959  result = a;
960  other = b;
961  }
962  /* And union the shorter input into the result */
963  otherlen = other->nwords;
964  i = 0;
965  do
966  {
967  result->words[i] |= other->words[i];
968  } while (++i < otherlen);
969  if (result != a)
970  pfree(a);
971 #ifdef REALLOCATE_BITMAPSETS
972  else
973  result = bms_copy_and_free(result);
974 #endif
975 
976  return result;
977 }
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:135
int b
Definition: isn.c:70
void pfree(void *pointer)
Definition: mcxt.c:1401
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_targetlist(), adjust_standard_join_alias_expression(), build_index_paths(), choose_best_statistics(), choose_bitmap_and(), create_bitmap_and_path(), create_bitmap_or_path(), create_lateral_join_info(), CreatePartitionPruneState(), deconstruct_distribute(), deconstruct_recurse(), ExecFindMatchingSubPlans(), ExecInitAgg(), expand_partitioned_rtentry(), ExplainPreScanNode(), finalize_plan(), find_nonnullable_rels_walker(), foreign_join_ok(), get_eclass_indexes_for_relids(), get_param_path_clause_serials(), heap_update(), join_is_legal(), make_outerjoininfo(), mbms_add_members(), perform_pruning_combine_step(), pull_varnos_walker(), pullup_replace_vars_callback(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), remove_leftjoinrel_from_query(), remove_self_join_rel(), remove_self_joins_recurse(), transformOnConflictArbiter(), and try_partitionwise_join().

◆ bms_add_range()

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

Definition at line 1032 of file bitmapset.c.

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

◆ bms_compare()

int bms_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 196 of file bitmapset.c.

197 {
198  int i;
199 
200  Assert(bms_is_valid_set(a));
201  Assert(bms_is_valid_set(b));
202 
203  /* Handle cases where either input is NULL */
204  if (a == NULL)
205  return (b == NULL) ? 0 : -1;
206  else if (b == NULL)
207  return +1;
208 
209  /* the set with the most words must be greater */
210  if (a->nwords != b->nwords)
211  return (a->nwords > b->nwords) ? +1 : -1;
212 
213  i = a->nwords - 1;
214  do
215  {
216  bitmapword aw = a->words[i];
217  bitmapword bw = b->words[i];
218 
219  if (aw != bw)
220  return (aw > bw) ? +1 : -1;
221  } while (--i >= 0);
222  return 0;
223 }

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

Referenced by append_startup_cost_compare(), and append_total_cost_compare().

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

Definition at line 135 of file bitmapset.c.

136 {
137  Bitmapset *result;
138  size_t size;
139 
140  Assert(bms_is_valid_set(a));
141 
142  if (a == NULL)
143  return NULL;
144 
145  size = BITMAPSET_SIZE(a->nwords);
146  result = (Bitmapset *) palloc(size);
147  memcpy(result, a, size);
148  return result;
149 }
void * palloc(Size size)
Definition: mcxt.c:1197
static pg_noinline void Size size
Definition: slab.c:607

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

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_param_path_clause_serials(), get_relation_statistics_worker(), innerrel_is_unique_ext(), join_is_legal(), join_is_removable(), load_enum_cache_data(), logicalrep_partition_open(), logicalrep_relmap_update(), make_outerjoininfo(), partition_bounds_copy(), perform_pruning_combine_step(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_rel_from_restrictinfo(), reparameterize_path_by_child(), and replace_relid().

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 881 of file bitmapset.c.

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

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(), finalize_plan(), finalize_primnode(), find_hash_columns(), findDefaultOnlyColumns(), fixup_whole_row_references(), get_join_domain_min_rels(), get_matching_list_bounds(), logicalrep_rel_open(), make_outerjoininfo(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_eclass(), remove_rel_from_restrictinfo(), remove_self_joins_recurse(), replace_relid(), substitute_phv_relids_walker(), and TopologicalSort().

◆ bms_del_members()

Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 1174 of file bitmapset.c.

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

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(), make_outerjoininfo(), make_partition_pruneinfo(), min_join_parameterization(), NumRelids(), and remove_self_joins_recurse().

◆ bms_difference()

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

Definition at line 359 of file bitmapset.c.

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

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(), finalize_plan(), find_placeholder_info(), make_restrictinfo_internal(), pull_varnos_walker(), remove_nulling_relids_mutator(), and remove_useless_groupby_columns().

◆ bms_equal()

bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 155 of file bitmapset.c.

156 {
157  int i;
158 
159  Assert(bms_is_valid_set(a));
160  Assert(bms_is_valid_set(b));
161 
162  /* Handle cases where either input is NULL */
163  if (a == NULL)
164  {
165  if (b == NULL)
166  return true;
167  return false;
168  }
169  else if (b == NULL)
170  return false;
171 
172  /* can't be equal if the word counts don't match */
173  if (a->nwords != b->nwords)
174  return false;
175 
176  /* check each word matches */
177  i = 0;
178  do
179  {
180  if (a->words[i] != b->words[i])
181  return false;
182  } while (++i < a->nwords);
183 
184  return true;
185 }

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

Referenced by _equalBitmapset(), add_path_precheck(), add_paths_to_append_rel(), AlterPublicationTables(), assign_param_for_var(), bitmap_match(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_path(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), 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(), match_pathkeys_to_index(), merge_clump(), pgoutput_column_list_init(), populate_joinrel_with_paths(), pull_varnos_walker(), remove_self_join_rel(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), set_rel_pathlist(), standard_join_search(), and try_partitionwise_join().

◆ bms_free()

◆ bms_get_singleton_member()

bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 728 of file bitmapset.c.

729 {
730  int result = -1;
731  int nwords;
732  int wordnum;
733 
734  Assert(bms_is_valid_set(a));
735 
736  if (a == NULL)
737  return false;
738 
739  nwords = a->nwords;
740  wordnum = 0;
741  do
742  {
743  bitmapword w = a->words[wordnum];
744 
745  if (w != 0)
746  {
747  if (result >= 0 || HAS_MULTIPLE_ONES(w))
748  return false;
749  result = wordnum * BITS_PER_BITMAPWORD;
750  result += bmw_rightmost_one_pos(w);
751  }
752  } while (++wordnum < nwords);
753 
754  /* we don't expect non-NULL sets to be empty */
755  Assert(result >= 0);
756  *member = result;
757  return true;
758 }
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:77
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:72

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(), 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_varno_walker(), set_base_rel_consider_startup(), and statext_is_compatible_clause().

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset a)

Definition at line 1429 of file bitmapset.c.

1430 {
1431  Assert(bms_is_valid_set(a));
1432 
1433  if (a == NULL)
1434  return 0; /* All empty sets hash to 0 */
1435  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1436  a->nwords * sizeof(bitmapword)));
1437 }
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222

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

Referenced by bitmap_hash().

◆ bms_int_members()

Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 1122 of file bitmapset.c.

1123 {
1124  int lastnonzero;
1125  int shortlen;
1126  int i;
1127 
1128  Assert(bms_is_valid_set(a));
1129  Assert(bms_is_valid_set(b));
1130 
1131  /* Handle cases where either input is NULL */
1132  if (a == NULL)
1133  return NULL;
1134  if (b == NULL)
1135  {
1136  pfree(a);
1137  return NULL;
1138  }
1139 
1140  /* Intersect b into a; we need never copy */
1141  shortlen = Min(a->nwords, b->nwords);
1142  lastnonzero = -1;
1143  i = 0;
1144  do
1145  {
1146  a->words[i] &= b->words[i];
1147 
1148  if (a->words[i] != 0)
1149  lastnonzero = i;
1150  } while (++i < shortlen);
1151 
1152  /* If we computed an empty result, we must return NULL */
1153  if (lastnonzero == -1)
1154  {
1155  pfree(a);
1156  return NULL;
1157  }
1158 
1159  /* get rid of trailing zero words */
1160  a->nwords = lastnonzero + 1;
1161 
1162 #ifdef REALLOCATE_BITMAPSETS
1163  a = bms_copy_and_free(a);
1164 #endif
1165 
1166  return a;
1167 }
#define Min(x, y)
Definition: c.h:991

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

◆ bms_intersect()

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

Definition at line 305 of file bitmapset.c.

306 {
307  Bitmapset *result;
308  const Bitmapset *other;
309  int lastnonzero;
310  int resultlen;
311  int i;
312 
313  Assert(bms_is_valid_set(a));
314  Assert(bms_is_valid_set(b));
315 
316  /* Handle cases where either input is NULL */
317  if (a == NULL || b == NULL)
318  return NULL;
319 
320  /* Identify shorter and longer input; copy the shorter one */
321  if (a->nwords <= b->nwords)
322  {
323  result = bms_copy(a);
324  other = b;
325  }
326  else
327  {
328  result = bms_copy(b);
329  other = a;
330  }
331  /* And intersect the longer input with the result */
332  resultlen = result->nwords;
333  lastnonzero = -1;
334  i = 0;
335  do
336  {
337  result->words[i] &= other->words[i];
338 
339  if (result->words[i] != 0)
340  lastnonzero = i;
341  } while (++i < resultlen);
342  /* If we computed an empty result, we must return NULL */
343  if (lastnonzero == -1)
344  {
345  pfree(result);
346  return NULL;
347  }
348 
349  /* get rid of trailing zero words */
350  result->nwords = lastnonzero + 1;
351  return result;
352 }

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(), set_param_references(), and UpdateChangedParamSet().

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 523 of file bitmapset.c.

524 {
525  int wordnum,
526  bitnum;
527 
528  Assert(bms_is_valid_set(a));
529 
530  /* XXX better to just return false for x<0 ? */
531  if (x < 0)
532  elog(ERROR, "negative bitmapset member not allowed");
533  if (a == NULL)
534  return false;
535 
536  wordnum = WORDNUM(x);
537  bitnum = BITNUM(x);
538  if (wordnum >= a->nwords)
539  return false;
540  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
541  return true;
542  return false;
543 }

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

Referenced by 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(), ATExecDropNotNull(), 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(), column_in_column_list(), ComputePartitionAttrs(), consider_groupingsets_paths(), contain_invalid_rfcolumn_walker(), contain_placeholder_references_walker(), cost_incremental_sort(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_path(), deconstruct_distribute_oj_quals(), DefineIndex(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), do_analyze_rel(), dropconstraint_internal(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecEvalGroupingFunc(), ExecInitModifyTable(), execute_attr_map_cols(), expand_indexqual_rowcompare(), expand_single_inheritance_child(), ExplainSubPlans(), expr_is_nonnullable(), extractRemainingColumns(), ExtractReplicaIdentity(), fetch_remote_table_info(), filter_event_trigger(), find_hash_columns(), find_modifytable_subplan(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), gen_partprune_steps_internal(), gen_prune_steps_from_opexps(), generate_base_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_foreign_key_join_selectivity(), get_join_domain_min_rels(), get_matching_hash_bounds(), get_tablefunc(), get_translated_update_targetlist(), get_variable(), has_partition_attrs(), hashagg_spill_tuple(), HeapDetermineColumnsInfo(), identify_current_nestloop_params(), index_expression_changed_walker(), index_unchanged_by_update(), 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_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_invalid_subplans_as_finished(), mark_rels_nulled_by_join(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), mbms_is_member(), MergeAttributes(), partitions_are_ordered(), perform_pruning_base_step(), plpgsql_param_fetch(), postgresExplainForeignScan(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pub_collist_contains_invalid_column(), publication_translate_columns(), pullup_replace_vars_callback(), rangeTableEntry_used_walker(), remove_leftjoinrel_from_query(), remove_nulling_relids_mutator(), remove_rel_from_eclass(), remove_rel_from_query(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), replace_relid(), replace_varno_walker(), rewriteTargetListIU(), rewriteValuesRTE(), semijoin_target_ok(), send_relation_and_attrs(), set_join_column_names(), set_rtable_names(), statext_mcv_clauselist_selectivity(), substitute_phv_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), transformTableLikeClause(), translate_col_privs(), TriggerEnabled(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), tsvector_update_trigger(), update_eclasses(), use_physical_tlist(), and view_cols_are_auto_updatable().

◆ bms_is_subset()

bool bms_is_subset ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 425 of file bitmapset.c.

426 {
427  int i;
428 
429  Assert(bms_is_valid_set(a));
430  Assert(bms_is_valid_set(b));
431 
432  /* Handle cases where either input is NULL */
433  if (a == NULL)
434  return true; /* empty set is a subset of anything */
435  if (b == NULL)
436  return false;
437 
438  /* 'a' can't be a subset of 'b' if it contains more words */
439  if (a->nwords > b->nwords)
440  return false;
441 
442  /* Check all 'a' members are set in 'b' */
443  i = 0;
444  do
445  {
446  if ((a->words[i] & ~b->words[i]) != 0)
447  return false;
448  } while (++i < a->nwords);
449  return true;
450 }

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_targetlist(), build_joinrel_tlist(), check_functional_grouping(), check_index_only(), choose_best_statistics(), clause_sides_match_join(), compute_semijoin_info(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_index_paths(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), find_join_domain(), foreign_join_ok(), generate_implied_equalities_for_column(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_joinrel_parampathinfo(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), identify_current_nestloop_params(), initial_cost_mergejoin(), innerrel_is_unique_ext(), is_simple_subquery(), join_clause_is_movable_into(), join_is_legal(), join_is_removable(), jointree_contains_lateral_outer_refs(), make_outerjoininfo(), pg_get_expr_worker(), populate_joinrel_with_paths(), process_implied_equality(), process_subquery_nestloop_params(), 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(), try_partial_nestloop_path(), and use_physical_tlist().

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

Definition at line 1243 of file bitmapset.c.

1244 {
1245  Bitmapset *result;
1246  Bitmapset *other;
1247  int otherlen;
1248  int i;
1249 
1250  Assert(bms_is_valid_set(a));
1251  Assert(bms_is_valid_set(b));
1252 
1253  /* Handle cases where either input is NULL */
1254  if (a == NULL)
1255  {
1256 #ifdef REALLOCATE_BITMAPSETS
1257  b = bms_copy_and_free(b);
1258 #endif
1259 
1260  return b;
1261  }
1262  if (b == NULL)
1263  {
1264 #ifdef REALLOCATE_BITMAPSETS
1265  a = bms_copy_and_free(a);
1266 #endif
1267 
1268  return a;
1269  }
1270 
1271  /* Identify shorter and longer input; use longer one as result */
1272  if (a->nwords < b->nwords)
1273  {
1274  result = b;
1275  other = a;
1276  }
1277  else
1278  {
1279  result = a;
1280  other = b;
1281  }
1282  /* And union the shorter input into the result */
1283  otherlen = other->nwords;
1284  i = 0;
1285  do
1286  {
1287  result->words[i] |= other->words[i];
1288  } while (++i < otherlen);
1289  if (other != result) /* pure paranoia */
1290  pfree(other);
1291 
1292 #ifdef REALLOCATE_BITMAPSETS
1293  result = bms_copy_and_free(result);
1294 #endif
1295 
1296  return result;
1297 }

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

◆ bms_make_singleton()

◆ bms_member_index()

int bms_member_index ( Bitmapset a,
int  x 
)

Definition at line 552 of file bitmapset.c.

553 {
554  int i;
555  int bitnum;
556  int wordnum;
557  int result = 0;
558  bitmapword mask;
559 
560  Assert(bms_is_valid_set(a));
561 
562  /* return -1 if not a member of the bitmap */
563  if (!bms_is_member(x, a))
564  return -1;
565 
566  wordnum = WORDNUM(x);
567  bitnum = BITNUM(x);
568 
569  /* count bits in preceding words */
570  for (i = 0; i < wordnum; i++)
571  {
572  bitmapword w = a->words[i];
573 
574  /* No need to count the bits in a zero word */
575  if (w != 0)
576  result += bmw_popcount(w);
577  }
578 
579  /*
580  * Now add bits of the last word, but only those before the item. We can
581  * do that by applying a mask and then using popcount again. To get
582  * 0-based index, we want to count only preceding bits, not the item
583  * itself, so we subtract 1.
584  */
585  mask = ((bitmapword) 1 << bitnum) - 1;
586  result += bmw_popcount(a->words[wordnum] & mask);
587 
588  return result;
589 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:523
#define bmw_popcount(w)
Definition: bitmapset.c:78

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

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

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 794 of file bitmapset.c.

795 {
796  BMS_Membership result = BMS_EMPTY_SET;
797  int nwords;
798  int wordnum;
799 
800  Assert(bms_is_valid_set(a));
801 
802  if (a == NULL)
803  return BMS_EMPTY_SET;
804 
805  nwords = a->nwords;
806  wordnum = 0;
807  do
808  {
809  bitmapword w = a->words[wordnum];
810 
811  if (w != 0)
812  {
813  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
814  return BMS_MULTIPLE;
815  result = BMS_SINGLETON;
816  }
817  } while (++wordnum < nwords);
818  return result;
819 }
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(), find_nonnullable_rels_walker(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), get_foreign_key_join_selectivity(), grouping_planner(), process_implied_equality(), relation_has_unique_index_ext(), remove_self_join_rel(), remove_self_joins_recurse(), remove_useless_groupby_columns(), set_subquery_pathlist(), set_tablesample_rel_pathlist(), split_selfjoin_quals(), and statext_mcv_clauselist_selectivity().

◆ bms_next_member()

int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1319 of file bitmapset.c.

1320 {
1321  int nwords;
1322  int wordnum;
1323  bitmapword mask;
1324 
1325  Assert(bms_is_valid_set(a));
1326 
1327  if (a == NULL)
1328  return -2;
1329  nwords = a->nwords;
1330  prevbit++;
1331  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1332  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1333  {
1334  bitmapword w = a->words[wordnum];
1335 
1336  /* ignore bits before prevbit */
1337  w &= mask;
1338 
1339  if (w != 0)
1340  {
1341  int result;
1342 
1343  result = wordnum * BITS_PER_BITMAPWORD;
1344  result += bmw_rightmost_one_pos(w);
1345  return result;
1346  }
1347 
1348  /* in subsequent words, consider all bits */
1349  mask = (~(bitmapword) 0);
1350  }
1351  return -2;
1352 }

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(), AdjustNotNullInheritance(), alias_relid_set(), apply_scanjoin_target_to_paths(), approximate_joinrel_size(), ATInheritAdjustNotNulls(), build_attnums_array(), check_relation_privileges(), check_selective_binary_conversion(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), clauselist_apply_dependencies(), ComputePartitionAttrs(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_partitionwise_grouping_paths(), CreateStatistics(), deparseLockingClause(), dependencies_clauselist_selectivity(), EstimateParamExecSpace(), ExecAppendAsyncBegin(), ExecAppendAsyncEventWait(), ExecAppendAsyncRequest(), ExecCheckOneRelPerms(), ExecCheckPermissionsModified(), ExecInitAgg(), ExecInitAppend(), ExecInitMergeAppend(), ExecMergeAppend(), ExecReScanAppend(), ExecScanReScan(), ExecSetParamPlanMulti(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_dependent_phvs_in_jointree(), find_hash_columns(), find_matching_subplans_recurse(), fixup_inherited_columns(), format_expr_params(), generate_base_implied_equalities(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_loop_count(), get_matching_partitions(), grouping_planner(), has_relevant_eclass_joinclause(), have_relevant_eclass_joinclause(), HeapDetermineColumnsInfo(), logicalrep_rel_mark_updatable(), logicalrep_report_missing_attrs(), lookup_var_attr_stats(), make_build_data(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), mark_rels_nulled_by_join(), match_eclasses_to_foreign_key_col(), offset_relid_set(), outBitmapset(), PartitionPruneFixSubPlanMap(), postgresBeginForeignScan(), postgresExplainForeignScan(), postgresPlanForeignModify(), pub_collist_contains_invalid_column(), remove_join_clause_from_rels(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_results_recurse(), remove_useless_self_joins(), SerializeParamExecParams(), show_eval_params(), statext_is_compatible_clause(), and transformTableLikeClause().

◆ bms_nonempty_difference()

bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 654 of file bitmapset.c.

655 {
656  int i;
657 
658  Assert(bms_is_valid_set(a));
659  Assert(bms_is_valid_set(b));
660 
661  /* Handle cases where either input is NULL */
662  if (a == NULL)
663  return false;
664  if (b == NULL)
665  return true;
666  /* if 'a' has more words then it must contain additional members */
667  if (a->nwords > b->nwords)
668  return true;
669  /* Check all 'a' members are set in 'b' */
670  i = 0;
671  do
672  {
673  if ((a->words[i] & ~b->words[i]) != 0)
674  return true;
675  } while (++i < a->nwords);
676  return false;
677 }

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

◆ bms_num_members()

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 595 of file bitmapset.c.

596 {
597  int shortlen;
598  int i;
599 
600  Assert(bms_is_valid_set(a));
601  Assert(bms_is_valid_set(b));
602 
603  /* Handle cases where either input is NULL */
604  if (a == NULL || b == NULL)
605  return false;
606  /* Check words in common */
607  shortlen = Min(a->nwords, b->nwords);
608  i = 0;
609  do
610  {
611  if ((a->words[i] & b->words[i]) != 0)
612  return true;
613  } while (++i < shortlen);
614  return false;
615 }

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(), ExecInitStoredGenerated(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_partition_attrs(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), join_clause_is_movable_into(), join_clause_is_movable_to(), join_is_legal(), join_is_removable(), join_search_one_level(), make_join_rel(), make_outerjoininfo(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo_internal(), mbms_overlap_sets(), partitions_are_ordered(), reduce_outer_joins_pass2(), remove_nulling_relids_mutator(), remove_self_joins_recurse(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), set_append_rel_size(), subbuild_joinrel_restrictlist(), 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 621 of file bitmapset.c.

622 {
623  ListCell *lc;
624  int wordnum,
625  bitnum;
626 
627  Assert(bms_is_valid_set(a));
628 
629  if (a == NULL || b == NIL)
630  return false;
631 
632  foreach(lc, b)
633  {
634  int x = lfirst_int(lc);
635 
636  if (x < 0)
637  elog(ERROR, "negative bitmapset member not allowed");
638  wordnum = WORDNUM(x);
639  bitnum = BITNUM(x);
640  if (wordnum < a->nwords)
641  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
642  return true;
643  }
644 
645  return false;
646 }
#define NIL
Definition: pg_list.h:68
#define lfirst_int(lc)
Definition: pg_list.h:173

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

Referenced by preprocess_grouping_sets().

◆ bms_prev_member()

int bms_prev_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1380 of file bitmapset.c.

1381 {
1382  int wordnum;
1383  int ushiftbits;
1384  bitmapword mask;
1385 
1386  Assert(bms_is_valid_set(a));
1387 
1388  /*
1389  * If set is NULL or if there are no more bits to the right then we've
1390  * nothing to do.
1391  */
1392  if (a == NULL || prevbit == 0)
1393  return -2;
1394 
1395  /* transform -1 to the highest possible bit we could have set */
1396  if (prevbit == -1)
1397  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1398  else
1399  prevbit--;
1400 
1401  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1402  mask = (~(bitmapword) 0) >> ushiftbits;
1403  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1404  {
1405  bitmapword w = a->words[wordnum];
1406 
1407  /* mask out bits left of prevbit */
1408  w &= mask;
1409 
1410  if (w != 0)
1411  {
1412  int result;
1413 
1414  result = wordnum * BITS_PER_BITMAPWORD;
1415  result += bmw_leftmost_one_pos(w);
1416  return result;
1417  }
1418 
1419  /* in subsequent words, consider all bits */
1420  mask = (~(bitmapword) 0);
1421  }
1422  return -2;
1423 }
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.c:76

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

Referenced by choose_next_subplan_locally().

◆ bms_replace_members()

Bitmapset* bms_replace_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 985 of file bitmapset.c.

986 {
987  int i;
988 
989  Assert(bms_is_valid_set(a));
990  Assert(bms_is_valid_set(b));
991 
992  if (a == NULL)
993  return bms_copy(b);
994  if (b == NULL)
995  {
996  pfree(a);
997  return NULL;
998  }
999 
1000  if (a->nwords < b->nwords)
1001  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
1002 
1003  i = 0;
1004  do
1005  {
1006  a->words[i] = b->words[i];
1007  } while (++i < b->nwords);
1008 
1009  a->nwords = b->nwords;
1010 
1011 #ifdef REALLOCATE_BITMAPSETS
1012 
1013  /*
1014  * There's no guarantee that the repalloc returned a new pointer, so copy
1015  * and free unconditionally here.
1016  */
1017  a = bms_copy_and_free(a);
1018 #endif
1019 
1020  return a;
1021 }

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

Referenced by DiscreteKnapsack().

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

Definition at line 685 of file bitmapset.c.

686 {
687  int result = -1;
688  int nwords;
689  int wordnum;
690 
691  Assert(bms_is_valid_set(a));
692 
693  if (a == NULL)
694  elog(ERROR, "bitmapset is empty");
695 
696  nwords = a->nwords;
697  wordnum = 0;
698  do
699  {
700  bitmapword w = a->words[wordnum];
701 
702  if (w != 0)
703  {
704  if (result >= 0 || HAS_MULTIPLE_ONES(w))
705  elog(ERROR, "bitmapset has multiple members");
706  result = wordnum * BITS_PER_BITMAPWORD;
707  result += bmw_rightmost_one_pos(w);
708  }
709  } while (++wordnum < nwords);
710 
711  /* we don't expect non-NULL sets to be empty */
712  Assert(result >= 0);
713  return result;
714 }

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

◆ bms_subset_compare()

BMS_Comparison bms_subset_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 458 of file bitmapset.c.

459 {
460  BMS_Comparison result;
461  int shortlen;
462  int i;
463 
464  Assert(bms_is_valid_set(a));
465  Assert(bms_is_valid_set(b));
466 
467  /* Handle cases where either input is NULL */
468  if (a == NULL)
469  {
470  if (b == NULL)
471  return BMS_EQUAL;
472  return BMS_SUBSET1;
473  }
474  if (b == NULL)
475  return BMS_SUBSET2;
476 
477  /* Check common words */
478  result = BMS_EQUAL; /* status so far */
479  shortlen = Min(a->nwords, b->nwords);
480  i = 0;
481  do
482  {
483  bitmapword aword = a->words[i];
484  bitmapword bword = b->words[i];
485 
486  if ((aword & ~bword) != 0)
487  {
488  /* a is not a subset of b */
489  if (result == BMS_SUBSET1)
490  return BMS_DIFFERENT;
491  result = BMS_SUBSET2;
492  }
493  if ((bword & ~aword) != 0)
494  {
495  /* b is not a subset of a */
496  if (result == BMS_SUBSET2)
497  return BMS_DIFFERENT;
498  result = BMS_SUBSET1;
499  }
500  } while (++i < shortlen);
501  /* Check extra words */
502  if (a->nwords > b->nwords)
503  {
504  /* if a has more words then a is not a subset of b */
505  if (result == BMS_SUBSET1)
506  return BMS_DIFFERENT;
507  return BMS_SUBSET2;
508  }
509  else if (a->nwords < b->nwords)
510  {
511  /* if b has more words then b is not a subset of a */
512  if (result == BMS_SUBSET2)
513  return BMS_DIFFERENT;
514  return BMS_SUBSET1;
515  }
516  return result;
517 }
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(), and set_cheapest().

◆ bms_union()

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

Definition at line 264 of file bitmapset.c.

265 {
266  Bitmapset *result;
267  const Bitmapset *other;
268  int otherlen;
269  int i;
270 
271  Assert(bms_is_valid_set(a));
272  Assert(bms_is_valid_set(b));
273 
274  /* Handle cases where either input is NULL */
275  if (a == NULL)
276  return bms_copy(b);
277  if (b == NULL)
278  return bms_copy(a);
279  /* Identify shorter and longer input; copy the longer one */
280  if (a->nwords <= b->nwords)
281  {
282  result = bms_copy(b);
283  other = a;
284  }
285  else
286  {
287  result = bms_copy(a);
288  other = b;
289  }
290  /* And union the shorter input into the result */
291  otherlen = other->nwords;
292  i = 0;
293  do
294  {
295  result->words[i] |= other->words[i];
296  } while (++i < otherlen);
297  return result;
298 }

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

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