1 //===- ilist_sort.h -------------------------------------------------------===//
2 //
3 // The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #ifndef MCLD_ADT_ILIST_SORT_H_
10 #define MCLD_ADT_ILIST_SORT_H_
11
12 #include <llvm/ADT/ilist.h>
13
14 #include <functional>
15 #include <iterator>
16
17 namespace mcld {
18
19 namespace detail {
20
21 template <typename T, typename Alloc, typename Comparator>
sort(llvm::iplist<T,Alloc> & xs,size_t size,Comparator is_less_than)22 void sort(llvm::iplist<T, Alloc>& xs, size_t size, Comparator is_less_than) {
23 typedef llvm::iplist<T, Alloc> iplist;
24 typedef typename iplist::iterator iterator;
25
26 assert(xs.size() == size && "Incorrect list size argument");
27
28 // Special cases for induction basis.
29 switch (size) {
30 case 0:
31 case 1: {
32 return;
33 }
34 case 2: {
35 iterator first = xs.begin();
36 iterator second = xs.begin();
37 ++second;
38 if (is_less_than(*second, *first)) {
39 xs.splice(first, xs, second);
40 }
41 return;
42 }
43 }
44
45 // Split the input linked list.
46 size_t mid = size / 2;
47 iterator mid_iter(xs.begin());
48 std::advance(mid_iter, mid);
49
50 iplist ys;
51 ys.splice(ys.begin(), xs, mid_iter, xs.end());
52
53 // Sort the xs and ys recursively.
54 sort(xs, mid, is_less_than);
55 sort(ys, size - mid, is_less_than);
56
57 // Merge two sorted linked lists.
58 iterator xs_it = xs.begin();
59 iterator xs_end = xs.end();
60 iterator ys_it = ys.begin();
61 iterator ys_end = ys.end();
62
63 while (xs_it != xs_end && ys_it != ys_end) {
64 if (is_less_than(*ys_it, *xs_it)) {
65 xs.splice(xs_it, ys, ys_it++);
66 } else {
67 ++xs_it;
68 }
69 }
70
71 xs.splice(xs_end, ys, ys_it, ys_end);
72 }
73
74 } // namespace detail
75
76 template <typename T, typename Alloc, typename Comparator = std::less<T> >
77 void sort(llvm::iplist<T, Alloc>& list,
78 Comparator is_less_than = Comparator()) {
79 detail::sort(list, list.size(), is_less_than);
80 }
81
82 } // namespace mcld
83
84 #endif // MCLD_ADT_ILIST_SORT_H_
85