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)
 
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)
 
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 32 of file bitmapset.c.

◆ BITNUM

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

Definition at line 30 of file bitmapset.c.

◆ bmw_leftmost_one_pos

#define bmw_leftmost_one_pos (   w)    pg_leftmost_one_pos32(w)

Definition at line 58 of file bitmapset.c.

◆ bmw_popcount

#define bmw_popcount (   w)    pg_popcount32(w)

Definition at line 60 of file bitmapset.c.

◆ bmw_rightmost_one_pos

#define bmw_rightmost_one_pos (   w)    pg_rightmost_one_pos32(w)

Definition at line 59 of file bitmapset.c.

◆ HAS_MULTIPLE_ONES

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

Definition at line 54 of file bitmapset.c.

◆ RIGHTMOST_ONE

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

Definition at line 52 of file bitmapset.c.

◆ WORDNUM

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

Definition at line 29 of file bitmapset.c.

Function Documentation

◆ bitmap_hash()

uint32 bitmap_hash ( const void *  key,
Size  keysize 
)

Definition at line 1181 of file bitmapset.c.

1182 {
1183  Assert(keysize == sizeof(Bitmapset *));
1184  return bms_hash_value(*((const Bitmapset *const *) key));
1185 }
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1158
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 1191 of file bitmapset.c.

1192 {
1193  Assert(keysize == sizeof(Bitmapset *));
1194  return !bms_equal(*((const Bitmapset *const *) key1),
1195  *((const Bitmapset *const *) key2));
1196 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94

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 739 of file bitmapset.c.

740 {
741  int wordnum,
742  bitnum;
743 
744  if (x < 0)
745  elog(ERROR, "negative bitmapset member not allowed");
746  if (a == NULL)
747  return bms_make_singleton(x);
748  wordnum = WORDNUM(x);
749  bitnum = BITNUM(x);
750 
751  /* enlarge the set if necessary */
752  if (wordnum >= a->nwords)
753  {
754  int oldnwords = a->nwords;
755  int i;
756 
757  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
758  a->nwords = wordnum + 1;
759  /* zero out the enlarged portion */
760  for (i = oldnwords; i < a->nwords; i++)
761  a->words[i] = 0;
762  }
763 
764  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
765  return a;
766 }
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
#define WORDNUM(x)
Definition: bitmapset.c:29
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:186
#define BITNUM(x)
Definition: bitmapset.c:30
uint32 bitmapword
Definition: bitmapset.h:46
#define ERROR
Definition: elog.h:35
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:1321

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

Referenced by _readBitmapset(), add_child_rel_equivalences(), add_row_identity_var(), adjust_child_relids(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), AlterPublicationTables(), apply_handle_update(), 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(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), do_analyze_rel(), DoCopy(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecInitAgg(), ExecInitAppend(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanGather(), ExecReScanGatherMerge(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), ExecSetParamPlan(), execute_attr_map_cols(), expand_single_inheritance_child(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), extractRemainingColumns(), fetch_remote_table_info(), fetch_statentries_for_relation(), fill_extraUpdatedCols(), 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_eclass_for_sort_expr(), get_matching_partitions(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), load_enum_cache_data(), logicalrep_read_attrs(), make_datum_param(), make_modifytable(), make_one_rel(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_pathkeys_for_groupagg(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), markRTEForSelectPriv(), mbms_add_member(), mbms_overlap_sets(), nodeRead(), offset_relid_set(), PartitionPruneFixSubPlanMap(), preprocess_grouping_sets(), pub_collist_to_bitmapset(), publication_translate_columns(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_useless_groupby_columns(), remove_useless_results_recurse(), rewriteTargetListIU(), rewriteTargetView(), RI_Initial_Check(), set_join_column_names(), set_param_references(), SS_identify_outer_params(), stat_covers_expressions(), statext_is_compatible_clause(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), transformGroupClause(), transformGroupClauseList(), transformMergeStmt(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), try_partitionwise_join(), use_physical_tlist(), and view_cols_are_auto_updatable().

◆ bms_add_members()

Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 796 of file bitmapset.c.

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

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

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_eq_member(), add_part_relids(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), build_index_paths(), check_outerjoin_delay(), choose_best_statistics(), choose_bitmap_and(), create_bitmap_and_path(), create_bitmap_or_path(), create_lateral_join_info(), CreatePartitionPruneState(), deconstruct_recurse(), DiscreteKnapsack(), ExecFindMatchingSubPlans(), ExecInitAgg(), expand_partitioned_rtentry(), ExplainPreScanNode(), finalize_plan(), find_nonnullable_rels_walker(), foreign_join_ok(), get_eclass_indexes_for_relids(), heap_update(), join_is_legal(), make_outerjoininfo(), mbms_add_members(), perform_pruning_combine_step(), pull_varnos_walker(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), transformOnConflictArbiter(), try_partitionwise_join(), and update_placeholder_eval_levels().

◆ bms_add_range()

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

Definition at line 837 of file bitmapset.c.

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

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

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

◆ bms_compare()

int bms_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 147 of file bitmapset.c.

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 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
#define Min(x, y)
Definition: c.h:937

References a, b, bms_is_empty(), i, and Min.

Referenced by append_startup_cost_compare(), and append_total_cost_compare().

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

Definition at line 74 of file bitmapset.c.

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 }
void * palloc(Size size)
Definition: mcxt.c:1199

References a, BITMAPSET_SIZE, and palloc().

Referenced by _copyBitmapset(), adjust_child_relids(), adjust_relid_set(), bms_add_members(), bms_difference(), bms_intersect(), bms_union(), build_child_join_rel(), build_index_paths(), build_join_rel(), calc_nestloop_required_outer(), check_equivalence_delay(), check_outerjoin_delay(), choose_bitmap_and(), classify_matching_subplans(), create_lateral_join_info(), CreatePartitionPruneState(), DiscreteKnapsack(), distribute_qual_to_rels(), ExecFindMatchingSubPlans(), expand_single_inheritance_child(), 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_relation_statistics_worker(), innerrel_is_unique(), join_is_legal(), load_enum_cache_data(), logicalrep_partition_open(), logicalrep_relmap_update(), make_outerjoininfo(), partition_bounds_copy(), perform_pruning_combine_step(), process_implied_equality(), reconsider_full_join_clause(), reconsider_outer_join_clause(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_rel_from_query(), and reparameterize_path_by_child().

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 776 of file bitmapset.c.

777 {
778  int wordnum,
779  bitnum;
780 
781  if (x < 0)
782  elog(ERROR, "negative bitmapset member not allowed");
783  if (a == NULL)
784  return NULL;
785  wordnum = WORDNUM(x);
786  bitnum = BITNUM(x);
787  if (wordnum < a->nwords)
788  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
789  return a;
790 }

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

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

◆ bms_del_members()

Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 932 of file bitmapset.c.

933 {
934  int shortlen;
935  int i;
936 
937  /* Handle cases where either input is NULL */
938  if (a == NULL)
939  return NULL;
940  if (b == NULL)
941  return a;
942  /* Remove b's bits from a; we need never copy */
943  shortlen = Min(a->nwords, b->nwords);
944  for (i = 0; i < shortlen; i++)
945  a->words[i] &= ~b->words[i];
946  return a;
947 }

References a, b, i, and Min.

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

◆ bms_difference()

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

Definition at line 292 of file bitmapset.c.

293 {
294  Bitmapset *result;
295  int shortlen;
296  int i;
297 
298  /* Handle cases where either input is NULL */
299  if (a == NULL)
300  return NULL;
301  if (b == NULL)
302  return bms_copy(a);
303  /* Copy the left input */
304  result = bms_copy(a);
305  /* And remove b's bits from result */
306  shortlen = Min(a->nwords, b->nwords);
307  for (i = 0; i < shortlen; i++)
308  result->words[i] &= ~b->words[i];
309  return result;
310 }

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

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

◆ bms_equal()

bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 94 of file bitmapset.c.

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 }

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

Referenced by _equalBitmapset(), add_path_precheck(), add_paths_to_append_rel(), AlterPublicationTables(), bitmap_match(), choose_bitmap_and(), create_append_path(), create_merge_append_path(), create_unique_path(), ExecInitPartitionPruning(), extract_rollup_sets(), fetch_upper_rel(), find_dependent_phvs_walker(), find_join_rel(), find_param_path_info(), generate_implied_equalities_for_column(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), has_join_restriction(), infer_arbiter_indexes(), is_safe_restriction_clause_for(), join_is_legal(), make_one_rel(), make_partitionedrel_pruneinfo(), match_pathkeys_to_index(), merge_clump(), pgoutput_column_list_init(), populate_joinrel_with_paths(), pull_varnos_walker(), set_rel_pathlist(), standard_join_search(), and try_partitionwise_join().

◆ bms_first_member()

int bms_first_member ( Bitmapset a)

Definition at line 1000 of file bitmapset.c.

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

References a, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, and RIGHTMOST_ONE.

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

◆ bms_free()

◆ bms_get_singleton_member()

bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 618 of file bitmapset.c.

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

References a, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, and HAS_MULTIPLE_ONES.

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

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset a)

Definition at line 1158 of file bitmapset.c.

1159 {
1160  int lastword;
1161 
1162  if (a == NULL)
1163  return 0; /* All empty sets hash to 0 */
1164  for (lastword = a->nwords; --lastword >= 0;)
1165  {
1166  if (a->words[lastword] != 0)
1167  break;
1168  }
1169  if (lastword < 0)
1170  return 0; /* All empty sets hash to 0 */
1171  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1172  (lastword + 1) * sizeof(bitmapword)));
1173 }
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:570

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

Referenced by bitmap_hash().

◆ bms_int_members()

Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 906 of file bitmapset.c.

907 {
908  int shortlen;
909  int i;
910 
911  /* Handle cases where either input is NULL */
912  if (a == NULL)
913  return NULL;
914  if (b == NULL)
915  {
916  pfree(a);
917  return NULL;
918  }
919  /* Intersect b into a; we need never copy */
920  shortlen = Min(a->nwords, b->nwords);
921  for (i = 0; i < shortlen; i++)
922  a->words[i] &= b->words[i];
923  for (; i < a->nwords; i++)
924  a->words[i] = 0;
925  return a;
926 }

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

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

◆ bms_intersect()

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

Definition at line 260 of file bitmapset.c.

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

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

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

◆ bms_is_empty()

bool bms_is_empty ( const Bitmapset a)

Definition at line 704 of file bitmapset.c.

705 {
706  int nwords;
707  int wordnum;
708 
709  if (a == NULL)
710  return true;
711  nwords = a->nwords;
712  for (wordnum = 0; wordnum < nwords; wordnum++)
713  {
714  bitmapword w = a->words[wordnum];
715 
716  if (w != 0)
717  return false;
718  }
719  return true;
720 }

References a.

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(), classify_matching_subplans(), 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(), ExecAppend(), ExecAppendAsyncBegin(), ExecAppendAsyncRequest(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecInitParallelPlan(), ExecParallelReinitialize(), ExecReScanSetParamPlan(), ExtractReplicaIdentity(), filter_event_trigger(), finalize_plan(), find_em_for_rel(), find_nonnullable_rels_walker(), find_placeholder_info(), find_single_rel_for_clauses(), findDefaultOnlyColumns(), 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_steps_using_prefix_recurse(), get_useful_ecs_for_relation(), GetParentedForeignKeyRefs(), hash_inner_and_outer(), is_pseudo_constant_clause_relids(), logicalrep_report_missing_attrs(), make_outerjoininfo(), make_partitionedrel_pruneinfo(), make_restrictinfo_internal(), match_clause_to_partition_key(), match_unsorted_outer(), min_join_parameterization(), PartitionPruneFixSubPlanMap(), pg_get_expr_worker(), postgresForeignAsyncConfigureWait(), postgresGetForeignJoinPaths(), postgresGetForeignPaths(), preprocess_grouping_sets(), process_equivalence(), process_implied_equality(), 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().

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 428 of file bitmapset.c.

429 {
430  int wordnum,
431  bitnum;
432 
433  /* XXX better to just return false for x<0 ? */
434  if (x < 0)
435  elog(ERROR, "negative bitmapset member not allowed");
436  if (a == NULL)
437  return false;
438  wordnum = WORDNUM(x);
439  bitnum = BITNUM(x);
440  if (wordnum >= a->nwords)
441  return false;
442  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
443  return true;
444  return false;
445 }

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

Referenced by add_row_identity_var(), adjust_appendrel_attrs_mutator(), adjust_child_relids(), adjust_relid_set(), adjust_rowcount_for_semijoins(), bms_is_subset_singleton(), bms_member_index(), check_index_predicates(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clauselist_selectivity_ext(), clauselist_selectivity_or(), column_in_column_list(), ComputePartitionAttrs(), consider_groupingsets_paths(), contain_invalid_rfcolumn_walker(), cost_incremental_sort(), 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(), ExecBuildUpdateProjection(), ExecComputeStoredGenerated(), ExecEvalGroupingFunc(), ExecInitModifyTable(), execute_attr_map_cols(), expand_indexqual_rowcompare(), expand_single_inheritance_child(), ExplainSubPlans(), extractRemainingColumns(), ExtractReplicaIdentity(), fetch_remote_table_info(), filter_event_trigger(), find_hash_columns(), find_modifytable_subplan(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), gen_partprune_steps_internal(), gen_prune_steps_from_opexps(), get_foreign_key_join_selectivity(), get_matching_hash_bounds(), get_tablefunc(), get_translated_update_targetlist(), get_variable(), has_partition_attrs(), hashagg_spill_tuple(), HeapDetermineColumnsInfo(), identify_current_nestloop_params(), index_expression_changed_walker(), index_unchanged_by_update(), InitPlan(), is_foreign_param(), is_pseudo_constant_for_index(), is_subquery_var(), IsBinaryTidClause(), isPlainForeignVar(), IsTidEqualAnyClause(), join_clause_is_movable_to(), join_is_removable(), lo_manage(), logicalrep_rel_mark_updatable(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_invalid_subplans_as_finished(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), mbms_is_member(), partitions_are_ordered(), perform_pruning_base_step(), plpgsql_param_fetch(), postgresExplainForeignScan(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pub_collist_contains_invalid_column(), publication_translate_columns(), pullup_replace_vars_callback(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), rewriteTargetListIU(), rewriteValuesRTE(), send_relation_and_attrs(), set_join_column_names(), set_rtable_names(), statext_mcv_clauselist_selectivity(), substitute_phv_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), tsvector_update_trigger(), use_physical_tlist(), and view_cols_are_auto_updatable().

◆ bms_is_subset()

bool bms_is_subset ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 316 of file bitmapset.c.

317 {
318  int shortlen;
319  int longlen;
320  int i;
321 
322  /* Handle cases where either input is NULL */
323  if (a == NULL)
324  return true; /* empty set is a subset of anything */
325  if (b == NULL)
326  return bms_is_empty(a);
327  /* Check common words */
328  shortlen = Min(a->nwords, b->nwords);
329  for (i = 0; i < shortlen; i++)
330  {
331  if ((a->words[i] & ~b->words[i]) != 0)
332  return false;
333  }
334  /* Check extra words */
335  if (a->nwords > b->nwords)
336  {
337  longlen = a->nwords;
338  for (; i < longlen; i++)
339  {
340  if (a->words[i] != 0)
341  return false;
342  }
343  }
344  return true;
345 }

References a, b, bms_is_empty(), i, and Min.

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(), choose_best_statistics(), 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_computable_ec_member(), find_ec_member_matching_expr(), find_em_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(), pg_get_expr_worker(), populate_joinrel_with_paths(), process_implied_equality(), process_subquery_nestloop_params(), remove_rel_from_query(), reparameterize_path(), replace_nestloop_params_mutator(), statext_mcv_clauselist_selectivity(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), try_partial_nestloop_path(), update_placeholder_eval_levels(), and use_physical_tlist().

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

Definition at line 953 of file bitmapset.c.

954 {
955  Bitmapset *result;
956  Bitmapset *other;
957  int otherlen;
958  int i;
959 
960  /* Handle cases where either input is NULL */
961  if (a == NULL)
962  return b;
963  if (b == NULL)
964  return a;
965  /* Identify shorter and longer input; use longer one as result */
966  if (a->nwords < b->nwords)
967  {
968  result = b;
969  other = a;
970  }
971  else
972  {
973  result = a;
974  other = b;
975  }
976  /* And union the shorter input into the result */
977  otherlen = other->nwords;
978  for (i = 0; i < otherlen; i++)
979  result->words[i] |= other->words[i];
980  if (other != result) /* pure paranoia */
981  pfree(other);
982  return result;
983 }

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

Referenced by add_paths_to_joinrel(), alias_relid_set(), 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 454 of file bitmapset.c.

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

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

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

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 675 of file bitmapset.c.

676 {
677  BMS_Membership result = BMS_EMPTY_SET;
678  int nwords;
679  int wordnum;
680 
681  if (a == NULL)
682  return BMS_EMPTY_SET;
683  nwords = a->nwords;
684  for (wordnum = 0; wordnum < nwords; wordnum++)
685  {
686  bitmapword w = a->words[wordnum];
687 
688  if (w != 0)
689  {
690  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
691  return BMS_MULTIPLE;
692  result = BMS_SINGLETON;
693  }
694  }
695  return result;
696 }
BMS_Membership
Definition: bitmapset.h:72
@ BMS_SINGLETON
Definition: bitmapset.h:74
@ BMS_EMPTY_SET
Definition: bitmapset.h:73
@ BMS_MULTIPLE
Definition: bitmapset.h:75

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

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

◆ bms_next_member()

int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1047 of file bitmapset.c.

1048 {
1049  int nwords;
1050  int wordnum;
1051  bitmapword mask;
1052 
1053  if (a == NULL)
1054  return -2;
1055  nwords = a->nwords;
1056  prevbit++;
1057  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1058  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1059  {
1060  bitmapword w = a->words[wordnum];
1061 
1062  /* ignore bits before prevbit */
1063  w &= mask;
1064 
1065  if (w != 0)
1066  {
1067  int result;
1068 
1069  result = wordnum * BITS_PER_BITMAPWORD;
1070  result += bmw_rightmost_one_pos(w);
1071  return result;
1072  }
1073 
1074  /* in subsequent words, consider all bits */
1075  mask = (~(bitmapword) 0);
1076  }
1077  return -2;
1078 }

References a, BITNUM, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, and WORDNUM.

Referenced by add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_join_clause_to_rels(), add_part_relids(), adjust_view_column_set(), alias_relid_set(), apply_scanjoin_target_to_paths(), approximate_joinrel_size(), build_attnums_array(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), clauselist_apply_dependencies(), ComputePartitionAttrs(), create_lateral_join_info(), create_partitionwise_grouping_paths(), CreateStatistics(), deparseLockingClause(), dependencies_clauselist_selectivity(), EstimateParamExecSpace(), ExecAppendAsyncBegin(), ExecAppendAsyncEventWait(), ExecAppendAsyncRequest(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecInitAgg(), ExecInitAppend(), ExecInitMergeAppend(), ExecMergeAppend(), ExecReScanAppend(), ExecScanReScan(), ExecSetParamPlanMulti(), expand_partitioned_rtentry(), find_appinfos_by_relids(), find_dependent_phvs_in_jointree(), 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(), logicalrep_rel_mark_updatable(), lookup_var_attr_stats(), make_build_data(), make_partitionedrel_pruneinfo(), make_pathkeys_for_groupagg(), match_eclasses_to_foreign_key_col(), offset_relid_set(), outBitmapset(), PartitionPruneFixSubPlanMap(), postgresBeginForeignScan(), postgresExplainForeignScan(), postgresPlanForeignModify(), pub_collist_contains_invalid_column(), remove_join_clause_from_rels(), remove_useless_results_recurse(), SerializeParamExecParams(), show_eval_params(), and statext_is_compatible_clause().

◆ bms_nonempty_difference()

bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 548 of file bitmapset.c.

549 {
550  int shortlen;
551  int i;
552 
553  /* Handle cases where either input is NULL */
554  if (a == NULL)
555  return false;
556  if (b == NULL)
557  return !bms_is_empty(a);
558  /* Check words in common */
559  shortlen = Min(a->nwords, b->nwords);
560  for (i = 0; i < shortlen; i++)
561  {
562  if ((a->words[i] & ~b->words[i]) != 0)
563  return true;
564  }
565  /* Check extra words in a */
566  for (; i < a->nwords; i++)
567  {
568  if (a->words[i] != 0)
569  return true;
570  }
571  return false;
572 }

References a, b, bms_is_empty(), i, and Min.

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

◆ bms_num_members()

int bms_num_members ( const Bitmapset a)

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 495 of file bitmapset.c.

496 {
497  int shortlen;
498  int i;
499 
500  /* Handle cases where either input is NULL */
501  if (a == NULL || b == NULL)
502  return false;
503  /* Check words in common */
504  shortlen = Min(a->nwords, b->nwords);
505  for (i = 0; i < shortlen; i++)
506  {
507  if ((a->words[i] & b->words[i]) != 0)
508  return true;
509  }
510  return false;
511 }

References a, b, i, and Min.

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(), classify_matching_subplans(), compute_semijoin_info(), create_nestloop_path(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), fill_extraUpdatedCols(), 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(), 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(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), try_partitionwise_join(), and update_placeholder_eval_levels().

◆ bms_overlap_list()

bool bms_overlap_list ( const Bitmapset a,
const List b 
)

Definition at line 517 of file bitmapset.c.

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

References a, 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 1106 of file bitmapset.c.

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

References a, BITNUM, BITS_PER_BITMAPWORD, bmw_leftmost_one_pos, and WORDNUM.

Referenced by choose_next_subplan_locally().

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

Definition at line 580 of file bitmapset.c.

581 {
582  int result = -1;
583  int nwords;
584  int wordnum;
585 
586  if (a == NULL)
587  elog(ERROR, "bitmapset is empty");
588  nwords = a->nwords;
589  for (wordnum = 0; wordnum < nwords; wordnum++)
590  {
591  bitmapword w = a->words[wordnum];
592 
593  if (w != 0)
594  {
595  if (result >= 0 || HAS_MULTIPLE_ONES(w))
596  elog(ERROR, "bitmapset has multiple members");
597  result = wordnum * BITS_PER_BITMAPWORD;
598  result += bmw_rightmost_one_pos(w);
599  }
600  }
601  if (result < 0)
602  elog(ERROR, "bitmapset is empty");
603  return result;
604 }

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

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

◆ bms_subset_compare()

BMS_Comparison bms_subset_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 353 of file bitmapset.c.

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

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

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

◆ bms_union()

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

Definition at line 226 of file bitmapset.c.

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

References a, b, 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(), ExecGetAllUpdatedCols(), ExecPartitionCheckEmitError(), ExecWithCheckOptions(), finalize_plan(), find_hash_columns(), 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(), index_unchanged_by_update(), 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(), resolve_special_varno(), substitute_phv_relids_walker(), and try_partitionwise_join().