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

[David Majnemer via llvm-dev]

On Thu, Aug 18, 2016 at 8:23 AM, Duncan P. N. Exon Smith via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

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

The one in-tree is a merge sort implementation, it should meet both
criteria.


>
> 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).
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160818/c7dc1136/attachment.html>