From 9f724cfeec7b78cc2d20361132cbf006d7672a18 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com>
Date: Mon, 9 Mar 2020 22:43:28 +0100
Subject: map fixes

Fixed maxLoadFactor and added hash map reduce on initial hash, faster.
---
 cmap.h | 24 +++++++++++++-----------
 1 file changed, 13 insertions(+), 11 deletions(-)

diff --git a/cmap.h b/cmap.h
index 1bc8a615..2b6319f1 100644
--- a/cmap.h
+++ b/cmap.h
@@ -25,10 +25,9 @@
 
 #include "cvector.h"
 
-#define cmap_initializer  {cvector_initializer, 0, 80, 167}
+#define cmap_initializer  {cvector_initializer, 0, 0.8f}
 #define cmap_size(cm)     ((size_t) (cm)._size)
 #define cmap_buckets(cm)  cvector_capacity((cm)._vec)
-#define cmap_maxLoadFactor(cm) ((cm).maxLoadPercentage / 100.0)
 
 
 // CMapEntry:
@@ -79,8 +78,7 @@ typedef struct CMapEntry_##tag CMapEntry_##tag
 typedef struct CMap_##tag { \
     CVector_map_##tag _vec; \
     size_t _size; \
-    uint16_t maxLoadPercentage; \
-    uint16_t expandPercentage; \
+    float maxLoadFactor; \
 } CMap_##tag; \
  \
 typedef struct cmap_##tag##_iter_t { \
@@ -114,15 +112,15 @@ static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \
     _cdef_swap(size_t, a->_size, b->_size); \
 } \
  \
-static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float loadFactor) { \
-    self->maxLoadPercentage = (uint16_t) (loadFactor * 100.99); \
-    if (cmap_size(*self) > cmap_buckets(*self) * loadFactor) \
-        cmap_##tag##_reserve(self, 7 + cmap_size(*self) / self->maxLoadPercentage); \
+static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \
+    self->maxLoadFactor = fac; \
+    if (cmap_size(*self) > cmap_buckets(*self) * fac) \
+        cmap_##tag##_reserve(self, 7 + (size_t) (cmap_size(*self) / fac)); \
 } \
  \
 static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \
     size_t cap = cvector_capacity(cm._vec); \
-    size_t idx = keyHasher(&rawKey, sizeof(Key)) % cap; \
+    size_t idx = cmap_reduce(keyHasher(&rawKey, sizeof(Key)), cap); \
     size_t first = idx, found = cap, state = cm._vec.data[idx].state; \
     FIBONACCI_DECL; \
     do { \
@@ -143,8 +141,8 @@ static inline CMapEntry_##tag* cmap_##tag##_get(CMap_##tag cm, KeyRaw rawKey) {
  \
 static inline CMapEntry_##tag* cmap_##tag##_put(CMap_##tag* self, KeyRaw rawKey, Value value) { \
     size_t cap = cvector_capacity(self->_vec); \
-    if (cmap_size(*self) >= cap * self->maxLoadPercentage / 100) \
-        cap = cmap_##tag##_reserve(self, cap * self->expandPercentage / 100); \
+    if (cmap_size(*self) >= cap * self->maxLoadFactor) \
+        cap = cmap_##tag##_reserve(self, (size_t) (cap * 1.8)); \
     size_t idx = cmap_##tag##_bucket(*self, rawKey); \
     CMapEntry_##tag* e = &self->_vec.data[idx]; \
     e->value = value; \
@@ -207,4 +205,8 @@ typedef Value cmap_##tag##_value_t
 #define FIBONACCI_DECL  size_t fib1 = 0, fib2 = 1, fibx
 #define FIBONACCI_NEXT  (fibx = fib1 + fib2, fib1 = fib2, fib2 = fibx)
 
+static inline uint32_t cmap_reduce(uint32_t x, uint32_t N) {
+    return ((uint64_t) x * (uint64_t) N) >> 32 ;
+}
+
 #endif
-- 
cgit v1.2.3


From 4d237ccc0afa8f2fa655b6b885bae025e0d81993 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com>
Date: Tue, 10 Mar 2020 01:06:13 +0100
Subject: Fixed map lookup speed. small bug.

---
 cmap.h | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

diff --git a/cmap.h b/cmap.h
index 2b6319f1..d55cb317 100644
--- a/cmap.h
+++ b/cmap.h
@@ -33,7 +33,7 @@
 // CMapEntry:
 enum { CMapEntry_VACANT = 0, 
        CMapEntry_INUSE = 1,
-       CMapEntry_REMOVED = 2
+       CMapEntry_ERASED = 2
 };
 #define declare_CMapEntry(tag, Key, Value, keyDestroy, valueDestroy) \
 struct CMapEntry_##tag { \
@@ -121,16 +121,21 @@ static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) {
 static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \
     size_t cap = cvector_capacity(cm._vec); \
     size_t idx = cmap_reduce(keyHasher(&rawKey, sizeof(Key)), cap); \
-    size_t first = idx, found = cap, state = cm._vec.data[idx].state; \
+    size_t first = idx, erased_idx = cap, state = cm._vec.data[idx].state; \
     FIBONACCI_DECL; \
     do { \
-        if (state == CMapEntry_INUSE && keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) == 0) \
-            return idx; \
-        if (state == CMapEntry_REMOVED && found == cap) \
-            found = idx; \
+        switch (state) { \
+            case CMapEntry_VACANT: \
+                return erased_idx == cap ? idx : erased_idx; \
+            case CMapEntry_INUSE: \
+                if (keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) == 0) return idx; \
+                break; \
+            case CMapEntry_ERASED: \
+                if (erased_idx == cap) erased_idx = idx; \
+                break; \
+        } \
         state = cm._vec.data[ idx = (first + FIBONACCI_NEXT) % cap ].state; \
-    } while (state != CMapEntry_VACANT); \
-    return found == cap ? idx : found; \
+    } while (1); \
 } \
  \
 static inline CMapEntry_##tag* cmap_##tag##_get(CMap_##tag cm, KeyRaw rawKey) { \
@@ -173,7 +178,7 @@ static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \
     CMapEntry_##tag* e = cmap_##tag##_get(*self, rawKey); \
     if (e) { \
         cmapentry_##tag##_destroy(e); \
-        e->state = CMapEntry_REMOVED; \
+        e->state = CMapEntry_ERASED; \
         --self->_size; \
         return true; \
     } \
-- 
cgit v1.2.3


From 1f93cd63a5e2f13d5954c7519c7869ba6c870427 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com>
Date: Tue, 10 Mar 2020 09:43:22 +0100
Subject: Fix map

Swaps inuse buckets with tombstones if possibe when used
---
 cdef.h    |  4 ++--
 cmap.h    | 13 +++++++++----
 cstring.h |  8 ++++----
 3 files changed, 15 insertions(+), 10 deletions(-)

diff --git a/cdef.h b/cdef.h
index 3282f9ac..865436a0 100644
--- a/cdef.h
+++ b/cdef.h
@@ -37,8 +37,8 @@
 // #define foo_1(X)     foo_2(X, 100)
 // #define foo_2(X, Y)  X + Y
 
-#define                 _cdef_max_alloca   (1000)
-#define                 _cdef_swap(T, x, y) { T __t = x; x = y; y = __t; }
+#define                 cdef_max_alloca   (1000)
+#define                 cdef_swap(T, x, y) { T __t = x; x = y; y = __t; }
 
 #define                 cdef_initRaw(x) (x)
 #define                 cdef_getRaw(x) (x)
diff --git a/cmap.h b/cmap.h
index d55cb317..5ec158ec 100644
--- a/cmap.h
+++ b/cmap.h
@@ -109,7 +109,7 @@ static inline void cmap_##tag##_clear(CMap_##tag* self) { \
  \
 static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \
     cvector_map_##tag##_swap(&a->_vec, &b->_vec); \
-    _cdef_swap(size_t, a->_size, b->_size); \
+    cdef_swap(size_t, a->_size, b->_size); \
 } \
  \
 static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \
@@ -126,10 +126,15 @@ static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \
     do { \
         switch (state) { \
             case CMapEntry_VACANT: \
-                return erased_idx == cap ? idx : erased_idx; \
+                return erased_idx != cap ? erased_idx : idx; \
             case CMapEntry_INUSE: \
-                if (keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) == 0) return idx; \
-                break; \
+                if (keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \
+                    break; \
+                if (erased_idx != cap) { \
+                    cdef_swap(CMapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \
+                    return erased_idx; \
+                } \
+                return idx; \
             case CMapEntry_ERASED: \
                 if (erased_idx == cap) erased_idx = idx; \
                 break; \
diff --git a/cstring.h b/cstring.h
index 02dd3446..f877847c 100644
--- a/cstring.h
+++ b/cstring.h
@@ -138,10 +138,10 @@ static inline void _cstring_internalMove(CString* self, size_t pos1, size_t pos2
 }
 
 static inline void cstring_insertN(CString* self, size_t pos, const char* str, size_t n) {
-    char* xstr = (char *) memcpy(n > _cdef_max_alloca ? malloc(n) : alloca(n), str, n);
+    char* xstr = (char *) memcpy(n > cdef_max_alloca ? malloc(n) : alloca(n), str, n);
     _cstring_internalMove(self, pos, pos + n);
     memcpy(&self->str[pos], xstr, n);
-    if (n > _cdef_max_alloca) free(xstr); 
+    if (n > cdef_max_alloca) free(xstr); 
 }
 
 static inline void cstring_insert(CString* self, size_t pos, const char* str) {
@@ -161,10 +161,10 @@ static inline size_t cstring_findN(CString cs, size_t pos, const char* needle, s
 static inline size_t cstring_replaceN(CString* self, size_t pos, const char* s1, size_t n1, const char* s2, size_t n2) {
     size_t pos2 = cstring_findN(*self, pos, s1, n1);
     if (pos2 == cstring_npos) return cstring_npos;
-    char* xs2 = (char *) memcpy(n2 > _cdef_max_alloca ? malloc(n2) : alloca(n2), s2, n2);
+    char* xs2 = (char *) memcpy(n2 > cdef_max_alloca ? malloc(n2) : alloca(n2), s2, n2);
     _cstring_internalMove(self, pos2 + n1, pos2 + n2);
     memcpy(&self->str[pos2], xs2, n2);
-    if (n2 > _cdef_max_alloca) free(xs2);
+    if (n2 > cdef_max_alloca) free(xs2);
     return pos2;
 }
 
-- 
cgit v1.2.3