From e8aed0431140fd0d202d302f19f756046858bad7 Mon Sep 17 00:00:00 2001 From: tylov Date: Sun, 23 Jul 2023 23:48:00 +0200 Subject: Updated docs. --- README.md | 60 +++--- docs/algorithm_api.md | 434 +++++++++++++++++++++++++++++++++++++++ docs/ccommon_api.md | 557 -------------------------------------------------- docs/cspan_api.md | 11 +- 4 files changed, 470 insertions(+), 592 deletions(-) create mode 100644 docs/algorithm_api.md delete mode 100644 docs/ccommon_api.md diff --git a/README.md b/README.md index b49214d4..6351fc07 100644 --- a/README.md +++ b/README.md @@ -3,8 +3,8 @@ STC - Smart Template Containers =============================== -### [Version 4.3 RC3](#version-history) - +### [Version 4.3 Released](#version-history) +- See details for breaking changes. --- Description ----------- @@ -33,10 +33,10 @@ Containers Algorithms ---------- -- [***Ranged for-loops*** - c_foreach, c_forpair, c_forlist](docs/ccommon_api.md#ranged-for-loops) -- [***Range algorithms*** - c_forrange, crange, c_forfilter](docs/ccommon_api.md#range-algorithms) -- [***Generic algorithms*** - c_init, c_find_if, c_erase_if, csort, etc.](docs/ccommon_api.md#generic-algorithms) -- [***Coroutines*** - Simon Tatham's coroutines done right.](docs/ccommon_api.md#coroutines) +- [***Ranged for-loops*** - c_foreach, c_forpair, c_forlist](docs/algorithm_api.md#ranged-for-loops) +- [***Range algorithms*** - c_forrange, crange, c_forfilter](docs/algorithm_api.md#range-algorithms) +- [***Generic algorithms*** - c_init, c_find_if, c_erase_if, csort, etc.](docs/algorithm_api.md#generic-algorithms) +- [***Coroutines*** - ergonomic portable coroutines](docs/coroutine_api.md) - [***Regular expressions*** - Rob Pike's Plan 9 regexp modernized!](docs/cregex_api.md) - [***Random numbers*** - a very fast *PRNG* based on *SFC64*](docs/crandom_api.md) - [***Command line argument parser*** - similar to *getopt()*](docs/coption_api.md) @@ -61,12 +61,11 @@ List of contents --- ## Highlights -- **No boilerplate code** - Specify only the required template parameters, e.g. ***cmp***- and/or ***clone***-, ***drop***- functions, and leave the rest as defaults. +- **Minimal boilerplate code** - Specify only the required template parameters, and leave the rest as defaults. - **Fully type safe** - Because of templating, it avoids error-prone casting of container types and elements back and forth from the containers. -- **User friendly** - Just include the headers and you are good. The API and functionality is very close to c++ STL and is fully listed in the docs. -- **Unparalleled performance** - Maps and sets are much faster than the C++ STL containers, the remaining are similar in speed. +- **High performance** - Unordered maps and sets, queues and deques are significantly faster than the C++ STL containers, the remaining are similar or close to STL in speed (See graph below). - **Fully memory managed** - Containers destructs keys/values via default or user supplied drop function. They may be cloned if element types are clonable. Also, smart pointers are supported and can be stored in containers. See [***carc***](docs/carc_api.md) and [***cbox***](docs/cbox_api.md). -- **Uniform, easy-to-learn API** - Intuitive method/type names and uniform usage across the various containers. +- **Uniform, easy-to-learn API** - Just include the headers and you are good. The API and functionality resembles c++ STL and is fully listed in the docs. Intuitive method/type names and uniform usage across the various containers. - **No signed/unsigned mixing** - Unsigned sizes and indices mixed with signed for comparison and calculation is asking for trouble. STC only uses signed numbers in the API for this reason. - **Small footprint** - Small source code and generated executables. The executable from the example below using *four different* container types is only ***19 Kb in size*** compiled with gcc -O3 -s on Linux. - **Dual mode compilation** - By default it is a simple header-only library with inline and static methods only, but you can easily switch to create a traditional library with shared symbols, without changing existing source files. See the Installation section. @@ -95,17 +94,17 @@ So instead of calling e.g. `cvec_str_push(&vec, cstr_from("Hello"))`, you may ca same element access syntax. E.g.: - `c_foreach (it, MyInts, myints) *it.ref += 42;` works for any container defined as `MyInts` with `int` elements. - - `c_foreach (it, MyInts, it1, it2) *it.ref += 42;` iterates from `it1` up to `it2`. + - `c_foreach (it, MyInts, it1, it2) *it.ref += 42;` iterates from `it1` up to not including `it2`. --- ## Performance STC is a fast and memory efficient library, and code compiles fast: -![Benchmark](misc/benchmarks/pics/benchmark.gif) +![Benchmark](docs/pics/Figure_1.png) Benchmark notes: -- The barchart shows average test times over three platforms: Mingw64 10.30, Win-Clang 12, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. +- The barchart shows average test times over three compilers: **Mingw64 13.1.0, Win-Clang 16.0.5, VC-19-36**. CPU: **Ryzen 7 5700X**. - Containers uses value types `uint64_t` and pairs of `uint64_t` for the maps. - Black bars indicates performance variation between various platforms/compilers. - Iterations are repeated 4 times over n elements. @@ -615,19 +614,20 @@ STC is generally very memory efficient. Memory usage for the different container ## Version 4.3 - Some breaking changes. -- coroutines: much improved with some new API and added features. -- cspan: Support for column-major (fortran order) multidim spans and transposed views. -- Removed default comparison for clist, cvec and cdeq (as with cstack and cqueue). - - Using i_key_str, i_keyclass, i_keyboxed still expects comparisons defined. - - Define i_cmp_native to enable built-in i_key types comparisons (<, ==). -- cstr and csview are now shared linked by default. Static linking by defining i_static. -- New cdeq and cqueue implementation(s), using circular buffer. -- Renamed i_extern => i_import. - - Define i_import before #include will also define utf8 case conversions. - - Define i_import before #include will also define cstr + utf8 tables. -- Renamed c_make() => c_init() macro for initialization lists. -- Renamed input enum flags for cregex functions. -- Removed deprecated crandom.h. Use crand.h with new API. +- **coroutines**: much improved with some new API and added features. +- **cspan**: Rewritten to add support for **column-major** order (fortran) multidim spans and transposed views. +- Removed default comparison for **clist**, **cvec** and **cdeq** (like cstack and cqueue). + - Define `i_cmp_native` to enable built-in i_key types comparisons (<, ==). + - Use of `i_keyclass` still expects comparison functions defined. + - Use of `i_keyboxed` compares hosted pointers instead of pointed to values if comparisons not defined. +- **cstr** and **csview** now uses *shared linking* by default. Implement by either defining `i_implement` or `i_static` before including. +- All new faster and smaller **cqueue** and **cdeq** implementations, using a circular buffer. +- Renamed i_extern => `i_import`. + - Define `i_import` before `#include ` will also define utf8 case conversions. + - Define `i_import` before `#include ` will also define cstr + utf8 tables. +- Renamed c_make() => ***c_init()*** macro for initializing containers with element lists. +- Renamed input enum flags for ***cregex***-functions. +- Removed deprecated . Use `` with the new API. - Removed deprecated uppercase flow-control macro names. - Improved default string hash function. @@ -653,8 +653,8 @@ Major changes: - Customizable allocator [per templated container type](https://github.com/tylov/STC/discussions/44#discussioncomment-4891925). - Updates on **cregex** with several [new unicode character classes](docs/cregex_api.md#regex-cheatsheet). - Algorithms: - - [crange](docs/ccommon_api.md#crange) - similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html) integer range generator. - - [c_forfilter](docs/ccommon_api.md#c_forfilter) - ranges-like view filtering. + - [crange](docs/algorithm_api.md#crange) - similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html) integer range generator. + - [c_forfilter](docs/algorithm_api.md#c_forfilter) - ranges-like view filtering. - [csort](include/stc/algo/sort.h) - [fast quicksort](misc/benchmarks/various/csort_bench.c) with custom inline comparison. - Renamed `c_ARGSV()` => `c_SV()`: **csview** print arg. Note `c_sv()` is shorthand for *csview_from()*. - Support for [uppercase flow-control](include/stc/priv/altnames.h) macro names in ccommon.h. @@ -715,10 +715,10 @@ Major changes: - Renamed: *csptr_X_make()* to `carc_X_from()`. - Renamed: *cstr_new()* to `cstr_lit(literal)`, and *cstr_assign_fmt()* to `cstr_printf()`. - Renamed: *c_default_fromraw()* to `c_default_from()`. -- Changed: the [**c_apply**](docs/ccommon_api.md) macros API. +- Changed: the [**c_apply**](docs/algorithm_api.md) macros API. - Replaced: *csview_first_token()* and *csview_next_token()* with one function: `csview_token()`. - Added: **checkauto** tool for checking that c-source files uses `c_auto*` macros correctly. - Added: general `i_keyclass` / `i_valclass` template parameters which auto-binds template functions. - Added: `i_opt` template parameter: compile-time options: `c_no_cmp`, `c_no_clone`, `c_no_atomic`, `c_is_forward`; may be combined with `|` - Added: [**cbox**](docs/cbox_api.md) type: smart pointer, similar to [Rust Box](https://doc.rust-lang.org/rust-by-example/std/box.html) and [std::unique_ptr](https://en.cppreference.com/w/cpp/memory/unique_ptr). -- Added: [**c_forpair**](docs/ccommon_api.md) macro: for-loop with "structured binding" +- Added: [**c_forpair**](docs/algorithm_api.md) macro: for-loop with "structured binding" diff --git a/docs/algorithm_api.md b/docs/algorithm_api.md new file mode 100644 index 00000000..490771b5 --- /dev/null +++ b/docs/algorithm_api.md @@ -0,0 +1,434 @@ +# STC Algorithms + +"No raw loops" - Sean Parent +## Ranged for-loops + +### c_foreach, c_forpair +```c +#include +``` + +| Usage | Description | +|:-----------------------------------------|:------------------------------------------| +| `c_foreach (it, ctype, container)` | Iteratate all elements | +| `c_foreach (it, ctype, it1, it2)` | Iterate the range [it1, it2) | +| `c_forpair (key, val, ctype, container)` | Iterate with structured binding | + +```c +#define i_key int +#define i_val int +#define i_tag ii +#include +... +csmap_ii map = c_init(csmap_ii, { {23,1}, {3,2}, {7,3}, {5,4}, {12,5} }); + +c_foreach (i, csmap_ii, map) + printf(" %d", i.ref->first); +// 3 5 7 12 23 +// same without using c_foreach: +for (csmap_ii_iter i = csmap_ii_begin(&map); i.ref; csmap_ii_next(&i)) + printf(" %d", i.ref->first); + +csmap_ii_iter it = csmap_ii_find(&map, 7); +// iterate from it to end +c_foreach (i, csmap_ii, it, csmap_ii_end(&map)) + printf(" %d", i.ref->first); +// 7 12 23 + +// structured binding: +c_forpair (id, count, csmap_ii, map) + printf(" (%d %d)", *_.id, *_.count); +// (3 2) (5 4) (7 3) (12 5) (23 1) +``` + +### c_forlist +Iterate compound literal array elements. Additional to `i.ref`, you can access `i.size` and `i.index` for the input list/element. +```c +// apply multiple push_backs +c_forlist (i, int, {1, 2, 3}) + cvec_i_push_back(&vec, *i.ref); + +// insert in existing map +c_forlist (i, cmap_ii_raw, { {4, 5}, {6, 7} }) + cmap_ii_insert(&map, i.ref->first, i.ref->second); + +// string literals pushed to a stack of cstr: +c_forlist (i, const char*, {"Hello", "crazy", "world"}) + cstack_str_emplace(&stk, *i.ref); +``` +--- + +## Integer range loops + +### c_forrange +Abstraction for iterating sequence of integers. Like python's **for** *i* **in** *range()* loop. + +| Usage | Python equivalent | +|:---------------------------------------------|:-------------------------------------| +| `c_forrange (stop)` | `for _ in range(stop):` | +| `c_forrange (i, stop) // i type = long long` | `for i in range(stop):` | +| `c_forrange (i, start, stop)` | `for i in range(start, stop):` | +| `c_forrange (i, start, stop, step)` | `for i in range(start, stop, step):` | + +```c +c_forrange (5) printf("x"); +// xxxxx +c_forrange (i, 5) printf(" %lld", i); +// 0 1 2 3 4 +c_forrange (i, -3, 3) printf(" %lld", i); +// -3 -2 -1 0 1 2 +c_forrange (i, 30, 0, -5) printf(" %lld", i); +// 30 25 20 15 10 5 +``` + +### crange: Integer range generator object +A number sequence generator type, similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html). The **crange_value** type is `long long`. Below *start*, *stop*, and *step* are of type *crange_value*: +```c +crange crange_init(stop); // will generate 0, 1, ..., stop-1 +crange crange_init(start, stop); // will generate start, start+1, ... stop-1 +crange crange_init(start, stop, step); // will generate start, start+step, ... upto-not-including stop + // note that step may be negative. +crange_iter crange_begin(crange* self); +crange_iter crange_end(crange* self); +void crange_next(crange_iter* it); + +// 1. All primes less than 32: +crange r1 = crange_init(3, 32, 2); +printf("2"); // first prime +c_forfilter (i, crange, r1, isPrime(*i.ref)) + printf(" %lld", *i.ref); +// 2 3 5 7 11 13 17 19 23 29 31 + +// 2. The first 11 primes: +printf("2"); +crange range = crange_init(3, INT64_MAX, 2); +c_forfilter (i, crange, range, + isPrime(*i.ref) && + c_flt_take(10) +){ + printf(" %lld", *i.ref); +} +// 2 3 5 7 11 13 17 19 23 29 31 +``` + +### c_forfilter +Iterate a container or a crange with chained `&&` filtering. + +| Usage | Description | +|:----------------------------------------------------|:---------------------------------------| +| `c_forfilter (it, ctype, container, filter)` | Filter out items in chain with && | +| `c_forfilter_it (it, ctype, startit, filter)` | Filter from startit iterator position | + +| Built-in filter | Description | +|:----------------------------------|:-------------------------------------------| +| `c_flt_skip(it, numItems)` | Skip numItems (inc count) | +| `c_flt_take(it, numItems)` | Take numItems (inc count) | +| `c_flt_skipwhile(it, predicate)` | Skip items until predicate is false | +| `c_flt_takewhile(it, predicate)` | Take items until predicate is false | +| `c_flt_counter(it)` | Increment current and return count | +| `c_flt_getcount(it)` | Number of items passed skip*/take*/counter | + +[ [Run this example](https://godbolt.org/z/n9aYrYPv8) ] +```c +#include +#include + +bool isPrime(long long i) { + for (long long j=2; j*j <= i; ++j) + if (i % j == 0) return false; + return true; +} + +int main(void) { + // Get 10 prime numbers starting from 1000. Skip the first 15 primes, + // then select every 25th prime (including the initial). + crange R = crange_init(1001, INT64_MAX, 2); // 1001, 1003, ... + + c_forfilter (i, crange, R, + isPrime(*i.ref) && + c_flt_skip(i, 15) && + c_flt_counter(i) % 25 == 1 && + c_flt_take(i, 10) + ){ + printf(" %lld", *i.ref); + } +} +// out: 1097 1289 1481 1637 1861 2039 2243 2417 2657 2803 +``` +Note that `c_flt_take()` and `c_flt_takewhile()` breaks the loop on false. + +--- +## Generic algorithms + +### c_init, c_drop + +Make any container from an initializer list: +```c +#define i_key_str // owned cstr string value type +#include + +#define i_key int +#define i_val int +#include +... +// Initializes with const char*, internally converted to cstr! +cset_str myset = c_init(cset_str, {"This", "is", "the", "story"}); + +int x = 7, y = 8; +cmap_int mymap = c_init(cmap_int, { {1, 2}, {3, 4}, {5, 6}, {x, y} }); +``` +Drop multiple containers of the same type: +```c +c_drop(cset_str, &myset, &myset2); +``` + +### c_find_if, c_erase_if, c_eraseremove_if +Find or erase linearily in containers using a predicate +- For `c_find_if(iter, C, c, pred)`, ***iter*** is in/out and must be declared prior to call. +- Use `c_erase_if(iter, C, c, pred)` with **clist**, **cmap**, **cset**, **csmap**, and **csset**. +- Use `c_eraseremove_if(iter, C, c, pred)` with **cstack**, **cvec**, **cdeq**, and **cqueue**. +```c +// Search vec for first value > 2: +cvec_i_iter i; +c_find_if(i, cvec_i, vec, *i.ref > 2); +if (i.ref) printf("%d\n", *i.ref); + +// Erase all values > 2 in vec: +c_eraseremove_if(i, cvec_i, vec, *i.ref > 2); + +// Search map for a string containing "hello" and erase it: +cmap_str_iter it, it1 = ..., it2 = ...; +c_find_if(it, csmap_str, it1, it2, cstr_contains(it.ref, "hello")); +if (it.ref) cmap_str_erase_at(&map, it); + +// Erase all strings containing "hello" in a sorted map: +c_erase_if(i, csmap_str, map, cstr_contains(i.ref, "hello")); +``` + +### sort_n_ - two times faster qsort + +The **sort_n**, **sort_ij** algorithm is about twice as fast as *qsort()*, and often simpler to use. +You may customize `i_tag` and the comparison function `i_cmp` or `i_less`. + +There is a [benchmark/test file here](../misc/benchmarks/various/csort_bench.c). +```c +#define i_key int +#include +#include + +int main(void) { + int nums[] = {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}; + ints_sort_n(nums, c_arraylen(nums)); // note: function name derived from i_key + c_forrange (i, c_arraylen(arr)) printf(" %d", arr[i]); +} +``` +Containers with random access may also be sorted. Even sorting cdeq/cqueue (with ring buffer) is +possible and very fast. Note that `i_more` must be defined to retain specified template parameters for use by sort: +```c +#define i_type MyDeq +#define i_key int +#define i_more +#include // deque +#include +#include + +int main(void) { + MyDeq deq = c_init(MyDeq, {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}); + MyDeq_sort_n(&deq, MyDeq_size(&deq)); + c_foreach (i, MyDeq, deq) printf(" %d", *i.ref); + MyDeq_drop(&deq); +} +``` + +### c_new, c_delete + +- `c_new(Type, val)` - Allocate *and init* a new object on the heap +- `c_delete(Type, ptr)` - Drop *and free* an object allocated on the heap. NULL is OK. +```c +#include + +cstr *str_p = c_new(cstr, cstr_from("Hello")); +printf("%s\n", cstr_str(str_p)); +c_delete(cstr, str_p); +``` + +### c_malloc, c_calloc, c_realloc, c_free +Memory allocator wrappers that uses signed sizes. + +### c_arraylen +Return number of elements in an array. array must not be a pointer! +```c +int array[] = {1, 2, 3, 4}; +intptr_t n = c_arraylen(array); +``` + +### c_swap, c_const_cast +```c +// Safe macro for swapping internals of two objects of same type: +c_swap(cmap_int, &map1, &map2); + +// Type-safe casting a from const (pointer): +const char cs[] = "Hello"; +char* s = c_const_cast(char*, cs); // OK +int* ip = c_const_cast(int*, cs); // issues a warning! +``` + +### Predefined template parameter functions + +**crawstr** - Non-owned `const char*` "class" element type: `#define i_keyclass crawstr` +```c +typedef const char* crawstr; +int crawstr_cmp(const crawstr* x, const crawstr* y); +bool crawstr_eq(const crawstr* x, const crawstr* y); +uint64_t crawstr_hash(const crawstr* x); +``` +Default implementations +```c +int c_default_cmp(const Type*, const Type*); // <=> +bool c_default_less(const Type*, const Type*); // < +bool c_default_eq(const Type*, const Type*); // == +uint64_t c_default_hash(const Type*); +Type c_default_clone(Type val); // return val +Type c_default_toraw(const Type* p); // return *p +void c_default_drop(Type* p); // does nothing +``` +--- +## RAII scope macros +General ***defer*** mechanics for resource acquisition. These macros allows you to specify the +freeing of the resources at the point where the acquisition takes place. +The **checkauto** utility described below, ensures that the `c_auto*` macros are used correctly. + +| Usage | Description | +|:---------------------------------------|:----------------------------------------------------------| +| `c_defer (drop...)` | Defer `drop...` to end of scope | +| `c_scope (init, drop)` | Execute `init` and defer `drop` to end of scope | +| `c_scope (init, pred, drop)` | Adds a predicate in order to exit early if init failed | +| `c_with (Type var=init, drop)` | Declare `var`. Defer `drop...` to end of scope | +| `c_with (Type var=init, pred, drop)` | Adds a predicate in order to exit early if init failed | +| `c_auto (Type, var1,...,var4)` | `c_with (Type var1=Type_init(), Type_drop(&var1))` ... | +| `continue` | Exit a defer-block without resource leak | + +```c +#include // or +... +// `c_defer` executes the expression(s) when leaving scope. +// Note: does not require inclusion of "raii.h". +cstr s1 = cstr_lit("Hello"), s2 = cstr_lit("world"); +c_defer (cstr_drop(&s1), cstr_drop(&s2)) +{ + printf("%s %s\n", cstr_str(&s1), cstr_str(&s2)); +} + +// `c_scope` syntactically "binds" initialization and defer. +static pthread_mutex_t mut; +c_scope (pthread_mutex_lock(&mut), pthread_mutex_unlock(&mut)) +{ + /* Do syncronized work. */ +} + +// `c_with` is similar to python `with`: declare a variable and defer the drop call. +c_with (cstr str = cstr_lit("Hello"), cstr_drop(&str)) +{ + cstr_append(&str, " world"); + printf("%s\n", cstr_str(&str)); +} + +// `c_auto` automatically initialize and drops up to 4 variables: +c_auto (cstr, s1, s2) +{ + cstr_append(&s1, "Hello"); + cstr_append(&s1, " world"); + cstr_append(&s2, "Cool"); + cstr_append(&s2, " stuff"); + printf("%s %s\n", cstr_str(&s1), cstr_str(&s2)); +} +``` +**Example 1**: Use multiple **c_with** in sequence: +```c +bool ok = false; +c_with (uint8_t* buf = malloc(BUF_SIZE), buf != NULL, free(buf)) +c_with (FILE* fp = fopen(fname, "rb"), fp != NULL, fclose(fp)) +{ + int n = fread(buf, 1, BUF_SIZE, fp); + if (n <= 0) continue; // auto cleanup! NB do not break or return here. + ... + ok = true; +} +return ok; +``` +**Example 2**: Load each line of a text file into a vector of strings: +```c +#include +#define i_implement +#include + +#define i_key_str +#include + +// receiver should check errno variable +cvec_str readFile(const char* name) +{ + cvec_str vec = {0}; // returned + c_with (FILE* fp = fopen(name, "r"), fp != NULL, fclose(fp)) + c_with (cstr line = {0}, cstr_drop(&line)) + while (cstr_getline(&line, fp)) + cvec_str_emplace(&vec, cstr_str(&line)); + return vec; +} + +int main(void) +{ + c_with (cvec_str vec = readFile(__FILE__), cvec_str_drop(&vec)) + c_foreach (i, cvec_str, vec) + printf("| %s\n", cstr_str(i.ref)); +} +``` + +### The **checkauto** utility program (for RAII) +The **checkauto** program will check the source code for any misuses of the `c_auto*` macros which +may lead to resource leakages. The `c_auto*`- macros are implemented as one-time executed **for-loops**, +so any `return` or `break` appearing within such a block will lead to resource leaks, as it will disable +the cleanup/drop method to be called. A `break` may originally be intended to break a loop or switch +outside the `c_auto` scope. + +NOTE: One must always make sure to unwind temporary allocated resources before a `return` in C. However, by using `c_auto*`-macros, +- it is much easier to automatically detect misplaced return/break between resource acquisition and destruction. +- it prevents forgetting to call the destructor at the end. + +The **checkauto** utility will report any misusages. The following example shows how to correctly break/return +from a `c_auto` scope: +```c +int flag = 0; +for (int i = 0; i 0) break; + ... +} +``` diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md deleted file mode 100644 index 0e8d9719..00000000 --- a/docs/ccommon_api.md +++ /dev/null @@ -1,557 +0,0 @@ -# STC Algorithms - ---- -## Ranged for-loops - -### c_foreach, c_forpair - -| Usage | Description | -|:-----------------------------------------|:------------------------------------------| -| `c_foreach (it, ctype, container)` | Iteratate all elements | -| `c_foreach (it, ctype, it1, it2)` | Iterate the range [it1, it2) | -| `c_forpair (key, val, ctype, container)` | Iterate with structured binding | - -```c -#define i_key int -#define i_val int -#define i_tag ii -#include -... -csmap_ii map = c_init(csmap_ii, { {23,1}, {3,2}, {7,3}, {5,4}, {12,5} }); - -c_foreach (i, csmap_ii, map) - printf(" %d", i.ref->first); -// 3 5 7 12 23 -// same without using c_foreach: -for (csmap_ii_iter i = csmap_ii_begin(&map); i.ref; csmap_ii_next(&i)) - printf(" %d", i.ref->first); - -csmap_ii_iter it = csmap_ii_find(&map, 7); -// iterate from it to end -c_foreach (i, csmap_ii, it, csmap_ii_end(&map)) - printf(" %d", i.ref->first); -// 7 12 23 - -// structured binding: -c_forpair (id, count, csmap_ii, map) - printf(" (%d %d)", *_.id, *_.count); -// (3 2) (5 4) (7 3) (12 5) (23 1) -``` - -### c_forlist -Iterate compound literal array elements. Additional to `i.ref`, you can access `i.size` and `i.index` for the input list/element. -```c -// apply multiple push_backs -c_forlist (i, int, {1, 2, 3}) - cvec_i_push_back(&vec, *i.ref); - -// insert in existing map -c_forlist (i, cmap_ii_raw, { {4, 5}, {6, 7} }) - cmap_ii_insert(&map, i.ref->first, i.ref->second); - -// string literals pushed to a stack of cstr: -c_forlist (i, const char*, {"Hello", "crazy", "world"}) - cstack_str_emplace(&stk, *i.ref); -``` - ---- -## Range algorithms - -### c_forrange -Abstraction for iterating sequence of integers. Like python's **for** *i* **in** *range()* loop. - -| Usage | Python equivalent | -|:---------------------------------------------|:-------------------------------------| -| `c_forrange (stop)` | `for _ in range(stop):` | -| `c_forrange (i, stop) // i type = long long` | `for i in range(stop):` | -| `c_forrange (i, start, stop)` | `for i in range(start, stop):` | -| `c_forrange (i, start, stop, step)` | `for i in range(start, stop, step):` | - -```c -c_forrange (5) printf("x"); -// xxxxx -c_forrange (i, 5) printf(" %lld", i); -// 0 1 2 3 4 -c_forrange (i, -3, 3) printf(" %lld", i); -// -3 -2 -1 0 1 2 -c_forrange (i, 30, 0, -5) printf(" %lld", i); -// 30 25 20 15 10 5 -``` - -### crange -A number sequence generator type, similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html). The **crange_value** type is `long long`. Below *start*, *stop*, and *step* are of type *crange_value*: -```c -crange crange_init(stop); // will generate 0, 1, ..., stop-1 -crange crange_init(start, stop); // will generate start, start+1, ... stop-1 -crange crange_init(start, stop, step); // will generate start, start+step, ... upto-not-including stop - // note that step may be negative. -crange_iter crange_begin(crange* self); -crange_iter crange_end(crange* self); -void crange_next(crange_iter* it); - -// 1. All primes less than 32: -crange r1 = crange_init(3, 32, 2); -printf("2"); // first prime -c_forfilter (i, crange, r1, isPrime(*i.ref)) - printf(" %lld", *i.ref); -// 2 3 5 7 11 13 17 19 23 29 31 - -// 2. The first 11 primes: -printf("2"); -crange range = crange_init(3, INT64_MAX, 2); -c_forfilter (i, crange, range, - isPrime(*i.ref) && - c_flt_take(10) -){ - printf(" %lld", *i.ref); -} -// 2 3 5 7 11 13 17 19 23 29 31 -``` - -### c_forfilter -Iterate a container/range with chained range filtering. - -| Usage | Description | -|:----------------------------------------------------|:---------------------------------------| -| `c_forfilter (it, ctype, container, filter)` | Filter out items in chain with && | -| `c_forfilter_it (it, ctype, startit, filter)` | Filter from startit position | - -| Built-in filter | Description | -|:----------------------------------|:-------------------------------------------| -| `c_flt_skip(it, numItems)` | Skip numItems (inc count) | -| `c_flt_take(it, numItems)` | Take numItems (inc count) | -| `c_flt_skipwhile(it, predicate)` | Skip items until predicate is false | -| `c_flt_takewhile(it, predicate)` | Take items until predicate is false | -| `c_flt_counter(it)` | Increment current and return count | -| `c_flt_getcount(it)` | Number of items passed skip*/take*/counter | - -[ [Run this example](https://godbolt.org/z/n9aYrYPv8) ] -```c -#include -#include - -bool isPrime(long long i) { - for (long long j=2; j*j <= i; ++j) - if (i % j == 0) return false; - return true; -} - -int main(void) { - // Get 10 prime numbers starting from 1000. Skip the first 15 primes, - // then select every 25th prime (including the initial). - crange R = crange_init(1001, INT64_MAX, 2); // 1001, 1003, ... - - c_forfilter (i, crange, R, - isPrime(*i.ref) && - c_flt_skip(i, 15) && - c_flt_counter(i) % 25 == 1 && - c_flt_take(i, 10) - ){ - printf(" %lld", *i.ref); - } -} -// out: 1097 1289 1481 1637 1861 2039 2243 2417 2657 2803 -``` -Note that `c_flt_take()` and `c_flt_takewhile()` breaks the loop on false. - ---- -## Generic algorithms - -### c_init, c_drop - -Make any container from an initializer list: -```c -#define i_key_str // owned cstr string value type -#include - -#define i_key int -#define i_val int -#include -... -// Initializes with const char*, internally converted to cstr! -cset_str myset = c_init(cset_str, {"This", "is", "the", "story"}); - -int x = 7, y = 8; -cmap_int mymap = c_init(cmap_int, { {1, 2}, {3, 4}, {5, 6}, {x, y} }); -``` -Drop multiple containers of the same type: -```c -c_drop(cset_str, &myset, &myset2); -``` - -### c_find_if, c_erase_if, c_eraseremove_if -Find or erase linearily in containers using a predicate -- For `c_find_if(iter, C, c, pred)`, ***iter*** is in/out and must be declared prior to call. -- Use `c_erase_if(iter, C, c, pred)` with **clist**, **cmap**, **cset**, **csmap**, and **csset**. -- Use `c_eraseremove_if(iter, C, c, pred)` with **cstack**, **cvec**, **cdeq**, and **cqueue**. -```c -// Search vec for first value > 2: -cvec_i_iter i; -c_find_if(i, cvec_i, vec, *i.ref > 2); -if (i.ref) printf("%d\n", *i.ref); - -// Erase all values > 2 in vec: -c_eraseremove_if(i, cvec_i, vec, *i.ref > 2); - -// Search map for a string containing "hello" and erase it: -cmap_str_iter it, it1 = ..., it2 = ...; -c_find_if(it, csmap_str, it1, it2, cstr_contains(it.ref, "hello")); -if (it.ref) cmap_str_erase_at(&map, it); - -// Erase all strings containing "hello" in a sorted map: -c_erase_if(i, csmap_str, map, cstr_contains(i.ref, "hello")); -``` - -### sort_n_ - two times faster qsort - -The **sort_n**, **sort_ij** algorithm is about twice as fast as *qsort()*, and often simpler to use. -You may customize `i_tag` and the comparison function `i_cmp` or `i_less`. - -There is a [benchmark/test file here](../misc/benchmarks/various/csort_bench.c). -```c -#define i_key int -#include -#include - -int main(void) { - int nums[] = {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}; - intarray_sort_n(nums, c_arraylen(nums)); - c_forrange (i, c_arraylen(arr)) printf(" %d", arr[i]); -} -``` -Containers with random access may also be sorted. Even sorting cdeq/cqueue (with ring buffer) is -possible and very fast. Note that `i_more` must be defined to retain specified template parameters for use by sort: -```c -#define i_type MyDeq -#define i_key int -#define i_more -#include // deque -#include -#include - -int main(void) { - MyDeq deq = c_init(MyDeq, {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}); - MyDeq_sort_n(&deq, MyDeq_size(&deq)); - c_foreach (i, MyDeq, deq) printf(" %d", *i.ref); - MyDeq_drop(&deq); -} -``` - -### c_new, c_delete - -- `c_new(Type, val)` - Allocate *and init* a new object on the heap -- `c_delete(Type, ptr)` - Drop *and free* an object allocated on the heap. NULL is OK. -```c -#include - -cstr *str_p = c_new(cstr, cstr_from("Hello")); -printf("%s\n", cstr_str(str_p)); -c_delete(cstr, str_p); -``` - -### c_malloc, c_calloc, c_realloc, c_free -Memory allocator wrappers that uses signed sizes. - -### c_arraylen -Return number of elements in an array. array must not be a pointer! -```c -int array[] = {1, 2, 3, 4}; -intptr_t n = c_arraylen(array); -``` - -### c_swap, c_const_cast -```c -// Safe macro for swapping internals of two objects of same type: -c_swap(cmap_int, &map1, &map2); - -// Type-safe casting a from const (pointer): -const char cs[] = "Hello"; -char* s = c_const_cast(char*, cs); // OK -int* ip = c_const_cast(int*, cs); // issues a warning! -``` - -### Predefined template parameter functions - -**crawstr** - Non-owned `const char*` "class" element type: `#define i_keyclass crawstr` -```c -typedef const char* crawstr; -int crawstr_cmp(const crawstr* x, const crawstr* y); -bool crawstr_eq(const crawstr* x, const crawstr* y); -uint64_t crawstr_hash(const crawstr* x); -``` -Default implementations -```c -int c_default_cmp(const Type*, const Type*); // <=> -bool c_default_less(const Type*, const Type*); // < -bool c_default_eq(const Type*, const Type*); // == -uint64_t c_default_hash(const Type*); -Type c_default_clone(Type val); // return val -Type c_default_toraw(const Type* p); // return *p -void c_default_drop(Type* p); // does nothing -``` - ---- -## Coroutines -This is a much improved implementation of -[Simon Tatham's coroutines](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html), -which utilizes the *Duff's device* trick. Tatham's implementation is not typesafe, -and it always allocates the coroutine's internal state dynamically. But crucially, -it does not let the coroutine do self-cleanup on early finish - i.e. it -only frees the initial dynamically allocated memory. - -In this implementation, a coroutine may have any signature, but it should -take a struct pointer as parameter, which must contain the member `int cco_state;` -The struct should normally store all the *local* variables to be used in the -coroutine. It can also store input and output data if desired. - -The coroutine example below generates Pythagorian triples, but the calling loop -skips the triples which are upscaled version of smaller ones, by checking -the gcd() function. It also ensures that it stops when the diagonal size >= 100: - -[ [Run this code](https://godbolt.org/z/coqqrfbd5) ] -```c -#include -#include - -struct triples { - int n; // input: max number of triples to be generated. - int a, b, c; - int cco_state; // required member -}; - -int triples(struct triples* i) { // coroutine - cco_routine(i) { - for (i->c = 5; i->n; ++i->c) { - for (i->a = 1; i->a < i->c; ++i->a) { - for (i->b = i->a + 1; i->b < i->c; ++i->b) { - if ((int64_t)i->a*i->a + (int64_t)i->b*i->b == (int64_t)i->c*i->c) { - cco_yield(); - if (--i->n == 0) - cco_return; - } - } - } - } - cco_cleanup: - puts("done"); - } - return 0; -} - -int gcd(int a, int b) { // greatest common denominator - while (b) { - int t = a % b; - a = b; - b = t; - } - return a; -} - -int main(void) -{ - struct triples t = {.n=INT32_MAX}; - int n = 0; - - while (triples(&t)) { - // Skip triples with GCD(a,b) > 1 - if (gcd(t.a, t.b) > 1) - continue; - - // Stop when c >= 100 - if (t.c < 100) - printf("%d: [%d, %d, %d]\n", ++n, t.a, t.b, t.c); - else - cco_stop(&t); // cleanup in next coroutine call/resume - } -} -``` -### Coroutine API -To resume the coroutine from where it was suspended with *cco_yield()*: call the coroutine again. - -**Note**: *cco_yield()* / *cco_await()* may not be called inside a `switch` statement from a -cco_routine scope; Use `if-else-if` constructs instead. - -| | Function / operator | Description | -|:----------|:-------------------------------------|:----------------------------------------| -|`cco_result` | `CCO_DONE`, `CCO_AWAIT`, `CCO_YIELD` | Default set of return values from coroutines | -| | `cco_cleanup:` | Label for cleanup position in coroutine | -| `bool` | `cco_done(co)` | Is coroutine done? | -| | `cco_routine(co) {}` | The coroutine scope | -| | `cco_yield();` | Yield/suspend execution (return CCO_YIELD)| -| | `cco_yield_v(ret);` | Yield/suspend execution (return ret) | -| | `cco_yield_final();` | Yield final suspend, enter cleanup-state | -| | `cco_yield_final(ret);` | Yield a final value | -| | `cco_await(condition);` | Suspend until condition is true (return CCO_AWAIT)| -| | `cco_call_await(cocall);` | Await for subcoro to finish (returns its ret value) | -| | `cco_call_await(cocall, retbit);` | Await for subcoro's return to be in (retbit \| CCO_DONE) | -| | `cco_return;` | Return from coroutine (inside cco_routine) | -| | Task objects: | | -| | `cco_task_struct(Name, ...);` | Define a coroutine task struct | -| | `cco_task_await(task, cco_runtime* rt);`| Await for task to finish | -| | `cco_task_await(task, rt, retbit);` | Await for task's return to be in (retbit \| CCO_DONE) | -|`cco_result`| `cco_task_resume(task, rt);` | Resume suspended task | -| | Semaphores: | | -| | `cco_sem` | Semaphore type | -| `cco_sem` | `cco_sem_from(long value)` | Create semaphore | -| | `cco_sem_set(sem, long value)` | Set semaphore value | -| | `cco_sem_await(sem)` | Await for the semaphore count > 0 | -| | `cco_sem_release(sem)` | Signal the semaphore (count += 1) | -| | Timers: | | -| | `cco_timer` | Timer type | -| | `cco_timer_await(tm, double sec)` | Await secs for timer to expire (usec prec.)| -| | `cco_timer_start(tm, double sec)` | Start timer for secs duration | -| | `cco_timer_restart(tm)` | Restart timer with same duration | -| `bool` | `cco_timer_expired(tm)` | Return true if timer is expired | -| `double` | `cco_timer_elapsed(tm)` | Return seconds elapsed | -| `double` | `cco_timer_remaining(tm)` | Return seconds remaining | -| | From caller side: | | -| `void` | `cco_stop(co)` | Next call of coroutine finalizes | -| `void` | `cco_reset(co)` | Reset state to initial (for reuse) | -| `void` | `cco_call_blocking(cocall) {}` | Run blocking until cocall is finished | -| `void` | `cco_call_blocking(cocall, int* outres) {}`| Run blocking until cocall is finished | -| | `cco_task_blocking(task) {}` | Run blocking until task is finished | -| | `cco_task_blocking(task, rt, STACKSZ) {}`| Run blocking until task is finished | -| | Time functions: | | -| `double` | `cco_time(void)` | Return secs with usec prec. since Epoch | -| | `cco_sleep(double sec)` | Sleep for seconds (msec or usec prec.) | - ---- -## RAII scope macros -General ***defer*** mechanics for resource acquisition. These macros allows you to specify the -freeing of the resources at the point where the acquisition takes place. -The **checkauto** utility described below, ensures that the `c_auto*` macros are used correctly. - -| Usage | Description | -|:---------------------------------------|:----------------------------------------------------------| -| `c_defer (drop...)` | Defer `drop...` to end of scope | -| `c_scope (init, drop)` | Execute `init` and defer `drop` to end of scope | -| `c_scope (init, pred, drop)` | Adds a predicate in order to exit early if init failed | -| `c_with (Type var=init, drop)` | Declare `var`. Defer `drop...` to end of scope | -| `c_with (Type var=init, pred, drop)` | Adds a predicate in order to exit early if init failed | -| `c_auto (Type, var1,...,var4)` | `c_with (Type var1=Type_init(), Type_drop(&var1))` ... | -| `continue` | Exit a defer-block without resource leak | - -```c -#include // or -... -// `c_defer` executes the expression(s) when leaving scope. -// Note: does not require inclusion of "raii.h". -cstr s1 = cstr_lit("Hello"), s2 = cstr_lit("world"); -c_defer (cstr_drop(&s1), cstr_drop(&s2)) -{ - printf("%s %s\n", cstr_str(&s1), cstr_str(&s2)); -} - -// `c_scope` syntactically "binds" initialization and defer. -static pthread_mutex_t mut; -c_scope (pthread_mutex_lock(&mut), pthread_mutex_unlock(&mut)) -{ - /* Do syncronized work. */ -} - -// `c_with` is similar to python `with`: declare a variable and defer the drop call. -c_with (cstr str = cstr_lit("Hello"), cstr_drop(&str)) -{ - cstr_append(&str, " world"); - printf("%s\n", cstr_str(&str)); -} - -// `c_auto` automatically initialize and drops up to 4 variables: -c_auto (cstr, s1, s2) -{ - cstr_append(&s1, "Hello"); - cstr_append(&s1, " world"); - cstr_append(&s2, "Cool"); - cstr_append(&s2, " stuff"); - printf("%s %s\n", cstr_str(&s1), cstr_str(&s2)); -} -``` -**Example 1**: Use multiple **c_with** in sequence: -```c -bool ok = false; -c_with (uint8_t* buf = malloc(BUF_SIZE), buf != NULL, free(buf)) -c_with (FILE* fp = fopen(fname, "rb"), fp != NULL, fclose(fp)) -{ - int n = fread(buf, 1, BUF_SIZE, fp); - if (n <= 0) continue; // auto cleanup! NB do not break or return here. - ... - ok = true; -} -return ok; -``` -**Example 2**: Load each line of a text file into a vector of strings: -```c -#include -#define i_implement -#include - -#define i_key_str -#include - -// receiver should check errno variable -cvec_str readFile(const char* name) -{ - cvec_str vec = {0}; // returned - c_with (FILE* fp = fopen(name, "r"), fp != NULL, fclose(fp)) - c_with (cstr line = {0}, cstr_drop(&line)) - while (cstr_getline(&line, fp)) - cvec_str_emplace(&vec, cstr_str(&line)); - return vec; -} - -int main(void) -{ - c_with (cvec_str vec = readFile(__FILE__), cvec_str_drop(&vec)) - c_foreach (i, cvec_str, vec) - printf("| %s\n", cstr_str(i.ref)); -} -``` - -### The **checkauto** utility program (for RAII) -The **checkauto** program will check the source code for any misuses of the `c_auto*` macros which -may lead to resource leakages. The `c_auto*`- macros are implemented as one-time executed **for-loops**, -so any `return` or `break` appearing within such a block will lead to resource leaks, as it will disable -the cleanup/drop method to be called. A `break` may originally be intended to break a loop or switch -outside the `c_auto` scope. - -NOTE: One must always make sure to unwind temporary allocated resources before a `return` in C. However, by using `c_auto*`-macros, -- it is much easier to automatically detect misplaced return/break between resource acquisition and destruction. -- it prevents forgetting to call the destructor at the end. - -The **checkauto** utility will report any misusages. The following example shows how to correctly break/return -from a `c_auto` scope: -```c -int flag = 0; -for (int i = 0; i 0) break; - ... -} -``` diff --git a/docs/cspan_api.md b/docs/cspan_api.md index e1c92bbf..1312ae6d 100644 --- a/docs/cspan_api.md +++ b/docs/cspan_api.md @@ -21,10 +21,11 @@ using_cspan4(S, ValueType); // define span types S, S2, S3, S4 with ``` ## Methods -All functions are type-safe. Note that the span argument itself is generally not side-effect safe, -i.e., it may be expanded multiple times. However, all index arguments are safe, e.g. -`cspan_at(&ms3, i++, j++, k++)` is allowed. If the number of arguments does not match the span rank, -a compile error is issued. Runtime bounds checks are enabled by default (define `STC_NDEBUG` or `NDEBUG` to disable). +All functions are type-safe. NOTE: the span argument itself is generally **not** side-effect safe - +it may be expanded multiple times. However, all index arguments are safe, e.g. +`cspan_at(&ms3, i++, j++, k++)` is safe, but `cspan_at(&spans[n++], i, j)` is an error! If the number +of arguments does not match the span rank, a compile error is issued. Runtime bounds checks are enabled +by default (define `STC_NDEBUG` or `NDEBUG` to disable). ```c SpanType cspan_init(TYPE SpanType, {v1, v2, ...}); // make a 1-d cspan from values SpanType cspan_from(STCContainer* cnt); // make a 1-d cspan from a cvec, cstack, cpque (heap) @@ -45,7 +46,7 @@ void SpanType_next(SpanTypeN_iter* it); SpanTypeN cspan_md(ValueType* data, d1, d2, ...); // make a multi-dim cspan, row-major order. SpanTypeN cspan_md_order(char order, ValueType* data, d1, d2, ...); // order='C': row-major, 'F': column-major (FORTRAN). - // transpose a md span (inverse axes). no changes to the underlying array. + // transpose a md span (inverse axes). No changes to the underlying array. void cspan_transpose(const SpanTypeN* self); bool cspan_is_order_F(const SpanTypeN* self); -- cgit v1.2.3