Renamed cflist.h to clist, because it is not like std::forward_list which misses pushBack().

3 files changed, 398 insertions, 343 deletions

diff --git a/demos.c b/demos.c
index 82505241..c4052eb8 100644
--- a/demos.c
+++ b/demos.c
@@ -1,9 +1,12 @@
 #include "stc/cstring.h"
 #include "stc/cvector.h"
+#include "stc/clist.h"
 #include "stc/cmap.h"
 
 
-void stringdemo() {
+void stringdemo1()
+{
+    printf("STRINGDEMO1\n");
     CString cs = cstring_make("one-nine-three-seven-five");
     printf("%s.\n", cs.str);
 
@@ -31,7 +34,9 @@ void stringdemo() {
 
 declare_CVector(ix, int64_t); // ix is just an example tag name.
 
-void vectordemo() {
+void vectordemo1()
+{
+    printf("VECTORDEMO1\n");
     CVector_ix bignums = cvector_init; // = (CVector_ix) cvector_init; if initializing after declaration.
     cvector_ix_reserve(&bignums, 100);
     for (size_t i = 0; i<100; ++i)
@@ -48,24 +53,49 @@ void vectordemo() {
 
 declare_CVector(cs, CString, cstring_destroy, cstring_compare); // supply inline destructor of values
 
-void stringvectordemo() {
+void vectordemo2()
+{
+    printf("VECTORDEMO2\n");
     CVector_cs names = cvector_init;
     cvector_cs_pushBack(&names, cstring_make("Mary"));
     cvector_cs_pushBack(&names, cstring_make("Joe"));
     cvector_cs_pushBack(&names, cstring_make("Chris"));
-    cstring_assign(&names.data[1], "Anna");      // replace Joe
+    cstring_assign(&names.data[1], "Jane");      // replace Joe
     printf("names[1]: %s\n", names.data[1].str);
 
     cvector_cs_sort(&names);                     // Sort the array
     c_foreach (i, cvector_cs, names)
-        printf("name: %s\n", i.item->str);
+        printf("sorted: %s\n", i.item->str);
     cvector_cs_destroy(&names);
 }
 
+declare_CList(ix, int); 
+
+void listdemo1()
+{
+    printf("LISTDEMO1\n");
+    CList_ix nums = clist_init;
+    clist_ix_pushBack(&nums, 123);
+    clist_ix_pushBack(&nums, 231);
+    clist_ix_pushBack(&nums, 444);
+    clist_ix_pushBack(&nums, 321);
+    *clist_ix_find(&nums, 231) = 1000;
+    c_foreach (i, clist_ix, nums)
+        printf("value: %d\n", i.item->value);    
+    clist_ix_sort(&nums);                     // Sort the array
+    clist_ix_remove(&nums, 123);
+    c_foreach (i, clist_ix, nums)
+        printf("sorted: %d\n", i.item->value);
+
+    clist_ix_destroy(&nums);
+}
+
 
 declare_CMap(ii, int, int);
 
-void mapdemo() {
+void mapdemo1()
+{
+    printf("MAPDEMO1\n");
     CMap_ii nums = cmap_init;
     cmap_ii_put(&nums, 8, 64);
     cmap_ii_put(&nums, 11, 121);
@@ -78,7 +108,9 @@ void mapdemo() {
 
 declare_CMap_stringkey(si, int); // Shorthand macro for the general declare_CMap expansion.
 
-void stringmapdemo() {
+void mapdemo2()
+{
+    printf("MAPDEMO2\n");
     CMap_si nums = cmap_init;
     cmap_si_put(&nums, "Hello", 64);
     cmap_si_put(&nums, "Groovy", 121);
@@ -86,11 +118,11 @@ void stringmapdemo() {
 
     // iterate the map:
     for (cmap_si_iter_t i = cmap_si_begin(&nums); i.item; i = cmap_si_next(i))
-        printf("%s: %d\n", i.item->key.str, i.item->value);
+        printf("long: %s: %d\n", i.item->key.str, i.item->value);
 
     // or rather use the short form:
     c_foreach (i, cmap_si, nums)
-        printf("%s: %d\n", i.item->key.str, i.item->value);
+        printf("short: %s: %d\n", i.item->key.str, i.item->value);
 
     cmap_si_destroy(&nums);
 }
@@ -98,14 +130,19 @@ void stringmapdemo() {
 
 declare_CMap_stringkey(ss, CString, cstring_destroy); 
 
-void stringmapdemo2() {
+void mapdemo3()
+{
+    printf("MAPDEMO3\n");
     CMap_ss table = cmap_init;
+    cmap_ss_put(&table, "Map", cstring_make("test"));
     cmap_ss_put(&table, "Make", cstring_make("my"));
     cmap_ss_put(&table, "Sunny", cstring_make("day"));
-    printf("Sunny: %s\n", cmap_ss_get(table, "Sunny")->value.str);
+    printf("remove: Make: %s\n", cmap_ss_get(table, "Make")->value.str);
     cmap_ss_erase(&table, "Make");
 
     printf("size %d\n", cmap_size(table));
+    c_foreach (i, cmap_ss, table)
+        printf("key: %s\n", i.item->key.str);
     cmap_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector).
 }
 
@@ -113,10 +150,11 @@ void stringmapdemo2() {
 
 int main()
 {
-    stringdemo();
-    vectordemo();
-    stringvectordemo();
-    mapdemo();
-    stringmapdemo();
-    stringmapdemo2();
+    stringdemo1();
+    vectordemo1();
+    vectordemo2();
+    listdemo1();
+    mapdemo1();
+    mapdemo2();
+    mapdemo3();
 }
diff --git a/stc/cflist.h b/stc/cflist.h
deleted file mode 100644
index 81a56a23..00000000
--- a/stc/cflist.h
+++ /dev/null
@@ -1,326 +0,0 @@
-/* MIT License
- *
- * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in all
- * copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-#ifndef CFLIST__H__
-#define CFLIST__H__
-
-#include "cdefs.h"
-
-/*  Circular Singly-linked Lists.
-    
-    This implements a std::forward_list-like class (hence the name),
-    but because it is circular, it also support push and splice at
-    both ends of the list. This makes it ideal to be used as a queue, 
-    unlike forward_list. As with forward_list, it supports popFront
-    and eraseAfter. Basic usage is very similar to CVector:
-   
-    #include "stc/cflist.h"
-    #omclude "stc/cstring.h"
-    declare_CFList(i, int64_t);
-    declare_CFList_string(s);
- 
-    int main() {
-        CFList_i list = cflist_init;
-        CFList_s slist = cflist_init;
-        int n;
-
-        // Add one million random numbers...
-        for (int i=0; i<1000000; ++i)
-            cflist_i_pushBack(&list, rand() * rand());
-        n = 0; 
-        c_foreach (i, cflist_i, list)
-            if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value);
-        // Sort them...
-        cflist_i_sort(&list); // mergesort O(n*log n)
-        n = 0;
-        c_foreach (i, cflist_i, list)
-            if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value);
-        cflist_i_destroy(&list);
-
-        // Test CFList with CStrings 
-        cflist_s_pushBack(&slist, cstring_make("Item 1"));
-        cflist_s_pushBack(&slist, cstring_make("Item 2"));
-        cflist_s_pushBack(&slist, cstring_make("Item X"));
-        cflist_s_pushBack(&slist, cstring_make("Item 3"));
-        printf("\n");
-        c_foreach (i, cflist_s, slist)
-            printf("%s\n", i.item->value.str);
-        // Change the list...
-        cflist_s_pushFront(&slist, cstring_make("Item 0"));
-        cflist_s_remove(&slist, "Item X");
-        printf("\n");
-        c_foreach (i, cflist_s, slist)
-            printf("%s\n", i.item->value.str);
-        cflist_s_destroy(&slist);
-    }
- */
-
-#define declare_CFList(...)    c_MACRO_OVERLOAD(declare_CFList, __VA_ARGS__)
-
-#define declare_CFList_2(tag, Value) \
-                               declare_CFList_3(tag, Value, c_noDestroy)
-#define declare_CFList_3(tag, Value, valueDestroy) \
-                               declare_CFList_4(tag, Value, valueDestroy, c_defaultCompare)
-#define declare_CFList_4(tag, Value, valueDestroy, valueCompare) \
-                               declare_CFList_6(tag, Value, valueDestroy, Value, valueCompare, c_defaultGetRaw)
-#define declare_CFList_string(tag) \
-                               declare_CFList_6(tag, CString, cstring_destroy, const char*, cstring_compareRaw, cstring_getRaw)                            
-
-#define declare_CFListTypes(tag, Value) \
-    c_struct (CFListNode_##tag) { \
-        CFListNode_##tag *next; \
-        Value value; \
-    }; \
- \
-    c_struct (CFList_##tag) { \
-        CFListNode_##tag* last; \
-    }; \
- \
-    c_struct (cflist_##tag##_iter_t) { \
-        CFListNode_##tag *item, **_last; \
-    }
-
-#define cflist_init          {NULL}
-#define cflist_front(list)   (list).last->next->value
-#define cflist_back(list)    (list).last->value
-#define cflist_empty(list)   ((list).last == NULL)
-
-
-#define declare_CFList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
- \
-    declare_CFListTypes(tag, Value); \
-    typedef ValueRaw cflist_##tag##_raw_t; \
- \
-    STC_API void \
-    cflist_##tag##_destroy(CFList_##tag* self); \
- \
-    STC_API void \
-    cflist_##tag##_pushFront(CFList_##tag* self, Value value); \
- \
-    STC_API void \
-    cflist_##tag##_popFront(CFList_##tag* self); \
- \
-    STC_API void \
-    cflist_##tag##_pushBack(CFList_##tag* self, Value value); \
- \
-    STC_API void \
-    cflist_##tag##_insertAfter(CFList_##tag* self, cflist_##tag##_iter_t pos, Value value); \
- \
-    STC_API void \
-    cflist_##tag##_eraseAfter(CFList_##tag* self, cflist_##tag##_iter_t pos); \
- \
-    STC_API void \
-    cflist_##tag##_spliceFront(CFList_##tag* self, CFList_##tag* other); \
- \
-    STC_API void \
-    cflist_##tag##_spliceAfter(CFList_##tag* self, cflist_##tag##_iter_t pos, CFList_##tag* other); \
- \
-    STC_API int \
-    cflist_##tag##_remove(CFList_##tag* self, ValueRaw val); \
- \
-    STC_API void \
-    cflist_##tag##_sort(CFList_##tag* self); \
- \
-    static inline cflist_##tag##_iter_t \
-    cflist_##tag##_begin(CFList_##tag* lst) { \
-        CFListNode_##tag *head = lst->last ? lst->last->next : NULL; \
-        cflist_##tag##_iter_t it = {head, &lst->last}; return it; \
-    } \
-    static inline cflist_##tag##_iter_t \
-    cflist_##tag##_next(cflist_##tag##_iter_t it) { \
-        it.item = it.item == *it._last ? NULL : it.item->next; return it; \
-    } \
-    static inline cflist_##tag##_iter_t \
-    cflist_##tag##_last(CFList_##tag* lst) { \
-        cflist_##tag##_iter_t it = {lst->last, &lst->last}; return it; \
-    } \
- \
-    implement_CFList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
- \
-    typedef Value cflist_##tag##_value_t
-
-    
-/* -------------------------- IMPLEMENTATION ------------------------- */
-
-#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
-#define implement_CFList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
- \
-    STC_API void \
-    cflist_##tag##_destroy(CFList_##tag* self) { \
-        while (self->last) \
-            cflist_##tag##_popFront(self); \
-    } \
- \
-    STC_API void \
-    cflist_##tag##_pushFront(CFList_##tag* self, Value value) { \
-        _cflist_insertAfter(tag, self->last, value); \
-        if (!self->last) self->last = entry; \
-    } \
-    STC_API void \
-    cflist_##tag##_popFront(CFList_##tag* self) { \
-        _cflist_eraseAfter(tag, self->last, valueDestroy); \
-    } \
- \
-    STC_API void \
-    cflist_##tag##_pushBack(CFList_##tag* self, Value value) { \
-        _cflist_insertAfter(tag, self->last, value); \
-        self->last = entry; \
-    } \
- \
-    STC_API void \
-    cflist_##tag##_insertAfter(CFList_##tag* self, cflist_##tag##_iter_t pos, Value value) { \
-        _cflist_insertAfter(tag, pos.item, value); \
-        if (!self->last || pos.item == self->last) self->last = entry; \
-    } \
- \
-    STC_API void \
-    cflist_##tag##_eraseAfter(CFList_##tag* self, cflist_##tag##_iter_t pos) { \
-        _cflist_eraseAfter(tag, pos.item, valueDestroy); \
-    } \
- \
-    static inline void \
-    _cflist_##tag##_splice(CFList_##tag* self, cflist_##tag##_iter_t pos, CFList_##tag* other, bool bottom) { \
-        if (!pos.item) \
-            self->last = pos.item = other->last; \
-        else if (other->last) { \
-            CFListNode_##tag *next = pos.item->next; \
-            pos.item->next = other->last->next; \
-            other->last->next = next; \
-            if (bottom && pos.item == self->last) self->last = other->last; \
-        } \
-        other->last = NULL; \
-    } \
-    STC_API void \
-    cflist_##tag##_spliceFront(CFList_##tag* self, CFList_##tag* other) { \
-        _cflist_##tag##_splice(self, cflist_##tag##_last(self), other, false); \
-    } \
-    STC_API void \
-    cflist_##tag##_spliceAfter(CFList_##tag* self, cflist_##tag##_iter_t pos, CFList_##tag* other) { \
-        _cflist_##tag##_splice(self, pos, other, true); \
-    } \
- \
-    STC_API int \
-    cflist_##tag##_remove(CFList_##tag* self, ValueRaw val) { \
-        cflist_##tag##_iter_t prev = {self->last}; int n = 0; \
-        ValueRaw r; \
-        c_foreach (i, cflist_##tag, *self) { \
-            if (valueCompareRaw((r = valueGetRaw(&i.item->value), &r), &val) == 0) { \
-                cflist_##tag##_eraseAfter(self, prev), ++n; \
-                if (prev.item == i.item) break; \
-            } \
-            prev = i; \
-        } \
-        return n; \
-    } \
- \
-    static inline int \
-    cflist_##tag##_sortCmp(const void* x, const void* y) { \
-        ValueRaw a = valueGetRaw(&((CFListNode_##tag *) x)->value); \
-        ValueRaw b = valueGetRaw(&((CFListNode_##tag *) y)->value); \
-        return valueCompareRaw(&a, &b); \
-    } \
-    STC_API void \
-    cflist_##tag##_sort(CFList_##tag* self) { \
-        CFListNode__base* last = _cflist_mergesort((CFListNode__base *) self->last, cflist_##tag##_sortCmp); \
-        self->last = (CFListNode_##tag *) last; \
-    }
-
-#define _cflist_insertAfter(tag, node, val) \
-    CFListNode_##tag *entry = c_new_1(CFListNode_##tag), \
-                       *next = self->last ? node->next : entry; \
-    entry->value = val; \
-    entry->next = next; \
-    if (node) node->next = entry
-    /* +: set self->last based on node */
-
-#define _cflist_eraseAfter(tag, node, valueDestroy) \
-    CFListNode_##tag* del = node->next, *next = del->next; \
-    node->next = next; \
-    if (del == next) self->last = NULL; \
-    else if (self->last == del) self->last = node; \
-    valueDestroy(&del->value); \
-    free(del)
-
-declare_CFListTypes(_base, int);
-
-/* Singly linked list Mergesort implementation by Simon Tatham. O(n*log(n)).
- * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
- */
-static inline CFListNode__base *
-_cflist_mergesort(CFListNode__base *list, int (*cmp)(const void*, const void*)) {
-    CFListNode__base *p, *q, *e, *tail, *oldhead;
-    int insize = 1, nmerges, psize, qsize, i;
-    if (!list) return NULL;
-    
-    while (1) {
-        p = list;
-        oldhead = list;
-        list = tail = NULL;
-        nmerges = 0;
-
-        while (p) {
-            ++nmerges;
-            q = p;
-            psize = 0;
-            for (i = 0; i < insize; ++i) {
-                ++psize;
-                q = (q->next == oldhead ? NULL : q->next);
-                if (!q) break;
-            }
-            qsize = insize;
-
-            while (psize > 0 || (qsize > 0 && q)) {
-                if (psize == 0) {
-                    e = q; q = q->next; --qsize;
-                    if (q == oldhead) q = NULL;
-                } else if (qsize == 0 || !q) {
-                    e = p; p = p->next; --psize;
-                    if (p == oldhead) p = NULL;
-                } else if (cmp(p, q) <= 0) {
-                    e = p; p = p->next; --psize;
-                    if (p == oldhead) p = NULL;
-                } else {
-                    e = q; q = q->next; --qsize;
-                    if (q == oldhead) q = NULL;
-                }
-                if (tail)
-                    tail->next = e;
-                else
-                    list = e;
-                tail = e;
-            }
-            p = q;
-        }
-        tail->next = list;
-
-        if (nmerges <= 1)
-            return tail;
-
-        insize *= 2;
-    }
-}
-
-#else
-#define implement_CFList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw)
-#endif
-
-#endif
diff --git a/stc/clist.h b/stc/clist.h
new file mode 100644
index 00000000..5fdb3b28
--- /dev/null
+++ b/stc/clist.h
@@ -0,0 +1,343 @@
+/* MIT License
+ *
+ * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#ifndef CLIST__H__
+#define CLIST__H__
+
+#include "cdefs.h"
+
+/*  Circular Singly-linked Lists.
+    
+    This implements a std::forward_list-like class in C, but because it is circular,
+    it also support push* and splice* at both ends of the list. This makes it ideal
+    for being used as a queue, unlike std::forward_list's push_front/pop_front only.
+    Basic usage is similar to CVector:
+   
+    #include "stc/clist.h"
+    #omclude "stc/cstring.h"
+    declare_CList(i, int64_t);
+    declare_CList_string(s);
+ 
+    int main() {
+        CList_i list = clist_init;
+        CList_s slist = clist_init;
+        int n;
+
+        // Add one million random numbers...
+        for (int i=0; i<1000000; ++i)
+            clist_i_pushBack(&list, rand() * rand());
+        n = 0; 
+        c_foreach (i, clist_i, list)
+            if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value);
+        // Sort them...
+        clist_i_sort(&list); // mergesort O(n*log n)
+        n = 0;
+        c_foreach (i, clist_i, list)
+            if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value);
+        clist_i_destroy(&list);
+
+        // Test CList with CStrings 
+        clist_s_pushBack(&slist, cstring_make("Item 1"));
+        clist_s_pushBack(&slist, cstring_make("Item 2"));
+        clist_s_pushBack(&slist, cstring_make("Item X"));
+        clist_s_pushBack(&slist, cstring_make("Item 3"));
+        printf("\n");
+        c_foreach (i, clist_s, slist)
+            printf("%s\n", i.item->value.str);
+        // Change the list...
+        clist_s_pushFront(&slist, cstring_make("Item 0"));
+        clist_s_remove(&slist, "Item X");
+        printf("\n");
+        c_foreach (i, clist_s, slist)
+            printf("%s\n", i.item->value.str);
+        clist_s_destroy(&slist);
+    }
+ */
+
+#define declare_CList(...)    c_MACRO_OVERLOAD(declare_CList, __VA_ARGS__)
+
+#define declare_CList_2(tag, Value) \
+                               declare_CList_3(tag, Value, c_noDestroy)
+#define declare_CList_3(tag, Value, valueDestroy) \
+                               declare_CList_4(tag, Value, valueDestroy, c_defaultCompare)
+#define declare_CList_4(tag, Value, valueDestroy, valueCompare) \
+                               declare_CList_6(tag, Value, valueDestroy, Value, valueCompare, c_defaultGetRaw)
+#define declare_CList_string(tag) \
+                               declare_CList_6(tag, CString, cstring_destroy, const char*, cstring_compareRaw, cstring_getRaw)                            
+
+#define declare_CListTypes(tag, Value) \
+    c_struct (CListNode_##tag) { \
+        CListNode_##tag *next; \
+        Value value; \
+    }; \
+ \
+    c_struct (CList_##tag) { \
+        CListNode_##tag* last; \
+    }; \
+ \
+    c_struct (clist_##tag##_iter_t) { \
+        CListNode_##tag *item, **_last; \
+    }
+
+#define clist_init          {NULL}
+#define clist_front(list)   (list).last->next->value
+#define clist_back(list)    (list).last->value
+#define clist_empty(list)   ((list).last == NULL)
+
+
+#define declare_CList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
+ \
+    declare_CListTypes(tag, Value); \
+    typedef ValueRaw clist_##tag##_raw_t; \
+ \
+    STC_API void \
+    clist_##tag##_destroy(CList_##tag* self); \
+ \
+    STC_API void \
+    clist_##tag##_pushFront(CList_##tag* self, Value value); \
+ \
+    STC_API void \
+    clist_##tag##_popFront(CList_##tag* self); \
+ \
+    STC_API void \
+    clist_##tag##_pushBack(CList_##tag* self, Value value); \
+ \
+    STC_API void \
+    clist_##tag##_insertAfter(CList_##tag* self, clist_##tag##_iter_t pos, Value value); \
+ \
+    STC_API void \
+    clist_##tag##_eraseAfter(CList_##tag* self, clist_##tag##_iter_t pos); \
+ \
+    STC_API void \
+    clist_##tag##_spliceFront(CList_##tag* self, CList_##tag* other); \
+ \
+    STC_API void \
+    clist_##tag##_spliceAfter(CList_##tag* self, clist_##tag##_iter_t pos, CList_##tag* other); \
+ \
+    STC_API clist_##tag##_iter_t \
+    clist_##tag##_findBefore(CList_##tag* self, ValueRaw val); \
+ \
+    STC_API Value* \
+    clist_##tag##_find(CList_##tag* self, ValueRaw val); \
+ \
+    STC_API clist_##tag##_iter_t \
+    clist_##tag##_remove(CList_##tag* self, ValueRaw val); \
+ \
+    STC_API void \
+    clist_##tag##_sort(CList_##tag* self); \
+ \
+    static inline clist_##tag##_iter_t \
+    clist_##tag##_begin(CList_##tag* self) { \
+        CListNode_##tag *head = self->last ? self->last->next : NULL; \
+        clist_##tag##_iter_t it = {head, &self->last}; return it; \
+    } \
+    static inline clist_##tag##_iter_t \
+    clist_##tag##_next(clist_##tag##_iter_t it) { \
+        it.item = it.item == *it._last ? NULL : it.item->next; return it; \
+    } \
+    static inline clist_##tag##_iter_t \
+    clist_##tag##_last(CList_##tag* self) { \
+        clist_##tag##_iter_t it = {self->last, &self->last}; return it; \
+    } \
+ \
+    implement_CList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
+ \
+    typedef Value clist_##tag##_value_t
+
+    
+/* -------------------------- IMPLEMENTATION ------------------------- */
+
+#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
+#define implement_CList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw) \
+ \
+    STC_API void \
+    clist_##tag##_destroy(CList_##tag* self) { \
+        while (self->last) \
+            clist_##tag##_popFront(self); \
+    } \
+ \
+    STC_API void \
+    clist_##tag##_pushFront(CList_##tag* self, Value value) { \
+        _clist_insertAfter(self, tag, self->last, value); \
+        if (!self->last) self->last = entry; \
+    } \
+    STC_API void \
+    clist_##tag##_popFront(CList_##tag* self) { \
+        _clist_eraseAfter(self, tag, self->last, valueDestroy); \
+    } \
+ \
+    STC_API void \
+    clist_##tag##_pushBack(CList_##tag* self, Value value) { \
+        _clist_insertAfter(self, tag, self->last, value); \
+        self->last = entry; \
+    } \
+ \
+    STC_API void \
+    clist_##tag##_insertAfter(CList_##tag* self, clist_##tag##_iter_t pos, Value value) { \
+        _clist_insertAfter(self, tag, pos.item, value); \
+        if (!self->last || pos.item == self->last) self->last = entry; \
+    } \
+ \
+    STC_API void \
+    clist_##tag##_eraseAfter(CList_##tag* self, clist_##tag##_iter_t pos) { \
+        _clist_eraseAfter(self, tag, pos.item, valueDestroy); \
+    } \
+ \
+    static inline void \
+    _clist_##tag##_splice(CList_##tag* self, clist_##tag##_iter_t pos, CList_##tag* other, bool bottom) { \
+        if (!pos.item) \
+            self->last = pos.item = other->last; \
+        else if (other->last) { \
+            CListNode_##tag *next = pos.item->next; \
+            pos.item->next = other->last->next; \
+            other->last->next = next; \
+            if (bottom && pos.item == self->last) self->last = other->last; \
+        } \
+        other->last = NULL; \
+    } \
+    STC_API void \
+    clist_##tag##_spliceFront(CList_##tag* self, CList_##tag* other) { \
+        _clist_##tag##_splice(self, clist_##tag##_last(self), other, false); \
+    } \
+    STC_API void \
+    clist_##tag##_spliceAfter(CList_##tag* self, clist_##tag##_iter_t pos, CList_##tag* other) { \
+        _clist_##tag##_splice(self, pos, other, true); \
+    } \
+ \
+    STC_API clist_##tag##_iter_t \
+    clist_##tag##_findBefore(CList_##tag* self, ValueRaw val) { \
+        clist_##tag##_iter_t prev = {self->last, &self->last}; \
+        c_foreach (i, clist_##tag, *self) { \
+            ValueRaw r = valueGetRaw(&i.item->value); \
+            if (valueCompareRaw(&r, &val) == 0) { \
+                return prev; \
+            } \
+            prev = i; \
+        } \
+        prev.item = NULL; return prev; \
+    } \
+ \
+    STC_API Value* \
+    clist_##tag##_find(CList_##tag* self, ValueRaw val) { \
+        clist_##tag##_iter_t it = clist_##tag##_findBefore(self, val); \
+        return it.item ? &it.item->next->value : NULL; \
+    } \
+ \
+    STC_API clist_##tag##_iter_t \
+    clist_##tag##_remove(CList_##tag* self, ValueRaw val) { \
+        clist_##tag##_iter_t it = clist_##tag##_findBefore(self, val); \
+        if (it.item) clist_##tag##_eraseAfter(self, it); \
+        return it; \
+    } \
+ \
+    static inline int \
+    clist_##tag##_sortCmp(const void* x, const void* y) { \
+        ValueRaw a = valueGetRaw(&((CListNode_##tag *) x)->value); \
+        ValueRaw b = valueGetRaw(&((CListNode_##tag *) y)->value); \
+        return valueCompareRaw(&a, &b); \
+    } \
+    STC_API void \
+    clist_##tag##_sort(CList_##tag* self) { \
+        CListNode__base* last = _clist_mergesort((CListNode__base *) self->last, clist_##tag##_sortCmp); \
+        self->last = (CListNode_##tag *) last; \
+    }
+
+#define _clist_insertAfter(self, tag, node, val) \
+    CListNode_##tag *entry = c_new_1(CListNode_##tag), \
+                    *next = self->last ? node->next : entry; \
+    entry->value = val; \
+    entry->next = next; \
+    if (node) node->next = entry
+    /* +: set self->last based on node */
+
+#define _clist_eraseAfter(self, tag, node, valueDestroy) \
+    CListNode_##tag* del = node->next, *next = del->next; \
+    node->next = next; \
+    if (del == next) self->last = NULL; \
+    else if (self->last == del) self->last = node; \
+    valueDestroy(&del->value); \
+    free(del)
+
+declare_CListTypes(_base, int);
+
+/* Singly linked list Mergesort implementation by Simon Tatham. O(n*log n).
+ * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+ */
+static inline CListNode__base *
+_clist_mergesort(CListNode__base *list, int (*cmp)(const void*, const void*)) {
+    CListNode__base *p, *q, *e, *tail, *oldhead;
+    int insize = 1, nmerges, psize, qsize, i;
+    if (!list) return NULL;
+    
+    while (1) {
+        p = list;
+        oldhead = list;
+        list = tail = NULL;
+        nmerges = 0;
+
+        while (p) {
+            ++nmerges;
+            q = p;
+            psize = 0;
+            for (i = 0; i < insize; ++i) {
+                ++psize;
+                q = (q->next == oldhead ? NULL : q->next);
+                if (!q) break;
+            }
+            qsize = insize;
+
+            while (psize > 0 || (qsize > 0 && q)) {
+                if (psize == 0) {
+                    e = q; q = q->next; --qsize;
+                    if (q == oldhead) q = NULL;
+                } else if (qsize == 0 || !q) {
+                    e = p; p = p->next; --psize;
+                    if (p == oldhead) p = NULL;
+                } else if (cmp(p, q) <= 0) {
+                    e = p; p = p->next; --psize;
+                    if (p == oldhead) p = NULL;
+                } else {
+                    e = q; q = q->next; --qsize;
+                    if (q == oldhead) q = NULL;
+                }
+                if (tail)
+                    tail->next = e;
+                else
+                    list = e;
+                tail = e;
+            }
+            p = q;
+        }
+        tail->next = list;
+
+        if (nmerges <= 1)
+            return tail;
+
+        insize *= 2;
+    }
+}
+
+#else
+#define implement_CList_6(tag, Value, valueDestroy, ValueRaw, valueCompareRaw, valueGetRaw)
+#endif
+
+#endif