updated for version 7.4.358v7.4.358

Problem:    Sort is not always stable.
Solution:   Add an index instead of relying on the pointer to remain the same.
            Idea by Jun Takimoto.

1 files changed, 34 insertions, 16 deletions

diff --git a/src/eval.c b/src/eval.c
index 84a798c7c..aedbaa4ce 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -17329,6 +17329,13 @@ static int
 #endif
 	item_compare2 __ARGS((const void *s1, const void *s2));
 
+/* struct used in the array that's given to qsort() */
+typedef struct
+{
+    listitem_T	*item;
+    int		idx;
+} sortItem_T;
+
 static int	item_compare_ic;
 static int	item_compare_numeric;
 static char_u	*item_compare_func;
@@ -17349,14 +17356,17 @@ item_compare(s1, s2)
     const void	*s1;
     const void	*s2;
 {
+    sortItem_T  *si1, *si2;
     char_u	*p1, *p2;
     char_u	*tofree1, *tofree2;
     int		res;
     char_u	numbuf1[NUMBUFLEN];
     char_u	numbuf2[NUMBUFLEN];
 
-    p1 = tv2string(&(*(listitem_T **)s1)->li_tv, &tofree1, numbuf1, 0);
-    p2 = tv2string(&(*(listitem_T **)s2)->li_tv, &tofree2, numbuf2, 0);
+    si1 = (sortItem_T *)s1;
+    si2 = (sortItem_T *)s2;
+    p1 = tv2string(&si1->item->li_tv, &tofree1, numbuf1, 0);
+    p2 = tv2string(&si2->item->li_tv, &tofree2, numbuf2, 0);
     if (p1 == NULL)
 	p1 = (char_u *)"";
     if (p2 == NULL)
@@ -17379,7 +17389,7 @@ item_compare(s1, s2)
     /* 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;
+	res = si1->idx > si2->idx ? 1 : -1;
 
     vim_free(tofree1);
     vim_free(tofree2);
@@ -17394,6 +17404,7 @@ item_compare2(s1, s2)
     const void	*s1;
     const void	*s2;
 {
+    sortItem_T  *si1, *si2;
     int		res;
     typval_T	rettv;
     typval_T	argv[3];
@@ -17403,10 +17414,13 @@ item_compare2(s1, s2)
     if (item_compare_func_err)
 	return 0;
 
+    si1 = (sortItem_T *)s1;
+    si2 = (sortItem_T *)s2;
+
     /* Copy the values.  This is needed to be able to set v_lock to VAR_FIXED
      * in the copy without changing the original list items. */
-    copy_tv(&(*(listitem_T **)s1)->li_tv, &argv[0]);
-    copy_tv(&(*(listitem_T **)s2)->li_tv, &argv[1]);
+    copy_tv(&si1->item->li_tv, &argv[0]);
+    copy_tv(&si2->item->li_tv, &argv[1]);
 
     rettv.v_type = VAR_UNKNOWN;		/* clear_tv() uses this */
     res = call_func(item_compare_func, (int)STRLEN(item_compare_func),
@@ -17426,7 +17440,7 @@ item_compare2(s1, s2)
     /* 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;
+	res = si1->idx > si2->idx ? 1 : -1;
 
     return res;
 }
@@ -17442,7 +17456,7 @@ do_sort_uniq(argvars, rettv, sort)
 {
     list_T	*l;
     listitem_T	*li;
-    listitem_T	**ptrs;
+    sortItem_T	*ptrs;
     long	len;
     long	i;
 
@@ -17510,7 +17524,7 @@ do_sort_uniq(argvars, rettv, sort)
 	}
 
 	/* Make an array with each entry pointing to an item in the List. */
-	ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
+	ptrs = (sortItem_T *)alloc((int)(len * sizeof(sortItem_T)));
 	if (ptrs == NULL)
 	    return;
 
@@ -17519,7 +17533,11 @@ do_sort_uniq(argvars, rettv, sort)
 	{
 	    /* sort(): ptrs will be the list to sort */
 	    for (li = l->lv_first; li != NULL; li = li->li_next)
-		ptrs[i++] = li;
+	    {
+		ptrs[i].item = li;
+		ptrs[i].idx = i;
+		++i;
+	    }
 
 	    item_compare_func_err = FALSE;
 	    item_compare_keep_zero = FALSE;
@@ -17531,7 +17549,7 @@ do_sort_uniq(argvars, rettv, sort)
 	    else
 	    {
 		/* Sort the array with item pointers. */
-		qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
+		qsort((void *)ptrs, (size_t)len, sizeof(sortItem_T),
 		    item_compare_func == NULL ? item_compare : item_compare2);
 
 		if (!item_compare_func_err)
@@ -17540,7 +17558,7 @@ do_sort_uniq(argvars, rettv, sort)
 		    l->lv_first = l->lv_last = l->lv_idx_item = NULL;
 		    l->lv_len = 0;
 		    for (i = 0; i < len; ++i)
-			list_append(l, ptrs[i]);
+			list_append(l, ptrs[i].item);
 		}
 	    }
 	}
@@ -17559,7 +17577,7 @@ do_sort_uniq(argvars, rettv, sort)
 	    {
 		if (item_compare_func_ptr((void *)&li, (void *)&li->li_next)
 									 == 0)
-		    ptrs[i++] = li;
+		    ptrs[i++].item = li;
 		if (item_compare_func_err)
 		{
 		    EMSG(_("E882: Uniq compare function failed"));
@@ -17571,12 +17589,12 @@ do_sort_uniq(argvars, rettv, sort)
 	    {
 		while (--i >= 0)
 		{
-		    li = ptrs[i]->li_next;
-		    ptrs[i]->li_next = li->li_next;
+		    li = ptrs[i].item->li_next;
+		    ptrs[i].item->li_next = li->li_next;
 		    if (li->li_next != NULL)
-			li->li_next->li_prev = ptrs[i];
+			li->li_next->li_prev = ptrs[i].item;
 		    else
-			l->lv_last = ptrs[i];
+			l->lv_last = ptrs[i].item;
 		    list_fix_watch(l, li);
 		    listitem_free(li);
 		    l->lv_len--;