PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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_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

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

Definition at line 30 of file bitmapset.c.

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

#define BITNUM (   x)    ((x) % BITS_PER_BITMAPWORD)
#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().

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

Definition at line 50 of file bitmapset.c.

Referenced by bms_first_member().

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

Function Documentation

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_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(), SS_identify_outer_params(), statext_ndistinct_build(), statext_ndistinct_deserialize(), transformGroupClause(), transformGroupClauseList(), 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:962
int i
#define elog
Definition: elog.h:219
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(), 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:949
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i
Bitmapset* bms_copy ( const Bitmapset a)
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
Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

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

818 {
819  int shortlen;
820  int i;
821 
822  /* Handle cases where either input is NULL */
823  if (a == NULL)
824  return NULL;
825  if (b == NULL)
826  return a;
827  /* Remove b's bits from a; we need never copy */
828  shortlen = Min(a->nwords, b->nwords);
829  for (i = 0; i < shortlen; i++)
830  a->words[i] &= ~b->words[i];
831  return a;
832 }
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
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
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
int bms_first_member ( Bitmapset a)

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

886 {
887  int nwords;
888  int wordnum;
889 
890  if (a == NULL)
891  return -1;
892  nwords = a->nwords;
893  for (wordnum = 0; wordnum < nwords; wordnum++)
894  {
895  bitmapword w = a->words[wordnum];
896 
897  if (w != 0)
898  {
899  int result;
900 
901  w = RIGHTMOST_ONE(w);
902  a->words[wordnum] &= ~w;
903 
904  result = wordnum * BITS_PER_BITMAPWORD;
905  while ((w & 255) == 0)
906  {
907  w >>= 8;
908  result += 8;
909  }
910  result += rightmost_one_pos[w & 255];
911  return result;
912  }
913  }
914  return -1;
915 }
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
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
uint32 bms_hash_value ( const Bitmapset a)

Definition at line 984 of file bitmapset.c.

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

Referenced by bitmap_hash().

985 {
986  int lastword;
987 
988  if (a == NULL)
989  return 0; /* All empty sets hash to 0 */
990  for (lastword = a->nwords; --lastword >= 0;)
991  {
992  if (a->words[lastword] != 0)
993  break;
994  }
995  if (lastword < 0)
996  return 0; /* All empty sets hash to 0 */
997  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
998  (lastword + 1) * sizeof(bitmapword)));
999 }
#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
Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

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

792 {
793  int shortlen;
794  int i;
795 
796  /* Handle cases where either input is NULL */
797  if (a == NULL)
798  return NULL;
799  if (b == NULL)
800  {
801  pfree(a);
802  return NULL;
803  }
804  /* Intersect b into a; we need never copy */
805  shortlen = Min(a->nwords, b->nwords);
806  for (i = 0; i < shortlen; i++)
807  a->words[i] &= b->words[i];
808  for (; i < a->nwords; i++)
809  a->words[i] = 0;
810  return a;
811 }
int nwords
Definition: bitmapset.h:39
#define Min(x, y)
Definition: c.h:812
void pfree(void *pointer)
Definition: mcxt.c:949
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i
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(), 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
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(), 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
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
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
Bitmapset* bms_join ( Bitmapset a,
Bitmapset b 
)

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

839 {
840  Bitmapset *result;
841  Bitmapset *other;
842  int otherlen;
843  int i;
844 
845  /* Handle cases where either input is NULL */
846  if (a == NULL)
847  return b;
848  if (b == NULL)
849  return a;
850  /* Identify shorter and longer input; use longer one as result */
851  if (a->nwords < b->nwords)
852  {
853  result = b;
854  other = a;
855  }
856  else
857  {
858  result = a;
859  other = b;
860  }
861  /* And union the shorter input into the result */
862  otherlen = other->nwords;
863  for (i = 0; i < otherlen; i++)
864  result->words[i] |= other->words[i];
865  if (other != result) /* pure paranoia */
866  pfree(other);
867  return result;
868 }
int nwords
Definition: bitmapset.h:39
void pfree(void *pointer)
Definition: mcxt.c:949
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int i
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:877
#define elog
Definition: elog.h:219
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
int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 937 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(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecInitAgg(), ExecScanReScan(), fixup_inherited_columns(), format_expr_params(), 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(), set_customscan_references(), set_foreignscan_references(), setup_param_list(), setup_unshared_param_list(), statext_dependencies_build(), and statext_ndistinct_serialize().

938 {
939  int nwords;
940  int wordnum;
941  bitmapword mask;
942 
943  if (a == NULL)
944  return -2;
945  nwords = a->nwords;
946  prevbit++;
947  mask = (~(bitmapword) 0) << BITNUM(prevbit);
948  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
949  {
950  bitmapword w = a->words[wordnum];
951 
952  /* ignore bits before prevbit */
953  w &= mask;
954 
955  if (w != 0)
956  {
957  int result;
958 
959  result = wordnum * BITS_PER_BITMAPWORD;
960  while ((w & 255) == 0)
961  {
962  w >>= 8;
963  result += 8;
964  }
965  result += rightmost_one_pos[w & 255];
966  return result;
967  }
968 
969  /* in subsequent words, consider all bits */
970  mask = (~(bitmapword) 0);
971  }
972  return -2;
973 }
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
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
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(), 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
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
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
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_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
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

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

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