[llvm-dev] code to sort otherwise-unsortable "ilist"s, e.g. symbol tables

[Abe Skolnik via llvm-dev]

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); }