From 630cd3059f43e88af1592827675d667250428c04 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 20:54:59 +0200 Subject: Update README.md --- README.md | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/README.md b/README.md index 689a62bd..26fbaeac 100644 --- a/README.md +++ b/README.md @@ -8,6 +8,29 @@ An elegant, modern, generic, typesafe, and very efficient standard container lib This is a small headers only library with the most used container components: **cstring**, **cvector**, **carray**, **clist** and **chash**. +All containers, except CString is generic (similar to templates in C++). Typical usage is: +``` +#include +declare_CVector(my, int); +int main(void) { + CVector_my vec = cvector_init; + cvector_pushBack(&vec, 123); + cvector_destroy(&vec); +} +``` +Installation +------------ + +This is a header only library, so files can simply be included in your program. The functions will be inlined by default. If the library is extensively used accross many files with same instantiated type, it can alternatively be compiled as a library in order to minimize executable size. In that case, specify -DSTC_HEADER on the compiler line, and create one file that contains all implementations of containers, e.g. +``` +#define STC_IMPLEMENT +#include +#include +declare_CVector(my, int); +declare_CMap(my, int, int); +... +``` + Usage by examples ----------------- -- cgit v1.2.3 From 477e7b8b64f19c91f19ce8233f4cf7a97a6d0126 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 20:55:51 +0200 Subject: Update README.md --- README.md | 2 ++ 1 file changed, 2 insertions(+) diff --git a/README.md b/README.md index 26fbaeac..b7061160 100644 --- a/README.md +++ b/README.md @@ -12,6 +12,7 @@ All containers, except CString is generic (similar to templates in C++). Typical ``` #include declare_CVector(my, int); + int main(void) { CVector_my vec = cvector_init; cvector_pushBack(&vec, 123); @@ -26,6 +27,7 @@ This is a header only library, so files can simply be included in your program. #define STC_IMPLEMENT #include #include + declare_CVector(my, int); declare_CMap(my, int, int); ... -- cgit v1.2.3 From e43ae7e8a82eb325fd11daf9211ccbdafcd73867 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 21:11:38 +0200 Subject: Update README.md --- README.md | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) diff --git a/README.md b/README.md index b7061160..a7c26ef7 100644 --- a/README.md +++ b/README.md @@ -4,32 +4,31 @@ STC - C99 Standard Container Library Introduction ------------ -An elegant, modern, generic, typesafe, and very efficient standard container library for C99. +An elegant, modern, generic, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash**, **carray**, and **clist**. -This is a small headers only library with the most used container components: **cstring**, **cvector**, **carray**, **clist** and **chash**. - -All containers, except CString is generic (similar to templates in C++). Typical usage is: +All containers, except CString are generic (similar to templates in C++). The typical usage is: ``` #include -declare_CVector(my, int); +declare_CVector(i, int); int main(void) { - CVector_my vec = cvector_init; - cvector_pushBack(&vec, 123); - cvector_destroy(&vec); + CVector_i vec = cvector_init; + cvector_i_pushBack(&vec, 42); + cvector_i_destroy(&vec); } ``` Installation ------------ -This is a header only library, so files can simply be included in your program. The functions will be inlined by default. If the library is extensively used accross many files with same instantiated type, it can alternatively be compiled as a library in order to minimize executable size. In that case, specify -DSTC_HEADER on the compiler line, and create one file that contains all implementations of containers, e.g. +Because it is headers only, files can simply be included in your program. The functions will be inlined by default. If the library is extensively used accross many files with same instantiated type, alternatively compile as a library to minimize executable size; specify -DSTC_HEADER on the compiler line, and put all the instantiations of the containers you use in one C file, e.g. ``` -#define STC_IMPLEMENT -#include -#include +#define STC_IMPLEMENTATION +#include +#include -declare_CVector(my, int); -declare_CMap(my, int, int); +declare_CVector(i, int); +declare_CHash(ii, map, int, int); +declare_CHash(64, set, int64_t); ... ``` -- cgit v1.2.3 From 25889303a83c8430660d82400f14223287627487 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 21:27:10 +0200 Subject: Update README.md --- README.md | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/README.md b/README.md index a7c26ef7..70e7b8e5 100644 --- a/README.md +++ b/README.md @@ -4,9 +4,11 @@ STC - C99 Standard Container Library Introduction ------------ -An elegant, modern, generic, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash**, **carray**, and **clist**. +An elegant, modern, generic, customizable, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash**, **carray**, and **clist**. -All containers, except CString are generic (similar to templates in C++). The typical usage is: +The usage is quite similar to c++ standard containers, so it should be easy for those who are familiar with that. + +All containers mentioned above, except for CString are generic (similar to templates in C++). The typical usage is: ``` #include declare_CVector(i, int); @@ -20,7 +22,7 @@ int main(void) { Installation ------------ -Because it is headers only, files can simply be included in your program. The functions will be inlined by default. If the library is extensively used accross many files with same instantiated type, alternatively compile as a library to minimize executable size; specify -DSTC_HEADER on the compiler line, and put all the instantiations of the containers you use in one C file, e.g. +Because it is headers only, files can simply be included in your program. The functions will be inlined by default. If containers are extensively used accross many files with the same instantiated type, it is recommended to build as a library to minimize executable size. In this case, specify -DSTC_HEADER to the compiler, and put all the instantiations of the containers used in one C file, e.g. ``` #define STC_IMPLEMENTATION #include @@ -83,7 +85,7 @@ CVector of CString ``` #include #include -declare_CVector(cs, CString, cstring_destroy); // supply inline destructor of values +declare_CVector_string(cs); int main() { CVector_cs names = cvector_init; -- cgit v1.2.3 From a82bec44a0c0ac564c19090c4117742ecf942775 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 21:30:35 +0200 Subject: Update README.md --- README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/README.md b/README.md index 70e7b8e5..ffa9a569 100644 --- a/README.md +++ b/README.md @@ -4,7 +4,7 @@ STC - C99 Standard Container Library Introduction ------------ -An elegant, modern, generic, customizable, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash**, **carray**, and **clist**. +An elegant, modern, generic, customizable, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash** (map and set), **carray** (multi-dim. dynamic array), and **clist** (circular singly linked list, suited to be used as queue). The usage is quite similar to c++ standard containers, so it should be easy for those who are familiar with that. -- cgit v1.2.3 From f4ea94c315716b51227132927643d22182b6e94a Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 21:44:26 +0200 Subject: Update README.md --- README.md | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/README.md b/README.md index ffa9a569..9e2315d7 100644 --- a/README.md +++ b/README.md @@ -4,11 +4,16 @@ STC - C99 Standard Container Library Introduction ------------ -An elegant, modern, generic, customizable, typesafe, and very efficient standard container library for C99. This is a small headers only library with the most used container components: **cstring**, **cvector**, **chash** (map and set), **carray** (multi-dim. dynamic array), and **clist** (circular singly linked list, suited to be used as queue). +An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, and very efficient standard container library for C99. This is a small headers only library with the most used container components: +- **CString** - Compact and powerful string class +- **CVector** - Dynamic generic vector class. +- **CHash** - Unorderd map and set. +- **CArray** - Multi-dimensional dynamic array +- **CList** - A circular singly linked list, suited to be used as queue (supports pushBack, pushFront, and popFront). The usage is quite similar to c++ standard containers, so it should be easy for those who are familiar with that. -All containers mentioned above, except for CString are generic (similar to templates in C++). The typical usage is: +All containers mentioned above, except for CString are generic (similar to templates in C++). A simple example: ``` #include declare_CVector(i, int); -- cgit v1.2.3 From ff299f2de10fc84f089c0e59bd1702ed4b75c87a Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 21:49:29 +0200 Subject: Update README.md --- README.md | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/README.md b/README.md index 9e2315d7..5221d4d8 100644 --- a/README.md +++ b/README.md @@ -42,7 +42,7 @@ declare_CHash(64, set, int64_t); Usage by examples ----------------- -CString demo +**CString** *demo* ``` #include @@ -68,7 +68,7 @@ int main() { cstring_destroy(&cs); } ``` -Simple CVector of 64bit int +**CVector** of *int64_t* ``` #include declare_CVector(ix, int64_t); // ix is just an example tag name, use anything without underscore. @@ -86,7 +86,7 @@ int main() { cvector_ix_destroy(&bignums); } ``` -CVector of CString +**CVector** of *CString* ``` #include #include @@ -102,7 +102,7 @@ int main() { cvector_cs_destroy(&names); } ``` -CHash map of int -> int +**CHash map** of *int -> int* ``` #include declare_CHash(ii, map, int, int); @@ -116,7 +116,7 @@ int main() { chash_ii_destroy(&nums); } ``` -CHash set of CString +**CHash set** of *CString* ``` #include #include @@ -135,7 +135,7 @@ int main() { chash_s_destroy(&words); } ``` -CHash map of CString -> CString. Temporary CString values are created by "make", and moved to the container +**CHash map** of *CString -> CString*. Temporary CString values are created by "make", and moved to the container ``` #include #include -- cgit v1.2.3 From 09b79d1dc6ec7188066232376eec0c561ec9bd91 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 20 Jun 2020 23:05:37 +0200 Subject: Update README.md --- README.md | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) diff --git a/README.md b/README.md index 5221d4d8..b3d10d43 100644 --- a/README.md +++ b/README.md @@ -4,12 +4,14 @@ STC - C99 Standard Container Library Introduction ------------ -An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, and very efficient standard container library for C99. This is a small headers only library with the most used container components: -- **CString** - Compact and powerful string class -- **CVector** - Dynamic generic vector class. -- **CHash** - Unorderd map and set. -- **CArray** - Multi-dimensional dynamic array -- **CList** - A circular singly linked list, suited to be used as queue (supports pushBack, pushFront, and popFront). +An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, and very efficient standard container library for C99. This is a small headers only library with the most used container components, and a few algorithms: +- **cstring.h** - Compact and powerful string class +- **cvector.h** - Dynamic generic vector class. +- **chash.h** - Unordered **map** and **set**. +- **carray.h** - Multi-dimensional dynamic array +- **clist.h** - A circular singly linked list, suited to be used as queue (supports pushBack, pushFront, and popFront). +- **coption.h** - Header-only implementation of getopt_long-like function, to parse command line arguments. +- **crandom.h** - Header-only collection of efficent modern random number generators **xoroshiro128ss**, **sfc32/64** and **Mersenne Twister**. It also implements the crypto-strong **siphash** algorithm. The usage is quite similar to c++ standard containers, so it should be easy for those who are familiar with that. @@ -38,11 +40,15 @@ declare_CHash(ii, map, int, int); declare_CHash(64, set, int64_t); ... ``` +Performance +----------- + +These are all very efficient containers as they have templated "intrusive" elements. The Usage by examples ----------------- -**CString** *demo* +**CString** demo ``` #include -- cgit v1.2.3 From 36fb54245b244c384f171207c079ec6dd0e62f16 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sun, 21 Jun 2020 00:09:16 +0200 Subject: Update README.md --- README.md | 44 ++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 40 insertions(+), 4 deletions(-) diff --git a/README.md b/README.md index b3d10d43..fdc6b8d2 100644 --- a/README.md +++ b/README.md @@ -11,9 +11,9 @@ An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, - **carray.h** - Multi-dimensional dynamic array - **clist.h** - A circular singly linked list, suited to be used as queue (supports pushBack, pushFront, and popFront). - **coption.h** - Header-only implementation of getopt_long-like function, to parse command line arguments. -- **crandom.h** - Header-only collection of efficent modern random number generators **xoroshiro128ss**, **sfc32/64** and **Mersenne Twister**. It also implements the crypto-strong **siphash** algorithm. +- **crandom.h** - Header-only collection of efficent modern random number generators **xoroshiro128ss**, **sfc32/64** and Mersenne Twister **mt19937**. It also implements the crypto-strong **siphash** algorithm. -The usage is quite similar to c++ standard containers, so it should be easy for those who are familiar with that. +The usage of containers is similar to c++ standard containers, so it should be easy for those who are familiar with that. All containers mentioned above, except for CString are generic (similar to templates in C++). A simple example: ``` @@ -29,7 +29,7 @@ int main(void) { Installation ------------ -Because it is headers only, files can simply be included in your program. The functions will be inlined by default. If containers are extensively used accross many files with the same instantiated type, it is recommended to build as a library to minimize executable size. In this case, specify -DSTC_HEADER to the compiler, and put all the instantiations of the containers used in one C file, e.g. +Because it is headers only, files can simply be included in your program. The functions will be inlined by default. If containers are extensively used accross many files with the same instantiated type, it is recommended to build as a library to minimize executable size. In this case, specify **-DSTC_HEADER** to the compiler, and put all the instantiations of the containers used in one C file, e.g. ``` #define STC_IMPLEMENTATION #include @@ -43,7 +43,43 @@ declare_CHash(64, set, int64_t); Performance ----------- -These are all very efficient containers as they have templated "intrusive" elements. The +The library is very efficent. The containers have templated "intrusive"/in-place elements. Possibly the most speed critical is the **CHash map / CHash set** implementation. This is among the fastest of C and C++ map implementations: benchmark.c compiled with g++ v9.2.0 -O3 on windows (results are similar with Visual Studio or g++ on linux): + +**CMAP=this**, KMAP=khash, UMAP=std::unordered_map, BMAP=ska::bytell_hash_map, FMAP=ska::flat_hash_map, RMAP=robin_hood::unordered_map +``` +Random keys are in range [0, 2^20): +map: 7000000 repeats of Insert random key + (try to) remove a different random key: +CMAP(ii): sz: 523938, bucks: 1013337, time: 0.39, sum: 24500003500000, erase: 3237392 (fastest) +KMAP(ii): sz: 523938, bucks: 2097152, time: 0.46, sum: 24500003500000, erase: 3237392 +UMAP(ii): sz: 523938, bucks: 1056323, time: 2.21, sum: 24500003500000, erase: 3237392 +BMAP(ii): sz: 523938, bucks: 1048576, time: 0.46, sum: 24500003500000, erase: 3237392 +FMAP(ii): sz: 523938, bucks: 1048576, time: 0.43, sum: 24500003500000, erase: 3237392 +RMAP(ii): sz: 523938, bucks: 838860, time: 0.82, sum: 24500003500000, erase: 3237392 + +map: Insert 10000000 sequensial keys, then remove them in same order: +CMAP(ii): sz: 0, bucks: 17001171, time: 0.75, erase 10000000 (second) +KMAP(ii): sz: 0, bucks: 16777216, time: 0.48, erase 10000000 +UMAP(ii): sz: 0, bucks: 17961079, time: 1.04, erase 10000000 +BMAP(ii): sz: 0, bucks: 16777216, time: 1.04, erase 10000000 +FMAP(ii): sz: 0, bucks: 16777216, time: 0.94, erase 10000000 +RMAP(ii): sz: 0, bucks: 13421772, time: 0.84, erase 10000000 + +map: Insert 10000000 random keys, then remove them in same order: +CMAP(ii): sz: 0, bucks: 1621347, time: 0.41, erase 1048490 (fastest) +KMAP(ii): sz: 0, bucks: 2097152, time: 0.77, erase 1048490 +UMAP(ii): sz: 0, bucks: 2144977, time: 1.67, erase 1048490 +BMAP(ii): sz: 0, bucks: 2097152, time: 0.52, erase 1048490 +FMAP(ii): sz: 0, bucks: 2097152, time: 0.44, erase 1048490 +RMAP(ii): sz: 0, bucks: 1677721, time: 0.65, erase 1048490 +``` +Memory efficiency +----------------- + +Near optimal memory usage for all the containers. The circular list is intrusive so only one allocation is needed for each node, however a custom allocator and various techniques could improve the linked lists memory usage. +- **CString**, **CVector**: one pointer for representation. Heap allocation holds size and capacity. +- **CList**: one pointer for representation. Each node allocates block storing value and next pointer. +- **CHash set**: Representation size of 4 pointers. One array of Key per bucket, one array of one byte per buckets. +- **CHash map**: Representation size of 4 pointers. One array of (Key, Value) per bucket, one array of one byte per buckets. Usage by examples ----------------- -- cgit v1.2.3 From 218dacfe2f4a025fff090ee3d405baa58a64120e Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sun, 21 Jun 2020 00:11:06 +0200 Subject: Update README.md --- README.md | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/README.md b/README.md index fdc6b8d2..4d69a12c 100644 --- a/README.md +++ b/README.md @@ -5,12 +5,12 @@ Introduction ------------ An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, and very efficient standard container library for C99. This is a small headers only library with the most used container components, and a few algorithms: -- **cstring.h** - Compact and powerful string class -- **cvector.h** - Dynamic generic vector class. +- **cstring.h** - Compact and powerful **string** class +- **cvector.h** - Dynamic generic **vector** class. - **chash.h** - Unordered **map** and **set**. -- **carray.h** - Multi-dimensional dynamic array -- **clist.h** - A circular singly linked list, suited to be used as queue (supports pushBack, pushFront, and popFront). -- **coption.h** - Header-only implementation of getopt_long-like function, to parse command line arguments. +- **carray.h** - Multi-dimensional dynamic **array** +- **clist.h** - A circular singly linked **list**, suited to be used as **queue** (supports pushBack, pushFront, and popFront). +- **coption.h** - Header-only implementation of **getopt_long**-like function, to parse command line arguments. - **crandom.h** - Header-only collection of efficent modern random number generators **xoroshiro128ss**, **sfc32/64** and Mersenne Twister **mt19937**. It also implements the crypto-strong **siphash** algorithm. The usage of containers is similar to c++ standard containers, so it should be easy for those who are familiar with that. -- cgit v1.2.3 From 666390920c458a363964864c5c455b8ed2139503 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sun, 21 Jun 2020 00:14:50 +0200 Subject: Update README.md --- README.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/README.md b/README.md index 4d69a12c..65308788 100644 --- a/README.md +++ b/README.md @@ -5,11 +5,11 @@ Introduction ------------ An elegant, modern, generic, customizable, typesafe, consistent, user-friendly, and very efficient standard container library for C99. This is a small headers only library with the most used container components, and a few algorithms: -- **cstring.h** - Compact and powerful **string** class +- **cstring.h** - Compact and powerful **string** class. - **cvector.h** - Dynamic generic **vector** class. - **chash.h** - Unordered **map** and **set**. - **carray.h** - Multi-dimensional dynamic **array** -- **clist.h** - A circular singly linked **list**, suited to be used as **queue** (supports pushBack, pushFront, and popFront). +- **clist.h** - A circular singly linked **list**, suited to be used as **queue**. Supports *pushBack, pushFront, and popFront*, as well as *splice* functions and (merge) *sorting*. - **coption.h** - Header-only implementation of **getopt_long**-like function, to parse command line arguments. - **crandom.h** - Header-only collection of efficent modern random number generators **xoroshiro128ss**, **sfc32/64** and Mersenne Twister **mt19937**. It also implements the crypto-strong **siphash** algorithm. -- cgit v1.2.3