<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Aug 18, 2016 at 8:23 AM, Duncan P. N. Exon Smith via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">+llvm-dev<br>
<span class=""><br>
> On 2016-Aug-18, at 08:02, Abe Skolnik <<a href="mailto:a.skolnik@samsung.com">a.skolnik@samsung.com</a>> wrote:<br>
><br>
>> Thanks for submitting!  I'll likely fix the sort code eventually, so I may use this as a reference.<br>
><br>
</span>> You are welcome.<br>
><br>
> Should I clean it up to comply with style guidelines, forward-port to the latest trunk, and create a proper patch for official submission?<br>
><br>
> Regards,<br>
><br>
> Abe<br>
<br>
IMO list sorts should be:<br>
- O(n lg n) complexity.<br>
- Stable.<br>
<br>
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.)<br></blockquote><div><br></div><div>The one in-tree is a merge sort implementation, it should meet both criteria.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
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:<br>
<span class="im HOEnZb"><br>
>> Another option is to privately split out lower-level versions of some of the functions that avoid triggering the problematic callbacks (my current plan).<br>
<br>
<br>
</span><div class="HOEnZb"><div class="h5">______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div>