From bd3dc494097811542fd0e9bd73d876f534543e54 Mon Sep 17 00:00:00 2001 From: "yizhi.fzh" Date: Tue, 20 Feb 2024 11:11:53 +0800 Subject: [PATCH v8 2/5] Introduce a Bitset data struct. While Bitmapset is designed for variable-length of bits, Bitset is designed for fixed-length of bits, the fixed length must be specified at the bitset_init stage and keep unchanged at the whole lifespan. Because of this, some operations on Bitset is simpler than Bitmapset. The bitset_clear unsets all the bits but kept the allocated memory, this capacity is impossible for bit Bitmapset for some solid reasons and this is the main reason to add this data struct. [1] https://postgr.es/m/CAApHDvpdp9LyAoMXvS7iCX-t3VonQM3fTWCmhconEvORrQ%2BZYA%40mail.gmail.com [2] https://postgr.es/m/875xzqxbv5.fsf%40163.com --- src/backend/nodes/bitmapset.c | 200 +++++++++++++++++- src/backend/nodes/outfuncs.c | 51 +++++ src/include/nodes/bitmapset.h | 28 +++ src/include/nodes/nodes.h | 4 + src/test/modules/test_misc/Makefile | 11 + src/test/modules/test_misc/README | 4 +- .../test_misc/expected/test_bitset.out | 7 + src/test/modules/test_misc/meson.build | 17 ++ .../modules/test_misc/sql/test_bitset.sql | 3 + src/test/modules/test_misc/test_misc--1.0.sql | 5 + src/test/modules/test_misc/test_misc.c | 118 +++++++++++ src/test/modules/test_misc/test_misc.control | 4 + src/tools/pgindent/typedefs.list | 1 + 13 files changed, 441 insertions(+), 12 deletions(-) create mode 100644 src/test/modules/test_misc/expected/test_bitset.out create mode 100644 src/test/modules/test_misc/sql/test_bitset.sql create mode 100644 src/test/modules/test_misc/test_misc--1.0.sql create mode 100644 src/test/modules/test_misc/test_misc.c create mode 100644 src/test/modules/test_misc/test_misc.control diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index 65805d4527..40cfea2308 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -1315,23 +1315,18 @@ bms_join(Bitmapset *a, Bitmapset *b) * It makes no difference in simple loop usage, but complex iteration logic * might need such an ability. */ -int -bms_next_member(const Bitmapset *a, int prevbit) + +static int +bms_next_member_internal(int nwords, const bitmapword *words, int prevbit) { - int nwords; int wordnum; bitmapword mask; - Assert(bms_is_valid_set(a)); - - if (a == NULL) - return -2; - nwords = a->nwords; prevbit++; mask = (~(bitmapword) 0) << BITNUM(prevbit); for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++) { - bitmapword w = a->words[wordnum]; + bitmapword w = words[wordnum]; /* ignore bits before prevbit */ w &= mask; @@ -1351,6 +1346,19 @@ bms_next_member(const Bitmapset *a, int prevbit) return -2; } +int +bms_next_member(const Bitmapset *a, int prevbit) +{ + Assert(a == NULL || IsA(a, Bitmapset)); + + Assert(bms_is_valid_set(a)); + + if (a == NULL) + return -2; + + return bms_next_member_internal(a->nwords, a->words, prevbit); +} + /* * bms_prev_member - find prev member of a set * @@ -1458,3 +1466,177 @@ bitmap_match(const void *key1, const void *key2, Size keysize) return !bms_equal(*((const Bitmapset *const *) key1), *((const Bitmapset *const *) key2)); } + +/* + * bitset_init - create a Bitset. the set will be round up to nwords; + */ +Bitset * +bitset_init(size_t size) +{ + int nword = (size + BITS_PER_BITMAPWORD - 1) / BITS_PER_BITMAPWORD; + Bitset *result; + + if (size == 0) + return NULL; + + result = (Bitset *) palloc0(sizeof(Bitset) + nword * sizeof(bitmapword)); + result->nwords = nword; + + return result; +} + +/* + * bitset_clear - clear the bits only, but the memory is still there. + */ +void +bitset_clear(Bitset *a) +{ + if (a != NULL) + memset(a->words, 0, sizeof(bitmapword) * a->nwords); +} + +void +bitset_free(Bitset *a) +{ + if (a != NULL) + pfree(a); +} + +bool +bitset_is_empty(Bitset *a) +{ + int i; + + if (a == NULL) + return true; + + for (i = 0; i < a->nwords; i++) + { + bitmapword w = a->words[i]; + + if (w != 0) + return false; + } + + return true; +} + +Bitset * +bitset_copy(Bitset *a) +{ + Bitset *result; + + if (a == NULL) + return NULL; + + result = bitset_init(a->nwords * BITS_PER_BITMAPWORD); + + memcpy(result->words, a->words, sizeof(bitmapword) * a->nwords); + return result; +} + +void +bitset_add_member(Bitset *a, int x) +{ + int wordnum, + bitnum; + + Assert(x >= 0); + + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + + Assert(wordnum < a->nwords); + + a->words[wordnum] |= ((bitmapword) 1 << bitnum); +} + +void +bitset_del_member(Bitset *a, int x) +{ + int wordnum, + bitnum; + + Assert(x >= 0); + + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + + Assert(wordnum < a->nwords); + + a->words[wordnum] &= ~((bitmapword) 1 << bitnum); +} + +int +bitset_is_member(int x, Bitset *a) +{ + int wordnum, + bitnum; + + /* used in expression engine */ + Assert(x >= 0); + + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + + if (a == NULL) + return false; + + if (wordnum >= a->nwords) + return false; + + return (a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0; +} + +int +bitset_next_member(const Bitset *a, int prevbit) +{ + if (a == NULL) + return -2; + + return bms_next_member_internal(a->nwords, a->words, prevbit); +} + + +/* + * bitset_to_bitmap - build a legal bitmapset from bitset. + */ +Bitmapset * +bitset_to_bitmap(Bitset *a) +{ + int n; + + bool found = false; /* any non-empty bits */ + Bitmapset *result; + int i; + + if (a == NULL) + return NULL; + + n = a->nwords - 1; + do + { + if (a->words[n] > 0) + { + found = true; + break; + } + } while (--n >= 0); + + if (!found) + return NULL; + + result = (Bitmapset *) palloc0(BITMAPSET_SIZE(n + 1)); + result->type = T_Bitmapset; + result->nwords = n + 1; + + Assert(result->nwords <= a->nwords); + + i = 0; + do + { + result->words[i] = a->words[i]; + } while (++i < result->nwords); + + return result; +} diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 2c30bba212..f2ee806ef1 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -331,6 +331,43 @@ outBitmapset(StringInfo str, const Bitmapset *bms) appendStringInfoChar(str, ')'); } + + +/* + * outBitset - + * similar to outBitmapset, but for Bitset. + */ +static void +outBitsetInternal(struct StringInfoData *str, + const struct Bitset *bs, + bool asBitmap) +{ + int x; + + appendStringInfoChar(str, '('); + if (asBitmap) + appendStringInfoChar(str, 'b'); + else + appendStringInfo(str, "bs"); + x = -1; + while ((x = bitset_next_member(bs, x)) >= 0) + appendStringInfo(str, " %d", x); + appendStringInfoChar(str, ')'); +} + + +/* + * outBitset - + * similar to outBitmapset, but for Bitset. + */ +void +outBitset(struct StringInfoData *str, + const struct Bitset *bs) +{ + outBitsetInternal(str, bs, false); +} + + /* * Print the value of a Datum given its type. */ @@ -783,3 +820,17 @@ bmsToString(const Bitmapset *bms) outBitmapset(&str, bms); return str.data; } + +/* + * bitsetToString - + * similar to bmsToString, but for Bitset + */ +char * +bitsetToString(const struct Bitset *bs, bool asBitmap) +{ + StringInfoData str; + + initStringInfo(&str); + outBitsetInternal(&str, bs, asBitmap); + return str.data; +} diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h index 906e8dcc15..95ff37c6e9 100644 --- a/src/include/nodes/bitmapset.h +++ b/src/include/nodes/bitmapset.h @@ -55,6 +55,24 @@ typedef struct Bitmapset bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */ } Bitmapset; +/* + * While Bitmapset is designed for variable-length of bits, Bitset is + * designed for fixed-length of bits, the fixed length must be specified at + * the bitset_init stage and keep unchanged at the whole lifespan. Because + * of this, some operations on Bitset is simpler than Bitmapset. + * + * The bitset_clear unsets all the bits but kept the allocated memory, this + * capacity is impossible for bit Bitmapset for some solid reasons. + * + * Also for performance aspect, the functions for Bitset removed some + * unlikely checks, instead with some Asserts. + */ + +typedef struct Bitset +{ + int nwords; /* number of words in array */ + bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */ +} Bitset; /* result of bms_subset_compare */ typedef enum @@ -124,4 +142,14 @@ extern uint32 bms_hash_value(const Bitmapset *a); extern uint32 bitmap_hash(const void *key, Size keysize); extern int bitmap_match(const void *key1, const void *key2, Size keysize); +extern Bitset *bitset_init(size_t size); +extern void bitset_clear(Bitset *a); +extern void bitset_free(Bitset *a); +extern bool bitset_is_empty(Bitset *a); +extern Bitset *bitset_copy(Bitset *a); +extern void bitset_add_member(Bitset *a, int x); +extern void bitset_del_member(Bitset *a, int x); +extern int bitset_is_member(int bit, Bitset *a); +extern int bitset_next_member(const Bitset *a, int prevbit); +extern Bitmapset *bitset_to_bitmap(Bitset *a); #endif /* BITMAPSET_H */ diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 2969dd831b..4d13107990 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -186,16 +186,20 @@ castNodeImpl(NodeTag type, void *ptr) * nodes/{outfuncs.c,print.c} */ struct Bitmapset; /* not to include bitmapset.h here */ +struct Bitset; /* not to include bitmapset.h here */ struct StringInfoData; /* not to include stringinfo.h here */ extern void outNode(struct StringInfoData *str, const void *obj); extern void outToken(struct StringInfoData *str, const char *s); extern void outBitmapset(struct StringInfoData *str, const struct Bitmapset *bms); +extern void outBitset(struct StringInfoData *str, const struct Bitset *bs); + extern void outDatum(struct StringInfoData *str, uintptr_t value, int typlen, bool typbyval); extern char *nodeToString(const void *obj); extern char *bmsToString(const struct Bitmapset *bms); +extern char *bitsetToString(const struct Bitset *bs, bool asBitmap); /* * nodes/{readfuncs.c,read.c} diff --git a/src/test/modules/test_misc/Makefile b/src/test/modules/test_misc/Makefile index 39c6c2014a..af96604096 100644 --- a/src/test/modules/test_misc/Makefile +++ b/src/test/modules/test_misc/Makefile @@ -2,6 +2,17 @@ TAP_TESTS = 1 +MODULE_big = test_misc +OBJS = \ + $(WIN32RES) \ + test_misc.o +PGFILEDESC = "test_misc" + +EXTENSION = test_misc +DATA = test_misc--1.0.sql + +REGRESS = test_bitset + ifdef USE_PGXS PG_CONFIG = pg_config PGXS := $(shell $(PG_CONFIG) --pgxs) diff --git a/src/test/modules/test_misc/README b/src/test/modules/test_misc/README index 4876733fa2..ec426c4ad5 100644 --- a/src/test/modules/test_misc/README +++ b/src/test/modules/test_misc/README @@ -1,4 +1,2 @@ -This directory doesn't actually contain any extension module. - -What it is is a home for otherwise-unclassified TAP tests that exercise core +What it is is a home for otherwise-unclassified tests that exercise core server features. We might equally well have called it, say, src/test/misc. diff --git a/src/test/modules/test_misc/expected/test_bitset.out b/src/test/modules/test_misc/expected/test_bitset.out new file mode 100644 index 0000000000..3d0302d30d --- /dev/null +++ b/src/test/modules/test_misc/expected/test_bitset.out @@ -0,0 +1,7 @@ +CREATE EXTENSION test_misc; +SELECT test_bitset(); + test_bitset +------------- + +(1 row) + diff --git a/src/test/modules/test_misc/meson.build b/src/test/modules/test_misc/meson.build index 964d95db26..a23f3e3f47 100644 --- a/src/test/modules/test_misc/meson.build +++ b/src/test/modules/test_misc/meson.build @@ -1,5 +1,22 @@ # Copyright (c) 2022-2024, PostgreSQL Global Development Group +test_misc_sources = files( + 'test_misc.c', +) + +if host_system == 'windows' + test_misc_sources += rc_lib_gen.process(win32ver_rc, extra_args: [ + '--NAME', 'test_misc', + '--FILEDESC', 'test_misc - ',]) +endif + +test_misc = shared_module('test_misc', + test_misc_sources, + kwargs: pg_test_mod_args, +) + +test_install_libs += test_misc + tests += { 'name': 'test_misc', 'sd': meson.current_source_dir(), diff --git a/src/test/modules/test_misc/sql/test_bitset.sql b/src/test/modules/test_misc/sql/test_bitset.sql new file mode 100644 index 0000000000..0f73bbf532 --- /dev/null +++ b/src/test/modules/test_misc/sql/test_bitset.sql @@ -0,0 +1,3 @@ +CREATE EXTENSION test_misc; + +SELECT test_bitset(); diff --git a/src/test/modules/test_misc/test_misc--1.0.sql b/src/test/modules/test_misc/test_misc--1.0.sql new file mode 100644 index 0000000000..79afaa6263 --- /dev/null +++ b/src/test/modules/test_misc/test_misc--1.0.sql @@ -0,0 +1,5 @@ +\echo Use "CREATE EXTENSION test_misc" to load this file. \quit + +CREATE FUNCTION test_bitset() + RETURNS pg_catalog.void + AS 'MODULE_PATHNAME' LANGUAGE C; diff --git a/src/test/modules/test_misc/test_misc.c b/src/test/modules/test_misc/test_misc.c new file mode 100644 index 0000000000..70d0255ada --- /dev/null +++ b/src/test/modules/test_misc/test_misc.c @@ -0,0 +1,118 @@ +/*-------------------------------------------------------------------------- + * + * test_misc.c + * + * Copyright (c) 2022-2024, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/test/modules/test_dsa/test_misc.c + * + * ------------------------------------------------------------------------- + */ +#include "postgres.h" +#include "fmgr.h" +#include "nodes/bitmapset.h" +#include "nodes/nodes.h" +#define BIT_ADD 0 +#define BIT_DEL 1 +#ifdef USE_ASSERT_CHECKING +static void compare_bms_bs(Bitmapset **bms, Bitset *bs, int member, int op); +#endif +PG_MODULE_MAGIC; +/* Test basic DSA functionality */ +PG_FUNCTION_INFO_V1(test_bitset); +Datum +test_bitset(PG_FUNCTION_ARGS) +{ +#ifdef USE_ASSERT_CHECKING + Bitset *bs; + Bitset *bs2; + char *str1, + *str2, + *empty_str; + Bitmapset *bms = NULL; + int i; + + empty_str = bmsToString(NULL); + /* size = 0 */ + bs = bitset_init(0); + Assert(bs == NULL); + bitset_clear(bs); + Assert(bitset_is_empty(bs)); + /* bitset_add_member(bs, 0); // crash. */ + /* bitset_del_member(bs, 0); // crash. */ + Assert(!bitset_is_member(0, bs)); + Assert(bitset_next_member(bs, -1) == -2); + bs2 = bitset_copy(bs); + Assert(bs2 == NULL); + bitset_free(bs); + bitset_free(bs2); + /* size == 68, nword == 2 */ + bs = bitset_init(68); + for (i = 0; i < 68; i = i + 3) + { + compare_bms_bs(&bms, bs, i, BIT_ADD); + } + Assert(!bitset_is_empty(bs)); + for (i = 0; i < 68; i = i + 3) + { + compare_bms_bs(&bms, bs, i, BIT_DEL); + } + Assert(bitset_is_empty(bs)); + bitset_clear(bs); + str1 = bitsetToString(bs, true); + Assert(strcmp(str1, empty_str) == 0); + bms = bitset_to_bitmap(bs); + str2 = bmsToString(bms); + Assert(strcmp(str1, str2) == 0); + bms = bitset_to_bitmap(NULL); + Assert(strcmp(bmsToString(bms), empty_str) == 0); + bitset_free(bs); +#endif + PG_RETURN_VOID(); +} +#ifdef USE_ASSERT_CHECKING +static void +compare_bms_bs(Bitmapset **bms, Bitset *bs, int member, int op) +{ + char *str1, + *str2, + *str3, + *str4; + Bitmapset *bms3; + Bitset *bs4; + + if (op == BIT_ADD) + { + *bms = bms_add_member(*bms, member); + bitset_add_member(bs, member); + Assert(bms_is_member(member, *bms)); + Assert(bitset_is_member(member, bs)); + } + else if (op == BIT_DEL) + { + *bms = bms_del_member(*bms, member); + bitset_del_member(bs, member); + Assert(!bms_is_member(member, *bms)); + Assert(!bitset_is_member(member, bs)); + } + else + Assert(false); + /* compare the rest existing bit */ + str1 = bmsToString(*bms); + str2 = bitsetToString(bs, true); + Assert(strcmp(str1, str2) == 0); + /* test bitset_to_bitmap */ + bms3 = bitset_to_bitmap(bs); + str3 = bmsToString(bms3); + Assert(strcmp(str3, str2) == 0); + /* test bitset_copy */ + bs4 = bitset_copy(bs); + str4 = bitsetToString(bs4, true); + Assert(strcmp(str3, str4) == 0); + pfree(str1); + pfree(str2); + pfree(str3); + pfree(str4); +} +#endif diff --git a/src/test/modules/test_misc/test_misc.control b/src/test/modules/test_misc/test_misc.control new file mode 100644 index 0000000000..48fd08758f --- /dev/null +++ b/src/test/modules/test_misc/test_misc.control @@ -0,0 +1,4 @@ +comment = 'Test misc' +default_version = '1.0' +module_pathname = '$libdir/test_misc' +relocatable = true diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index ac55727e05..152e586252 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -268,6 +268,7 @@ BitmapOr BitmapOrPath BitmapOrState Bitmapset +Bitset Block BlockId BlockIdData -- 2.34.1