blob: 58ffadf1cf00ead29e2834cf94fa87a0063b85b1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
* fstree_sort.c
*
* Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
* Copyright (C) 2019 Zachary Dremann <dremann@gmail.com>
*/
#include "internal.h"
#include <string.h>
static tree_node_t *merge(tree_node_t *lhs, tree_node_t *rhs)
{
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) {
it = lhs;
lhs = lhs->next;
} else {
it = rhs;
rhs = rhs->next;
}
*next_ptr = it;
next_ptr = &it->next;
}
it = (lhs != NULL ? lhs : rhs);
*next_ptr = it;
return head;
}
tree_node_t *tree_node_list_sort(tree_node_t *head)
{
tree_node_t *it, *half, *prev;
it = half = prev = head;
while (it != NULL) {
prev = half;
half = half->next;
it = it->next;
if (it != NULL) {
it = it->next;
}
}
// 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->next = NULL;
return merge(tree_node_list_sort(head), tree_node_list_sort(half));
}
|
