Added cmap_emplace_key() / csmap_emplace_key()

More docs.

4 files changed, 69 insertions, 51 deletions

diff --git a/include/stc/algo/filter.h b/include/stc/algo/filter.h
index 1a62c3e1..320cd50d 100644
--- a/include/stc/algo/filter.h
+++ b/include/stc/algo/filter.h
@@ -24,7 +24,7 @@
 #include <stdio.h>
 #define i_val int
 #include <stc/cstack.h>
-#include <stc/calgo.h>
+#include <stc/algorithm.h>
 
 int main(void)
 {
diff --git a/include/stc/cmap.h b/include/stc/cmap.h
index 513a8b93..2dd8cbe6 100644
--- a/include/stc/cmap.h
+++ b/include/stc/cmap.h
@@ -55,7 +55,6 @@ int main(void) {
 #include <stdlib.h>
 #include <string.h>
 struct chash_slot { uint8_t hashx; };
-typedef struct { intptr_t idx; uint8_t hashx, found; } chash_bucket;
 #endif // CMAP_H_INCLUDED
 
 #ifndef _i_prefix
@@ -94,7 +93,7 @@ STC_API _cx_Self        _cx_MEMB(_clone)(_cx_Self map);
 STC_API void            _cx_MEMB(_drop)(_cx_Self* self);
 STC_API void            _cx_MEMB(_clear)(_cx_Self* self);
 STC_API bool            _cx_MEMB(_reserve)(_cx_Self* self, intptr_t capacity);
-STC_API chash_bucket    _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr);
+STC_API _cx_result      _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr);
 STC_API _cx_result      _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey);
 STC_API void            _cx_MEMB(_erase_entry)(_cx_Self* self, _cx_value* val);
 STC_API float           _cx_MEMB(_max_load_factor)(const _cx_Self* self);
@@ -106,9 +105,9 @@ STC_INLINE bool         _cx_MEMB(_empty)(const _cx_Self* map) { return !map->siz
 STC_INLINE intptr_t     _cx_MEMB(_size)(const _cx_Self* map) { return (intptr_t)map->size; }
 STC_INLINE intptr_t     _cx_MEMB(_bucket_count)(_cx_Self* map) { return map->bucket_count; }
 STC_INLINE bool         _cx_MEMB(_contains)(const _cx_Self* self, _cx_keyraw rkey)
-                            { return self->size && _cx_MEMB(_bucket_)(self, &rkey).found; }
+                            { return self->size && !_cx_MEMB(_bucket_)(self, &rkey).inserted; }
 
-#ifndef _i_isset
+#ifdef _i_ismap
     STC_API _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key key, i_val mapped);
     #if !defined i_no_emplace
         STC_API _cx_result  _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped);
@@ -116,14 +115,15 @@ STC_INLINE bool         _cx_MEMB(_contains)(const _cx_Self* self, _cx_keyraw rke
 
     STC_INLINE const _cx_mapped*
     _cx_MEMB(_at)(const _cx_Self* self, _cx_keyraw rkey) {
-        chash_bucket b = _cx_MEMB(_bucket_)(self, &rkey);
-        c_assert(b.found);
-        return &self->data[b.idx].second;
+        _cx_result b = _cx_MEMB(_bucket_)(self, &rkey);
+        c_assert(!b.inserted);
+        return &b.ref->second;
     }
+
     STC_INLINE _cx_mapped*
     _cx_MEMB(_at_mut)(_cx_Self* self, _cx_keyraw rkey)
         { return (_cx_mapped*)_cx_MEMB(_at)(self, rkey); }
-#endif // !_i_isset
+#endif // _i_ismap
 
 #if !defined i_no_clone
 STC_INLINE void _cx_MEMB(_copy)(_cx_Self *self, const _cx_Self* other) {
@@ -151,6 +151,16 @@ _cx_MEMB(_emplace)(_cx_Self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmappe
     }
     return _res;
 }
+
+#ifdef _i_ismap
+    STC_INLINE _cx_result
+    _cx_MEMB(_emplace_key)(_cx_Self* self, _cx_keyraw rkey) {
+        _cx_result _res = _cx_MEMB(_insert_entry_)(self, rkey);
+        if (_res.inserted)
+            _res.ref->first = i_keyfrom(rkey);
+        return _res;
+    }
+#endif // _i_ismap
 #endif // !i_no_emplace
 
 STC_INLINE _cx_raw _cx_MEMB(_value_toraw)(const _cx_value* val) {
@@ -215,19 +225,19 @@ STC_INLINE _cx_iter _cx_MEMB(_advance)(_cx_iter it, size_t n) {
 
 STC_INLINE _cx_iter
 _cx_MEMB(_find)(const _cx_Self* self, _cx_keyraw rkey) {
-    chash_bucket b;
-    if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found)
-        return c_LITERAL(_cx_iter){self->data + b.idx, 
+    _cx_result b;
+    if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted)
+        return c_LITERAL(_cx_iter){b.ref, 
                                    self->data + self->bucket_count,
-                                   self->slot + b.idx};
+                                   self->slot + (b.ref - self->data)};
     return _cx_MEMB(_end)(self);
 }
 
 STC_INLINE const _cx_value*
 _cx_MEMB(_get)(const _cx_Self* self, _cx_keyraw rkey) {
-    chash_bucket b;
-    if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found)
-        return self->data + b.idx;
+    _cx_result b;
+    if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted)
+        return b.ref;
     return NULL;
 }
 
@@ -237,10 +247,10 @@ _cx_MEMB(_get_mut)(_cx_Self* self, _cx_keyraw rkey)
 
 STC_INLINE int
 _cx_MEMB(_erase)(_cx_Self* self, _cx_keyraw rkey) {
-    chash_bucket b = {0};
-    if (self->size && (b = _cx_MEMB(_bucket_)(self, &rkey)).found)
-        _cx_MEMB(_erase_entry)(self, self->data + b.idx);
-    return b.found;
+    _cx_result b;
+    if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted)
+        { _cx_MEMB(_erase_entry)(self, b.ref); return 1; }
+    return 0;
 }
 
 STC_INLINE _cx_iter
@@ -313,7 +323,7 @@ STC_DEF void _cx_MEMB(_clear)(_cx_Self* self) {
     c_memset(self->slot, 0, c_sizeof(chash_slot)*self->bucket_count);
 }
 
-#ifndef _i_isset
+#ifdef _i_ismap
     STC_DEF _cx_result
     _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key _key, i_val _mapped) {
         _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key)));
@@ -340,42 +350,41 @@ STC_DEF void _cx_MEMB(_clear)(_cx_Self* self) {
         return _res;
     }
     #endif // !i_no_emplace
-#endif // !_i_isset
+#endif // _i_ismap
 
-STC_DEF chash_bucket
+STC_DEF _cx_result
 _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr) {
     const uint64_t _hash = i_hash(rkeyptr);
     intptr_t _cap = self->bucket_count;
-    chash_bucket b = {fastrange_2(_hash, _cap), (uint8_t)(_hash | 0x80)};
+    intptr_t _idx = fastrange_2(_hash, _cap);
+    _cx_result b = {NULL, true, (uint8_t)(_hash | 0x80)};
     const chash_slot* s = self->slot;
-    while (s[b.idx].hashx) {
-        if (s[b.idx].hashx == b.hashx) {
-            const _cx_keyraw _raw = i_keyto(_i_keyref(self->data + b.idx));
+    while (s[_idx].hashx) {
+        if (s[_idx].hashx == b.hashx) {
+            const _cx_keyraw _raw = i_keyto(_i_keyref(self->data + _idx));
             if (i_eq((&_raw), rkeyptr)) {
-                b.found = true; 
+                b.inserted = false; 
                 break;
             }
         }
-        if (++b.idx == _cap) b.idx = 0;
+        if (++_idx == _cap) _idx = 0;
     }
+    b.ref = self->data + _idx;
     return b;
 }
 
 STC_DEF _cx_result
 _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) {
-    _cx_result res = {NULL};
     if (self->size >= (intptr_t)((float)self->bucket_count * (i_max_load_factor)))
         if (!_cx_MEMB(_reserve)(self, (intptr_t)(self->size*3/2 + 2)))
-            return res;
+            return c_LITERAL(_cx_result){NULL};
 
-    chash_bucket b = _cx_MEMB(_bucket_)(self, &rkey);
-    res.ref = &self->data[b.idx];
-    if (!b.found) {
-        self->slot[b.idx].hashx = b.hashx;
-        res.inserted = true;
+    _cx_result b = _cx_MEMB(_bucket_)(self, &rkey);
+    if (b.inserted) {
+        self->slot[b.ref - self->data].hashx = b.hashx;
         ++self->size;
     }
-    return res;
+    return b;
 }
 
 #if !defined i_no_clone
@@ -417,9 +426,9 @@ _cx_MEMB(_reserve)(_cx_Self* self, const intptr_t _newcap) {
         const chash_slot* s = self->slot;
         for (intptr_t i = 0; i < _oldbucks; ++i, ++d) if ((s++)->hashx) {
             _cx_keyraw r = i_keyto(_i_keyref(d));
-            chash_bucket b = _cx_MEMB(_bucket_)(&m, &r);
-            m.slot[b.idx].hashx = b.hashx;
-            m.data[b.idx] = *d; // move
+            _cx_result b = _cx_MEMB(_bucket_)(&m, &r);
+            m.slot[b.ref - m.data].hashx = b.hashx;
+            *b.ref = *d; // move
         }
         c_swap(_cx_Self, self, &m);
     }
diff --git a/include/stc/csmap.h b/include/stc/csmap.h
index f4d33a4d..d2e1d1fc 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -170,19 +170,29 @@ _cx_MEMB(_shrink_to_fit)(_cx_Self *self) {
 }
 #endif // !i_no_clone
 
-#ifndef _i_isset
+STC_API _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey);
+
+#ifdef _i_ismap
     STC_API _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key key, i_val mapped);
     #if !defined i_no_emplace
         STC_API _cx_result  _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped);
-    #endif
 
+        STC_INLINE _cx_result
+        _cx_MEMB(_emplace_key)(_cx_Self* self, _cx_keyraw rkey) {
+            _cx_result res = _cx_MEMB(_insert_entry_)(self, rkey);
+            if (res.inserted)
+                res.ref->first = i_keyfrom(rkey);
+            return res;
+        }
+    #endif
     STC_INLINE const _cx_mapped*
     _cx_MEMB(_at)(const _cx_Self* self, _cx_keyraw rkey)
         { _cx_iter it; return &_cx_MEMB(_find_it)(self, rkey, &it)->second; }
+
     STC_INLINE _cx_mapped*
     _cx_MEMB(_at_mut)(_cx_Self* self, _cx_keyraw rkey)
         { _cx_iter it; return &_cx_MEMB(_find_it)(self, rkey, &it)->second; }
-#endif // !_i_isset
+#endif // _i_ismap
 
 STC_INLINE _cx_iter
 _cx_MEMB(_end)(const _cx_Self* self) {
@@ -209,8 +219,6 @@ _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) {
     return true;
 }
 
-static _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey);
-
 STC_INLINE _cx_result
 _cx_MEMB(_insert)(_cx_Self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) {
     _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key)));
@@ -326,7 +334,7 @@ _cx_MEMB(_new_node_)(_cx_Self* self, int level) {
     return tn;
 }
 
-#ifndef _i_isset
+#ifdef _i_ismap
     STC_DEF _cx_result
     _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key _key, i_val _mapped) {
         _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key)));
@@ -353,7 +361,7 @@ _cx_MEMB(_new_node_)(_cx_Self* self, int level) {
         return _res;
     }
     #endif // !i_no_emplace
-#endif // !_i_isset
+#endif // !_i_ismap
 
 STC_DEF _cx_value*
 _cx_MEMB(_find_it)(const _cx_Self* self, _cx_keyraw rkey, _cx_iter* out) {
@@ -407,7 +415,7 @@ _cx_MEMB(_split_)(_cx_node *d, int32_t tn) {
     return tn;
 }
 
-static int32_t
+STC_DEF int32_t
 _cx_MEMB(_insert_entry_i_)(_cx_Self* self, int32_t tn, const _cx_keyraw* rkey, _cx_result* _res) {
     int32_t up[64], tx = tn;
     _cx_node* d = self->nodes;
@@ -439,7 +447,7 @@ _cx_MEMB(_insert_entry_i_)(_cx_Self* self, int32_t tn, const _cx_keyraw* rkey, _
     return up[0];
 }
 
-static _cx_result
+STC_DEF _cx_result
 _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) {
     _cx_result res = {NULL};
     int32_t tn = _cx_MEMB(_insert_entry_i_)(self, self->root, &rkey, &res);
@@ -448,7 +456,7 @@ _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) {
     return res;
 }
 
-static int32_t
+STC_DEF int32_t
 _cx_MEMB(_erase_r_)(_cx_Self *self, int32_t tn, const _cx_keyraw* rkey, int *erased) {
     _cx_node *d = self->nodes;
     if (tn == 0)
@@ -533,7 +541,7 @@ _cx_MEMB(_erase_range)(_cx_Self* self, _cx_iter it1, _cx_iter it2) {
 }
 
 #if !defined i_no_clone
-static int32_t
+STC_DEF int32_t
 _cx_MEMB(_clone_r_)(_cx_Self* self, _cx_node* src, int32_t sn) {
     if (sn == 0)
         return 0;
diff --git a/include/stc/forward.h b/include/stc/forward.h
index 484a8b63..085205cf 100644
--- a/include/stc/forward.h
+++ b/include/stc/forward.h
@@ -120,6 +120,7 @@ typedef struct chash_slot chash_slot;
     typedef struct { \
         SELF##_value *ref; \
         bool inserted; \
+        uint8_t hashx; \
     } SELF##_result; \
 \
     typedef struct { \