diff options
Diffstat (limited to 'docs/ccommon_api.md')
| -rw-r--r-- | docs/ccommon_api.md | 525 |
1 files changed, 326 insertions, 199 deletions
diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index 8dcb2ff3..7a3c3196 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -1,106 +1,16 @@ -# STC [ccommon](../include/stc/ccommon.h): Generic algorithms and macros +# STC Algorithms -The following macros are recommended to use, and they safe/have no side-effects. +--- +## Ranged for-loops -## Scope macros (RAII) -### c_auto, c_with, c_scope, c_defer -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. +### c_foreach, c_foreach_rv, c_forpair -| Usage | Description | -|:---------------------------------------|:----------------------------------------------------------| -| `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))` ... | -| `c_scope (init, drop)` | Execute `init` and defer `drop` to end of scope | -| `c_defer (drop...)` | Defer `drop...` to end of scope | -| `continue` | Exit a block above without memory leaks | - -For multiple variables, use either multiple **c_with** in sequence, or declare variable outside -scope and use **c_scope**. For convenience, **c_auto** support up to 4 variables. -```c -// `c_with` is similar to python `with`: it declares and can drop a variable after going out of scope. -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; - -// `c_auto` automatically initialize and destruct 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)); -} - -// `c_with` is a general variant of `c_auto`: -c_with (cstr str = cstr_lit("Hello"), cstr_drop(&str)) -{ - cstr_append(&str, " world"); - printf("%s\n", cstr_str(&str)); -} - -// `c_scope` is like `c_with` but works with an already declared variable. -static pthread_mutex_t mut; -c_scope (pthread_mutex_lock(&mut), pthread_mutex_unlock(&mut)) -{ - /* Do syncronized work. */ -} - -// `c_defer` executes the expressions when leaving scope. Prefer c_with or c_scope. -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)); -} -``` -**Example**: Load each line of a text file into a vector of strings: -```c -#include <errno.h> -#include <stc/cstr.h> - -#define i_val_str -#include <stc/cvec.h> - -// receiver should check errno variable -cvec_str readFile(const char* name) -{ - cvec_str vec = cvec_str_init(); // returned - - c_with (FILE* fp = fopen(name, "r"), fp != NULL, fclose(fp)) - c_with (cstr line = cstr_NULL, cstr_drop(&line)) - while (cstr_getline(&line, fp)) - cvec_str_emplace_back(&vec, cstr_str(&line)); - return vec; -} - -int main() -{ - c_with (cvec_str x = readFile(__FILE__), cvec_str_drop(&x)) - c_foreach (i, cvec_str, x) - printf("%s\n", cstr_str(i.ref)); -} -``` -## Loop abstraction macros - -### 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 | +| Usage | Description | +|:-----------------------------------------|:------------------------------------------| +| `c_foreach (it, ctype, container)` | Iteratate all elements | +| `c_foreach (it, ctype, it1, it2)` | Iterate the range [it1, it2) | +| `c_foreach_rv (it, ctype, container)` | Iteratate in reverse (cstack, cvec, cdeq) | +| `c_forpair (key, val, ctype, container)` | Iterate with structured binding | ```c #define i_key int @@ -129,6 +39,25 @@ c_forpair (id, count, csmap_ii, map) // (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.data`, `i.size`, and `i.index` of 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. @@ -150,46 +79,56 @@ c_forrange (i, 30, 0, -5) printf(" %lld", i); // 30 25 20 15 10 5 ``` -### c_forlist -Iterate compound literal array elements. Additional to `i.ref`, you can access `i.data`, `i.size`, and `i.index` of the input list/element. +### 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 -// 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); +crange& crange_obj(...) // create a compound literal crange object +crange crange_make(stop); // will generate 0, 1, ..., stop-1 +crange crange_make(start, stop); // will generate start, start+1, ... stop-1 +crange crange_make(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); -// string literals pushed to a stack of cstr: -c_forlist (i, const char*, {"Hello", "crazy", "world"}) - cstack_str_emplace(&stk, *i.ref); +// 1. All primes less than 32: +crange r1 = crange_make(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 -// reverse the list: -c_forlist (i, int, {1, 2, 3}) - cvec_i_push_back(&vec, i.data[i.size - 1 - i.index]); +// 2. The first 11 primes: +printf("2"); +c_forfilter (i, crange, crange_obj(3, INT64_MAX, 2), + 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 containers with stop-criteria and chained range filtering. +Iterate a container/range with chained range filtering. | Usage | Description | |:----------------------------------------------------|:---------------------------------------| | `c_forfilter (it, ctype, container, filter)` | Filter out items in chain with && | -| `c_forwhile (it, ctype, start, pred)` | Iterate until pred is false | - -| 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_count(it)` | Increment current and return value | -| `c_flt_last(it)` | Get value of last count/skip/take | +| `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 -// Example: -#include <stc/algo/crange.h> -#include <stc/algo/filter.h> +#include <stc/calgo.h> #include <stdio.h> bool isPrime(long long i) { @@ -197,59 +136,33 @@ bool isPrime(long long i) { if (i % j == 0) return false; return true; } + int main() { - // Get 10 prime numbers starting from 1000. - // Skip the first 24 primes, then select every 15th prime. - crange R = crange_make(1001, INT32_MAX, 2); + // Get 10 prime numbers starting from 1000. Skip the first 15 primes, + // then select every 25th prime (including the initial). + crange R = crange_make(1001, INT64_MAX, 2); // 1001, 1003, ... c_forfilter (i, crange, R, - isPrime(*i.ref) - && c_flt_skip(i, 24) - && c_flt_count(i) % 15 == 1 - && c_flt_take(i, 10)) + isPrime(*i.ref) && + c_flt_skip(i, 15) && + c_flt_counter(i) % 25 == 1 && + c_flt_take(i, 10) + ){ printf(" %lld", *i.ref); - puts(""); + } } -// out: 1171 1283 1409 1493 1607 1721 1847 1973 2081 2203 +// 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. +Note that `c_flt_take()` and `c_flt_takewhile()` breaks the loop on false. -## Generators +--- +## Generic algorithms -### 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_obj(...) // create a compound literal crange object -crange crange_make(stop); // will generate 0, 1, ..., stop-1 -crange crange_make(start, stop); // will generate start, start+1, ... stop-1 -crange crange_make(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_make(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 +### c_make, c_drop -// 2. The 11 first primes: -printf("2"); -c_forfilter (i, crange, crange_obj(3, INT64_MAX, 2) - , isPrime(*i.ref) - && c_flt_take(10)) - printf(" %lld", *i.ref); -// 2 3 5 7 11 13 17 19 23 29 31 -``` -## Algorithms - -### c_make, c_new, c_delete - -- *c_make(C, {...})*: Make any container from an initializer list. Example: +Make any container from an initializer list: ```c -#define i_val_str // cstr value type +#define i_val_str // owned cstr string value type #include <stc/cset.h> #define i_key int @@ -258,26 +171,21 @@ c_forfilter (i, crange, crange_obj(3, INT64_MAX, 2) ... // Initializes with const char*, internally converted to cstr! cset_str myset = c_make(cset_str, {"This", "is", "the", "story"}); +cset_str myset2 = c_clone(myset); int x = 7, y = 8; cmap_int mymap = c_make(cmap_int, { {1, 2}, {3, 4}, {5, 6}, {x, y} }); ``` - -- ***c_new(Type)***: Allocate *and init* a new object on the heap -- ***c_delete(Type, ptr)***: Drop *and free* an object allocated on the heap +Drop multiple containers of the same type: ```c -#include <stc/cstr.h> - -cstr *stringptr = c_new(cstr, cstr_from("Hello")); -printf("%s\n", cstr_str(stringptr)); -c_delete(cstr, stringptr); +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*** must be declared outside/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**. +- 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; @@ -296,29 +204,36 @@ if (it.ref) cmap_str_erase_at(&map, it); c_erase_if(i, csmap_str, map, cstr_contains(i.ref, "hello")); ``` -### c_swap, c_drop +### csort - two times faster qsort + +When very fast array sorting is required, **csort** 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 -// Safe macro for swapping internals of two objects of same type: -c_swap(cmap_int, &map1, &map2); +#define i_val int +#include <stc/algo/csort.h> -// Drop multiple containers of same type: -c_drop(cvec_i, &vec1, &vec2, &vec3); +int main() { + int array[] = {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}; + csort_int(array, c_arraylen(array)); +} ``` -### General predefined template parameter functions + +### 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 -int c_default_cmp(const Type*, const Type*); -Type c_default_clone(Type val); // simple copy -Type c_default_toraw(const Type* val); // dereference val -void c_default_drop(Type* val); // does nothing +#include <stc/cstr.h> -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); +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: customizable allocators +### c_malloc, c_calloc, c_realloc, c_free Memory allocator wrappers that uses signed sizes. ### c_arraylen @@ -328,7 +243,219 @@ int array[] = {1, 2, 3, 4}; intptr_t n = c_arraylen(array); ``` -## The **checkauto** utility program (for RAII) +### 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_valclass 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 <stc/calgo.h> + +struct triples { + int n; // input: max number of triples to be generated. + int a, b, c; + int cco_state; // required member +}; + +bool triples_next(struct triples* i) { // coroutine + cco_begin(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(true); + if (--i->n == 0) cco_return; + } + } + } + } + cco_final: // required label + puts("done"); + cco_end(false); +} + +int gcd(int a, int b) { // greatest common denominator + while (b) { + int t = a % b; + a = b; + b = t; + } + return a; +} + +int main() +{ + struct triples t = {.n=INT32_MAX}; + int n = 0; + + while (triples_next(&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 +**Note**: *cco_yield()* may not be called inside a `switch` statement. Use `if-else-if` constructs instead. +To resume the coroutine from where it was suspended with *cco_yield()*, simply call the coroutine again. + +| | Function / operator | Description | +|:----------|:-------------------------------------|:----------------------------------------| +| | `cco_final:` | Obligatory label in coroutine | +| | `cco_return;` | Early return from the coroutine | +| `bool` | `cco_alive(ctx)` | Is coroutine in initial or suspended state? | +| `bool` | `cco_suspended(ctx)` | Is coroutine in suspended state? | +| `void` | `cco_begin(ctx)` | Begin coroutine block | +| `rettype` | `cco_end(retval)` | End coroutine block with return value | +| `void` | `cco_end()` | End coroutine block | +| `rettype` | `cco_yield(retval)` | Suspend execution and return a value | +| `void` | `cco_yield()` | Suspend execution | +| `rettype` | `cco_yield(corocall2, ctx2, retval)` | Yield from another coroutine and return val | +| `void` | `cco_yield(corocall2, ctx2)` | Yield from another coroutine | +| | From the caller side: | | +| `void` | `cco_stop(ctx)` | Next call of coroutine returns `cco_end()` | +| `void` | `cco_reset(ctx)` | Reset state to initial (for reuse) | + +--- +## 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 +// `c_defer` executes the expression(s) when leaving scope. +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 <errno.h> +#include <stc/cstr.h> + +#define i_val_str +#include <stc/cvec.h> + +// 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() +{ + 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 |