diff options
| -rw-r--r-- | README.md | 67 | ||||
| -rw-r--r-- | docs/ccommon_api.md | 208 | ||||
| -rw-r--r-- | include/stc/ccommon.h | 2 | ||||
| -rw-r--r-- | include/stc/extend.h | 2 | ||||
| -rw-r--r-- | misc/examples/forloops.c | 2 | ||||
| -rw-r--r-- | misc/examples/functor.c | 2 |
6 files changed, 148 insertions, 135 deletions
@@ -3,7 +3,7 @@ STC - Smart Template Containers for C ===================================== -### [Version 4.2](#version-history) +### [Version 4.2 RC](#version-history) --- Description @@ -35,13 +35,13 @@ Containers Algorithms ---------- -- [***common*** Generic container algorithms](docs/ccommon_api.md#algorithms) -- [***filter*** - Ranges-like filtering](docs/ccommon_api.md#c_forfilter) -- [***coroutine*** - Tiny, fast and portable coroutine implementation](docs/ccommon_api.md#coroutines) -- [***cregex*** - Regular expressions based on Rob Pike's regexp9](docs/cregex_api.md) -- [***crange*** - Generalized iota integer generator](docs/ccommon_api.md#crange) -- [***crand*** - A novel very fast *PRNG* based on ***sfc64***](docs/crandom_api.md) -- [***coption*** - A ***getopt***-alike command line argument parser](docs/coption_api.md) +- [***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_make, c_find_if, c_erase_if, etc.](docs/ccommon_api.md#generic-algorithms) +- [***Coroutines*** - Simon Tatham's coroutines done right](docs/ccommon_api.md#coroutines) +- [***Regular expressions*** - modernized Rob Pike's Plan-9 regexp](docs/cregex_api.md) +- [***Random numbers*** - a novel very fast *PRNG* based on *SFC64*](docs/crandom_api.md) +- [***Command line argument parser*** - similar to *getopt()*](docs/coption_api.md) --- List of contents @@ -49,7 +49,7 @@ List of contents - [Highlights](#highlights) - [STC is unique!](#stc-is-unique) - [Performance](#performance) -- [STC naming conventions](#stc-naming-conventions) +- [Naming conventions](#naming-conventions) - [Usage](#usage) - [Installation](#installation) - [Specifying template parameters](#specifying-template-parameters) @@ -57,19 +57,19 @@ List of contents - [The *erase* methods](#the-erase-methods) - [User-defined container type name](#user-defined-container-type-name) - [Forward declarations](#forward-declarations) -- [Per-container-instance customization](#per-container-instance-customization) +- [Per container-instance customization](#per-container-instance-customization) - [Memory efficiency](#memory-efficiency) --- ## Highlights -- **No boilerplate code** - Minimal code is needed to setup containers with any element type. Specify only what is needed, e.g. ***cmp***- and/or ***clone***-, ***drop***- functions, and leave the rest as defaults. +- **No boilerplate code** - Specify only the required template parameters, e.g. ***cmp***- and/or ***clone***-, ***drop***- functions, 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. +- **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. -- **Fully memory managed** - All containers will destruct keys/values via destructor (defined as macro parameters before including the container header). Also, smart pointers are supported and can be stored in containers, see ***carc*** and ***cbox***. -- **Uniform, easy-to-learn API** - Uniform and intuitive method/type names and usage across the various containers. -- **No signed/unsigned mixing** - Unsigned sizes and indices mixed with signed in comparisons and calculations is asking for trouble. STC uses only signed numbers in the API for this reason. +- **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*** and ***cbox***. +- **Uniform, easy-to-learn API** - 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. - **No callback functions** - All passed template argument functions/macros are directly called from the implementation, no slow callbacks which requires storage. @@ -87,7 +87,8 @@ that the elements are of basic types. For more complex types, additional templat 2. ***Alternative insert/lookup type***. You may specify an alternative type to use for lookup in containers. E.g., containers with STC string elements (**cstr**) uses `const char*` as lookup type, so construction of a `cstr` (which may allocate memory) for the lookup *is not needed*. Hence, the alt. lookup -key does not need to be destroyed after use, as it is normally a POD type. Finally, the alternative +key does not need to be destroyed after use as it is normally a POD type. Finally, the alternative +key does not need to be destroyed after use as it is normally a POD type. Finally, the alternative lookup type may be passed to an ***emplace***-function. E.g. instead of calling `cvec_str_push(&vec, cstr_from("Hello"))`, you may call `cvec_str_emplace(&vec, "Hello")`, which is functionally identical, but more convenient. @@ -100,7 +101,7 @@ same element access syntax. E.g.: --- ## Performance -STC is a fast and memory efficient library, and code compiles very fast: +STC is a fast and memory efficient library, and code compiles fast:  @@ -114,7 +115,7 @@ Benchmark notes: - **map and unordered map**: *insert*: n/2 random numbers, n/2 sequential numbers. *erase*: n/2 keys in the map, n/2 random keys. --- -## STC naming conventions +## Naming conventions - Container names are prefixed by `c`, e.g. `cvec`, `cstr`. - Public STC macros are prefixed by `c_`, e.g. `c_foreach`, `c_make`. @@ -144,10 +145,10 @@ Benchmark notes: --- ## Usage -The functionality of STC containers is similar to C++ STL standard containers. All containers except for a few, +STC containers have similar functionality to C++ STL standard containers. All containers except for a few, like **cstr** and **cbits** are generic/templated. No type casting is done, so containers are type-safe like -templated types in C++. However, the specification of template parameters are naturally different. Here is -a basic usage example: +templated types in C++. However, the specification of template parameters are naturally different. In STC, +you specify template parameters by `#define` before including the container: ```c #define i_type Floats // Container type name; unless defined name would be cvec_float #define i_val float // Container element type @@ -166,7 +167,7 @@ int main(void) Floats_sort(&nums); - c_foreach (i, Floats, nums) // Alternative and recommended way to iterate nums. + c_foreach (i, Floats, nums) // Alternative and recommended way to iterate. printf(" %g", *i.ref); // i.ref is a pointer to the current element. Floats_drop(&nums); // cleanup memory @@ -181,7 +182,7 @@ You may switch to a different container type, e.g. a sorted set (csset): int main() { - Floats nums = c_make(Floats, {30.f, 10.f, 20.f}); // Initialize nums with a list of floats. + Floats nums = c_make(Floats, {30.f, 10.f, 20.f}); // Initialize with a list of floats. Floats_push(&nums, 50.f); Floats_push(&nums, 40.f); @@ -192,11 +193,11 @@ int main() Floats_drop(&nums); } ``` -For user-defined struct elements, `i_cmp` compare function should be defined, as the default `<` and `==` +For user-defined struct elements, `i_cmp` compare function should be defined as the default `<` and `==` only works for integral types. *Alternatively, `#define i_opt c_no_cmp` to disable sorting and searching*. Similarily, if an element destructor `i_valdrop` is defined, `i_valclone` function is required. *Alternatively `#define i_opt c_no_clone` to disable container cloning.* -Let's make a vector of vectors that can be cloned. All of its element vectors will be destroyed when destroying the Vec2D. +Let's make a vector of vectors, which can be cloned. All of its element vectors will be destroyed when destroying the Vec2D. ```c #include <stdio.h> @@ -206,7 +207,7 @@ Let's make a vector of vectors that can be cloned. All of its element vectors wi #define i_type Vec2D #define i_valclass Vec // Use i_valclass when element type has "members" _clone(), _drop() and _cmp(). -#define i_opt c_no_cmp // However, disable search/sort for Vec2D because Vec_cmp() is not defined. +#define i_opt c_no_cmp // Disable cmp (search/sort) for Vec2D because Vec_cmp() is not defined. #include <stc/cvec.h> int main(void) @@ -542,11 +543,11 @@ typedef struct Dataset { ``` --- -## Per-container-instance customization -Sometimes it is useful to extend a container type to hold extra data, e.g. a comparison -or allocator function pointer or some context that the function pointers can use. Most -libraries solve this by adding an opaque pointer (void*) or some function pointer(s) into -the data structure for the user to manage. This solution has a few disadvantages, e.g. the +## Per container-instance customization +Sometimes it is useful to extend a container type to store extra data, e.g. a comparison +or allocator function pointer or a context which the function pointers can use. Most +libraries solve this by adding an opaque pointer (void*) or function pointer(s) into +the data structure for the user to manage. This solution has a few disadvantages: the pointers are not typesafe, and they take up space when not needed. STC solves this by letting the user create a container wrapper struct where both the container and extra data fields can be stored. The template parameters may then access the extra data using the "container_of" @@ -564,10 +565,10 @@ the by inclusion of `<stc/extend.h>`. #define i_allocator pgs #define i_no_clone -#define i_extend MemoryContext memctx +#define i_extend MemoryContext memctx; #include <stc/extend.h> ``` -Define both `i_type` and `i_con` (the container type) before including the custom header: +To use it, define both `i_type` and `i_con` (the container type) before including the custom header: ```c #define i_type IMap #define i_key int diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index af27bd1d..21eaf884 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -2,16 +2,17 @@ The following macros are recommended to use, and they safe/have no side-effects. -## Loop abstraction macros +--- +## Ranged for-loops -### c_foreach, c_foreach_r, c_forpair +### c_foreach, c_foreach_rv, c_forpair -| Usage | Description | -|:-----------------------------------------|:----------------------------------------| -| `c_foreach (it, ctype, container)` | Iteratate all elements | -| `c_foreach (it, ctype, it1, it2)` | Iterate the range [it1, it2) | -| `c_foreach_r (it, ctype, container)` | Iteratate in reverse (cstack,cvec,cdeq) | -| `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 @@ -40,6 +41,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. @@ -61,24 +81,38 @@ 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); +crange& crange_object(...) // 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); -// insert in existing map -c_forlist (i, cmap_ii_raw, { {4, 5}, {6, 7} }) - cmap_ii_insert(&map, i.ref->first, i.ref->second); +// 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 -// string literals pushed to a stack of cstr: -c_forlist (i, const char*, {"Hello", "crazy", "world"}) - cstack_str_emplace(&stk, *i.ref); +// 2. The first 11 primes: +printf("2"); +c_forfilter (i, crange, crange_object(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 | |:----------------------------------------------------|:---------------------------------------| @@ -122,46 +156,14 @@ int main() { ``` Note that `c_flt_take()` and `c_flt_takewhile()` breaks the loop on false. -## Generators - -### 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_object(...) // 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 - -// 2. The first 11 primes: -printf("2"); -c_forfilter (i, crange, crange_object(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 +--- +## Generic algorithms -### c_make, c_new, c_delete +### c_make, c_drop -- *c_make(C, {...})*: Make any container from an initializer list. Example: +Make any container from an initializer list: ```c -#define i_val_str // owned cstr string value type -//#define i_valclass crawstr // non-owning const char* values with strcmp/cstrhash -//#define i_val const char* // non-owning const char* values with pointer cmp/hash. +#define i_val_str // owned cstr string value type #include <stc/cset.h> #define i_key int @@ -170,26 +172,21 @@ c_forfilter (i, crange, crange_object(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; @@ -208,51 +205,66 @@ 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, c_const_cast +### 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 <stc/cstr.h> + +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); -// Drop multiple containers of same type: -c_drop(cvec_i, &vec1, &vec2, &vec3); - // 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! ``` -### General predefined template parameter functions +### Predefined template parameter functions +**crawstr** - Non-owned `const char*` "class" element type: `#define i_valclass crawstr` ```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 - 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); ``` - -### c_malloc, c_calloc, c_realloc, c_free: customizable allocators -Memory allocator wrappers that uses signed sizes. - -### c_arraylen -Return number of elements in an array. array must not be a pointer! +Default implementations ```c -int array[] = {1, 2, 3, 4}; -intptr_t n = c_arraylen(array); +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 an improved implementation of Simon Tatham's classic C code, which utilizes the *Duff's device* trick. However, Tatham's implementation is not typesafe, -and it always allocates the coroutine's internal state dynamically. Also, -it does not let the coroutine do self-cleanup on early finish, i.e. it -just frees the dynamically allocated memory. +and it always allocates the coroutine's internal state dynamically. But most 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 some struct pointer as parameter, which must contain the member `int cco_state;` @@ -260,8 +272,8 @@ 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 main user-loop -skips the triples which are upscaled version of smaller ones, by checking -the gcd() function, and breaks when diagonal length >= 100: +skips the triples which are upscaled version of smaller ones by checking +the gcd() function, and breaks when the diagonal size >= 100: ```c #include <stc/algo/coroutine.h> @@ -271,14 +283,14 @@ struct triples { 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) { +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; + if (--i->n == 0) cco_return; } } } diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 362b09ce..24ad59f9 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -182,7 +182,7 @@ STC_INLINE char* cstrnstrn(const char *str, const char *needle, for (C##_iter it = start, *_endref = (C##_iter*)(finish).ref \ ; it.ref != (C##_value*)_endref; C##_next(&it)) -#define c_foreach_r(it, C, cnt) \ +#define c_foreach_rv(it, C, cnt) \ for (C##_iter it = {.ref=C##_end(&cnt).end - 1, .end=(cnt).data - 1} \ ; it.ref != it.end; --it.ref) diff --git a/include/stc/extend.h b/include/stc/extend.h index a8cb5f5b..cbfc4a12 100644 --- a/include/stc/extend.h +++ b/include/stc/extend.h @@ -50,7 +50,7 @@ #endif typedef struct { - i_extend; + i_extend i_type get; } c_PASTE(i_type, Ext); diff --git a/misc/examples/forloops.c b/misc/examples/forloops.c index 82126456..1fc00614 100644 --- a/misc/examples/forloops.c +++ b/misc/examples/forloops.c @@ -42,7 +42,7 @@ int main() printf(" %d", *i.ref);
puts("\n\nc_foreach_r: reverse");
- c_foreach_r (i, IVec, vec)
+ c_foreach_rv (i, IVec, vec)
printf(" %d", *i.ref);
puts("\n\nc_foreach in map:");
diff --git a/misc/examples/functor.c b/misc/examples/functor.c index 7cc770d0..7417080b 100644 --- a/misc/examples/functor.c +++ b/misc/examples/functor.c @@ -9,7 +9,7 @@ #define i_type IPQue #define i_val int -#define i_extend bool (*less)(const int*, const int*) +#define i_extend bool (*less)(const int*, const int*); #define i_less(x, y) c_getcon(self)->less(x, y) #define i_con cpque #include <stc/extend.h> |