Renamed cslist to cflist (forward_list). Renamed cstring_makeCopy() to cstring_clone()

3 files changed, 300 insertions, 250 deletions

diff --git a/stc/cflist.h b/stc/cflist.h
new file mode 100644
index 00000000..f094e7de
--- /dev/null
+++ b/stc/cflist.h
@@ -0,0 +1,292 @@
+/* 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 CSLIST__H__
+#define CSLIST__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_defaultDestroy)
+#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, valueCompare, Value, c_defaultGetRaw)
+#define declare_CFList_string(tag) \
+                               declare_CFList_6(tag, CString, cstring_destroy, cstring_compareRaw, const char*, 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, valueCompare, ValueRaw, valueGetRaw) \
+ \
+    declare_CFListTypes(tag, Value); \
+    typedef ValueRaw cflist_##tag##_raw_t; \
+ \
+    static inline void \
+    cflist_##tag##_pushFront(CFList_##tag* self, Value value) { \
+        _cflist_insertAfter(tag, self->last, value); \
+         if (!self->last) self->last = entry; \
+    } \
+    static inline void \
+    cflist_##tag##_pushBack(CFList_##tag* self, Value value) { \
+        _cflist_insertAfter(tag, self->last, value); \
+        self->last = entry; \
+    } \
+    static inline 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; \
+    } \
+ \
+    static inline void \
+    cflist_##tag##_eraseAfter(CFList_##tag* self, cflist_##tag##_iter_t pos) { \
+        _cflist_eraseAfter(tag, pos.item, valueDestroy); \
+    } \
+ \
+    static inline void \
+    cflist_##tag##_popFront(CFList_##tag* self) { \
+        _cflist_eraseAfter(tag, self->last, valueDestroy); \
+    } \
+ \
+    static inline void \
+    cflist_##tag##_destroy(CFList_##tag* self) { \
+        while (self->last) \
+            cflist_##tag##_popFront(self); \
+    } \
+ \
+    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 valueCompare(&a, &b); \
+    } \
+     \
+    static inline void \
+    cflist_##tag##_sort(CFList_##tag* self) { \
+        CFListNode__base* last = cflist_mergesort((CFListNode__base *) self->last, cflist_##tag##_sortCmp); \
+        self->last = (CFListNode_##tag *) last; \
+    } \
+ \
+    static inline cflist_##tag##_iter_t \
+    cflist_##tag##_begin(CFList_##tag* lst) { \
+        CFListNode_##tag *head = lst->last ? lst->last->next : NULL; \
+        return (cflist_##tag##_iter_t) {head, &lst->last}; \
+    } \
+    static inline cflist_##tag##_iter_t \
+    cflist_##tag##_last(CFList_##tag* lst) { \
+        return (cflist_##tag##_iter_t) {lst->last, &lst->last}; \
+    } \
+ \
+    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 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; \
+    } \
+    static inline void \
+    cflist_##tag##_spliceFront(CFList_##tag* self, CFList_##tag* other) { \
+        _cflist_##tag##_splice(self, cflist_##tag##_last(self), other, false); \
+    } \
+    static inline void \
+    cflist_##tag##_spliceAfter(CFList_##tag* self, cflist_##tag##_iter_t pos, CFList_##tag* other) { \
+        _cflist_##tag##_splice(self, pos, other, true); \
+    } \
+ \
+    static inline 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 (valueCompare((r = valueGetRaw(&i.item->value), &r), &val) == 0) { \
+                cflist_##tag##_eraseAfter(self, prev), ++n; \
+                if (prev.item == i.item) break; \
+            } \
+            prev = i; \
+        } \
+        return n; \
+    } \
+ \
+    typedef Value cflist_##tag##_value_t
+    
+
+#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 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;
+    }
+}
+
+#endif
diff --git a/stc/cslist.h b/stc/cslist.h
deleted file mode 100644
index 9c1814f3..00000000
--- a/stc/cslist.h
+++ /dev/null
@@ -1,242 +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 CSLIST__H__
-#define CSLIST__H__
-
-#include "cdefs.h"
-
-/* Circular Singly-linked Lists */
-
-
-#define declare_CSList(...)    c_MACRO_OVERLOAD(declare_CSList, __VA_ARGS__)
-
-#define declare_CSList_2(tag, Value) \
-                               declare_CSList_3(tag, Value, c_defaultDestroy)
-#define declare_CSList_3(tag, Value, valueDestroy) \
-                               declare_CSList_4(tag, Value, valueDestroy, c_defaultCompare)
-#define declare_CSList_4(tag, Value, valueDestroy, valueCompare) \
-                               declare_CSList_6(tag, Value, valueDestroy, valueCompare, Value, c_defaultGetRaw)
-#define declare_CSList_string(tag) \
-                               declare_CSList_6(tag, CString, cstring_destroy, cstring_compareRaw, const char*, cstring_getRaw)                            
-
-
-#define declare_CSListTypes(tag, Value) \
-    c_struct (CSListNode_##tag) { \
-        CSListNode_##tag *next; \
-        Value value; \
-    }; \
- \
-    c_struct (CSList_##tag) { \
-        CSListNode_##tag* last; \
-    }; \
- \
-    c_struct (cslist_##tag##_iter_t) { \
-        CSListNode_##tag *item, **_last; \
-    }
-
-
-#define cslist_init          {NULL}
-#define cslist_front(list)   (list).last->next->value
-#define cslist_back(list)    (list).last->value
-#define cslist_empty(list)   ((list).last == NULL)
-
-#define declare_CSList_6(tag, Value, valueDestroy, valueCompare, ValueRaw, valueGetRaw) \
- \
-    declare_CSListTypes(tag, Value); \
- \
-    static inline void \
-    cslist_##tag##_pushFront(CSList_##tag* self, Value value) { \
-        _cslist_insertAfter(tag, self->last, value); \
-         if (!self->last) self->last = entry; \
-    } \
-    static inline void \
-    cslist_##tag##_pushBack(CSList_##tag* self, Value value) { \
-        _cslist_insertAfter(tag, self->last, value); \
-        self->last = entry; \
-    } \
-    static inline void \
-    cslist_##tag##_insertAfter(CSList_##tag* self, cslist_##tag##_iter_t pos, Value value) { \
-        _cslist_insertAfter(tag, pos.item, value); \
-        if (!self->last || pos.item == self->last) self->last = entry; \
-    } \
- \
-    static inline void \
-    cslist_##tag##_eraseAfter(CSList_##tag* self, cslist_##tag##_iter_t pos) { \
-        _cslist_eraseAfter(tag, pos.item, valueDestroy); \
-    } \
- \
-    static inline void \
-    cslist_##tag##_popFront(CSList_##tag* self) { \
-        _cslist_eraseAfter(tag, self->last, valueDestroy); \
-    } \
- \
-    static inline void \
-    cslist_##tag##_destroy(CSList_##tag* self) { \
-        while (self->last) \
-            cslist_##tag##_popFront(self); \
-    } \
- \
-    static inline int \
-    cslist_##tag##_sortCmp(const void* x, const void* y) { \
-        CSListNode_##tag *a = (CSListNode_##tag *)x, *b = (CSListNode_##tag *)y; \
-        return valueCompare(valueGetRaw(&a->value), valueGetRaw(&b->value)); \
-    } \
-     \
-    static inline void \
-    cslist_##tag##_sort(CSList_##tag* self) { \
-        CSListNode__base* last = cslist_mergesort((CSListNode__base *) self->last, cslist_##tag##_sortCmp); \
-        self->last = (CSListNode_##tag *) last; \
-    } \
- \
-    static inline cslist_##tag##_iter_t \
-    cslist_##tag##_begin(CSList_##tag* lst) { \
-        CSListNode_##tag *head = lst->last ? lst->last->next : NULL; \
-        return (cslist_##tag##_iter_t) {head, &lst->last}; \
-    } \
-    static inline cslist_##tag##_iter_t \
-    cslist_##tag##_last(CSList_##tag* lst) { \
-        return (cslist_##tag##_iter_t) {lst->last, &lst->last}; \
-    } \
- \
-    static inline cslist_##tag##_iter_t \
-    cslist_##tag##_next(cslist_##tag##_iter_t it) { \
-        it.item = it.item == *it._last ? NULL : it.item->next; \
-        return it; \
-    } \
- \
-    static inline void \
-    _cslist_##tag##_splice(CSList_##tag* self, cslist_##tag##_iter_t pos, CSList_##tag* other, bool bottom) { \
-        if (!pos.item) \
-            self->last = pos.item = other->last; \
-        else if (other->last) { \
-            CSListNode_##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; \
-    } \
-    static inline void \
-    cslist_##tag##_spliceFront(CSList_##tag* self, CSList_##tag* other) { \
-        _cslist_##tag##_splice(self, cslist_##tag##_last(self), other, false); \
-    } \
-    static inline void \
-    cslist_##tag##_spliceAfter(CSList_##tag* self, cslist_##tag##_iter_t pos, CSList_##tag* other) { \
-        _cslist_##tag##_splice(self, pos, other, true); \
-    } \
- \
-    static inline int \
-    cslist_##tag##_remove(CSList_##tag* self, ValueRaw val) { \
-        cslist_##tag##_iter_t prev = {self->last}; int n = 0; \
-        c_foreach (i, cslist_##tag, *self) { \
-            if (valueCompare(valueGetRaw(&i.item->value), &val) == 0) { \
-                cslist_##tag##_eraseAfter(self, prev), ++n; \
-                if (prev.item == i.item) break; \
-            } \
-            prev = i; \
-        } \
-        return n; \
-    } \
- \
-    typedef Value cslist_##tag##_value_t
-    
-
-#define _cslist_insertAfter(tag, node, val) \
-    CSListNode_##tag *entry = c_new_1(CSListNode_##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 _cslist_eraseAfter(tag, node, valueDestroy) \
-    CSListNode_##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_CSListTypes(_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 CSListNode__base *
-cslist_mergesort(CSListNode__base *list, int (*cmp)(const void*, const void*)) {
-    CSListNode__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;
-    }
-}
-
-#endif
diff --git a/stc/cstring.h b/stc/cstring.h
index 99ab4e81..535dd0f9 100644
--- a/stc/cstring.h
+++ b/stc/cstring.h
@@ -64,13 +64,6 @@ cstring_resize(CString* self, size_t len, char fill) {
     self->str[ _cstring_rep(*self)[0] = len ] = '\0';

 }

 

-static inline CString

-cstring_move(CString* self) {

-    CString mv = *self;

-    *self = cstring_init;

-    return mv;

-}

-

 static inline void

 cstring_destroy(CString* self) {

     if (cstring_capacity(*self)) {

@@ -102,10 +95,17 @@ cstring_make(const char* str) {
 }

 

 static inline CString

-cstring_makeCopy(CString cs) {

+cstring_clone(CString cs) {

     return cstring_makeN(cs.str, cstring_size(cs));

 }

 

+static inline CString

+cstring_move(CString* self) {

+    CString mv = *self;

+    *self = cstring_init;

+    return mv;

+}

+

 static inline void

 cstring_clear(CString* self) {

     CString cs = cstring_init;