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> 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
