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 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_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 29 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 51 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 49 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 668 of file bitmapset.c.

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

Referenced by _readBitmapset(), adjust_relid_set(), adjust_view_column_set(), alias_relid_set(), ATExecAttachPartition(), build_subplan(), check_functional_grouping(), check_index_only(), checkInsertTargets(), classify_index_clause_usage(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), deparseColumnRef(), DoCopy(), EvalPlanQualBegin(), ExecInitAgg(), ExecNestLoop(), ExecRecursiveUnion(), ExecReScanRecursiveUnion(), ExecReScanSetParamPlan(), ExecScanSubPlan(), ExecSetParamPlan(), ExplainPreScanNode(), ExplainSubPlans(), extract_rollup_sets(), fetch_remote_table_info(), 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_relids_in_jointree(), 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(), 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(), transformGroupClause(), transformGroupClauseList(), transformRangeTableFunc(), transformUpdateTargetList(), translate_col_privs(), use_physical_tlist(), and view_cols_are_auto_updatable().

669 {
670  int wordnum,
671  bitnum;
672 
673  if (x < 0)
674  elog(ERROR, "negative bitmapset member not allowed");
675  if (a == NULL)
676  return bms_make_singleton(x);
677  wordnum = WORDNUM(x);
678  bitnum = BITNUM(x);
679 
680  /* enlarge the set if necessary */
681  if (wordnum >= a->nwords)
682  {
683  int oldnwords = a->nwords;
684  int i;
685 
686  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
687  a->nwords = wordnum + 1;
688  /* zero out the enlarged portion */
689  for (i = oldnwords; i < a->nwords; i++)
690  a->words[i] = 0;
691  }
692 
693  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
694  return a;
695 }
int nwords
Definition: bitmapset.h:34
#define WORDNUM(x)
Definition: bitmapset.c:26
#define BITNUM(x)
Definition: bitmapset.c:27
uint32 bitmapword
Definition: bitmapset.h:29
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:29
#define ERROR
Definition: elog.h:43
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:178
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:963
int i
#define elog
Definition: elog.h:219
Bitmapset* bms_add_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 725 of file bitmapset.c.

References bms_copy(), i, NULL, 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(), ExecInitAgg(), ExplainPreScanNode(), finalize_plan(), foreign_join_ok(), join_is_legal(), make_outerjoininfo(), pull_varnos_walker(), reduce_outer_joins_pass1(), reduce_outer_joins_pass2(), and update_placeholder_eval_levels().

726 {
727  Bitmapset *result;
728  const Bitmapset *other;
729  int otherlen;
730  int i;
731 
732  /* Handle cases where either input is NULL */
733  if (a == NULL)
734  return bms_copy(b);
735  if (b == NULL)
736  return a;
737  /* Identify shorter and longer input; copy the longer one if needed */
738  if (a->nwords < b->nwords)
739  {
740  result = bms_copy(b);
741  other = a;
742  }
743  else
744  {
745  result = a;
746  other = b;
747  }
748  /* And union the shorter input into the result */
749  otherlen = other->nwords;
750  for (i = 0; i < otherlen; i++)
751  result->words[i] |= other->words[i];
752  if (result != a)
753  pfree(a);
754  return result;
755 }
int nwords
Definition: bitmapset.h:34
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
void pfree(void *pointer)
Definition: mcxt.c:950
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
Bitmapset* bms_del_member ( Bitmapset a,
int  x 
)

Definition at line 705 of file bitmapset.c.

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

Referenced by adjust_relid_set(), build_index_paths(), finalize_plan(), finalize_primnode(), find_hash_columns(), fixup_whole_row_references(), postgresGetForeignPaths(), preprocess_rowmarks(), remove_rel_from_query(), substitute_multiple_relids_walker(), and TopologicalSort().

706 {
707  int wordnum,
708  bitnum;
709 
710  if (x < 0)
711  elog(ERROR, "negative bitmapset member not allowed");
712  if (a == NULL)
713  return NULL;
714  wordnum = WORDNUM(x);
715  bitnum = BITNUM(x);
716  if (wordnum < a->nwords)
717  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
718  return a;
719 }
#define WORDNUM(x)
Definition: bitmapset.c:26
#define BITNUM(x)
Definition: bitmapset.c:27
uint32 bitmapword
Definition: bitmapset.h:29
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
#define elog
Definition: elog.h:219
Bitmapset* bms_del_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 787 of file bitmapset.c.

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

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

788 {
789  int shortlen;
790  int i;
791 
792  /* Handle cases where either input is NULL */
793  if (a == NULL)
794  return NULL;
795  if (b == NULL)
796  return a;
797  /* Remove b's bits from a; we need never copy */
798  shortlen = Min(a->nwords, b->nwords);
799  for (i = 0; i < shortlen; i++)
800  a->words[i] &= ~b->words[i];
801  return a;
802 }
int nwords
Definition: bitmapset.h:34
#define Min(x, y)
Definition: c.h:806
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
Bitmapset* bms_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 283 of file bitmapset.c.

References bms_copy(), i, Min, NULL, 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().

284 {
285  Bitmapset *result;
286  int shortlen;
287  int i;
288 
289  /* Handle cases where either input is NULL */
290  if (a == NULL)
291  return NULL;
292  if (b == NULL)
293  return bms_copy(a);
294  /* Copy the left input */
295  result = bms_copy(a);
296  /* And remove b's bits from result */
297  shortlen = Min(a->nwords, b->nwords);
298  for (i = 0; i < shortlen; i++)
299  result->words[i] &= ~b->words[i];
300  return result;
301 }
int nwords
Definition: bitmapset.h:34
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
#define Min(x, y)
Definition: c.h:806
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
bool bms_equal ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 130 of file bitmapset.c.

References bms_is_empty(), i, NULL, Bitmapset::nwords, and Bitmapset::words.

Referenced by add_path_precheck(), add_paths_to_append_rel(), 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_ec_member_for_tle(), find_join_rel(), fix_indexqual_references(), generate_implied_equalities_for_column(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parameterized_child_path(), get_eclass_for_sort_expr(), get_joinrel_parampathinfo(), 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(), prepare_sort_from_pathkeys(), and remove_rel_from_query().

131 {
132  const Bitmapset *shorter;
133  const Bitmapset *longer;
134  int shortlen;
135  int longlen;
136  int i;
137 
138  /* Handle cases where either input is NULL */
139  if (a == NULL)
140  {
141  if (b == NULL)
142  return true;
143  return bms_is_empty(b);
144  }
145  else if (b == NULL)
146  return bms_is_empty(a);
147  /* Identify shorter and longer input */
148  if (a->nwords <= b->nwords)
149  {
150  shorter = a;
151  longer = b;
152  }
153  else
154  {
155  shorter = b;
156  longer = a;
157  }
158  /* And process */
159  shortlen = shorter->nwords;
160  for (i = 0; i < shortlen; i++)
161  {
162  if (shorter->words[i] != longer->words[i])
163  return false;
164  }
165  longlen = longer->nwords;
166  for (; i < longlen; i++)
167  {
168  if (longer->words[i] != 0)
169  return false;
170  }
171  return true;
172 }
int nwords
Definition: bitmapset.h:34
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
#define NULL
Definition: c.h:229
int i
int bms_first_member ( Bitmapset a)

Definition at line 855 of file bitmapset.c.

References BITS_PER_BITMAPWORD, NULL, 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(), HeapSatisfiesHOTandKeyUpdate(), make_row_comparison_op(), and mdsync().

856 {
857  int nwords;
858  int wordnum;
859 
860  if (a == NULL)
861  return -1;
862  nwords = a->nwords;
863  for (wordnum = 0; wordnum < nwords; wordnum++)
864  {
865  bitmapword w = a->words[wordnum];
866 
867  if (w != 0)
868  {
869  int result;
870 
871  w = RIGHTMOST_ONE(w);
872  a->words[wordnum] &= ~w;
873 
874  result = wordnum * BITS_PER_BITMAPWORD;
875  while ((w & 255) == 0)
876  {
877  w >>= 8;
878  result += 8;
879  }
880  result += rightmost_one_pos[w & 255];
881  return result;
882  }
883  }
884  return -1;
885 }
int nwords
Definition: bitmapset.h:34
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
uint32 bitmapword
Definition: bitmapset.h:29
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:67
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define RIGHTMOST_ONE(x)
Definition: bitmapset.c:49
#define NULL
Definition: c.h:229
bool bms_get_singleton_member ( const Bitmapset a,
int *  member 
)

Definition at line 539 of file bitmapset.c.

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

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

540 {
541  int result = -1;
542  int nwords;
543  int wordnum;
544 
545  if (a == NULL)
546  return false;
547  nwords = a->nwords;
548  for (wordnum = 0; wordnum < nwords; wordnum++)
549  {
550  bitmapword w = a->words[wordnum];
551 
552  if (w != 0)
553  {
554  if (result >= 0 || HAS_MULTIPLE_ONES(w))
555  return false;
556  result = wordnum * BITS_PER_BITMAPWORD;
557  while ((w & 255) == 0)
558  {
559  w >>= 8;
560  result += 8;
561  }
562  result += rightmost_one_pos[w & 255];
563  }
564  }
565  if (result < 0)
566  return false;
567  *member = result;
568  return true;
569 }
int nwords
Definition: bitmapset.h:34
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:51
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
uint32 bitmapword
Definition: bitmapset.h:29
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:67
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
uint32 bms_hash_value ( const Bitmapset a)

Definition at line 954 of file bitmapset.c.

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

Referenced by bitmap_hash().

955 {
956  int lastword;
957 
958  if (a == NULL)
959  return 0; /* All empty sets hash to 0 */
960  for (lastword = a->nwords; --lastword >= 0;)
961  {
962  if (a->words[lastword] != 0)
963  break;
964  }
965  if (lastword < 0)
966  return 0; /* All empty sets hash to 0 */
967  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
968  (lastword + 1) * sizeof(bitmapword)));
969 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
int nwords
Definition: bitmapset.h:34
uint32 bitmapword
Definition: bitmapset.h:29
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
Bitmapset* bms_int_members ( Bitmapset a,
const Bitmapset b 
)

Definition at line 761 of file bitmapset.c.

References i, Min, NULL, 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().

762 {
763  int shortlen;
764  int i;
765 
766  /* Handle cases where either input is NULL */
767  if (a == NULL)
768  return NULL;
769  if (b == NULL)
770  {
771  pfree(a);
772  return NULL;
773  }
774  /* Intersect b into a; we need never copy */
775  shortlen = Min(a->nwords, b->nwords);
776  for (i = 0; i < shortlen; i++)
777  a->words[i] &= b->words[i];
778  for (; i < a->nwords; i++)
779  a->words[i] = 0;
780  return a;
781 }
int nwords
Definition: bitmapset.h:34
#define Min(x, y)
Definition: c.h:806
void pfree(void *pointer)
Definition: mcxt.c:950
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
Bitmapset* bms_intersect ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 251 of file bitmapset.c.

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

Referenced by get_eclass_for_sort_expr(), make_outerjoininfo(), process_equivalence(), reconsider_full_join_clause(), reconsider_outer_join_clause(), and UpdateChangedParamSet().

252 {
253  Bitmapset *result;
254  const Bitmapset *other;
255  int resultlen;
256  int i;
257 
258  /* Handle cases where either input is NULL */
259  if (a == NULL || b == NULL)
260  return NULL;
261  /* Identify shorter and longer input; copy the shorter one */
262  if (a->nwords <= b->nwords)
263  {
264  result = bms_copy(a);
265  other = b;
266  }
267  else
268  {
269  result = bms_copy(b);
270  other = a;
271  }
272  /* And intersect the longer input with the result */
273  resultlen = result->nwords;
274  for (i = 0; i < resultlen; i++)
275  result->words[i] &= other->words[i];
276  return result;
277 }
int nwords
Definition: bitmapset.h:34
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
bool bms_is_empty ( const Bitmapset a)

Definition at line 633 of file bitmapset.c.

References NULL, 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(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_lateral_join_info(), distribute_qual_to_rels(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecReScanSetParamPlan(), finalize_plan(), find_nonnullable_rels_walker(), find_placeholder_info(), get_appendrel_parampathinfo(), get_baserel_parampathinfo(), get_cheapest_parallel_safe_total_inner(), get_joinrel_parampathinfo(), hash_inner_and_outer(), is_pseudo_constant_clause_relids(), make_outerjoininfo(), make_restrictinfo_internal(), match_unsorted_outer(), min_join_parameterization(), postgresGetForeignPaths(), 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().

634 {
635  int nwords;
636  int wordnum;
637 
638  if (a == NULL)
639  return true;
640  nwords = a->nwords;
641  for (wordnum = 0; wordnum < nwords; wordnum++)
642  {
643  bitmapword w = a->words[wordnum];
644 
645  if (w != 0)
646  return false;
647  }
648  return true;
649 }
int nwords
Definition: bitmapset.h:34
uint32 bitmapword
Definition: bitmapset.h:29
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
bool bms_is_member ( int  x,
const Bitmapset a 
)

Definition at line 419 of file bitmapset.c.

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

Referenced by adjust_relid_set(), adjust_rowcompare_for_index(), adjust_rowcount_for_semijoins(), ATExecAttachPartition(), bms_is_subset_singleton(), check_redundant_nullability_qual(), check_relation_privileges(), checkInsertTargets(), ComputePartitionAttrs(), copyParamList(), create_foreignscan_plan(), create_lateral_join_info(), create_nestloop_plan(), DefineIndex(), deparseLockingClause(), deparseTargetList(), deparseVar(), enum_known_sorted(), EstimateParamListSpace(), examine_variable(), exec_check_rw_parameter(), ExecBuildSlotValueDescription(), ExecEvalGroupingFuncExpr(), ExecInitModifyTable(), ExplainSubPlans(), fixup_whole_row_references(), foreign_expr_walker(), func_get_detail(), get_foreign_key_join_selectivity(), 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().

420 {
421  int wordnum,
422  bitnum;
423 
424  /* XXX better to just return false for x<0 ? */
425  if (x < 0)
426  elog(ERROR, "negative bitmapset member not allowed");
427  if (a == NULL)
428  return false;
429  wordnum = WORDNUM(x);
430  bitnum = BITNUM(x);
431  if (wordnum >= a->nwords)
432  return false;
433  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
434  return true;
435  return false;
436 }
int nwords
Definition: bitmapset.h:34
#define WORDNUM(x)
Definition: bitmapset.c:26
#define BITNUM(x)
Definition: bitmapset.c:27
uint32 bitmapword
Definition: bitmapset.h:29
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
#define elog
Definition: elog.h:219
bool bms_is_subset ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 307 of file bitmapset.c.

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

Referenced by add_child_rel_equivalences(), 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_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(), HeapSatisfiesHOTandKeyUpdate(), initial_cost_mergejoin(), 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(), 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().

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

Definition at line 808 of file bitmapset.c.

References i, NULL, 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().

809 {
810  Bitmapset *result;
811  Bitmapset *other;
812  int otherlen;
813  int i;
814 
815  /* Handle cases where either input is NULL */
816  if (a == NULL)
817  return b;
818  if (b == NULL)
819  return a;
820  /* Identify shorter and longer input; use longer one as result */
821  if (a->nwords < b->nwords)
822  {
823  result = b;
824  other = a;
825  }
826  else
827  {
828  result = a;
829  other = b;
830  }
831  /* And union the shorter input into the result */
832  otherlen = other->nwords;
833  for (i = 0; i < otherlen; i++)
834  result->words[i] |= other->words[i];
835  if (other != result) /* pure paranoia */
836  pfree(other);
837  return result;
838 }
int nwords
Definition: bitmapset.h:34
void pfree(void *pointer)
Definition: mcxt.c:950
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int i
Bitmapset* bms_make_singleton ( int  x)

Definition at line 178 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(), extract_lateral_references(), find_nonnullable_rels_walker(), get_relids_in_jointree(), load_enum_cache_data(), pg_column_is_updatable(), pull_up_sublinks_jointree_recurse(), pullup_replace_vars_callback(), and reduce_outer_joins_pass1().

179 {
180  Bitmapset *result;
181  int wordnum,
182  bitnum;
183 
184  if (x < 0)
185  elog(ERROR, "negative bitmapset member not allowed");
186  wordnum = WORDNUM(x);
187  bitnum = BITNUM(x);
188  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
189  result->nwords = wordnum + 1;
190  result->words[wordnum] = ((bitmapword) 1 << bitnum);
191  return result;
192 }
int nwords
Definition: bitmapset.h:34
#define WORDNUM(x)
Definition: bitmapset.c:26
#define BITNUM(x)
Definition: bitmapset.c:27
uint32 bitmapword
Definition: bitmapset.h:29
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:29
#define ERROR
Definition: elog.h:43
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
void * palloc0(Size size)
Definition: mcxt.c:878
#define elog
Definition: elog.h:219
BMS_Membership bms_membership ( const Bitmapset a)

Definition at line 604 of file bitmapset.c.

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

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

605 {
606  BMS_Membership result = BMS_EMPTY_SET;
607  int nwords;
608  int wordnum;
609 
610  if (a == NULL)
611  return BMS_EMPTY_SET;
612  nwords = a->nwords;
613  for (wordnum = 0; wordnum < nwords; wordnum++)
614  {
615  bitmapword w = a->words[wordnum];
616 
617  if (w != 0)
618  {
619  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
620  return BMS_MULTIPLE;
621  result = BMS_SINGLETON;
622  }
623  }
624  return result;
625 }
int nwords
Definition: bitmapset.h:34
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:51
uint32 bitmapword
Definition: bitmapset.h:29
BMS_Membership
Definition: bitmapset.h:49
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
int bms_next_member ( const Bitmapset a,
int  prevbit 
)

Definition at line 907 of file bitmapset.c.

References BITNUM, BITS_PER_BITMAPWORD, NULL, 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(), ExecCheckRTEPerms(), ExecCheckRTEPermsModified(), ExecInitAgg(), ExecScanReScan(), fixup_inherited_columns(), format_expr_params(), get_loop_count(), logicalrep_rel_open(), offset_relid_set(), outBitmapset(), postgresBeginForeignScan(), postgresPlanDirectModify(), postgresPlanForeignModify(), remove_join_clause_from_rels(), set_customscan_references(), set_foreignscan_references(), setup_param_list(), and setup_unshared_param_list().

908 {
909  int nwords;
910  int wordnum;
911  bitmapword mask;
912 
913  if (a == NULL)
914  return -2;
915  nwords = a->nwords;
916  prevbit++;
917  mask = (~(bitmapword) 0) << BITNUM(prevbit);
918  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
919  {
920  bitmapword w = a->words[wordnum];
921 
922  /* ignore bits before prevbit */
923  w &= mask;
924 
925  if (w != 0)
926  {
927  int result;
928 
929  result = wordnum * BITS_PER_BITMAPWORD;
930  while ((w & 255) == 0)
931  {
932  w >>= 8;
933  result += 8;
934  }
935  result += rightmost_one_pos[w & 255];
936  return result;
937  }
938 
939  /* in subsequent words, consider all bits */
940  mask = (~(bitmapword) 0);
941  }
942  return -2;
943 }
int nwords
Definition: bitmapset.h:34
#define WORDNUM(x)
Definition: bitmapset.c:26
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
#define BITNUM(x)
Definition: bitmapset.c:27
uint32 bitmapword
Definition: bitmapset.h:29
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:67
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
bool bms_nonempty_difference ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 464 of file bitmapset.c.

References bms_is_empty(), i, Min, NULL, 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().

465 {
466  int shortlen;
467  int i;
468 
469  /* Handle cases where either input is NULL */
470  if (a == NULL)
471  return false;
472  if (b == NULL)
473  return !bms_is_empty(a);
474  /* Check words in common */
475  shortlen = Min(a->nwords, b->nwords);
476  for (i = 0; i < shortlen; i++)
477  {
478  if ((a->words[i] & ~b->words[i]) != 0)
479  return true;
480  }
481  /* Check extra words in a */
482  for (; i < a->nwords; i++)
483  {
484  if (a->words[i] != 0)
485  return true;
486  }
487  return false;
488 }
int nwords
Definition: bitmapset.h:34
#define Min(x, y)
Definition: c.h:806
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
#define NULL
Definition: c.h:229
int i
int bms_num_members ( const Bitmapset a)

Definition at line 575 of file bitmapset.c.

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

Referenced by build_join_rel(), deparseFromExpr(), deparseLockingClause(), deparseVar(), find_hash_columns(), and NumRelids().

576 {
577  int result = 0;
578  int nwords;
579  int wordnum;
580 
581  if (a == NULL)
582  return 0;
583  nwords = a->nwords;
584  for (wordnum = 0; wordnum < nwords; wordnum++)
585  {
586  bitmapword w = a->words[wordnum];
587 
588  /* we assume here that bitmapword is an unsigned type */
589  while (w != 0)
590  {
591  result += number_of_ones[w & 255];
592  w >>= 8;
593  }
594  }
595  return result;
596 }
int nwords
Definition: bitmapset.h:34
uint32 bitmapword
Definition: bitmapset.h:29
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
static const uint8 number_of_ones[256]
Definition: bitmapset.c:86
#define NULL
Definition: c.h:229
bool bms_overlap ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 442 of file bitmapset.c.

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

Referenced by add_child_rel_equivalences(), add_paths_to_joinrel(), 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(), 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(), replace_nestloop_params_mutator(), select_outer_pathkeys_for_merge(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), and update_placeholder_eval_levels().

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

Definition at line 496 of file bitmapset.c.

References BITS_PER_BITMAPWORD, elog, ERROR, HAS_MULTIPLE_ONES, NULL, 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().

497 {
498  int result = -1;
499  int nwords;
500  int wordnum;
501 
502  if (a == NULL)
503  elog(ERROR, "bitmapset is empty");
504  nwords = a->nwords;
505  for (wordnum = 0; wordnum < nwords; wordnum++)
506  {
507  bitmapword w = a->words[wordnum];
508 
509  if (w != 0)
510  {
511  if (result >= 0 || HAS_MULTIPLE_ONES(w))
512  elog(ERROR, "bitmapset has multiple members");
513  result = wordnum * BITS_PER_BITMAPWORD;
514  while ((w & 255) == 0)
515  {
516  w >>= 8;
517  result += 8;
518  }
519  result += rightmost_one_pos[w & 255];
520  }
521  }
522  if (result < 0)
523  elog(ERROR, "bitmapset is empty");
524  return result;
525 }
int nwords
Definition: bitmapset.h:34
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:51
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
uint32 bitmapword
Definition: bitmapset.h:29
#define ERROR
Definition: elog.h:43
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:67
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
#define NULL
Definition: c.h:229
#define elog
Definition: elog.h:219
BMS_Comparison bms_subset_compare ( const Bitmapset a,
const Bitmapset b 
)

Definition at line 344 of file bitmapset.c.

References BMS_DIFFERENT, BMS_EQUAL, bms_is_empty(), BMS_SUBSET1, BMS_SUBSET2, i, Min, NULL, Bitmapset::nwords, and Bitmapset::words.

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

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

Definition at line 217 of file bitmapset.c.

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

Referenced by 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(), 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(), remove_useless_joins(), and substitute_multiple_relids_walker().

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

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