| //===- ilist_sort.h -------------------------------------------------------===// |
| // |
| // The MCLinker Project |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef MCLD_ADT_ILIST_SORT_H_ |
| #define MCLD_ADT_ILIST_SORT_H_ |
| |
| #include <llvm/ADT/ilist.h> |
| |
| #include <functional> |
| #include <iterator> |
| |
| namespace mcld { |
| |
| namespace detail { |
| |
| template <typename T, typename Alloc, typename Comparator> |
| void sort(llvm::iplist<T, Alloc>& xs, size_t size, Comparator is_less_than) { |
| typedef llvm::iplist<T, Alloc> iplist; |
| typedef typename iplist::iterator iterator; |
| |
| assert(xs.size() == size && "Incorrect list size argument"); |
| |
| // Special cases for induction basis. |
| switch (size) { |
| case 0: |
| case 1: { |
| return; |
| } |
| case 2: { |
| iterator first = xs.begin(); |
| iterator second = xs.begin(); |
| ++second; |
| if (is_less_than(*second, *first)) { |
| xs.splice(first, xs, second); |
| } |
| return; |
| } |
| } |
| |
| // Split the input linked list. |
| size_t mid = size / 2; |
| iterator mid_iter(xs.begin()); |
| std::advance(mid_iter, mid); |
| |
| iplist ys; |
| ys.splice(ys.begin(), xs, mid_iter, xs.end()); |
| |
| // Sort the xs and ys recursively. |
| sort(xs, mid, is_less_than); |
| sort(ys, size - mid, is_less_than); |
| |
| // Merge two sorted linked lists. |
| iterator xs_it = xs.begin(); |
| iterator xs_end = xs.end(); |
| iterator ys_it = ys.begin(); |
| iterator ys_end = ys.end(); |
| |
| while (xs_it != xs_end && ys_it != ys_end) { |
| if (is_less_than(*ys_it, *xs_it)) { |
| xs.splice(xs_it, ys, ys_it++); |
| } else { |
| ++xs_it; |
| } |
| } |
| |
| xs.splice(xs_end, ys, ys_it, ys_end); |
| } |
| |
| } // namespace detail |
| |
| template <typename T, typename Alloc, typename Comparator = std::less<T> > |
| void sort(llvm::iplist<T, Alloc>& list, |
| Comparator is_less_than = Comparator()) { |
| detail::sort(list, list.size(), is_less_than); |
| } |
| |
| } // namespace mcld |
| |
| #endif // MCLD_ADT_ILIST_SORT_H_ |