PostgreSQL Source Code  git master
bitmapset.c File Reference
#include "postgres.h"
#include "nodes/bitmapset.h"
#include "nodes/pg_list.h"
#include "port/pg_bitutils.h"
#include "utils/hashutils.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)
 
bool bms_is_empty (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_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_first_member (Bitmapset *a)
 
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)
 

Macro Definition Documentation

◆ BITMAPSET_SIZE

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

Definition at line 32 of file bitmapset.c.

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

◆ BITNUM

◆ bmw_leftmost_one_pos

#define bmw_leftmost_one_pos (   w)    pg_leftmost_one_pos32(w)

Definition at line 58 of file bitmapset.c.

Referenced by bms_prev_member().

◆ bmw_popcount

#define bmw_popcount (   w)    pg_popcount32(w)

Definition at line 60 of file bitmapset.c.

Referenced by bms_member_index(), and bms_num_members().

◆ bmw_rightmost_one_pos

#define bmw_rightmost_one_pos (   w)    pg_rightmost_one_pos32(w)

◆ HAS_MULTIPLE_ONES

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

Definition at line 54 of file bitmapset.c.

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

◆ RIGHTMOST_ONE

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

Definition at line 52 of file bitmapset.c.

Referenced by bms_first_member().

◆ WORDNUM

Function Documentation

◆ bms_add_member()

Bitmapset* bms_add_member ( Bitmapset a,
int  x 
)

Definition at line 736 of file bitmapset.c.

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

Referenced by _readBitmapset(), add_child_rel_equivalences(), adjust_appendrel_attrs_multilevel(), adjust_child_relids(), adjust_child_relids_multilevel(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), build_subplan(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), do_analyze_rel(), DoCopy(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecFindInitialMatchingSubPlans(), ExecInitAgg(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanGather(), ExecReScanGatherMerge(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), ExecSetParamPlan(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), fetch_remote_table_info(), fetch_statentries_for_relation(), finalize_plan(), finalize_primnode(), find_childrel_parents(), find_hash_columns(), find_matching_subplans_recurse(), find_unaggregated_cols_walker(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), gen_partprune_steps_internal(), generate_base_implied_equalities(), get_eclass_for_sort_expr(), get_matching_partitions(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineModifiedColumns(), infer_arbiter_indexes(), inheritance_planner(), intorel_startup(), load_enum_cache_data(), logicalrep_read_attrs(), make_datum_param(), make_modifytable(), make_one_rel(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), markRTEForSelectPriv(), offset_relid_set(), preprocess_grouping_sets(), pull_exec_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), RelationGetIndexAttrBitmap(), remove_useless_groupby_columns(), remove_useless_results_recurse(), rewriteTargetView(), RI_Initial_Check(), set_customscan_references(), set_foreignscan_references(), set_join_column_names(), set_param_references(), SS_identify_outer_params(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), statext_ndistinct_build(), statext_ndistinct_deserialize(), transformGroupClause(), transformGroupClauseList(), transformInsertStmt(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), use_physical_tlist(), and view_cols_are_auto_updatable().

737 {
738  int wordnum,
739  bitnum;
740 
741  if (x < 0)
742  elog(ERROR, "negative bitmapset member not allowed");
743  if (a == NULL)
744  return bms_make_singleton(x);
745  wordnum = WORDNUM(x);
746  bitnum = BITNUM(x);
747 
748  /* enlarge the set if necessary */
749  if (wordnum >= a->nwords)
750  {
751  int oldnwords = a->nwords;
752  int i;
753 
754  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
755  a->nwords = wordnum + 1;
756  /* zero out the enlarged portion */
757  for (i = oldnwords; i < a->nwords; i++)
758  a->words[i] = 0;
759  }
760 
761  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
762  return a;
763 }
int nwords
Definition: bitmapset.h:51
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
#define ERROR
Definition: elog.h:43
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:186
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1069
#define elog(elevel,...)
Definition: elog.h:228
int i

◆ bms_add_members()

Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 793 of file bitmapset.c.

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

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_eq_member(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), build_index_paths(), check_outerjoin_delay(), choose_bitmap_and(), create_lateral_join_info(), deconstruct_recurse(), DiscreteKnapsack(), ExecCreatePartitionPruneState(), ExecFindInitialMatchingSubPlans(), ExecFindMatchingSubPlans(), ExecInitAgg(), ExplainPreScanNode(), finalize_plan(), find_nonnullable_rels_walker(), foreign_join_ok(), get_eclass_indexes_for_relids(), heap_update(), join_is_legal(), make_outerjoininfo(), perform_pruning_combine_step(), pull_varnos_walker(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), statext_mcv_clauselist_selectivity(), transformOnConflictArbiter(), and update_placeholder_eval_levels().

794 {
795  Bitmapset *result;
796  const Bitmapset *other;
797  int otherlen;
798  int i;
799 
800  /* Handle cases where either input is NULL */
801  if (a == NULL)
802  return bms_copy(b);
803  if (b == NULL)
804  return a;
805  /* Identify shorter and longer input; copy the longer one if needed */
806  if (a->nwords < b->nwords)
807  {
808  result = bms_copy(b);
809  other = a;
810  }
811  else
812  {
813  result = a;
814  other = b;
815  }
816  /* And union the shorter input into the result */
817  otherlen = other->nwords;
818  for (i = 0; i < otherlen; i++)
819  result->words[i] |= other->words[i];
820  if (result != a)
821  pfree(a);
822  return result;
823 }
int nwords
Definition: bitmapset.h:51
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
void pfree(void *pointer)
Definition: mcxt.c:1056
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_add_range()

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

Definition at line 834 of file bitmapset.c.

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

Referenced by ExecInitAppend(), ExecInitMergeAppend(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_partitions(), get_matching_range_bounds(), make_partition_pruneinfo(), perform_pruning_combine_step(), and prune_append_rel_partitions().

835 {
836  int lwordnum,
837  lbitnum,
838  uwordnum,
839  ushiftbits,
840  wordnum;
841 
842  /* do nothing if nothing is called for, without further checking */
843  if (upper < lower)
844  return a;
845 
846  if (lower < 0)
847  elog(ERROR, "negative bitmapset member not allowed");
848  uwordnum = WORDNUM(upper);
849 
850  if (a == NULL)
851  {
852  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
853  a->nwords = uwordnum + 1;
854  }
855  else if (uwordnum >= a->nwords)
856  {
857  int oldnwords = a->nwords;
858  int i;
859 
860  /* ensure we have enough words to store the upper bit */
861  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
862  a->nwords = uwordnum + 1;
863  /* zero out the enlarged portion */
864  for (i = oldnwords; i < a->nwords; i++)
865  a->words[i] = 0;
866  }
867 
868  wordnum = lwordnum = WORDNUM(lower);
869 
870  lbitnum = BITNUM(lower);
871  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
872 
873  /*
874  * Special case when lwordnum is the same as uwordnum we must perform the
875  * upper and lower masking on the word.
876  */
877  if (lwordnum == uwordnum)
878  {
879  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
880  & (~(bitmapword) 0) >> ushiftbits;
881  }
882  else
883  {
884  /* turn on lbitnum and all bits left of it */
885  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
886 
887  /* turn on all bits for any intermediate words */
888  while (wordnum < uwordnum)
889  a->words[wordnum++] = ~(bitmapword) 0;
890 
891  /* turn on upper's bit and all bits right of it. */
892  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
893  }
894 
895  return a;
896 }
int nwords
Definition: bitmapset.h:51
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define BITNUM(x)
Definition: bitmapset.c:30
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
uint32 bitmapword
Definition: bitmapset.h:44
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
void * palloc0(Size size)
Definition: mcxt.c:980
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1069
#define elog(elevel,...)
Definition: elog.h:228
int i

◆ bms_compare()

int bms_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 147 of file bitmapset.c.

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

Referenced by append_startup_cost_compare(), and append_total_cost_compare().

148 {
149  int shortlen;
150  int i;
151 
152  /* Handle cases where either input is NULL */
153  if (a == NULL)
154  return bms_is_empty(b) ? 0 : -1;
155  else if (b == NULL)
156  return bms_is_empty(a) ? 0 : +1;
157  /* Handle cases where one input is longer than the other */
158  shortlen = Min(a->nwords, b->nwords);
159  for (i = shortlen; i < a->nwords; i++)
160  {
161  if (a->words[i] != 0)
162  return +1;
163  }
164  for (i = shortlen; i < b->nwords; i++)
165  {
166  if (b->words[i] != 0)
167  return -1;
168  }
169  /* Process words in common */
170  i = shortlen;
171  while (--i >= 0)
172  {
173  bitmapword aw = a->words[i];
174  bitmapword bw = b->words[i];
175 
176  if (aw != bw)
177  return (aw > bw) ? +1 : -1;
178  }
179  return 0;
180 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
int i

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

Definition at line 74 of file bitmapset.c.

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

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

75 {
76  Bitmapset *result;
77  size_t size;
78 
79  if (a == NULL)
80  return NULL;
81  size = BITMAPSET_SIZE(a->nwords);
82  result = (Bitmapset *) palloc(size);
83  memcpy(result, a, size);
84  return result;
85 }
int nwords
Definition: bitmapset.h:51
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
void * palloc(Size size)
Definition: mcxt.c:949

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 773 of file bitmapset.c.

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

Referenced by adjust_child_relids(), adjust_relid_set(), build_index_paths(), BuildParameterizedTidPaths(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), finalize_plan(), finalize_primnode(), find_hash_columns(), fixup_whole_row_references(), get_matching_list_bounds(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_query(), substitute_phv_relids_walker(), and TopologicalSort().

774 {
775  int wordnum,
776  bitnum;
777 
778  if (x < 0)
779  elog(ERROR, "negative bitmapset member not allowed");
780  if (a == NULL)
781  return NULL;
782  wordnum = WORDNUM(x);
783  bitnum = BITNUM(x);
784  if (wordnum < a->nwords)
785  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
786  return a;
787 }
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define elog(elevel,...)
Definition: elog.h:228

◆ bms_del_members()

Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 928 of file bitmapset.c.

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

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

929 {
930  int shortlen;
931  int i;
932 
933  /* Handle cases where either input is NULL */
934  if (a == NULL)
935  return NULL;
936  if (b == NULL)
937  return a;
938  /* Remove b's bits from a; we need never copy */
939  shortlen = Min(a->nwords, b->nwords);
940  for (i = 0; i < shortlen; i++)
941  a->words[i] &= ~b->words[i];
942  return a;
943 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_difference()

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

Definition at line 291 of file bitmapset.c.

References bms_copy(), i, Min, 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(), finalize_plan(), find_placeholder_info(), and remove_useless_groupby_columns().

292 {
293  Bitmapset *result;
294  int shortlen;
295  int i;
296 
297  /* Handle cases where either input is NULL */
298  if (a == NULL)
299  return NULL;
300  if (b == NULL)
301  return bms_copy(a);
302  /* Copy the left input */
303  result = bms_copy(a);
304  /* And remove b's bits from result */
305  shortlen = Min(a->nwords, b->nwords);
306  for (i = 0; i < shortlen; i++)
307  result->words[i] &= ~b->words[i];
308  return result;
309 }
int nwords
Definition: bitmapset.h:51
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
#define Min(x, y)
Definition: c.h:905
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_equal()

bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 94 of file bitmapset.c.

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

Referenced by add_path_precheck(), add_paths_to_append_rel(), adjust_appendrel_attrs_multilevel(), adjust_child_relids_multilevel(), bitmap_match(), bms_equal_any(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_path(), extract_rollup_sets(), fetch_upper_rel(), find_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(), has_join_restriction(), infer_arbiter_indexes(), is_safe_restriction_clause_for(), join_is_legal(), make_one_rel(), make_partitionedrel_pruneinfo(), match_pathkeys_to_index(), populate_joinrel_with_paths(), and try_partitionwise_join().

95 {
96  const Bitmapset *shorter;
97  const Bitmapset *longer;
98  int shortlen;
99  int longlen;
100  int i;
101 
102  /* Handle cases where either input is NULL */
103  if (a == NULL)
104  {
105  if (b == NULL)
106  return true;
107  return bms_is_empty(b);
108  }
109  else if (b == NULL)
110  return bms_is_empty(a);
111  /* Identify shorter and longer input */
112  if (a->nwords <= b->nwords)
113  {
114  shorter = a;
115  longer = b;
116  }
117  else
118  {
119  shorter = b;
120  longer = a;
121  }
122  /* And process */
123  shortlen = shorter->nwords;
124  for (i = 0; i < shortlen; i++)
125  {
126  if (shorter->words[i] != longer->words[i])
127  return false;
128  }
129  longlen = longer->nwords;
130  for (; i < longlen; i++)
131  {
132  if (longer->words[i] != 0)
133  return false;
134  }
135  return true;
136 }
int nwords
Definition: bitmapset.h:51
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
int i

◆ bms_first_member()

int bms_first_member ( Bitmapset a)

Definition at line 996 of file bitmapset.c.

References BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, Bitmapset::nwords, RIGHTMOST_ONE, and Bitmapset::words.

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

997 {
998  int nwords;
999  int wordnum;
1000 
1001  if (a == NULL)
1002  return -1;
1003  nwords = a->nwords;
1004  for (wordnum = 0; wordnum < nwords; wordnum++)
1005  {
1006  bitmapword w = a->words[wordnum];
1007 
1008  if (w != 0)
1009  {
1010  int result;
1011 
1012  w = RIGHTMOST_ONE(w);
1013  a->words[wordnum] &= ~w;
1014 
1015  result = wordnum * BITS_PER_BITMAPWORD;
1016  result += bmw_rightmost_one_pos(w);
1017  return result;
1018  }
1019  }
1020  return -1;
1021 }
int nwords
Definition: bitmapset.h:51
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:59
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define RIGHTMOST_ONE(x)
Definition: bitmapset.c:52

◆ bms_free()

◆ bms_get_singleton_member()

bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 615 of file bitmapset.c.

References BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, HAS_MULTIPLE_ONES, Bitmapset::nwords, and Bitmapset::words.

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

616 {
617  int result = -1;
618  int nwords;
619  int wordnum;
620 
621  if (a == NULL)
622  return false;
623  nwords = a->nwords;
624  for (wordnum = 0; wordnum < nwords; wordnum++)
625  {
626  bitmapword w = a->words[wordnum];
627 
628  if (w != 0)
629  {
630  if (result >= 0 || HAS_MULTIPLE_ONES(w))
631  return false;
632  result = wordnum * BITS_PER_BITMAPWORD;
633  result += bmw_rightmost_one_pos(w);
634  }
635  }
636  if (result < 0)
637  return false;
638  *member = result;
639  return true;
640 }
int nwords
Definition: bitmapset.h:51
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:54
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:59
uint32 bitmapword
Definition: bitmapset.h:44
Oid member
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset a)

Definition at line 1154 of file bitmapset.c.

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

Referenced by bitmap_hash().

1155 {
1156  int lastword;
1157 
1158  if (a == NULL)
1159  return 0; /* All empty sets hash to 0 */
1160  for (lastword = a->nwords; --lastword >= 0;)
1161  {
1162  if (a->words[lastword] != 0)
1163  break;
1164  }
1165  if (lastword < 0)
1166  return 0; /* All empty sets hash to 0 */
1167  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1168  (lastword + 1) * sizeof(bitmapword)));
1169 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
int nwords
Definition: bitmapset.h:51
Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.c:148
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_int_members()

Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 902 of file bitmapset.c.

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

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

903 {
904  int shortlen;
905  int i;
906 
907  /* Handle cases where either input is NULL */
908  if (a == NULL)
909  return NULL;
910  if (b == NULL)
911  {
912  pfree(a);
913  return NULL;
914  }
915  /* Intersect b into a; we need never copy */
916  shortlen = Min(a->nwords, b->nwords);
917  for (i = 0; i < shortlen; i++)
918  a->words[i] &= b->words[i];
919  for (; i < a->nwords; i++)
920  a->words[i] = 0;
921  return a;
922 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
void pfree(void *pointer)
Definition: mcxt.c:1056
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_intersect()

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

Definition at line 259 of file bitmapset.c.

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

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

260 {
261  Bitmapset *result;
262  const Bitmapset *other;
263  int resultlen;
264  int i;
265 
266  /* Handle cases where either input is NULL */
267  if (a == NULL || b == NULL)
268  return NULL;
269  /* Identify shorter and longer input; copy the shorter one */
270  if (a->nwords <= b->nwords)
271  {
272  result = bms_copy(a);
273  other = b;
274  }
275  else
276  {
277  result = bms_copy(b);
278  other = a;
279  }
280  /* And intersect the longer input with the result */
281  resultlen = result->nwords;
282  for (i = 0; i < resultlen; i++)
283  result->words[i] &= other->words[i];
284  return result;
285 }
int nwords
Definition: bitmapset.h:51
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_is_empty()

bool bms_is_empty ( const Bitmapset a)

Definition at line 701 of file bitmapset.c.

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

Referenced by add_eq_member(), add_vars_to_targetlist(), bms_compare(), bms_equal(), bms_is_subset(), bms_nonempty_difference(), bms_subset_compare(), build_index_paths(), build_join_rel(), calc_nestloop_required_outer(), check_index_predicates(), compute_semijoin_info(), consider_groupingsets_paths(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_foreign_join_path(), create_foreign_upper_path(), create_lateral_join_info(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecFindInitialMatchingSubPlans(), ExecInitAppend(), ExecInitMergeAppend(), ExecInitParallelPlan(), ExecParallelReinitialize(), ExecReScanSetParamPlan(), ExtractReplicaIdentity(), finalize_plan(), find_em_expr_for_rel(), find_nonnullable_rels_walker(), find_placeholder_info(), find_single_rel_for_clauses(), gen_partprune_steps_internal(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parallel_safe_total_inner(), get_joinrel_parampathinfo(), get_matching_list_bounds(), get_matching_range_bounds(), get_useful_ecs_for_relation(), GetParentedForeignKeyRefs(), hash_inner_and_outer(), is_pseudo_constant_clause_relids(), make_outerjoininfo(), make_partitionedrel_pruneinfo(), make_restrictinfo_internal(), match_clause_to_partition_key(), match_unsorted_outer(), min_join_parameterization(), postgresGetForeignJoinPaths(), postgresGetForeignPaths(), preprocess_grouping_sets(), process_equivalence(), pull_varnos_walker(), recurse_set_operations(), relation_has_unique_index_for(), relation_is_updatable(), remove_rel_from_query(), remove_result_refs(), rewriteTargetView(), sepgsql_dml_privileges(), set_subquery_pathlist(), sort_inner_and_outer(), substitute_phv_relids_walker(), TopologicalSort(), try_partial_hashjoin_path(), try_partial_mergejoin_path(), try_partial_nestloop_path(), UpdateChangedParamSet(), and use_physical_tlist().

702 {
703  int nwords;
704  int wordnum;
705 
706  if (a == NULL)
707  return true;
708  nwords = a->nwords;
709  for (wordnum = 0; wordnum < nwords; wordnum++)
710  {
711  bitmapword w = a->words[wordnum];
712 
713  if (w != 0)
714  return false;
715  }
716  return true;
717 }
int nwords
Definition: bitmapset.h:51
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 427 of file bitmapset.c.

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

Referenced by adjust_child_relids(), adjust_relid_set(), adjust_rowcount_for_semijoins(), bms_is_subset_singleton(), bms_member_index(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clauselist_selectivity_simple(), ComputePartitionAttrs(), consider_groupingsets_paths(), create_foreignscan_plan(), create_lateral_join_info(), DefineIndex(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), do_analyze_rel(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecEvalGroupingFunc(), ExecInitModifyTable(), expand_indexqual_rowcompare(), ExplainSubPlans(), ExtractReplicaIdentity(), find_hash_columns(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), gen_partprune_steps_internal(), gen_prune_steps_from_opexps(), get_foreign_key_join_selectivity(), get_matching_hash_bounds(), get_tablefunc(), has_partition_attrs(), identify_current_nestloop_params(), inheritance_planner(), InitPlan(), is_foreign_param(), is_pseudo_constant_for_index(), is_subquery_var(), IsTidEqualAnyClause(), IsTidEqualClause(), join_clause_is_movable_to(), join_is_removable(), logicalrep_rel_open(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_invalid_subplans_as_finished(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), perform_pruning_base_step(), plpgsql_param_fetch(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pullup_replace_vars_callback(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), set_join_column_names(), set_rtable_names(), statext_is_compatible_clause(), statext_mcv_clauselist_selectivity(), substitute_phv_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), use_physical_tlist(), and view_cols_are_auto_updatable().

428 {
429  int wordnum,
430  bitnum;
431 
432  /* XXX better to just return false for x<0 ? */
433  if (x < 0)
434  elog(ERROR, "negative bitmapset member not allowed");
435  if (a == NULL)
436  return false;
437  wordnum = WORDNUM(x);
438  bitnum = BITNUM(x);
439  if (wordnum >= a->nwords)
440  return false;
441  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
442  return true;
443  return false;
444 }
int nwords
Definition: bitmapset.h:51
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define elog(elevel,...)
Definition: elog.h:228

◆ bms_is_subset()

bool bms_is_subset ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 315 of file bitmapset.c.

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

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), check_functional_grouping(), check_index_only(), check_outerjoin_delay(), clause_sides_match_join(), compute_semijoin_info(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_index_paths(), deconstruct_recurse(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_ec_member_for_tle(), find_em_expr_for_rel(), foreign_join_ok(), generate_implied_equalities_for_column(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_joinrel_parampathinfo(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), identify_current_nestloop_params(), initial_cost_mergejoin(), innerrel_is_unique(), is_simple_subquery(), join_clause_is_movable_into(), join_is_legal(), join_is_removable(), jointree_contains_lateral_outer_refs(), make_outerjoininfo(), populate_joinrel_with_paths(), prepare_sort_from_pathkeys(), process_subquery_nestloop_params(), remove_rel_from_query(), reparameterize_path(), replace_nestloop_params_mutator(), statext_mcv_clauselist_selectivity(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), try_partial_nestloop_path(), update_placeholder_eval_levels(), and use_physical_tlist().

316 {
317  int shortlen;
318  int longlen;
319  int i;
320 
321  /* Handle cases where either input is NULL */
322  if (a == NULL)
323  return true; /* empty set is a subset of anything */
324  if (b == NULL)
325  return bms_is_empty(a);
326  /* Check common words */
327  shortlen = Min(a->nwords, b->nwords);
328  for (i = 0; i < shortlen; i++)
329  {
330  if ((a->words[i] & ~b->words[i]) != 0)
331  return false;
332  }
333  /* Check extra words */
334  if (a->nwords > b->nwords)
335  {
336  longlen = a->nwords;
337  for (; i < longlen; i++)
338  {
339  if (a->words[i] != 0)
340  return false;
341  }
342  }
343  return true;
344 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
int i

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

Definition at line 949 of file bitmapset.c.

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

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

950 {
951  Bitmapset *result;
952  Bitmapset *other;
953  int otherlen;
954  int i;
955 
956  /* Handle cases where either input is NULL */
957  if (a == NULL)
958  return b;
959  if (b == NULL)
960  return a;
961  /* Identify shorter and longer input; use longer one as result */
962  if (a->nwords < b->nwords)
963  {
964  result = b;
965  other = a;
966  }
967  else
968  {
969  result = a;
970  other = b;
971  }
972  /* And union the shorter input into the result */
973  otherlen = other->nwords;
974  for (i = 0; i < otherlen; i++)
975  result->words[i] |= other->words[i];
976  if (other != result) /* pure paranoia */
977  pfree(other);
978  return result;
979 }
int nwords
Definition: bitmapset.h:51
void pfree(void *pointer)
Definition: mcxt.c:1056
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_make_singleton()

Bitmapset* bms_make_singleton ( int  x)

Definition at line 186 of file bitmapset.c.

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

Referenced by ATExecDropColumn(), ATPrepAlterColumnType(), bms_add_member(), build_base_rel_tlists(), build_simple_rel(), deconstruct_recurse(), deparseReturningList(), DiscreteKnapsack(), ExecInitAppend(), ExecInitMergeAppend(), expand_inherited_rtentry(), extract_lateral_references(), find_dependent_phvs(), find_nonnullable_rels_walker(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_range_bounds(), get_relids_in_jointree(), inheritance_planner(), load_enum_cache_data(), pg_column_is_updatable(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), and reduce_outer_joins_pass1().

187 {
188  Bitmapset *result;
189  int wordnum,
190  bitnum;
191 
192  if (x < 0)
193  elog(ERROR, "negative bitmapset member not allowed");
194  wordnum = WORDNUM(x);
195  bitnum = BITNUM(x);
196  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
197  result->nwords = wordnum + 1;
198  result->words[wordnum] = ((bitmapword) 1 << bitnum);
199  return result;
200 }
int nwords
Definition: bitmapset.h:51
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
void * palloc0(Size size)
Definition: mcxt.c:980
#define elog(elevel,...)
Definition: elog.h:228

◆ bms_member_index()

int bms_member_index ( Bitmapset a,
int  x 
)

Definition at line 453 of file bitmapset.c.

References BITNUM, bms_is_member(), bmw_popcount, i, WORDNUM, and Bitmapset::words.

Referenced by mcv_get_match_bitmap().

454 {
455  int i;
456  int bitnum;
457  int wordnum;
458  int result = 0;
459  bitmapword mask;
460 
461  /* return -1 if not a member of the bitmap */
462  if (!bms_is_member(x, a))
463  return -1;
464 
465  wordnum = WORDNUM(x);
466  bitnum = BITNUM(x);
467 
468  /* count bits in preceding words */
469  for (i = 0; i < wordnum; i++)
470  {
471  bitmapword w = a->words[i];
472 
473  /* No need to count the bits in a zero word */
474  if (w != 0)
475  result += bmw_popcount(w);
476  }
477 
478  /*
479  * Now add bits of the last word, but only those before the item. We can
480  * do that by applying a mask and then using popcount again. To get
481  * 0-based index, we want to count only preceding bits, not the item
482  * itself, so we subtract 1.
483  */
484  mask = ((bitmapword) 1 << bitnum) - 1;
485  result += bmw_popcount(a->words[wordnum] & mask);
486 
487  return result;
488 }
#define bmw_popcount(w)
Definition: bitmapset.c:60
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 672 of file bitmapset.c.

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

Referenced by add_child_join_rel_equivalences(), bms_is_subset_singleton(), clauselist_selectivity_simple(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependency_is_compatible_clause(), distribute_qual_to_rels(), distribute_restrictinfo_to_rels(), examine_variable(), find_join_input_rel(), find_nonnullable_rels_walker(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), get_foreign_key_join_selectivity(), remove_useless_groupby_columns(), set_rel_pathlist(), set_tablesample_rel_pathlist(), statext_is_compatible_clause(), statext_mcv_clauselist_selectivity(), and treat_as_join_clause().

673 {
674  BMS_Membership result = BMS_EMPTY_SET;
675  int nwords;
676  int wordnum;
677 
678  if (a == NULL)
679  return BMS_EMPTY_SET;
680  nwords = a->nwords;
681  for (wordnum = 0; wordnum < nwords; wordnum++)
682  {
683  bitmapword w = a->words[wordnum];
684 
685  if (w != 0)
686  {
687  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
688  return BMS_MULTIPLE;
689  result = BMS_SINGLETON;
690  }
691  }
692  return result;
693 }
int nwords
Definition: bitmapset.h:51
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:54
uint32 bitmapword
Definition: bitmapset.h:44
BMS_Membership
Definition: bitmapset.h:66
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_next_member()

int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1043 of file bitmapset.c.

References BITNUM, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, Bitmapset::nwords, WORDNUM, and Bitmapset::words.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_join_clause_to_rels(), add_paths_to_append_rel(), adjust_view_column_set(), alias_relid_set(), approximate_joinrel_size(), build_attnums_array(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), ComputePartitionAttrs(), create_lateral_join_info(), deparseLockingClause(), EstimateParamExecSpace(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecFindInitialMatchingSubPlans(), ExecInitAgg(), ExecInitAppend(), ExecInitMergeAppend(), ExecMergeAppend(), ExecScanReScan(), ExecSetParamPlanMulti(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_matching_subplans_recurse(), fixup_inherited_columns(), format_expr_params(), generate_base_implied_equalities(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_partitionwise_join_paths(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_loop_count(), get_matching_partitions(), has_relevant_eclass_joinclause(), have_relevant_eclass_joinclause(), inheritance_planner(), logicalrep_rel_open(), lookup_var_attr_stats(), match_eclasses_to_foreign_key_col(), offset_relid_set(), outBitmapset(), pg_ndistinct_out(), postgresBeginForeignScan(), postgresPlanDirectModify(), postgresPlanForeignModify(), remove_join_clause_from_rels(), remove_useless_results_recurse(), SerializeParamExecParams(), set_customscan_references(), set_foreignscan_references(), show_eval_params(), statext_is_compatible_clause(), and statext_ndistinct_serialize().

1044 {
1045  int nwords;
1046  int wordnum;
1047  bitmapword mask;
1048 
1049  if (a == NULL)
1050  return -2;
1051  nwords = a->nwords;
1052  prevbit++;
1053  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1054  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1055  {
1056  bitmapword w = a->words[wordnum];
1057 
1058  /* ignore bits before prevbit */
1059  w &= mask;
1060 
1061  if (w != 0)
1062  {
1063  int result;
1064 
1065  result = wordnum * BITS_PER_BITMAPWORD;
1066  result += bmw_rightmost_one_pos(w);
1067  return result;
1068  }
1069 
1070  /* in subsequent words, consider all bits */
1071  mask = (~(bitmapword) 0);
1072  }
1073  return -2;
1074 }
int nwords
Definition: bitmapset.h:51
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define BITNUM(x)
Definition: bitmapset.c:30
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:59
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_nonempty_difference()

bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 545 of file bitmapset.c.

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

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

546 {
547  int shortlen;
548  int i;
549 
550  /* Handle cases where either input is NULL */
551  if (a == NULL)
552  return false;
553  if (b == NULL)
554  return !bms_is_empty(a);
555  /* Check words in common */
556  shortlen = Min(a->nwords, b->nwords);
557  for (i = 0; i < shortlen; i++)
558  {
559  if ((a->words[i] & ~b->words[i]) != 0)
560  return true;
561  }
562  /* Check extra words in a */
563  for (; i < a->nwords; i++)
564  {
565  if (a->words[i] != 0)
566  return true;
567  }
568  return false;
569 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
int i

◆ bms_num_members()

int bms_num_members ( const Bitmapset a)

Definition at line 646 of file bitmapset.c.

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

Referenced by adjust_appendrel_attrs_multilevel(), build_attnums_array(), build_join_rel(), BuildRelationExtStatistics(), choose_best_statistics(), clauselist_selectivity_simple(), ComputeExtStatisticsRows(), dependencies_clauselist_selectivity(), estimate_multivariate_ndistinct(), ExecFindInitialMatchingSubPlans(), ExecInitAppend(), ExecInitMergeAppend(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_hash_columns(), find_strongest_dependency(), gen_partprune_steps_internal(), get_matching_hash_bounds(), lookup_var_attr_stats(), make_partition_pruneinfo(), mark_invalid_subplans_as_finished(), NumRelids(), SerializeParamExecParams(), statext_ndistinct_build(), and statext_ndistinct_serialize().

647 {
648  int result = 0;
649  int nwords;
650  int wordnum;
651 
652  if (a == NULL)
653  return 0;
654  nwords = a->nwords;
655  for (wordnum = 0; wordnum < nwords; wordnum++)
656  {
657  bitmapword w = a->words[wordnum];
658 
659  /* No need to count the bits in a zero word */
660  if (w != 0)
661  result += bmw_popcount(w);
662  }
663  return result;
664 }
#define bmw_popcount(w)
Definition: bitmapset.c:60
int nwords
Definition: bitmapset.h:51
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 494 of file bitmapset.c.

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

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_paths_to_joinrel(), adjust_child_relids_multilevel(), allow_star_schema_join(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), check_outerjoin_delay(), choose_bitmap_and(), compute_semijoin_info(), create_nestloop_path(), distribute_qual_to_rels(), eclass_useful_for_merging(), 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_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_partition_attrs(), have_dangerous_phv(), have_join_order_restriction(), 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_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo_internal(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), reparameterize_path_by_child(), replace_nestloop_params_mutator(), select_outer_pathkeys_for_merge(), transformUpdateTargetList(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), try_partitionwise_join(), and update_placeholder_eval_levels().

495 {
496  int shortlen;
497  int i;
498 
499  /* Handle cases where either input is NULL */
500  if (a == NULL || b == NULL)
501  return false;
502  /* Check words in common */
503  shortlen = Min(a->nwords, b->nwords);
504  for (i = 0; i < shortlen; i++)
505  {
506  if ((a->words[i] & b->words[i]) != 0)
507  return true;
508  }
509  return false;
510 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i

◆ bms_overlap_list()

bool bms_overlap_list ( const Bitmapset a,
const List b 
)

Definition at line 516 of file bitmapset.c.

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

Referenced by preprocess_grouping_sets().

517 {
518  ListCell *lc;
519  int wordnum,
520  bitnum;
521 
522  if (a == NULL || b == NIL)
523  return false;
524 
525  foreach(lc, b)
526  {
527  int x = lfirst_int(lc);
528 
529  if (x < 0)
530  elog(ERROR, "negative bitmapset member not allowed");
531  wordnum = WORDNUM(x);
532  bitnum = BITNUM(x);
533  if (wordnum < a->nwords)
534  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
535  return true;
536  }
537 
538  return false;
539 }
#define NIL
Definition: pg_list.h:65
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:191
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define elog(elevel,...)
Definition: elog.h:228

◆ bms_prev_member()

int bms_prev_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1102 of file bitmapset.c.

References BITNUM, BITS_PER_BITMAPWORD, bmw_leftmost_one_pos, Bitmapset::nwords, WORDNUM, and Bitmapset::words.

Referenced by choose_next_subplan_locally().

1103 {
1104  int wordnum;
1105  int ushiftbits;
1106  bitmapword mask;
1107 
1108  /*
1109  * If set is NULL or if there are no more bits to the right then we've
1110  * nothing to do.
1111  */
1112  if (a == NULL || prevbit == 0)
1113  return -2;
1114 
1115  /* transform -1 to the highest possible bit we could have set */
1116  if (prevbit == -1)
1117  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1118  else
1119  prevbit--;
1120 
1121  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1122  mask = (~(bitmapword) 0) >> ushiftbits;
1123  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1124  {
1125  bitmapword w = a->words[wordnum];
1126 
1127  /* mask out bits left of prevbit */
1128  w &= mask;
1129 
1130  if (w != 0)
1131  {
1132  int result;
1133 
1134  result = wordnum * BITS_PER_BITMAPWORD;
1135  result += bmw_leftmost_one_pos(w);
1136  return result;
1137  }
1138 
1139  /* in subsequent words, consider all bits */
1140  mask = (~(bitmapword) 0);
1141  }
1142  return -2;
1143 }
int nwords
Definition: bitmapset.h:51
#define WORDNUM(x)
Definition: bitmapset.c:29
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.c:58

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

Definition at line 577 of file bitmapset.c.

References BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, elog, ERROR, HAS_MULTIPLE_ONES, Bitmapset::nwords, and Bitmapset::words.

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

578 {
579  int result = -1;
580  int nwords;
581  int wordnum;
582 
583  if (a == NULL)
584  elog(ERROR, "bitmapset is empty");
585  nwords = a->nwords;
586  for (wordnum = 0; wordnum < nwords; wordnum++)
587  {
588  bitmapword w = a->words[wordnum];
589 
590  if (w != 0)
591  {
592  if (result >= 0 || HAS_MULTIPLE_ONES(w))
593  elog(ERROR, "bitmapset has multiple members");
594  result = wordnum * BITS_PER_BITMAPWORD;
595  result += bmw_rightmost_one_pos(w);
596  }
597  }
598  if (result < 0)
599  elog(ERROR, "bitmapset is empty");
600  return result;
601 }
int nwords
Definition: bitmapset.h:51
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:54
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:59
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
#define elog(elevel,...)
Definition: elog.h:228

◆ bms_subset_compare()

BMS_Comparison bms_subset_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 352 of file bitmapset.c.

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

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

353 {
354  BMS_Comparison result;
355  int shortlen;
356  int longlen;
357  int i;
358 
359  /* Handle cases where either input is NULL */
360  if (a == NULL)
361  {
362  if (b == NULL)
363  return BMS_EQUAL;
364  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
365  }
366  if (b == NULL)
367  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
368  /* Check common words */
369  result = BMS_EQUAL; /* status so far */
370  shortlen = Min(a->nwords, b->nwords);
371  for (i = 0; i < shortlen; i++)
372  {
373  bitmapword aword = a->words[i];
374  bitmapword bword = b->words[i];
375 
376  if ((aword & ~bword) != 0)
377  {
378  /* a is not a subset of b */
379  if (result == BMS_SUBSET1)
380  return BMS_DIFFERENT;
381  result = BMS_SUBSET2;
382  }
383  if ((bword & ~aword) != 0)
384  {
385  /* b is not a subset of a */
386  if (result == BMS_SUBSET2)
387  return BMS_DIFFERENT;
388  result = BMS_SUBSET1;
389  }
390  }
391  /* Check extra words */
392  if (a->nwords > b->nwords)
393  {
394  longlen = a->nwords;
395  for (; i < longlen; i++)
396  {
397  if (a->words[i] != 0)
398  {
399  /* a is not a subset of b */
400  if (result == BMS_SUBSET1)
401  return BMS_DIFFERENT;
402  result = BMS_SUBSET2;
403  }
404  }
405  }
406  else if (a->nwords < b->nwords)
407  {
408  longlen = b->nwords;
409  for (; i < longlen; i++)
410  {
411  if (b->words[i] != 0)
412  {
413  /* b is not a subset of a */
414  if (result == BMS_SUBSET2)
415  return BMS_DIFFERENT;
416  result = BMS_SUBSET1;
417  }
418  }
419  }
420  return result;
421 }
int nwords
Definition: bitmapset.h:51
#define Min(x, y)
Definition: c.h:905
uint32 bitmapword
Definition: bitmapset.h:44
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
int i
BMS_Comparison
Definition: bitmapset.h:57

◆ bms_union()

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

Definition at line 225 of file bitmapset.c.

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

Referenced by build_child_join_rel(), build_join_rel(), 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_path(), create_nestloop_plan(), deconstruct_recurse(), ExecConstraints(), ExecPartitionCheckEmitError(), ExecWithCheckOptions(), finalize_plan(), foreign_join_ok(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), 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(), has_legal_joinclause(), join_is_removable(), make_join_rel(), make_outerjoininfo(), make_restrictinfo_internal(), min_join_parameterization(), postgresGetForeignPaths(), postgresPlanForeignModify(), pull_up_sublinks_jointree_recurse(), reduce_unique_semijoins(), remove_useless_joins(), substitute_phv_relids_walker(), and try_partitionwise_join().

226 {
227  Bitmapset *result;
228  const Bitmapset *other;
229  int otherlen;
230  int i;
231 
232  /* Handle cases where either input is NULL */
233  if (a == NULL)
234  return bms_copy(b);
235  if (b == NULL)
236  return bms_copy(a);
237  /* Identify shorter and longer input; copy the longer one */
238  if (a->nwords <= b->nwords)
239  {
240  result = bms_copy(b);
241  other = a;
242  }
243  else
244  {
245  result = bms_copy(a);
246  other = b;
247  }
248  /* And union the shorter input into the result */
249  otherlen = other->nwords;
250  for (i = 0; i < otherlen; i++)
251  result->words[i] |= other->words[i];
252  return result;
253 }
int nwords
Definition: bitmapset.h:51
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int i