Jun T wrote: > On 2014/07/03, at 2:06, Bram Moolenaar <[email protected]> wrote: > > > + static int item_compare_keep_zero; > > This variable is set to FALSE for the sort() function, and only set to > TRUE for uniq(). Is this intentional?
Yes, uniq() needs the zero to decide elements are equal. > Even if I set this variable to TRUE for sort(), the sort is still not stable > and test55 fails on my Mac: Setting it to TRUE has the opposite effect. > > + /* When the result would be zero, compare the pointers > > themselves. Makes > > + * the sort stable. */ > > + if (res == 0 && !item_compare_keep_zero) > > + res = s1 > s2 ? 1 : -1; > > + > > This doesn't work, it seems. During the sort process the qsort() > function swaps the data in the array ptrs[]. > Comparing s1 and s2 is to compare the current position in the array, > which may have been already modified (swapped) by qsort(). Right, qsort may move pointers over a larger distance. It did work for the tests I did, but I suppose that's because they start off being next to each other and all undergo the same "large move". It will fail when starting in another order. > I think we need to save the original position along with the data. > See the patch in my previous post (26 June, Re: Patch 7.4.341, the 4th post in > https://groups.google.com/forum/#!topic/vim_dev/RUByys6B3Yk). In this patch, > the original position is saved in the member 'i' of the struct sdata_T. > > I think my patch works, but I guess it will make the sort somewhat slower, > because there are now two function calls per comparison. If this is a problem, > then we could modify item_compare() itself instead of using a wrapper function > item_compare_stable(). Hmm, we need to fill an array with pointers, might as well add an int right after the pointer. Effectively this means sorting this struct: { void *ptr; /* the list element to be sorted */ int idx; /* original position in the list */ } The array will take more space, qsort has larger elements to move around, but otherwise the cost is quite low, we don't need another function call. > PS. > What is the best way of referring to a previous post in this mailing list? A URL to groups.google.com probably works best. -- If your life is a hard drive, Christ can be your backup. /// Bram Moolenaar -- [email protected] -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org /// -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
