Merge branch 'master' of https://github.com/tylo-work/C99Containers

1 files changed, 82 insertions, 9 deletions

diff --git a/README.md b/README.md
index 55862655..d5ab26b1 100644
--- a/README.md
+++ b/README.md
@@ -4,14 +4,87 @@ STC - C99 Standard Container Library
 Introduction

 ------------

 

-An elegant, modern, generic, typesafe, and very efficient standard container library for C99.

+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*, 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.

+

+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:

+```

+#include <stc/vector.h>

+declare_CVector(i, int);

+

+int main(void) {

+    CVector_i vec = cvector_init;

+    cvector_i_pushBack(&vec, 42);

+    cvector_i_destroy(&vec);

+}

+```

+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.

+```

+#define STC_IMPLEMENTATION

+#include <stc/cvector.h>

+#include <stc/chash.h>

+

+declare_CVector(i, int);

+declare_CHash(ii, map, int, int);

+declare_CHash(64, set, int64_t);

+...

+```

+Performance

+-----------

+

+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<uint64_t, uint64_t>: 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<uint64_t, uint64_t>: 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<uint64_t, uint64_t>: 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

+-----------------

 

-This is a small headers only library with the most used container components: **cstring**, **cvector**, **carray**, **clist** and **chash**. 

+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

 -----------------

 

-CString demo

+**CString** demo

 ```

 #include <stc/cstring.h>

 

@@ -37,7 +110,7 @@ int main() {
     cstring_destroy(&cs);

 }

 ```

-Simple CVector of 64bit int

+**CVector** of *int64_t*

 ```

 #include <stc/cvector.h>

 declare_CVector(ix, int64_t); // ix is just an example tag name, use anything without underscore.

@@ -55,11 +128,11 @@ int main() {
     cvector_ix_destroy(&bignums);

 }

 ```

-CVector of CString

+**CVector** of *CString*

 ```

 #include <stc/cstring.h>

 #include <stc/cvector.h>

-declare_CVector(cs, CString, cstring_destroy); // supply inline destructor of values

+declare_CVector_string(cs);

 

 int main() {

     CVector_cs names = cvector_init;

@@ -71,7 +144,7 @@ int main() {
     cvector_cs_destroy(&names);

 }

 ```

-CHash map of int -> int

+**CHash map** of *int -> int*

 ```

 #include <stc/chash.h>

 declare_CHash(ii, map, int, int);

@@ -85,7 +158,7 @@ int main() {
     chash_ii_destroy(&nums);

 }

 ```

-CHash set of CString

+**CHash set** of *CString*

 ```

 #include <stc/cstring.h>

 #include <stc/chash.h>

@@ -104,7 +177,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 <stc/cstring.h>

 #include <stc/chash.h>