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.

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_ceil_log2_32 (uint32 num)
 
static uint64 pg_ceil_log2_64 (uint64 num)
 
uint64 pg_popcount (const char *buf, int bytes)
 
static uint32 pg_rotate_right32 (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]
 
int(* pg_popcount32 )(uint32 word)
 
int(* pg_popcount64 )(uint64 word)
 

Function Documentation

◆ pg_ceil_log2_32()

static uint32 pg_ceil_log2_32 ( uint32  num)
inlinestatic

Definition at line 189 of file pg_bitutils.h.

References pg_leftmost_one_pos32().

Referenced by _hash_spareindex(), and my_log2().

190 {
191  if (num < 2)
192  return 0;
193  else
194  return pg_leftmost_one_pos32(num - 1) + 1;
195 }
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:32

◆ pg_ceil_log2_64()

static uint64 pg_ceil_log2_64 ( uint64  num)
inlinestatic

Definition at line 202 of file pg_bitutils.h.

References buf, generate_unaccent_rules::bytes(), pg_leftmost_one_pos64(), pg_popcount(), pg_popcount32, pg_popcount64, and word().

Referenced by my_log2(), and PGSharedMemoryAttach().

203 {
204  if (num < 2)
205  return 0;
206  else
207  return pg_leftmost_one_pos64(num - 1) + 1;
208 }
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:55

◆ pg_leftmost_one_pos32()

static int pg_leftmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 32 of file pg_bitutils.h.

References Assert, and pg_leftmost_one_pos.

Referenced by _hash_init_metabuffer(), decimalLength32(), make_main_region_dsm_handle(), pg_ceil_log2_32(), pg_nextpower2_32(), and rho().

33 {
34 #ifdef HAVE__BUILTIN_CLZ
35  Assert(word != 0);
36 
37  return 31 - __builtin_clz(word);
38 #else
39  int shift = 32 - 8;
40 
41  Assert(word != 0);
42 
43  while ((word >> shift) == 0)
44  shift -= 8;
45 
46  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
47 #endif /* HAVE__BUILTIN_CLZ */
48 }
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
#define Assert(condition)
Definition: c.h:745
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246

◆ pg_leftmost_one_pos64()

static int pg_leftmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 55 of file pg_bitutils.h.

References Assert, and pg_leftmost_one_pos.

Referenced by decimalLength64(), pg_ceil_log2_64(), and pg_nextpower2_64().

56 {
57 #ifdef HAVE__BUILTIN_CLZ
58  Assert(word != 0);
59 
60 #if defined(HAVE_LONG_INT_64)
61  return 63 - __builtin_clzl(word);
62 #elif defined(HAVE_LONG_LONG_INT_64)
63  return 63 - __builtin_clzll(word);
64 #else
65 #error must have a working 64-bit integer datatype
66 #endif
67 #else /* !HAVE__BUILTIN_CLZ */
68  int shift = 64 - 8;
69 
70  Assert(word != 0);
71 
72  while ((word >> shift) == 0)
73  shift -= 8;
74 
75  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
76 #endif /* HAVE__BUILTIN_CLZ */
77 }
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
#define Assert(condition)
Definition: c.h:745
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246

◆ pg_nextpower2_32()

static uint32 pg_nextpower2_32 ( uint32  num)
inlinestatic

Definition at line 146 of file pg_bitutils.h.

References Assert, pg_leftmost_one_pos32(), and PG_UINT32_MAX.

Referenced by _h_spoolinit(), _hash_init_metabuffer(), accumArrayResultArr(), enlarge_list(), ExecChooseHashTableSize(), ExecHashBuildSkewHash(), ginHeapTupleFastCollect(), new_list(), and table_block_parallelscan_startblock_init().

147 {
148  Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
149 
150  /*
151  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
152  * will turn on all previous bits resulting in no common bits being set
153  * between num and num-1.
154  */
155  if ((num & (num - 1)) == 0)
156  return num; /* already power 2 */
157 
158  return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
159 }
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:32
#define PG_UINT32_MAX
Definition: c.h:458
unsigned int uint32
Definition: c.h:374
#define Assert(condition)
Definition: c.h:745

◆ pg_nextpower2_64()

static uint64 pg_nextpower2_64 ( uint64  num)
inlinestatic

Definition at line 169 of file pg_bitutils.h.

References Assert, pg_leftmost_one_pos64(), and PG_UINT64_MAX.

170 {
171  Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
172 
173  /*
174  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
175  * will turn on all previous bits resulting in no common bits being set
176  * between num and num-1.
177  */
178  if ((num & (num - 1)) == 0)
179  return num; /* already power 2 */
180 
181  return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
182 }
#define PG_UINT64_MAX
Definition: c.h:461
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:55
#define Assert(condition)
Definition: c.h:745

◆ pg_popcount()

uint64 pg_popcount ( const char *  buf,
int  bytes 
)

Definition at line 282 of file pg_bitutils.c.

References pg_number_of_ones, pg_popcount32, pg_popcount64, and TYPEALIGN.

Referenced by bloom_prop_bits_set(), heap_tuple_infomask_flags(), pg_ceil_log2_64(), and sizebitvec().

283 {
284  uint64 popcnt = 0;
285 
286 #if SIZEOF_VOID_P >= 8
287  /* Process in 64-bit chunks if the buffer is aligned. */
288  if (buf == (const char *) TYPEALIGN(8, buf))
289  {
290  const uint64 *words = (const uint64 *) buf;
291 
292  while (bytes >= 8)
293  {
294  popcnt += pg_popcount64(*words++);
295  bytes -= 8;
296  }
297 
298  buf = (const char *) words;
299  }
300 #else
301  /* Process in 32-bit chunks if the buffer is aligned. */
302  if (buf == (const char *) TYPEALIGN(4, buf))
303  {
304  const uint32 *words = (const uint32 *) buf;
305 
306  while (bytes >= 4)
307  {
308  popcnt += pg_popcount32(*words++);
309  bytes -= 4;
310  }
311 
312  buf = (const char *) words;
313  }
314 #endif
315 
316  /* Process any remaining bytes */
317  while (bytes--)
318  popcnt += pg_number_of_ones[(unsigned char) *buf++];
319 
320  return popcnt;
321 }
int(* pg_popcount32)(uint32 word)
Definition: pg_bitutils.c:132
def bytes(source, encoding='ascii', errors='strict')
int(* pg_popcount64)(uint64 word)
Definition: pg_bitutils.c:133
static char * buf
Definition: pg_test_fsync.c:67
unsigned int uint32
Definition: c.h:374
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:691

◆ pg_rightmost_one_pos32()

static int pg_rightmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 85 of file pg_bitutils.h.

References Assert, and pg_rightmost_one_pos.

86 {
87 #ifdef HAVE__BUILTIN_CTZ
88  Assert(word != 0);
89 
90  return __builtin_ctz(word);
91 #else
92  int result = 0;
93 
94  Assert(word != 0);
95 
96  while ((word & 255) == 0)
97  {
98  word >>= 8;
99  result += 8;
100  }
101  result += pg_rightmost_one_pos[word & 255];
102  return result;
103 #endif /* HAVE__BUILTIN_CTZ */
104 }
#define Assert(condition)
Definition: c.h:745
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62

◆ pg_rightmost_one_pos64()

static int pg_rightmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 111 of file pg_bitutils.h.

References Assert, and pg_rightmost_one_pos.

112 {
113 #ifdef HAVE__BUILTIN_CTZ
114  Assert(word != 0);
115 
116 #if defined(HAVE_LONG_INT_64)
117  return __builtin_ctzl(word);
118 #elif defined(HAVE_LONG_LONG_INT_64)
119  return __builtin_ctzll(word);
120 #else
121 #error must have a working 64-bit integer datatype
122 #endif
123 #else /* !HAVE__BUILTIN_CTZ */
124  int result = 0;
125 
126  Assert(word != 0);
127 
128  while ((word & 255) == 0)
129  {
130  word >>= 8;
131  result += 8;
132  }
133  result += pg_rightmost_one_pos[word & 255];
134  return result;
135 #endif /* HAVE__BUILTIN_CTZ */
136 }
#define Assert(condition)
Definition: c.h:745
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62

◆ pg_rotate_right32()

static uint32 pg_rotate_right32 ( uint32  word,
int  n 
)
inlinestatic

Definition at line 221 of file pg_bitutils.h.

References BITS_PER_BYTE, and word().

Referenced by ExecHashGetBucketAndBatch().

222 {
223  return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
224 }
#define BITS_PER_BYTE
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246

Variable Documentation

◆ pg_leftmost_one_pos

PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]

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]

Definition at line 87 of file pg_bitutils.c.

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

◆ pg_popcount32

int(* pg_popcount32) (uint32 word)

Definition at line 132 of file pg_bitutils.c.

Referenced by pg_ceil_log2_64(), and pg_popcount().

◆ pg_popcount64

int(* pg_popcount64) (uint64 word)

Definition at line 133 of file pg_bitutils.c.

Referenced by pg_ceil_log2_64(), pg_popcount(), and visibilitymap_count().

◆ pg_rightmost_one_pos

PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]

Definition at line 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().