PostgreSQL Source Code  git master
bitmapset.h File Reference
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
 

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)
 
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)
 
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)
 
uint32 bms_hash_value (const Bitmapset *a)
 

Macro Definition Documentation

◆ BITS_PER_BITMAPWORD

Typedef Documentation

◆ Bitmapset

◆ bitmapword

Definition at line 34 of file bitmapset.h.

◆ signedbitmapword

Definition at line 35 of file bitmapset.h.

Enumeration Type Documentation

◆ BMS_Comparison

Enumerator
BMS_EQUAL 
BMS_SUBSET1 
BMS_SUBSET2 
BMS_DIFFERENT 

Definition at line 45 of file bitmapset.h.

46 {
47  BMS_EQUAL, /* sets are equal */
48  BMS_SUBSET1, /* first set is a subset of the second */
49  BMS_SUBSET2, /* second set is a subset of the first */
50  BMS_DIFFERENT /* neither set is a subset of the other */
BMS_Comparison
Definition: bitmapset.h:45

◆ BMS_Membership

Enumerator
BMS_EMPTY_SET 
BMS_SINGLETON 
BMS_MULTIPLE 

Definition at line 54 of file bitmapset.h.

55 {
56  BMS_EMPTY_SET, /* 0 members */
57  BMS_SINGLETON, /* 1 member */
58  BMS_MULTIPLE /* >1 member */
BMS_Membership
Definition: bitmapset.h:54

Function Documentation

◆ bms_add_member()

Bitmapset* bms_add_member ( Bitmapset a,
int  x 
)

Definition at line 742 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(), 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_unaggregated_cols_walker(), fixup_inherited_columns(), fixup_whole_row_references(), func_get_detail(), 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_row_comparison_op(), make_window_input_target(), makeDependencyGraphWalker(), markRTEForSelectPriv(), offset_relid_set(), preprocess_grouping_sets(), 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().

743 {
744  int wordnum,
745  bitnum;
746 
747  if (x < 0)
748  elog(ERROR, "negative bitmapset member not allowed");
749  if (a == NULL)
750  return bms_make_singleton(x);
751  wordnum = WORDNUM(x);
752  bitnum = BITNUM(x);
753 
754  /* enlarge the set if necessary */
755  if (wordnum >= a->nwords)
756  {
757  int oldnwords = a->nwords;
758  int i;
759 
760  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
761  a->nwords = wordnum + 1;
762  /* zero out the enlarged portion */
763  for (i = oldnwords; i < a->nwords; i++)
764  a->words[i] = 0;
765  }
766 
767  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
768  return a;
769 }
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:223
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:949
int i
#define elog
Definition: elog.h:219

◆ bms_add_members()

Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 799 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(), ExplainPreScanNode(), finalize_plan(), foreign_join_ok(), heap_update(), join_is_legal(), make_outerjoininfo(), pull_varnos_walker(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), transformOnConflictArbiter(), and update_placeholder_eval_levels().

800 {
801  Bitmapset *result;
802  const Bitmapset *other;
803  int otherlen;
804  int i;
805 
806  /* Handle cases where either input is NULL */
807  if (a == NULL)
808  return bms_copy(b);
809  if (b == NULL)
810  return a;
811  /* Identify shorter and longer input; copy the longer one if needed */
812  if (a->nwords < b->nwords)
813  {
814  result = bms_copy(b);
815  other = a;
816  }
817  else
818  {
819  result = a;
820  other = b;
821  }
822  /* And union the shorter input into the result */
823  otherlen = other->nwords;
824  for (i = 0; i < otherlen; i++)
825  result->words[i] |= other->words[i];
826  if (result != a)
827  pfree(a);
828  return result;
829 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
void pfree(void *pointer)
Definition: mcxt.c:936
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 840 of file bitmapset.c.

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

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

◆ bms_compare()

int bms_compare ( const Bitmapset a,
const Bitmapset b 
)

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

185 {
186  int shortlen;
187  int i;
188 
189  /* Handle cases where either input is NULL */
190  if (a == NULL)
191  return bms_is_empty(b) ? 0 : -1;
192  else if (b == NULL)
193  return bms_is_empty(a) ? 0 : +1;
194  /* Handle cases where one input is longer than the other */
195  shortlen = Min(a->nwords, b->nwords);
196  for (i = shortlen; i < a->nwords; i++)
197  {
198  if (a->words[i] != 0)
199  return +1;
200  }
201  for (i = shortlen; i < b->nwords; i++)
202  {
203  if (b->words[i] != 0)
204  return -1;
205  }
206  /* Process words in common */
207  i = shortlen;
208  while (--i >= 0)
209  {
210  bitmapword aw = a->words[i];
211  bitmapword bw = b->words[i];
212 
213  if (aw != bw)
214  return (aw > bw) ? +1 : -1;
215  }
216  return 0;
217 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
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:707
int i

◆ bms_copy()

Bitmapset* bms_copy ( const Bitmapset a)

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 779 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(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_query(), substitute_multiple_relids_walker(), and TopologicalSort().

780 {
781  int wordnum,
782  bitnum;
783 
784  if (x < 0)
785  elog(ERROR, "negative bitmapset member not allowed");
786  if (a == NULL)
787  return NULL;
788  wordnum = WORDNUM(x);
789  bitnum = BITNUM(x);
790  if (wordnum < a->nwords)
791  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
792  return a;
793 }
#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 933 of file bitmapset.c.

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

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

934 {
935  int shortlen;
936  int i;
937 
938  /* Handle cases where either input is NULL */
939  if (a == NULL)
940  return NULL;
941  if (b == NULL)
942  return a;
943  /* Remove b's bits from a; we need never copy */
944  shortlen = Min(a->nwords, b->nwords);
945  for (i = 0; i < shortlen; i++)
946  a->words[i] &= ~b->words[i];
947  return a;
948 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
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 328 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().

329 {
330  Bitmapset *result;
331  int shortlen;
332  int i;
333 
334  /* Handle cases where either input is NULL */
335  if (a == NULL)
336  return NULL;
337  if (b == NULL)
338  return bms_copy(a);
339  /* Copy the left input */
340  result = bms_copy(a);
341  /* And remove b's bits from result */
342  shortlen = Min(a->nwords, b->nwords);
343  for (i = 0; i < shortlen; i++)
344  result->words[i] &= ~b->words[i];
345  return result;
346 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
#define Min(x, y)
Definition: c.h:846
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 131 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(), join_is_removable(), make_one_rel(), match_pathkeys_to_index(), populate_joinrel_with_paths(), remove_rel_from_query(), and try_partitionwise_join().

132 {
133  const Bitmapset *shorter;
134  const Bitmapset *longer;
135  int shortlen;
136  int longlen;
137  int i;
138 
139  /* Handle cases where either input is NULL */
140  if (a == NULL)
141  {
142  if (b == NULL)
143  return true;
144  return bms_is_empty(b);
145  }
146  else if (b == NULL)
147  return bms_is_empty(a);
148  /* Identify shorter and longer input */
149  if (a->nwords <= b->nwords)
150  {
151  shorter = a;
152  longer = b;
153  }
154  else
155  {
156  shorter = b;
157  longer = a;
158  }
159  /* And process */
160  shortlen = shorter->nwords;
161  for (i = 0; i < shortlen; i++)
162  {
163  if (shorter->words[i] != longer->words[i])
164  return false;
165  }
166  longlen = longer->nwords;
167  for (; i < longlen; i++)
168  {
169  if (longer->words[i] != 0)
170  return false;
171  }
172  return true;
173 }
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:707
int i

◆ bms_first_member()

int bms_first_member ( Bitmapset a)

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

1002 {
1003  int nwords;
1004  int wordnum;
1005 
1006  if (a == NULL)
1007  return -1;
1008  nwords = a->nwords;
1009  for (wordnum = 0; wordnum < nwords; wordnum++)
1010  {
1011  bitmapword w = a->words[wordnum];
1012 
1013  if (w != 0)
1014  {
1015  int result;
1016 
1017  w = RIGHTMOST_ONE(w);
1018  a->words[wordnum] &= ~w;
1019 
1020  result = wordnum * BITS_PER_BITMAPWORD;
1021  while ((w & 255) == 0)
1022  {
1023  w >>= 8;
1024  result += 8;
1025  }
1026  result += rightmost_one_pos[w & 255];
1027  return result;
1028  }
1029  }
1030  return -1;
1031 }
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:68
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 613 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().

614 {
615  int result = -1;
616  int nwords;
617  int wordnum;
618 
619  if (a == NULL)
620  return false;
621  nwords = a->nwords;
622  for (wordnum = 0; wordnum < nwords; wordnum++)
623  {
624  bitmapword w = a->words[wordnum];
625 
626  if (w != 0)
627  {
628  if (result >= 0 || HAS_MULTIPLE_ONES(w))
629  return false;
630  result = wordnum * BITS_PER_BITMAPWORD;
631  while ((w & 255) == 0)
632  {
633  w >>= 8;
634  result += 8;
635  }
636  result += rightmost_one_pos[w & 255];
637  }
638  }
639  if (result < 0)
640  return false;
641  *member = result;
642  return true;
643 }
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
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:68
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40

◆ bms_hash_value()

uint32 bms_hash_value ( const Bitmapset a)

Definition at line 1100 of file bitmapset.c.

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

Referenced by bitmap_hash().

1101 {
1102  int lastword;
1103 
1104  if (a == NULL)
1105  return 0; /* All empty sets hash to 0 */
1106  for (lastword = a->nwords; --lastword >= 0;)
1107  {
1108  if (a->words[lastword] != 0)
1109  break;
1110  }
1111  if (lastword < 0)
1112  return 0; /* All empty sets hash to 0 */
1113  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1114  (lastword + 1) * sizeof(bitmapword)));
1115 }
#define DatumGetUInt32(X)
Definition: postgres.h:469
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 907 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(), pull_varnos_walker(), and relation_is_updatable().

908 {
909  int shortlen;
910  int i;
911 
912  /* Handle cases where either input is NULL */
913  if (a == NULL)
914  return NULL;
915  if (b == NULL)
916  {
917  pfree(a);
918  return NULL;
919  }
920  /* Intersect b into a; we need never copy */
921  shortlen = Min(a->nwords, b->nwords);
922  for (i = 0; i < shortlen; i++)
923  a->words[i] &= b->words[i];
924  for (; i < a->nwords; i++)
925  a->words[i] = 0;
926  return a;
927 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
void pfree(void *pointer)
Definition: mcxt.c:936
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 296 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().

297 {
298  Bitmapset *result;
299  const Bitmapset *other;
300  int resultlen;
301  int i;
302 
303  /* Handle cases where either input is NULL */
304  if (a == NULL || b == NULL)
305  return NULL;
306  /* Identify shorter and longer input; copy the shorter one */
307  if (a->nwords <= b->nwords)
308  {
309  result = bms_copy(a);
310  other = b;
311  }
312  else
313  {
314  result = bms_copy(b);
315  other = a;
316  }
317  /* And intersect the longer input with the result */
318  resultlen = result->nwords;
319  for (i = 0; i < resultlen; i++)
320  result->words[i] &= other->words[i];
321  return result;
322 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_is_empty()

bool bms_is_empty ( const Bitmapset a)

Definition at line 707 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(), ExecInitParallelPlan(), ExecParallelReinitialize(), ExecReScanSetParamPlan(), finalize_plan(), find_nonnullable_rels_walker(), find_placeholder_info(), find_single_rel_for_clauses(), generate_join_implied_equalities_for_ecs(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parallel_safe_total_inner(), get_joinrel_parampathinfo(), 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(), relation_has_unique_index_for(), relation_is_updatable(), remove_rel_from_query(), rewriteTargetView(), sepgsql_dml_privileges(), sort_inner_and_outer(), TopologicalSort(), try_partial_hashjoin_path(), try_partial_mergejoin_path(), try_partial_nestloop_path(), UpdateChangedParamSet(), and use_physical_tlist().

708 {
709  int nwords;
710  int wordnum;
711 
712  if (a == NULL)
713  return true;
714  nwords = a->nwords;
715  for (wordnum = 0; wordnum < nwords; wordnum++)
716  {
717  bitmapword w = a->words[wordnum];
718 
719  if (w != 0)
720  return false;
721  }
722  return true;
723 }
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 464 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(), ExecInitModifyTable(), ExplainSubPlans(), find_appinfos_by_relids(), find_hash_columns(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), get_foreign_key_join_selectivity(), get_partitioned_child_rels_for_join(), 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(), match_clause_to_indexcol(), match_rowcompare_to_indexcol(), plpgsql_param_fetch(), prepare_projection_slot(), preprocess_rowmarks(), process_subquery_nestloop_params(), pullup_replace_vars_callback(), remove_rel_from_query(), remove_unused_subquery_outputs(), remove_useless_groupby_columns(), replace_nestloop_params_mutator(), set_join_column_names(), set_rtable_names(), substitute_multiple_relids_walker(), tfuncLoadRows(), transformGroupClauseExpr(), translate_col_privs(), TriggerEnabled(), use_physical_tlist(), and view_cols_are_auto_updatable().

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

353 {
354  int shortlen;
355  int longlen;
356  int i;
357 
358  /* Handle cases where either input is NULL */
359  if (a == NULL)
360  return true; /* empty set is a subset of anything */
361  if (b == NULL)
362  return bms_is_empty(a);
363  /* Check common words */
364  shortlen = Min(a->nwords, b->nwords);
365  for (i = 0; i < shortlen; i++)
366  {
367  if ((a->words[i] & ~b->words[i]) != 0)
368  return false;
369  }
370  /* Check extra words */
371  if (a->nwords > b->nwords)
372  {
373  longlen = a->nwords;
374  for (; i < longlen; i++)
375  {
376  if (a->words[i] != 0)
377  return false;
378  }
379  }
380  return true;
381 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:707
int i

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

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

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

◆ bms_make_singleton()

Bitmapset* bms_make_singleton ( int  x)

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

224 {
225  Bitmapset *result;
226  int wordnum,
227  bitnum;
228 
229  if (x < 0)
230  elog(ERROR, "negative bitmapset member not allowed");
231  wordnum = WORDNUM(x);
232  bitnum = BITNUM(x);
233  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
234  result->nwords = wordnum + 1;
235  result->words[wordnum] = ((bitmapword) 1 << bitnum);
236  return result;
237 }
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:864
#define elog
Definition: elog.h:219

◆ bms_membership()

BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 678 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_tablesample_rel_pathlist(), and treat_as_join_clause().

679 {
680  BMS_Membership result = BMS_EMPTY_SET;
681  int nwords;
682  int wordnum;
683 
684  if (a == NULL)
685  return BMS_EMPTY_SET;
686  nwords = a->nwords;
687  for (wordnum = 0; wordnum < nwords; wordnum++)
688  {
689  bitmapword w = a->words[wordnum];
690 
691  if (w != 0)
692  {
693  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
694  return BMS_MULTIPLE;
695  result = BMS_SINGLETON;
696  }
697  }
698  return result;
699 }
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 1053 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(), adjust_view_column_set(), alias_relid_set(), approximate_joinrel_size(), create_lateral_join_info(), deparseLockingClause(), dependency_degree(), EstimateParamExecSpace(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecEvalParamExecParams(), ExecInitAgg(), ExecScanReScan(), fixup_inherited_columns(), format_expr_params(), generate_partitionwise_join_paths(), get_loop_count(), logicalrep_rel_open(), lookup_var_attr_stats(), offset_relid_set(), outBitmapset(), pg_ndistinct_out(), postgresBeginForeignScan(), postgresPlanDirectModify(), postgresPlanForeignModify(), remove_join_clause_from_rels(), SerializeParamExecParams(), set_customscan_references(), set_foreignscan_references(), show_eval_params(), statext_dependencies_build(), and statext_ndistinct_serialize().

1054 {
1055  int nwords;
1056  int wordnum;
1057  bitmapword mask;
1058 
1059  if (a == NULL)
1060  return -2;
1061  nwords = a->nwords;
1062  prevbit++;
1063  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1064  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1065  {
1066  bitmapword w = a->words[wordnum];
1067 
1068  /* ignore bits before prevbit */
1069  w &= mask;
1070 
1071  if (w != 0)
1072  {
1073  int result;
1074 
1075  result = wordnum * BITS_PER_BITMAPWORD;
1076  while ((w & 255) == 0)
1077  {
1078  w >>= 8;
1079  result += 8;
1080  }
1081  result += rightmost_one_pos[w & 255];
1082  return result;
1083  }
1084 
1085  /* in subsequent words, consider all bits */
1086  mask = (~(bitmapword) 0);
1087  }
1088  return -2;
1089 }
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:68
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 538 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().

539 {
540  int shortlen;
541  int i;
542 
543  /* Handle cases where either input is NULL */
544  if (a == NULL)
545  return false;
546  if (b == NULL)
547  return !bms_is_empty(a);
548  /* Check words in common */
549  shortlen = Min(a->nwords, b->nwords);
550  for (i = 0; i < shortlen; i++)
551  {
552  if ((a->words[i] & ~b->words[i]) != 0)
553  return true;
554  }
555  /* Check extra words in a */
556  for (; i < a->nwords; i++)
557  {
558  if (a->words[i] != 0)
559  return true;
560  }
561  return false;
562 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:707
int i

◆ bms_num_members()

int bms_num_members ( const Bitmapset a)

Definition at line 649 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(), find_appinfos_by_relids(), find_hash_columns(), find_strongest_dependency(), lookup_var_attr_stats(), NumRelids(), SerializeParamExecParams(), statext_dependencies_build(), statext_ndistinct_build(), and statext_ndistinct_serialize().

650 {
651  int result = 0;
652  int nwords;
653  int wordnum;
654 
655  if (a == NULL)
656  return 0;
657  nwords = a->nwords;
658  for (wordnum = 0; wordnum < nwords; wordnum++)
659  {
660  bitmapword w = a->words[wordnum];
661 
662  /* we assume here that bitmapword is an unsigned type */
663  while (w != 0)
664  {
665  result += number_of_ones[w & 255];
666  w >>= 8;
667  }
668  }
669  return result;
670 }
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:87

◆ bms_overlap()

bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

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

488 {
489  int shortlen;
490  int i;
491 
492  /* Handle cases where either input is NULL */
493  if (a == NULL || b == NULL)
494  return false;
495  /* Check words in common */
496  shortlen = Min(a->nwords, b->nwords);
497  for (i = 0; i < shortlen; i++)
498  {
499  if ((a->words[i] & b->words[i]) != 0)
500  return true;
501  }
502  return false;
503 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_overlap_list()

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

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

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

571 {
572  int result = -1;
573  int nwords;
574  int wordnum;
575 
576  if (a == NULL)
577  elog(ERROR, "bitmapset is empty");
578  nwords = a->nwords;
579  for (wordnum = 0; wordnum < nwords; wordnum++)
580  {
581  bitmapword w = a->words[wordnum];
582 
583  if (w != 0)
584  {
585  if (result >= 0 || HAS_MULTIPLE_ONES(w))
586  elog(ERROR, "bitmapset has multiple members");
587  result = wordnum * BITS_PER_BITMAPWORD;
588  while ((w & 255) == 0)
589  {
590  w >>= 8;
591  result += 8;
592  }
593  result += rightmost_one_pos[w & 255];
594  }
595  }
596  if (result < 0)
597  elog(ERROR, "bitmapset is empty");
598  return result;
599 }
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:68
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 389 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().

390 {
391  BMS_Comparison result;
392  int shortlen;
393  int longlen;
394  int i;
395 
396  /* Handle cases where either input is NULL */
397  if (a == NULL)
398  {
399  if (b == NULL)
400  return BMS_EQUAL;
401  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
402  }
403  if (b == NULL)
404  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
405  /* Check common words */
406  result = BMS_EQUAL; /* status so far */
407  shortlen = Min(a->nwords, b->nwords);
408  for (i = 0; i < shortlen; i++)
409  {
410  bitmapword aword = a->words[i];
411  bitmapword bword = b->words[i];
412 
413  if ((aword & ~bword) != 0)
414  {
415  /* a is not a subset of b */
416  if (result == BMS_SUBSET1)
417  return BMS_DIFFERENT;
418  result = BMS_SUBSET2;
419  }
420  if ((bword & ~aword) != 0)
421  {
422  /* b is not a subset of a */
423  if (result == BMS_SUBSET2)
424  return BMS_DIFFERENT;
425  result = BMS_SUBSET1;
426  }
427  }
428  /* Check extra words */
429  if (a->nwords > b->nwords)
430  {
431  longlen = a->nwords;
432  for (; i < longlen; i++)
433  {
434  if (a->words[i] != 0)
435  {
436  /* a is not a subset of b */
437  if (result == BMS_SUBSET1)
438  return BMS_DIFFERENT;
439  result = BMS_SUBSET2;
440  }
441  }
442  }
443  else if (a->nwords < b->nwords)
444  {
445  longlen = b->nwords;
446  for (; i < longlen; i++)
447  {
448  if (b->words[i] != 0)
449  {
450  /* b is not a subset of a */
451  if (result == BMS_SUBSET2)
452  return BMS_DIFFERENT;
453  result = BMS_SUBSET1;
454  }
455  }
456  }
457  return result;
458 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:846
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:707
int i
BMS_Comparison
Definition: bitmapset.h:45

◆ bms_union()

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

Definition at line 262 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(), ExecWithCheckOptions(), finalize_plan(), foreign_join_ok(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), generate_join_implied_equalities_for_ecs(), 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().

263 {
264  Bitmapset *result;
265  const Bitmapset *other;
266  int otherlen;
267  int i;
268 
269  /* Handle cases where either input is NULL */
270  if (a == NULL)
271  return bms_copy(b);
272  if (b == NULL)
273  return bms_copy(a);
274  /* Identify shorter and longer input; copy the longer one */
275  if (a->nwords <= b->nwords)
276  {
277  result = bms_copy(b);
278  other = a;
279  }
280  else
281  {
282  result = bms_copy(a);
283  other = b;
284  }
285  /* And union the shorter input into the result */
286  otherlen = other->nwords;
287  for (i = 0; i < otherlen; i++)
288  result->words[i] |= other->words[i];
289  return result;
290 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i