diff options
| author | Tyge Løvset <[email protected]> | 2021-01-19 15:59:01 +0100 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2021-01-19 15:59:01 +0100 |
| commit | b16aa1db5d453f19a1851b411e7ec67a653782ff (patch) | |
| tree | f33839c7ba2e73aac3dab63ae356e76e27546acd | |
| parent | 19c810bfe2e4dbb9026a1519880a0fb1fa466bad (diff) | |
| download | STC-modified-b16aa1db5d453f19a1851b411e7ec67a653782ff.tar.gz STC-modified-b16aa1db5d453f19a1851b411e7ec67a653782ff.zip | |
Renamed cbitset to cbits. Added more docs.
| -rw-r--r-- | README.md | 4 | ||||
| -rw-r--r-- | docs/cbits_api.md | 116 | ||||
| -rw-r--r-- | docs/cbitset_api.md | 115 | ||||
| -rw-r--r-- | docs/cdeq_api.md | 2 | ||||
| -rw-r--r-- | docs/clist_api.md | 9 | ||||
| -rw-r--r-- | docs/cpque_api.md | 10 | ||||
| -rw-r--r-- | docs/cqueue_api.md | 2 | ||||
| -rw-r--r-- | docs/cset_api.md | 2 | ||||
| -rw-r--r-- | docs/csset_api.md | 2 | ||||
| -rw-r--r-- | docs/cstack_api.md | 2 | ||||
| -rw-r--r-- | docs/cvec_api.md | 4 | ||||
| -rw-r--r-- | examples/bits.c | 54 | ||||
| -rw-r--r-- | examples/prime.c | 22 | ||||
| -rw-r--r-- | stc/cbits.h | 244 | ||||
| -rw-r--r-- | stc/cbitset.h | 244 |
15 files changed, 421 insertions, 411 deletions
@@ -9,7 +9,7 @@ Introduction An modern, templated, user-friendly, fast, fully typesafe, and customizable container library for C99, with a uniform API.
This is a compact headers-only library with the all of the standard data containers, and a few algorithms:
- [***carray*** - Templated **multi-dimensional array** type](docs/carray_api.md)
-- [***cbitset*** - A **std::bitset** / **boost::dynamic_bitset** alike type](docs/cbitset_api.md)
+- [***cbits*** - A **std::bitset** / **boost::dynamic_bitset** alike type](docs/cbits_api.md)
- [***cdeq*** - Templated **std::deque** alike type](docs/cdeq_api.md)
- [***clist*** - Templated **std::forward_list** alike type](docs/clist_api.md)
- [***cmap*** - Templated **std::unordered_map** alike type](docs/cmap_api.md)
@@ -30,7 +30,7 @@ Others: The usage of the containers is similar to the C++ standard containers in STL, so it should be easy if you are familiar with them.
-All containers mentioned above, except cstr_t and cbitset_t, are generic and therefore typesafe (similar to templates in C++).
+All containers mentioned above, except cstr_t and cbits_t, are generic and therefore typesafe (similar to templates in C++).
No casting is used. A simple example:
```c
#include <stc/cvec.h>
diff --git a/docs/cbits_api.md b/docs/cbits_api.md new file mode 100644 index 00000000..f2e135fd --- /dev/null +++ b/docs/cbits_api.md @@ -0,0 +1,116 @@ +# STC Container [cbits](../stc/cbits.h): Bitset + + +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. + +The **cbits** container is similar to the c++ class [std::bitset](https://en.cppreference.com/w/cpp/utility/bitset) and [boost::dynamic_bitset](https://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html). + +## Types + +| cbits | Type definition | Used to represent... | +|:--------------------|:--------------------------|:-----------------------------| +| `cbits` | `struct { ... }` | The cbits type | +| `cbits_iter_t` | `struct { ... }` | The cbits iterator type | + +## Header file + +All cstr definitions and prototypes may be included in your C source file by including a single header file. + +```c +#include "stc/cbits.h" +``` +## Methods + +```c +cbits cbits_init(void); +cbits cbits_with_size(size_t size, bool value); +cbits cbits_from_str(const char* str); + +cbits cbits_clone(cbits_t other); +void cbits_resize(cbits_t* self, size_t size, bool value); + +cbits cbits_intersect(cbits_t s1, cbits_t s2); +cbits cbits_union(cbits_t s1, cbits_t s2); +cbits cbits_xor(cbits_t s1, cbits_t s2); +cbits cbits_not(cbits_t s1); + +void cbits_del(cbits_t* self); + +cbits* cbits_assign(cbits_t* self, cbits_t other); +cbits* cbits_take(cbits_t* self, cbits_t other); +cbits cbits_move(cbits_t* self); + +size_t cbits_size(cbits_t set); +size_t cbits_count(cbits_t set); +bool cbits_is_disjoint(cbits_t set, cbits_t other); +bool cbits_is_subset(cbits_t set, cbits_t other); +bool cbits_is_superset(cbits_t set, cbits_t other); +char* cbits_to_str(cbits_t set, char* str, size_t start, intptr_t stop); + +void cbits_set(cbits_t *self, size_t i); +void cbits_reset(cbits_t *self, size_t i); +void cbits_set_value(cbits_t *self, size_t i, bool value); +void cbits_flip(cbits_t *self, size_t i); +bool cbits_test(cbits_t set, size_t i); +void cbits_set_all(cbits_t *self, bool value); +void cbits_set_all64(cbits_t *self, uint64_t pattern); +void cbits_flip_all(cbits_t *self); + +void cbits_intersect_with(cbits_t *self, cbits_t other); +void cbits_union_with(cbits_t *self, cbits_t other); +void cbits_xor_with(cbits_t *self, cbits_t other); + +cbits_iter_t cbits_begin(cbits_t* self); +cbits_iter_t cbits_end(cbits_t* self); +void cbits_next(cbits_iter_t* it); +bool cbits_itval(cbits_iter_t it); +``` + +## Example +```c +#include <stdio.h> +#include "stc/cbits.h" + +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); +} +``` +Output: +``` +computing prime numbers up to 100000000 +done +number of primes: 5761455 +2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 +``` diff --git a/docs/cbitset_api.md b/docs/cbitset_api.md deleted file mode 100644 index 7a5f1210..00000000 --- a/docs/cbitset_api.md +++ /dev/null @@ -1,115 +0,0 @@ -# STC Container [cbitset](../stc/cbitset.h): Bitset - - -A **cbitset** represents a resizable sequence of N bits. Bitsets can be manipulated by standard logic operators and converted to and from strings and integers. See [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) for similar c++ classes. - -## Types - -| cbitset | Type definition | Used to represent... | -|:----------------------|:--------------------------|:-------------------------------------| -| `cbitset_t` | `struct { ... }` | The cbitset type | -| `cbitset_iter_t` | `struct { ... }` | The cbitset iterator type | - -## Header file - -All cstr definitions and prototypes may be included in your C source file by including a single header file. - -```c -#include "stc/cbitset.h" -``` -## Methods - -```c -cbitset_t cbitset_init(void); -cbitset_t cbitset_with_size(size_t size, bool value); -cbitset_t cbitset_from_str(const char* str); - -cbitset_t cbitset_clone(cbitset_t other); -void cbitset_resize(cbitset_t* self, size_t size, bool value); - -cbitset_t cbitset_intersect(cbitset_t s1, cbitset_t s2); -cbitset_t cbitset_union(cbitset_t s1, cbitset_t s2); -cbitset_t cbitset_xor(cbitset_t s1, cbitset_t s2); -cbitset_t cbitset_not(cbitset_t s1); - -void cbitset_del(cbitset_t* self); - -cbitset_t* cbitset_assign(cbitset_t* self, cbitset_t other); -cbitset_t* cbitset_take(cbitset_t* self, cbitset_t other); -cbitset_t cbitset_move(cbitset_t* self); - -size_t cbitset_size(cbitset_t set); -size_t cbitset_count(cbitset_t set); -bool cbitset_is_disjoint(cbitset_t set, cbitset_t other); -bool cbitset_is_subset(cbitset_t set, cbitset_t other); -bool cbitset_is_superset(cbitset_t set, cbitset_t other); -char* cbitset_to_str(cbitset_t set, char* str, size_t start, intptr_t stop); - -void cbitset_set(cbitset_t *self, size_t i); -void cbitset_reset(cbitset_t *self, size_t i); -void cbitset_set_value(cbitset_t *self, size_t i, bool value); -void cbitset_flip(cbitset_t *self, size_t i); -bool cbitset_test(cbitset_t set, size_t i); -void cbitset_set_all(cbitset_t *self, bool value); -void cbitset_set_all64(cbitset_t *self, uint64_t pattern); -void cbitset_flip_all(cbitset_t *self); - -void cbitset_intersect_with(cbitset_t *self, cbitset_t other); -void cbitset_union_with(cbitset_t *self, cbitset_t other); -void cbitset_xor_with(cbitset_t *self, cbitset_t other); - -cbitset_iter_t cbitset_begin(cbitset_t* self); -cbitset_iter_t cbitset_end(cbitset_t* self); -void cbitset_next(cbitset_iter_t* it); -bool cbitset_itval(cbitset_iter_t it); -``` - -## Example -```c -#include <stdio.h> -#include "stc/cbitset.h" - -static inline cbitset_t sieveOfEratosthenes(size_t n) -{ - cbitset_t pbits = cbitset_with_size(n + 1, true); - cbitset_reset(&pbits, 0); - cbitset_reset(&pbits, 1); - - c_forrange (i, size_t, 2, n+1) { - // If pbits[i] is not changed, then it is a prime - if (cbitset_test(pbits, i) && i*i <= n) { - c_forrange (j, size_t, i*i, n+1, i) { - cbitset_reset(&pbits, j); - } - } - } - return pbits; -} - -int main(void) -{ - int n = 100000000; - printf("computing prime numbers up to %u\n", n); - - cbitset_t primes = sieveOfEratosthenes(n); - puts("done"); - - size_t np = cbitset_count(primes); - printf("number of primes: %zu\n", np); - - printf("2 "); - c_forrange (i, int, 3, 1001, 2) { - if (cbitset_test(primes, i)) printf("%d ", i); - } - puts(""); - cbitset_del(&primes); -} -``` -Output: -``` -computing prime numbers up to 100000000 -done -number of primes: 5761455 -2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 -``` diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index 83c2779e..7bc68b88 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -1,7 +1,7 @@ # STC Container [cdeq](../stc/cdeq.h): Double Ended Queue  -A **cdeq** is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. +A **cdeq** is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. Note that this container is implemented similar to a vector, but has the same performance profile for both *push_back()* and *push_front()* as *cvec_X_push_back()*. Iterators may be invalidated after push-operations. See [std::deque](https://en.cppreference.com/w/cpp/container/deque) for a similar c++ class. ## Declaration diff --git a/docs/clist_api.md b/docs/clist_api.md index 767d5f24..53e3b350 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -1,10 +1,11 @@ # STC Container [clist](../stc/clist.h): Forward List  -This is similar to c++ [std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list), but supports both -*push_front()* and *push_back()* as well as *pop_front()* in **O**(1) time. Implemented as a circular singly linked list. -Also supports various *splice* functions and *merge-sort*. Note that like std::forward_list, the representation size of **clist** -is only one pointer, and length of the list is not stored. The method *clist_X_size()* is therefore computed in **O**(*n*) time. +The **clist** container supports fast insertion and removal of elements from anywhere in the container. It is similar to the c++ [std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list), but **clist** also supports *push_back()* (**O**(1) time). It is implemented as a circular singly-linked list. Fast random access is not supported. + +Adding, removing and moving the elements within the list, or across several lists, does not invalidate the iterators currently referring to other elements in the list. However, an iterator or reference referring to an element is invalidated when the corresponding element is removed (via *erase_after*) from the list. + +**clist** also supports various *splice* functions and *merge-sort*. **clist** itself occupies only one pointer in memory, like *std::forward_list*, the length of **clist** is not stored. The method *clist_X_size()* is available, however computed in **O**(*n*) time. ## Declaration diff --git a/docs/cpque_api.md b/docs/cpque_api.md index c402ea24..10a40043 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -1,16 +1,20 @@ # STC Container [cpque](../stc/cpque.h): Priority Queue -This describes the API of the priority queue type **cpque**. It is implemented as a heap. +A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction. + See [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue) for a similar c++ class. +Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap. + ## Declaration ```c #define using_cpque(X, ctype, heap_variant) ``` The macro `using_cpque()` must be instantiated in the global scope. -**cpque** uses normally a **cvec** type as underlying implementation, specified as `ctype`. -The `heap_variant` must be given as `<` or `>`, specifying *max-heap* or *min-heap* for the priority queue. +**cpque** uses normally **cvec_X** or **cdeq_X** as underlying implementation, specified as `ctype`. +The `heap_variant` must be given as `<` or `>`, specifying *max-heap* or *min-heap* for the priority queue to change the ordering, e.g. `>` would cause the smallest element to appear as the *cpque_X_top()*. + Note that the function `{ctype}_value_compare(x, y)` defined by the underlying vector type is used to compare values (priorities). `X` is a type tag name and will affect the names of all cpque types and methods. Declaring `using_cpque(my, cvec_my, >);`, `X` should be replaced by `my` in the following documentation. diff --git a/docs/cqueue_api.md b/docs/cqueue_api.md index b399a14c..96b46c64 100644 --- a/docs/cqueue_api.md +++ b/docs/cqueue_api.md @@ -10,7 +10,7 @@ See [std::queue](https://en.cppreference.com/w/cpp/container/queue) for a simila #define using_cqueue(X, ctype) ``` The macro `using_cqueue()` must be instantiated in the global scope. **cqueue** uses normally -a **clist** type as underlying implementation, given as `ctype`. `X` is a type tag name and +a **cdeq_X** or **clist_X** type as underlying implementation, given as `ctype`. `X` is a type tag name and will affect the names of all cqueue types and methods. E.g. declaring `using_cqueue(my, clist_my);`, `X` should be replaced by `my` in all of the following documentation. diff --git a/docs/cset_api.md b/docs/cset_api.md index 9efd261c..4fe694e7 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -44,7 +44,7 @@ be replaced by `my` in all of the following documentation. All cset definitions and prototypes may be included in your C source file by including a single header file.
```c
-#include "stc/cmap.h"
+#include "stc/cmap.h" // both cmap and cset
```
## Methods
diff --git a/docs/csset_api.md b/docs/csset_api.md index 88b44168..23510763 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -38,7 +38,7 @@ be replaced by `my` in all of the following documentation. All csset definitions and prototypes may be included in your C source file by including a single header file.
```c
-#include "stc/csmap.h"
+#include "stc/csmap.h" // both csmap and csset
```
## Methods
diff --git a/docs/cstack_api.md b/docs/cstack_api.md index 04927112..5a2516b8 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -10,7 +10,7 @@ See [std::stack](https://en.cppreference.com/w/cpp/container/stack) for a simila #define using_cstack(X, ctype) ``` The macro `using_cstack()` must be instantiated in the global scope. **cstack** uses normally -a **cvec** type as underlying implementation, given as `ctype`. `X` is a type tag name and will +a **cvec_X** or **cdeq_X** type as underlying implementation, given as `ctype`. `X` is a type tag name and will affect the names of all cstack types and methods. E.g. declaring `using_cstack(my, cvec_my);`, `X` should be replaced by `my` in all of the following documentation. diff --git a/docs/cvec_api.md b/docs/cvec_api.md index 53c9e0f2..b19cf436 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -4,6 +4,10 @@ A **cvec** is a sequence container that encapsulates dynamic size arrays. See [std::vector](https://en.cppreference.com/w/cpp/container/vector) for a similar c++ class. +The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using *cvec_X_capacity()* function. Extra memory can be returned to the system via a call to *cvec_X_shrink_to_fit()*. + +Reallocations are usually costly operations in terms of performance. The *cvec_X_reserve()* function can be used to eliminate reallocations if the number of elements is known beforehand. + ## Declaration ```c diff --git a/examples/bits.c b/examples/bits.c index a720ae64..0cbe0f46 100644 --- a/examples/bits.c +++ b/examples/bits.c @@ -1,57 +1,57 @@ #include <stdio.h>
-#include <stc/cbitset.h>
+#include <stc/cbits.h>
int main() {
- cbitset_t set = cbitset_with_size(23, true);
- printf("count %zu, %zu\n", cbitset_count(set), set.size);
+ cbits_t set = cbits_with_size(23, true);
+ printf("count %zu, %zu\n", cbits_count(set), set.size);
- cbitset_reset(&set, 9);
- cbitset_resize(&set, 43, false);
+ cbits_reset(&set, 9);
+ cbits_resize(&set, 43, false);
c_withbuffer (str, char, set.size + 1)
- printf(" str: %s\n", cbitset_to_str(set, str, 0, -1));
+ printf(" str: %s\n", cbits_to_str(set, str, 0, -1));
printf("%4zu: ", set.size);
c_forrange (i, int, set.size)
- printf("%d", cbitset_test(set, i));
+ printf("%d", cbits_test(set, i));
puts("");
- cbitset_set(&set, 28);
- cbitset_resize(&set, 77, true);
- cbitset_resize(&set, 93, false);
- cbitset_resize(&set, 102, true);
- cbitset_set_value(&set, 99, false);
+ cbits_set(&set, 28);
+ cbits_resize(&set, 77, true);
+ cbits_resize(&set, 93, false);
+ cbits_resize(&set, 102, true);
+ cbits_set_value(&set, 99, false);
printf("%4zu: ", set.size);
c_forrange (i, int, set.size)
- printf("%d", cbitset_test(set, i));
+ printf("%d", cbits_test(set, i));
puts("\nIterator:");
printf("%4zu: ", set.size);
- c_foreach (i, cbitset, set)
- printf("%d", cbitset_itval(i));
+ c_foreach (i, cbits, set)
+ printf("%d", cbits_itval(i));
puts("");
- cbitset_t s2 = cbitset_clone(set);
- cbitset_flip_all(&s2);
- cbitset_set(&s2, 16);
- cbitset_set(&s2, 17);
- cbitset_set(&s2, 18);
+ cbits_t s2 = cbits_clone(set);
+ cbits_flip_all(&s2);
+ cbits_set(&s2, 16);
+ cbits_set(&s2, 17);
+ cbits_set(&s2, 18);
printf(" new: ");
c_forrange (i, int, s2.size)
- printf("%d", cbitset_test(s2, i));
+ printf("%d", cbits_test(s2, i));
puts("");
printf(" xor: ");
- cbitset_xor_with(&set, s2);
+ cbits_xor_with(&set, s2);
c_forrange (i, int, set.size)
- printf("%d", cbitset_test(set, i));
+ printf("%d", cbits_test(set, i));
puts("");
- cbitset_set_all(&set, false);
+ cbits_set_all(&set, false);
printf("%4zu: ", set.size);
c_forrange (i, int, set.size)
- printf("%d", cbitset_test(set, i));
+ printf("%d", cbits_test(set, i));
puts("");
- cbitset_del(&s2);
- cbitset_del(&set);
+ cbits_del(&s2);
+ cbits_del(&set);
}
\ No newline at end of file diff --git a/examples/prime.c b/examples/prime.c index 95e1fd46..f5e9d4a5 100644 --- a/examples/prime.c +++ b/examples/prime.c @@ -1,17 +1,17 @@ #include <stdio.h>
-#include <stc/cbitset.h>
+#include <stc/cbits.h>
-static inline cbitset_t sieveOfEratosthenes(size_t n)
+static inline cbits_t sieveOfEratosthenes(size_t n)
{
- cbitset_t pbits = cbitset_with_size(n + 1, true);
- cbitset_reset(&pbits, 0);
- cbitset_reset(&pbits, 1);
+ cbits_t pbits = cbits_with_size(n + 1, true);
+ cbits_reset(&pbits, 0);
+ cbits_reset(&pbits, 1);
c_forrange (i, size_t, 2, n+1) {
// If pbits[i] is not changed, then it is a prime
- if (cbitset_test(pbits, i) && i*i <= n) {
+ if (cbits_test(pbits, i) && i*i <= n) {
c_forrange (j, size_t, i*i, n+1, i) {
- cbitset_reset(&pbits, j);
+ cbits_reset(&pbits, j);
}
}
}
@@ -24,16 +24,16 @@ int main(void) int n = 100000000;
printf("computing prime numbers up to %u\n", n);
- cbitset_t primes = sieveOfEratosthenes(n);
+ cbits_t primes = sieveOfEratosthenes(n);
puts("done");
- size_t np = cbitset_count(primes);
+ size_t np = cbits_count(primes);
printf("number of primes: %zu\n", np);
printf("2 ");
c_forrange (i, int, 3, 1001, 2) {
- if (cbitset_test(primes, i)) printf("%d ", i);
+ if (cbits_test(primes, i)) printf("%d ", i);
}
puts("");
- cbitset_del(&primes);
+ cbits_del(&primes);
}
\ No newline at end of file diff --git a/stc/cbits.h b/stc/cbits.h new file mode 100644 index 00000000..258f9d09 --- /dev/null +++ b/stc/cbits.h @@ -0,0 +1,244 @@ +/* MIT License
+ *
+ * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#ifndef CBITSET__H__
+#define CBITSET__H__
+
+/*
+Similar to boost::dynamic_bitset / std::bitset
+
+#include <stdio.h>
+#include "cbits.h"
+
+int main() {
+ cbits_t bset = cbits_with_size(23, true);
+ cbits_reset(&bset, 9);
+ cbits_resize(&bset, 43, false);
+ printf("%4zu: ", bset.size); c_forrange (i, bset.size) printf("%d", cbits_test(&bset, i));
+ puts("");
+ cbits_set(&bset, 28);
+ cbits_resize(&bset, 77, true);
+ cbits_resize(&bset, 93, false);
+ cbits_resize(&bset, 102, true);
+ cbits_set_value(&bset, 99, false);
+ printf("%4zu: ", bset.size); c_forrange (i, bset.size) printf("%d", cbits_test(&bset, i));
+ puts("");
+ cbits_del(&bset);
+}
+*/
+#include <stdlib.h>
+#include <string.h>
+#include "ccommon.h"
+
+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_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);
+STC_API void cbits_resize(cbits_t* self, size_t size, bool value);
+STC_API size_t cbits_count(cbits_t set);
+STC_API bool cbits_is_disjoint(cbits_t set, cbits_t other);
+STC_API bool cbits_is_subset(cbits_t set, cbits_t other);
+STC_API bool cbits_is_superset(cbits_t set, cbits_t other);
+
+STC_INLINE size_t cbits_size(cbits_t set) {return set.size;}
+#define cbits_inits {NULL, 0}
+
+STC_INLINE cbits_t cbits_init() {
+ cbits_t bs = cbits_inits; return bs;
+}
+STC_INLINE void cbits_del(cbits_t* self) {
+ c_free(self->_arr);
+}
+
+STC_DEF cbits_t* cbits_take(cbits_t* self, cbits_t other) {
+ if (self->_arr != other._arr) cbits_del(self), *self = other;
+ return self;
+}
+STC_DEF cbits_t* cbits_assign(cbits_t* self, cbits_t other) {
+ if (self->_arr != other._arr) cbits_del(self), *self = cbits_clone(other);
+ return self;
+}
+STC_INLINE cbits_t cbits_move(cbits_t* self) {
+ cbits_t tmp = *self; self->_arr = NULL, self->size = 0;
+ return tmp;
+}
+
+STC_INLINE void cbits_set(cbits_t *self, size_t i) {
+ self->_arr[i >> 6] |= 1ull << (i & 63);
+}
+STC_INLINE void cbits_reset(cbits_t *self, size_t i) {
+ self->_arr[i >> 6] &= ~(1ull << (i & 63));
+}
+STC_INLINE void cbits_set_value(cbits_t *self, size_t i, bool value) {
+ value ? cbits_set(self, i) : cbits_reset(self, i);
+}
+STC_INLINE void cbits_flip(cbits_t *self, size_t i) {
+ self->_arr[i >> 6] ^= 1ull << (i & 63);
+}
+STC_INLINE bool cbits_test(cbits_t set, size_t i) {
+ return (set._arr[i >> 6] & (1ull << (i & 63))) != 0;
+}
+STC_INLINE void cbits_set_all(cbits_t *self, bool value) {
+ memset(self->_arr, value ? 0xff : 0x0, ((self->size + 63) >> 6) * 8);
+}
+STC_INLINE void cbits_set_all64(cbits_t *self, uint64_t pattern) {
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->_arr[i] = pattern;
+}
+STC_INLINE void cbits_flip_all(cbits_t *self) {
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->_arr[i] ^= ~0ull;
+}
+
+/* Intersection */
+STC_INLINE void cbits_intersect_with(cbits_t *self, cbits_t other) {
+ assert(self->size == other.size);
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->_arr[i] &= other._arr[i];
+}
+/* Union */
+STC_INLINE void cbits_union_with(cbits_t *self, cbits_t other) {
+ assert(self->size == other.size);
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->_arr[i] |= other._arr[i];
+}
+/* Exclusive disjunction */
+STC_INLINE void cbits_xor_with(cbits_t *self, cbits_t other) {
+ assert(self->size == other.size);
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->_arr[i] ^= other._arr[i];
+}
+
+STC_INLINE cbits_t cbits_intersect(cbits_t s1, cbits_t s2) {
+ cbits_t set = cbits_clone(s1);
+ cbits_intersect_with(&set, s2); return set;
+}
+STC_INLINE cbits_t cbits_union(cbits_t s1, cbits_t s2) {
+ cbits_t set = cbits_clone(s1);
+ cbits_union_with(&set, s2); return set;
+}
+STC_INLINE cbits_t cbits_xor(cbits_t s1, cbits_t s2) {
+ cbits_t set = cbits_clone(s1);
+ cbits_xor_with(&set, s2); return set;
+}
+STC_INLINE cbits_t cbits_not(cbits_t s1) {
+ cbits_t set = cbits_clone(s1);
+ cbits_flip_all(&set); return set;
+}
+
+typedef struct {
+ cbits_t *_bs;
+ size_t ref;
+} cbits_iter_t;
+
+STC_INLINE cbits_iter_t
+cbits_begin(cbits_t* self) {
+ cbits_iter_t it = {self, 0}; return it;
+}
+STC_INLINE cbits_iter_t
+cbits_end(cbits_t* self) {
+ cbits_iter_t it = {self, self->size}; return it;
+}
+STC_INLINE void
+cbits_next(cbits_iter_t* it) {++it->ref;}
+
+STC_INLINE bool cbits_itval(cbits_iter_t it) {
+ return cbits_test(*it._bs, it.ref);
+}
+
+#if defined(__GNUC__) || defined(__clang__)
+ STC_INLINE uint64_t cpopcount64(uint64_t x) {return __builtin_popcountll(x);}
+#elif defined(_MSC_VER) && defined(_WIN64)
+ #include <intrin.h>
+ STC_INLINE uint64_t cpopcount64(uint64_t x) {return __popcnt64(x);}
+#else
+ STC_INLINE uint64_t cpopcount64(uint64_t x) { /* http://en.wikipedia.org/wiki/Hamming_weight */
+ x -= (x >> 1) & 0x5555555555555555;
+ x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
+ x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
+ return (x * 0x0101010101010101) >> 56;
+ }
+#endif
+
+#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
+
+STC_DEF void cbits_resize(cbits_t* self, size_t size, bool value) {
+ size_t new_n = (size + 63) >> 6, osize = self->size, old_n = (osize + 63) >> 6;
+ self->_arr = (uint64_t *) c_realloc(self->_arr, new_n * 8);
+ self->size = size;
+ if (new_n >= old_n) {
+ memset(self->_arr + old_n, value ? 0xff : 0x0, (new_n - old_n) * 8);
+ if (old_n > 0) {
+ uint64_t m = (1ull << (osize & 63)) - 1; /* mask */
+ value ? (self->_arr[old_n - 1] |= ~m) : (self->_arr[old_n - 1] &= m);
+ }
+ }
+}
+
+STC_DEF cbits_t cbits_with_size(size_t size, bool value) {
+ cbits_t set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size};
+ cbits_set_all(&set, value);
+ return set;
+}
+STC_DEF cbits_t cbits_from_str(const char* str) {
+ const char* p = str; while (*p) ++p;
+ cbits_t set = cbits_with_size(p - str, false);
+ for (size_t i=0; i<set.size; ++i) if (str[i] == '1') cbits_set(&set, i);
+ return set;
+}
+STC_DEF char* cbits_to_str(cbits_t set, char* out, size_t start, intptr_t stop) {
+ size_t end = stop < 0 ? set.size : stop;
+ for (size_t i=start; i<end; ++i) out[i] = cbits_test(set, i) ? '1' : '0';
+ out[end] = '\0'; return out;
+}
+STC_DEF cbits_t cbits_clone(cbits_t other) {
+ size_t bytes = ((other.size + 63) >> 6) * 8;
+ cbits_t set = {(uint64_t *) memcpy(c_malloc(bytes), other._arr, bytes), other.size};
+ return set;
+}
+STC_DEF size_t cbits_count(cbits_t s) {
+ size_t count = 0, n = ((s.size + 63) >> 6) - 1;
+ if (s.size > 0) {
+ for (size_t i=0; i<n; ++i) count += cpopcount64(s._arr[i]);
+ count += cpopcount64(s._arr[n] & ((1ull << (s.size & 63)) - 1));
+ }
+ return count;
+}
+
+#define _cbits_SETOP(OPR) \
+ assert(s.size == other.size); \
+ if (s.size == 0) return false; /* ? */ \
+ size_t n = ((s.size + 63) >> 6) - 1; \
+ for (size_t i=0; i<n; ++i) \
+ if ((s._arr[i] OPR other._arr[i]) != s._arr[i]) \
+ return false; \
+ uint64_t m = (1ull << (s.size & 63)) - 1, last = s._arr[n] & m; \
+ return (last OPR (other._arr[n] & m)) == last
+
+STC_DEF bool cbits_is_disjoint(cbits_t s, cbits_t other) { _cbits_SETOP(^); }
+STC_DEF bool cbits_is_subset(cbits_t s, cbits_t other) { _cbits_SETOP(|); }
+STC_DEF bool cbits_is_superset(cbits_t s, cbits_t other) { _cbits_SETOP(&); }
+
+#endif
+#endif
diff --git a/stc/cbitset.h b/stc/cbitset.h deleted file mode 100644 index 4e6a7c41..00000000 --- a/stc/cbitset.h +++ /dev/null @@ -1,244 +0,0 @@ -/* MIT License
- *
- * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in all
- * copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-#ifndef CBITSET__H__
-#define CBITSET__H__
-
-/*
-Similar to boost::dynamic_bitset / std::bitset
-
-#include <stdio.h>
-#include "cbitset.h"
-
-int main() {
- cbitset_t bset = cbitset_with_size(23, true);
- cbitset_reset(&bset, 9);
- cbitset_resize(&bset, 43, false);
- printf("%4zu: ", bset.size); c_forrange (i, bset.size) printf("%d", cbitset_test(&bset, i));
- puts("");
- cbitset_set(&bset, 28);
- cbitset_resize(&bset, 77, true);
- cbitset_resize(&bset, 93, false);
- cbitset_resize(&bset, 102, true);
- cbitset_set_value(&bset, 99, false);
- printf("%4zu: ", bset.size); c_forrange (i, bset.size) printf("%d", cbitset_test(&bset, i));
- puts("");
- cbitset_del(&bset);
-}
-*/
-#include <stdlib.h>
-#include <string.h>
-#include "ccommon.h"
-
-typedef struct cbitset { uint64_t* _arr; size_t size; } cbitset_t, cbitset;
-
-STC_API cbitset_t cbitset_with_size(size_t size, bool value);
-STC_API cbitset_t cbitset_from_str(const char* str);
-STC_API char* cbitset_to_str(cbitset_t set, char* str, size_t start, intptr_t stop);
-STC_API cbitset_t cbitset_clone(cbitset_t other);
-STC_API void cbitset_resize(cbitset_t* self, size_t size, bool value);
-STC_API size_t cbitset_count(cbitset_t set);
-STC_API bool cbitset_is_disjoint(cbitset_t set, cbitset_t other);
-STC_API bool cbitset_is_subset(cbitset_t set, cbitset_t other);
-STC_API bool cbitset_is_superset(cbitset_t set, cbitset_t other);
-
-STC_INLINE size_t cbitset_size(cbitset_t set) {return set.size;}
-#define cbitset_inits {NULL, 0}
-
-STC_INLINE cbitset_t cbitset_init() {
- cbitset_t bs = cbitset_inits; return bs;
-}
-STC_INLINE void cbitset_del(cbitset_t* self) {
- c_free(self->_arr);
-}
-
-STC_DEF cbitset_t* cbitset_take(cbitset_t* self, cbitset_t other) {
- if (self->_arr != other._arr) cbitset_del(self), *self = other;
- return self;
-}
-STC_DEF cbitset_t* cbitset_assign(cbitset_t* self, cbitset_t other) {
- if (self->_arr != other._arr) cbitset_del(self), *self = cbitset_clone(other);
- return self;
-}
-STC_INLINE cbitset_t cbitset_move(cbitset_t* self) {
- cbitset_t tmp = *self; self->_arr = NULL, self->size = 0;
- return tmp;
-}
-
-STC_INLINE void cbitset_set(cbitset_t *self, size_t i) {
- self->_arr[i >> 6] |= 1ull << (i & 63);
-}
-STC_INLINE void cbitset_reset(cbitset_t *self, size_t i) {
- self->_arr[i >> 6] &= ~(1ull << (i & 63));
-}
-STC_INLINE void cbitset_set_value(cbitset_t *self, size_t i, bool value) {
- value ? cbitset_set(self, i) : cbitset_reset(self, i);
-}
-STC_INLINE void cbitset_flip(cbitset_t *self, size_t i) {
- self->_arr[i >> 6] ^= 1ull << (i & 63);
-}
-STC_INLINE bool cbitset_test(cbitset_t set, size_t i) {
- return (set._arr[i >> 6] & (1ull << (i & 63))) != 0;
-}
-STC_INLINE void cbitset_set_all(cbitset_t *self, bool value) {
- memset(self->_arr, value ? 0xff : 0x0, ((self->size + 63) >> 6) * 8);
-}
-STC_INLINE void cbitset_set_all64(cbitset_t *self, uint64_t pattern) {
- size_t n = (self->size + 63) >> 6;
- for (size_t i=0; i<n; ++i) self->_arr[i] = pattern;
-}
-STC_INLINE void cbitset_flip_all(cbitset_t *self) {
- size_t n = (self->size + 63) >> 6;
- for (size_t i=0; i<n; ++i) self->_arr[i] ^= ~0ull;
-}
-
-/* Intersection */
-STC_INLINE void cbitset_intersect_with(cbitset_t *self, cbitset_t other) {
- assert(self->size == other.size);
- size_t n = (self->size + 63) >> 6;
- for (size_t i=0; i<n; ++i) self->_arr[i] &= other._arr[i];
-}
-/* Union */
-STC_INLINE void cbitset_union_with(cbitset_t *self, cbitset_t other) {
- assert(self->size == other.size);
- size_t n = (self->size + 63) >> 6;
- for (size_t i=0; i<n; ++i) self->_arr[i] |= other._arr[i];
-}
-/* Exclusive disjunction */
-STC_INLINE void cbitset_xor_with(cbitset_t *self, cbitset_t other) {
- assert(self->size == other.size);
- size_t n = (self->size + 63) >> 6;
- for (size_t i=0; i<n; ++i) self->_arr[i] ^= other._arr[i];
-}
-
-STC_INLINE cbitset_t cbitset_intersect(cbitset_t s1, cbitset_t s2) {
- cbitset_t set = cbitset_clone(s1);
- cbitset_intersect_with(&set, s2); return set;
-}
-STC_INLINE cbitset_t cbitset_union(cbitset_t s1, cbitset_t s2) {
- cbitset_t set = cbitset_clone(s1);
- cbitset_union_with(&set, s2); return set;
-}
-STC_INLINE cbitset_t cbitset_xor(cbitset_t s1, cbitset_t s2) {
- cbitset_t set = cbitset_clone(s1);
- cbitset_xor_with(&set, s2); return set;
-}
-STC_INLINE cbitset_t cbitset_not(cbitset_t s1) {
- cbitset_t set = cbitset_clone(s1);
- cbitset_flip_all(&set); return set;
-}
-
-typedef struct {
- cbitset_t *_bs;
- size_t ref;
-} cbitset_iter_t;
-
-STC_INLINE cbitset_iter_t
-cbitset_begin(cbitset_t* self) {
- cbitset_iter_t it = {self, 0}; return it;
-}
-STC_INLINE cbitset_iter_t
-cbitset_end(cbitset_t* self) {
- cbitset_iter_t it = {self, self->size}; return it;
-}
-STC_INLINE void
-cbitset_next(cbitset_iter_t* it) {++it->ref;}
-
-STC_INLINE bool cbitset_itval(cbitset_iter_t it) {
- return cbitset_test(*it._bs, it.ref);
-}
-
-#if defined(__GNUC__) || defined(__clang__)
- STC_INLINE uint64_t cpopcount64(uint64_t x) {return __builtin_popcountll(x);}
-#elif defined(_MSC_VER) && defined(_WIN64)
- #include <intrin.h>
- STC_INLINE uint64_t cpopcount64(uint64_t x) {return __popcnt64(x);}
-#else
- STC_INLINE uint64_t cpopcount64(uint64_t x) { /* http://en.wikipedia.org/wiki/Hamming_weight */
- x -= (x >> 1) & 0x5555555555555555;
- x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
- x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
- return (x * 0x0101010101010101) >> 56;
- }
-#endif
-
-#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
-
-STC_DEF void cbitset_resize(cbitset_t* self, size_t size, bool value) {
- size_t new_n = (size + 63) >> 6, osize = self->size, old_n = (osize + 63) >> 6;
- self->_arr = (uint64_t *) c_realloc(self->_arr, new_n * 8);
- self->size = size;
- if (new_n >= old_n) {
- memset(self->_arr + old_n, value ? 0xff : 0x0, (new_n - old_n) * 8);
- if (old_n > 0) {
- uint64_t m = (1ull << (osize & 63)) - 1; /* mask */
- value ? (self->_arr[old_n - 1] |= ~m) : (self->_arr[old_n - 1] &= m);
- }
- }
-}
-
-STC_DEF cbitset_t cbitset_with_size(size_t size, bool value) {
- cbitset_t set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size};
- cbitset_set_all(&set, value);
- return set;
-}
-STC_DEF cbitset_t cbitset_from_str(const char* str) {
- const char* p = str; while (*p) ++p;
- cbitset_t set = cbitset_with_size(p - str, false);
- for (size_t i=0; i<set.size; ++i) if (str[i] == '1') cbitset_set(&set, i);
- return set;
-}
-STC_DEF char* cbitset_to_str(cbitset_t set, char* out, size_t start, intptr_t stop) {
- size_t end = stop < 0 ? set.size : stop;
- for (size_t i=start; i<end; ++i) out[i] = cbitset_test(set, i) ? '1' : '0';
- out[end] = '\0'; return out;
-}
-STC_DEF cbitset_t cbitset_clone(cbitset_t other) {
- size_t bytes = ((other.size + 63) >> 6) * 8;
- cbitset_t set = {(uint64_t *) memcpy(c_malloc(bytes), other._arr, bytes), other.size};
- return set;
-}
-STC_DEF size_t cbitset_count(cbitset_t s) {
- size_t count = 0, n = ((s.size + 63) >> 6) - 1;
- if (s.size > 0) {
- for (size_t i=0; i<n; ++i) count += cpopcount64(s._arr[i]);
- count += cpopcount64(s._arr[n] & ((1ull << (s.size & 63)) - 1));
- }
- return count;
-}
-
-#define _cbitset_SETOP(OPR) \
- assert(s.size == other.size); \
- if (s.size == 0) return false; /* ? */ \
- size_t n = ((s.size + 63) >> 6) - 1; \
- for (size_t i=0; i<n; ++i) \
- if ((s._arr[i] OPR other._arr[i]) != s._arr[i]) \
- return false; \
- uint64_t m = (1ull << (s.size & 63)) - 1, last = s._arr[n] & m; \
- return (last OPR (other._arr[n] & m)) == last
-
-STC_DEF bool cbitset_is_disjoint(cbitset_t s, cbitset_t other) { _cbitset_SETOP(^); }
-STC_DEF bool cbitset_is_subset(cbitset_t s, cbitset_t other) { _cbitset_SETOP(|); }
-STC_DEF bool cbitset_is_superset(cbitset_t s, cbitset_t other) { _cbitset_SETOP(&); }
-
-#endif
-#endif
|
