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

Duncan P. N. Exon Smith via llvm-dev llvm-dev at lists.llvm.org
Thu Aug 18 08:23:41 PDT 2016


> 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). 

More information about the llvm-dev mailing list