Fixed bug: cmap_erase_it() return iterator. Fixed mem-leak in cdeq_X_insert() and cvec_X_insert(). Added iterator invalidation documentation.

9 files changed, 86 insertions, 89 deletions

diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md
index b07ee2b0..d921a5fb 100644
--- a/docs/cdeq_api.md
+++ b/docs/cdeq_api.md
@@ -51,26 +51,23 @@ cdeq_X_value_t*     cdeq_X_front(const cdeq_X* self);
 cdeq_X_value_t*     cdeq_X_back(const cdeq_X* self);
 
 void                cdeq_X_push_front(cdeq_X* self, Value value);
-void                cdeq_X_push_back(cdeq_X* self, Value value);
 void                cdeq_X_emplace_front(cdeq_X* self, RawValue raw);
-void                cdeq_X_emplace_back(cdeq_X* self, RawValue raw);
-void                cdeq_X_emplace_n(cdeq_X *self, const cdeq_X_rawvalue_t arr[], size_t n);
-
 void                cdeq_X_pop_front(cdeq_X* self);
+
+void                cdeq_X_push_back(cdeq_X* self, Value value);
+void                cdeq_X_emplace_back(cdeq_X* self, RawValue raw);
 void                cdeq_X_pop_back(cdeq_X* self); 
 
-cdeq_X_iter_t       cdeq_X_emplace(cdeq_X* self, cdeq_X_iter_t it, RawValue raw);
-cdeq_X_iter_t       cdeq_X_emplace_at(cdeq_X* self, size_t idx, RawValue raw);
-cdeq_X_iter_t       cdeq_X_insert(cdeq_X* self, cdeq_X_iter_t it, Value value);
-cdeq_X_iter_t       cdeq_X_insert_at(cdeq_X* self, size_t idx, Value value);
+cdeq_X_iter_t       cdeq_X_insert(cdeq_X* self, cdeq_X_iter_t it, Value value);              // expects new/cloned value
 cdeq_X_iter_t       cdeq_X_insert_range(cdeq_X* self, cdeq_X_iter_t it,
-                                        cdeq_X_iter_t first, cdeq_X_iter_t finish);
-cdeq_X_iter_t       cdeq_X_insert_range_p(cdeq_X* self, cdeq_X_value_t* it,
-                                          const cdeq_X_value_t* pfirst, const cdeq_X_value_t* pfinish);
+                                        cdeq_X_iter_t it1, cdeq_X_iter_t it2);               // clones input values
+cdeq_X_iter_t       cdeq_X_insert_at(cdeq_X* self, size_t idx, const Value arr[], size_t n); // clones input values
+
+cdeq_X_iter_t       cdeq_X_emplace(cdeq_X* self, cdeq_X_iter_t it, RawValue raw);
+void                cdeq_X_emplace_n(cdeq_X *self, const RawValue arr[], size_t n);          // emplace_back only
 
 cdeq_X_iter_t       cdeq_X_erase_it(cdeq_X* self, cdeq_X_iter_t it);
-cdeq_X_iter_t       cdeq_X_erase_range(cdeq_X* self, cdeq_X_iter_t first, cdeq_X_iter_t finish);
-cdeq_X_iter_t       cdeq_X_erase_range_p(cdeq_X* self, cdeq_X_value_t* pfirst, cdeq_X_value_t* pfinish);
+cdeq_X_iter_t       cdeq_X_erase_range(cdeq_X* self, cdeq_X_iter_t it1, cdeq_X_iter_t it2);
 cdeq_X_iter_t       cdeq_X_erase_n(cdeq_X* self, size_t idx, size_t n);
 
 cdeq_X_iter_t       cdeq_X_find(const cdeq_X* self, RawValue raw);
diff --git a/docs/cmap_api.md b/docs/cmap_api.md
index 39550a19..f43afa44 100644
--- a/docs/cmap_api.md
+++ b/docs/cmap_api.md
@@ -4,6 +4,10 @@
 A **cmap** is an associative container that contains key-value pairs with unique keys. Search, insertion,
 and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as closed hashing (aka open addressing) with linear probing, and without leaving tombstones on erase.
 
+***Iterator invalidation***: References and iterators are invalidated after erase. No iterators are invalidated after insert.
+The order of elements is preserved after erase and insert. This makes it possible to erase individual elements while iterating
+through the container by using the returned iterator from *erase_it()*, which references the next element.
+
 See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) for a functional description.
 
 ## Header file and declaration
diff --git a/docs/csmap_api.md b/docs/csmap_api.md
index dca919fb..6aa341cd 100644
--- a/docs/csmap_api.md
+++ b/docs/csmap_api.md
@@ -6,6 +6,10 @@ using the comparison function *keyCompare*. Search, removal, and insertion opera
 **csmap** is implemented as an AA-tree (Arne Andersson, 1993), which tends to create a flatter structure
 (slightly more balanced) than red-black trees.
 
+***Iterator invalidation***: Iterators are invalidated after insert and erase. References are only invalidated
+after erase. It is possible to erase individual elements while iterating through the container by using the 
+returned iterator from *erase_it()*, which references the next element. Alternatively *erase_range()* can be used.
+
 See the c++ class [std::map](https://en.cppreference.com/w/cpp/container/map) for a functional description.
 
 ## Header file and declaration
diff --git a/docs/cstr_api.md b/docs/cstr_api.md
index 58f4a1bf..df457c0b 100644
--- a/docs/cstr_api.md
+++ b/docs/cstr_api.md
@@ -58,15 +58,16 @@ void         cstr_erase_n(cstr* self, size_t pos, size_t n);
 int          cstr_compare(const cstr *s1, const cstr *s2);
 bool         cstr_equals(cstr s, const char* str);
 bool         cstr_equals_s(cstr s, cstr s2);
-bool         cstr_iequals(cstr s, const char* str);                   // prefix i = case-insensitive
 size_t       cstr_find(cstr s, const char* substr);
 size_t       cstr_find_n(cstr s, const char* substr, size_t pos, size_t n);
-size_t       cstr_ifind_n(cstr s, const char* substr, size_t pos, size_t n);
 bool         cstr_contains(cstr s, const char* substr);
-bool         cstr_icontains(cstr s, const char* substr);
 bool         cstr_begins_with(cstr s, const char* substr);
-bool         cstr_ibegins_with(cstr s, const char* substr);
 bool         cstr_ends_with(cstr s, const char* substr);
+
+bool         cstr_iequals(cstr s, const char* str);                   // prefix i = case-insensitive
+size_t       cstr_ifind_n(cstr s, const char* substr, size_t pos, size_t n);
+bool         cstr_icontains(cstr s, const char* substr);
+bool         cstr_ibegins_with(cstr s, const char* substr);
 bool         cstr_iends_with(cstr s, const char* substr);
 
 void         cstr_push_back(cstr* self, char ch);
diff --git a/docs/cvec_api.md b/docs/cvec_api.md
index d945e5e2..14bce940 100644
--- a/docs/cvec_api.md
+++ b/docs/cvec_api.md
@@ -55,17 +55,15 @@ cvec_X_value_t*     cvec_X_back(const cvec_X* self);
 
 void                cvec_X_push_back(cvec_X* self, Value value);
 void                cvec_X_emplace_back(cvec_X* self, RawValue raw);
-void                cvec_X_emplace_n(cvec_X *self, const cvec_X_rawvalue_t arr[], size_t n);
-
 void                cvec_X_pop_back(cvec_X* self);
 
-cvec_X_iter_t       cvec_X_insert(cvec_X* self, cvec_X_iter_t it, Value value);
-cvec_X_iter_t       cvec_X_insert_at(cvec_X* self, size_t idx, Value value);
+cvec_X_iter_t       cvec_X_insert(cvec_X* self, cvec_X_iter_t it, Value value);              // expects new/cloned value
 cvec_X_iter_t       cvec_X_insert_range(cvec_X* self, cvec_X_iter_t it,
-                                        cvec_X_iter_t i1, cvec_X_iter_t i2);
+                                        cvec_X_iter_t i1, cvec_X_iter_t i2);                 // clones input values
+cvec_X_iter_t       cvec_X_insert_at(cvec_X* self, size_t idx, const Value[] arr, size_t n); // clones input values
 
 cvec_X_iter_t       cvec_X_emplace(cvec_X* self, cvec_X_iter_t it, RawValue raw);
-cvec_X_iter_t       cvec_X_emplace_at(cvec_X* self, size_t idx, RawValue raw);
+void                cvec_X_emplace_n(cvec_X *self, const RawValue arr[], size_t n);          // emplace_back only
 
 cvec_X_iter_t       cvec_X_erase_it(cvec_X* self, cvec_X_iter_t it);
 cvec_X_iter_t       cvec_X_erase_range(cvec_X* self, cvec_X_iter_t i1, cvec_X_iter_t i2);
diff --git a/stc/cdeq.h b/stc/cdeq.h
index 9c07fc4b..7fa661d9 100644
--- a/stc/cdeq.h
+++ b/stc/cdeq.h
@@ -113,35 +113,32 @@ typedef int (*c_cmp_fn)(const void*, const void*);
     } \

 \

     STC_API CX##_iter_t \

-    CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* pfirst, const CX##_value_t* pfinish); \

-\

-    STC_INLINE CX##_iter_t \

-    CX##_insert_range(CX* self, CX##_iter_t it, CX##_iter_t first, CX##_iter_t finish) { \

-        return CX##_insert_range_p(self, it.ref, first.ref, finish.ref); \

-    } \

+    CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* p1, \

+                                                     const CX##_value_t* p2, bool clone); \

     STC_INLINE CX##_iter_t \

     CX##_insert(CX* self, CX##_iter_t it, Value value) { \

-        return CX##_insert_range_p(self, it.ref, &value, &value + 1); \

-    } \

-    STC_INLINE CX##_iter_t \

-    CX##_insert_at(CX* self, size_t idx, Value value) { \

-        return CX##_insert_range_p(self, self->data + idx, &value, &value + 1); \

+        it = CX##_insert_range_p(self, it.ref, &value, &value + 1, false); \

+        *it.ref = value; return it; \

     } \

     STC_INLINE CX##_iter_t \

     CX##_emplace(CX* self, CX##_iter_t it, RawValue raw) { \

         return CX##_insert(self, it, valueFromRaw(raw)); \

     } \

     STC_INLINE CX##_iter_t \

-    CX##_emplace_at(CX* self, size_t idx, RawValue raw) { \

-        return CX##_insert_at(self, idx, valueFromRaw(raw)); \

+    CX##_insert_range(CX* self, CX##_iter_t it, CX##_iter_t it1, CX##_iter_t it2) { \

+        return CX##_insert_range_p(self, it.ref, it1.ref, it2.ref, true); \

+    } \

+    STC_INLINE CX##_iter_t \

+    CX##_insert_at(CX* self, size_t idx, const CX##_value_t arr[], size_t n) { \

+        return CX##_insert_range_p(self, self->data + idx, arr, arr + n, true); \

     } \

 \

     STC_API CX##_iter_t \

-    CX##_erase_range_p(CX* self, CX##_value_t* first, CX##_value_t* finish); \

+    CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2); \

 \

     STC_INLINE CX##_iter_t \

-    CX##_erase_range(CX* self, CX##_iter_t first, CX##_iter_t finish) { \

-        return CX##_erase_range_p(self, first.ref, finish.ref); \

+    CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \

+        return CX##_erase_range_p(self, it1.ref, it2.ref); \

     } \

     STC_INLINE CX##_iter_t \

     CX##_erase_it(CX* self, CX##_iter_t it) { \

@@ -166,7 +163,7 @@ typedef int (*c_cmp_fn)(const void*, const void*);
     CX##_index(CX deq, CX##_iter_t it) {return it.ref - deq.data;} \

 \

     STC_API CX##_iter_t \

-    CX##_find_in(CX##_iter_t first, CX##_iter_t finish, RawValue raw); \

+    CX##_find_in(CX##_iter_t p1, CX##_iter_t p2, RawValue raw); \

     STC_INLINE CX##_iter_t \

     CX##_find(const CX* self, RawValue raw) { \

         return CX##_find_in(CX##_begin(self), CX##_end(self), raw); \

@@ -276,14 +273,14 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
     CX##_clone(CX deq) { \

         size_t len = cdeq_rep_(&deq)->size; \

         CX out = CX##_with_capacity(len); \

-        CX##_insert_range_p(&out, out.data, deq.data, deq.data + len); \

+        CX##_insert_range_p(&out, out.data, deq.data, deq.data + len, true); \

         return out; \

     } \

 \

     STC_DEF CX##_iter_t \

     CX##_insert_range_p(CX* self, CX##_value_t* pos, \

-                              const CX##_value_t* first, const CX##_value_t* finish) { \

-        size_t n = finish - first, idx = pos - self->data, size = cdeq_rep_(self)->size; \

+                        const CX##_value_t* p1, const CX##_value_t* p2, bool clone) { \

+        size_t n = p2 - p1, idx = pos - self->data, size = cdeq_rep_(self)->size; \

         bool at_front = (idx*2 < size); \

         CX##_expand_(self, n, at_front); \

         if (at_front) { \

@@ -295,22 +292,21 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
         } \

         CX##_iter_t it = {pos}; \

         if (n) cdeq_rep_(self)->size += n; \

-        while (first != finish) \

-            *pos++ = valueFromRaw(valueToRaw(first++)); \

+        if (clone) while (p1 != p2) *pos++ = valueFromRaw(valueToRaw(p1++)); \

         return it; \

     } \

 \

     STC_DEF CX##_iter_t \

-    CX##_erase_range_p(CX* self, CX##_value_t* first, CX##_value_t* finish) { \

-        intptr_t len = finish - first; \

+    CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2) { \

+        intptr_t len = p2 - p1; \

         if (len > 0) { \

-            CX##_value_t* p = first, *end = self->data + cdeq_rep_(self)->size; \

-            while (p != finish) valueDel(p++); \

-            if (first == self->data) self->data += len; \

-            else memmove(first, finish, (end - finish) * sizeof(Value)); \

+            CX##_value_t* p = p1, *end = self->data + cdeq_rep_(self)->size; \

+            while (p != p2) valueDel(p++); \

+            if (p1 == self->data) self->data += len; \

+            else memmove(p1, p2, (end - p2) * sizeof(Value)); \

             cdeq_rep_(self)->size -= len; \

         } \

-        CX##_iter_t it = {first}; return it; \

+        CX##_iter_t it = {p1}; return it; \

     } \

 \

     STC_DEF CX##_iter_t \

diff --git a/stc/cmap.h b/stc/cmap.h
index ed1da3d9..fdfe08ee 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -295,7 +295,8 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored)
     STC_INLINE CX##_iter_t \

     CX##_erase_it(CX* self, CX##_iter_t it) { \

         CX##_erase_entry(self, it.ref); \

-        CX##_next(&it); return it; \

+        if (*it._hx == 0) CX##_next(&it); \

+        return it; \

     } \

 \

     _c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \

diff --git a/stc/csmap.h b/stc/csmap.h
index 6b58c6a3..74c6fd39 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -421,20 +421,20 @@ static struct csmap_rep _csmap_inits = {0, 0, 0, 0};
 \

     static inline CX##_size_t \

     CX##_insert_entry_i_(CX* self, CX##_size_t tn, const CX##_rawkey_t* rkey, CX##_result_t* res) { \

-        CX##_size_t up[64], it = tn; \

+        CX##_size_t up[64], tx = tn; \

         CX##_node_t* d = self->nodes; \

         int c, top = 0, dir = 0; \

-        while (it) { \

-            up[top++] = it; \

-            RawKey raw = keyToRaw(KEY_REF_##C(&d[it].value)); \

-            if ((c = keyCompareRaw(&raw, rkey)) == 0) {res->ref = &d[it].value; return tn;} \

+        while (tx) { \

+            up[top++] = tx; \

+            RawKey raw = keyToRaw(KEY_REF_##C(&d[tx].value)); \

+            if ((c = keyCompareRaw(&raw, rkey)) == 0) {res->ref = &d[tx].value; return tn;} \

             dir = (c == -1); \

-            it = d[it].link[dir]; \

+            tx = d[tx].link[dir]; \

         } \

-        it = CX##_node_new_(self, 1); d = self->nodes; \

-        res->ref = &d[it].value, res->inserted = true; \

-        if (top == 0) return it; \

-        d[up[top - 1]].link[dir] = it; \

+        tx = CX##_node_new_(self, 1); d = self->nodes; \

+        res->ref = &d[tx].value, res->inserted = true; \

+        if (top == 0) return tx; \

+        d[up[top - 1]].link[dir] = tx; \

         while (top--) { \

             if (top) dir = (d[up[top - 1]].link[1] == up[top]); \

             up[top] = CX##_skew_(d, up[top]); \

diff --git a/stc/cvec.h b/stc/cvec.h
index e938195b..b378be0f 100644
--- a/stc/cvec.h
+++ b/stc/cvec.h
@@ -100,32 +100,28 @@ typedef int (*c_cmp_fn)(const void*, const void*);
         return valueFromRaw(valueToRaw(&val)); \

     } \

 \

-    STC_API CX##_iter_t \

-    CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* pfirst, const CX##_value_t* pfinish); \

-\

-    STC_INLINE CX##_iter_t \

-    CX##_insert_range(CX* self, CX##_iter_t it, CX##_iter_t it1, CX##_iter_t it2) { \

-        return CX##_insert_range_p(self, it.ref, it1.ref, it2.ref); \

-    } \

+    STC_API CX##_iter_t CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* p1, \

+                                                                         const CX##_value_t* p2, bool clone); \

     STC_INLINE CX##_iter_t \

     CX##_insert(CX* self, CX##_iter_t it, Value value) { \

-        return CX##_insert_range_p(self, it.ref, &value, &value + 1); \

-    } \

-    STC_INLINE CX##_iter_t \

-    CX##_insert_at(CX* self, size_t idx, Value value) { \

-        return CX##_insert_range_p(self, self->data + idx, &value, &value + 1); \

+        it = CX##_insert_range_p(self, it.ref, &value, &value + 1, false); \

+        *it.ref = value; return it; \

     } \

     STC_INLINE CX##_iter_t \

     CX##_emplace(CX* self, CX##_iter_t it, RawValue raw) { \

         return CX##_insert(self, it, valueFromRaw(raw)); \

     } \

     STC_INLINE CX##_iter_t \

-    CX##_emplace_at(CX* self, size_t idx, RawValue raw) { \

-        return CX##_insert_at(self, idx, valueFromRaw(raw)); \

+    CX##_insert_range(CX* self, CX##_iter_t it, CX##_iter_t it1, CX##_iter_t it2) { \

+        return CX##_insert_range_p(self, it.ref, it1.ref, it2.ref, true); \

+    } \

+    STC_INLINE CX##_iter_t \

+    CX##_insert_at(CX* self, size_t idx, const CX##_value_t arr[], size_t n) { \

+        return CX##_insert_range_p(self, self->data + idx, arr, arr + n, true); \

     } \

 \

     STC_API CX##_iter_t \

-    CX##_erase_range_p(CX* self, CX##_value_t* first, CX##_value_t* finish); \

+    CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2); \

 \

     STC_INLINE CX##_iter_t \

     CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \

@@ -261,13 +257,14 @@ static struct cvec_rep _cvec_inits = {0, 0};
     CX##_clone(CX vec) { \

         size_t len = _cvec_rep(&vec)->size; \

         CX out = CX##_with_capacity(len); \

-        CX##_insert_range_p(&out, out.data, vec.data, vec.data + len); \

+        CX##_insert_range_p(&out, out.data, vec.data, vec.data + len, true); \

         return out; \

     } \

 \

     STC_DEF CX##_iter_t \

-    CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* first, const CX##_value_t* finish) { \

-        size_t len = finish - first, idx = pos - self->data, size = _cvec_rep(self)->size; \

+    CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* p1, \

+                                                     const CX##_value_t* p2, bool clone) { \

+        size_t len = p2 - p1, idx = pos - self->data, size = _cvec_rep(self)->size; \

         CX##_iter_t it = {pos}; \

         if (len == 0) return it; \

         if (size + len > CX##_capacity(*self)) \

@@ -275,21 +272,20 @@ static struct cvec_rep _cvec_inits = {0, 0};
             it.ref = pos = self->data + idx; \

         _cvec_rep(self)->size += len; \

         memmove(pos + len, pos, (size - idx) * sizeof(Value)); \

-        while (first != finish) \

-            *pos++ = valueFromRaw(valueToRaw(first++)); \

+        if (clone) while (p1 != p2) *pos++ = valueFromRaw(valueToRaw(p1++)); \

         return it; \

     } \

 \

     STC_DEF CX##_iter_t \

-    CX##_erase_range_p(CX* self, CX##_value_t* first, CX##_value_t* finish) { \

-        intptr_t len = finish - first; \

+    CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2) { \

+        intptr_t len = p2 - p1; \

         if (len > 0) { \

-            CX##_value_t* p = first, *end = self->data + _cvec_rep(self)->size; \

-            while (p != finish) valueDel(p++); \

-            memmove(first, finish, (end - finish) * sizeof(Value)); \

+            CX##_value_t* p = p1, *end = self->data + _cvec_rep(self)->size; \

+            while (p != p2) valueDel(p++); \

+            memmove(p1, p2, (end - p2) * sizeof(Value)); \

             _cvec_rep(self)->size -= len; \

         } \

-        CX##_iter_t it = {first}; return it; \

+        CX##_iter_t it = {p1}; return it; \

     } \

 \

     STC_DEF CX##_iter_t \