summaryrefslogtreecommitdiff
path: root/lib/fstree/fstree_sort.c
diff options
context:
space:
mode:
authorZachary Dremann <dremann@gmail.com>2019-07-27 19:56:09 -0400
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-07-29 00:11:24 +0200
commitdad72be359d2670dd4993101591e1b14638dedec (patch)
tree059c77a1d505775c12dadf7e36ccef85571f1b04 /lib/fstree/fstree_sort.c
parent6248b360c8c3b055b36b84b4bd37ec20a5915a89 (diff)
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>
Diffstat (limited to 'lib/fstree/fstree_sort.c')
-rw-r--r--lib/fstree/fstree_sort.c50
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)