neue Verzeichnisstruktur

1 files changed, 504 insertions, 0 deletions

diff --git a/src/dlist.c b/src/dlist.c
new file mode 100644
index 0000000..55e42d7
--- /dev/null
+++ b/src/dlist.c
@@ -0,0 +1,504 @@
+/* dlist -- double linked list */
+
+/* Standard C */
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* Project */
+#include "util.h"
+
+/* --8<-- dlist_type */
+typedef int T;
+
+struct dlist {
+        struct dlist_element *head, *tail;
+};
+
+struct dlist_element {
+        struct dlist_element *prev, *next;
+        T                     data;
+};
+/* -->8-- */
+
+/* --8<-- dlist_init */
+void
+dlist_init(struct dlist *dlist)
+{
+        dlist->head = NULL;
+        dlist->tail = NULL;
+}
+/* -->8-- */
+
+/* --8<-- dlist_empty */
+bool
+dlist_empty(struct dlist *dlist)
+{
+        return dlist->head == NULL;
+}
+/* -->8-- */
+
+/* --8<-- dlist_create_element */
+static struct dlist_element *
+create_element(T data)
+{
+        struct dlist_element *element;
+
+        element = malloc(sizeof *element);
+        if ( element ) {
+                element->data = data;
+        }
+
+        return element;
+}
+/* -->8-- */
+
+/* --8<-- dlist_push_front */
+struct dlist_element *
+dlist_push_front(struct dlist *dlist, T data)
+{
+        struct dlist_element *element;
+
+        element = create_element(data);
+        if ( element ) {
+                element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */
+
+                if ( dlist_empty(dlist) ) {
+                        element->next = NULL;
+                        dlist->tail   = element;
+                }
+                else {
+                        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;
+}
+/* -->8-- */
+
+/* --8<-- dlist_push_back */
+struct dlist_element *
+dlist_push_back(struct dlist *dlist, T data)
+{
+        struct dlist_element *element;
+
+        element = create_element(data);
+        if ( element ) {
+                element->next = NULL; /* Nachfolger ist in jedem Fall NULL */
+
+                if ( dlist_empty(dlist) ) {
+                        element->prev = NULL;
+                        dlist->head   = element;
+                }
+                else {
+                        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;
+}
+/* -->8-- */
+
+/* --8<-- dlist_pop_front */
+bool
+dlist_pop_front(struct dlist *dlist, T *data)
+{
+        if ( dlist->head ) {
+                struct dlist_element *element = dlist->head;
+
+                dlist->head = element->next;
+
+                if ( dlist->head == NULL )
+                        dlist->tail = NULL;
+                else
+                        element->next->prev = NULL;
+
+                if ( data ) {
+                        *data = element->data;
+                }
+                free(element);
+
+                return true;
+        }
+        else
+                return false;
+}
+/* -->8-- */
+
+/* --8<-- dlist_pop_back */
+bool
+dlist_pop_back(struct dlist *dlist, T *data)
+{
+        if ( dlist->head ) {
+                struct dlist_element *element = dlist->tail;
+
+                dlist->tail = element->prev;
+
+                if ( dlist->tail == NULL )
+                        dlist->head = NULL;
+                else
+                        element->prev->next = NULL;
+
+                if ( data ) {
+                        *data = element->data;
+                }
+                free(element);
+
+                return true;
+        }
+        else
+                return false;
+}
+/* -->8-- */
+
+/* --8<-- dlist_insert_next */
+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 ) {
+                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;
+}
+/* -->8-- */
+
+/* --8<-- dlist_insert_prev */
+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 ) {
+                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;
+}
+/* -->8-- */
+
+/* --8<-- dlist_remove */
+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);
+}
+/* -->8-- */
+
+/* --8<-- dlist_free */
+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);
+}
+/* -->8-- */
+
+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);
+                }
+        }
+}
+
+/* --8<-- dlist_merge */
+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 && e2 ) // Solange in e1 UND e2 Elemente sind...
+        {
+                if ( e1->data < e2->data ) {
+                        e1->prev = cur;
+                        if ( cur )
+                                cur->next = e1;
+                        else
+                                head = e1;
+                        cur = e1;
+                        e1  = e1->next;
+                }
+                else {
+                        e2->prev = cur;
+                        if ( cur )
+                                cur->next = e2;
+                        else
+                                head = e2;
+                        cur = e2;
+                        e2  = e2->next;
+                }
+        }
+
+        if ( e1 ) // in e1 sind noch Elemente vorhanden!
+        {
+                assert(e2 == NULL);
+
+                e1->prev = cur;
+                if ( cur )
+                        cur->next = e1;
+                else
+                        head = e1;
+
+                // list1->tail zeigt bereits auf das letzte Element in list1
+        }
+        else /* if ( e2 ) */
+        {
+                assert(e1 == NULL);
+                assert(e2);
+
+                e2->prev = cur;
+                if ( cur )
+                        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;
+}
+/* -->8-- */
+
+/* --8<-- dlist_sort */
+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 && fast->next )
+                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;
+}
+/* -->8-- */
+
+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
+}