Problems with Swenson's Timsort implementation while sorting structs

Question

I found Swenson's C implementation of Timsort: https://github.com/swenson/sort mentioned in one of the older SO questions.

I encountered two problems:

1)To use it I need to define SORT_CMP macro suitable for the type I want to sort. My type is defined as (a bit simplified here):

typedef struct{
    int a;
    int b;
} MyType

I try to define:

#define SORT_TYPE MyType
#define SORT_CMP(x,y) (x.a - y.a)

but I keep getting an error: "request for member 'a' in something not a structure or union" I thought that maybe x and y will be pointers but:

#define SORT_CMP(x,y) (x->a - y->a)

doesn't work either. Could you please help me with that? I am C newbie and probably missing something basic.

2)Is there any way to compile that code in Visual Studio ? It uses stuff from newer C standard (like declarations in the middle of the block) and cl.exe doesn't accept it. I compiled it using GCC (mingw) but mingw is 20% slower for the rest of my code than VC (with O2 or O3 flag vs lc.exe with /Ox) so any gains which I could have from using Timsort instead of stdlib qsort won't make up for that. The same goes for Pelles compiler. Most of my data has a lot of partially sorted sequences and sorting takes about 50% of the execution time so I feel there is gain to make here assuming I make it work in VC.

Answer 1

You might try adding parentheses around the macros parameters like so:

#define SORT_CMP(x,y) ((x).a - (y).a)

Most probably the macro is used with a dereferenced pointer to a SORT_TYPE variable:

SORT_TYPE * pMyTypeVar1, pMyTypeVar2;
...
SORT_CMP(*pMyTypeVar, *pMyTypeVar2);

If then those parentheses around the macro's parameters are missing the preprocessor produces something like this:

(*pMyTypeVar1.a - *pMyTypeVar2.a)

And as the dot-operator binds tighter than the star-operator the compiler tries to find the member a for the pointers pMyTypeVar1 and pMyTypeVar2 which won't work.

Using parentheses as proposed would lead to:

((*pMyTypeVar1).a - (*pMyTypeVar2).a)

This way the compiler first dereferences pMyTypeVar1 and pMyTypeVar2 and finally is able to find member a.