diff options
author | Bram Moolenaar <Bram@vim.org> | 2014-07-09 17:51:51 +0200 |
---|---|---|
committer | Bram Moolenaar <Bram@vim.org> | 2014-07-09 17:51:51 +0200 |
commit | 6bf5548df2d58215c99d582269b4ec9e7fb0c934 (patch) | |
tree | 3d2561afe222e42524f536e65cb46348d1cae9f3 /src/eval.c | |
parent | 0bed10a813a0b0d748f69dd52306b1b7d26b71fb (diff) |
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.
Diffstat (limited to 'src/eval.c')
-rw-r--r-- | src/eval.c | 50 |
1 files changed, 34 insertions, 16 deletions
diff --git a/src/eval.c b/src/eval.c index 84a798c7cc..aedbaa4ce0 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--; |