diff options
| -rw-r--r-- | lib/fstree/fstree_sort.c | 50 |
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) |