Dear all,
The below has been tested quite thoroughly by now, including performance-testing by the way of using a modified compiler that triggers the below while compiling at least an old part of LLVM ["Function.cpp"] and sorting a symbol table with >7000 global variables.
Unfortunately, the optimization I have been working on for which I _thought_ I needed the ability to sort a symbol table is showing poor performance numbers [from the compiled code, not the compiler itself], so I think I probably won`t submit that, at least not in its present form -- maybe in a much-more-limited form that doesn`t need the sorting. However, I thought this sorting code might be useful to somebody else, so here it is for feedback.
Maybe somebody wants to add the needed glue code so e.g. "my_ilist.sort()" will call the below rather than invoking the relevant ancestor-class "sort()" and crashing? If so, then ditto for e.g. "my_ilist.sort(my_comparator)", please.
Regards,
Abe
===== snippet from altered "llvm/include/llvm/ADT/ilist.h" =====
===== context within "ilist.h": the 2nd "public:" section of "template<typename NodeTy, typename Traits=ilist_traits<NodeTy> > class iplist : public Traits" =====
template <class Compare>
void sort_without_temporary_list(Compare comp) {
// The list is empty, vacuously sorted.
if (empty())
return;
// The list has a single element, vacuously sorted.
if (std::next(begin()) == end())
return;
iterator last_sorted{begin()};
iterator just_after_last_sorted{std::next(last_sorted)};
while (end() != just_after_last_sorted) {
while ( (end() != just_after_last_sorted) && ! comp(*just_after_last_sorted, *last_sorted) ) {
// advance the frontier by one element
++just_after_last_sorted;
++ last_sorted;
} // this loop _must_ come _before_ the code to figure out how many elem.s to splice and where to splice them to [place-marker: NOTE 668]
if (end() != just_after_last_sorted) { // check again in case advancing the frontier finished the job
// first, find the insertion point for the first-past-the-frontier elem.
iterator insertion_point{begin()};
while ( ! comp(*just_after_last_sorted, *insertion_point) ) ++insertion_point;
// set up some needed iterators
const iterator just_after_insertion_point{std::next(insertion_point)};
iterator prev_elem_checked_for_order_in_sublist_to_splice{ just_after_last_sorted};
iterator just_after_last_elem_in_sublist_to_splice{std::next(just_after_last_sorted)};
// try to make {the sublist to be spliced} as long as it can be while still being correct
while ( (end() != just_after_last_elem_in_sublist_to_splice) && // ...
/*...*/ ( ! comp(*just_after_insertion_point, *just_after_last_elem_in_sublist_to_splice) ) &&
/*...*/ ! comp(*just_after_last_elem_in_sublist_to_splice, *prev_elem_checked_for_order_in_sublist_to_splice) ) {
// extend the to-splice sublist by one element "to the right"
++prev_elem_checked_for_order_in_sublist_to_splice;
++just_after_last_elem_in_sublist_to_splice;
}
splice(insertion_point, *this, just_after_last_sorted, just_after_last_elem_in_sublist_to_splice);
just_after_last_sorted = std::next(last_sorted); // refresh the iterator so it points to whatever is now just past the frontier
// We don`t need to refresh the iterator "last_sorted" b/c this is a linked list...
// and we definitely did not insert at the frontier [see NOTE 668].
} // end if
} // end while
} // end of "sort_without_temporary_list(Compare comp)"
void sort_without_temporary_list() { sort_without_temporary_list(op_less); }
