From 09a96907962ac2d1115f545e194f06ea4fd3db19 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 2 Aug 2020 10:55:59 +0200 Subject: reformat code --- dlist.c | 151 +++++++++++++++++++++++++++++++++++----------------------------- 1 file changed, 83 insertions(+), 68 deletions(-) (limited to 'dlist.c') diff --git a/dlist.c b/dlist.c index 140d3a3..c006f20 100644 --- a/dlist.c +++ b/dlist.c @@ -1,10 +1,10 @@ /* dlist -- double linked list */ /* Standard C */ +#include +#include #include #include -#include -#include #include /* Project */ @@ -18,7 +18,7 @@ struct dlist { struct dlist_element { struct dlist_element *prev, *next; - T data; + T data; }; void @@ -32,7 +32,7 @@ static struct dlist_element * create_element(T data) { struct dlist_element *element; - + element = malloc(sizeof *element); if ( element != NULL ) { element->data = data; @@ -45,21 +45,21 @@ 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 */ + element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */ - if ( dlist->head == NULL ) { /* empty list */ + if ( dlist->head == NULL ) { /* empty list */ element->next = NULL; - dlist->tail = element; + dlist->tail = element; } - else { /* non empty list */ - element->next = dlist->head; + else { /* non empty list */ + element->next = dlist->head; element->next->prev = element; } - dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */ + dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */ } else ERROR("out of memory"); @@ -71,21 +71,21 @@ 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 */ + element->next = NULL; /* Nachfolger ist in jedem Fall NULL */ - if ( dlist->head == NULL ) { /* empty list */ + if ( dlist->head == NULL ) { /* empty list */ element->prev = NULL; - dlist->head = element; + dlist->head = element; } - else { /* non empty list */ - element->prev = dlist->tail; + else { /* non empty list */ + element->prev = dlist->tail; element->prev->next = element; } - dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */ + dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */ } else ERROR("out of memory"); @@ -141,14 +141,14 @@ 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 = new_element; dlist->head->prev = NULL; dlist->head->next = NULL; - dlist->tail = new_element; + dlist->tail = new_element; } else { new_element->next = element->next; @@ -172,14 +172,14 @@ 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 = new_element; dlist->head->prev = NULL; dlist->head->next = NULL; - dlist->tail = new_element; + dlist->tail = new_element; } else { new_element->next = element; @@ -226,7 +226,7 @@ void dlist_free(struct dlist *dlist) { struct dlist_element *elem, *next; - + for ( elem = dlist->head; elem; elem = next ) { next = elem->next; free(elem); @@ -285,60 +285,71 @@ dlist_sort_xxx(struct dlist *list) int insize = 1; - while (1) { + while ( 1 ) { struct dlist_element *p; - p = list->head; + p = list->head; list->head = NULL; list->tail = NULL; - int nmerges = 0; /* count number of merges we do in this pass */ - - while (p) { + 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 */ + nmerges++; /* there exists a merge to be done */ /* step `insize' places along from p */ - q = p; + q = p; int psize = 0; - for (int i = 0; i < insize; i++) { + for ( int i = 0; i < insize; i++ ) { psize++; q = q->next; - if (!q) break; + 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)) { - + while ( psize > 0 || (qsize > 0 && q) ) { struct dlist_element *e; /* decide whether next element of merge comes from p or q */ - if (psize == 0) { + if ( psize == 0 ) { /* p is empty; e must come from q. */ - e = q; q = q->next; qsize--; - } else if (qsize == 0 || !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) { + 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 { + e = p; + p = p->next; + psize--; + } + else { /* First element of q is lower; e must come from q. */ - e = q; q = q->next; qsize--; + e = q; + q = q->next; + qsize--; } /* add the next element to the merged list */ - if (list->tail) { + if ( list->tail ) { list->tail->next = e; - } else { + } + else { list->head = e; } - e->prev = list->tail; + e->prev = list->tail; list->tail = e; } @@ -348,8 +359,8 @@ dlist_sort_xxx(struct dlist *list) 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; + if ( nmerges <= 1 ) /* allow for nmerges==0, the empty list case */ + return; // list; /* Otherwise repeat, merging lists twice the size */ insize *= 2; @@ -364,31 +375,29 @@ dlist_merge(struct dlist *list1, struct dlist *list2) *e1 = list1->head, *e2 = list2->head; - while ( e1 != NULL && e2 != NULL ) // Solange in e1 UND e2 Elemente sind... + while ( e1 != NULL && e2 != NULL ) // Solange in e1 UND e2 Elemente sind... { - if ( e1->data < e2->data ) - { + if ( e1->data < e2->data ) { e1->prev = cur; if ( cur != NULL ) cur->next = e1; else head = e1; cur = e1; - e1 = e1->next; + e1 = e1->next; } - else - { + else { e2->prev = cur; if ( cur != NULL ) cur->next = e2; else head = e2; cur = e2; - e2 = e2->next; + e2 = e2->next; } } - if ( e1 != NULL ) // in e1 sind noch Elemente vorhanden! + if ( e1 != NULL ) // in e1 sind noch Elemente vorhanden! { assert(e2 == NULL); @@ -411,7 +420,7 @@ dlist_merge(struct dlist *list1, struct dlist *list2) else head = e2; - list1->tail = list2->tail; // list2->tail ist das Ende der Liste + list1->tail = list2->tail; // list2->tail ist das Ende der Liste } // Kopf neu setzen... @@ -428,17 +437,17 @@ dlist_merge(struct dlist *list1, struct dlist *list2) struct dlist * dlist_sort(struct dlist *list) { - if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig + 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; + *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 }; + list2 = { .head = slow->next, .tail = list->tail }; list1.tail->next = list2.head->prev = NULL; @@ -450,7 +459,8 @@ dlist_sort(struct dlist *list) return list; } -void merge_test(void) +void +merge_test(void) { struct dlist l1, l2; @@ -472,9 +482,15 @@ void merge_test(void) struct dlist_element *cur; for ( cur = ptr->head; cur; cur = cur->next ) { - if ( cur->prev ) printf("%4d", cur->prev->data); else printf("xxx "); + 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"); + if ( cur->next ) + printf("%4d", cur->next->data); + else + printf(" xxx"); puts(""); } @@ -483,7 +499,8 @@ void merge_test(void) dlist_free(&l2); } -void ls() +void +ls() { struct dlist list; @@ -498,14 +515,13 @@ void ls() dlist_sort(&list); clock_t ende = clock(); - printf("Dauer: %.3fsec\n", ((double) ende-start)/CLOCKS_PER_SEC); + 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) { @@ -536,4 +552,3 @@ main(void) return EXIT_SUCCESS; #endif } - -- cgit v1.3