Re: [PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[Jan Dubiec <jdx@o2.pl>]

[-- Attachment #1: Type: text/plain, Size: 1326 bytes --]

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.

[-- Attachment #2: qsort_test.c --]
[-- Type: text/plain, Size: 2299 bytes --]

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