Refinements.

4 files changed, 40 insertions, 30 deletions

diff --git a/README.md b/README.md
index bb7c78a2..cf6671ba 100644
--- a/README.md
+++ b/README.md
@@ -34,10 +34,10 @@ Performance
 -----------

 ![Benchmark](benchmarks/pics/benchmark.png)

 

-STC containers performs either about equal or better than the c++ std counterparts. **cmap** *insert* is almost 4x times faster than 

-*std::unordered_map* in this benchmark, and 2x times faster than *erase*! Iteration and destruction is an order of magnitude faster.

-**csmap** has noticable faster lookup than *std::map*'s typical red-black tree implementation. It uses an AA-tree (Arne Andersson, 1993),

-which tends to create a flatter structure (more balanced) than red-black trees.

+STC containers performs either about equal or better than the c++ std counterparts. **cmap** *insert* is almost 4x times faster

+than *std::unordered_map* in this benchmark, and 2x times faster *erase*! Iteration and destruction is an order of magnitude

+faster. **csmap** has noticable faster lookup than *std::map*'s typical red-black tree implementation. It uses an AA-tree

+(Arne Andersson, 1993), which tends to create a flatter structure (more balanced) than red-black trees.

 

 Notes:

 - The barchart shows average times from results from three platforms: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz.

@@ -55,7 +55,7 @@ Highlights
 - **Fully memory managed** - All containers will destruct keys, values via destructor passed as macro parameters to the ***using_***-declaration. Also smart-pointers are supported and can be stored in containers, see ***csptr***.

 - **Fully type safe** - Avoids error-prone casting of container types and elements back and forth from the containers.

 - **Uniform API** - Methods to ***construct***, ***initialize***, ***iterate*** and ***destruct*** have a uniform and intuitive usage across the various containers.

-- **Small footprint** - Small source code and generated executables. The executable from the example below using six different containers is *26 kb in size* compiled with TinyC.

+- **Small footprint** - Small source code and generated executables. The executable from the example below using six different containers is *27 kb in size* compiled with TinyC.

 - **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 next how-to.

 

 Usage

@@ -170,9 +170,12 @@ After erasing elements found:
 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 project folder to CPATH environment variable, to let GCC, Clang, and TinyC locate the headers.

+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 project folder to CPATH environment variable, to let GCC, Clang, and TinyC locate the headers.

 

-If containers are used accross 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 compiler option in your build environment, and place all the instantiations of containers used in a single C source file, e.g.:

+If containers are used accross 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 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

@@ -196,18 +199,28 @@ The containers are memory efficent, i.e. they occupy as little memory as practic
 - **clist**: Type size: one pointer. Each node allocates block storing value and next pointer.

 - **cdeq**:  Type size: two 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.5x when reaching that.

-- **csmap**: Type size: 1 pointer only. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses two 32-bit words by default for left/right childs, and one byte for `level`. *csmap* can be configured to allow more than 2^32 elements, ie. 2^64, but it will double the overhead per node.

+- **csmap**: Type size: 1 pointer. *csmap* manages its own array of tree-nodes for allocation efficiency. Each node uses two 32-bit words by default for left/right childs, and one byte for `level`. *csmap* can be configured to allow more than 2^32 elements, ie. 2^64, but it will double the overhead per node.

 - **carray**: carray1, carray2 and carray3. Type size: One pointer plus one, two, or three size_t variables to store dimensions. Arrays are allocated as one contiguous block of heap memory.

 - **csptr**: a shared-pointer uses two pointers, one for the data and one for the reference counter.

 

 FAQ

 ---

-**Q**: *How can **cmap** be so fast?*

+**Q**: *How come **cmap** is so fast?*

 

-**A**: It uses open addressing which holds all buckets in one block of memory. It has a separate array for precomputed hashes/used buckets - one byte per bucket. Further if avoids modulus operations and erases elements without leaving tombstones. Modern architechtures favors simple code and cached memory access, so linear probing is actually as fast or faster than the more advanced Robin Hood and Hopscotch hashing schemes, which also requires tombstones. **cmap** does not rely on wasteful power-of-two array sizes, it actually expands only by 1.5x when required.

+**A**: It uses open addressing which holds all buckets in one block of memory. It has a separate array for precomputed

+hashes/used buckets - one byte per bucket. Further if avoids modulus operations and erases elements without leaving

+tombstones. Modern architechtures favors simple code and cached memory access, so linear probing is actually as fast

+or faster than the more advanced Robin Hood and Hopscotch hashing schemes, which also requires tombstones. **cmap**

+does not rely on wasteful power-of-two array sizes, it actually expands only by 1.5x when required.

 

-**Q**: Why can **cvec_str_emplace_back()** take `const char *` argument when its value type `cstr` cannot be directly assigned from a `const char *`?

+**Q**: Why can **cvec_str_emplace_back()** take `const char *` argument when its value type `cstr` cannot be directly

+assigned from a `const char *`?

 

-**A**: STC containers simulates automatic type convertion found in c++. Most containers can take an optional "rawvalue" type as template parameter in the **using_**-declaration, along with back and forth convertion methods to the container value type. By default, rawvalue is equal to value. Various **emplace()**, **cmap_put()** and lookup methods accepts the rawvalue type, which is  convenient e.g. for strings.

+**A**: STC containers simulates automatic type convertion found in c++. Most containers can take an optional

+"rawvalue" type as template parameter in the **using_**-declaration, along with back and forth convertion methods

+to the container value type. By default, rawvalue is equal to value. Various **emplace()**, **cmap_put()** and

+lookup methods accepts the rawvalue type, which is  convenient e.g. for strings.

 

-Raw-value is also useful for map insertions, because values are only conditionally inserted - the **emplace()** method construct a cstr object from a rawvalue only when needed. **using_cvec_str()** declares the `cvec_str` container type with predefined `cstr` value and `const char *` rawvalue, along with convertion methods.

+The use of rawvalues are also useful for map insertions, because values are conditionally inserted - the **emplace()**

+method constructs a cstr object from a rawvalue when needed only. The shorthand **using_cvec_str()** declares `cvec_str`

+container type with `cstr` value and `const char *` rawvalue, along with convertion methods.

diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp
index 6f016d1d..f5c7aada 100644
--- a/benchmarks/cmap_benchmark2.cpp
+++ b/benchmarks/cmap_benchmark2.cpp
@@ -36,7 +36,7 @@ DEFMAP(map_s, <std::string, std::string>);
 

 using_cmap(i, int, int, c_default_equals, c_default_hash32);

 using_cmap(x, uint64_t, uint64_t, c_default_equals, c_default_hash64);

-using_cmap_strkey(s, cstr, cstr_del, cstr_clone);

+using_cmap_str();

 

 PICOBENCH_SUITE("Map1");

 

@@ -228,24 +228,24 @@ static void ins_and_access_cmap_s(picobench::state& s)
 {

     cstr str = cstr_with_size(s.arg(), 'x');

     size_t result = 0;

-    cmap_s map = cmap_s_init();

-    cmap_s_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0);

+    cmap_str map = cmap_str_init();

+    cmap_str_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0);

     stc64_srandom(seed);

 

     picobench::scope scope(s);

     c_forrange (s.iterations()) {

         randomize(str.str, cstr_size(str));

-        cmap_s_put(&map, str.str, cstr_clone(str));

+        cmap_str_put(&map, str.str, str.str);

         randomize(str.str, cstr_size(str));

-        cmap_s_iter_t it = cmap_s_find(&map, str.str);

+        cmap_str_iter_t it = cmap_str_find(&map, str.str);

         if (it.ref) {

             ++result;

-            cmap_s_erase_at(&map, it);

+            cmap_str_erase_at(&map, it);

         }

     }

-    s.set_result(result + cmap_s_size(map));

+    s.set_result(result + cmap_str_size(map));

     cstr_del(&str);

-    cmap_s_del(&map);

+    cmap_str_del(&map);

 }

 

 #define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000})

diff --git a/stc/cmap.h b/stc/cmap.h
index cb28ae2d..45df0883 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -309,13 +309,10 @@ typedef struct {size_t idx; uint32_t hx;} chash_bucket_t;
     typedef C##_##X C##_##X##_t

 

 STC_API    uint64_t c_default_hash(const void *data, size_t len);

-STC_INLINE uint64_t c_default_hash32(const void* data, size_t len) {

-    return *(const uint32_t *)data * 2654435769u;

-}

-STC_INLINE uint64_t c_default_hash64(const void* data, size_t len) {

-    return *(const uint64_t *)data * 11400714819323198485ull;

-}

-#define cstr_hash_raw(p, ignored) c_default_hash(*(p), strlen(*(p)))

+STC_INLINE uint64_t c_default_hash32(const void* data, size_t len)

+           {return *(const uint32_t *)data * 2654435769u;}

+STC_INLINE uint64_t c_default_hash64(const void* data, size_t len)

+           {return *(const uint64_t *)data * 11400714819323198485ull;}

 

 /* -------------------------- IMPLEMENTATION ------------------------- */

 

@@ -454,7 +451,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80};
     }

 

 STC_DEF uint64_t c_default_hash(const void *key, size_t len) {

-    const uint64_t m = 11400714819323198485ull; // 0xc6a4a7935bd1e995;

+    const uint64_t m = 0xc6a4a7935bd1e995;

     uint64_t k, h = m + len;

     const unsigned char *p = (const uint8_t *) key,

                         *end = p + (len & ~7ull);

diff --git a/stc/cstr.h b/stc/cstr.h
index ad89c6bd..02176664 100644
--- a/stc/cstr.h
+++ b/stc/cstr.h
@@ -221,9 +221,9 @@ cstr_iends_with(cstr_t s, const char* needle) {
 #define  cstr_to_raw(x)          ((x)->str)

 #define  cstr_compare_raw(x, y)  strcmp(*(x), *(y))

 #define  cstr_equals_raw(x, y)   (strcmp(*(x), *(y)) == 0)

+#define  cstr_hash_raw(p, none)  c_default_hash(*(p), strlen(*(p)))

 #define  cstr_compare_ref(x, y)  strcmp((x)->str, (y)->str)

 #define  cstr_equals_ref(x, y)   (strcmp((x)->str, (y)->str) == 0)

-#define  cstr_hash_ref(x, none)  c_default_hash((x)->str, cstr_size(x)))

 

 /* -------------------------- IMPLEMENTATION ------------------------- */