PostgreSQL Source Code  git master
bitmapset.c File Reference
#include "postgres.h"
#include "access/hash.h"
#include "nodes/pg_list.h"
Include dependency graph for bitmapset.c:

Go to the source code of this file.

Macros

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

Functions

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)
 
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)
 

Variables

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

Macro Definition Documentation

◆ BITMAPSET_SIZE

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

Definition at line 30 of file bitmapset.c.

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

◆ BITNUM

◆ HAS_MULTIPLE_ONES

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

Definition at line 52 of file bitmapset.c.

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

◆ RIGHTMOST_ONE

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

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

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

Referenced by _readBitmapset(), 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_subplans_for_params_recurse(), find_unaggregated_cols_walker(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), gen_partprune_steps_internal(), 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_partition_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), markRTEForSelectPriv(), offset_relid_set(), preprocess_grouping_sets(), prune_append_rel_partitions(), pull_partkey_params(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), RelationGetIndexAttrBitmap(), RememberFsyncRequest(), remove_useless_groupby_columns(), rewriteTargetView(), RI_Initial_Check(), set_customscan_references(), set_foreignscan_references(), set_join_column_names(), set_param_references(), SS_identify_outer_params(), statext_ndistinct_build(), statext_ndistinct_deserialize(), transformGroupClause(), transformGroupClauseList(), transformInsertStmt(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), use_physical_tlist(), and view_cols_are_auto_updatable().

765 {
766  int wordnum,
767  bitnum;
768 
769  if (x < 0)
770  elog(ERROR, "negative bitmapset member not allowed");
771  if (a == NULL)
772  return bms_make_singleton(x);
773  wordnum = WORDNUM(x);
774  bitnum = BITNUM(x);
775 
776  /* enlarge the set if necessary */
777  if (wordnum >= a->nwords)
778  {
779  int oldnwords = a->nwords;
780  int i;
781 
782  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
783  a->nwords = wordnum + 1;
784  /* zero out the enlarged portion */
785  for (i = oldnwords; i < a->nwords; i++)
786  a->words[i] = 0;
787  }
788 
789  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
790  return a;
791 }
int nwords
Definition: bitmapset.h:39
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:30
#define ERROR
Definition: elog.h:43
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:245
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1044
int i
#define elog
Definition: elog.h:219

◆ bms_add_members()

Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 821 of file bitmapset.c.

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

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

822 {
823  Bitmapset *result;
824  const Bitmapset *other;
825  int otherlen;
826  int i;
827 
828  /* Handle cases where either input is NULL */
829  if (a == NULL)
830  return bms_copy(b);
831  if (b == NULL)
832  return a;
833  /* Identify shorter and longer input; copy the longer one if needed */
834  if (a->nwords < b->nwords)
835  {
836  result = bms_copy(b);
837  other = a;
838  }
839  else
840  {
841  result = a;
842  other = b;
843  }
844  /* And union the shorter input into the result */
845  otherlen = other->nwords;
846  for (i = 0; i < otherlen; i++)
847  result->words[i] |= other->words[i];
848  if (result != a)
849  pfree(a);
850  return result;
851 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:133
void pfree(void *pointer)
Definition: mcxt.c:1031
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_add_range()

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

Definition at line 862 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(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_partitions(), get_matching_range_bounds(), and perform_pruning_combine_step().

863 {
864  int lwordnum,
865  lbitnum,
866  uwordnum,
867  ushiftbits,
868  wordnum;
869 
870  if (lower < 0 || upper < 0)
871  elog(ERROR, "negative bitmapset member not allowed");
872  if (lower > upper)
873  elog(ERROR, "lower range must not be above upper range");
874  uwordnum = WORDNUM(upper);
875 
876  if (a == NULL)
877  {
878  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
879  a->nwords = uwordnum + 1;
880  }
881 
882  /* ensure we have enough words to store the upper bit */
883  else if (uwordnum >= a->nwords)
884  {
885  int oldnwords = a->nwords;
886  int i;
887 
888  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
889  a->nwords = uwordnum + 1;
890  /* zero out the enlarged portion */
891  for (i = oldnwords; i < a->nwords; i++)
892  a->words[i] = 0;
893  }
894 
895  wordnum = lwordnum = WORDNUM(lower);
896 
897  lbitnum = BITNUM(lower);
898  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
899 
900  /*
901  * Special case when lwordnum is the same as uwordnum we must perform the
902  * upper and lower masking on the word.
903  */
904  if (lwordnum == uwordnum)
905  {
906  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
907  & (~(bitmapword) 0) >> ushiftbits;
908  }
909  else
910  {
911  /* turn on lbitnum and all bits left of it */
912  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
913 
914  /* turn on all bits for any intermediate words */
915  while (wordnum < uwordnum)
916  a->words[wordnum++] = ~(bitmapword) 0;
917 
918  /* turn on upper's bit and all bits right of it. */
919  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
920  }
921 
922  return a;
923 }
int nwords
Definition: bitmapset.h:39
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:44
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
#define BITNUM(x)
Definition: bitmapset.c:28
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:75
uint32 bitmapword
Definition: bitmapset.h:34
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:30
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
void * palloc0(Size size)
Definition: mcxt.c:955
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1044
int i
#define elog
Definition: elog.h:219

◆ bms_compare()

int bms_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 206 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().

207 {
208  int shortlen;
209  int i;
210 
211  /* Handle cases where either input is NULL */
212  if (a == NULL)
213  return bms_is_empty(b) ? 0 : -1;
214  else if (b == NULL)
215  return bms_is_empty(a) ? 0 : +1;
216  /* Handle cases where one input is longer than the other */
217  shortlen = Min(a->nwords, b->nwords);
218  for (i = shortlen; i < a->nwords; i++)
219  {
220  if (a->words[i] != 0)
221  return +1;
222  }
223  for (i = shortlen; i < b->nwords; i++)
224  {
225  if (b->words[i] != 0)
226  return -1;
227  }
228  /* Process words in common */
229  i = shortlen;
230  while (--i >= 0)
231  {
232  bitmapword aw = a->words[i];
233  bitmapword bw = b->words[i];
234 
235  if (aw != bw)
236  return (aw > bw) ? +1 : -1;
237  }
238  return 0;
239 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
int i

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

Definition at line 133 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(), ExecFindInitialMatchingSubPlans(), ExecFindMatchingSubPlans(), ExecSetupPartitionPruneState(), 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().

134 {
135  Bitmapset *result;
136  size_t size;
137 
138  if (a == NULL)
139  return NULL;
140  size = BITMAPSET_SIZE(a->nwords);
141  result = (Bitmapset *) palloc(size);
142  memcpy(result, a, size);
143  return result;
144 }
int nwords
Definition: bitmapset.h:39
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:30
void * palloc(Size size)
Definition: mcxt.c:924

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 801 of file bitmapset.c.

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

Referenced by adjust_child_relids(), adjust_relid_set(), build_index_paths(), 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_multiple_relids_walker(), and TopologicalSort().

802 {
803  int wordnum,
804  bitnum;
805 
806  if (x < 0)
807  elog(ERROR, "negative bitmapset member not allowed");
808  if (a == NULL)
809  return NULL;
810  wordnum = WORDNUM(x);
811  bitnum = BITNUM(x);
812  if (wordnum < a->nwords)
813  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
814  return a;
815 }
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define elog
Definition: elog.h:219

◆ bms_del_members()

Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 955 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(), and min_join_parameterization().

956 {
957  int shortlen;
958  int i;
959 
960  /* Handle cases where either input is NULL */
961  if (a == NULL)
962  return NULL;
963  if (b == NULL)
964  return a;
965  /* Remove b's bits from a; we need never copy */
966  shortlen = Min(a->nwords, b->nwords);
967  for (i = 0; i < shortlen; i++)
968  a->words[i] &= ~b->words[i];
969  return a;
970 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_difference()

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

Definition at line 350 of file bitmapset.c.

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

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

351 {
352  Bitmapset *result;
353  int shortlen;
354  int i;
355 
356  /* Handle cases where either input is NULL */
357  if (a == NULL)
358  return NULL;
359  if (b == NULL)
360  return bms_copy(a);
361  /* Copy the left input */
362  result = bms_copy(a);
363  /* And remove b's bits from result */
364  shortlen = Min(a->nwords, b->nwords);
365  for (i = 0; i < shortlen; i++)
366  result->words[i] &= ~b->words[i];
367  return result;
368 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:133
#define Min(x, y)
Definition: c.h:857
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_equal()

bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 153 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_join_rel(), find_param_path_info(), fix_indexqual_references(), 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(), match_pathkeys_to_index(), populate_joinrel_with_paths(), and try_partitionwise_join().

154 {
155  const Bitmapset *shorter;
156  const Bitmapset *longer;
157  int shortlen;
158  int longlen;
159  int i;
160 
161  /* Handle cases where either input is NULL */
162  if (a == NULL)
163  {
164  if (b == NULL)
165  return true;
166  return bms_is_empty(b);
167  }
168  else if (b == NULL)
169  return bms_is_empty(a);
170  /* Identify shorter and longer input */
171  if (a->nwords <= b->nwords)
172  {
173  shorter = a;
174  longer = b;
175  }
176  else
177  {
178  shorter = b;
179  longer = a;
180  }
181  /* And process */
182  shortlen = shorter->nwords;
183  for (i = 0; i < shortlen; i++)
184  {
185  if (shorter->words[i] != longer->words[i])
186  return false;
187  }
188  longlen = longer->nwords;
189  for (; i < longlen; i++)
190  {
191  if (longer->words[i] != 0)
192  return false;
193  }
194  return true;
195 }
int nwords
Definition: bitmapset.h:39
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
int i

◆ bms_first_member()

int bms_first_member ( Bitmapset a)

Definition at line 1023 of file bitmapset.c.

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

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

1024 {
1025  int nwords;
1026  int wordnum;
1027 
1028  if (a == NULL)
1029  return -1;
1030  nwords = a->nwords;
1031  for (wordnum = 0; wordnum < nwords; wordnum++)
1032  {
1033  bitmapword w = a->words[wordnum];
1034 
1035  if (w != 0)
1036  {
1037  int result;
1038 
1039  w = RIGHTMOST_ONE(w);
1040  a->words[wordnum] &= ~w;
1041 
1042  result = wordnum * BITS_PER_BITMAPWORD;
1043  while ((w & 255) == 0)
1044  {
1045  w >>= 8;
1046  result += 8;
1047  }
1048  result += rightmost_one_pos[w & 255];
1049  return result;
1050  }
1051  }
1052  return -1;
1053 }
int nwords
Definition: bitmapset.h:39
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
uint32 bitmapword
Definition: bitmapset.h:34
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:71
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define RIGHTMOST_ONE(x)
Definition: bitmapset.c:50

◆ bms_free()

◆ bms_get_singleton_member()

bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 635 of file bitmapset.c.

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

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

636 {
637  int result = -1;
638  int nwords;
639  int wordnum;
640 
641  if (a == NULL)
642  return false;
643  nwords = a->nwords;
644  for (wordnum = 0; wordnum < nwords; wordnum++)
645  {
646  bitmapword w = a->words[wordnum];
647 
648  if (w != 0)
649  {
650  if (result >= 0 || HAS_MULTIPLE_ONES(w))
651  return false;
652  result = wordnum * BITS_PER_BITMAPWORD;
653  while ((w & 255) == 0)
654  {
655  w >>= 8;
656  result += 8;
657  }
658  result += rightmost_one_pos[w & 255];
659  }
660  }
661  if (result < 0)
662  return false;
663  *member = result;
664  return true;
665 }
int nwords
Definition: bitmapset.h:39
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:52
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
uint32 bitmapword
Definition: bitmapset.h:34
Oid member
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:71
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset a)

Definition at line 1196 of file bitmapset.c.

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

Referenced by bitmap_hash().

1197 {
1198  int lastword;
1199 
1200  if (a == NULL)
1201  return 0; /* All empty sets hash to 0 */
1202  for (lastword = a->nwords; --lastword >= 0;)
1203  {
1204  if (a->words[lastword] != 0)
1205  break;
1206  }
1207  if (lastword < 0)
1208  return 0; /* All empty sets hash to 0 */
1209  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1210  (lastword + 1) * sizeof(bitmapword)));
1211 }
#define DatumGetUInt32(X)
Definition: postgres.h:471
int nwords
Definition: bitmapset.h:39
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:428

◆ bms_int_members()

Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 929 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(), make_outerjoininfo(), make_row_comparison_op(), perform_pruning_combine_step(), pull_varnos_walker(), and relation_is_updatable().

930 {
931  int shortlen;
932  int i;
933 
934  /* Handle cases where either input is NULL */
935  if (a == NULL)
936  return NULL;
937  if (b == NULL)
938  {
939  pfree(a);
940  return NULL;
941  }
942  /* Intersect b into 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  for (; i < a->nwords; i++)
947  a->words[i] = 0;
948  return a;
949 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
void pfree(void *pointer)
Definition: mcxt.c:1031
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_intersect()

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

Definition at line 318 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(), process_equivalence(), reconsider_full_join_clause(), reconsider_outer_join_clause(), set_param_references(), and UpdateChangedParamSet().

319 {
320  Bitmapset *result;
321  const Bitmapset *other;
322  int resultlen;
323  int i;
324 
325  /* Handle cases where either input is NULL */
326  if (a == NULL || b == NULL)
327  return NULL;
328  /* Identify shorter and longer input; copy the shorter one */
329  if (a->nwords <= b->nwords)
330  {
331  result = bms_copy(a);
332  other = b;
333  }
334  else
335  {
336  result = bms_copy(b);
337  other = a;
338  }
339  /* And intersect the longer input with the result */
340  resultlen = result->nwords;
341  for (i = 0; i < resultlen; i++)
342  result->words[i] &= other->words[i];
343  return result;
344 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:133
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_is_empty()

bool bms_is_empty ( const Bitmapset a)

Definition at line 729 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_lateral_join_info(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecFindInitialMatchingSubPlans(), ExecInitAppend(), ExecInitParallelPlan(), ExecParallelReinitialize(), ExecReScanSetParamPlan(), finalize_plan(), find_nonnullable_rels_walker(), find_placeholder_info(), find_single_rel_for_clauses(), find_subplans_for_params_recurse(), gen_partprune_steps_internal(), 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(), hash_inner_and_outer(), is_pseudo_constant_clause_relids(), make_outerjoininfo(), make_restrictinfo_internal(), match_unsorted_outer(), min_join_parameterization(), postgresGetForeignPaths(), preprocess_grouping_sets(), process_equivalence(), pull_varnos_walker(), recurse_set_operations(), relation_has_unique_index_for(), relation_is_updatable(), remove_rel_from_query(), rewriteTargetView(), sepgsql_dml_privileges(), set_subquery_pathlist(), sort_inner_and_outer(), TopologicalSort(), try_partial_hashjoin_path(), try_partial_mergejoin_path(), try_partial_nestloop_path(), UpdateChangedParamSet(), and use_physical_tlist().

730 {
731  int nwords;
732  int wordnum;
733 
734  if (a == NULL)
735  return true;
736  nwords = a->nwords;
737  for (wordnum = 0; wordnum < nwords; wordnum++)
738  {
739  bitmapword w = a->words[wordnum];
740 
741  if (w != 0)
742  return false;
743  }
744  return true;
745 }
int nwords
Definition: bitmapset.h:39
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 486 of file bitmapset.c.

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

Referenced by adjust_child_relids(), adjust_relid_set(), adjust_rowcompare_for_index(), adjust_rowcount_for_semijoins(), bms_is_subset_singleton(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clauselist_selectivity(), ComputePartitionAttrs(), consider_groupingsets_paths(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_plan(), 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(), ExecFindInitialMatchingSubPlans(), ExecInitAppend(), ExecInitModifyTable(), ExplainSubPlans(), find_appinfos_by_relids(), 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(), inheritance_planner(), InitPlan(), is_subquery_var(), 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_clause_to_indexcol(), match_rowcompare_to_indexcol(), partkey_datum_from_expr(), perform_pruning_base_step(), plpgsql_param_fetch(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), ProjIndexIsUnchanged(), pullup_replace_vars_callback(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), set_append_rel_size(), set_join_column_names(), set_rtable_names(), substitute_multiple_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), use_physical_tlist(), and view_cols_are_auto_updatable().

487 {
488  int wordnum,
489  bitnum;
490 
491  /* XXX better to just return false for x<0 ? */
492  if (x < 0)
493  elog(ERROR, "negative bitmapset member not allowed");
494  if (a == NULL)
495  return false;
496  wordnum = WORDNUM(x);
497  bitnum = BITNUM(x);
498  if (wordnum >= a->nwords)
499  return false;
500  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
501  return true;
502  return false;
503 }
int nwords
Definition: bitmapset.h:39
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define elog
Definition: elog.h:219

◆ bms_is_subset()

bool bms_is_subset ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 374 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(), create_nestloop_plan(), deconstruct_recurse(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_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_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), 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(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), try_partial_nestloop_path(), update_placeholder_eval_levels(), and use_physical_tlist().

375 {
376  int shortlen;
377  int longlen;
378  int i;
379 
380  /* Handle cases where either input is NULL */
381  if (a == NULL)
382  return true; /* empty set is a subset of anything */
383  if (b == NULL)
384  return bms_is_empty(a);
385  /* Check common words */
386  shortlen = Min(a->nwords, b->nwords);
387  for (i = 0; i < shortlen; i++)
388  {
389  if ((a->words[i] & ~b->words[i]) != 0)
390  return false;
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  return false;
400  }
401  }
402  return true;
403 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
int i

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

Definition at line 976 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_relids_in_jointree(), process_equivalence(), pull_up_sublinks_jointree_recurse(), pull_varnos_walker(), and UpdateChangedParamSet().

977 {
978  Bitmapset *result;
979  Bitmapset *other;
980  int otherlen;
981  int i;
982 
983  /* Handle cases where either input is NULL */
984  if (a == NULL)
985  return b;
986  if (b == NULL)
987  return a;
988  /* Identify shorter and longer input; use longer one as result */
989  if (a->nwords < b->nwords)
990  {
991  result = b;
992  other = a;
993  }
994  else
995  {
996  result = a;
997  other = b;
998  }
999  /* And union the shorter input into the result */
1000  otherlen = other->nwords;
1001  for (i = 0; i < otherlen; i++)
1002  result->words[i] |= other->words[i];
1003  if (other != result) /* pure paranoia */
1004  pfree(other);
1005  return result;
1006 }
int nwords
Definition: bitmapset.h:39
void pfree(void *pointer)
Definition: mcxt.c:1031
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_make_singleton()

Bitmapset* bms_make_singleton ( int  x)

Definition at line 245 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(), extract_lateral_references(), 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().

246 {
247  Bitmapset *result;
248  int wordnum,
249  bitnum;
250 
251  if (x < 0)
252  elog(ERROR, "negative bitmapset member not allowed");
253  wordnum = WORDNUM(x);
254  bitnum = BITNUM(x);
255  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
256  result->nwords = wordnum + 1;
257  result->words[wordnum] = ((bitmapword) 1 << bitnum);
258  return result;
259 }
int nwords
Definition: bitmapset.h:39
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:30
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
void * palloc0(Size size)
Definition: mcxt.c:955
#define elog
Definition: elog.h:219

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 700 of file bitmapset.c.

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

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

701 {
702  BMS_Membership result = BMS_EMPTY_SET;
703  int nwords;
704  int wordnum;
705 
706  if (a == NULL)
707  return BMS_EMPTY_SET;
708  nwords = a->nwords;
709  for (wordnum = 0; wordnum < nwords; wordnum++)
710  {
711  bitmapword w = a->words[wordnum];
712 
713  if (w != 0)
714  {
715  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
716  return BMS_MULTIPLE;
717  result = BMS_SINGLETON;
718  }
719  }
720  return result;
721 }
int nwords
Definition: bitmapset.h:39
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:52
uint32 bitmapword
Definition: bitmapset.h:34
BMS_Membership
Definition: bitmapset.h:54
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40

◆ bms_next_member()

int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1075 of file bitmapset.c.

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

Referenced by add_join_clause_to_rels(), add_paths_to_append_rel(), adjust_view_column_set(), alias_relid_set(), approximate_joinrel_size(), choose_next_subplan_for_worker(), choose_next_subplan_locally(), create_lateral_join_info(), deparseLockingClause(), dependency_degree(), EstimateParamExecSpace(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecEvalParamExecParams(), ExecInitAgg(), ExecScanReScan(), find_subplans_for_params_recurse(), fixup_inherited_columns(), format_expr_params(), generate_partitionwise_join_paths(), get_loop_count(), get_matching_partitions(), inheritance_planner(), logicalrep_rel_open(), lookup_var_attr_stats(), offset_relid_set(), outBitmapset(), pg_ndistinct_out(), postgresBeginForeignScan(), postgresPlanDirectModify(), postgresPlanForeignModify(), prune_append_rel_partitions(), remove_join_clause_from_rels(), SerializeParamExecParams(), set_customscan_references(), set_foreignscan_references(), show_eval_params(), statext_dependencies_build(), and statext_ndistinct_serialize().

1076 {
1077  int nwords;
1078  int wordnum;
1079  bitmapword mask;
1080 
1081  if (a == NULL)
1082  return -2;
1083  nwords = a->nwords;
1084  prevbit++;
1085  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1086  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1087  {
1088  bitmapword w = a->words[wordnum];
1089 
1090  /* ignore bits before prevbit */
1091  w &= mask;
1092 
1093  if (w != 0)
1094  {
1095  int result;
1096 
1097  result = wordnum * BITS_PER_BITMAPWORD;
1098  while ((w & 255) == 0)
1099  {
1100  w >>= 8;
1101  result += 8;
1102  }
1103  result += rightmost_one_pos[w & 255];
1104  return result;
1105  }
1106 
1107  /* in subsequent words, consider all bits */
1108  mask = (~(bitmapword) 0);
1109  }
1110  return -2;
1111 }
int nwords
Definition: bitmapset.h:39
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:71
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40

◆ bms_nonempty_difference()

bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 560 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().

561 {
562  int shortlen;
563  int i;
564 
565  /* Handle cases where either input is NULL */
566  if (a == NULL)
567  return false;
568  if (b == NULL)
569  return !bms_is_empty(a);
570  /* Check words in common */
571  shortlen = Min(a->nwords, b->nwords);
572  for (i = 0; i < shortlen; i++)
573  {
574  if ((a->words[i] & ~b->words[i]) != 0)
575  return true;
576  }
577  /* Check extra words in a */
578  for (; i < a->nwords; i++)
579  {
580  if (a->words[i] != 0)
581  return true;
582  }
583  return false;
584 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
int i

◆ bms_num_members()

int bms_num_members ( const Bitmapset a)

Definition at line 671 of file bitmapset.c.

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

Referenced by adjust_appendrel_attrs_multilevel(), build_join_rel(), BuildRelationExtStatistics(), choose_best_statistics(), deparseFromExpr(), deparseLockingClause(), deparseVar(), dependencies_clauselist_selectivity(), dependency_degree(), estimate_multivariate_ndistinct(), ExecFindInitialMatchingSubPlans(), ExecInitAppend(), find_appinfos_by_relids(), find_hash_columns(), find_strongest_dependency(), gen_partprune_steps_internal(), get_matching_hash_bounds(), lookup_var_attr_stats(), mark_invalid_subplans_as_finished(), NumRelids(), SerializeParamExecParams(), statext_dependencies_build(), statext_ndistinct_build(), and statext_ndistinct_serialize().

672 {
673  int result = 0;
674  int nwords;
675  int wordnum;
676 
677  if (a == NULL)
678  return 0;
679  nwords = a->nwords;
680  for (wordnum = 0; wordnum < nwords; wordnum++)
681  {
682  bitmapword w = a->words[wordnum];
683 
684  /* we assume here that bitmapword is an unsigned type */
685  while (w != 0)
686  {
687  result += number_of_ones[w & 255];
688  w >>= 8;
689  }
690  }
691  return result;
692 }
int nwords
Definition: bitmapset.h:39
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
static const uint8 number_of_ones[256]
Definition: bitmapset.c:109

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 509 of file bitmapset.c.

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

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), add_placeholders_to_child_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(), create_nestloop_plan(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecUpdateLockMode(), generate_implied_equalities_for_column(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_partition_attrs(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), inheritance_planner(), join_clause_is_movable_into(), join_clause_is_movable_to(), join_is_legal(), join_is_removable(), join_search_one_level(), make_join_rel(), make_outerjoininfo(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo_internal(), pullup_replace_vars_callback(), reduce_outer_joins_pass2(), reparameterize_path_by_child(), replace_nestloop_params_mutator(), select_outer_pathkeys_for_merge(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), try_partitionwise_join(), and update_placeholder_eval_levels().

510 {
511  int shortlen;
512  int i;
513 
514  /* Handle cases where either input is NULL */
515  if (a == NULL || b == NULL)
516  return false;
517  /* Check words in common */
518  shortlen = Min(a->nwords, b->nwords);
519  for (i = 0; i < shortlen; i++)
520  {
521  if ((a->words[i] & b->words[i]) != 0)
522  return true;
523  }
524  return false;
525 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_overlap_list()

bool bms_overlap_list ( const Bitmapset a,
const List b 
)

Definition at line 531 of file bitmapset.c.

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

Referenced by preprocess_grouping_sets().

532 {
533  ListCell *lc;
534  int wordnum,
535  bitnum;
536 
537  if (a == NULL || b == NIL)
538  return false;
539 
540  foreach(lc, b)
541  {
542  int x = lfirst_int(lc);
543 
544  if (x < 0)
545  elog(ERROR, "negative bitmapset member not allowed");
546  wordnum = WORDNUM(x);
547  bitnum = BITNUM(x);
548  if (wordnum < a->nwords)
549  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
550  return true;
551  }
552 
553  return false;
554 }
#define NIL
Definition: pg_list.h:69
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:107
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define elog
Definition: elog.h:219

◆ bms_prev_member()

int bms_prev_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1139 of file bitmapset.c.

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

Referenced by choose_next_subplan_locally().

1140 {
1141  int wordnum;
1142  int ushiftbits;
1143  bitmapword mask;
1144 
1145  /*
1146  * If set is NULL or if there are no more bits to the right then we've
1147  * nothing to do.
1148  */
1149  if (a == NULL || prevbit == 0)
1150  return -2;
1151 
1152  /* transform -1 to the highest possible bit we could have set */
1153  if (prevbit == -1)
1154  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1155  else
1156  prevbit--;
1157 
1158  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1159  mask = (~(bitmapword) 0) >> ushiftbits;
1160  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1161  {
1162  bitmapword w = a->words[wordnum];
1163 
1164  /* mask out bits left of prevbit */
1165  w &= mask;
1166 
1167  if (w != 0)
1168  {
1169  int result;
1170  int shift = BITS_PER_BITMAPWORD - 8;
1171 
1172  result = wordnum * BITS_PER_BITMAPWORD;
1173 
1174  while ((w >> shift) == 0)
1175  shift -= 8;
1176 
1177  result += shift + leftmost_one_pos[(w >> shift) & 255];
1178  return result;
1179  }
1180 
1181  /* in subsequent words, consider all bits */
1182  mask = (~(bitmapword) 0);
1183  }
1184  return -2;
1185 }
int nwords
Definition: bitmapset.h:39
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
static const uint8 leftmost_one_pos[256]
Definition: bitmapset.c:90

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

Definition at line 592 of file bitmapset.c.

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

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

593 {
594  int result = -1;
595  int nwords;
596  int wordnum;
597 
598  if (a == NULL)
599  elog(ERROR, "bitmapset is empty");
600  nwords = a->nwords;
601  for (wordnum = 0; wordnum < nwords; wordnum++)
602  {
603  bitmapword w = a->words[wordnum];
604 
605  if (w != 0)
606  {
607  if (result >= 0 || HAS_MULTIPLE_ONES(w))
608  elog(ERROR, "bitmapset has multiple members");
609  result = wordnum * BITS_PER_BITMAPWORD;
610  while ((w & 255) == 0)
611  {
612  w >>= 8;
613  result += 8;
614  }
615  result += rightmost_one_pos[w & 255];
616  }
617  }
618  if (result < 0)
619  elog(ERROR, "bitmapset is empty");
620  return result;
621 }
int nwords
Definition: bitmapset.h:39
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:52
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
uint32 bitmapword
Definition: bitmapset.h:34
#define ERROR
Definition: elog.h:43
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:71
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define elog
Definition: elog.h:219

◆ bms_subset_compare()

BMS_Comparison bms_subset_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 411 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().

412 {
413  BMS_Comparison result;
414  int shortlen;
415  int longlen;
416  int i;
417 
418  /* Handle cases where either input is NULL */
419  if (a == NULL)
420  {
421  if (b == NULL)
422  return BMS_EQUAL;
423  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
424  }
425  if (b == NULL)
426  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
427  /* Check common words */
428  result = BMS_EQUAL; /* status so far */
429  shortlen = Min(a->nwords, b->nwords);
430  for (i = 0; i < shortlen; i++)
431  {
432  bitmapword aword = a->words[i];
433  bitmapword bword = b->words[i];
434 
435  if ((aword & ~bword) != 0)
436  {
437  /* a is not a subset of b */
438  if (result == BMS_SUBSET1)
439  return BMS_DIFFERENT;
440  result = BMS_SUBSET2;
441  }
442  if ((bword & ~aword) != 0)
443  {
444  /* b is not a subset of a */
445  if (result == BMS_SUBSET2)
446  return BMS_DIFFERENT;
447  result = BMS_SUBSET1;
448  }
449  }
450  /* Check extra words */
451  if (a->nwords > b->nwords)
452  {
453  longlen = a->nwords;
454  for (; i < longlen; i++)
455  {
456  if (a->words[i] != 0)
457  {
458  /* a is not a subset of b */
459  if (result == BMS_SUBSET1)
460  return BMS_DIFFERENT;
461  result = BMS_SUBSET2;
462  }
463  }
464  }
465  else if (a->nwords < b->nwords)
466  {
467  longlen = b->nwords;
468  for (; i < longlen; i++)
469  {
470  if (b->words[i] != 0)
471  {
472  /* b is not a subset of a */
473  if (result == BMS_SUBSET2)
474  return BMS_DIFFERENT;
475  result = BMS_SUBSET1;
476  }
477  }
478  }
479  return result;
480 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:857
uint32 bitmapword
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:729
int i
BMS_Comparison
Definition: bitmapset.h:45

◆ bms_union()

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

Definition at line 284 of file bitmapset.c.

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

Referenced by build_child_join_rel(), build_join_rel(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), check_index_predicates(), check_relation_privileges(), compute_semijoin_info(), consider_index_join_outer_rels(), create_join_clause(), create_nestloop_path(), create_nestloop_plan(), deconstruct_recurse(), ExecConstraints(), ExecPartitionCheckEmitError(), ExecSetupPartitionPruneState(), ExecWithCheckOptions(), finalize_plan(), foreign_join_ok(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), 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(), pull_up_sublinks_jointree_recurse(), reduce_unique_semijoins(), remove_useless_joins(), substitute_multiple_relids_walker(), and try_partitionwise_join().

285 {
286  Bitmapset *result;
287  const Bitmapset *other;
288  int otherlen;
289  int i;
290 
291  /* Handle cases where either input is NULL */
292  if (a == NULL)
293  return bms_copy(b);
294  if (b == NULL)
295  return bms_copy(a);
296  /* Identify shorter and longer input; copy the longer one */
297  if (a->nwords <= b->nwords)
298  {
299  result = bms_copy(b);
300  other = a;
301  }
302  else
303  {
304  result = bms_copy(a);
305  other = b;
306  }
307  /* And union the shorter input into the result */
308  otherlen = other->nwords;
309  for (i = 0; i < otherlen; i++)
310  result->words[i] |= other->words[i];
311  return result;
312 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:133
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

Variable Documentation

◆ leftmost_one_pos

const uint8 leftmost_one_pos[256]
static
Initial value:
= {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
}

Definition at line 90 of file bitmapset.c.

Referenced by bms_prev_member().

◆ number_of_ones

const uint8 number_of_ones[256]
static
Initial value:
= {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 109 of file bitmapset.c.

Referenced by bms_num_members().

◆ rightmost_one_pos

const uint8 rightmost_one_pos[256]
static
Initial value:
= {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}

Definition at line 71 of file bitmapset.c.

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