noporpoise / sort_r Goto Github PK

47.0 5.0 8.0 47 KB

Portable qsort_r / qsort_s

Makefile 2.84% C 95.15% Shell 2.02%

sort_r's Introduction

sort_r

Isaac Turner 2022
Portable qsort_r / qsort_s
Discussion here: http://stackoverflow.com/questions/4300896/how-portable-is-the-re-entrant-qsort-r-function-compared-to-qsort
License: Public Domain - use as you wish, no warranty

About

If you want to qsort() an array with a comparison operator that takes parameters you need to use global variables to pass those parameters (not possible when writing multithreaded code), or use qsort_r/qsort_s which are not portable (there are separate GNU/BSD/Windows versions and they all take different arguments).

So I wrote a portable qsort_r/qsort_s called sort_r():

void sort_r(void *base, size_t nel, size_t width,
            int (*compar)(const void *a1, const void *a2, void *aarg),
            void *arg);

base is the array to be sorted nel is the number of elements in the array width is the size in bytes of each element of the array compar is the comparison function arg is a pointer to be passed to the comparison function

Using sort_r

Add #include "sort_r.h" to the top of your code. Then copy sort_r.h into your working directory, or add -I path/to/sort_r to your compile arguments.

Build Example

Compile example code (example.c) with:

make

To build using nested functions and qsort instead of qsort_r use

make NESTED_QSORT=1

Nested functions are not permitted under ISO C, they are a GCC extension.

License

Public Domain. Use as you wish. No warranty. There may be bugs.

sort_r's People

Contributors

Stargazers

Watchers

Forkers

dajobe mikepb cap artynet srlehn yuuichihosomi zhang197652 hmtheboy154

sort_r's Issues

‘sort_r_arg_swap’ defined but not used warning (gcc/Linux)

Move sort_r_arg_swap and sort_r_data definition to #else block created on line 58 solves the problem.

Dereferencing void *base on 83 line

Hi again, at the 83 line:
qsort_s(*base, nel, width, &sort_r_arg_swap, &tmp);
perhaps it supposed to be:
qsort_s(base, nel, width, &sort_r_arg_swap, &tmp);
I have not tested it in this configuration yet. I hope I'm right.
...and I thanks - your code is better then mine I used to use before…

O(N^2) if all elements are equal

Hi,

I'm using this code in https://github.com/behdad/harfbuzz/, and our fuzzers have found a timeout for us, which I tracked down to this code performing slow. Upon inspection, it's clear that if all array elements are the same, the code performs at its worst case. The median-pivot method helps with the case of array being mostly sorted or reverse-sorted, but doesn't help all-the-same.

Given that elements equal to the pivot can be partitioned on either side, I'm going to modify the code to use that property to choose a more central breaking point. I'll report on my progress. Thanks.

Nallow _SORT_R_BSD condition

In this context, _SORT_R_BSD means qsort_r from FreeBSD,
so it must be defined only for FreeBSD, its forks (DragonFly) and having userland from it (MacOS X).

musl support

So I'm using this repo and it's great! But I tried compiling my project on alpine linux recently, which uses musl, which apparently doesn't provide an implementation of qsort_r. They also don't define any macros AFAIK that let you detect musl.

I'll see if I can think of a nice way to fix it, but it seems like it might just require a flag. I would just #undef some macros to hack it in but none of these look terribly safe to #undef:

#if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || \
     defined __FreeBSD__ || defined __DragonFly__)
#  define _SORT_R_BSD
#elif (defined _GNU_SOURCE || defined __gnu_hurd__ || defined __GNU__ || \
       defined __linux__ || defined __MINGW32__ || defined __GLIBC__)
#  define _SORT_R_LINUX
#elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__)
#  define _SORT_R_WINDOWS
#  undef _SORT_R_INLINE
#  define _SORT_R_INLINE __inline
#else
  /* Using our own recursive quicksort sort_r_simple() */
#endif

Compiling with TDM-GCC on Windows fails - undefined reference to `qsort_r'

OS: Windows 10
Compiler: TDM-GCC-64

Compilation fails with the below error -

sort_r.h:288: undefined reference to `qsort_r'

I was able to fix it by removing the check for __MINGW32__ in the _SORT_R_LINUX definition