1 files changed, 539 insertions, 0 deletions

diff --git a/dlist.c b/dlist.c
new file mode 100644
index 0000000..140d3a3
--- /dev/null
+++ b/dlist.c
@@ -0,0 +1,539 @@
+/* dlist -- double linked list */
+
+/* Standard C */
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <time.h>
+
+/* Project */
+#include "util.h"
+
+typedef int T;
+
+struct dlist {
+        struct dlist_element *head, *tail;
+};
+
+struct dlist_element {
+        struct dlist_element *prev, *next;
+        T data;
+};
+
+void
+dlist_init(struct dlist *dlist)
+{
+        dlist->head = NULL;
+        dlist->tail = NULL;
+}
+
+static struct dlist_element *
+create_element(T data)
+{
+        struct dlist_element *element;
+   
+        element = malloc(sizeof *element);
+        if ( element != NULL ) {
+                element->data = data;
+        }
+
+        return element;
+}
+
+struct dlist_element *
+dlist_push_front(struct dlist *dlist, T data)
+{
+        struct dlist_element *element;
+   
+        element = create_element(data);
+        if ( element != NULL ) {
+                element->prev = NULL;                   /* Vorgänger ist in jedem Fall NULL */
+
+                if ( dlist->head == NULL ) {    /* empty list */
+                        element->next = NULL;
+                        dlist->tail = element;
+                }
+                else {                                                  /* non empty list */
+                        element->next = dlist->head;
+                        element->next->prev = element;
+                }
+
+                dlist->head = element;                  /* Neues Element ist in jedem Fall der neue Anfang! */
+        }
+        else
+                ERROR("out of memory");
+
+        return element;
+}
+
+struct dlist_element *
+dlist_push_back(struct dlist *dlist, T data)
+{
+        struct dlist_element *element;
+        
+        element = create_element(data);
+        if ( element != NULL ) {
+                element->next = NULL;                   /* Nachfolger ist in jedem Fall NULL */
+
+                if ( dlist->head == NULL ) {    /* empty list */
+                        element->prev = NULL;
+                        dlist->head = element;
+                }
+                else {                                                  /* non empty list */
+                        element->prev = dlist->tail;
+                        element->prev->next = element;
+                }
+
+                dlist->tail = element;                  /* Neues Element ist in jedem Fall das neue Ende! */
+        }
+        else
+                ERROR("out of memory");
+
+        return element;
+}
+
+bool
+dlist_pop_front(struct dlist *dlist, T *data)
+{
+        if ( dlist->head != NULL ) {
+                struct dlist_element *element = dlist->head;
+
+                dlist->head = element->next;
+
+                if ( dlist->head == NULL )
+                        dlist->tail = NULL;
+                else
+                        element->next->prev = NULL;
+
+                *data = element->data;
+                free(element);
+
+                return true;
+        }
+        else
+                return false;
+}
+
+bool
+dlist_pop_back(struct dlist *dlist, T *data)
+{
+        if ( dlist->head != NULL ) {
+                struct dlist_element *element = dlist->tail;
+
+                dlist->tail = element->prev;
+
+                if ( dlist->tail == NULL )
+                        dlist->head = NULL;
+                else
+                        element->prev->next = NULL;
+
+                *data = element->data;
+                free(element);
+
+                return true;
+        }
+        else
+                return false;
+}
+
+struct dlist_element *
+dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
+{
+        struct dlist_element *new_element;
+        
+        new_element = create_element(data);
+        if ( new_element != NULL ) {
+                if ( dlist->head == NULL ) {
+                        dlist->head = new_element;
+                        dlist->head->prev = NULL;
+                        dlist->head->next = NULL;
+                        dlist->tail = new_element;
+                }
+                else {
+                        new_element->next = element->next;
+                        new_element->prev = element;
+
+                        if ( element->next == NULL )
+                                dlist->tail = new_element;
+                        else
+                                element->next->prev = new_element;
+
+                        element->next = new_element;
+                }
+        }
+        else
+                ERROR("out of memory");
+
+        return new_element;
+}
+
+struct dlist_element *
+dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
+{
+        struct dlist_element *new_element;
+        
+        new_element = create_element(data);
+        if ( new_element != NULL ) {
+                if ( dlist->head == NULL ) {
+                        dlist->head = new_element;
+                        dlist->head->prev = NULL;
+                        dlist->head->next = NULL;
+                        dlist->tail = new_element;
+                }
+                else {
+                        new_element->next = element;
+                        new_element->prev = element->prev;
+
+                        if ( element->prev == NULL )
+                                dlist->head = new_element;
+                        else
+                                element->prev->next = new_element;
+
+                        element->prev = new_element;
+                }
+        }
+        else
+                ERROR("out of memory");
+
+        return new_element;
+}
+
+void
+dlist_remove(struct dlist *dlist, struct dlist_element *element)
+{
+        if ( element == dlist->head ) {
+                dlist->head = element->next;
+
+                if ( dlist->head == NULL )
+                        dlist->tail = NULL;
+                else
+                        element->next->prev = NULL;
+        }
+        else {
+                element->prev->next = element->next;
+
+                if ( element->next == NULL )
+                        dlist->tail = element->prev;
+                else
+                        element->next->prev = element->prev;
+        }
+
+        free(element);
+}
+
+void
+dlist_free(struct dlist *dlist)
+{
+        struct dlist_element *elem, *next;
+        
+        for ( elem = dlist->head; elem; elem = next ) {
+                next = elem->next;
+                free(elem);
+        }
+
+        dlist_init(dlist);
+}
+
+void
+dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl)
+{
+        for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
+                visit(elem->data, cl);
+}
+
+void
+print_list(const char *msg, struct dlist *dlist)
+{
+        printf("%s:", msg);
+
+        for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next )
+                printf(" %d", elem->data);
+
+        putchar('\n');
+}
+
+void
+print_list_rev(const char *msg, struct dlist *dlist)
+{
+        printf("%s:", msg);
+
+        for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
+                printf(" %d", elem->data);
+
+        putchar('\n');
+}
+
+void
+remove_if(struct dlist *list)
+{
+        struct dlist_element *elem, *next;
+
+        for ( elem = list->head; elem; elem = next ) {
+                next = elem->next;
+
+                if ( (elem->data & 1) == 1 )
+                        dlist_remove(list, elem);
+        }
+}
+
+void
+dlist_sort_xxx(struct dlist *list)
+{
+        if ( list->head == NULL )
+                return;
+
+        int insize = 1;
+
+        while (1) {
+                struct dlist_element *p;
+
+                p = list->head;
+                list->head = NULL;
+                list->tail = NULL;
+
+                int nmerges = 0;  /* count number of merges we do in this pass */
+
+                while (p) {
+
+                        struct dlist_element *q;
+
+                        nmerges++;  /* there exists a merge to be done */
+                        /* step `insize' places along from p */
+                        q = p;
+                        int psize = 0;
+                        for (int i = 0; i < insize; i++) {
+                                psize++;
+                                q = q->next;
+                                if (!q) break;
+                        }
+
+                        /* if q hasn't fallen off end, we have two lists to merge */
+                        int qsize = insize;
+
+                        /* now we have two lists; merge them */
+                        while (psize > 0 || (qsize > 0 && q)) {
+
+                                struct dlist_element *e;
+
+                                /* decide whether next element of merge comes from p or q */
+                                if (psize == 0) {
+                                        /* p is empty; e must come from q. */
+                                        e = q; q = q->next; qsize--;
+                                } else if (qsize == 0 || !q) {
+                                        /* q is empty; e must come from p. */
+                                        e = p; p = p->next; psize--;
+                                } else if (p->data < q->data) {
+                                        /* First element of p is lower ;
+                                         * e must come from p. */
+                                        e = p; p = p->next; psize--;
+                                } else {
+                                        /* First element of q is lower; e must come from q. */
+                                        e = q; q = q->next; qsize--;
+                                }
+
+                                /* add the next element to the merged list */
+                                if (list->tail) {
+                                        list->tail->next = e;
+                                } else {
+                                        list->head = e;
+                                }
+                                e->prev = list->tail;
+                                list->tail = e;
+                        }
+
+                        /* now p has stepped `insize' places along, and q has too */
+                        p = q;
+                }
+                list->tail->next = NULL;
+
+                /* If we have done only one merge, we're finished. */
+                if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
+                        return; // list;
+
+                /* Otherwise repeat, merging lists twice the size */
+                insize *= 2;
+        }
+}
+
+struct dlist *
+dlist_merge(struct dlist *list1, struct dlist *list2)
+{
+        struct dlist_element *head = NULL,
+                             *cur  = NULL,
+                             *e1   = list1->head,
+                             *e2   = list2->head;
+
+        while ( e1 != NULL && e2 != NULL )              // Solange in e1 UND e2 Elemente sind...
+        {
+                if ( e1->data < e2->data )
+                {
+                        e1->prev = cur;
+                        if ( cur != NULL )
+                                cur->next = e1;
+                        else
+                                head = e1;
+                        cur = e1;
+                        e1 = e1->next;
+                }
+                else
+                {
+                        e2->prev = cur;
+                        if ( cur != NULL )
+                                cur->next = e2;
+                        else
+                                head = e2;
+                        cur = e2;
+                        e2 = e2->next;
+                }
+        }
+
+        if ( e1 != NULL )       // in e1 sind noch Elemente vorhanden!
+        {
+                assert(e2 == NULL);
+
+                e1->prev = cur;
+                if ( cur != NULL )
+                        cur->next = e1;
+                else
+                        head = e1;
+
+                // list1->tail zeigt bereits auf das letzte Element in list1
+        }
+        else /* if ( e2 != NULL ) */
+        {
+                assert(e1 == NULL);
+                assert(e2 != NULL);
+
+                e2->prev = cur;
+                if ( cur != NULL )
+                        cur->next = e2;
+                else
+                        head = e2;
+
+                list1->tail = list2->tail;      // list2->tail ist das Ende der Liste
+        }
+
+        // Kopf neu setzen...
+        list1->head = head;
+
+        // Liste2 ist leer
+        list2->head = NULL;
+        list2->tail = NULL;
+
+        // Zeiger auf Liste1 zurückliefern
+        return list1;
+}
+
+struct dlist *
+dlist_sort(struct dlist *list)
+{
+        if ( list->head == NULL || list->head->next == NULL )           // Leer oder nur ein Element? => Fertig
+                return list;
+
+        struct dlist_element *slow = list->head,
+                                                 *fast = list->head->next;
+
+        while ( fast != NULL && fast->next != NULL )
+                slow = slow->next, fast = fast->next->next;
+
+        struct dlist list1 = { .head = list->head, .tail = slow },
+                                 list2 = { .head = slow->next, .tail = list->tail };
+
+        list1.tail->next = list2.head->prev = NULL;
+
+        dlist_merge(dlist_sort(&list1), dlist_sort(&list2));
+
+        list->head = list1.head;
+        list->tail = list1.tail;
+
+        return list;
+}
+
+void merge_test(void)
+{
+        struct dlist l1, l2;
+
+        dlist_init(&l1);
+        dlist_init(&l2);
+
+        dlist_push_back(&l1, 7);
+        dlist_push_back(&l1, 10);
+        dlist_push_back(&l1, 11);
+        dlist_push_back(&l1, 19);
+        dlist_push_back(&l1, 23);
+
+        dlist_push_back(&l2, 4);
+        dlist_push_back(&l2, 14);
+        dlist_push_back(&l2, 15);
+
+        struct dlist *ptr;
+        ptr = dlist_merge(&l1, &l2);
+
+        struct dlist_element *cur;
+        for ( cur = ptr->head; cur; cur = cur->next ) {
+                if ( cur->prev ) printf("%4d", cur->prev->data); else printf("xxx ");
+                printf("%4d", cur->data);
+                if ( cur->next ) printf("%4d", cur->next->data); else printf(" xxx");
+
+                puts("");
+        }
+
+        dlist_free(&l1);
+        dlist_free(&l2);
+}
+
+void ls()
+{
+        struct dlist list;
+
+        dlist_init(&list);
+
+        for ( int i = 0; i != 30000000; ++i )
+                dlist_insert_prev(&list, list.tail, rand() % 9999);
+
+        //print_list("Unsortiert:", &list);
+        printf("start\n");
+        clock_t start = clock();
+        dlist_sort(&list);
+        clock_t ende = clock();
+
+        printf("Dauer: %.3fsec\n", ((double) ende-start)/CLOCKS_PER_SEC);
+        //print_list("Sortiert:", &list);
+        //print_list_rev("Sortiert:", &list);
+
+        dlist_free(&list);
+}
+
+
+int
+main(void)
+{
+        ls();
+
+#if 0
+        merge_test();
+#endif
+
+#if 0
+        struct dlist list;
+
+        dlist_init(&list);
+
+        for ( int i = 0; i != 10; ++i )
+                dlist_insert_prev(&list, list.tail, i);
+
+        print_list("Ausgabe: ", &list);
+
+        remove_if(&list);
+
+        print_list("Ausgabe: ", &list);
+
+        dlist_free(&list);
+
+        ls();
+
+        return EXIT_SUCCESS;
+#endif
+}
+