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