Re: [PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.
Jan Dubiec <[email protected]>
| Newsgroups | gmane.comp.gdb.patches |
|---|---|
| Message-ID | <[email protected]> |
On 22.08.2026 13:02, Jan Dubiec wrote: > See the comment below. I don't know why qsort behaves so strangely. It > could be a bug, or simply a consequence of its being an unstable sort. > Unfortunately, I don't have time to investigate the root cause. OK, I did some testing that shows that Microsoft's implementation of qsort() uses an unstable sorting algorithm, i.e. the order of equal elements may change. See the attached program. It compares insertion sort, which is a stable algorithm, with qsort(). The test fails on Windows and passes on Linux. The compiler is irrelevant — both Microsoft's compiler and GCC from MinGW produce the same result. It's worth noting that although the test passes on Linux, this is not guaranteed. According to AI, the qsort() implementation in glibc generally uses merge sort (stable), but may fall back to heapsort (unstable), depending on the size of the data. The glibc documentation seems to confirm this — it clearly states that "If two elements compare equal, their order after sorting is unpredictable": https://sourceware.org/glibc/manual/2.44/html_node/Array-Sort-Function.html So I think the best solution is to use a sorting algorithm known to be stable on every host, e.g. the insertion sort implementation from my previous message. What do you think? /J.D.
qsort_test.c
(text/plain, 2.2 KB)
/*
* Compile commad: gcc -O2 -s -o qsort_test.exe qsort_test.c
* or cl /O2 /Fe:qsort_test.exe qsort_test.c
* Usage: qsort_test.exe [-d]
* -d - dump tables to stdout
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TABLESIZE 5
typedef struct {
int f1;
int f2;
int f3;
} element_type;
static int
element_comparator (const void *el1, const void *el2)
{
element_type *p1 = (element_type*) el1;
element_type *p2 = (element_type*) el2;
/* Only f1 and f2 are used as sort keys; f3 is irrelevant. */
if (p1->f1 != p2->f1)
return (p1->f1 > p2->f1) - (p1->f1 < p2->f1);
if (p1->f2 != p2->f2)
return (p1->f2 > p2->f2) - (p1->f2 < p2->f2);
return 0;
}
static void
insertion_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *a = base;
unsigned char *tmp;
size_t i, j;
if (nmemb < 2 || size == 0)
return;
tmp = malloc(size);
if (tmp == NULL)
return;
for (i = 1; i < nmemb; ++i) {
memcpy(tmp, a + i * size, size);
j = i;
while (j > 0 && compar(tmp, a + (j - 1) * size) < 0) {
memcpy(a + j * size, a + (j - 1) * size, size);
--j;
}
memcpy(a + j * size, tmp, size);
}
free(tmp);
}
int main (int argc, char *argv[])
{
element_type t0[TABLESIZE] = {
{0, 0, 10}, {7, 7, 10}, {5, 5, 10}, {7, 7, 5}, {0, 0, 11}
};
element_type t1[TABLESIZE], t2[TABLESIZE];
size_t i;
memcpy(t1, t0, TABLESIZE*sizeof(element_type));
memcpy(t2, t0, TABLESIZE*sizeof(element_type));
insertion_sort(t1, TABLESIZE, sizeof(element_type), element_comparator);
qsort(t2, TABLESIZE, sizeof(element_type), element_comparator);
/* Dump tables to stdout */
if (argc > 1 && argv[1][0] == '-' && argv[1][1] == 'd') {
for (i = 0; i < TABLESIZE; ++i) {
printf("t0[%zu]:\t%d\t%d\t%d\n", i, t0[i].f1, t0[i].f2, t0[i].f3);
printf("t1[%zu]:\t%d\t%d\t%d\n", i, t1[i].f1, t1[i].f2, t1[i].f3);
printf("t2[%zu]:\t%d\t%d\t%d\n\n", i, t2[i].f1, t2[i].f2, t2[i].f3);
}
}
for (i = 0; i < TABLESIZE; ++i) {
if ( memcmp(&t1[i], &t2[i], sizeof(element_type)) ) {
printf("First fail at element %zu\n", i);
printf("FAIL\n");
return -1;
}
}
printf("PASS\n");
return 0;
}