From e8aed0431140fd0d202d302f19f756046858bad7 Mon Sep 17 00:00:00 2001 From: tylov Date: Sun, 23 Jul 2023 23:48:00 +0200 Subject: Updated docs. --- docs/algorithm_api.md | 434 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 434 insertions(+) create mode 100644 docs/algorithm_api.md (limited to 'docs/algorithm_api.md') 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; + ... +} +``` -- cgit v1.2.3 From d7fba27af452de2d709767e615fa2e90d6b3a391 Mon Sep 17 00:00:00 2001 From: tylov Date: Wed, 26 Jul 2023 21:23:15 +0200 Subject: Added cmap_emplace_key() / csmap_emplace_key() More docs. --- README.md | 29 +++++----- docs/algorithm_api.md | 4 +- docs/cmap_api.md | 8 ++- docs/csmap_api.md | 1 + include/stc/algo/filter.h | 2 +- include/stc/cmap.h | 87 +++++++++++++++------------- include/stc/csmap.h | 30 ++++++---- include/stc/forward.h | 1 + misc/examples/smartpointers/arc_containers.c | 1 - misc/tests/cspan_test.c | 4 +- 10 files changed, 95 insertions(+), 72 deletions(-) (limited to 'docs/algorithm_api.md') diff --git a/README.md b/README.md index 9b6698e5..d66a7f1c 100644 --- a/README.md +++ b/README.md @@ -619,23 +619,24 @@ STC is generally very memory efficient. Memory usage for the different container # Version History ## Version 4.3 -- Some breaking changes. -- **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. +- Some breaking changes: + - **cstr** and **csview** now uses *shared linking* by default. Implement by either defining `i_implement` or `i_static` before including. + - Changes in `coroutine.h`: much improved with some new API and added features. + - Renamed stc/calgo.h => `` + - Removed deprecated stc/crandom.h. Use `` with the new API. + - Removed default comparison for **clist**, **cvec** and **cdeq**: + - Define `i_cmp_native` to enable comparison for built-in i_key types (<, ==). + - Use of `i_keyclass` still expects comparison functions to be defined. + - Use of `i_keyboxed` compares hosted pointers instead of pointed to values if comparisons not defined. + - Renamed input enum flags for ***cregex***-functions. +- **cspan**: Changed representation of strides to add **column-major** order (fortran) multidimensional spans and transposed views. - 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. +- Renamed i_extern => `i_import` (i_extern deprecated). + - Define `i_import` before `#include ` will also define full 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. +- Renamed c_make() => ***c_init()*** macro for initializing containers with element lists. c_make deprecated. - Removed deprecated uppercase flow-control macro names. -- Improved default string hash function. +- Other smaller additions, bug fixes and improved documentation. ## Version 4.2 - New home! And online single headers for https://godbolt.org diff --git a/docs/algorithm_api.md b/docs/algorithm_api.md index 490771b5..40ff32d6 100644 --- a/docs/algorithm_api.md +++ b/docs/algorithm_api.md @@ -130,7 +130,7 @@ Iterate a container or a crange with chained `&&` filtering. [ [Run this example](https://godbolt.org/z/n9aYrYPv8) ] ```c -#include +#include #include bool isPrime(long long i) { @@ -309,8 +309,6 @@ The **checkauto** utility described below, ensures that the `c_auto*` macros are | `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"); diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 17f27662..4e6da57d 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -71,7 +71,8 @@ cmap_X_result cmap_X_insert_or_assign(cmap_X* self, i_key key, i_val map cmap_X_result cmap_X_push(cmap_X* self, cmap_X_value entry); // similar to insert cmap_X_result cmap_X_emplace(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map -cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update +cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update mapped +cmap_X_result cmap_X_emplace_key(cmap_X* self, i_keyraw rkey); // see example 1. int cmap_X_erase(cmap_X* self, i_keyraw rkey); // return 0 or 1 cmap_X_iter cmap_X_erase_at(cmap_X* self, cmap_X_iter it); // return iter after it @@ -138,6 +139,11 @@ int main(void) cmap_str_emplace(&umap, "BLACK", "#000000"); cmap_str_emplace(&umap, "WHITE", "#FFFFFF"); + // Insert only if "CYAN" is not in the map: create mapped value when needed only. + cmap_str_result res = cmap_str_emplace_key(&umap, "CYAN"); + if (res.inserted) + res.ref->second = cstr_from("#00FFFF"); // must assign second if key was inserted. + // Output values by key printf("The HEX of color RED is:[%s]\n", cstr_str(cmap_str_at(&umap, "RED"))); printf("The HEX of color BLACK is:[%s]\n", cstr_str(cmap_str_at(&umap, "BLACK"))); diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 164b0f8a..d739283b 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -72,6 +72,7 @@ csmap_X_result csmap_X_push(csmap_X* self, csmap_X_value entry); csmap_X_result csmap_X_emplace(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map csmap_X_result csmap_X_emplace_or_assign(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped +csmap_X_result csmap_X_emplace_key(csmap_X* self, i_keyraw rkey); // if key not in map, mapped is left unassigned int csmap_X_erase(csmap_X* self, i_keyraw rkey); csmap_X_iter csmap_X_erase_at(csmap_X* self, csmap_X_iter it); // returns iter after it diff --git a/include/stc/algo/filter.h b/include/stc/algo/filter.h index 1a62c3e1..320cd50d 100644 --- a/include/stc/algo/filter.h +++ b/include/stc/algo/filter.h @@ -24,7 +24,7 @@ #include #define i_val int #include -#include +#include int main(void) { diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 513a8b93..2dd8cbe6 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -55,7 +55,6 @@ int main(void) { #include #include struct chash_slot { uint8_t hashx; }; -typedef struct { intptr_t idx; uint8_t hashx, found; } chash_bucket; #endif // CMAP_H_INCLUDED #ifndef _i_prefix @@ -94,7 +93,7 @@ STC_API _cx_Self _cx_MEMB(_clone)(_cx_Self map); STC_API void _cx_MEMB(_drop)(_cx_Self* self); STC_API void _cx_MEMB(_clear)(_cx_Self* self); STC_API bool _cx_MEMB(_reserve)(_cx_Self* self, intptr_t capacity); -STC_API chash_bucket _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr); +STC_API _cx_result _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr); STC_API _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey); STC_API void _cx_MEMB(_erase_entry)(_cx_Self* self, _cx_value* val); STC_API float _cx_MEMB(_max_load_factor)(const _cx_Self* self); @@ -106,9 +105,9 @@ STC_INLINE bool _cx_MEMB(_empty)(const _cx_Self* map) { return !map->siz STC_INLINE intptr_t _cx_MEMB(_size)(const _cx_Self* map) { return (intptr_t)map->size; } STC_INLINE intptr_t _cx_MEMB(_bucket_count)(_cx_Self* map) { return map->bucket_count; } STC_INLINE bool _cx_MEMB(_contains)(const _cx_Self* self, _cx_keyraw rkey) - { return self->size && _cx_MEMB(_bucket_)(self, &rkey).found; } + { return self->size && !_cx_MEMB(_bucket_)(self, &rkey).inserted; } -#ifndef _i_isset +#ifdef _i_ismap STC_API _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key key, i_val mapped); #if !defined i_no_emplace STC_API _cx_result _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped); @@ -116,14 +115,15 @@ STC_INLINE bool _cx_MEMB(_contains)(const _cx_Self* self, _cx_keyraw rke STC_INLINE const _cx_mapped* _cx_MEMB(_at)(const _cx_Self* self, _cx_keyraw rkey) { - chash_bucket b = _cx_MEMB(_bucket_)(self, &rkey); - c_assert(b.found); - return &self->data[b.idx].second; + _cx_result b = _cx_MEMB(_bucket_)(self, &rkey); + c_assert(!b.inserted); + return &b.ref->second; } + STC_INLINE _cx_mapped* _cx_MEMB(_at_mut)(_cx_Self* self, _cx_keyraw rkey) { return (_cx_mapped*)_cx_MEMB(_at)(self, rkey); } -#endif // !_i_isset +#endif // _i_ismap #if !defined i_no_clone STC_INLINE void _cx_MEMB(_copy)(_cx_Self *self, const _cx_Self* other) { @@ -151,6 +151,16 @@ _cx_MEMB(_emplace)(_cx_Self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmappe } return _res; } + +#ifdef _i_ismap + STC_INLINE _cx_result + _cx_MEMB(_emplace_key)(_cx_Self* self, _cx_keyraw rkey) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, rkey); + if (_res.inserted) + _res.ref->first = i_keyfrom(rkey); + return _res; + } +#endif // _i_ismap #endif // !i_no_emplace STC_INLINE _cx_raw _cx_MEMB(_value_toraw)(const _cx_value* val) { @@ -215,19 +225,19 @@ STC_INLINE _cx_iter _cx_MEMB(_advance)(_cx_iter it, size_t n) { STC_INLINE _cx_iter _cx_MEMB(_find)(const _cx_Self* self, _cx_keyraw rkey) { - chash_bucket b; - if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found) - return c_LITERAL(_cx_iter){self->data + b.idx, + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + return c_LITERAL(_cx_iter){b.ref, self->data + self->bucket_count, - self->slot + b.idx}; + self->slot + (b.ref - self->data)}; return _cx_MEMB(_end)(self); } STC_INLINE const _cx_value* _cx_MEMB(_get)(const _cx_Self* self, _cx_keyraw rkey) { - chash_bucket b; - if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found) - return self->data + b.idx; + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + return b.ref; return NULL; } @@ -237,10 +247,10 @@ _cx_MEMB(_get_mut)(_cx_Self* self, _cx_keyraw rkey) STC_INLINE int _cx_MEMB(_erase)(_cx_Self* self, _cx_keyraw rkey) { - chash_bucket b = {0}; - if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found) - _cx_MEMB(_erase_entry)(self, self->data + b.idx); - return b.found; + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + { _cx_MEMB(_erase_entry)(self, b.ref); return 1; } + return 0; } STC_INLINE _cx_iter @@ -313,7 +323,7 @@ STC_DEF void _cx_MEMB(_clear)(_cx_Self* self) { c_memset(self->slot, 0, c_sizeof(chash_slot)*self->bucket_count); } -#ifndef _i_isset +#ifdef _i_ismap STC_DEF _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key _key, i_val _mapped) { _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key))); @@ -340,42 +350,41 @@ STC_DEF void _cx_MEMB(_clear)(_cx_Self* self) { return _res; } #endif // !i_no_emplace -#endif // !_i_isset +#endif // _i_ismap -STC_DEF chash_bucket +STC_DEF _cx_result _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr) { const uint64_t _hash = i_hash(rkeyptr); intptr_t _cap = self->bucket_count; - chash_bucket b = {fastrange_2(_hash, _cap), (uint8_t)(_hash | 0x80)}; + intptr_t _idx = fastrange_2(_hash, _cap); + _cx_result b = {NULL, true, (uint8_t)(_hash | 0x80)}; const chash_slot* s = self->slot; - while (s[b.idx].hashx) { - if (s[b.idx].hashx == b.hashx) { - const _cx_keyraw _raw = i_keyto(_i_keyref(self->data + b.idx)); + while (s[_idx].hashx) { + if (s[_idx].hashx == b.hashx) { + const _cx_keyraw _raw = i_keyto(_i_keyref(self->data + _idx)); if (i_eq((&_raw), rkeyptr)) { - b.found = true; + b.inserted = false; break; } } - if (++b.idx == _cap) b.idx = 0; + if (++_idx == _cap) _idx = 0; } + b.ref = self->data + _idx; return b; } STC_DEF _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) { - _cx_result res = {NULL}; if (self->size >= (intptr_t)((float)self->bucket_count * (i_max_load_factor))) if (!_cx_MEMB(_reserve)(self, (intptr_t)(self->size*3/2 + 2))) - return res; + return c_LITERAL(_cx_result){NULL}; - chash_bucket b = _cx_MEMB(_bucket_)(self, &rkey); - res.ref = &self->data[b.idx]; - if (!b.found) { - self->slot[b.idx].hashx = b.hashx; - res.inserted = true; + _cx_result b = _cx_MEMB(_bucket_)(self, &rkey); + if (b.inserted) { + self->slot[b.ref - self->data].hashx = b.hashx; ++self->size; } - return res; + return b; } #if !defined i_no_clone @@ -417,9 +426,9 @@ _cx_MEMB(_reserve)(_cx_Self* self, const intptr_t _newcap) { const chash_slot* s = self->slot; for (intptr_t i = 0; i < _oldbucks; ++i, ++d) if ((s++)->hashx) { _cx_keyraw r = i_keyto(_i_keyref(d)); - chash_bucket b = _cx_MEMB(_bucket_)(&m, &r); - m.slot[b.idx].hashx = b.hashx; - m.data[b.idx] = *d; // move + _cx_result b = _cx_MEMB(_bucket_)(&m, &r); + m.slot[b.ref - m.data].hashx = b.hashx; + *b.ref = *d; // move } c_swap(_cx_Self, self, &m); } diff --git a/include/stc/csmap.h b/include/stc/csmap.h index f4d33a4d..d2e1d1fc 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -170,19 +170,29 @@ _cx_MEMB(_shrink_to_fit)(_cx_Self *self) { } #endif // !i_no_clone -#ifndef _i_isset +STC_API _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey); + +#ifdef _i_ismap STC_API _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key key, i_val mapped); #if !defined i_no_emplace STC_API _cx_result _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped); - #endif + STC_INLINE _cx_result + _cx_MEMB(_emplace_key)(_cx_Self* self, _cx_keyraw rkey) { + _cx_result res = _cx_MEMB(_insert_entry_)(self, rkey); + if (res.inserted) + res.ref->first = i_keyfrom(rkey); + return res; + } + #endif STC_INLINE const _cx_mapped* _cx_MEMB(_at)(const _cx_Self* self, _cx_keyraw rkey) { _cx_iter it; return &_cx_MEMB(_find_it)(self, rkey, &it)->second; } + STC_INLINE _cx_mapped* _cx_MEMB(_at_mut)(_cx_Self* self, _cx_keyraw rkey) { _cx_iter it; return &_cx_MEMB(_find_it)(self, rkey, &it)->second; } -#endif // !_i_isset +#endif // _i_ismap STC_INLINE _cx_iter _cx_MEMB(_end)(const _cx_Self* self) { @@ -209,8 +219,6 @@ _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { return true; } -static _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey); - STC_INLINE _cx_result _cx_MEMB(_insert)(_cx_Self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key))); @@ -326,7 +334,7 @@ _cx_MEMB(_new_node_)(_cx_Self* self, int level) { return tn; } -#ifndef _i_isset +#ifdef _i_ismap STC_DEF _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key _key, i_val _mapped) { _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key))); @@ -353,7 +361,7 @@ _cx_MEMB(_new_node_)(_cx_Self* self, int level) { return _res; } #endif // !i_no_emplace -#endif // !_i_isset +#endif // !_i_ismap STC_DEF _cx_value* _cx_MEMB(_find_it)(const _cx_Self* self, _cx_keyraw rkey, _cx_iter* out) { @@ -407,7 +415,7 @@ _cx_MEMB(_split_)(_cx_node *d, int32_t tn) { return tn; } -static int32_t +STC_DEF int32_t _cx_MEMB(_insert_entry_i_)(_cx_Self* self, int32_t tn, const _cx_keyraw* rkey, _cx_result* _res) { int32_t up[64], tx = tn; _cx_node* d = self->nodes; @@ -439,7 +447,7 @@ _cx_MEMB(_insert_entry_i_)(_cx_Self* self, int32_t tn, const _cx_keyraw* rkey, _ return up[0]; } -static _cx_result +STC_DEF _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) { _cx_result res = {NULL}; int32_t tn = _cx_MEMB(_insert_entry_i_)(self, self->root, &rkey, &res); @@ -448,7 +456,7 @@ _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) { return res; } -static int32_t +STC_DEF int32_t _cx_MEMB(_erase_r_)(_cx_Self *self, int32_t tn, const _cx_keyraw* rkey, int *erased) { _cx_node *d = self->nodes; if (tn == 0) @@ -533,7 +541,7 @@ _cx_MEMB(_erase_range)(_cx_Self* self, _cx_iter it1, _cx_iter it2) { } #if !defined i_no_clone -static int32_t +STC_DEF int32_t _cx_MEMB(_clone_r_)(_cx_Self* self, _cx_node* src, int32_t sn) { if (sn == 0) return 0; diff --git a/include/stc/forward.h b/include/stc/forward.h index 484a8b63..085205cf 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -120,6 +120,7 @@ typedef struct chash_slot chash_slot; typedef struct { \ SELF##_value *ref; \ bool inserted; \ + uint8_t hashx; \ } SELF##_result; \ \ typedef struct { \ diff --git a/misc/examples/smartpointers/arc_containers.c b/misc/examples/smartpointers/arc_containers.c index 2fb04c56..6209005d 100644 --- a/misc/examples/smartpointers/arc_containers.c +++ b/misc/examples/smartpointers/arc_containers.c @@ -2,7 +2,6 @@ // and demonstrate sharing and cloning of maps. #define i_implement #include -#include #define i_type Map #define i_key_str // strings #define i_val int diff --git a/misc/tests/cspan_test.c b/misc/tests/cspan_test.c index d7ca9b64..ce267b14 100644 --- a/misc/tests/cspan_test.c +++ b/misc/tests/cspan_test.c @@ -1,6 +1,5 @@ #include #include -#include #include "ctest.h" using_cspan3(intspan, int); @@ -48,7 +47,8 @@ CTEST(cspan, slice) { #include CTEST(cspan, slice2) { - c_auto (cstack_int, stack) + cstack_int stack = {0}; + c_defer (cstack_int_drop(&stack)) { c_forrange (i, 10*20*30) cstack_int_push(&stack, i); -- cgit v1.2.3 From d65debf1846fad56e59852e4003e24f99bfd1517 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 2 Aug 2023 16:31:45 +0200 Subject: Renamed (most internal "class" type) crawstr => ccharptr --- docs/algorithm_api.md | 11 ++++++----- include/stc/ccommon.h | 12 ++++++------ include/stc/priv/template.h | 2 +- 3 files changed, 13 insertions(+), 12 deletions(-) (limited to 'docs/algorithm_api.md') diff --git a/docs/algorithm_api.md b/docs/algorithm_api.md index 40ff32d6..127aa120 100644 --- a/docs/algorithm_api.md +++ b/docs/algorithm_api.md @@ -275,12 +275,13 @@ 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` +**ccharptr** - Non-owning `const char*` "class" element type: `#define i_keyclass ccharptr` ```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); +typedef const char* ccharptr; +int ccharptr_cmp(const ccharptr* x, const ccharptr* y); +uint64_t ccharptr_hash(const ccharptr* x); +ccharptr ccharptr_clone(ccharptr sp); +void ccharptr_drop(ccharptr* x); ``` Default implementations ```c diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 77f754fa..2528b94f 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -124,12 +124,12 @@ typedef long long _llong; #define c_litstrlen(literal) (c_sizeof("" literal) - 1) #define c_arraylen(a) (intptr_t)(sizeof(a)/sizeof 0[a]) -// Non-owning c-string -typedef const char* crawstr; -#define crawstr_clone(s) (s) -#define crawstr_drop(p) ((void)p) -#define crawstr_cmp(xp, yp) strcmp(*(xp), *(yp)) -#define crawstr_hash(p) cstrhash(*(p)) +// Non-owning c-string "class" +typedef const char* ccharptr; +#define ccharptr_cmp(xp, yp) strcmp(*(xp), *(yp)) +#define ccharptr_hash(p) cstrhash(*(p)) +#define ccharptr_clone(s) (s) +#define ccharptr_drop(p) ((void)p) #define c_sv(...) c_MACRO_OVERLOAD(c_sv, __VA_ARGS__) #define c_sv_1(lit) c_sv_2(lit, c_litstrlen(lit)) diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index 0f4ac893..49b4d8da 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -111,7 +111,7 @@ #if defined i_key_str #define i_keyclass cstr - #define i_rawclass crawstr + #define i_rawclass ccharptr #ifndef i_tag #define i_tag str #endif -- cgit v1.2.3 From ea878349e94ef00643b2510045f6482385cff1a7 Mon Sep 17 00:00:00 2001 From: tylov Date: Fri, 11 Aug 2023 23:11:01 +0200 Subject: Updated godbolt code. --- README.md | 2 +- docs/algorithm_api.md | 2 +- docs/coroutine_api.md | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'docs/algorithm_api.md') diff --git a/README.md b/README.md index 722d2559..d516f389 100644 --- a/README.md +++ b/README.md @@ -240,7 +240,7 @@ int main(void) ``` This example uses four different container types: -[ [Run this code](https://godbolt.org/z/qor16Gf6j) ] +[ [Run this code](https://godbolt.org/z/j68od14hv) ] ```c #include diff --git a/docs/algorithm_api.md b/docs/algorithm_api.md index 127aa120..63bced22 100644 --- a/docs/algorithm_api.md +++ b/docs/algorithm_api.md @@ -128,7 +128,7 @@ Iterate a container or a crange with chained `&&` filtering. | `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) ] +[ [Run this example](https://godbolt.org/z/exqYEK6qa) ] ```c #include #include diff --git a/docs/coroutine_api.md b/docs/coroutine_api.md index 6bd558f2..f7d81a34 100644 --- a/docs/coroutine_api.md +++ b/docs/coroutine_api.md @@ -78,7 +78,7 @@ yield or await from a (deeply) nested coroutine call using cco_task objects desc The first example is a generator of Pythagorian triples, and stops when diagonal size > max_c. -[ [Run this code](https://godbolt.org/z/3Efn17cP6) ] +[ [Run this code](https://godbolt.org/z/d5zW3f9Gv) ] ```c #include #include @@ -126,7 +126,7 @@ The next variant skips the triples which are upscaled version of smaller ones by the gcd() function. Note that the gcd1_triples struct contains the triples struct so that both functions have separate call frames: -[ [Run this code](https://godbolt.org/z/ndhMq1haj) ] +[ [Run this code](https://godbolt.org/z/a7da9M8P5) ] ```c int gcd(int a, int b) { // greatest common denominator while (b) { -- cgit v1.2.3