From 583a0ac357dba6b8c35db7450e8286469516a3b9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 28 Oct 2021 12:04:23 +0200 Subject: updated shootouts, fixed some warnings --- README.md | 722 ++++++++++++++++++++--------------------- benchmarks/build_all.sh | 2 +- benchmarks/shootout2_cmap.cpp | 2 +- benchmarks/shootout4_crand.cpp | 130 +++----- benchmarks/shootout5_crand.cpp | 137 -------- examples/new_sptr.c | 2 +- examples/read.c | 6 +- examples/sharedptr.c | 2 +- examples/sptr_ex.c | 2 +- 9 files changed, 418 insertions(+), 587 deletions(-) delete mode 100644 benchmarks/shootout5_crand.cpp diff --git a/README.md b/README.md index b7da6a25..501a9a53 100644 --- a/README.md +++ b/README.md @@ -1,361 +1,361 @@ -![STC](docs/pics/containers.jpg) - -STC - Smart Template Containers for C -====================================== - -News ----- -**VERSION 2.X RELEASED**: There are two main breaking changes from V1.X. -- Uses a different way to instantiate templated containers, which is incompatible with v1.X. -- c_forauto, c_forvar, c_forscope macros are now renamed to **c_auto**, **c_autovar**, and **c_autoscope**. These are for automatic scope resource management, aka RAII. - -The new template instantiation style has multiple advantages, e.g. implementation does not contain long macro definitions for code generation. Also, specifying template arguments is more user friendly and flexible. - -Introduction ------------- -STC is a modern, templated, user-friendly, fast, fully type-safe, and customizable container library for C99, -with a uniform API across the containers, and is similar to the c++ standard library containers API. -It is a compact, header-only library which includes the all the major "standard" data containers except for the -multimap/set variants. There are examples on how to create multimaps in the examples folder. - -For an introduction to templated containers, please read the blog by Ian Fisher on -[type-safe generic data structures in C](https://iafisher.com/blog/2020/06/type-safe-generics-in-c). -Note that STC does not use long macro expansions anymore, but relies on one or more inclusions of the same file, -which by the compiler is seen as different code because of macro name substitutions. - -- [***carr2, carr3*** - **2d** and **3d** dynamic **array** type](docs/carray_api.md) -- [***cbits*** - **std::bitset** alike type](docs/cbits_api.md) -- [***cdeq*** - **std::deque** alike type](docs/cdeq_api.md) -- [***clist*** - **std::forward_list** alike type](docs/clist_api.md) -- [***cmap*** - **std::unordered_map** alike type](docs/cmap_api.md) -- [***cpque*** - **std::priority_queue** alike type](docs/cpque_api.md) -- [***csptr*** - **std::shared_ptr** alike support](docs/csptr_api.md) -- [***cqueue*** - **std::queue** alike type](docs/cqueue_api.md) -- [***cset*** - **std::unordered_set** alike type](docs/cset_api.md) -- [***csmap*** - **std::map** sorted map alike type](docs/csmap_api.md) -- [***csset*** - **std::set** sorted set alike type](docs/csset_api.md) -- [***cstack*** - **std::stack** alike type](docs/cstack_api.md) -- [***cstr*** - **std::string** alike type](docs/cstr_api.md) -- [***csview*** - **std::string_view** alike type](docs/csview_api.md) -- [***cvec*** - **std::vector** alike type](docs/cvec_api.md) - -Others: -- [***crandom*** - A novel very fast *PRNG* named **stc64**](docs/crandom_api.md) -- [***ccommon*** - Some handy macros and general definitions](docs/ccommon_api.md) - -Highlights ----------- -- **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. -- **Templates** - Use `#define i_`**xxx** to specify container template arguments. There are templates for element-*type*, -*comparison*, -*destruction*, -*cloning*, -*conversion types*, and more. -- **Unparalleled performance** - Some containers are much faster than the c++ STL containers, the rest are about equal in speed. -- **Fully memory managed** - All containers will destruct keys/values via destructor defined as macro parameters before including the container header. Also, shared pointers are supported and can be stored in containers, see ***csptr***. -- **Fully type safe** - Because of templating, it avoids error-prone casting of container types and elements back and forth from the containers. -- **Uniform, easy-to-learn API** - Methods to ***construct***, ***initialize***, ***iterate*** and ***destruct*** have uniform and intuitive usage across the various containers. -- **Small footprint** - Small source code and generated executables. The executable from the example below with six different containers is *22 kb in size* compiled with gcc -Os 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. -- **Compiles with C++ and C99** - C code can be compiled with C++ (container element types must be POD). -- **Container prefix and forward declaration** - Templated containers may have user defined prefix, e.g. myvec_push_back(). They may also be forward declared without including the full API/implementation. See documentation below. - -Performance ------------ -![Benchmark](benchmarks/pics/benchmark.gif) -Benchmark notes: -- The barchart shows average test times over three platforms: Mingw64 10.30, Win-Clang 12, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. -- 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. -- **find()**: not executed for *forward_list*, *deque*, and *vector* because these c++ containers does not have native *find()*. -- **deque**: *insert*: n/3 push_front(), n/3 push_back()+pop_front(), n/3 push_back(). -- **map and unordered map**: *insert*: n/2 random numbers, n/2 sequential numbers. *erase*: n/2 keys in the map, n/2 random keys. - -Usage ------ -The usage of the containers is similar to the c++ standard containers in STL, so it should be easy if you are familiar with them. -All containers are generic/templated, except for **cstr** and **cbits**. No casting is used, so containers are type-safe like -templates in c++. A basic usage example: -```c -#define i_val float -#include - -int main(void) { - cvec_float vec = cvec_float_init(); - cvec_float_push_back(&vec, 10.f); - cvec_float_push_back(&vec, 20.f); - cvec_float_push_back(&vec, 30.f); - - c_foreach (i, cvec_float, vec) - printf(" %g", *i.ref); - - cvec_float_del(&vec); -} -``` -In order to include two **cvec**s with different element types, include cvec.h twice. For structs, specify a compare function (or none), as `<` and `==` operators does not work on them (this enables sorting and searching). -```c -#define i_val struct One -#define i_cmp c_no_compare -#define i_tag one -#include - -#define i_val struct Two -#define i_cmp c_no_compare -#define i_tag two -#include -... -cvec_one v1 = cvec_one_init(); -cvec_two v2 = cvec_two_init(); -``` - -With six different containers: -```c -#include -#include - -struct Point { float x, y; }; - -int Point_compare(const struct Point* a, const struct Point* b) { - int cmp = c_default_compare(&a->x, &b->x); - return cmp ? cmp : c_default_compare(&a->y, &b->y); -} - -#define i_key int -#include // cset_int: unordered set - -#define i_val struct Point -#define i_cmp Point_compare -#define i_tag pnt -#include // cvec_pnt: vector of struct Point - -#define i_val int -#include // cdeq_int: deque of int - -#define i_val int -#include // clist_int: singly linked list - -#define i_val int -#include - -#define i_key int -#define i_val int -#include // csmap_int: sorted map int => int - -int main(void) { - // define six containers with automatic call of init and del (destruction after scope exit) - c_auto (cset_int, set) - c_auto (cvec_pnt, vec) - c_auto (cdeq_int, deq) - c_auto (clist_int, lst) - c_auto (cstack_int, stk) - c_auto (csmap_int, map) - { - // add some elements to each container - c_apply(cset_int, insert, &set, {10, 20, 30}); - c_apply(cvec_pnt, push_back, &vec, { {10, 1}, {20, 2}, {30, 3} }); - c_apply(cdeq_int, push_back, &deq, {10, 20, 30}); - c_apply(clist_int, push_back, &lst, {10, 20, 30}); - c_apply(cstack_int, push, &stk, {10, 20, 30}); - c_apply_pair(csmap_int, insert, &map, { {20, 2}, {10, 1}, {30, 3} }); - - // add one more element to each container - cset_int_insert(&set, 40); - cvec_pnt_push_back(&vec, (struct Point) {40, 4}); - cdeq_int_push_front(&deq, 5); - clist_int_push_front(&lst, 5); - cstack_int_push(&stk, 40); - csmap_int_insert(&map, 40, 4); - - // find an element in each container - cset_int_iter_t i1 = cset_int_find(&set, 20); - cvec_pnt_iter_t i2 = cvec_pnt_find(&vec, (struct Point) {20, 2}); - cdeq_int_iter_t i3 = cdeq_int_find(&deq, 20); - clist_int_iter_t i4 = clist_int_find(&lst, 20); - csmap_int_iter_t i5 = csmap_int_find(&map, 20); - printf("\nFound: %d, (%g, %g), %d, %d, [%d: %d]\n", *i1.ref, i2.ref->x, i2.ref->y, - *i3.ref, *i4.ref, - i5.ref->first, i5.ref->second); - // erase the elements found - cset_int_erase_at(&set, i1); - cvec_pnt_erase_at(&vec, i2); - cdeq_int_erase_at(&deq, i3); - clist_int_erase_at(&lst, i4); - csmap_int_erase_at(&map, i5); - - printf("After erasing elements found:"); - printf("\n set:"); c_foreach (i, cset_int, set) printf(" %d", *i.ref); - printf("\n vec:"); c_foreach (i, cvec_pnt, vec) printf(" (%g, %g)", i.ref->x, i.ref->y); - printf("\n deq:"); c_foreach (i, cdeq_int, deq) printf(" %d", *i.ref); - printf("\n lst:"); c_foreach (i, clist_int, lst) printf(" %d", *i.ref); - printf("\n stk:"); c_foreach (i, cstack_int, stk) printf(" %d", *i.ref); - printf("\n map:"); c_foreach (i, csmap_int, map) printf(" [%d: %d]", i.ref->first, - i.ref->second); - } -} -``` -**Note**: Do ***not*** `return` from inside a `c_auto*`-block. Instead, first `continue`, which will jump out of the block, then call `return` after the block. - -Output -``` -Found: 20, (20, 2), 20, 20, [20: 2] -After erasing elements found: - set: 10 30 40 - vec: (10, 1) (30, 3) (40, 4) - deq: 5 10 30 - lst: 5 10 30 - stk: 10 20 30 40 - map: [10: 1] [30: 3] [40: 4] -``` - -Installation ------------- -Because it is headers-only, headers can simply be included in your program. The methods are static by default (some inlined). -You may add the *include* folder to the **CPATH** environment variable to let GCC, Clang, and TinyC locate the headers. - -If containers are used across several translation units with common instantiated container types, it is recommended to -build as a "library" to minimize the executable size. To enable this mode, specify **-DSTC_HEADER** as a compiler option -in your build environment and place all the instantiations of containers used in a single C-source file, e.g.: -```c -// stc_libs.c -#define STC_IMPLEMENTATION -#include -#include "Point.h" - -#define i_key int -#define i_val int -#define i_tag ii -#include // cmap_ii: int => int - -#define i_key int64_t -#define i_tag ix -#include // cset_ix - -#define i_val int -#include // cvec_int - -#define i_val Point -#define i_tag pnt -#include // clist_pnt -``` - -The *emplace* versus non-emplace container methods --------------------------------------------------- -STC, like c++ STL, has two sets of methods for adding elements to containers. One set begins -with **emplace**, e.g. *cvec_X_emplace_back()*. This is a convenient alternative to -*cvec_X_push_back()* when dealing non-trivial container elements, e.g. strings, shared pointers or -other elements using dynamic memory or shared resources. - -The **emplace** methods ***constructs*** or ***clones*** the given elements before they are added -to the container. In contrast, the *non-emplace* methods ***moves*** the given elements into the -container. For containers of integral or trivial element types, **emplace** and corresponding -*non-emplace* methods are identical. - -| non-emplace: Move | emplace: Clone | Container | -|:--------------------------|:-----------------------------|:--------------------------------------------| -| insert() | emplace() | cmap, csmap, cset, csset, cdeq, clist, cvec | -| insert_or_assign(), put() | emplace_or_assign() | cmap, csmap | -| push() | emplace() | cqueue, cpque, cstack | -| push_back() | emplace_back() | cdeq, clist, cvec | -| push_front() | emplace_front() | cdeq, clist | - -Strings are the most commonly used non-trivial data type. STC containers have proper pre-defined -definitions for cstr container elements, so they are fail-safe to use both with the **emplace** -and non-emplace methods: -```c -#define i_val_str // special macro to enable container of cstr -#include // vector of string (cstr) -... -c_auto (cvec_str, vec) // declare and call cvec_str_init() and defer cvec_str_del(&vec) -c_autovar (cstr s = cstr_lit("a string literal"), cstr_del(&s)) // c_autovar is a more general c_auto. -{ - const char* hello = "Hello"; - cvec_str_push_back(&vec, cstr_from(hello); // construct and add string from const char* - cvec_str_push_back(&vec, cstr_clone(s)); // clone and append a cstr - - cvec_str_emplace_back(&vec, "Yay, literal"); // internally constructs cstr from const char* - cvec_str_emplace_back(&vec, cstr_clone(s)); // <-- COMPILE ERROR: expects const char* - cvec_str_emplace_back(&vec, s.str); // Ok: const char* input type. -} -``` -This is made possible because the type configuration may be given an optional -conversion/"rawvalue"-type as template parameter, along with a back and forth conversion -methods to the container value type. - -Hence, `i_val x = ..., y = i_valfrom(i_valto(&x))` works as a *clone* function, where the output of -`i_valto()` is type `i_valraw`. Function `i_valfrom()` is a *clone* function when `i_valraw/i_valto` is -undefined (i_valraw defaults to `i_val`). Same for `i_key`. - -Rawvalues are also beneficial for **lookup** and **map insertions**. The **emplace** methods constructs -`cstr`-objects from the rawvalues, but only when required: -```c -cmap_str_emplace(&map, "Hello", "world"); -// Two cstr-objects were constructed by emplace - -cmap_str_emplace(&map, "Hello", "again"); -// No cstr was constructed because "Hello" was already in the map. - -cmap_str_emplace_or_assign(&map, "Hello", "there"); -// Only cstr_from("there") constructed. "world" was destructed and replaced. - -cmap_str_insert(&map, cstr_from("Hello"), cstr_from("you")); -// Two cstr's constructed outside call, but both destructed by insert -// because "Hello" existed. No mem-leak but less efficient. - -it = cmap_str_find(&map, "Hello"); -// No cstr constructed for lookup, although keys are cstr-type. -``` -Apart from strings, maps and sets are normally used with trivial value types. However, the -last example on the **cmap** page demonstrates how to specify a map with non-trivial keys. - -Erase methods -------------- -| Name | Description | Container | -|:--------------------------|:-----------------------------|:--------------------------------------------| -| erase() | key based | csmap, csset, cmap, cset, cstr | -| erase_at() | iterator based | csmap, csset, cmap, cset, cvec, cdeq, clist | -| erase_range() | iterator based | csmap, csset, cvec, cdeq, clist | -| erase_n() | index based | cvec, cdeq, cstr | -| remove() | remove all matching values | clist | - -Forward declaring containers ----------------------------- -It is possible to forward declare containers. This is useful when a container is part of a struct, -but still not expose or include the full implementation / API of the container. -```c -// Header file -#include // only include data structures -forward_cstack(cstack_pnt, struct Point); // declare cstack_pnt and cstack_pnt_value_t, cstack_pnt_iter_t; - // the element may be forward declared type as well -typedef struct Dataset { - cstack_pnt vertices; - cstack_pnt colors; -} Dataset; - -... -// Implementation -#define i_fwd // flag that the container was forward declared. -#define i_val struct Point -#define i_tag pnt -#include -``` - -User-defined container type name --------------------------------- -Define `i_cnt` instead of `i_tag`: -```c -#define i_val int -#define i_cnt myvec -#include - -myvec vec = myvec_init(); -myvec_push_back(&vec, 1); -... -``` - -Memory efficiency ------------------ -- **cstr**, **cvec**: Type size: 1 pointer. The size and capacity is stored as part of the heap allocation that also holds the vector elements. -- **clist**: Type size: 1 pointer. Each node allocates a struct which stores the value and next pointer. -- **cdeq**: Type size: 2 pointers. Otherwise like *cvec*. -- **cmap**: Type size: 4 pointers. *cmap* uses one table of keys+value, and one table of precomputed hash-value/used bucket, which occupies only one byte per bucket. The closed hashing has a default max load factor of 85%, and hash table scales by 1.6x when reaching that. -- **csmap**: Type size: 1 pointer. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses only two 32-bit ints for child nodes, and one byte for `level`. -- **carr2**, **carr3**: Type size: 1 pointer plus dimension variables. Arrays are allocated as one contiguous block of heap memory, and one allocation for pointers of indices to the array. -- **csptr**: Type size: 2 pointers, one for the data and one for the reference counter. +![STC](docs/pics/containers.jpg) + +STC - Smart Template Containers for C +====================================== + +News +---- +**VERSION 2.X RELEASED**: There are two main breaking changes from V1.X. +- Uses a different way to instantiate templated containers, which is incompatible with v1.X. +- c_forauto, c_forvar, c_forscope macros are now renamed to **c_auto**, **c_autovar**, and **c_autoscope**. These are for automatic scope resource management, aka RAII. + +The new template instantiation style has multiple advantages, e.g. implementation does not contain long macro definitions for code generation. Also, specifying template arguments is more user friendly and flexible. + +Introduction +------------ +STC is a modern, templated, user-friendly, fast, fully type-safe, and customizable container library for C99, +with a uniform API across the containers, and is similar to the c++ standard library containers API. +It is a compact, header-only library which includes the all the major "standard" data containers except for the +multimap/set variants. There are examples on how to create multimaps in the examples folder. + +For an introduction to templated containers, please read the blog by Ian Fisher on +[type-safe generic data structures in C](https://iafisher.com/blog/2020/06/type-safe-generics-in-c). +Note that STC does not use long macro expansions anymore, but relies on one or more inclusions of the same file, +which by the compiler is seen as different code because of macro name substitutions. + +- [***carr2, carr3*** - **2d** and **3d** dynamic **array** type](docs/carray_api.md) +- [***cbits*** - **std::bitset** alike type](docs/cbits_api.md) +- [***cdeq*** - **std::deque** alike type](docs/cdeq_api.md) +- [***clist*** - **std::forward_list** alike type](docs/clist_api.md) +- [***cmap*** - **std::unordered_map** alike type](docs/cmap_api.md) +- [***cpque*** - **std::priority_queue** alike type](docs/cpque_api.md) +- [***csptr*** - **std::shared_ptr** alike support](docs/csptr_api.md) +- [***cqueue*** - **std::queue** alike type](docs/cqueue_api.md) +- [***cset*** - **std::unordered_set** alike type](docs/cset_api.md) +- [***csmap*** - **std::map** sorted map alike type](docs/csmap_api.md) +- [***csset*** - **std::set** sorted set alike type](docs/csset_api.md) +- [***cstack*** - **std::stack** alike type](docs/cstack_api.md) +- [***cstr*** - **std::string** alike type](docs/cstr_api.md) +- [***csview*** - **std::string_view** alike type](docs/csview_api.md) +- [***cvec*** - **std::vector** alike type](docs/cvec_api.md) + +Others: +- [***crandom*** - A novel very fast *PRNG* named **stc64**](docs/crandom_api.md) +- [***ccommon*** - Some handy macros and general definitions](docs/ccommon_api.md) + +Highlights +---------- +- **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. +- **Templates** - Use `#define i_{arg}` to specify container template arguments. There are templates for element-*type*, -*comparison*, -*destruction*, -*cloning*, -*conversion types*, and more. +- **Unparalleled performance** - Some containers are much faster than the c++ STL containers, the rest are about equal in speed. +- **Fully memory managed** - All containers will destruct keys/values via destructor defined as macro parameters before including the container header. Also, shared pointers are supported and can be stored in containers, see ***csptr***. +- **Fully type safe** - Because of templating, it avoids error-prone casting of container types and elements back and forth from the containers. +- **Uniform, easy-to-learn API** - Methods to ***construct***, ***initialize***, ***iterate*** and ***destruct*** have uniform and intuitive usage across the various containers. +- **Small footprint** - Small source code and generated executables. The executable from the example below with six different containers is *22 kb in size* compiled with gcc -Os 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. +- **Compiles with C++ and C99** - C code can be compiled with C++ (container element types must be POD). +- **Container prefix and forward declaration** - Templated containers may have user defined prefix, e.g. myvec_push_back(). They may also be forward declared without including the full API/implementation. See documentation below. + +Performance +----------- +![Benchmark](benchmarks/pics/benchmark.gif) +Benchmark notes: +- The barchart shows average test times over three platforms: Mingw64 10.30, Win-Clang 12, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. +- 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. +- **find()**: not executed for *forward_list*, *deque*, and *vector* because these c++ containers does not have native *find()*. +- **deque**: *insert*: n/3 push_front(), n/3 push_back()+pop_front(), n/3 push_back(). +- **map and unordered map**: *insert*: n/2 random numbers, n/2 sequential numbers. *erase*: n/2 keys in the map, n/2 random keys. + +Usage +----- +The usage of the containers is similar to the c++ standard containers in STL, so it should be easy if you are familiar with them. +All containers are generic/templated, except for **cstr** and **cbits**. No casting is used, so containers are type-safe like +templates in c++. A basic usage example: +```c +#define i_val float +#include + +int main(void) { + cvec_float vec = cvec_float_init(); + cvec_float_push_back(&vec, 10.f); + cvec_float_push_back(&vec, 20.f); + cvec_float_push_back(&vec, 30.f); + + c_foreach (i, cvec_float, vec) + printf(" %g", *i.ref); + + cvec_float_del(&vec); +} +``` +In order to include two **cvec**s with different element types, include cvec.h twice. For structs, specify a compare function (or none), as `<` and `==` operators does not work on them (this enables sorting and searching). +```c +#define i_val struct One +#define i_cmp c_no_compare +#define i_tag one +#include + +#define i_val struct Two +#define i_cmp c_no_compare +#define i_tag two +#include +... +cvec_one v1 = cvec_one_init(); +cvec_two v2 = cvec_two_init(); +``` + +With six different containers: +```c +#include +#include + +struct Point { float x, y; }; + +int Point_compare(const struct Point* a, const struct Point* b) { + int cmp = c_default_compare(&a->x, &b->x); + return cmp ? cmp : c_default_compare(&a->y, &b->y); +} + +#define i_key int +#include // cset_int: unordered set + +#define i_val struct Point +#define i_cmp Point_compare +#define i_tag pnt +#include // cvec_pnt: vector of struct Point + +#define i_val int +#include // cdeq_int: deque of int + +#define i_val int +#include // clist_int: singly linked list + +#define i_val int +#include + +#define i_key int +#define i_val int +#include // csmap_int: sorted map int => int + +int main(void) { + // define six containers with automatic call of init and del (destruction after scope exit) + c_auto (cset_int, set) + c_auto (cvec_pnt, vec) + c_auto (cdeq_int, deq) + c_auto (clist_int, lst) + c_auto (cstack_int, stk) + c_auto (csmap_int, map) + { + // add some elements to each container + c_apply(cset_int, insert, &set, {10, 20, 30}); + c_apply(cvec_pnt, push_back, &vec, { {10, 1}, {20, 2}, {30, 3} }); + c_apply(cdeq_int, push_back, &deq, {10, 20, 30}); + c_apply(clist_int, push_back, &lst, {10, 20, 30}); + c_apply(cstack_int, push, &stk, {10, 20, 30}); + c_apply_pair(csmap_int, insert, &map, { {20, 2}, {10, 1}, {30, 3} }); + + // add one more element to each container + cset_int_insert(&set, 40); + cvec_pnt_push_back(&vec, (struct Point) {40, 4}); + cdeq_int_push_front(&deq, 5); + clist_int_push_front(&lst, 5); + cstack_int_push(&stk, 40); + csmap_int_insert(&map, 40, 4); + + // find an element in each container + cset_int_iter_t i1 = cset_int_find(&set, 20); + cvec_pnt_iter_t i2 = cvec_pnt_find(&vec, (struct Point) {20, 2}); + cdeq_int_iter_t i3 = cdeq_int_find(&deq, 20); + clist_int_iter_t i4 = clist_int_find(&lst, 20); + csmap_int_iter_t i5 = csmap_int_find(&map, 20); + printf("\nFound: %d, (%g, %g), %d, %d, [%d: %d]\n", *i1.ref, i2.ref->x, i2.ref->y, + *i3.ref, *i4.ref, + i5.ref->first, i5.ref->second); + // erase the elements found + cset_int_erase_at(&set, i1); + cvec_pnt_erase_at(&vec, i2); + cdeq_int_erase_at(&deq, i3); + clist_int_erase_at(&lst, i4); + csmap_int_erase_at(&map, i5); + + printf("After erasing elements found:"); + printf("\n set:"); c_foreach (i, cset_int, set) printf(" %d", *i.ref); + printf("\n vec:"); c_foreach (i, cvec_pnt, vec) printf(" (%g, %g)", i.ref->x, i.ref->y); + printf("\n deq:"); c_foreach (i, cdeq_int, deq) printf(" %d", *i.ref); + printf("\n lst:"); c_foreach (i, clist_int, lst) printf(" %d", *i.ref); + printf("\n stk:"); c_foreach (i, cstack_int, stk) printf(" %d", *i.ref); + printf("\n map:"); c_foreach (i, csmap_int, map) printf(" [%d: %d]", i.ref->first, + i.ref->second); + } +} +``` +**Note**: Do ***not*** `return` from inside a `c_auto*`-block. Instead, first `continue`, which will jump out of the block, then call `return` after the block. + +Output +``` +Found: 20, (20, 2), 20, 20, [20: 2] +After erasing elements found: + set: 10 30 40 + vec: (10, 1) (30, 3) (40, 4) + deq: 5 10 30 + lst: 5 10 30 + stk: 10 20 30 40 + map: [10: 1] [30: 3] [40: 4] +``` + +Installation +------------ +Because it is headers-only, headers can simply be included in your program. The methods are static by default (some inlined). +You may add the *include* folder to the **CPATH** environment variable to let GCC, Clang, and TinyC locate the headers. + +If containers are used across several translation units with common instantiated container types, it is recommended to +build as a "library" to minimize the executable size. To enable this mode, specify **-DSTC_HEADER** as a compiler option +in your build environment and place all the instantiations of containers used in a single C-source file, e.g.: +```c +// stc_libs.c +#define STC_IMPLEMENTATION +#include +#include "Point.h" + +#define i_key int +#define i_val int +#define i_tag ii +#include // cmap_ii: int => int + +#define i_key int64_t +#define i_tag ix +#include // cset_ix + +#define i_val int +#include // cvec_int + +#define i_val Point +#define i_tag pnt +#include // clist_pnt +``` + +The *emplace* versus non-emplace container methods +-------------------------------------------------- +STC, like c++ STL, has two sets of methods for adding elements to containers. One set begins +with **emplace**, e.g. *cvec_X_emplace_back()*. This is a convenient alternative to +*cvec_X_push_back()* when dealing non-trivial container elements, e.g. strings, shared pointers or +other elements using dynamic memory or shared resources. + +The **emplace** methods ***constructs*** or ***clones*** the given elements before they are added +to the container. In contrast, the *non-emplace* methods ***moves*** the given elements into the +container. For containers of integral or trivial element types, **emplace** and corresponding +*non-emplace* methods are identical. + +| non-emplace: Move | emplace: Clone | Container | +|:--------------------------|:-----------------------------|:--------------------------------------------| +| insert() | emplace() | cmap, csmap, cset, csset, cdeq, clist, cvec | +| insert_or_assign(), put() | emplace_or_assign() | cmap, csmap | +| push() | emplace() | cqueue, cpque, cstack | +| push_back() | emplace_back() | cdeq, clist, cvec | +| push_front() | emplace_front() | cdeq, clist | + +Strings are the most commonly used non-trivial data type. STC containers have proper pre-defined +definitions for cstr container elements, so they are fail-safe to use both with the **emplace** +and non-emplace methods: +```c +#define i_val_str // special macro to enable container of cstr +#include // vector of string (cstr) +... +c_auto (cvec_str, vec) // declare and call cvec_str_init() and defer cvec_str_del(&vec) +c_autovar (cstr s = cstr_lit("a string literal"), cstr_del(&s)) // c_autovar is a more general c_auto. +{ + const char* hello = "Hello"; + cvec_str_push_back(&vec, cstr_from(hello); // construct and add string from const char* + cvec_str_push_back(&vec, cstr_clone(s)); // clone and append a cstr + + cvec_str_emplace_back(&vec, "Yay, literal"); // internally constructs cstr from const char* + cvec_str_emplace_back(&vec, cstr_clone(s)); // <-- COMPILE ERROR: expects const char* + cvec_str_emplace_back(&vec, s.str); // Ok: const char* input type. +} +``` +This is made possible because the type configuration may be given an optional +conversion/"rawvalue"-type as template parameter, along with a back and forth conversion +methods to the container value type. + +Hence, `i_val x = ..., y = i_valfrom(i_valto(&x))` works as a *clone* function, where the output of +`i_valto()` is type `i_valraw`. Function `i_valfrom()` is a *clone* function when `i_valraw/i_valto` is +undefined (i_valraw defaults to `i_val`). Same for `i_key`. + +Rawvalues are also beneficial for **lookup** and **map insertions**. The **emplace** methods constructs +`cstr`-objects from the rawvalues, but only when required: +```c +cmap_str_emplace(&map, "Hello", "world"); +// Two cstr-objects were constructed by emplace + +cmap_str_emplace(&map, "Hello", "again"); +// No cstr was constructed because "Hello" was already in the map. + +cmap_str_emplace_or_assign(&map, "Hello", "there"); +// Only cstr_from("there") constructed. "world" was destructed and replaced. + +cmap_str_insert(&map, cstr_from("Hello"), cstr_from("you")); +// Two cstr's constructed outside call, but both destructed by insert +// because "Hello" existed. No mem-leak but less efficient. + +it = cmap_str_find(&map, "Hello"); +// No cstr constructed for lookup, although keys are cstr-type. +``` +Apart from strings, maps and sets are normally used with trivial value types. However, the +last example on the **cmap** page demonstrates how to specify a map with non-trivial keys. + +Erase methods +------------- +| Name | Description | Container | +|:--------------------------|:-----------------------------|:--------------------------------------------| +| erase() | key based | csmap, csset, cmap, cset, cstr | +| erase_at() | iterator based | csmap, csset, cmap, cset, cvec, cdeq, clist | +| erase_range() | iterator based | csmap, csset, cvec, cdeq, clist | +| erase_n() | index based | cvec, cdeq, cstr | +| remove() | remove all matching values | clist | + +Forward declaring containers +---------------------------- +It is possible to forward declare containers. This is useful when a container is part of a struct, +but still not expose or include the full implementation / API of the container. +```c +// Header file +#include // only include data structures +forward_cstack(cstack_pnt, struct Point); // declare cstack_pnt and cstack_pnt_value_t, cstack_pnt_iter_t; + // the element may be forward declared type as well +typedef struct Dataset { + cstack_pnt vertices; + cstack_pnt colors; +} Dataset; + +... +// Implementation +#define i_fwd // flag that the container was forward declared. +#define i_val struct Point +#define i_tag pnt +#include +``` + +User-defined container type name +-------------------------------- +Define `i_cnt` instead of `i_tag`: +```c +#define i_val int +#define i_cnt myvec +#include + +myvec vec = myvec_init(); +myvec_push_back(&vec, 1); +... +``` + +Memory efficiency +----------------- +- **cstr**, **cvec**: Type size: 1 pointer. The size and capacity is stored as part of the heap allocation that also holds the vector elements. +- **clist**: Type size: 1 pointer. Each node allocates a struct which stores the value and next pointer. +- **cdeq**: Type size: 2 pointers. Otherwise like *cvec*. +- **cmap**: Type size: 4 pointers. *cmap* uses one table of keys+value, and one table of precomputed hash-value/used bucket, which occupies only one byte per bucket. The closed hashing has a default max load factor of 85%, and hash table scales by 1.6x when reaching that. +- **csmap**: Type size: 1 pointer. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses only two 32-bit ints for child nodes, and one byte for `level`. +- **carr2**, **carr3**: Type size: 1 pointer plus dimension variables. Arrays are allocated as one contiguous block of heap memory, and one allocation for pointers of indices to the array. +- **csptr**: Type size: 2 pointers, one for the data and one for the reference counter. diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh index 6217d5e1..36dc8f33 100644 --- a/benchmarks/build_all.sh +++ b/benchmarks/build_all.sh @@ -1,4 +1,4 @@ -#!/bin/sh +#!/bin/bash cc='g++ -std=c++17' #cc='clang' #cc='clang -c -DSTC_HEADER' diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp index 1704079d..58a31009 100644 --- a/benchmarks/shootout2_cmap.cpp +++ b/benchmarks/shootout2_cmap.cpp @@ -58,7 +58,7 @@ stc64_t rng; #define UMAP_SETUP(X, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor) #define UMAP_PUT(X, key, val) (map[key] = val) -#define UMAP_EMPLACE(X, key, val) (*map.emplace(key, val).first).second +#define UMAP_EMPLACE(X, key, val) map.emplace(key, val).first->second #define UMAP_FIND(X, key) (map.find(key) != map.end()) #define UMAP_ERASE(X, key) map.erase(key) #define UMAP_FOR(X, i) for (auto i: map) diff --git a/benchmarks/shootout4_crand.cpp b/benchmarks/shootout4_crand.cpp index 5d5fd3d7..455fcb80 100644 --- a/benchmarks/shootout4_crand.cpp +++ b/benchmarks/shootout4_crand.cpp @@ -1,6 +1,7 @@ #include #include #include +#include #include static inline uint64_t rotl64(const uint64_t x, const int k) @@ -20,20 +21,19 @@ static void init_state(uint64_t *rng, uint64_t seed) { for (int i=0; i<4; ++i) rng[i] = splitmix64(); } -/* jsf64 */ +/* romu_trio */ -static inline uint64_t jsf64(uint64_t *s) { - uint64_t e = s[0] - rotl64(s[1], 7); - s[0] = s[1] ^ rotl64(s[2], 13); - s[1] = s[2] + rotl64(s[3], 37); - s[2] = s[3] + e; - s[3] = e + s[0]; - return s[3]; +uint64_t romu_trio(uint64_t s[3]) { + uint64_t xp = s[0], yp = s[1], zp = s[2]; + s[0] = 15241094284759029579u * zp; + s[1] = yp - xp; s[1] = rotl64(s[1], 12); + s[2] = zp - yp; s[2] = rotl64(s[2], 44); + return xp; } /* sfc64 */ -static inline uint64_t sfc64(uint64_t *s) { +static inline uint64_t sfc64(uint64_t s[4]) { uint64_t result = s[0] + s[1] + s[3]++; s[0] = s[1] ^ (s[1] >> 11); s[1] = s[2] + (s[2] << 3); @@ -41,20 +41,24 @@ static inline uint64_t sfc64(uint64_t *s) { return result; } -/* sfc64 with Weyl increment */ -static uint64_t weyl = 1234566789123ull; -static inline uint64_t sfc64w(uint64_t *s) { - uint64_t result = s[0] + s[1] + (s[3] += weyl|1); - s[0] = s[1] ^ (s[1] >> 11); - s[1] = s[2] + (s[2] << 3); - s[2] = rotl64(s[2], 24) + result; - return result; +/* xoshiro128+ */ + +uint64_t xoroshiro128plus(uint64_t s[2]) { + const uint64_t s0 = s[0]; + uint64_t s1 = s[1]; + const uint64_t result = s0 + s1; + + s1 ^= s0; + s[0] = rotl64(s0, 24) ^ s1 ^ (s1 << 16); // a, b + s[1] = rotl64(s1, 37); // c + + return result; } /* xoshiro256** */ -static inline uint64_t xoshiro256starstar(uint64_t* s) { +static inline uint64_t xoshiro256starstar(uint64_t s[4]) { const uint64_t result = rotl64(s[1] * 5, 7) * 9; const uint64_t t = s[1] << 17; s[2] ^= s[0]; @@ -89,11 +93,6 @@ static inline uint64_t wyrand64(uint64_t *seed){ } -inline unsigned long long lehmer64(uint64_t* s) { - *(__uint128_t *)s *= 0xda942042e4dd58b5ull; - return *(__uint128_t *)s >> 64; -} - using namespace std; int main(void) @@ -102,101 +101,72 @@ int main(void) uint64_t* recipient = new uint64_t[N]; static stc64_t rng; init_state(rng.state, 12345123); + std::mt19937 mt(12345123); cout << "WARMUP" << endl; for (size_t i = 0; i < N; i++) recipient[i] = wyrand64(rng.state); clock_t beg, end; - for (size_t ti = 0; ti < 4; ti++) { + for (size_t ti = 0; ti < 2; ti++) { init_state(rng.state, 12345123); - cout << endl << "ROUND " << ti+1 << endl; - beg = clock(); - for (size_t i = 0; i < N; i++) - recipient[i] = wyrand64(rng.state); - end = clock(); - cout << "wyrand64:\t" - << (float(end - beg) / CLOCKS_PER_SEC) - << " s: " << recipient[312] << endl; - beg = clock(); - for (size_t i = 0; i < N; i++) - recipient[i] = sfc64w(rng.state); - end = clock(); - cout << "sfc64w:\t\t" - << (float(end - beg) / CLOCKS_PER_SEC) - << " s: " << recipient[312] << endl; + cout << endl << "ROUND " << ti+1 << " ---------" << endl; beg = clock(); for (size_t i = 0; i < N; i++) - recipient[i] = stc64_rand(&rng); + recipient[i] = romu_trio(rng.state); end = clock(); - cout << "stc64:\t\t" + cout << "romu_trio:\t" << (float(end - beg) / CLOCKS_PER_SEC) - << " s: " << recipient[312] << endl; + << "s: " << recipient[312] << endl; beg = clock(); for (size_t i = 0; i < N; i++) - recipient[i] = xoshiro256starstar(rng.state); + recipient[i] = wyrand64(rng.state); end = clock(); - cout << "xoshiro256**:\t" + cout << "wyrand64:\t" << (float(end - beg) / CLOCKS_PER_SEC) - << " s: " << recipient[312] << endl; + << "s: " << recipient[312] << endl; beg = clock(); for (size_t i = 0; i < N; i++) - recipient[i] = lehmer64(rng.state); - end = clock(); - cout << "lehmer64:\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << recipient[312] << endl; - - cout << "Next we do random number computations only, doing no work." - << endl; - init_state(rng.state, 12345123); - uint64_t s = 0; - beg = clock(); - for (size_t i = 0; i < N; i++) - s += wyrand64(rng.state); + recipient[i] = sfc64(rng.state); end = clock(); - cout << "wyrand64:\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << s << endl; + cout << "sfc64:\t\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << "s: " << recipient[312] << endl; - s = 0; beg = clock(); for (size_t i = 0; i < N; i++) - s += sfc64w(rng.state); + recipient[i] = stc64_rand(&rng); end = clock(); - cout << "sfc64w:\t\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << s << endl; + cout << "stc64:\t\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << "s: " << recipient[312] << endl; - s = 0; beg = clock(); for (size_t i = 0; i < N; i++) - s += stc64_rand(&rng); + recipient[i] = xoroshiro128plus(rng.state); end = clock(); - cout << "stc64:\t\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << s << endl; + cout << "xoroshiro128+:\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << "s: " << recipient[312] << endl; - s = 0; beg = clock(); for (size_t i = 0; i < N; i++) - s += xoshiro256starstar(rng.state); + recipient[i] = xoshiro256starstar(rng.state); end = clock(); cout << "xoshiro256**:\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << s << endl; + << (float(end - beg) / CLOCKS_PER_SEC) + << "s: " << recipient[312] << endl; - s = 0; beg = clock(); for (size_t i = 0; i < N; i++) - s += lehmer64(rng.state); + recipient[i] = mt(); end = clock(); - cout << "lehmer64:\t" - << ((float) end - beg) / CLOCKS_PER_SEC - << " s: " << s << endl; + cout << "std::mt19937:\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << "s: " << recipient[312] << endl; } delete[] recipient; return 0; diff --git a/benchmarks/shootout5_crand.cpp b/benchmarks/shootout5_crand.cpp deleted file mode 100644 index 0a034fc4..00000000 --- a/benchmarks/shootout5_crand.cpp +++ /dev/null @@ -1,137 +0,0 @@ -#include -#include -#include -#include "stc/crandom.h" -//#include "pcg_random.hpp" - -static struct stc32_state { stc64_t rng; uint64_t spare; unsigned n; } stc32_global = - {{0x7a5fed, 0x8e3f52, 0x9bc713, 0x6a09e667a7541669}, 0, 0}; - -STC_INLINE void stc32_srandom(uint64_t seed) { stc32_global.rng = stc64_init(seed); } -STC_INLINE uint32_t stc32_random(void) { - return (uint32_t) (++stc32_global.n & 1 ? (stc32_global.spare = stc64_rand(&stc32_global.rng)) - : (stc32_global.spare >> 32)); -} - -static unsigned long myrand_next = 1; - -/* RAND_MAX assumed to be 32767 */ -int myrand(void) { - myrand_next = myrand_next * 214013 + 2531011; - return (myrand_next >> 16) & 0x7fff; -} - -void mysrand(unsigned seed) { - myrand_next = seed; -} - - -enum {N = 1000000000}; - -void test1(void) -{ - clock_t diff, before; - uint64_t sum; - - std::random_device device; - std::mt19937 rng(device()); - std::uniform_int_distribution idist(1, 10); - std::uniform_real_distribution fdist(1, 10); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += rng(); - } - diff = clock() - before; - printf("std::random:\t\t%.02f, %zu, sz:%zu\n", (float) diff / CLOCKS_PER_SEC, sum, sizeof rng); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += idist(rng); - } - diff = clock() - before; - printf("std::uniform:\t\t%.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, sum); - - c_forrange (30) printf("%02d ", idist(rng)); - puts(""); - c_forrange (8) printf("%f ", fdist(rng)); - puts("\n"); -} -/* -void test2() -{ - clock_t diff, before; - uint64_t sum; - - // Seed with a real random value, if available - pcg_extras::seed_seq_from seed_source; - - // Make a random number engine - pcg64 rng(seed_source); - - // Choose a random mean between 1 and 10 - std::uniform_int_distribution idist(1, 10); - std::uniform_real_distribution fdist(1, 10); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += rng(); - } - diff = clock() - before; - printf("pcg64::random:\t\t%.02f, %zu, sz:%zu\n", (float) diff / CLOCKS_PER_SEC, sum, sizeof rng); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += idist(rng); - } - diff = clock() - before; - printf("pcg64::uniform:\t\t%.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, sum); - - c_forrange (30) printf("%02d ", idist(rng)); - puts(""); - c_forrange (8) printf("%f ", fdist(rng)); - puts("\n"); -} -*/ - -void test3(void) -{ - clock_t diff, before; - uint64_t sum; - - stc64_t rng = stc64_init(time(NULL)); - stc64_uniform_t idist = stc64_uniform_init(1, 10); - stc64_uniformf_t fdist = stc64_uniformf_init(1, 10); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += stc64_rand(&rng); - } - diff = clock() - before; - printf("stc64_random:\t\t%.02f, %zu sz:%zu\n", (float) diff / CLOCKS_PER_SEC, sum, sizeof rng); - - before = clock(); - sum = 0; - c_forrange (N) { - sum += stc64_uniform(&rng, &idist); - } - diff = clock() - before; - printf("stc64_uniform:\t\t%.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, sum); - - c_forrange (30) printf("%02zd ", stc64_uniform(&rng, &idist)); - puts(""); - c_forrange (8) printf("%f ", stc64_uniformf(&rng, &fdist)); - puts("\n"); -} - -int main() -{ - test1(); - //test2(); - test3(); -} \ No newline at end of file diff --git a/examples/new_sptr.c b/examples/new_sptr.c index 59512803..77e663b7 100644 --- a/examples/new_sptr.c +++ b/examples/new_sptr.c @@ -30,7 +30,7 @@ int main(void) { c_autovar (csptr_person p = csptr_person_make(Person_init("John", "Smiths")), csptr_person_del(&p)) c_autovar (csptr_person q = csptr_person_clone(p), csptr_person_del(&q)) // share the pointer { - printf("%s %s. uses: %u\n", q.get->name.str, q.get->last.str, *q.use_count); + printf("%s %s. uses: %lu\n", q.get->name.str, q.get->last.str, *q.use_count); } c_auto (cstack_iptr, stk) { diff --git a/examples/read.c b/examples/read.c index c415c6e5..728bf579 100644 --- a/examples/read.c +++ b/examples/read.c @@ -1,8 +1,6 @@ -#include -#include - #define i_val_str #include +#include cvec_str read_file(const char* name) { @@ -23,4 +21,4 @@ int main() if (errno) printf("error: read_file(" __FILE__ "). errno: %d\n", errno); -} \ No newline at end of file +} diff --git a/examples/sharedptr.c b/examples/sharedptr.c index 94de3d38..dbb3746f 100644 --- a/examples/sharedptr.c +++ b/examples/sharedptr.c @@ -45,7 +45,7 @@ int main() c_foreach (i, csset_intp, set) printf(" %d", *i.ref->get); c_autovar (csptr_int p = csptr_int_clone(vec.data[0]), csptr_int_del(&p)) { - printf("\n%d is now owned by %u objects\n", *p.get, *p.use_count); + printf("\n%d is now owned by %lu objects\n", *p.get, *p.use_count); } puts("Done"); diff --git a/examples/sptr_ex.c b/examples/sptr_ex.c index 85d6c34d..17ac27e1 100644 --- a/examples/sptr_ex.c +++ b/examples/sptr_ex.c @@ -47,7 +47,7 @@ void example3() }); c_foreach (s, cvec_song, v2) - printf("%s - %s: refs %u\n", s.ref->get->artist.str, s.ref->get->title.str, + printf("%s - %s: refs %lu\n", s.ref->get->artist.str, s.ref->get->title.str, *s.ref->use_count); } } -- cgit v1.2.3