diff options
Diffstat (limited to 'src/backend/nodes/bitmapset.c')
| -rw-r--r-- | src/backend/nodes/bitmapset.c | 131 |
1 files changed, 24 insertions, 107 deletions
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index 62cd00903c0..d0380abf3e4 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -22,6 +22,7 @@ #include "access/hash.h" #include "nodes/pg_list.h" +#include "port/pg_bitutils.h" #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) @@ -51,79 +52,23 @@ #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) +/* Set the bitwise macro version we must use based on the bitmapword size */ +#if BITS_PER_BITMAPWORD == 32 -/* - * Lookup tables to avoid need for bit-by-bit groveling - * - * rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit - * in a nonzero byte value x. The entry for x=0 is never used. - * - * leftmost_one_pos[x] gives the bit number (0-7) of the leftmost one bit in a - * nonzero byte value x. The entry for x=0 is never used. - * - * number_of_ones[x] gives the number of one-bits (0-8) in a byte value x. - * - * We could make these tables larger and reduce the number of iterations - * in the functions that use them, but bytewise shifts and masks are - * especially fast on many machines, so working a byte at a time seems best. - */ +#define bmw_popcount(w) pg_popcount32(w) +#define bmw_rightmost_one(w) pg_rightmost_one32(w) +#define bmw_leftmost_one(w) pg_leftmost_one32(w) + +#elif BITS_PER_BITMAPWORD == 64 + +#define bmw_popcount(w) pg_popcount64(w) +#define bmw_rightmost_one(w) pg_rightmost_one64(w) +#define bmw_leftmost_one(w) pg_leftmost_one64(w) + +#else +#error "invalid BITS_PER_BITMAPWORD" +#endif -static const uint8 rightmost_one_pos[256] = { - 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 -}; - -static const uint8 leftmost_one_pos[256] = { - 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, - 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, - 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, - 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 -}; - -static const uint8 number_of_ones[256] = { - 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 -}; /* @@ -607,12 +552,7 @@ bms_singleton_member(const Bitmapset *a) if (result >= 0 || HAS_MULTIPLE_ONES(w)) elog(ERROR, "bitmapset has multiple members"); result = wordnum * BITS_PER_BITMAPWORD; - while ((w & 255) == 0) - { - w >>= 8; - result += 8; - } - result += rightmost_one_pos[w & 255]; + result += bmw_rightmost_one(w); } } if (result < 0) @@ -650,12 +590,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member) if (result >= 0 || HAS_MULTIPLE_ONES(w)) return false; result = wordnum * BITS_PER_BITMAPWORD; - while ((w & 255) == 0) - { - w >>= 8; - result += 8; - } - result += rightmost_one_pos[w & 255]; + result += bmw_rightmost_one(w); } } if (result < 0) @@ -681,12 +616,9 @@ bms_num_members(const Bitmapset *a) { bitmapword w = a->words[wordnum]; - /* we assume here that bitmapword is an unsigned type */ - while (w != 0) - { - result += number_of_ones[w & 255]; - w >>= 8; - } + /* No need to count the bits in a zero word */ + if (w != 0) + result += bmw_popcount(w); } return result; } @@ -1041,12 +973,7 @@ bms_first_member(Bitmapset *a) a->words[wordnum] &= ~w; result = wordnum * BITS_PER_BITMAPWORD; - while ((w & 255) == 0) - { - w >>= 8; - result += 8; - } - result += rightmost_one_pos[w & 255]; + result += bmw_rightmost_one(w); return result; } } @@ -1096,12 +1023,7 @@ bms_next_member(const Bitmapset *a, int prevbit) int result; result = wordnum * BITS_PER_BITMAPWORD; - while ((w & 255) == 0) - { - w >>= 8; - result += 8; - } - result += rightmost_one_pos[w & 255]; + result += bmw_rightmost_one(w); return result; } @@ -1168,14 +1090,9 @@ bms_prev_member(const Bitmapset *a, int prevbit) if (w != 0) { int result; - int shift = BITS_PER_BITMAPWORD - 8; result = wordnum * BITS_PER_BITMAPWORD; - - while ((w >> shift) == 0) - shift -= 8; - - result += shift + leftmost_one_pos[(w >> shift) & 255]; + result += bmw_leftmost_one(w); return result; } |