Simplify fstree sorting

For merging, the use of a pointer to a pointer can simplify linked list
operations

For sorting, find the half-way point of the list in a single iteration
over the list

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

1 files changed, 21 insertions, 29 deletions

diff --git a/lib/fstree/fstree_sort.c b/lib/fstree/fstree_sort.c
index a38e2a6..404554d 100644
--- a/lib/fstree/fstree_sort.c
+++ b/lib/fstree/fstree_sort.c
@@ -7,7 +7,9 @@
 
 static tree_node_t *merge(tree_node_t *lhs, tree_node_t *rhs)
 {
-	tree_node_t *head = NULL, *prev = NULL, *it;
+	tree_node_t *it;
+	tree_node_t *head = NULL;
+	tree_node_t **next_ptr = &head;
 
 	while (lhs != NULL && rhs != NULL) {
 		if (strcmp(lhs->name, rhs->name) <= 0) {
@@ -18,49 +20,39 @@ static tree_node_t *merge(tree_node_t *lhs, tree_node_t *rhs)
 			rhs = rhs->next;
 		}
 
-		it->next = NULL;
-
-		if (prev != NULL) {
-			prev->next = it;
-			prev = it;
-		} else {
-			prev = head = it;
-		}
+		*next_ptr = it;
+		next_ptr = &it->next;
 	}
 
 	it = (lhs != NULL ? lhs : rhs);
-
-	if (prev != NULL) {
-		prev->next = it;
-	} else {
-		head = it;
-	}
-
+	*next_ptr = it;
 	return head;
 }
 
 tree_node_t *tree_node_list_sort(tree_node_t *head)
 {
-	tree_node_t *it, *prev;
-	size_t i, count = 0;
+	tree_node_t *it, *half, *prev;
 
-	for (it = head; it != NULL; it = it->next)
-		++count;
+	it = half = prev = head;
+	while (it != NULL) {
+		prev = half;
+		half = half->next;
+		it = it->next;
+		if (it != NULL) {
+			it = it->next;
+		}
+	}
 
-	if (count < 2)
+	// half refers to the (count/2)'th element ROUNDED UP.
+	// It will be null therefore only in the empty and the
+	// single element list
+	if (half == NULL) {
 		return head;
-
-	prev = NULL;
-	it = head;
-
-	for (i = 0; i < count / 2; ++i) {
-		prev = it;
-		it = it->next;
 	}
 
 	prev->next = NULL;
 
-	return merge(tree_node_list_sort(head), tree_node_list_sort(it));
+	return merge(tree_node_list_sort(head), tree_node_list_sort(half));
 }
 
 void tree_node_sort_recursive(tree_node_t *n)