[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?
IMO list sorts should be:
- O(n lg n) complexity.
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