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

{
    if (num < 2)
        return 0;
    else
        return pg_leftmost_one_pos32(num - 1) + 1;
}

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

{
    if (num < 2)
        return 0;
    else
        return pg_leftmost_one_pos64(num - 1) + 1;
}

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(), pg_ceil_log2_32(), and pg_nextpower2_32().

{
#ifdef HAVE__BUILTIN_CLZ
    Assert(word != 0);

    return 31 - __builtin_clz(word);
#else
    int         shift = 32 - 8;

    Assert(word != 0);

    while ((word >> shift) == 0)
        shift -= 8;

    return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif                          /* HAVE__BUILTIN_CLZ */
}

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

{
#ifdef HAVE__BUILTIN_CLZ
    Assert(word != 0);

#if defined(HAVE_LONG_INT_64)
    return 63 - __builtin_clzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
    return 63 - __builtin_clzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else                           /* !HAVE__BUILTIN_CLZ */
    int         shift = 64 - 8;

    Assert(word != 0);

    while ((word >> shift) == 0)
        shift -= 8;

    return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif                          /* HAVE__BUILTIN_CLZ */
}

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(), and new_list().

{
    Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);

    /*
     * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     * will turn on all previous bits resulting in no common bits being set
     * between num and num-1.
     */
    if ((num & (num - 1)) == 0)
        return num;             /* already power 2 */

    return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
}

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.

{
    Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);

    /*
     * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     * will turn on all previous bits resulting in no common bits being set
     * between num and num-1.
     */
    if ((num & (num - 1)) == 0)
        return num;             /* already power 2 */

    return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
}

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

{
    uint64      popcnt = 0;

#if SIZEOF_VOID_P >= 8
    /* Process in 64-bit chunks if the buffer is aligned. */
    if (buf == (const char *) TYPEALIGN(8, buf))
    {
        const uint64 *words = (const uint64 *) buf;

        while (bytes >= 8)
        {
            popcnt += pg_popcount64(*words++);
            bytes -= 8;
        }

        buf = (const char *) words;
    }
#else
    /* Process in 32-bit chunks if the buffer is aligned. */
    if (buf == (const char *) TYPEALIGN(4, buf))
    {
        const uint32 *words = (const uint32 *) buf;

        while (bytes >= 4)
        {
            popcnt += pg_popcount32(*words++);
            bytes -= 4;
        }

        buf = (const char *) words;
    }
#endif

    /* Process any remaining bytes */
    while (bytes--)
        popcnt += pg_number_of_ones[(unsigned char) *buf++];

    return popcnt;
}

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.

{
#ifdef HAVE__BUILTIN_CTZ
    Assert(word != 0);

    return __builtin_ctz(word);
#else
    int         result = 0;

    Assert(word != 0);

    while ((word & 255) == 0)
    {
        word >>= 8;
        result += 8;
    }
    result += pg_rightmost_one_pos[word & 255];
    return result;
#endif                          /* HAVE__BUILTIN_CTZ */
}

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.

{
#ifdef HAVE__BUILTIN_CTZ
    Assert(word != 0);

#if defined(HAVE_LONG_INT_64)
    return __builtin_ctzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
    return __builtin_ctzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else                           /* !HAVE__BUILTIN_CTZ */
    int         result = 0;

    Assert(word != 0);

    while ((word & 255) == 0)
    {
        word >>= 8;
        result += 8;
    }
    result += pg_rightmost_one_pos[word & 255];
    return result;
#endif                          /* HAVE__BUILTIN_CTZ */
}

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

{
    return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
}

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