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 --- include/stc/cbits.h | 285 +++++++++++++++++++++++++++++++--------------------- 1 file changed, 171 insertions(+), 114 deletions(-) (limited to 'include') 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