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

[Duncan P. N. Exon Smith via llvm-dev]

+llvm-dev

> On 2016-Aug-18, at 08:02, Abe Skolnik <a.skolnik at samsung.com> wrote:
> 
>> Thanks for submitting!  I'll likely fix the sort code eventually, so I may use this as a reference.
> 
> You are welcome.
> 
> Should I clean it up to comply with style guidelines, forward-port to the latest trunk, and create a proper patch for official submission?
> 
> Regards,
> 
> Abe

IMO list sorts should be:
- O(n lg n) complexity.
- Stable.

I haven't looked carefully enough at this to be sure it meets these criteria.  Does it?  (It's possible the current in-tree one doesn't either (I haven't bothered to understand it), but if we're going to fix it let's *fix* it.)

I'm also not convinced this is the right direction; using a single list makes it complicated.  My inclination is to split out lower-level merge/sort operations that avoid the calls to transferNodesToList, as I mentioned before:

>> Another option is to privately split out lower-level versions of some of the functions that avoid triggering the problematic callbacks (my current plan).