On Tue, Dec 6, 2022 at 12:57 PM Tom Lane <t...@sss.pgh.pa.us> wrote: > > Well, they've already escaped to tidbitmap.c as a copy. How do you feel > > about going that route? > > Not terribly pleased with that either, I must admit.
Okay, I won't pursue that further. > If we do put RIGHTMOST_ONE functionality into pg_bitutils.h, > I'd envision it as pg_bitutils.h exporting both 32-bit and > 64-bit versions of that, and then bitmapset.c choosing the > appropriate one just like it chooses bmw_rightmost_one_pos. Here's a quick go at that. I've not attempted to use it for what I need, but it looks like it fits the bill. -- John Naylor EDB: http://www.enterprisedb.com
src/backend/nodes/bitmapset.c | 36 ++---------------------------------- src/include/nodes/bitmapset.h | 16 ++++++++++++++-- src/include/port/pg_bitutils.h | 31 +++++++++++++++++++++++++++++++ src/tools/pgindent/typedefs.list | 1 - 4 files changed, 47 insertions(+), 37 deletions(-) diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index b7b274aeff..4384ff591d 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -32,39 +32,7 @@ #define BITMAPSET_SIZE(nwords) \ (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword)) -/*---------- - * This is a well-known cute trick for isolating the rightmost one-bit - * in a word. It assumes two's complement arithmetic. Consider any - * nonzero value, and focus attention on the rightmost one. The value is - * then something like - * xxxxxx10000 - * where x's are unspecified bits. The two's complement negative is formed - * by inverting all the bits and adding one. Inversion gives - * yyyyyy01111 - * where each y is the inverse of the corresponding x. Incrementing gives - * yyyyyy10000 - * and then ANDing with the original value gives - * 00000010000 - * This works for all cases except original value = zero, where of course - * we get zero. - *---------- - */ -#define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x))) - -#define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) - -/* Select appropriate bit-twiddling functions for bitmap word size */ -#if BITS_PER_BITMAPWORD == 32 -#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w) -#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w) -#define bmw_popcount(w) pg_popcount32(w) -#elif BITS_PER_BITMAPWORD == 64 -#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w) -#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w) -#define bmw_popcount(w) pg_popcount64(w) -#else -#error "invalid BITS_PER_BITMAPWORD" -#endif +#define HAS_MULTIPLE_ONES(x) (bmw_rightmost_one(x) != (x)) /* @@ -1013,7 +981,7 @@ bms_first_member(Bitmapset *a) { int result; - w = RIGHTMOST_ONE(w); + w = bmw_rightmost_one(w); a->words[wordnum] &= ~w; result = wordnum * BITS_PER_BITMAPWORD; diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h index 2792281658..fdc504596b 100644 --- a/src/include/nodes/bitmapset.h +++ b/src/include/nodes/bitmapset.h @@ -38,13 +38,11 @@ struct List; #define BITS_PER_BITMAPWORD 64 typedef uint64 bitmapword; /* must be an unsigned type */ -typedef int64 signedbitmapword; /* must be the matching signed type */ #else #define BITS_PER_BITMAPWORD 32 typedef uint32 bitmapword; /* must be an unsigned type */ -typedef int32 signedbitmapword; /* must be the matching signed type */ #endif @@ -75,6 +73,20 @@ typedef enum BMS_MULTIPLE /* >1 member */ } BMS_Membership; +/* Select appropriate bit-twiddling functions for bitmap word size */ +#if BITS_PER_BITMAPWORD == 32 +#define bmw_rightmost_one(w) pg_rightmost_one32(w) +#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w) +#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w) +#define bmw_popcount(w) pg_popcount32(w) +#elif BITS_PER_BITMAPWORD == 64 +#define bmw_rightmost_one(w) pg_rightmost_one64(w) +#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w) +#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w) +#define bmw_popcount(w) pg_popcount64(w) +#else +#error "invalid BITS_PER_BITMAPWORD" +#endif /* * function prototypes in nodes/bitmapset.c diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h index 814e0b2dba..f95b6afd86 100644 --- a/src/include/port/pg_bitutils.h +++ b/src/include/port/pg_bitutils.h @@ -17,6 +17,37 @@ extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]; extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]; extern PGDLLIMPORT const uint8 pg_number_of_ones[256]; +/*---------- + * This is a well-known cute trick for isolating the rightmost one-bit + * in a word. It assumes two's complement arithmetic. Consider any + * nonzero value, and focus attention on the rightmost one. The value is + * then something like + * xxxxxx10000 + * where x's are unspecified bits. The two's complement negative is formed + * by inverting all the bits and adding one. Inversion gives + * yyyyyy01111 + * where each y is the inverse of the corresponding x. Incrementing gives + * yyyyyy10000 + * and then ANDing with the original value gives + * 00000010000 + * This works for all cases except original value = zero, where of course + * we get zero. + *---------- + */ +static inline uint32 +pg_rightmost_one32(uint32 word) +{ + int32 result = (int32) word & -((int32) word); + return (uint32) result; +} + +static inline uint64 +pg_rightmost_one64(uint64 word) +{ + int64 result = (int64) word & -((int64) word); + return (uint64) result; +} + /* * pg_leftmost_one_pos32 * Returns the position of the most significant set bit in "word", diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 58daeca831..68df6ddc0b 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -3651,7 +3651,6 @@ shmem_request_hook_type shmem_startup_hook_type sig_atomic_t sigjmp_buf -signedbitmapword sigset_t size_t slist_head