Alles in Ordnung

Perl returns its hash values in a random order. Since 5.14 or so, the random order changes every time. So if you loop over your hash values, you get a different ordering each time.

for my $k (keys %hash) { }

No problem you say, I'll use sort to order my keys.

for my $k (sort keys %hash) { }

But what if you want to use a non-default order, like case-insensitive? Easy-peasy you claim.

for my $k (sort {uc ($a) cmp uc ($b)} keys %hash) { }

Now here's my problem. I'm using XS to loop through the hash, and I want to sort the keys in the hash according to the user's preference.

Well, there must be a way to sort things with the Perl API mustn't there? Well, there is something called sortsv_flags which wants a user-defined sorting routine of the type SVCOMPARE_t. So if I stuff the hash keys into an array of pointers, then I can sort them using Perl's default sorting if I use Per's default sorting routine, which is called Perl_sv_cmp. So that is that "sorted".

However, what if I want to allow a user-defined ordering in my XS program? I had a look with Google and with grep cpan but I couldn't find a lot of information, or an example of an XS module which does this. Writing a callback to call the Perl function from C is documented in perlcall, but it's not at all clear to me how I can set the user-defined function within my SVCOMPARE_t function, since there seems to be no way to pass my object into that.

The way I would do this in C is by using qsort_r, which allows me to pass a pointer to a void * which I can fill with anything I want to. The easiest way to go seems to be to use that, but qsort_r is another can of worms, since it is not standardised.

qsort_r started out on BSD, then Gnu implemented it, but Gnu had a bright idea of putting the arguments in the opposite order to BSD. Then Bill Gates came along and thought he would implement it too for his "Windows" operating system, but he decided to call it qsort_s, but with some of the arguments in the same order as Gnu, and some of the arguments in the same order as BSD. 👷‍

Some bright spark figured this all out though and made some macros, which you can find on github, which do it all for you and give you a universal qsort_r-like function. That would be great, except the macros don't actually work on 🍓 Strawberry Perl, since that looks too much like a Gnu environment, and changing the macros so that they give the correct definition of qsort_s, I then found out that some versions of Windows don't even seem to have the qsort_s function.

Thankfully the 👑 Regents of the University of California 👑 have made their operating system open source, so what I did in the end is just to copy the BSD qsort_r source code into my module, give it a different name, and voila, I now have reliable user-defined sorting in the module, and it seems to work OK so far.

But is this really the best possible solution? Is there not some kind of clever trick that one can use to access the Perl sorting with a user-defined function from XS, and get all the $a and $b stuff too?

2 Comments

You’re looking for the code in pp_sort, aren’t you? After all, you want to offer basically the same interface as Perl’s sort. That suggests to go looking at its implementation.

Looking at pp_sort itself, a lot of it isn’t implemented in terms of intermediate functions you could reuse. So it looks like you’re either going to have to copy-paste a fair chunk of it (and maybe more than a fair chunk if you’re looking to replicate some of its optimisations) or else arrange to call it (which I don’t know how easy that will be… does it want to look at the optree and therefore force you to mock up enough of one to make it go?).

Leave a comment

About Ben Bullock

user-pic Perl user since about 2006, I have also released some CPAN modules.