1 files changed, 203 insertions, 0 deletions

diff --git a/list.c b/list.c
new file mode 100644
index 0000000..8b18de8
--- /dev/null
+++ b/list.c
@@ -0,0 +1,203 @@
+/* simple Implementation of single linked lists */
+/* written and placed in the public domain by Thomas Schmucker */
+
+/* Standard C */
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* Project */
+#include "util.h"
+
+typedef int T;
+
+struct list_item {
+        struct list_item *next;
+        T data;
+};
+
+struct list_item *
+list_add(struct list_item *next, T data)
+{
+        struct list_item *new_item;
+
+        new_item = malloc(sizeof *new_item);
+        if ( new_item != NULL ) {
+                new_item->next = next;
+                new_item->data = data;
+        }
+        else
+                ERROR("out of memory");
+
+        return new_item;
+}
+
+struct list_item *
+list_delete(struct list_item *list, T data)
+{
+        struct list_item *prev = NULL;
+
+        for ( struct list_item *p = list; p; p = p->next ) {
+                if ( p->data == data ) {
+                        if ( prev == NULL ) {           /* first element in list? */
+                                list = p->next;
+                        }
+                        else {
+                                prev->next = p->next;
+                        }
+
+                        free(p);
+
+                        return list;
+                }
+                prev = p;
+        }
+        //ERROR("data not found");      /* uncomment, if this case should be reported as an error */
+        return list;
+}
+
+size_t
+list_length(struct list_item *list)
+{
+        size_t len = 0;
+
+        for ( ; list; list = list->next )
+                ++len;
+
+        return len;
+}
+
+struct list_item *
+list_copy(struct list_item *list)
+{
+        struct list_item *head, **p = &head;
+
+        for ( ; list; list = list->next ) {
+                *p = malloc(sizeof **p);
+                if ( *p != NULL ) {
+                        (*p)->data = list->data;        // copy elements
+                        p = &(*p)->next;
+                }
+                else
+                        ERROR("out of memory");
+        }
+        *p = NULL;
+        return head;
+}
+
+struct list_item *
+list_reverse(struct list_item *list)
+{
+        struct list_item *head = NULL, *next;
+
+        for ( ; list; list = next ) {
+                next = list->next;
+                list->next = head;
+                head = list;
+        }
+        return head;
+}
+
+void
+list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
+{
+        for ( ; list; list = list->next ) {
+                visit(list->data, cl);
+        }
+}
+
+struct list_item *
+list_merge(struct list_item *a, struct list_item *b)
+{
+        struct list_item dummy = { .next = NULL };
+        struct list_item *head = &dummy, *c = head;
+
+        while ( a != NULL && b != NULL )
+                if ( a->data < b->data )
+                        c->next = a, c = a, a = a->next;
+                else
+                        c->next = b, c = b, b = b->next;
+
+        c->next = ( a != NULL ) ? a : b;
+
+        return head->next;
+}
+
+struct list_item *
+list_sort(struct list_item *c)
+{
+        if ( c == NULL || c->next == NULL )
+                return c;
+
+        struct list_item *a = c,
+                                         *b = c->next;
+
+        while ( b != NULL && b->next != NULL )
+                c = c->next, b = b->next->next;
+
+        b = c->next, c->next = NULL;
+
+        return list_merge(list_sort(a), list_sort(b));
+}
+
+void
+list_free(struct list_item *list)
+{
+        struct list_item *next;
+
+        for ( ; list; list = next ) {
+                next = list->next;
+                free(list);
+        }
+}
+
+static void print_data(T data, void *cl) { fprintf(cl, "%d\n", data); }
+
+int
+main()
+{
+        clock_t start;
+
+        /*
+        struct list_item *mylist = NULL;
+
+        mylist = list_add(mylist, 42);
+        mylist = list_add(mylist, 43);
+        mylist = list_add(mylist, 44);
+
+        mylist = list_delete(mylist, 45);
+
+        list_apply(mylist, print_data, stdout);
+
+        struct list_item *mylist2 = list_reverse(list_copy(mylist));
+
+        list_free(mylist);
+        list_apply(mylist2, print_data);
+        list_free(mylist2);
+        */
+
+        srand(time(NULL));
+
+        static const int COUNT = 10000000;
+
+        struct list_item *x = NULL;
+        for ( int i = 0; i != COUNT; ++i ) {
+                int r = rand();
+                x = list_add(x, r);
+        }
+
+        puts("start");
+        start = clock();
+        x = list_sort(x);
+        printf("Fertig: %.3lf sec\n", (double)(clock() - start) / CLOCKS_PER_SEC);
+
+        //list_apply(x, print_data);
+        printf("Len: %zu\n", list_length(x));
+
+        list_free(x);
+
+        return EXIT_SUCCESS;
+}
+
+
+