From 314a41be6b39b6c5967d79555dbf018dbc7eb5f6 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 22 May 2022 20:45:31 +0200 Subject: Rewrote cbits to make it dual: fixed-sized or dynamically sized by adding optional i_len template parameter. Renamed cbits_set_values() to cbits_set_pattern(). Added example bits2.c --- docs/cbits_api.md | 15 +-- examples/bits.c | 26 ++--- examples/bits2.c | 42 ++++++++ include/stc/cbits.h | 285 +++++++++++++++++++++++++++++++--------------------- 4 files changed, 234 insertions(+), 134 deletions(-) create mode 100644 examples/bits2.c diff --git a/docs/cbits_api.md b/docs/cbits_api.md index b9cf5069..b9d54737 100644 --- a/docs/cbits_api.md +++ b/docs/cbits_api.md @@ -1,7 +1,7 @@ # STC [cbits](../include/stc/cbits.h): Bitset ![Bitset](pics/bitset.jpg) -A **cbits** represents a set of bits. It provides accesses to the value of individual bits via *cbits_test()* and provides the bitwise operators that one can apply to builtin integers. The number of bits in the set is specified at runtime via a parameter to the constructor *cbits_with_size()* or by *cbits_resize()*. A **cbits** bitset can be manipulated by standard logic operators and converted to and from strings. +A **cbits** represents either a fixed or a dynamically sized sequence of bits. It provides accesses to the value of individual bits via *cbits_test()* and provides the bitwise operators that one can apply to builtin integers. The number of bits in the set is specified at runtime via a parameter to the constructor *cbits_with_size()* or by *cbits_resize()*. A **cbits** bitset can be manipulated by standard logic operators and converted to and from strings. See the c++ class [std::bitset](https://en.cppreference.com/w/cpp/utility/bitset) or [boost::dynamic_bitset](https://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html) @@ -12,21 +12,22 @@ for a functional description. All cbits definitions and prototypes are available by including a single header file. ```c +#define i_len N // if defined, the bitset will be fixed-size of N bits on the stack. +#define i_type name // optional, specifies the name of the bitset type. Default to cbits or cbitsN #include ``` ## Methods ```c cbits cbits_init(void); -cbits cbits_new(const char literal[]); cbits cbits_from(const char* str); -cbits cbits_with_size(size_t size, bool value); -cbits cbits_with_values(size_t size, uint64_t pattern); +cbits cbits_with_size(size_t size, bool value); // size must be <= N if N is defined +cbits cbits_with_pattern(size_t size, uint64_t pattern); cbits cbits_clone(cbits other); void cbits_clear(cbits* self); cbits* cbits_copy(cbits* self, cbits other); -void cbits_resize(cbits* self, size_t size, bool value); +void cbits_resize(cbits* self, size_t size, bool value); // only if i_len is not defined void cbits_drop(cbits* self); cbits* cbits_take(cbits* self, cbits other); // give other to self @@ -43,9 +44,9 @@ char* cbits_to_str(cbits set, char* str, size_t start, intptr_t stop) void cbits_set(cbits *self, size_t i); void cbits_reset(cbits *self, size_t i); -void cbits_set_all(cbits *self, bool value); void cbits_set_value(cbits *self, size_t i, bool value); -void cbits_set_values(cbits *self, uint64_t pattern); +void cbits_set_all(cbits *self, bool value); +void cbits_set_pattern(cbits *self, uint64_t pattern); void cbits_flip_all(cbits *self); void cbits_flip(cbits *self, size_t i); diff --git a/examples/bits.c b/examples/bits.c index 680b3501..bd2a9f03 100644 --- a/examples/bits.c +++ b/examples/bits.c @@ -4,8 +4,8 @@ int main() { c_autovar (cbits set = cbits_with_size(23, true), cbits_drop(&set)) { - printf("count %" PRIuMAX ", %" PRIuMAX "\n", cbits_count(set), set.size); - cbits s1 = cbits_new("1110100110111"); + printf("count %" PRIuMAX ", %" PRIuMAX "\n", cbits_count(set), cbits_size(set)); + cbits s1 = cbits_from("1110100110111"); char buf[256]; cbits_to_str(s1, buf, 0, -1); printf("buf: %s: %" PRIuMAX "\n", buf, cbits_count(s1)); @@ -13,11 +13,11 @@ int main() cbits_reset(&set, 9); cbits_resize(&set, 43, false); - c_autobuf (str, char, set.size + 1) + c_autobuf (str, char, cbits_size(set) + 1) printf(" str: %s\n", cbits_to_str(set, str, 0, -1)); - printf("%4" PRIuMAX ": ", set.size); - c_forrange (i, set.size) + printf("%4" PRIuMAX ": ", cbits_size(set)); + c_forrange (i, cbits_size(set)) printf("%d", cbits_test(set, i)); puts(""); @@ -26,13 +26,13 @@ int main() cbits_resize(&set, 93, false); cbits_resize(&set, 102, true); cbits_set_value(&set, 99, false); - printf("%4" PRIuMAX ": ", set.size); - c_forrange (i, set.size) + printf("%4" PRIuMAX ": ", cbits_size(set)); + c_forrange (i, cbits_size(set)) printf("%d", cbits_test(set, i)); puts("\nIterate:"); - printf("%4" PRIuMAX ": ", set.size); - c_forrange (i, set.size) + printf("%4" PRIuMAX ": ", cbits_size(set)); + c_forrange (i, cbits_size(set)) printf("%d", cbits_test(set, i)); puts(""); @@ -42,19 +42,19 @@ int main() cbits_set(&s2, 17); cbits_set(&s2, 18); printf(" new: "); - c_forrange (i, s2.size) + c_forrange (i, cbits_size(s2)) printf("%d", cbits_test(s2, i)); puts(""); printf(" xor: "); cbits_xor(&set, s2); - c_forrange (i, set.size) + c_forrange (i, cbits_size(set)) printf("%d", cbits_test(set, i)); puts(""); cbits_set_all(&set, false); - printf("%4" PRIuMAX ": ", set.size); - c_forrange (i, set.size) + printf("%4" PRIuMAX ": ", cbits_size(set)); + c_forrange (i, cbits_size(set)) printf("%d", cbits_test(set, i)); puts(""); } diff --git a/examples/bits2.c b/examples/bits2.c new file mode 100644 index 00000000..e9202efc --- /dev/null +++ b/examples/bits2.c @@ -0,0 +1,42 @@ +#include +// Example of static sized (stack allocated) bitsets + +#define i_type Bits +#define i_len 80 // enable fixed bitset on the stack +#include + +int main() +{ + Bits s1 = Bits_from("1110100110111"); + + printf("size %" PRIuMAX "\n", Bits_size(s1)); + char buf[256]; + Bits_to_str(s1, buf, 0, -1); + printf("buf: %s: count=%" PRIuMAX "\n", buf, Bits_count(s1)); + + Bits_reset(&s1, 8); + c_autobuf (str, char, Bits_size(s1) + 1) + printf(" s1: %s\n", Bits_to_str(s1, str, 0, -1)); + + Bits s2 = Bits_clone(s1); + + Bits_flip_all(&s2); + Bits_reset(&s2, 66); + Bits_reset(&s2, 67); + printf(" s2: "); + c_forrange (i, Bits_size(s2)) + printf("%d", Bits_test(s2, i)); + puts(""); + + printf("xor: "); + Bits_xor(&s1, s2); + c_forrange (i, Bits_size(s1)) + printf("%d", Bits_test(s1, i)); + puts(""); + + printf("all: "); + Bits_set_pattern(&s1, 0x3333333333333333); + c_forrange (i, Bits_size(s1)) + printf("%d", Bits_test(s1, i)); + puts(""); +} diff --git a/include/stc/cbits.h b/include/stc/cbits.h index 8964c275..07b752bd 100644 --- a/include/stc/cbits.h +++ b/include/stc/cbits.h @@ -34,8 +34,8 @@ int main() { cbits_reset(&bset, 9); cbits_resize(&bset, 43, false); - printf("%4zu: ", bset.size); - c_forrange (i, bset.size) + printf("%4zu: ", cbits_size(bset)); + c_forrange (i, cbits_size(bset)) printf("%d", cbits_at(&bset, i)); puts(""); cbits_set(&bset, 28); @@ -44,8 +44,8 @@ int main() { cbits_resize(&bset, 102, true); cbits_set_value(&bset, 99, false); - printf("%4zu: ", bset.size); - c_forrange (i, bset.size) + printf("%4zu: ", cbits_size(bset)); + c_forrange (i, cbits_size(bset)) printf("%d", cbits_at(&bset, i)); puts(""); } @@ -55,100 +55,116 @@ int main() { #include #include -struct cbits { - uint64_t *data64; - size_t size; -} typedef cbits; - -STC_API cbits cbits_from_n(const char* str, size_t n); -STC_API cbits cbits_with_size(size_t size, bool value); -STC_API cbits cbits_with_values(size_t size, uint64_t pattern); -STC_API char* cbits_to_str(cbits set, char* str, size_t start, intptr_t stop); -STC_API cbits cbits_clone(cbits other); -STC_API void cbits_resize(cbits* self, size_t size, bool value); -STC_API cbits* cbits_copy(cbits* self, cbits other); -STC_API size_t cbits_count(cbits set); -STC_API bool cbits_subset_of(cbits set, cbits other); -STC_API bool cbits_disjoint(cbits set, cbits other); - -STC_INLINE cbits cbits_init() { return c_make(cbits){NULL, 0}; } -STC_INLINE cbits cbits_from(const char* s) { return cbits_from_n(s, strlen(s)); } -STC_INLINE void cbits_clear(cbits* self) { self->size = 0; } -STC_INLINE void cbits_drop(cbits* self) { c_free(self->data64); } -STC_INLINE size_t cbits_size(cbits set) { return set.size; } +#if !defined i_type && defined i_len + #define i_type c_paste(cbits, i_len) +#elif !defined i_type + #define i_type cbits +#endif +#define _i_memb(name) c_paste(i_type, name) +#ifdef i_len + struct { uint64_t data64[(i_len - 1)/64 + 1]; } typedef i_type; +#else + struct { uint64_t *data64; size_t _size; } typedef i_type; +#endif #define _cbits_bit(i) ((uint64_t)1 << ((i) & 63)) -#define _cbits_words(n) (((n) + 63) >> 6) +#define _cbits_words(n) (((n) + 63)>>6) #define _cbits_bytes(n) (_cbits_words(n) * sizeof(uint64_t)) -#define cbits_new(literal) \ - cbits_from_n(literal, c_strlen_lit(literal)) +#ifndef i_len +STC_API void _i_memb(_resize)(i_type* self, size_t size, bool value); +#endif +STC_API i_type _i_memb(_with_size)(size_t size, bool value); +STC_API i_type _i_memb(_with_pattern)(size_t size, uint64_t pattern); +STC_API i_type _i_memb(_from_n)(const char* str, size_t n); +STC_API i_type* _i_memb(_copy)(i_type* self, i_type other); +STC_API i_type _i_memb(_clone)(i_type other); +STC_API size_t _i_memb(_count)(i_type set); +STC_API bool _i_memb(_subset_of)(i_type set, i_type other); +STC_API bool _i_memb(_disjoint)(i_type set, i_type other); +STC_API char* _i_memb(_to_str)(i_type set, char* str, size_t start, intptr_t stop); -STC_INLINE cbits* cbits_take(cbits* self, cbits other) { - if (self->data64 != other.data64) {cbits_drop(self); *self = other;} - return self; -} +#ifdef i_len +#define _i_assert(x) (void)0 +STC_INLINE i_type _i_memb(_init)(void) { return c_make(i_type){0}; } +STC_INLINE void _i_memb(_drop)(i_type* self) {} +STC_INLINE size_t _i_memb(_size)(i_type set) { return i_len; } +STC_INLINE i_type _i_memb(_move)(i_type* self) { return *self; } +STC_INLINE i_type* _i_memb(_take)(i_type* self, i_type other) + { *self = other; return self; } +#else +#define _i_assert(x) assert(x) +STC_INLINE i_type _i_memb(_init)(void) { return c_make(i_type){NULL}; } +STC_INLINE void _i_memb(_drop)(i_type* self) { c_free(self->data64); } +STC_INLINE size_t _i_memb(_size)(i_type set) { return set._size; } -STC_INLINE cbits cbits_move(cbits* self) { - cbits tmp = *self; self->data64 = NULL, self->size = 0; +STC_INLINE i_type _i_memb(_move)(i_type* self) { + i_type tmp = *self; + self->data64 = NULL, self->_size = 0; return tmp; } -STC_INLINE bool cbits_test(cbits set, const size_t i) { - return (set.data64[i >> 6] & _cbits_bit(i)) != 0; +STC_INLINE i_type* _i_memb(_take)(i_type* self, i_type other) { + if (self->data64 != other.data64) { + _i_memb(_drop)(self); + *self = other; + } + return self; } +#endif -STC_INLINE bool cbits_at(cbits set, const size_t i) { - return (set.data64[i >> 6] & _cbits_bit(i)) != 0; -} +STC_INLINE i_type _i_memb(_from)(const char* s) + { return _i_memb(_from_n)(s, strlen(s)); } -STC_INLINE void cbits_set(cbits *self, const size_t i) { - self->data64[i >> 6] |= _cbits_bit(i); -} +STC_INLINE bool _i_memb(_test)(i_type set, const size_t i) + { return (set.data64[i>>6] & _cbits_bit(i)) != 0; } -STC_INLINE void cbits_reset(cbits *self, const size_t i) { - self->data64[i >> 6] &= ~_cbits_bit(i); -} +STC_INLINE bool _i_memb(_at)(i_type set, const size_t i) + { return (set.data64[i>>6] & _cbits_bit(i)) != 0; } -STC_INLINE void cbits_set_value(cbits *self, const size_t i, const bool value) { - self->data64[i >> 6] ^= ((uint64_t)-(int)value ^ self->data64[i >> 6]) & _cbits_bit(i); -} +STC_INLINE void _i_memb(_set)(i_type *self, const size_t i) + { self->data64[i>>6] |= _cbits_bit(i); } -STC_INLINE void cbits_flip(cbits *self, const size_t i) { - self->data64[i >> 6] ^= _cbits_bit(i); -} +STC_INLINE void _i_memb(_reset)(i_type *self, const size_t i) + { self->data64[i>>6] &= ~_cbits_bit(i); } -STC_INLINE void cbits_set_all(cbits *self, const bool value) { - memset(self->data64, -(int)value, _cbits_bytes(self->size)); +STC_INLINE void _i_memb(_set_value)(i_type *self, const size_t i, const bool value) { + self->data64[i>>6] ^= ((uint64_t)-(int)value ^ self->data64[i>>6]) & _cbits_bit(i); } -STC_INLINE void cbits_set_values(cbits *self, const uint64_t pattern) { - size_t n = _cbits_words(self->size); - for (size_t i=0; idata64[i] = pattern; +STC_INLINE void _i_memb(_flip)(i_type *self, const size_t i) + { self->data64[i>>6] ^= _cbits_bit(i); } + +STC_INLINE void _i_memb(_set_all)(i_type *self, const bool value) + { memset(self->data64, value? ~0 : 0, _cbits_bytes(_i_memb(_size)(*self))); } + +STC_INLINE void _i_memb(_set_pattern)(i_type *self, const uint64_t pattern) { + size_t n = _cbits_words(_i_memb(_size)(*self)); + while (n--) self->data64[n] = pattern; } -STC_INLINE void cbits_flip_all(cbits *self) { - size_t n = _cbits_words(self->size); - for (size_t i=0; idata64[i] ^= ~(uint64_t)0; +STC_INLINE void _i_memb(_flip_all)(i_type *self) { + size_t n = _cbits_words(_i_memb(_size)(*self)); + while (n--) self->data64[n] ^= ~(uint64_t)0; } /* Intersection */ -STC_INLINE void cbits_intersect(cbits *self, cbits other) { - assert(self->size == other.size); - size_t n = _cbits_words(self->size); - for (size_t i=0; idata64[i] &= other.data64[i]; +STC_INLINE void _i_memb(_intersect)(i_type *self, i_type other) { + _i_assert(self->_size == other._size); + size_t n = _cbits_words(_i_memb(_size)(*self)); + while (n--) self->data64[n] &= other.data64[n]; } /* Union */ -STC_INLINE void cbits_union(cbits *self, cbits other) { - assert(self->size == other.size); - size_t n = _cbits_words(self->size); - for (size_t i=0; idata64[i] |= other.data64[i]; +STC_INLINE void _i_memb(_union)(i_type *self, i_type other) { + _i_assert(self->_size == other._size); + size_t n = _cbits_words(_i_memb(_size)(*self)); + while (n--) self->data64[n] |= other.data64[n]; } /* Exclusive disjunction */ -STC_INLINE void cbits_xor(cbits *self, cbits other) { - assert(self->size == other.size); - size_t n = _cbits_words(self->size); - for (size_t i=0; idata64[i] ^= other.data64[i]; +STC_INLINE void _i_memb(_xor)(i_type *self, i_type other) { + _i_assert(self->_size == other._size); + size_t n = _cbits_words(_i_memb(_size)(*self)); + while (n--) self->data64[n] ^= other.data64[n]; } #if defined(__GNUC__) || defined(__clang__) @@ -167,75 +183,116 @@ STC_INLINE void cbits_xor(cbits *self, cbits other) { #if defined(i_implement) -STC_DEF cbits* cbits_copy(cbits* self, cbits other) { - if (self->data64 == other.data64) return self; - if (self->size != other.size) return cbits_take(self, cbits_clone(other)); - memcpy(self->data64, other.data64, _cbits_bytes(other.size)); +#ifdef i_len +STC_DEF i_type _i_memb(_clone)(i_type other) + { return other; } + +STC_DEF i_type* _i_memb(_copy)(i_type* self, i_type other) + { *self = other; return self; } + +STC_DEF i_type _i_memb(_with_size)(const size_t size, const bool value) { + assert(size <= i_len); + i_type set; _i_memb(_set_all)(&set, value); + return set; +} + +STC_DEF i_type _i_memb(_with_pattern)(const size_t size, const uint64_t pattern) { + assert(size <= i_len); + i_type set; _i_memb(_set_pattern)(&set, pattern); + return set; +} +#else + +STC_DEF i_type _i_memb(_clone)(i_type other) { + const size_t bytes = _cbits_bytes(other._size); + i_type set = {(uint64_t *)memcpy(c_malloc(bytes), other.data64, bytes), other._size}; + return set; +} + +STC_DEF i_type* _i_memb(_copy)(i_type* self, i_type other) { + if (self->data64 == other.data64) + return self; + if (self->_size != other._size) + return _i_memb(_take)(self, _i_memb(_clone)(other)); + memcpy(self->data64, other.data64, _cbits_bytes(other._size)); return self; } -STC_DEF void cbits_resize(cbits* self, const size_t size, const bool value) { - const size_t new_n = _cbits_words(size), osize = self->size, old_n = _cbits_words(osize); - self->data64 = (uint64_t *) c_realloc(self->data64, new_n * 8); - self->size = size; +STC_DEF void _i_memb(_resize)(i_type* self, const size_t size, const bool value) { + const size_t new_n = _cbits_words(size), osize = self->_size, old_n = _cbits_words(osize); + self->data64 = (uint64_t *)c_realloc(self->data64, new_n*8); + self->_size = size; if (new_n >= old_n) { - memset(self->data64 + old_n, -(int)value, (new_n - old_n) * 8); + memset(self->data64 + old_n, -(int)value, (new_n - old_n)*8); if (old_n > 0) { uint64_t m = _cbits_bit(osize) - 1; /* mask */ - value ? (self->data64[old_n - 1] |= ~m) : (self->data64[old_n - 1] &= m); + value ? (self->data64[old_n - 1] |= ~m) + : (self->data64[old_n - 1] &= m); } } } -STC_DEF cbits cbits_with_size(const size_t size, const bool value) { - cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size}; - cbits_set_all(&set, value); +STC_DEF i_type _i_memb(_with_size)(const size_t size, const bool value) { + i_type set = {(uint64_t *)c_malloc(_cbits_bytes(size)), size}; + _i_memb(_set_all)(&set, value); return set; } -STC_DEF cbits cbits_with_values(const size_t size, const uint64_t pattern) { - cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size}; - cbits_set_values(&set, pattern); + +STC_DEF i_type _i_memb(_with_pattern)(const size_t size, const uint64_t pattern) { + i_type set = {(uint64_t *)c_malloc(_cbits_bytes(size)), size}; + _i_memb(_set_pattern)(&set, pattern); return set; } -STC_DEF cbits cbits_from_n(const char* str, const size_t n) { - cbits set = cbits_with_size(n, false); - for (size_t i=0; i>6; + size_t count = 0; + for (size_t i = 0; i < n; ++i) + count += cpopcount64(set.data64[i]); + if (sz & 63) + count += cpopcount64(set.data64[n] & (_cbits_bit(sz) - 1)); + return count; +} + +STC_DEF char* _i_memb(_to_str)(i_type set, char* out, size_t start, intptr_t stop) { + if (stop < 0) + stop = _i_memb(_size)(set); memset(out, '0', stop - start); - for (intptr_t i=start; i> 6; - for (size_t i = 0; i < n; ++i) count += cpopcount64(s.data64[i]); - if (s.size & 63) count += cpopcount64(s.data64[n] & (_cbits_bit(s.size) - 1)); - return count; -} #define _cbits_OPR(OPR, VAL) \ - assert(s.size == other.size); \ - const size_t n = s.size >> 6; \ + _i_assert(set._size == other._size); \ + const size_t sz = _i_memb(_size)(set), n = sz>>6; \ for (size_t i = 0; i < n; ++i) \ - if ((s.data64[i] OPR other.data64[i]) != VAL) \ + if ((set.data64[i] OPR other.data64[i]) != VAL) \ return false; \ - if (!(s.size & 63)) return true; \ - const uint64_t i = n, m = _cbits_bit(s.size) - 1; \ - return ((s.data64[i] OPR other.data64[i]) & m) == (VAL & m) + if (!(sz & 63)) \ + return true; \ + const uint64_t i = n, m = _cbits_bit(sz) - 1; \ + return ((set.data64[i] OPR other.data64[i]) & m) == (VAL & m) -STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_OPR(|, s.data64[i]); } -STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_OPR(&, 0); } +STC_DEF bool _i_memb(_subset_of)(i_type set, i_type other) { _cbits_OPR(|, set.data64[i]); } +STC_DEF bool _i_memb(_disjoint)(i_type set, i_type other) { _cbits_OPR(&, 0); } #endif #endif +#undef _i_memb +#undef _i_assert +#undef i_len +#undef i_type #undef i_opt -- cgit v1.2.3