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

Go to the source code of this file.

Macros

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

Functions

Bitmapsetbms_copy (const Bitmapset *a)
 
bool bms_equal (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_make_singleton (int x)
 
void bms_free (Bitmapset *a)
 
Bitmapsetbms_union (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_intersect (const Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_difference (const Bitmapset *a, const Bitmapset *b)
 
bool bms_is_subset (const Bitmapset *a, const Bitmapset *b)
 
BMS_Comparison bms_subset_compare (const Bitmapset *a, const Bitmapset *b)
 
bool bms_is_member (int x, const Bitmapset *a)
 
bool bms_overlap (const Bitmapset *a, const Bitmapset *b)
 
bool bms_overlap_list (const Bitmapset *a, const List *b)
 
bool bms_nonempty_difference (const Bitmapset *a, const Bitmapset *b)
 
int bms_singleton_member (const Bitmapset *a)
 
bool bms_get_singleton_member (const Bitmapset *a, int *member)
 
int bms_num_members (const Bitmapset *a)
 
BMS_Membership bms_membership (const Bitmapset *a)
 
bool bms_is_empty (const Bitmapset *a)
 
Bitmapsetbms_add_member (Bitmapset *a, int x)
 
Bitmapsetbms_del_member (Bitmapset *a, int x)
 
Bitmapsetbms_add_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_add_range (Bitmapset *a, int lower, int upper)
 
Bitmapsetbms_int_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_del_members (Bitmapset *a, const Bitmapset *b)
 
Bitmapsetbms_join (Bitmapset *a, Bitmapset *b)
 
int bms_first_member (Bitmapset *a)
 
int bms_next_member (const Bitmapset *a, int prevbit)
 
uint32 bms_hash_value (const Bitmapset *a)
 

Variables

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

Macro Definition Documentation

◆ BITMAPSET_SIZE

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

Definition at line 30 of file bitmapset.c.

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

◆ BITNUM

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

◆ HAS_MULTIPLE_ONES

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

Definition at line 52 of file bitmapset.c.

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

◆ RIGHTMOST_ONE

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

Definition at line 50 of file bitmapset.c.

Referenced by bms_first_member().

◆ WORDNUM

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

Function Documentation

◆ bms_add_member()

Bitmapset* bms_add_member ( Bitmapset a,
int  x 
)

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

699 {
700  int wordnum,
701  bitnum;
702 
703  if (x < 0)
704  elog(ERROR, "negative bitmapset member not allowed");
705  if (a == NULL)
706  return bms_make_singleton(x);
707  wordnum = WORDNUM(x);
708  bitnum = BITNUM(x);
709 
710  /* enlarge the set if necessary */
711  if (wordnum >= a->nwords)
712  {
713  int oldnwords = a->nwords;
714  int i;
715 
716  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
717  a->nwords = wordnum + 1;
718  /* zero out the enlarged portion */
719  for (i = oldnwords; i < a->nwords; i++)
720  a->words[i] = 0;
721  }
722 
723  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
724  return a;
725 }
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:179
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 755 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().

756 {
757  Bitmapset *result;
758  const Bitmapset *other;
759  int otherlen;
760  int i;
761 
762  /* Handle cases where either input is NULL */
763  if (a == NULL)
764  return bms_copy(b);
765  if (b == NULL)
766  return a;
767  /* Identify shorter and longer input; copy the longer one if needed */
768  if (a->nwords < b->nwords)
769  {
770  result = bms_copy(b);
771  other = a;
772  }
773  else
774  {
775  result = a;
776  other = b;
777  }
778  /* And union the shorter input into the result */
779  otherlen = other->nwords;
780  for (i = 0; i < otherlen; i++)
781  result->words[i] |= other->words[i];
782  if (result != a)
783  pfree(a);
784  return result;
785 }
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 796 of file bitmapset.c.

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

797 {
798  int lwordnum,
799  lbitnum,
800  uwordnum,
801  ushiftbits,
802  wordnum;
803 
804  if (lower < 0 || upper < 0)
805  elog(ERROR, "negative bitmapset member not allowed");
806  if (lower > upper)
807  elog(ERROR, "lower range must not be above upper range");
808  uwordnum = WORDNUM(upper);
809 
810  if (a == NULL)
811  {
812  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
813  a->nwords = uwordnum + 1;
814  }
815 
816  /* ensure we have enough words to store the upper bit */
817  else if (uwordnum >= a->nwords)
818  {
819  int oldnwords = a->nwords;
820  int i;
821 
822  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
823  a->nwords = uwordnum + 1;
824  /* zero out the enlarged portion */
825  for (i = oldnwords; i < a->nwords; i++)
826  a->words[i] = 0;
827  }
828 
829  wordnum = lwordnum = WORDNUM(lower);
830 
831  lbitnum = BITNUM(lower);
832  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
833 
834  /*
835  * Special case when lwordnum is the same as uwordnum we must perform the
836  * upper and lower masking on the word.
837  */
838  if (lwordnum == uwordnum)
839  {
840  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
841  & (~(bitmapword) 0) >> ushiftbits;
842  }
843  else
844  {
845  /* turn on lbitnum and all bits left of it */
846  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
847 
848  /* turn on all bits for any intermediate words */
849  while (wordnum < uwordnum)
850  a->words[wordnum++] = ~(bitmapword) 0;
851 
852  /* turn on upper's bit and all bits right of it. */
853  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
854  }
855 
856  return a;
857 }
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_copy()

Bitmapset* bms_copy ( const Bitmapset a)

◆ bms_del_member()

Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

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

736 {
737  int wordnum,
738  bitnum;
739 
740  if (x < 0)
741  elog(ERROR, "negative bitmapset member not allowed");
742  if (a == NULL)
743  return NULL;
744  wordnum = WORDNUM(x);
745  bitnum = BITNUM(x);
746  if (wordnum < a->nwords)
747  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
748  return a;
749 }
#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 889 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().

890 {
891  int shortlen;
892  int i;
893 
894  /* Handle cases where either input is NULL */
895  if (a == NULL)
896  return NULL;
897  if (b == NULL)
898  return a;
899  /* Remove b's bits from a; we need never copy */
900  shortlen = Min(a->nwords, b->nwords);
901  for (i = 0; i < shortlen; i++)
902  a->words[i] &= ~b->words[i];
903  return a;
904 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
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 284 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().

285 {
286  Bitmapset *result;
287  int shortlen;
288  int i;
289 
290  /* Handle cases where either input is NULL */
291  if (a == NULL)
292  return NULL;
293  if (b == NULL)
294  return bms_copy(a);
295  /* Copy the left input */
296  result = bms_copy(a);
297  /* And remove b's bits from result */
298  shortlen = Min(a->nwords, b->nwords);
299  for (i = 0; i < shortlen; i++)
300  result->words[i] &= ~b->words[i];
301  return result;
302 }
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
#define Min(x, y)
Definition: c.h:812
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_partition_wise_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:663
int i

◆ bms_first_member()

int bms_first_member ( Bitmapset a)

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

958 {
959  int nwords;
960  int wordnum;
961 
962  if (a == NULL)
963  return -1;
964  nwords = a->nwords;
965  for (wordnum = 0; wordnum < nwords; wordnum++)
966  {
967  bitmapword w = a->words[wordnum];
968 
969  if (w != 0)
970  {
971  int result;
972 
973  w = RIGHTMOST_ONE(w);
974  a->words[wordnum] &= ~w;
975 
976  result = wordnum * BITS_PER_BITMAPWORD;
977  while ((w & 255) == 0)
978  {
979  w >>= 8;
980  result += 8;
981  }
982  result += rightmost_one_pos[w & 255];
983  return result;
984  }
985  }
986  return -1;
987 }
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 569 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().

570 {
571  int result = -1;
572  int nwords;
573  int wordnum;
574 
575  if (a == NULL)
576  return false;
577  nwords = a->nwords;
578  for (wordnum = 0; wordnum < nwords; wordnum++)
579  {
580  bitmapword w = a->words[wordnum];
581 
582  if (w != 0)
583  {
584  if (result >= 0 || HAS_MULTIPLE_ONES(w))
585  return false;
586  result = wordnum * BITS_PER_BITMAPWORD;
587  while ((w & 255) == 0)
588  {
589  w >>= 8;
590  result += 8;
591  }
592  result += rightmost_one_pos[w & 255];
593  }
594  }
595  if (result < 0)
596  return false;
597  *member = result;
598  return true;
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
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 1056 of file bitmapset.c.

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

Referenced by bitmap_hash().

1057 {
1058  int lastword;
1059 
1060  if (a == NULL)
1061  return 0; /* All empty sets hash to 0 */
1062  for (lastword = a->nwords; --lastword >= 0;)
1063  {
1064  if (a->words[lastword] != 0)
1065  break;
1066  }
1067  if (lastword < 0)
1068  return 0; /* All empty sets hash to 0 */
1069  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1070  (lastword + 1) * sizeof(bitmapword)));
1071 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
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 863 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().

864 {
865  int shortlen;
866  int i;
867 
868  /* Handle cases where either input is NULL */
869  if (a == NULL)
870  return NULL;
871  if (b == NULL)
872  {
873  pfree(a);
874  return NULL;
875  }
876  /* Intersect b into a; we need never copy */
877  shortlen = Min(a->nwords, b->nwords);
878  for (i = 0; i < shortlen; i++)
879  a->words[i] &= b->words[i];
880  for (; i < a->nwords; i++)
881  a->words[i] = 0;
882  return a;
883 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
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 252 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().

253 {
254  Bitmapset *result;
255  const Bitmapset *other;
256  int resultlen;
257  int i;
258 
259  /* Handle cases where either input is NULL */
260  if (a == NULL || b == NULL)
261  return NULL;
262  /* Identify shorter and longer input; copy the shorter one */
263  if (a->nwords <= b->nwords)
264  {
265  result = bms_copy(a);
266  other = b;
267  }
268  else
269  {
270  result = bms_copy(b);
271  other = a;
272  }
273  /* And intersect the longer input with the result */
274  resultlen = result->nwords;
275  for (i = 0; i < resultlen; i++)
276  result->words[i] &= other->words[i];
277  return result;
278 }
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 663 of file bitmapset.c.

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

Referenced by add_eq_member(), add_vars_to_targetlist(), 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().

664 {
665  int nwords;
666  int wordnum;
667 
668  if (a == NULL)
669  return true;
670  nwords = a->nwords;
671  for (wordnum = 0; wordnum < nwords; wordnum++)
672  {
673  bitmapword w = a->words[wordnum];
674 
675  if (w != 0)
676  return false;
677  }
678  return true;
679 }
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 420 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(), copyParamList(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_plan(), DefineIndex(), deparseLockingClause(), deparseTargetList(), deparseVar(), dependencies_clauselist_selectivity(), dependency_is_fully_matched(), do_analyze_rel(), enum_known_sorted(), estimate_multivariate_ndistinct(), EstimateParamListSpace(), 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(), inheritance_planner(), InitPlan(), is_partition_attr(), 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(), SerializeParamList(), 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().

421 {
422  int wordnum,
423  bitnum;
424 
425  /* XXX better to just return false for x<0 ? */
426  if (x < 0)
427  elog(ERROR, "negative bitmapset member not allowed");
428  if (a == NULL)
429  return false;
430  wordnum = WORDNUM(x);
431  bitnum = BITNUM(x);
432  if (wordnum >= a->nwords)
433  return false;
434  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
435  return true;
436  return false;
437 }
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 308 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().

309 {
310  int shortlen;
311  int longlen;
312  int i;
313 
314  /* Handle cases where either input is NULL */
315  if (a == NULL)
316  return true; /* empty set is a subset of anything */
317  if (b == NULL)
318  return bms_is_empty(a);
319  /* Check common words */
320  shortlen = Min(a->nwords, b->nwords);
321  for (i = 0; i < shortlen; i++)
322  {
323  if ((a->words[i] & ~b->words[i]) != 0)
324  return false;
325  }
326  /* Check extra words */
327  if (a->nwords > b->nwords)
328  {
329  longlen = a->nwords;
330  for (; i < longlen; i++)
331  {
332  if (a->words[i] != 0)
333  return false;
334  }
335  }
336  return true;
337 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
int i

◆ bms_join()

Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

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

911 {
912  Bitmapset *result;
913  Bitmapset *other;
914  int otherlen;
915  int i;
916 
917  /* Handle cases where either input is NULL */
918  if (a == NULL)
919  return b;
920  if (b == NULL)
921  return a;
922  /* Identify shorter and longer input; use longer one as result */
923  if (a->nwords < b->nwords)
924  {
925  result = b;
926  other = a;
927  }
928  else
929  {
930  result = a;
931  other = b;
932  }
933  /* And union the shorter input into the result */
934  otherlen = other->nwords;
935  for (i = 0; i < otherlen; i++)
936  result->words[i] |= other->words[i];
937  if (other != result) /* pure paranoia */
938  pfree(other);
939  return result;
940 }
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 179 of file bitmapset.c.

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

Referenced by 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().

180 {
181  Bitmapset *result;
182  int wordnum,
183  bitnum;
184 
185  if (x < 0)
186  elog(ERROR, "negative bitmapset member not allowed");
187  wordnum = WORDNUM(x);
188  bitnum = BITNUM(x);
189  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
190  result->nwords = wordnum + 1;
191  result->words[wordnum] = ((bitmapword) 1 << bitnum);
192  return result;
193 }
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 634 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().

635 {
636  BMS_Membership result = BMS_EMPTY_SET;
637  int nwords;
638  int wordnum;
639 
640  if (a == NULL)
641  return BMS_EMPTY_SET;
642  nwords = a->nwords;
643  for (wordnum = 0; wordnum < nwords; wordnum++)
644  {
645  bitmapword w = a->words[wordnum];
646 
647  if (w != 0)
648  {
649  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
650  return BMS_MULTIPLE;
651  result = BMS_SINGLETON;
652  }
653  }
654  return result;
655 }
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 1009 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_partition_wise_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(), setup_param_list(), setup_unshared_param_list(), show_eval_params(), statext_dependencies_build(), and statext_ndistinct_serialize().

1010 {
1011  int nwords;
1012  int wordnum;
1013  bitmapword mask;
1014 
1015  if (a == NULL)
1016  return -2;
1017  nwords = a->nwords;
1018  prevbit++;
1019  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1020  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1021  {
1022  bitmapword w = a->words[wordnum];
1023 
1024  /* ignore bits before prevbit */
1025  w &= mask;
1026 
1027  if (w != 0)
1028  {
1029  int result;
1030 
1031  result = wordnum * BITS_PER_BITMAPWORD;
1032  while ((w & 255) == 0)
1033  {
1034  w >>= 8;
1035  result += 8;
1036  }
1037  result += rightmost_one_pos[w & 255];
1038  return result;
1039  }
1040 
1041  /* in subsequent words, consider all bits */
1042  mask = (~(bitmapword) 0);
1043  }
1044  return -2;
1045 }
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 494 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().

495 {
496  int shortlen;
497  int i;
498 
499  /* Handle cases where either input is NULL */
500  if (a == NULL)
501  return false;
502  if (b == NULL)
503  return !bms_is_empty(a);
504  /* Check words in common */
505  shortlen = Min(a->nwords, b->nwords);
506  for (i = 0; i < shortlen; i++)
507  {
508  if ((a->words[i] & ~b->words[i]) != 0)
509  return true;
510  }
511  /* Check extra words in a */
512  for (; i < a->nwords; i++)
513  {
514  if (a->words[i] != 0)
515  return true;
516  }
517  return false;
518 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
int i

◆ bms_num_members()

int bms_num_members ( const Bitmapset a)

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

606 {
607  int result = 0;
608  int nwords;
609  int wordnum;
610 
611  if (a == NULL)
612  return 0;
613  nwords = a->nwords;
614  for (wordnum = 0; wordnum < nwords; wordnum++)
615  {
616  bitmapword w = a->words[wordnum];
617 
618  /* we assume here that bitmapword is an unsigned type */
619  while (w != 0)
620  {
621  result += number_of_ones[w & 255];
622  w >>= 8;
623  }
624  }
625  return result;
626 }
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 443 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_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_partition_wise_join(), and update_placeholder_eval_levels().

444 {
445  int shortlen;
446  int i;
447 
448  /* Handle cases where either input is NULL */
449  if (a == NULL || b == NULL)
450  return false;
451  /* Check words in common */
452  shortlen = Min(a->nwords, b->nwords);
453  for (i = 0; i < shortlen; i++)
454  {
455  if ((a->words[i] & b->words[i]) != 0)
456  return true;
457  }
458  return false;
459 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i

◆ bms_overlap_list()

bool bms_overlap_list ( const Bitmapset a,
const List b 
)

Definition at line 465 of file bitmapset.c.

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

Referenced by preprocess_grouping_sets().

466 {
467  ListCell *lc;
468  int wordnum,
469  bitnum;
470 
471  if (a == NULL || b == NIL)
472  return false;
473 
474  foreach(lc, b)
475  {
476  int x = lfirst_int(lc);
477 
478  if (x < 0)
479  elog(ERROR, "negative bitmapset member not allowed");
480  wordnum = WORDNUM(x);
481  bitnum = BITNUM(x);
482  if (wordnum < a->nwords)
483  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
484  return true;
485  }
486 
487  return false;
488 }
#define NIL
Definition: pg_list.h:69
#define WORDNUM(x)
Definition: bitmapset.c:27
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:107
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
#define elog
Definition: elog.h:219

◆ bms_singleton_member()

int bms_singleton_member ( const Bitmapset a)

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

527 {
528  int result = -1;
529  int nwords;
530  int wordnum;
531 
532  if (a == NULL)
533  elog(ERROR, "bitmapset is empty");
534  nwords = a->nwords;
535  for (wordnum = 0; wordnum < nwords; wordnum++)
536  {
537  bitmapword w = a->words[wordnum];
538 
539  if (w != 0)
540  {
541  if (result >= 0 || HAS_MULTIPLE_ONES(w))
542  elog(ERROR, "bitmapset has multiple members");
543  result = wordnum * BITS_PER_BITMAPWORD;
544  while ((w & 255) == 0)
545  {
546  w >>= 8;
547  result += 8;
548  }
549  result += rightmost_one_pos[w & 255];
550  }
551  }
552  if (result < 0)
553  elog(ERROR, "bitmapset is empty");
554  return result;
555 }
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 345 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().

346 {
347  BMS_Comparison result;
348  int shortlen;
349  int longlen;
350  int i;
351 
352  /* Handle cases where either input is NULL */
353  if (a == NULL)
354  {
355  if (b == NULL)
356  return BMS_EQUAL;
357  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
358  }
359  if (b == NULL)
360  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
361  /* Check common words */
362  result = BMS_EQUAL; /* status so far */
363  shortlen = Min(a->nwords, b->nwords);
364  for (i = 0; i < shortlen; i++)
365  {
366  bitmapword aword = a->words[i];
367  bitmapword bword = b->words[i];
368 
369  if ((aword & ~bword) != 0)
370  {
371  /* a is not a subset of b */
372  if (result == BMS_SUBSET1)
373  return BMS_DIFFERENT;
374  result = BMS_SUBSET2;
375  }
376  if ((bword & ~aword) != 0)
377  {
378  /* b is not a subset of a */
379  if (result == BMS_SUBSET2)
380  return BMS_DIFFERENT;
381  result = BMS_SUBSET1;
382  }
383  }
384  /* Check extra words */
385  if (a->nwords > b->nwords)
386  {
387  longlen = a->nwords;
388  for (; i < longlen; i++)
389  {
390  if (a->words[i] != 0)
391  {
392  /* a is not a subset of b */
393  if (result == BMS_SUBSET1)
394  return BMS_DIFFERENT;
395  result = BMS_SUBSET2;
396  }
397  }
398  }
399  else if (a->nwords < b->nwords)
400  {
401  longlen = b->nwords;
402  for (; i < longlen; i++)
403  {
404  if (b->words[i] != 0)
405  {
406  /* b is not a subset of a */
407  if (result == BMS_SUBSET2)
408  return BMS_DIFFERENT;
409  result = BMS_SUBSET1;
410  }
411  }
412  }
413  return result;
414 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
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:663
int i
BMS_Comparison
Definition: bitmapset.h:45

◆ bms_union()

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

Definition at line 218 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(), ExecPartitionCheck(), 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_partition_wise_join().

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

Variable Documentation

◆ number_of_ones

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

Definition at line 87 of file bitmapset.c.

Referenced by bms_num_members().

◆ rightmost_one_pos

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

Definition at line 68 of file bitmapset.c.

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