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
17namespace mcld {
18
19namespace detail {
20
21template <typename T, typename Alloc, typename Comparator>
22void 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
76template <typename T, typename Alloc, typename Comparator = std::less<T> >
77void 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