PostgreSQL Source Code  git master
bitmapset.h File Reference
#include "nodes/nodes.h"
Include dependency graph for bitmapset.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Bitmapset
 

Macros

#define BITS_PER_BITMAPWORD   32
 
#define bms_is_empty(a)   ((a) == NULL)
 

Typedefs

typedef uint32 bitmapword
 
typedef int32 signedbitmapword
 
typedef struct Bitmapset Bitmapset
 

Enumerations

enum  BMS_Comparison { BMS_EQUAL , BMS_SUBSET1 , BMS_SUBSET2 , BMS_DIFFERENT }
 
enum  BMS_Membership { BMS_EMPTY_SET , BMS_SINGLETON , BMS_MULTIPLE }
 

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 struct List *b)
 
bool bms_nonempty_difference (const Bitmapset *a, const Bitmapset *b)
 
int bms_singleton_member (const Bitmapset *a)
 
bool bms_get_singleton_member (const Bitmapset *a, int *member)
 
int bms_num_members (const Bitmapset *a)
 
BMS_Membership bms_membership (const Bitmapset *a)
 
Bitmapsetbms_add_member (Bitmapset *a, int x)
 
Bitmapsetbms_del_member (Bitmapset *a, int x)
 
Bitmapsetbms_add_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_add_range (Bitmapset *a, int lower, int upper)
 
Bitmapsetbms_int_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_del_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_join (Bitmapset *a, Bitmapset *b)
 
int bms_next_member (const Bitmapset *a, int prevbit)
 
int bms_prev_member (const Bitmapset *a, int prevbit)
 
uint32 bms_hash_value (const Bitmapset *a)
 
uint32 bitmap_hash (const void *key, Size keysize)
 
int bitmap_match (const void *key1, const void *key2, Size keysize)
 

Macro Definition Documentation

◆ BITS_PER_BITMAPWORD

#define BITS_PER_BITMAPWORD   32

Definition at line 43 of file bitmapset.h.

◆ bms_is_empty

#define bms_is_empty (   a)    ((a) == NULL)

Definition at line 105 of file bitmapset.h.

Typedef Documentation

◆ Bitmapset

typedef struct Bitmapset Bitmapset

◆ bitmapword

typedef uint32 bitmapword

Definition at line 44 of file bitmapset.h.

◆ signedbitmapword

Definition at line 45 of file bitmapset.h.

Enumeration Type Documentation

◆ BMS_Comparison

Enumerator
BMS_EQUAL 
BMS_SUBSET1 
BMS_SUBSET2 
BMS_DIFFERENT 

Definition at line 60 of file bitmapset.h.

61 {
62  BMS_EQUAL, /* sets are equal */
63  BMS_SUBSET1, /* first set is a subset of the second */
64  BMS_SUBSET2, /* second set is a subset of the first */
65  BMS_DIFFERENT /* neither set is a subset of the other */
BMS_Comparison
Definition: bitmapset.h:61
@ BMS_DIFFERENT
Definition: bitmapset.h:65
@ BMS_SUBSET1
Definition: bitmapset.h:63
@ BMS_EQUAL
Definition: bitmapset.h:62
@ BMS_SUBSET2
Definition: bitmapset.h:64

◆ BMS_Membership

Enumerator
BMS_EMPTY_SET 
BMS_SINGLETON 
BMS_MULTIPLE 

Definition at line 69 of file bitmapset.h.

70 {
71  BMS_EMPTY_SET, /* 0 members */
72  BMS_SINGLETON, /* 1 member */
73  BMS_MULTIPLE /* >1 member */
BMS_Membership
Definition: bitmapset.h:70
@ BMS_SINGLETON
Definition: bitmapset.h:72
@ BMS_EMPTY_SET
Definition: bitmapset.h:71
@ BMS_MULTIPLE
Definition: bitmapset.h:73

Function Documentation

◆ bitmap_hash()

uint32 bitmap_hash ( const void *  key,
Size  keysize 
)

Definition at line 1226 of file bitmapset.c.

1227 {
1228  Assert(keysize == sizeof(Bitmapset *));
1229  return bms_hash_value(*((const Bitmapset *const *) key));
1230 }
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1212
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 1236 of file bitmapset.c.

1237 {
1238  Assert(keysize == sizeof(Bitmapset *));
1239  return !bms_equal(*((const Bitmapset *const *) key1),
1240  *((const Bitmapset *const *) key2));
1241 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:97

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

754 {
755  int wordnum,
756  bitnum;
757 
758  if (x < 0)
759  elog(ERROR, "negative bitmapset member not allowed");
760  if (a == NULL)
761  return bms_make_singleton(x);
762  wordnum = WORDNUM(x);
763  bitnum = BITNUM(x);
764 
765  /* enlarge the set if necessary */
766  if (wordnum >= a->nwords)
767  {
768  int oldnwords = a->nwords;
769  int i;
770 
771  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
772  a->nwords = wordnum + 1;
773  /* zero out the enlarged portion */
774  i = oldnwords;
775  do
776  {
777  a->words[i] = 0;
778  } while (++i < a->nwords);
779  }
780 
781  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
782  return a;
783 }
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:38
#define WORDNUM(x)
Definition: bitmapset.c:35
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:171
#define BITNUM(x)
Definition: bitmapset.c:36
uint32 bitmapword
Definition: bitmapset.h:44
#define ERROR
Definition: elog.h:39
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:1476

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

Referenced by _readBitmapset(), add_child_rel_equivalences(), add_outer_joins_to_relids(), add_row_identity_var(), adjust_child_relids(), adjust_group_pathkeys_for_groupagg(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), AlterPublicationTables(), apply_handle_update(), ATInheritAdjustNotNulls(), build_joinrel_tlist(), build_subplan(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), clauselist_apply_dependencies(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), create_list_bounds(), DecodeTextArrayToBitmapset(), deconstruct_distribute_oj_quals(), deconstruct_recurse(), deparseColumnRef(), dependencies_clauselist_selectivity(), DiscreteKnapsack(), do_analyze_rel(), DoCopy(), estimate_multivariate_ndistinct(), EvalPlanQualBegin(), ExecAsyncAppendResponse(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecInitAgg(), ExecInitAppend(), ExecInitStoredGenerated(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanGather(), ExecReScanGatherMerge(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), execute_attr_map_cols(), expand_single_inheritance_child(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), extractRemainingColumns(), fetch_remote_table_info(), fetch_statentries_for_relation(), finalize_plan(), finalize_primnode(), find_childrel_parents(), find_cols(), find_cols_walker(), find_hash_columns(), find_matching_subplans_recurse(), find_window_run_conditions(), findDefaultOnlyColumns(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), gen_partprune_steps_internal(), generate_base_implied_equalities(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_eclass_for_sort_expr(), get_matching_partitions(), get_param_path_clause_serials(), get_primary_key_attnos(), get_relation_constraint_attnos(), get_relation_statistics(), get_relids_in_jointree(), HeapDetermineColumnsInfo(), infer_arbiter_indexes(), join_is_removable(), load_enum_cache_data(), logicalrep_read_attrs(), make_datum_param(), make_modifytable(), make_outerjoininfo(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), mark_rels_nulled_by_join(), markRelsAsNulledBy(), markRTEForSelectPriv(), mbms_add_member(), mbms_overlap_sets(), MergeAttributes(), nodeRead(), offset_relid_set(), PartitionPruneFixSubPlanMap(), preprocess_grouping_sets(), pub_collist_to_bitmapset(), publication_translate_columns(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_up_sublinks_jointree_recurse(), pull_varattnos_walker(), pull_varnos_walker(), reduce_outer_joins_pass2(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttrBitmap(), remove_rel_from_query(), 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(), transformTableLikeClause(), transformUpdateTargetList(), translate_col_privs(), try_partitionwise_join(), use_physical_tlist(), and view_cols_are_auto_updatable().

◆ bms_add_members()

Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 835 of file bitmapset.c.

836 {
837  Bitmapset *result;
838  const Bitmapset *other;
839  int otherlen;
840  int i;
841 
842  /* Handle cases where either input is NULL */
843  if (a == NULL)
844  return bms_copy(b);
845  if (b == NULL)
846  return a;
847  /* Identify shorter and longer input; copy the longer one if needed */
848  if (a->nwords < b->nwords)
849  {
850  result = bms_copy(b);
851  other = a;
852  }
853  else
854  {
855  result = a;
856  other = b;
857  }
858  /* And union the shorter input into the result */
859  otherlen = other->nwords;
860  i = 0;
861  do
862  {
863  result->words[i] |= other->words[i];
864  } while (++i < otherlen);
865  if (result != a)
866  pfree(a);
867  return result;
868 }
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:80
int b
Definition: isn.c:70
void pfree(void *pointer)
Definition: mcxt.c:1456
int nwords
Definition: bitmapset.h:54
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:55

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

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

◆ bms_add_range()

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

Definition at line 879 of file bitmapset.c.

880 {
881  int lwordnum,
882  lbitnum,
883  uwordnum,
884  ushiftbits,
885  wordnum;
886 
887  /* do nothing if nothing is called for, without further checking */
888  if (upper < lower)
889  return a;
890 
891  if (lower < 0)
892  elog(ERROR, "negative bitmapset member not allowed");
893  uwordnum = WORDNUM(upper);
894 
895  if (a == NULL)
896  {
897  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
898  a->type = T_Bitmapset;
899  a->nwords = uwordnum + 1;
900  }
901  else if (uwordnum >= a->nwords)
902  {
903  int oldnwords = a->nwords;
904  int i;
905 
906  /* ensure we have enough words to store the upper bit */
907  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
908  a->nwords = uwordnum + 1;
909  /* zero out the enlarged portion */
910  i = oldnwords;
911  do
912  {
913  a->words[i] = 0;
914  } while (++i < a->nwords);
915  }
916 
917  wordnum = lwordnum = WORDNUM(lower);
918 
919  lbitnum = BITNUM(lower);
920  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
921 
922  /*
923  * Special case when lwordnum is the same as uwordnum we must perform the
924  * upper and lower masking on the word.
925  */
926  if (lwordnum == uwordnum)
927  {
928  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
929  & (~(bitmapword) 0) >> ushiftbits;
930  }
931  else
932  {
933  /* turn on lbitnum and all bits left of it */
934  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
935 
936  /* turn on all bits for any intermediate words */
937  while (wordnum < uwordnum)
938  a->words[wordnum++] = ~(bitmapword) 0;
939 
940  /* turn on upper's bit and all bits right of it. */
941  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
942  }
943 
944  return a;
945 }
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
void * palloc0(Size size)
Definition: mcxt.c:1257
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80

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

139 {
140  int i;
141 
142  Assert(a == NULL || a->words[a->nwords - 1] != 0);
143  Assert(b == NULL || b->words[b->nwords - 1] != 0);
144 
145  /* Handle cases where either input is NULL */
146  if (a == NULL)
147  return (b == NULL) ? 0 : -1;
148  else if (b == NULL)
149  return +1;
150 
151  /* the set with the most words must be greater */
152  if (a->nwords != b->nwords)
153  return (a->nwords > b->nwords) ? +1 : -1;
154 
155  i = a->nwords - 1;
156  do
157  {
158  bitmapword aw = a->words[i];
159  bitmapword bw = b->words[i];
160 
161  if (aw != bw)
162  return (aw > bw) ? +1 : -1;
163  } while (--i >= 0);
164  return 0;
165 }

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

Referenced by append_startup_cost_compare(), and append_total_cost_compare().

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

Definition at line 80 of file bitmapset.c.

81 {
82  Bitmapset *result;
83  size_t size;
84 
85  if (a == NULL)
86  return NULL;
87  size = BITMAPSET_SIZE(a->nwords);
88  result = (Bitmapset *) palloc(size);
89  memcpy(result, a, size);
90  return result;
91 }
void * palloc(Size size)
Definition: mcxt.c:1226

References a, BITMAPSET_SIZE, and palloc().

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

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 793 of file bitmapset.c.

794 {
795  int wordnum,
796  bitnum;
797 
798  if (x < 0)
799  elog(ERROR, "negative bitmapset member not allowed");
800  if (a == NULL)
801  return NULL;
802  wordnum = WORDNUM(x);
803  bitnum = BITNUM(x);
804 
805  /* member can't exist. Return 'a' unmodified */
806  if (unlikely(wordnum >= a->nwords))
807  return a;
808 
809  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
810 
811  /* when last word becomes empty, trim off all trailing empty words */
812  if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
813  {
814  /* find the last non-empty word and make that the new final word */
815  for (int i = wordnum - 1; i >= 0; i--)
816  {
817  if (a->words[i] != 0)
818  {
819  a->nwords = i + 1;
820  return a;
821  }
822  }
823 
824  /* the set is now empty */
825  pfree(a);
826  return NULL;
827  }
828  return a;
829 }
#define unlikely(x)
Definition: c.h:300

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

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

◆ bms_del_members()

Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 993 of file bitmapset.c.

994 {
995  int i;
996 
997  Assert(a == NULL || a->words[a->nwords - 1] != 0);
998  Assert(b == NULL || b->words[b->nwords - 1] != 0);
999 
1000  /* Handle cases where either input is NULL */
1001  if (a == NULL)
1002  return NULL;
1003  if (b == NULL)
1004  return a;
1005  /* Remove b's bits from a; we need never copy */
1006  if (a->nwords > b->nwords)
1007  {
1008  /*
1009  * We'll never need to remove trailing zero words when 'a' has more
1010  * words than 'b'.
1011  */
1012  i = 0;
1013  do
1014  {
1015  a->words[i] &= ~b->words[i];
1016  } while (++i < b->nwords);
1017  }
1018  else
1019  {
1020  int lastnonzero = -1;
1021 
1022  /* we may need to remove trailing zero words from the result. */
1023  i = 0;
1024  do
1025  {
1026  a->words[i] &= ~b->words[i];
1027 
1028  /* remember the last non-zero word */
1029  if (a->words[i] != 0)
1030  lastnonzero = i;
1031  } while (++i < a->nwords);
1032 
1033  /* check if 'a' has become empty */
1034  if (lastnonzero == -1)
1035  {
1036  pfree(a);
1037  return NULL;
1038  }
1039 
1040  /* trim off any trailing zero words */
1041  a->nwords = lastnonzero + 1;
1042  }
1043 
1044  return a;
1045 }

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

Referenced by adjust_group_pathkeys_for_groupagg(), build_join_rel(), calc_nestloop_required_outer(), check_index_predicates(), classify_matching_subplans(), DiscreteKnapsack(), finalize_plan(), get_join_domain_min_rels(), make_outerjoininfo(), make_partition_pruneinfo(), min_join_parameterization(), and NumRelids().

◆ bms_difference()

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

Definition at line 297 of file bitmapset.c.

298 {
299  Bitmapset *result;
300  int i;
301 
302  Assert(a == NULL || a->words[a->nwords - 1] != 0);
303  Assert(b == NULL || b->words[b->nwords - 1] != 0);
304 
305  /* Handle cases where either input is NULL */
306  if (a == NULL)
307  return NULL;
308  if (b == NULL)
309  return bms_copy(a);
310 
311  /*
312  * In Postgres' usage, an empty result is a very common case, so it's
313  * worth optimizing for that by testing bms_nonempty_difference(). This
314  * saves us a palloc/pfree cycle compared to checking after-the-fact.
315  */
316  if (!bms_nonempty_difference(a, b))
317  return NULL;
318 
319  /* Copy the left input */
320  result = bms_copy(a);
321 
322  /* And remove b's bits from result */
323  if (result->nwords > b->nwords)
324  {
325  /*
326  * We'll never need to remove trailing zero words when 'a' has more
327  * words than 'b' as the additional words must be non-zero.
328  */
329  i = 0;
330  do
331  {
332  result->words[i] &= ~b->words[i];
333  } while (++i < b->nwords);
334  }
335  else
336  {
337  int lastnonzero = -1;
338 
339  /* we may need to remove trailing zero words from the result. */
340  i = 0;
341  do
342  {
343  result->words[i] &= ~b->words[i];
344 
345  /* remember the last non-zero word */
346  if (result->words[i] != 0)
347  lastnonzero = i;
348  } while (++i < result->nwords);
349 
350  /* trim off trailing zero words */
351  result->nwords = lastnonzero + 1;
352  }
353  Assert(result->nwords != 0);
354 
355  /* Need not check for empty result, since we handled that case above */
356  return result;
357 }
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:581

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

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

◆ bms_equal()

bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 97 of file bitmapset.c.

98 {
99  int i;
100 
101  Assert(a == NULL || a->words[a->nwords - 1] != 0);
102  Assert(b == NULL || b->words[b->nwords - 1] != 0);
103 
104  /* Handle cases where either input is NULL */
105  if (a == NULL)
106  {
107  if (b == NULL)
108  return true;
109  return false;
110  }
111  else if (b == NULL)
112  return false;
113 
114  /* can't be equal if the word counts don't match */
115  if (a->nwords != b->nwords)
116  return false;
117 
118  /* check each word matches */
119  i = 0;
120  do
121  {
122  if (a->words[i] != b->words[i])
123  return false;
124  } while (++i < a->nwords);
125 
126  return true;
127 }

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

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(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), extract_rollup_sets(), fetch_upper_rel(), find_dependent_phvs_walker(), find_join_rel(), find_param_path_info(), generate_implied_equalities_for_column(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), get_join_domain_min_rels(), has_join_restriction(), infer_arbiter_indexes(), 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(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), set_rel_pathlist(), standard_join_search(), and try_partitionwise_join().

◆ bms_free()

◆ bms_get_singleton_member()

bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 652 of file bitmapset.c.

653 {
654  int result = -1;
655  int nwords;
656  int wordnum;
657 
658  if (a == NULL)
659  return false;
660  nwords = a->nwords;
661  wordnum = 0;
662  do
663  {
664  bitmapword w = a->words[wordnum];
665 
666  if (w != 0)
667  {
668  if (result >= 0 || HAS_MULTIPLE_ONES(w))
669  return false;
670  result = wordnum * BITS_PER_BITMAPWORD;
671  result += bmw_rightmost_one_pos(w);
672  }
673  } while (++wordnum < nwords);
674 
675  /* we don't expect non-NULL sets to be empty */
676  Assert(result >= 0);
677  *member = result;
678  return true;
679 }
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:65
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:60

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

Referenced by add_placeholders_to_base_rels(), create_lateral_join_info(), 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 1212 of file bitmapset.c.

1213 {
1214  if (a == NULL)
1215  return 0; /* All empty sets hash to 0 */
1216  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1217  a->nwords * sizeof(bitmapword)));
1218 }
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222

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

Referenced by bitmap_hash().

◆ bms_int_members()

Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 951 of file bitmapset.c.

952 {
953  int lastnonzero;
954  int shortlen;
955  int i;
956 
957  /* Handle cases where either input is NULL */
958  if (a == NULL)
959  return NULL;
960  if (b == NULL)
961  {
962  pfree(a);
963  return NULL;
964  }
965  /* Intersect b into a; we need never copy */
966  shortlen = Min(a->nwords, b->nwords);
967  lastnonzero = -1;
968  i = 0;
969  do
970  {
971  a->words[i] &= b->words[i];
972 
973  if (a->words[i] != 0)
974  lastnonzero = i;
975  } while (++i < shortlen);
976 
977  /* If we computed an empty result, we must return NULL */
978  if (lastnonzero == -1)
979  {
980  pfree(a);
981  return NULL;
982  }
983 
984  /* get rid of trailing zero words */
985  a->nwords = lastnonzero + 1;
986  return a;
987 }
#define Min(x, y)
Definition: c.h:993

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

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

◆ bms_intersect()

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

Definition at line 248 of file bitmapset.c.

249 {
250  Bitmapset *result;
251  const Bitmapset *other;
252  int lastnonzero;
253  int resultlen;
254  int i;
255 
256  /* Handle cases where either input is NULL */
257  if (a == NULL || b == NULL)
258  return NULL;
259  /* Identify shorter and longer input; copy the shorter one */
260  if (a->nwords <= b->nwords)
261  {
262  result = bms_copy(a);
263  other = b;
264  }
265  else
266  {
267  result = bms_copy(b);
268  other = a;
269  }
270  /* And intersect the longer input with the result */
271  resultlen = result->nwords;
272  lastnonzero = -1;
273  i = 0;
274  do
275  {
276  result->words[i] &= other->words[i];
277 
278  if (result->words[i] != 0)
279  lastnonzero = i;
280  } while (++i < resultlen);
281  /* If we computed an empty result, we must return NULL */
282  if (lastnonzero == -1)
283  {
284  pfree(result);
285  return NULL;
286  }
287 
288  /* get rid of trailing zero words */
289  result->nwords = lastnonzero + 1;
290  return result;
291 }

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

Referenced by build_joinrel_tlist(), classify_matching_subplans(), create_lateral_join_info(), distribute_qual_to_rels(), get_matching_part_pairs(), identify_current_nestloop_params(), make_outerjoininfo(), match_eclasses_to_foreign_key_col(), set_param_references(), and UpdateChangedParamSet().

◆ bms_is_member()

bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 460 of file bitmapset.c.

461 {
462  int wordnum,
463  bitnum;
464 
465  /* XXX better to just return false for x<0 ? */
466  if (x < 0)
467  elog(ERROR, "negative bitmapset member not allowed");
468  if (a == NULL)
469  return false;
470  wordnum = WORDNUM(x);
471  bitnum = BITNUM(x);
472  if (wordnum >= a->nwords)
473  return false;
474  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
475  return true;
476  return false;
477 }

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

Referenced by add_nulling_relids_mutator(), add_outer_joins_to_relids(), add_row_identity_var(), adjust_appendrel_attrs_mutator(), adjust_child_relids(), adjust_relid_set(), adjust_rowcount_for_semijoins(), ATExecDropNotNull(), bms_member_index(), build_joinrel_tlist(), check_index_predicates(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), clause_selectivity_ext(), clauselist_selectivity_ext(), clauselist_selectivity_or(), column_in_column_list(), ComputePartitionAttrs(), consider_groupingsets_paths(), contain_invalid_rfcolumn_walker(), contain_placeholder_references_walker(), cost_incremental_sort(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_path(), deconstruct_distribute_oj_quals(), DefineIndex(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), do_analyze_rel(), dropconstraint_internal(), enum_known_sorted(), estimate_multivariate_ndistinct(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecBuildUpdateProjection(), ExecCheckPermissions(), ExecEvalGroupingFunc(), ExecInitModifyTable(), execute_attr_map_cols(), expand_indexqual_rowcompare(), expand_single_inheritance_child(), ExplainSubPlans(), extractRemainingColumns(), ExtractReplicaIdentity(), fetch_remote_table_info(), filter_event_trigger(), find_hash_columns(), find_modifytable_subplan(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), gen_partprune_steps_internal(), gen_prune_steps_from_opexps(), generate_base_implied_equalities(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_foreign_key_join_selectivity(), get_join_domain_min_rels(), get_matching_hash_bounds(), get_tablefunc(), get_translated_update_targetlist(), get_variable(), has_partition_attrs(), hashagg_spill_tuple(), HeapDetermineColumnsInfo(), identify_current_nestloop_params(), index_expression_changed_walker(), index_unchanged_by_update(), InitPlan(), is_foreign_param(), is_pseudo_constant_for_index(), is_subquery_var(), IsBinaryTidClause(), isPlainForeignVar(), IsTidEqualAnyClause(), join_clause_is_movable_to(), join_is_removable(), lo_manage(), logicalrep_rel_mark_updatable(), logicalrep_write_attrs(), make_outerjoininfo(), make_window_input_target(), mark_invalid_subplans_as_finished(), mark_rels_nulled_by_join(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), mbms_is_member(), MergeAttributes(), partitions_are_ordered(), perform_pruning_base_step(), plpgsql_param_fetch(), postgresExplainForeignScan(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pub_collist_contains_invalid_column(), publication_translate_columns(), pullup_replace_vars_callback(), rangeTableEntry_used_walker(), remove_nulling_relids_mutator(), remove_rel_from_eclass(), 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(), transformTableLikeClause(), translate_col_privs(), TriggerEnabled(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), 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 363 of file bitmapset.c.

364 {
365  int i;
366 
367  Assert(a == NULL || a->words[a->nwords - 1] != 0);
368  Assert(b == NULL || b->words[b->nwords - 1] != 0);
369 
370  /* Handle cases where either input is NULL */
371  if (a == NULL)
372  return true; /* empty set is a subset of anything */
373  if (b == NULL)
374  return false;
375 
376  /* 'a' can't be a subset of 'b' if it contains more words */
377  if (a->nwords > b->nwords)
378  return false;
379 
380  /* Check all 'a' members are set in 'b' */
381  i = 0;
382  do
383  {
384  if ((a->words[i] & ~b->words[i]) != 0)
385  return false;
386  } while (++i < a->nwords);
387  return true;
388 }

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

Referenced by add_child_rel_equivalences(), add_outer_joins_to_relids(), add_paths_to_joinrel(), add_placeholders_to_joinrel(), add_vars_to_targetlist(), build_joinrel_tlist(), check_functional_grouping(), check_index_only(), choose_best_statistics(), clause_sides_match_join(), compute_semijoin_info(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_index_paths(), distribute_qual_to_rels(), eclass_already_used(), eclass_useful_for_merging(), extract_rollup_sets(), final_cost_hashjoin(), finalize_plan(), find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), find_join_domain(), foreign_join_ok(), generate_implied_equalities_for_column(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_parameterized_child_path(), get_cheapest_path_for_pathkeys(), get_join_index_paths(), get_join_variables(), get_joinrel_parampathinfo(), get_switched_clauses(), has_join_restriction(), has_relevant_eclass_joinclause(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), identify_current_nestloop_params(), initial_cost_mergejoin(), innerrel_is_unique(), 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(), search_indexed_tlist_for_phv(), search_indexed_tlist_for_var(), statext_mcv_clauselist_selectivity(), subbuild_joinrel_joinlist(), subbuild_joinrel_restrictlist(), try_partial_nestloop_path(), and use_physical_tlist().

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

Definition at line 1051 of file bitmapset.c.

1052 {
1053  Bitmapset *result;
1054  Bitmapset *other;
1055  int otherlen;
1056  int i;
1057 
1058  /* Handle cases where either input is NULL */
1059  if (a == NULL)
1060  return b;
1061  if (b == NULL)
1062  return a;
1063  /* Identify shorter and longer input; use longer one as result */
1064  if (a->nwords < b->nwords)
1065  {
1066  result = b;
1067  other = a;
1068  }
1069  else
1070  {
1071  result = a;
1072  other = b;
1073  }
1074  /* And union the shorter input into the result */
1075  otherlen = other->nwords;
1076  i = 0;
1077  do
1078  {
1079  result->words[i] |= other->words[i];
1080  } while (++i < otherlen);
1081  if (other != result) /* pure paranoia */
1082  pfree(other);
1083  return result;
1084 }

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

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

◆ bms_make_singleton()

◆ bms_member_index()

int bms_member_index ( Bitmapset a,
int  x 
)

Definition at line 486 of file bitmapset.c.

487 {
488  int i;
489  int bitnum;
490  int wordnum;
491  int result = 0;
492  bitmapword mask;
493 
494  /* return -1 if not a member of the bitmap */
495  if (!bms_is_member(x, a))
496  return -1;
497 
498  wordnum = WORDNUM(x);
499  bitnum = BITNUM(x);
500 
501  /* count bits in preceding words */
502  for (i = 0; i < wordnum; i++)
503  {
504  bitmapword w = a->words[i];
505 
506  /* No need to count the bits in a zero word */
507  if (w != 0)
508  result += bmw_popcount(w);
509  }
510 
511  /*
512  * Now add bits of the last word, but only those before the item. We can
513  * do that by applying a mask and then using popcount again. To get
514  * 0-based index, we want to count only preceding bits, not the item
515  * itself, so we subtract 1.
516  */
517  mask = ((bitmapword) 1 << bitnum) - 1;
518  result += bmw_popcount(a->words[wordnum] & mask);
519 
520  return result;
521 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:460
#define bmw_popcount(w)
Definition: bitmapset.c:66

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

int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1106 of file bitmapset.c.

1107 {
1108  int nwords;
1109  int wordnum;
1110  bitmapword mask;
1111 
1112  if (a == NULL)
1113  return -2;
1114  nwords = a->nwords;
1115  prevbit++;
1116  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1117  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1118  {
1119  bitmapword w = a->words[wordnum];
1120 
1121  /* ignore bits before prevbit */
1122  w &= mask;
1123 
1124  if (w != 0)
1125  {
1126  int result;
1127 
1128  result = wordnum * BITS_PER_BITMAPWORD;
1129  result += bmw_rightmost_one_pos(w);
1130  return result;
1131  }
1132 
1133  /* in subsequent words, consider all bits */
1134  mask = (~(bitmapword) 0);
1135  }
1136  return -2;
1137 }

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

◆ bms_nonempty_difference()

bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 581 of file bitmapset.c.

582 {
583  int i;
584 
585  Assert(a == NULL || a->words[a->nwords - 1] != 0);
586  Assert(b == NULL || b->words[b->nwords - 1] != 0);
587 
588  /* Handle cases where either input is NULL */
589  if (a == NULL)
590  return false;
591  if (b == NULL)
592  return true;
593  /* if 'a' has more words then it must contain additional members */
594  if (a->nwords > b->nwords)
595  return true;
596  /* Check all 'a' members are set in 'b' */
597  i = 0;
598  do
599  {
600  if ((a->words[i] & ~b->words[i]) != 0)
601  return true;
602  } while (++i < a->nwords);
603  return false;
604 }

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

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

◆ bms_num_members()

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 527 of file bitmapset.c.

528 {
529  int shortlen;
530  int i;
531 
532  /* Handle cases where either input is NULL */
533  if (a == NULL || b == NULL)
534  return false;
535  /* Check words in common */
536  shortlen = Min(a->nwords, b->nwords);
537  i = 0;
538  do
539  {
540  if ((a->words[i] & b->words[i]) != 0)
541  return true;
542  } while (++i < shortlen);
543  return false;
544 }

References a, b, i, and Min.

Referenced by add_child_join_rel_equivalences(), add_nulling_relids_mutator(), add_paths_to_joinrel(), adjust_child_relids_multilevel(), allow_star_schema_join(), calc_nestloop_required_outer(), calc_non_nestloop_required_outer(), choose_bitmap_and(), classify_matching_subplans(), compute_semijoin_info(), create_nestloop_path(), distribute_qual_to_rels(), eclass_useful_for_merging(), ExecInitStoredGenerated(), ExecReScanAgg(), ExecReScanAppend(), ExecReScanFunctionScan(), ExecReScanMergeAppend(), ExecUpdateLockMode(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_dependent_generated_columns(), get_joinrel_parampathinfo(), get_useful_ecs_for_relation(), has_join_restriction(), has_legal_joinclause(), has_partition_attrs(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), heap_update(), join_clause_is_movable_into(), join_clause_is_movable_to(), join_is_legal(), join_is_removable(), join_search_one_level(), make_join_rel(), make_outerjoininfo(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo_internal(), mbms_overlap_sets(), partitions_are_ordered(), reduce_outer_joins_pass2(), remove_nulling_relids_mutator(), reparameterize_path_by_child(), select_outer_pathkeys_for_merge(), set_append_rel_size(), subbuild_joinrel_restrictlist(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and try_partitionwise_join().

◆ bms_overlap_list()

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

◆ bms_prev_member()

int bms_prev_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 1165 of file bitmapset.c.

1166 {
1167  int wordnum;
1168  int ushiftbits;
1169  bitmapword mask;
1170 
1171  /*
1172  * If set is NULL or if there are no more bits to the right then we've
1173  * nothing to do.
1174  */
1175  if (a == NULL || prevbit == 0)
1176  return -2;
1177 
1178  /* transform -1 to the highest possible bit we could have set */
1179  if (prevbit == -1)
1180  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1181  else
1182  prevbit--;
1183 
1184  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1185  mask = (~(bitmapword) 0) >> ushiftbits;
1186  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1187  {
1188  bitmapword w = a->words[wordnum];
1189 
1190  /* mask out bits left of prevbit */
1191  w &= mask;
1192 
1193  if (w != 0)
1194  {
1195  int result;
1196 
1197  result = wordnum * BITS_PER_BITMAPWORD;
1198  result += bmw_leftmost_one_pos(w);
1199  return result;
1200  }
1201 
1202  /* in subsequent words, consider all bits */
1203  mask = (~(bitmapword) 0);
1204  }
1205  return -2;
1206 }
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.c:64

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

613 {
614  int result = -1;
615  int nwords;
616  int wordnum;
617 
618  if (a == NULL)
619  elog(ERROR, "bitmapset is empty");
620  nwords = a->nwords;
621  wordnum = 0;
622  do
623  {
624  bitmapword w = a->words[wordnum];
625 
626  if (w != 0)
627  {
628  if (result >= 0 || HAS_MULTIPLE_ONES(w))
629  elog(ERROR, "bitmapset has multiple members");
630  result = wordnum * BITS_PER_BITMAPWORD;
631  result += bmw_rightmost_one_pos(w);
632  }
633  } while (++wordnum < nwords);
634 
635  /* we don't expect non-NULL sets to be empty */
636  Assert(result >= 0);
637  return result;
638 }

References a, Assert(), 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 396 of file bitmapset.c.

397 {
398  BMS_Comparison result;
399  int shortlen;
400  int i;
401 
402  Assert(a == NULL || a->words[a->nwords - 1] != 0);
403  Assert(b == NULL || b->words[b->nwords - 1] != 0);
404 
405  /* Handle cases where either input is NULL */
406  if (a == NULL)
407  {
408  if (b == NULL)
409  return BMS_EQUAL;
410  return BMS_SUBSET1;
411  }
412  if (b == NULL)
413  return BMS_SUBSET2;
414  /* Check common words */
415  result = BMS_EQUAL; /* status so far */
416  shortlen = Min(a->nwords, b->nwords);
417  i = 0;
418  do
419  {
420  bitmapword aword = a->words[i];
421  bitmapword bword = b->words[i];
422 
423  if ((aword & ~bword) != 0)
424  {
425  /* a is not a subset of b */
426  if (result == BMS_SUBSET1)
427  return BMS_DIFFERENT;
428  result = BMS_SUBSET2;
429  }
430  if ((bword & ~aword) != 0)
431  {
432  /* b is not a subset of a */
433  if (result == BMS_SUBSET2)
434  return BMS_DIFFERENT;
435  result = BMS_SUBSET1;
436  }
437  } while (++i < shortlen);
438  /* Check extra words */
439  if (a->nwords > b->nwords)
440  {
441  /* if a has more words then a is not a subset of b */
442  if (result == BMS_SUBSET1)
443  return BMS_DIFFERENT;
444  return BMS_SUBSET2;
445  }
446  else if (a->nwords < b->nwords)
447  {
448  /* if b has more words then b is not a subset of a */
449  if (result == BMS_SUBSET2)
450  return BMS_DIFFERENT;
451  return BMS_SUBSET1;
452  }
453  return result;
454 }

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

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

◆ bms_union()

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

Definition at line 211 of file bitmapset.c.

212 {
213  Bitmapset *result;
214  const Bitmapset *other;
215  int otherlen;
216  int i;
217 
218  /* Handle cases where either input is NULL */
219  if (a == NULL)
220  return bms_copy(b);
221  if (b == NULL)
222  return bms_copy(a);
223  /* Identify shorter and longer input; copy the longer one */
224  if (a->nwords <= b->nwords)
225  {
226  result = bms_copy(b);
227  other = a;
228  }
229  else
230  {
231  result = bms_copy(a);
232  other = b;
233  }
234  /* And union the shorter input into the result */
235  otherlen = other->nwords;
236  i = 0;
237  do
238  {
239  result->words[i] |= other->words[i];
240  } while (++i < otherlen);
241  return result;
242 }

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

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