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 ///