reformat codedlist_sort_xxx

1 files changed, 83 insertions, 68 deletions

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 <assert.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdbool.h>
-#include <assert.h>
 #include <time.h>
 
 /* 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
 }
-