PostgreSQL Source Code  git master
pg_bitutils.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define pg_leftmost_one_pos_size_t   pg_leftmost_one_pos64
 
#define pg_nextpower2_size_t   pg_nextpower2_64
 
#define pg_prevpower2_size_t   pg_prevpower2_64
 

Functions

static int pg_leftmost_one_pos32 (uint32 word)
 
static int pg_leftmost_one_pos64 (uint64 word)
 
static int pg_rightmost_one_pos32 (uint32 word)
 
static int pg_rightmost_one_pos64 (uint64 word)
 
static uint32 pg_nextpower2_32 (uint32 num)
 
static uint64 pg_nextpower2_64 (uint64 num)
 
static uint32 pg_prevpower2_32 (uint32 num)
 
static uint64 pg_prevpower2_64 (uint64 num)
 
static uint32 pg_ceil_log2_32 (uint32 num)
 
static uint64 pg_ceil_log2_64 (uint64 num)
 
int pg_popcount32 (uint32 word)
 
int pg_popcount64 (uint64 word)
 
uint64 pg_popcount (const char *buf, int bytes)
 
static uint32 pg_rotate_right32 (uint32 word, int n)
 
static uint32 pg_rotate_left32 (uint32 word, int n)
 

Variables

PGDLLIMPORT const uint8 pg_leftmost_one_pos [256]
 
PGDLLIMPORT const uint8 pg_rightmost_one_pos [256]
 
PGDLLIMPORT const uint8 pg_number_of_ones [256]
 

Macro Definition Documentation

◆ pg_leftmost_one_pos_size_t

#define pg_leftmost_one_pos_size_t   pg_leftmost_one_pos64

Definition at line 338 of file pg_bitutils.h.

◆ pg_nextpower2_size_t

#define pg_nextpower2_size_t   pg_nextpower2_64

Definition at line 339 of file pg_bitutils.h.

◆ pg_prevpower2_size_t

#define pg_prevpower2_size_t   pg_prevpower2_64

Definition at line 340 of file pg_bitutils.h.

Function Documentation

◆ pg_ceil_log2_32()

static uint32 pg_ceil_log2_32 ( uint32  num)
inlinestatic

Definition at line 258 of file pg_bitutils.h.

259 {
260  if (num < 2)
261  return 0;
262  else
263  return pg_leftmost_one_pos32(num - 1) + 1;
264 }
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:41

References pg_leftmost_one_pos32().

Referenced by _hash_spareindex(), and my_log2().

◆ pg_ceil_log2_64()

static uint64 pg_ceil_log2_64 ( uint64  num)
inlinestatic

Definition at line 271 of file pg_bitutils.h.

272 {
273  if (num < 2)
274  return 0;
275  else
276  return pg_leftmost_one_pos64(num - 1) + 1;
277 }
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:72

References pg_leftmost_one_pos64().

Referenced by GetHugePageSize(), and my_log2().

◆ pg_leftmost_one_pos32()

static int pg_leftmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 41 of file pg_bitutils.h.

42 {
43 #ifdef HAVE__BUILTIN_CLZ
44  Assert(word != 0);
45 
46  return 31 - __builtin_clz(word);
47 #elif defined(_MSC_VER)
48  unsigned long result;
49  bool non_zero;
50 
51  Assert(word != 0);
52 
53  non_zero = _BitScanReverse(&result, word);
54  return (int) result;
55 #else
56  int shift = 32 - 8;
57 
58  Assert(word != 0);
59 
60  while ((word >> shift) == 0)
61  shift -= 8;
62 
63  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
64 #endif /* HAVE__BUILTIN_CLZ */
65 }
Assert(fmt[strlen(fmt) - 1] !='\n')
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474

References Assert(), pg_leftmost_one_pos, and word().

Referenced by _hash_get_oldblock_from_newbucket(), _hash_init_metabuffer(), add_paths_to_append_rel(), AllocSetFreeIndex(), decimalLength32(), generate_union_paths(), make_main_region_dsm_handle(), pg_ceil_log2_32(), pg_nextpower2_32(), pg_prevpower2_32(), and rho().

◆ pg_leftmost_one_pos64()

static int pg_leftmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 72 of file pg_bitutils.h.

73 {
74 #ifdef HAVE__BUILTIN_CLZ
75  Assert(word != 0);
76 
77 #if defined(HAVE_LONG_INT_64)
78  return 63 - __builtin_clzl(word);
79 #elif defined(HAVE_LONG_LONG_INT_64)
80  return 63 - __builtin_clzll(word);
81 #else
82 #error must have a working 64-bit integer datatype
83 #endif /* HAVE_LONG_INT_64 */
84 
85 #elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
86  unsigned long result;
87  bool non_zero;
88 
89  Assert(word != 0);
90 
91  non_zero = _BitScanReverse64(&result, word);
92  return (int) result;
93 #else
94  int shift = 64 - 8;
95 
96  Assert(word != 0);
97 
98  while ((word >> shift) == 0)
99  shift -= 8;
100 
101  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
102 #endif /* HAVE__BUILTIN_CLZ */
103 }

References Assert(), pg_leftmost_one_pos, and word().

Referenced by decimalLength64(), permute(), pg_ceil_log2_64(), pg_nextpower2_64(), pg_prevpower2_64(), and pg_prng_uint64_range().

◆ pg_nextpower2_32()

static uint32 pg_nextpower2_32 ( uint32  num)
inlinestatic

Definition at line 189 of file pg_bitutils.h.

190 {
191  Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
192 
193  /*
194  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
195  * will turn on all previous bits resulting in no common bits being set
196  * between num and num-1.
197  */
198  if ((num & (num - 1)) == 0)
199  return num; /* already power 2 */
200 
201  return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
202 }
unsigned int uint32
Definition: c.h:493
#define PG_UINT32_MAX
Definition: c.h:577

References Assert(), pg_leftmost_one_pos32(), and PG_UINT32_MAX.

Referenced by _h_spoolinit(), _hash_init_metabuffer(), accumArrayResultArr(), array_agg_array_combine(), array_agg_combine(), bottomup_sort_and_shrink(), bottomup_sort_and_shrink_cmp(), enlarge_list(), ensure_record_cache_typmod_slot_exists(), ExecChooseHashTableSize(), ExecHashBuildSkewHash(), ExecParallelHashIncreaseNumBatches(), ginHeapTupleFastCollect(), LWLockRegisterTranche(), new_list(), RequestNamedLWLockTranche(), and table_block_parallelscan_startblock_init().

◆ pg_nextpower2_64()

static uint64 pg_nextpower2_64 ( uint64  num)
inlinestatic

Definition at line 212 of file pg_bitutils.h.

213 {
214  Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
215 
216  /*
217  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
218  * will turn on all previous bits resulting in no common bits being set
219  * between num and num-1.
220  */
221  if ((num & (num - 1)) == 0)
222  return num; /* already power 2 */
223 
224  return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
225 }
#define PG_UINT64_MAX
Definition: c.h:580

References Assert(), pg_leftmost_one_pos64(), and PG_UINT64_MAX.

◆ pg_popcount()

uint64 pg_popcount ( const char *  buf,
int  bytes 
)

Definition at line 296 of file pg_bitutils.c.

297 {
298  uint64 popcnt = 0;
299 
300 #if SIZEOF_VOID_P >= 8
301  /* Process in 64-bit chunks if the buffer is aligned. */
302  if (buf == (const char *) TYPEALIGN(8, buf))
303  {
304  const uint64 *words = (const uint64 *) buf;
305 
306  while (bytes >= 8)
307  {
308  popcnt += pg_popcount64(*words++);
309  bytes -= 8;
310  }
311 
312  buf = (const char *) words;
313  }
314 #else
315  /* Process in 32-bit chunks if the buffer is aligned. */
316  if (buf == (const char *) TYPEALIGN(4, buf))
317  {
318  const uint32 *words = (const uint32 *) buf;
319 
320  while (bytes >= 4)
321  {
322  popcnt += pg_popcount32(*words++);
323  bytes -= 4;
324  }
325 
326  buf = (const char *) words;
327  }
328 #endif
329 
330  /* Process any remaining bytes */
331  while (bytes--)
332  popcnt += pg_number_of_ones[(unsigned char) *buf++];
333 
334  return popcnt;
335 }
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:791
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:284
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:278
static char * buf
Definition: pg_test_fsync.c:73

References buf, pg_number_of_ones, pg_popcount32(), pg_popcount64(), and TYPEALIGN.

Referenced by bit_bit_count(), bloom_prop_bits_set(), bytea_bit_count(), GetWALBlockInfo(), heap_tuple_infomask_flags(), process_pipe_input(), and sizebitvec().

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 278 of file pg_bitutils.c.

279 {
280  return pg_popcount32_slow(word);
281 }
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:223

References pg_popcount32_slow(), and word().

Referenced by pg_popcount(), and plan_single_revoke().

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 284 of file pg_bitutils.c.

285 {
286  return pg_popcount64_slow(word);
287 }
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:245

References pg_popcount64_slow(), and word().

Referenced by pg_popcount(), and visibilitymap_count().

◆ pg_prevpower2_32()

static uint32 pg_prevpower2_32 ( uint32  num)
inlinestatic

Definition at line 235 of file pg_bitutils.h.

236 {
237  return ((uint32) 1) << pg_leftmost_one_pos32(num);
238 }

References pg_leftmost_one_pos32().

Referenced by ExecParallelHashIncreaseNumBatches().

◆ pg_prevpower2_64()

static uint64 pg_prevpower2_64 ( uint64  num)
inlinestatic

Definition at line 248 of file pg_bitutils.h.

249 {
250  return ((uint64) 1) << pg_leftmost_one_pos64(num);
251 }

References pg_leftmost_one_pos64().

◆ pg_rightmost_one_pos32()

static int pg_rightmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 111 of file pg_bitutils.h.

112 {
113 #ifdef HAVE__BUILTIN_CTZ
114  Assert(word != 0);
115 
116  return __builtin_ctz(word);
117 #elif defined(_MSC_VER)
118  unsigned long result;
119  bool non_zero;
120 
121  Assert(word != 0);
122 
123  non_zero = _BitScanForward(&result, word);
124  return (int) result;
125 #else
126  int result = 0;
127 
128  Assert(word != 0);
129 
130  while ((word & 255) == 0)
131  {
132  word >>= 8;
133  result += 8;
134  }
135  result += pg_rightmost_one_pos[word & 255];
136  return result;
137 #endif /* HAVE__BUILTIN_CTZ */
138 }
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62

References Assert(), pg_rightmost_one_pos, and word().

Referenced by ProcessProcSignalBarrier().

◆ pg_rightmost_one_pos64()

static int pg_rightmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 145 of file pg_bitutils.h.

146 {
147 #ifdef HAVE__BUILTIN_CTZ
148  Assert(word != 0);
149 
150 #if defined(HAVE_LONG_INT_64)
151  return __builtin_ctzl(word);
152 #elif defined(HAVE_LONG_LONG_INT_64)
153  return __builtin_ctzll(word);
154 #else
155 #error must have a working 64-bit integer datatype
156 #endif /* HAVE_LONG_INT_64 */
157 
158 #elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
159  unsigned long result;
160  bool non_zero;
161 
162  Assert(word != 0);
163 
164  non_zero = _BitScanForward64(&result, word);
165  return (int) result;
166 #else
167  int result = 0;
168 
169  Assert(word != 0);
170 
171  while ((word & 255) == 0)
172  {
173  word >>= 8;
174  result += 8;
175  }
176  result += pg_rightmost_one_pos[word & 255];
177  return result;
178 #endif /* HAVE__BUILTIN_CTZ */
179 }

References Assert(), pg_rightmost_one_pos, and word().

Referenced by fasthash_accum_cstring_aligned().

◆ pg_rotate_left32()

static uint32 pg_rotate_left32 ( uint32  word,
int  n 
)
inlinestatic

Definition at line 326 of file pg_bitutils.h.

327 {
328  return (word << n) | (word >> (32 - n));
329 }

References word().

Referenced by CatalogCacheComputeHashValue(), ExecHashGetHashValue(), guc_name_hash(), hash_multirange(), hash_range(), JsonbHashScalarValue(), MemoizeHash_hash(), and TupleHashTableHash_internal().

◆ pg_rotate_right32()

static uint32 pg_rotate_right32 ( uint32  word,
int  n 
)
inlinestatic

Definition at line 320 of file pg_bitutils.h.

321 {
322  return (word >> n) | (word << (32 - n));
323 }

References word().

Referenced by ExecHashGetBucketAndBatch().

Variable Documentation

◆ pg_leftmost_one_pos

PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
extern

Definition at line 34 of file pg_bitutils.c.

Referenced by AllocSetFreeIndex(), pg_leftmost_one_pos32(), and pg_leftmost_one_pos64().

◆ pg_number_of_ones

PGDLLIMPORT const uint8 pg_number_of_ones[256]
extern

Definition at line 87 of file pg_bitutils.c.

Referenced by hemdistsign(), pg_popcount(), pg_popcount32_slow(), and pg_popcount64_slow().

◆ pg_rightmost_one_pos

PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
extern

Definition at line 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().