Replaced default hash for cmap.

8 files changed, 71 insertions, 78 deletions

diff --git a/README.md b/README.md
index a38a402e..70c60e43 100644
--- a/README.md
+++ b/README.md
@@ -204,10 +204,12 @@ The containers are memory efficent, i.e. they occupy as little memory as practic
 

 FAQ

 ---

-- **Q**: Why is **cmap** so fast?

-- **A**: Many reasons. It uses open addressing which holds all buckets in one block of memory. It uses a separate array for precomputed hashes/used buckets - only one byte per bucket. It 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, and they require tombstones. **cmap** does not rely on wasteful power-of-two array sizes, it actually expands only by 1.5x when required.

+**Q**: *How did you make **cmap** so fast?*

 

-- **Q**: How come **cvec_str_emplace_back()** can take a `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++. All 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**: 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**: *How come **cvec_str_emplace_back()** can take a `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++. All 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.

 

 It 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 `cvec_str` container type with predefined `cstr` value and `const char *` rawvalue, along with convertion methods.

diff --git a/benchmarks/cmap_benchmark.cpp b/benchmarks/cmap_benchmark.cpp
index 56c92264..3fb939fa 100644
--- a/benchmarks/cmap_benchmark.cpp
+++ b/benchmarks/cmap_benchmark.cpp
@@ -16,11 +16,7 @@ uint64_t seed = 1, mask1 = 0xffffffff;
 

 static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; }

 

-static inline uint32_t hash64(const void* data, size_t len) {

-    uint64_t x = *(const uint64_t *)data * 11400714819323198485ull;

-    return x ^ (x >> 32);

-}

-using_cmap(x, size_t, size_t, c_default_equals, hash64);

+using_cmap(x, size_t, size_t, c_default_equals, c_default_hash64);

 

 #ifdef __cplusplus

 Sample test_std_unordered_map() {

diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp
index 4d6db980..6f016d1d 100644
--- a/benchmarks/cmap_benchmark2.cpp
+++ b/benchmarks/cmap_benchmark2.cpp
@@ -15,13 +15,6 @@
 enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80};

 uint64_t seed = time(NULL);

 

-static inline uint32_t hash32(const void* data, size_t len) {

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

-}

-static inline uint32_t hash64(const void* data, size_t len) {

-    uint64_t x = *(const uint64_t *)data * 11400714819323198485ull;

-    return x ^ (x >> 24);

-}

 template <class K, class V> using umap = std::unordered_map<K, V>;

 template <class K, class V> using bmap = ska::bytell_hash_map<K, V>;

 template <class K, class V> using fmap = ska::flat_hash_map<K, V>;

@@ -41,8 +34,8 @@ DEFMAP(map_i, <int, int>);
 DEFMAP(map_x, <uint64_t, uint64_t>);

 DEFMAP(map_s, <std::string, std::string>);

 

-using_cmap(i, int, int, c_default_equals, hash32);

-using_cmap(x, uint64_t, uint64_t, c_default_equals, hash64);

+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);

 

 PICOBENCH_SUITE("Map1");

diff --git a/benchmarks/pics/benchmark.png b/benchmarks/pics/benchmark.png
index b07e31c9..047fcbb3 100644
--- a/benchmarks/pics/benchmark.png
+++ b/benchmarks/pics/benchmark.png
diff --git a/examples/advanced.c b/examples/advanced.c
index f99d8671..a854b2bb 100644
--- a/examples/advanced.c
+++ b/examples/advanced.c
@@ -20,8 +20,8 @@ typedef struct VikingRaw {
     const char* country;
 } VikingRaw;
 
-uint32_t vikingraw_hash(const VikingRaw* raw, size_t ignore) {
-    uint32_t hash = c_string_hash(raw->name) ^ (c_string_hash(raw->country) << 3);
+uint64_t vikingraw_hash(const VikingRaw* raw, size_t ignore) {
+    uint64_t hash = c_default_hash(raw->name, strlen(raw->name)) ^ (c_default_hash(raw->country, strlen(raw->country)) >> 15);
     return hash;
 }
 static inline int vikingraw_equals(const VikingRaw* rx, const VikingRaw* ry) {
diff --git a/stc/cmap.h b/stc/cmap.h
index 5f907a29..cb28ae2d 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -136,6 +136,9 @@ typedef struct {size_t idx; uint32_t hx;} chash_bucket_t;
 #define MAP_ONLY_cmap(...) __VA_ARGS__

 #define KEY_REF_cset(vp)   (vp)

 #define KEY_REF_cmap(vp)   (&(vp)->first)

+#ifndef CMAP_SIZE_T

+#define CMAP_SIZE_T uint32_t

+#endif

 

 #define _using_CHASH(X, C, Key, Mapped, keyEqualsRaw, keyHashRaw, mappedDel, mappedFromRaw, \

                         keyDel, keyFromRaw, keyToRaw, RawKey, mappedToRaw, RawMapped) \

@@ -143,6 +146,7 @@ typedef struct {size_t idx; uint32_t hx;} chash_bucket_t;
     typedef Mapped C##_##X##_mapped_t; \

     typedef RawKey C##_##X##_rawkey_t; \

     typedef RawMapped C##_##X##_rawmapped_t; \

+    typedef CMAP_SIZE_T C##_##X##_size_t; \

 \

     typedef SET_ONLY_##C( C##_##X##_key_t ) \

             MAP_ONLY_##C( struct {C##_##X##_key_t first; \

@@ -162,7 +166,7 @@ typedef struct {size_t idx; uint32_t hx;} chash_bucket_t;
     typedef struct { \

         C##_##X##_value_t* table; \

         uint8_t* _hashx; \

-        uint32_t size, bucket_count; \

+        C##_##X##_size_t size, bucket_count; \

         float min_load_factor; \

         float max_load_factor; \

     } C##_##X; \

@@ -300,13 +304,19 @@ typedef struct {size_t idx; uint32_t hx;} chash_bucket_t;
         C##_##X##_next(&pos); return pos; \

     } \

 \

-    STC_API uint32_t c_default_hash(const void *data, size_t len); \

-    STC_API uint32_t c_default_hash32(const void* data, size_t len); \

-\

     _implement_CHASH(X, C, Key, Mapped, keyEqualsRaw, keyHashRaw, mappedDel, keyDel, \

                         keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

     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)))

+

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

 

 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

@@ -443,17 +453,25 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80};
             C##_##X##_reserve(self, k*1.2); \

     }

 

-STC_DEF uint32_t c_default_hash(const void *data, size_t len) {

-    const volatile uint16_t *key = (const uint16_t *) data;

-    uint64_t x = *key++ * 11400714819323198485llu;

-    while (len -= 2) x = (*key++ + x) * 11400714819323198485llu;

-    return (uint32_t) x;

-}

-STC_DEF uint32_t c_default_hash32(const void* data, size_t len) {

-    const volatile uint32_t *key = (const uint32_t *) data;

-    uint64_t x = *key++ * 2654435769ull;

-    while (len -= 4) x = (*key++ + x) * 2654435769ull;

-    return (uint32_t) x;

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

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

+    uint64_t k, h = m + len;

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

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

+    for (; p != end; p += 8) {

+        memcpy(&k, p, 8);

+        h ^= k*m;

+    }

+    switch (len & 7) {

+        case 7: h ^= (uint64_t) p[6] << 48;

+        case 6: h ^= (uint64_t) p[5] << 40;

+        case 5: h ^= (uint64_t) p[4] << 32;

+        case 4: h ^= (uint64_t) p[3] << 24;

+        case 3: h ^= (uint64_t) p[2] << 16;

+        case 2: h ^= (uint64_t) p[1] << 8;

+        case 1: h ^= (uint64_t) p[0]; h *= m;

+    }

+    return h ^ (h >> 15);

 }

 

 #else

diff --git a/stc/csmap.h b/stc/csmap.h
index c72efede..41d2ef07 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -127,9 +127,15 @@ int main(void) {
 #define CSMAP_SIZE_T uint32_t

 #endif

 

-#define _using_AATREE_types(X, C, Key, Mapped) \

+struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };

+#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes)

+

+#define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                         keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

     typedef Key C##_##X##_key_t; \

     typedef Mapped C##_##X##_mapped_t; \

+    typedef RawKey C##_##X##_rawkey_t; \

+    typedef RawMapped C##_##X##_rawmapped_t; \

     typedef CSMAP_SIZE_T C##_##X##_size_t; \

 \

     typedef SET_ONLY_##C( C##_##X##_key_t ) \

@@ -137,6 +143,16 @@ int main(void) {
                                   C##_##X##_mapped_t second;} ) \

     C##_##X##_value_t; \

 \

+    typedef SET_ONLY_##C( C##_##X##_rawkey_t ) \

+            MAP_ONLY_##C( struct {C##_##X##_rawkey_t first; \

+                                  C##_##X##_rawmapped_t second;} ) \

+    C##_##X##_rawvalue_t; \

+\

+    typedef struct { \

+        C##_##X##_value_t *first; \

+        bool second; /* inserted */ \

+    } C##_##X##_result_t; \

+\

     typedef struct C##_##X##_node { \

         C##_##X##_size_t link[2]; \

         int8_t level; \

@@ -144,34 +160,15 @@ int main(void) {
     } C##_##X##_node_t; \

 \

     typedef struct { \

-        C##_##X##_value_t *ref; \

-        C##_##X##_node_t *_d; \

-        int _top; \

-        C##_##X##_size_t _tn, _st[48]; \

-    } C##_##X##_iter_t

-

-struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };

-#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes)

-

-#define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                         keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

-    _using_AATREE_types(X, C, Key, Mapped); \

-\

-    typedef struct { \

         C##_##X##_node_t* nodes; \

     } C##_##X; \

 \

-    typedef RawKey C##_##X##_rawkey_t; \

-    typedef RawMapped C##_##X##_rawmapped_t; \

-    typedef SET_ONLY_##C( C##_##X##_rawkey_t ) \

-            MAP_ONLY_##C( struct {C##_##X##_rawkey_t first; \

-                                  C##_##X##_rawmapped_t second;} ) \

-    C##_##X##_rawvalue_t; \

-\

     typedef struct { \

-        C##_##X##_value_t *first; \

-        bool second; \

-    } C##_##X##_result_t; \

+        C##_##X##_value_t *ref; \

+        C##_##X##_node_t *_d; \

+        int _top; \

+        C##_##X##_size_t _tn, _st[48]; \

+    } C##_##X##_iter_t; \

 \

     STC_API C##_##X C##_##X##_init(void); \

     STC_API C##_##X C##_##X##_clone(C##_##X tree); \

diff --git a/stc/cstr.h b/stc/cstr.h
index 369d6034..ad89c6bd 100644
--- a/stc/cstr.h
+++ b/stc/cstr.h
@@ -218,25 +218,12 @@ cstr_iends_with(cstr_t s, const char* needle) {
 }

 

 /* cvec/cmap API functions: */

-

-STC_INLINE uint32_t

-c_string_hash(const char* str) {

-    uint32_t hash = 5381, c; /* djb2 */

-    const uint8_t* p = (const uint8_t*) str;

-    while ((c = *p++)) hash = ((hash << 5) + hash) ^ c;

-    return hash;

-}

-STC_INLINE

-uint32_t cstr_hash_raw(const char* const* p, size_t none) {

-    return c_string_hash(*p);

-}

-

 #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_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_string_hash((x)->str)

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

 

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

 

@@ -270,7 +257,7 @@ STC_DEF cstr_t
 cstr_from_n(const char* str, size_t len) {

     if (len == 0) return cstr_inits;

     struct cstr_rep* rep = (struct cstr_rep*) c_malloc(_cstr_opt_mem(len));

-    cstr_t s = {strncpy(rep->str, str, len)};

+    cstr_t s = {(char *) memcpy(rep->str, str, len)};

     s.str[rep->size = len] = '\0';

     rep->cap = _cstr_opt_cap(len);

     return s;

@@ -332,7 +319,7 @@ cstr_append_n(cstr_t* self, const char* str, size_t len) {
         if (newlen > _cstr_rep(self)->cap) {

             /* handle self append */

             size_t off = (size_t) (str - self->str);

-            cstr_reserve(self, newlen * 3 / 2);

+            cstr_reserve(self, newlen*3/2);

             if (off <= oldlen) str = self->str + off;

         }

         memcpy(&self->str[oldlen], str, len);

@@ -346,7 +333,7 @@ STC_INLINE void _cstr_internal_move(cstr_t* self, size_t pos1, size_t pos2) {
         return;

     size_t len = _cstr_rep(self)->size, newlen = len + pos2 - pos1;

     if (newlen > _cstr_rep(self)->cap)

-        cstr_reserve(self, newlen * 3 / 2);

+        cstr_reserve(self, newlen*3/2);

     memmove(&self->str[pos2], &self->str[pos1], len - pos1);

     self->str[_cstr_rep(self)->size = newlen] = '\0';

 }

@@ -377,7 +364,7 @@ cstr_getdelim(cstr_t *self, int delim, FILE *fp) {
         return false;

     for (;;) {

         if (pos == cap)

-            cap = cstr_reserve(self, cap * 3 / 2 + 34);

+            cap = cstr_reserve(self, cap*3/2 + 34);

         if (c == delim || c == EOF) {

             self->str[_cstr_rep(self)->size = pos] = '\0';

             return true;