Replaced lowBiasHash with fibonacciHash32 / fibonacciHash64. Added <container>_<tag>_init(void) function.

6 files changed, 35 insertions, 48 deletions

diff --git a/examples/benchmark.c b/examples/benchmark.c
index 3c1b49bb..65eef03f 100644
--- a/examples/benchmark.c
+++ b/examples/benchmark.c
@@ -14,16 +14,11 @@
 

 // Visual Studio: compile with -TP to force C++:  cl -TP -EHsc -O2 benchmark.c

 

-

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

-    const uint64_t key = *(const uint64_t *) data;

-    return (uint32_t) (key * 11400714819323198485llu);

-}

-declare_CMap(ii, int64_t, int64_t, c_defaultDestroy, c_defaultEquals, fibonacci_hash);

+declare_CMap(ii, int64_t, int64_t, c_defaultDestroy, c_defaultEquals, c_fibonacciHash64);

 

 KHASH_MAP_INIT_INT64(ii, uint64_t)

 

-size_t seed = 1234;

+size_t seed;

 static const float maxLoadFactor = 0.77f;

 

 crandom64_t rng;

@@ -32,7 +27,7 @@ crandom64_t rng;
 

 

 #define CMAP_SETUP(tag, Key, Value) CMap_##tag map = cmap_init \

-                                    /* ; cmap_##tag##_setLoadFactors(&map, maxLoadFactor, 0.0)*/

+                                    ; cmap_##tag##_setLoadFactors(&map, maxLoadFactor, 0.0)

 #define CMAP_PUT(tag, key, val)     cmap_##tag##_put(&map, key, val)->value

 #define CMAP_ERASE(tag, key)        cmap_##tag##_erase(&map, key)

 #define CMAP_FIND(tag, key)         (cmap_##tag##_find(map, key) != NULL)

@@ -80,8 +75,9 @@ crandom64_t rng;
 #define RMAP_BUCKETS(tag)           map.bucket_count()

 #define RMAP_CLEAR(tag)             map.clear()

 

-const size_t N1 = 7000000;

-const size_t N2 = 10000000;

+const size_t N1 = 10000000 * 5;

+const size_t N2 = 10000000 * 5;

+const size_t N3 = 10000000 * 10;

 #define      RR   20

 int rr = RR;

 

@@ -97,7 +93,7 @@ int rr = RR;
         erased += M##_ERASE(tag, RAND(rr)); \

     } \

     difference = clock() - before; \

-    printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, sum: %zu, erase: %zu\n", \

+    printf(#M ": size: %zu, buckets: %8zu, time: %.02f, sum: %zu, erased %zu\n", \

            M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \

     M##_CLEAR(tag); \

 }

@@ -112,7 +108,7 @@ int rr = RR;
     for (size_t i = 0; i < N2; ++i) \

         erased += M##_ERASE(tag, i); \

     difference = clock() - before; \

-    printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \

+    printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \

            M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \

     M##_CLEAR(tag); \

 }

@@ -123,13 +119,13 @@ int rr = RR;
     size_t erased = 0; \

     clock_t difference, before = clock(); \

     SEED(seed); \

-    for (size_t i = 0; i < N2; ++i) \

+    for (size_t i = 0; i < N3; ++i) \

         M##_PUT(tag, RAND(rr), i); \

     SEED(seed); \

-    for (size_t i = 0; i < N2; ++i) \

+    for (size_t i = 0; i < N3; ++i) \

         erased += M##_ERASE(tag, RAND(rr)); \

     difference = clock() - before; \

-    printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \

+    printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \

            M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \

     M##_CLEAR(tag); \

 }

@@ -139,8 +135,8 @@ int main(int argc, char* argv[])
 {

     rr = argc == 2 ? atoi(argv[1]) : RR;

     seed = time(NULL);

-    printf("\nRandom keys are in range [0, 2^%d):\n",  rr);

-    printf("\nmap<uint64_t, uint64_t>: %zu repeats of Insert random key + remove a different random key:\n", N1);

+    printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n",  rr, seed);

+    printf("\nUnordered maps: %zu repeats of Insert random key + try to remove a random key:\n", N1);

     MAP_TEST1(CMAP, ii)

     MAP_TEST1(KMAP, ii)

 #ifdef __cplusplus

@@ -150,7 +146,7 @@ int main(int argc, char* argv[])
     MAP_TEST1(RMAP, ii)

 #endif

 

-    printf("\nmap<uint64_t, uint64_t>: Insert %zu index keys, then remove them in same order:\n", N2);

+    printf("\nUnordered maps: Insert %zu index keys, then remove them in same order:\n", N2);

     MAP_TEST2(CMAP, ii)

     MAP_TEST2(KMAP, ii)

 #ifdef __cplusplus

@@ -160,7 +156,7 @@ int main(int argc, char* argv[])
     MAP_TEST2(RMAP, ii)

 #endif

 

-    printf("\nmap<uint64_t, uint64_t>: Insert %zu random keys, then remove them in same order:\n", N2);

+    printf("\nUnordered maps: Insert %zu random keys, then remove them in same order:\n", N3);

     MAP_TEST3(CMAP, ii)

     MAP_TEST3(KMAP, ii)

 #ifdef __cplusplus

diff --git a/stc/cdefs.h b/stc/cdefs.h
index b33b9186..8e536438 100644
--- a/stc/cdefs.h
+++ b/stc/cdefs.h
@@ -38,12 +38,8 @@
 

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

 #define STC_API extern

-#define STC_VARDECL extern

-#define STC_VARDEF

 #else

 #define STC_API STC_INLINE

-#define STC_VARDECL static

-#define STC_VARDEF static

 #endif

 

 /* Macro overloading feature support: https://rextester.com/ONP80107 */

@@ -97,16 +93,19 @@ static inline uint32_t  c_defaultHash(const void *data, size_t len) {
     return x;

 }

 

-/* https://nullprogram.com/blog/2018/07/31/: assume len positive multiple of 4 */

+/* https://programmingpraxis.com/2018/06/19/fibonacci-hash */

 /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */

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

+static inline uint32_t c_fibonacciHash32(const void* data, size_t len) {

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

-    uint32_t x = *key;

-    do {

-        x ^= *key++ >> 16;

-        x *= UINT32_C(0x7feb352d);

-    } while (len -= 4);

+    uint32_t x = *key++ * 2654435769u;

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

     return x;

 }

+static inline uint32_t c_fibonacciHash64(const void* data, size_t len) {

+    const volatile uint64_t *key = (const uint64_t *) data;

+    uint64_t x = *key++ * 11400714819323198485ull;

+    while (len -= 8) x ^= *key++ * 11400714819323198485ull;

+    return (uint32_t) (x >> 13);

+}

 

 #endif

diff --git a/stc/clist.h b/stc/clist.h
index 85c2d9b9..026becff 100644
--- a/stc/clist.h
+++ b/stc/clist.h
@@ -91,7 +91,8 @@
  \

     declare_CListTypes(tag, Value); \

  \

-    STC_VARDECL CList_##tag clist_##tag##_init; \

+    STC_INLINE CList_##tag \

+    clist_##tag##_init(void) {CList_##tag x = clist_init; return x;} \

     STC_API void \

     clist_##tag##_destroy(CList_##tag* self); \

     STC_INLINE void \

@@ -149,9 +150,7 @@
 

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

 #define implement_CList_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \

- \

-    STC_VARDEF CList_##tag clist_##tag##_init = clist_init; \

- \

+  \

     STC_API void \

     clist_##tag##_destroy(CList_##tag* self) { \

         while (self->last) \

diff --git a/stc/cmap.h b/stc/cmap.h
index 0b5ae2a5..21f24862 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -158,7 +158,8 @@ typedef struct { \
     uint8_t* _hx; \

 } CType##Iter_##tag, ctype##_##tag##_iter_t; \

  \

-STC_VARDECL CType##_##tag ctype##_##tag##_init; \

+STC_INLINE CType##_##tag \

+ctype##_##tag##_init(void) {CType##_##tag x = cmap_init; return x;} \

 STC_API CType##_##tag \

 ctype##_##tag##_make(size_t initialSize); \

 STC_API void \

@@ -203,10 +204,7 @@ typedef Value CType##Value_##tag, ctype##_##tag##_value_t
 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

 #define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \

                              keyDestroy, RawKey, keyGetRaw, keyInitRaw) \

- \

-STC_VARDEF CType##_##tag ctype##_##tag##_init = cmap_init; \

- \

-STC_API CType##_##tag \

+ STC_API CType##_##tag \

 ctype##_##tag##_make(size_t initialSize) { \

     CType##_##tag h = ctype##_init; \

     ctype##_##tag##_reserve(&h, initialSize); \

diff --git a/stc/cstr.h b/stc/cstr.h
index 4cb1fe60..972e29b6 100644
--- a/stc/cstr.h
+++ b/stc/cstr.h
@@ -35,18 +35,16 @@ typedef struct CStr {
     char* str;

 } CStr;

 

-static size_t _cstr_nullrep[] = {0, 0, 0};

 #define _cstr_rep(self)   (((size_t *) (self)->str) - 2)

 #define _cstr_size(s)     ((size_t *) (s).str)[-2]

 #define _cstr_mem(cap)    (sizeof(size_t) * (3 + (cap)/sizeof(size_t)))

+static size_t _cstr_nullrep[] = {0, 0, 0};

 

+static  CStr cstr_init =  {(char* ) &_cstr_nullrep[2]};

 #define cstr_size(s)      ((const size_t *) (s).str)[-2]

 #define cstr_capacity(s)  ((const size_t *) (s).str)[-1]

 #define cstr_npos         ((size_t) (-1))

 

-

-STC_VARDECL CStr cstr_init;

-

 STC_API CStr

 cstr_makeN(const char* str, size_t len);

 STC_API CStr

@@ -198,8 +196,6 @@ STC_INLINE uint32_t cstr_hashRaw(const char* const* sPtr, size_t ignored) {
 

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

 

-STC_VARDEF CStr cstr_init = {(char* ) &_cstr_nullrep[2]};

-

 STC_API void

 cstr_reserve(CStr* self, size_t cap) {

     size_t len = cstr_size(*self), oldcap = cstr_capacity(*self);

diff --git a/stc/cvec.h b/stc/cvec.h
index 5f393223..74153455 100644
--- a/stc/cvec.h
+++ b/stc/cvec.h
@@ -51,7 +51,8 @@ typedef struct CVec_##tag { \
     Value* data; \

 } CVec_##tag; \

  \

-STC_VARDECL CVec_##tag cvec_##tag##_init; \

+STC_INLINE CVec_##tag \

+cvec_##tag##_init(void) {CVec_##tag x = cvec_init; return x;} \

 STC_API CVec_##tag \

 cvec_##tag##_make(size_t size, Value null); \

 STC_API void \

@@ -113,8 +114,6 @@ typedef RawValue CVecRawValue_##tag
 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

 #define implement_CVec_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \

  \

-STC_VARDEF CVec_##tag cvec_##tag##_init = cvec_init; \

- \

 STC_API CVec_##tag \

 cvec_##tag##_make(size_t size, Value null) { \

     CVec_##tag vec = cvec_init; \