PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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_optimized (const char *buf, int bytes)
 
uint64 pg_popcount_masked_optimized (const char *buf, int bytes, bits8 mask)
 
static uint64 pg_popcount (const char *buf, int bytes)
 
static uint64 pg_popcount_masked (const char *buf, int bytes, bits8 mask)
 
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 416 of file pg_bitutils.h.

◆ pg_nextpower2_size_t

#define pg_nextpower2_size_t   pg_nextpower2_64

Definition at line 417 of file pg_bitutils.h.

◆ pg_prevpower2_size_t

#define pg_prevpower2_size_t   pg_prevpower2_64

Definition at line 418 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}
#define Assert(condition)
Definition: c.h:812
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:1476

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 SIZEOF_LONG == 8
78 return 63 - __builtin_clzl(word);
79#elif SIZEOF_LONG_LONG == 8
80 return 63 - __builtin_clzll(word);
81#else
82#error "cannot find integer type of the same size as uint64_t"
83#endif
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(), pg_prng_uint64_range(), and RT_KEY_GET_SHIFT().

◆ 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}
#define PG_UINT32_MAX
Definition: c.h:544
uint32_t uint32
Definition: c.h:485

References Assert, pg_leftmost_one_pos32(), and PG_UINT32_MAX.

Referenced by _h_spoolinit(), _hash_init_metabuffer(), accumArrayResultArr(), addlit(), 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}
uint64_t uint64
Definition: c.h:486
#define PG_UINT64_MAX
Definition: c.h:547

References Assert, pg_leftmost_one_pos64(), and PG_UINT64_MAX.

◆ pg_popcount()

static uint64 pg_popcount ( const char *  buf,
int  bytes 
)
inlinestatic

Definition at line 339 of file pg_bitutils.h.

340{
341 /*
342 * We set the threshold to the point at which we'll first use special
343 * instructions in the optimized version.
344 */
345#if SIZEOF_VOID_P >= 8
346 int threshold = 8;
347#else
348 int threshold = 4;
349#endif
350
351 if (bytes < threshold)
352 {
353 uint64 popcnt = 0;
354
355 while (bytes--)
356 popcnt += pg_number_of_ones[(unsigned char) *buf++];
357 return popcnt;
358 }
359
360 return pg_popcount_optimized(buf, bytes);
361}
PGDLLIMPORT const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
uint64 pg_popcount_optimized(const char *buf, int bytes)
Definition: pg_bitutils.c:515
static char * buf
Definition: pg_test_fsync.c:72

References buf, pg_number_of_ones, and pg_popcount_optimized().

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

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 499 of file pg_bitutils.c.

500{
501 return pg_popcount32_slow(word);
502}
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:348

References pg_popcount32_slow(), and word().

Referenced by plan_single_revoke().

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 505 of file pg_bitutils.c.

506{
507 return pg_popcount64_slow(word);
508}
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:370

References pg_popcount64_slow(), and word().

◆ pg_popcount_masked()

static uint64 pg_popcount_masked ( const char *  buf,
int  bytes,
bits8  mask 
)
inlinestatic

Definition at line 370 of file pg_bitutils.h.

371{
372 /*
373 * We set the threshold to the point at which we'll first use special
374 * instructions in the optimized version.
375 */
376#if SIZEOF_VOID_P >= 8
377 int threshold = 8;
378#else
379 int threshold = 4;
380#endif
381
382 if (bytes < threshold)
383 {
384 uint64 popcnt = 0;
385
386 while (bytes--)
387 popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
388 return popcnt;
389 }
390
391 return pg_popcount_masked_optimized(buf, bytes, mask);
392}
uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:525

References buf, pg_number_of_ones, and pg_popcount_masked_optimized().

Referenced by visibilitymap_count().

◆ pg_popcount_masked_optimized()

uint64 pg_popcount_masked_optimized ( const char *  buf,
int  bytes,
bits8  mask 
)

Definition at line 525 of file pg_bitutils.c.

526{
527 return pg_popcount_masked_slow(buf, bytes, mask);
528}
static uint64 pg_popcount_masked_slow(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:444

References buf, and pg_popcount_masked_slow().

Referenced by pg_popcount_masked().

◆ pg_popcount_optimized()

uint64 pg_popcount_optimized ( const char *  buf,
int  bytes 
)

Definition at line 515 of file pg_bitutils.c.

516{
517 return pg_popcount_slow(buf, bytes);
518}
static uint64 pg_popcount_slow(const char *buf, int bytes)
Definition: pg_bitutils.c:398

References buf, and pg_popcount_slow().

Referenced by pg_popcount().

◆ 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(), RT_NODE_16_GET_INSERTPOS(), and RT_NODE_16_SEARCH_EQ().

◆ 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 SIZEOF_LONG == 8
151 return __builtin_ctzl(word);
152#elif SIZEOF_LONG_LONG == 8
153 return __builtin_ctzll(word);
154#else
155#error "cannot find integer type of the same size as uint64_t"
156#endif
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 if().

◆ pg_rotate_left32()

static uint32 pg_rotate_left32 ( uint32  word,
int  n 
)
inlinestatic

◆ pg_rotate_right32()

static uint32 pg_rotate_right32 ( uint32  word,
int  n 
)
inlinestatic

Definition at line 398 of file pg_bitutils.h.

399{
400 return (word >> n) | (word << (32 - n));
401}

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

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