From ac55496d881e0a17b3eff85f1faae5aafbc53b50 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 22 Jul 2020 17:30:45 +0200 Subject: erster Commit --- dlist.c | 539 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 539 insertions(+) create mode 100644 dlist.c (limited to 'dlist.c') 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 +#include +#include +#include +#include + +/* 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 +} + -- cgit v1.3