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