From c8a7b59dcc8a1d6cd7bf5f5bc6b76f26a97b34d6 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 29 Mar 2021 14:27:14 +0200 Subject: Another update of cbits. --- docs/cbits_api.md | 11 ++++++----- examples/cbits_prime.c | 39 --------------------------------------- examples/prime.c | 27 ++++++++++++--------------- stc/cbits.h | 7 ++++--- 4 files changed, 22 insertions(+), 62 deletions(-) delete mode 100644 examples/cbits_prime.c diff --git a/docs/cbits_api.md b/docs/cbits_api.md index 86a91e1b..e4b60da6 100644 --- a/docs/cbits_api.md +++ b/docs/cbits_api.md @@ -19,6 +19,7 @@ All cbits definitions and prototypes are available by including a single header ```c cbits cbits_init(void); cbits cbits_with_size(size_t size, bool value); +cbits cbits_with_values(size_t size, uint64_t pattern); cbits cbits_from_str(const char* str); cbits cbits_clone(cbits other); @@ -35,17 +36,17 @@ size_t cbits_count(cbits set); // count number of bool cbits_test(cbits set, size_t i); bool cbits_at(cbits set, size_t i); // same as cbits_test() -bool cbits_is_subset(cbits set, cbits other); // is set a subset of other? -bool cbits_is_disjoint(cbits set, cbits other); // xor test +bool cbits_subset_of(cbits set, cbits other); // is set a subset of other? +bool cbits_disjoint(cbits set, cbits other); // no common bits 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_value(cbits *self, size_t i, bool value); -void cbits_flip(cbits *self, size_t i); void cbits_set_all(cbits *self, bool value); -void cbits_set_all64(cbits *self, uint64_t pattern); +void cbits_set_value(cbits *self, size_t i, bool value); +void cbits_set_values(cbits *self, uint64_t pattern); void cbits_flip_all(cbits *self); +void cbits_flip(cbits *self, size_t i); void cbits_intersect(cbits *self, cbits other); void cbits_union(cbits *self, cbits other); diff --git a/examples/cbits_prime.c b/examples/cbits_prime.c deleted file mode 100644 index e2e7877a..00000000 --- a/examples/cbits_prime.c +++ /dev/null @@ -1,39 +0,0 @@ -#include -#include - -static inline cbits sieveOfEratosthenes(size_t n) -{ - cbits primes = cbits_with_size(n + 1, true); - cbits_reset(&primes, 0); - cbits_reset(&primes, 1); - - c_forrange (i, size_t, 2, n+1) { - // If primes[i] is not changed, then it is a prime - if (cbits_test(primes, i) && i*i <= n) { - c_forrange (j, size_t, i*i, n+1, i) { - cbits_reset(&primes, j); - } - } - } - return primes; -} - - -int main(void) -{ - int n = 100000000; - printf("computing prime numbers up to %u\n", n); - - cbits primes = sieveOfEratosthenes(n); - puts("done"); - - size_t np = cbits_count(primes); - printf("number of primes: %zu\n", np); - - printf("2 "); - c_forrange (i, int, 3, 1001, 2) { - if (cbits_test(primes, i)) printf("%d ", i); - } - puts(""); - cbits_del(&primes); -} \ No newline at end of file diff --git a/examples/prime.c b/examples/prime.c index f11f1627..39418c49 100644 --- a/examples/prime.c +++ b/examples/prime.c @@ -5,40 +5,37 @@ cbits sieveOfEratosthenes(size_t n) { - cbits bits = cbits_with_pattern(n, 0xAAAAAAAAAAAAAAAA); - size_t q = sqrt(n); - cbits_reset(&bits, 1); - cbits_set(&bits, 2); + cbits bits = cbits_with_size(n>>1, true); + size_t q = (size_t) sqrt(n); - for (size_t j, i = 3; i <= q; i += 2) { - for (j = i; j < n; j += 2) { - if (cbits_test(bits, j)) { + for (size_t i = 3; i <= q; i += 2) { + for (size_t j = i; j < n; j += 2) { + if (cbits_test(bits, j>>1)) { i = j; break; } } - for (j = i*i; j < n; j += i*2) - cbits_reset(&bits, j); + for (size_t j = i*i; j < n; j += i*2) + cbits_reset(&bits, j>>1); } return bits; } - int main(void) { size_t n = 100000000; - printf("computing prime numbers up to %u\n", n); + printf("computing prime numbers up to %zu\n", n); clock_t t1 = clock(); cbits primes = sieveOfEratosthenes(n + 1); size_t np = cbits_count(primes); clock_t t2 = clock(); - printf("number of primes: %zu, time: %f\n", np, (t2 - t1)/(float)CLOCKS_PER_SEC); + printf("number of primes: %zu, time: %f\n", np, (t2 - t1) / (float)CLOCKS_PER_SEC); - for (size_t i=0; i<=1000; ++i) - if (cbits_test(primes, i)) printf("%d ", i); + printf(" 2"); for (size_t i = 3; i < 1000; i += 2) + if (cbits_test(primes, i>>1)) printf(" %zu", i); puts(""); cbits_del(&primes); -} \ No newline at end of file +} diff --git a/stc/cbits.h b/stc/cbits.h index c15441f2..d2a309d4 100644 --- a/stc/cbits.h +++ b/stc/cbits.h @@ -58,6 +58,7 @@ int main() { typedef struct cbits { uint64_t* _arr; size_t size; } cbits_t, cbits; STC_API cbits_t cbits_with_size(size_t size, bool value); +STC_API cbits_t cbits_with_values(size_t size, uint64_t pattern); STC_API cbits_t cbits_from_str(const char* str); STC_API char* cbits_to_str(cbits_t set, char* str, size_t start, intptr_t stop); STC_API cbits_t cbits_clone(cbits_t other); @@ -110,7 +111,7 @@ STC_INLINE void cbits_set_all(cbits_t *self, bool value) { memset(self->_arr, -(int)value, ((self->size + 63) >> 6) * 8); } -STC_INLINE void cbits_set_all64(cbits_t *self, uint64_t pattern) { +STC_INLINE void cbits_set_values(cbits_t *self, uint64_t pattern) { size_t n = (self->size + 63) >> 6; for (size_t i=0; i_arr[i] = pattern; } @@ -180,9 +181,9 @@ STC_DEF cbits_t cbits_with_size(size_t size, bool value) { cbits_set_all(&set, value); return set; } -STC_DEF cbits_t cbits_with_pattern(size_t size, uint64_t pattern) { +STC_DEF cbits_t cbits_with_values(size_t size, uint64_t pattern) { cbits_t set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size}; - cbits_set_all64(&set, pattern); + cbits_set_values(&set, pattern); return set; } STC_DEF cbits_t cbits_from_str(const char* str) { -- cgit v1.2.3