Blob Blame History Raw
To: vim_dev@googlegroups.com
Subject: Patch 7.4.358
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------

Patch 7.4.358 (after 7.4.351)
Problem:    Sort is not always stable.
Solution:   Add an index instead of relying on the pointer to remain the same.
	    Idea by Jun Takimoto.
Files:	    src/eval.c


*** ../vim-7.4.357/src/eval.c	2014-07-02 19:06:14.686326091 +0200
--- src/eval.c	2014-07-09 17:42:05.699813489 +0200
***************
*** 17329,17334 ****
--- 17329,17341 ----
  #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,17362 ****
      const void	*s1;
      const void	*s2;
  {
      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);
      if (p1 == NULL)
  	p1 = (char_u *)"";
      if (p2 == NULL)
--- 17356,17372 ----
      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];
  
!     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,17385 ****
      /* 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;
  
      vim_free(tofree1);
      vim_free(tofree2);
--- 17389,17395 ----
      /* When the result would be zero, compare the pointers themselves.  Makes
       * the sort stable. */
      if (res == 0 && !item_compare_keep_zero)
! 	res = si1->idx > si2->idx ? 1 : -1;
  
      vim_free(tofree1);
      vim_free(tofree2);
***************
*** 17394,17399 ****
--- 17404,17410 ----
      const void	*s1;
      const void	*s2;
  {
+     sortItem_T  *si1, *si2;
      int		res;
      typval_T	rettv;
      typval_T	argv[3];
***************
*** 17403,17412 ****
      if (item_compare_func_err)
  	return 0;
  
      /* 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]);
  
      rettv.v_type = VAR_UNKNOWN;		/* clear_tv() uses this */
      res = call_func(item_compare_func, (int)STRLEN(item_compare_func),
--- 17414,17426 ----
      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(&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,17432 ****
      /* 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;
  
      return res;
  }
--- 17440,17446 ----
      /* When the result would be zero, compare the pointers themselves.  Makes
       * the sort stable. */
      if (res == 0 && !item_compare_keep_zero)
! 	res = si1->idx > si2->idx ? 1 : -1;
  
      return res;
  }
***************
*** 17442,17448 ****
  {
      list_T	*l;
      listitem_T	*li;
!     listitem_T	**ptrs;
      long	len;
      long	i;
  
--- 17456,17462 ----
  {
      list_T	*l;
      listitem_T	*li;
!     sortItem_T	*ptrs;
      long	len;
      long	i;
  
***************
*** 17510,17516 ****
  	}
  
  	/* Make an array with each entry pointing to an item in the List. */
! 	ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
  	if (ptrs == NULL)
  	    return;
  
--- 17524,17530 ----
  	}
  
  	/* Make an array with each entry pointing to an item in the List. */
! 	ptrs = (sortItem_T *)alloc((int)(len * sizeof(sortItem_T)));
  	if (ptrs == NULL)
  	    return;
  
***************
*** 17519,17525 ****
  	{
  	    /* sort(): ptrs will be the list to sort */
  	    for (li = l->lv_first; li != NULL; li = li->li_next)
! 		ptrs[i++] = li;
  
  	    item_compare_func_err = FALSE;
  	    item_compare_keep_zero = FALSE;
--- 17533,17543 ----
  	{
  	    /* sort(): ptrs will be the list to sort */
  	    for (li = l->lv_first; li != NULL; li = li->li_next)
! 	    {
! 		ptrs[i].item = li;
! 		ptrs[i].idx = i;
! 		++i;
! 	    }
  
  	    item_compare_func_err = FALSE;
  	    item_compare_keep_zero = FALSE;
***************
*** 17531,17537 ****
  	    else
  	    {
  		/* Sort the array with item pointers. */
! 		qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
  		    item_compare_func == NULL ? item_compare : item_compare2);
  
  		if (!item_compare_func_err)
--- 17549,17555 ----
  	    else
  	    {
  		/* Sort the array with item pointers. */
! 		qsort((void *)ptrs, (size_t)len, sizeof(sortItem_T),
  		    item_compare_func == NULL ? item_compare : item_compare2);
  
  		if (!item_compare_func_err)
***************
*** 17540,17546 ****
  		    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]);
  		}
  	    }
  	}
--- 17558,17564 ----
  		    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].item);
  		}
  	    }
  	}
***************
*** 17559,17565 ****
  	    {
  		if (item_compare_func_ptr((void *)&li, (void *)&li->li_next)
  									 == 0)
! 		    ptrs[i++] = li;
  		if (item_compare_func_err)
  		{
  		    EMSG(_("E882: Uniq compare function failed"));
--- 17577,17583 ----
  	    {
  		if (item_compare_func_ptr((void *)&li, (void *)&li->li_next)
  									 == 0)
! 		    ptrs[i++].item = li;
  		if (item_compare_func_err)
  		{
  		    EMSG(_("E882: Uniq compare function failed"));
***************
*** 17571,17582 ****
  	    {
  		while (--i >= 0)
  		{
! 		    li = ptrs[i]->li_next;
! 		    ptrs[i]->li_next = li->li_next;
  		    if (li->li_next != NULL)
! 			li->li_next->li_prev = ptrs[i];
  		    else
! 			l->lv_last = ptrs[i];
  		    list_fix_watch(l, li);
  		    listitem_free(li);
  		    l->lv_len--;
--- 17589,17600 ----
  	    {
  		while (--i >= 0)
  		{
! 		    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].item;
  		    else
! 			l->lv_last = ptrs[i].item;
  		    list_fix_watch(l, li);
  		    listitem_free(li);
  		    l->lv_len--;
*** ../vim-7.4.357/src/version.c	2014-07-09 14:00:45.175044250 +0200
--- src/version.c	2014-07-09 17:23:12.791836515 +0200
***************
*** 736,737 ****
--- 736,739 ----
  {   /* Add new patch number below this line */
+ /**/
+     358,
  /**/

-- 
An indication you must be a manager:
You can explain to somebody the difference between "re-engineering",
"down-sizing", "right-sizing", and "firing people's asses".

 /// Bram Moolenaar -- Bram@Moolenaar.net -- 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    ///