diff options
Diffstat (limited to 'src/backend/nodes/bitmapset.c')
| -rw-r--r-- | src/backend/nodes/bitmapset.c | 131 |
1 files changed, 107 insertions, 24 deletions
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index d0380abf3e4..62cd00903c0 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -22,7 +22,6 @@ #include "access/hash.h" #include "nodes/pg_list.h" -#include "port/pg_bitutils.h" #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) @@ -52,23 +51,79 @@ #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 -#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 +/* + * 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. + */ +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 +}; /* @@ -552,7 +607,12 @@ bms_singleton_member(const Bitmapset *a) if (result >= 0 || HAS_MULTIPLE_ONES(w)) elog(ERROR, "bitmapset has multiple members"); result = wordnum * BITS_PER_BITMAPWORD; - result += bmw_rightmost_one(w); + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; } } if (result < 0) @@ -590,7 +650,12 @@ bms_get_singleton_member(const Bitmapset *a, int *member) if (result >= 0 || HAS_MULTIPLE_ONES(w)) return false; result = wordnum * BITS_PER_BITMAPWORD; - result += bmw_rightmost_one(w); + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; } } if (result < 0) @@ -616,9 +681,12 @@ bms_num_members(const Bitmapset *a) { bitmapword w = a->words[wordnum]; - /* No need to count the bits in a zero word */ - if (w != 0) - result += bmw_popcount(w); + /* we assume here that bitmapword is an unsigned type */ + while (w != 0) + { + result += number_of_ones[w & 255]; + w >>= 8; + } } return result; } @@ -973,7 +1041,12 @@ bms_first_member(Bitmapset *a) a->words[wordnum] &= ~w; result = wordnum * BITS_PER_BITMAPWORD; - result += bmw_rightmost_one(w); + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; return result; } } @@ -1023,7 +1096,12 @@ bms_next_member(const Bitmapset *a, int prevbit) int result; result = wordnum * BITS_PER_BITMAPWORD; - result += bmw_rightmost_one(w); + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; return result; } @@ -1090,9 +1168,14 @@ bms_prev_member(const Bitmapset *a, int prevbit) if (w != 0) { int result; + int shift = BITS_PER_BITMAPWORD - 8; result = wordnum * BITS_PER_BITMAPWORD; - result += bmw_leftmost_one(w); + + while ((w >> shift) == 0) + shift -= 8; + + result += shift + leftmost_one_pos[(w >> shift) & 255]; return result; } |