Updated benchmark. Some improvements in cmap iterator. cmap_try_emplace() API change.

4 files changed, 78 insertions, 47 deletions

diff --git a/README.md b/README.md
index 00151960..2cafd2c5 100644
--- a/README.md
+++ b/README.md
@@ -142,7 +142,7 @@ Finally, cmap mimics c++17 unordered_map::try_emplace() and avoids cstr memory l
 ```

 declare_cmap_str(ss, cstr_t, cstr_destroy); // cstr_t -> cstr_t

 ...

-cmap_try_emplace(&map, ss, "already here", cstr_make("won't be called then")); // special: tag 'ss' is a parameter here.

+cmap_try_emplace(ss, &map, "already here", cstr_make("won't be called then")); // note: tag 'ss' is a parameter here.

 ```

 You may want to look at **examples/advanced.c**, it demonstrates how to use a custom struct as a hash map key, using the optional parameters to declare_cmap().

 

diff --git a/examples/benchmark.c b/examples/benchmark.c
index 753f39b3..3ff193bc 100644
--- a/examples/benchmark.c
+++ b/examples/benchmark.c
@@ -11,6 +11,8 @@
 #include "others/bytell_hash_map.hpp"

 #include "others/robin_hood.hpp"

 #include "others/hopscotch_map.h"

+#include "others/sparsepp/spp.h"

+template<typename C> inline void destroy_me(C& c) { C().swap(c); }

 #endif

 

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

@@ -35,59 +37,90 @@ crandom_eng64_t rng;
 #define CMAP_SETUP(tt, Key, Value) cmap_##tt map = cmap_init \

                                     ; cmap_##tt##_set_load_factors(&map, max_load_factor, 0.0)

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

+#define CMAP_INSERT(tt, key, val)  cmap_##tt##_insert(&map, key, val)

+#define CMAP_EMPLACE(tt, key, val) cmap_try_emplace(tt, &map, key, val)

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

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

 #define CMAP_SIZE(tt)              cmap_size(map)

-#define CMAP_BUCKETS(tt)           (map).bucket_count

-#define CMAP_CLEAR(tt)             cmap_##tt##_destroy(&map)

+#define CMAP_BUCKETS(tt)           cmap_bucket_count(map)

+#define CMAP_CLEAR(tt)             cmap_##tt##_clear(&map)

+#define CMAP_DTOR(tt)              cmap_##tt##_destroy(&map)

 

 #define KMAP_SETUP(tt, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret

 #define KMAP_PUT(tt, key, val)     (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki]))

+#define KMAP_INSERT(tt, key, val)  (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val) : val)

 #define KMAP_ERASE(tt, key)        ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0)

 #define KMAP_FIND(tt, key)         (kh_get(ii, map, key) != kh_end(map))

 #define KMAP_SIZE(tt)              kh_size(map)

 #define KMAP_BUCKETS(tt)           kh_n_buckets(map)

-#define KMAP_CLEAR(tt)             kh_destroy(ii, map)

+#define KMAP_CLEAR(tt)             kh_clear(ii, map)

+#define KMAP_DTOR(tt)              kh_destroy(ii, map)

 

 #define UMAP_SETUP(tt, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(max_load_factor)

 #define UMAP_PUT(tt, key, val)     (map[key] = val)

+#define UMAP_INSERT(tt, key, val)  map.insert(std::make_pair(key, val))

+#define UMAP_EMPLACE(tt, key, val) map.emplace(key, val)

 #define UMAP_FIND(tt, key)         (map.find(key) != map.end())

 #define UMAP_ERASE(tt, key)        map.erase(key)

 #define UMAP_SIZE(tt)              map.size()

 #define UMAP_BUCKETS(tt)           map.bucket_count()

 #define UMAP_CLEAR(tt)             map.clear()

+#define UMAP_DTOR(tt)              destroy_me(map)

 

 #define BMAP_SETUP(tt, Key, Value) ska::bytell_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)

-#define BMAP_PUT(tt, key, val)     (map[key] = val)

-#define BMAP_FIND(tt, key)         (map.find(key) != map.end())

-#define BMAP_ERASE(tt, key)        map.erase(key)

-#define BMAP_SIZE(tt)              map.size()

-#define BMAP_BUCKETS(tt)           map.bucket_count()

-#define BMAP_CLEAR(tt)             map.clear()

+#define BMAP_PUT(tt, key, val)     UMAP_PUT(tt, key, val)

+#define BMAP_INSERT(tt, key, val)  UMAP_INSERT(tt, key, val)

+#define BMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val)

+#define BMAP_FIND(tt, key)         UMAP_FIND(tt, key)

+#define BMAP_ERASE(tt, key)        UMAP_ERASE(tt, key)

+#define BMAP_SIZE(tt)              UMAP_SIZE(tt)

+#define BMAP_BUCKETS(tt)           UMAP_BUCKETS(tt)

+#define BMAP_CLEAR(tt)             UMAP_CLEAR(tt)

+#define BMAP_DTOR(tt)              UMAP_DTOR(tt)

 

 #define FMAP_SETUP(tt, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)

-#define FMAP_PUT(tt, key, val)     (map[key] = val)

-#define FMAP_FIND(tt, key)         (map.find(key) != map.end())

-#define FMAP_ERASE(tt, key)        map.erase(key)

-#define FMAP_SIZE(tt)              map.size()

-#define FMAP_BUCKETS(tt)           map.bucket_count()

-#define FMAP_CLEAR(tt)             map.clear()

+#define FMAP_PUT(tt, key, val)     UMAP_PUT(tt, key, val)

+#define FMAP_INSERT(tt, key, val)  UMAP_INSERT(tt, key, val)

+#define FMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val)

+#define FMAP_FIND(tt, key)         UMAP_FIND(tt, key)

+#define FMAP_ERASE(tt, key)        UMAP_ERASE(tt, key)

+#define FMAP_SIZE(tt)              UMAP_SIZE(tt)

+#define FMAP_BUCKETS(tt)           UMAP_BUCKETS(tt)

+#define FMAP_CLEAR(tt)             UMAP_CLEAR(tt)

+#define FMAP_DTOR(tt)              UMAP_DTOR(tt)

 

 #define HMAP_SETUP(tt, Key, Value) tsl::hopscotch_map<Key, Value> map; map.max_load_factor(max_load_factor)

-#define HMAP_PUT(tt, key, val)     (map[key] = val)

-#define HMAP_FIND(tt, key)         (map.find(key) != map.end())

-#define HMAP_ERASE(tt, key)        map.erase(key)

-#define HMAP_SIZE(tt)              map.size()

-#define HMAP_BUCKETS(tt)           map.bucket_count()

-#define HMAP_CLEAR(tt)             map.clear()

+#define HMAP_PUT(tt, key, val)     UMAP_PUT(tt, key, val)

+#define HMAP_INSERT(tt, key, val)  UMAP_INSERT(tt, key, val)

+#define HMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val)

+#define HMAP_FIND(tt, key)         UMAP_FIND(tt, key)

+#define HMAP_ERASE(tt, key)        UMAP_ERASE(tt, key)

+#define HMAP_SIZE(tt)              UMAP_SIZE(tt)

+#define HMAP_BUCKETS(tt)           UMAP_BUCKETS(tt)

+#define HMAP_CLEAR(tt)             UMAP_CLEAR(tt)

+#define HMAP_DTOR(tt)              UMAP_DTOR(tt)

 

 #define RMAP_SETUP(tt, Key, Value) robin_hood::unordered_map<Key, Value> map

-#define RMAP_PUT(tt, key, val)     (map[key] = val)

-#define RMAP_FIND(tt, key)         (map.find(key) != map.end())

-#define RMAP_ERASE(tt, key)        map.erase(key)

-#define RMAP_SIZE(tt)              map.size()

+#define RMAP_PUT(tt, key, val)     UMAP_PUT(tt, key, val)

+#define RMAP_INSERT(tt, key, val)  UMAP_INSERT(tt, key, val)

+#define RMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val)

+#define RMAP_FIND(tt, key)         UMAP_FIND(tt, key)

+#define RMAP_ERASE(tt, key)        UMAP_ERASE(tt, key)

+#define RMAP_SIZE(tt)              UMAP_SIZE(tt)

 #define RMAP_BUCKETS(tt)           map.mask()

-#define RMAP_CLEAR(tt)             map.clear()

+#define RMAP_CLEAR(tt)             UMAP_CLEAR(tt)

+#define RMAP_DTOR(tt)              UMAP_DTOR(tt)

+

+#define SMAP_SETUP(tt, Key, Value) spp::sparse_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)

+#define SMAP_PUT(tt, key, val)     UMAP_PUT(tt, key, val)

+#define SMAP_INSERT(tt, key, val)  UMAP_INSERT(tt, key, val)

+#define SMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val)

+#define SMAP_FIND(tt, key)         UMAP_FIND(tt, key)

+#define SMAP_ERASE(tt, key)        UMAP_ERASE(tt, key)

+#define SMAP_SIZE(tt)              UMAP_SIZE(tt)

+#define SMAP_BUCKETS(tt)           UMAP_BUCKETS(tt)

+#define SMAP_CLEAR(tt)             UMAP_CLEAR(tt)

+#define SMAP_DTOR(tt)              UMAP_DTOR(tt)

 

 const size_t N1 = 10000000 * 5;

 const size_t N2 = 10000000 * 5;

@@ -145,9 +178,9 @@ int rr = RR;
 }

 

 #ifndef __cplusplus

-#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) // MAP_TEST##n(KMAP, ii)

+#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii)

 #else

-#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) \

+#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) MAP_TEST##n(SMAP, ii) \

                     MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) MAP_TEST##n(HMAP, ii)

 #endif

 

diff --git a/examples/words.c b/examples/words.c
index f6182cbd..a10811c1 100644
--- a/examples/words.c
+++ b/examples/words.c
@@ -9,7 +9,7 @@ declare_clist_str();
 declare_cmap_str(si, int);
 
 typedef const char* input_t;
- 
+
 int main1()
 {
     clist_str lwords = clist_init;
@@ -17,11 +17,7 @@ int main1()
         "this", "sentence", "is", "not", "a", "sentence",
         "this", "sentence", "is", "a", "hoax"
     ));
-    c_foreach (w, clist_str, lwords) {
-        printf("%s\n", w.item->value);
-    }
-    
-    
+
     cvec_str words = cvec_init;
     c_push(&words, cvec_str, c_items(
         "this", "sentence", "is", "not", "a", "sentence",
@@ -32,7 +28,7 @@ int main1()
     c_foreach (w, cvec_str, words) {
         ++cmap_si_insert(&word_map, w.item->str, 0)->value;
     }
- 
+
     c_foreach (pair, cmap_si, word_map) {
         printf("%d occurrences of word '%s'\n",
                pair.item->value,
@@ -56,12 +52,12 @@ int main2()
         "this", "sentence", "is", "not", "a", "sentence",
         "this", "sentence", "is", "a", "hoax" 
     };
- 
+
     std::unordered_map<std::string, size_t>  word_map;
     for (const auto &w : words) {
         ++word_map[w];
     }
- 
+
     for (const auto &pair : word_map) {
         std::cout << pair.second
                   << " occurrences of word '"
diff --git a/stc/cmap.h b/stc/cmap.h
index 211fea1a..6be45863 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -55,9 +55,11 @@ int main(void) {
 

 #define cmap_init                     {NULL, NULL, 0, 0, 0.85f, 0.15f}

 #define cmap_size(m)                  ((size_t) (m).size)

+#define cmap_bucket_count(m)          ((size_t) (m).bucket_count)

 #define cset_init                     cmap_init

 #define cset_size(s)                  cmap_size(s)

-#define cmap_try_emplace(self, tag, k, v) do { \

+#define cset_bucket_count(s)          cmap_bucket_count(s)

+#define cmap_try_emplace(tag, self, k, v) do { \

     struct cmap_##tag##_result __r = cmap_##tag##_insert_key(self, k); \

     if (__r.inserted) __r.entry->value = v; \

 } while (false)

@@ -299,7 +301,7 @@ ctype##_##tag##_put(ctype##_##tag* self, OPT_2_##ctype(ctype##_##tag##_rawkey_t
 STC_API ctype##_##tag##_entry_t* \

 ctype##_##tag##_insert(ctype##_##tag* self, OPT_2_##ctype(ctype##_##tag##_rawkey_t rawKey, Value value)) { \

     struct ctype##_##tag##_result res = ctype##_##tag##_insert_key(self, rawKey); \

-    OPT_1_##ctype( if (res.inserted) res.entry->value = value; ) \

+    OPT_1_##ctype( if (res.inserted) res.entry->value = value; else valueDestroy(&value); ) \

     return res.entry; \

 } \

  \

@@ -310,12 +312,12 @@ ctype##_##tag##_reserve(ctype##_##tag* self, size_t newcap) { \
     newcap = (size_t) (newcap / self->max_load_factor) | 1; \

     ctype##_##tag tmp = { \

         c_new_n(ctype##_##tag##_entry_t, newcap), \

-        (uint8_t *) calloc(newcap, sizeof(uint8_t)), \

+        (uint8_t *) calloc(newcap + 1, sizeof(uint8_t)), \

         self->size, (uint32_t) newcap, \

         self->max_load_factor, self->shrink_limit_factor \

     }; \

     /* Rehash: */ \

-    c_swap(ctype##_##tag, *self, tmp); \

+    tmp._hashx[newcap] = 0xff; c_swap(ctype##_##tag, *self, tmp); \

     ctype##_##tag##_entry_t* e = tmp.table, *slot = self->table; \

     uint8_t* hashx = self->_hashx; \

     uint32_t hx; \

@@ -375,7 +377,7 @@ ctype##_##tag##_begin(ctype##_##tag* map) { \
  \

 STC_API void \

 ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \

-    while (++it->item != it->end && *++it->_hx == 0) ; \

+    while ((++it->item, *++it->_hx == 0)) ; \

 }

 

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

@@ -383,14 +385,14 @@ ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \
 STC_API uint32_t c_default_hash16(const void *data, size_t len) {

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

     uint64_t x = 0xc613fc15u;

-    while (len -= 2) x = ((*key++ + x) * 2654435769u) >> 13;

+    while (len -= 2) x = ((*key++ + x) * 2654435769ull) >> 13;

     return (uint32_t) x;

 }

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

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

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

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

-    return (uint32_t) x;

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

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

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

 }

 

 #else