CODEWITHSUNDEEP
csortingcompile-time
Tomek Sowiński
Tomek Sowiński

Reputation: 863

Can C sort at compile time?

Is it possible to sort elements at compile time in C?

Syntax is of secondary importance, I was thinking of a macro like this:

SORT(9, -1, 12, 4)   // expands to: -1, 4, 9, 12
SORT(dog, cat, cow)  // expands to: cat, cow, dog

but I won't frown at any API as long as it sorts without issuing a single CPU instruction.

The requirements are pretty lax:

I realize the solution will probably resort to some language voodoo that barely compiles, I just want to know if it's possible.

Upvotes: 6

Views: 1283

Answers (3)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Not really, you cannot sort in C at compile time (at least if you want to sort a sufficiently large number of compile-time constant integers; in that case having a 300 macros or functions named SORT_1, SORT_2, ... SORT_300 is not practical, unless you generate these functions or macros, which you do not want to), however....

Pragmatical approach would be to use your own or some other preprocessor (e.g. gpp) and have it do the sort. Or simply, have the numbers in some included file and generate that sorted file (e.g. with a make rule using awk & sort)

You could also consider linking using link-time-optimization to an LTO-compiled libc, using its LTO-optimized qsort. This is not usual, AFAIK, and you have no guarantee that the compiler is smart-enough to inline your LTO qsort etc... (AFAIK, current C compilers don't do that).

If compiling with a recent GCC (4.8, 4.9 or soon 5.0 in march 2015), you could customize it (e.g. with MELT or with your own C++ plugin) to define your __builtin_my_compile_time_sort (or perhaps some _Pragma) to do the job. This is compiler specific (could mean several days of work, unless you know MELT already)

The simplest thing would be to accept slightly complicating the build step. It is not a big deal.

Upvotes: 1

VoidStar
VoidStar

Reputation: 5421

Here is a macro approach:

#define GET_1_of_3(a, b, c) ((a) < (b) ? ((c) < (a) ? (c) : (a)) : ((c) < (b) ? (c) : (b)))
#define GET_2_of_3(a, b, c) ((c) > (a) && (c) < (b) || (c) < (a) && (c) > (b) ? (c) : ((b) > (a) && (b) < (c) || (b) < (a) && (b) > (c) ? (b) : (a)))
#define GET_3_of_3(a, b, c) ((a) > (b) ? ((c) > (a) ? (c) : (a)) : ((c) > (b) ? (c) : (b)))
#define SORT_3(a, b, c) GET_1_of_3(a, b, c),GET_2_of_3(a, b, c),GET_3_of_3(a, b, c)

void main(){
    int x[3] = { SORT_3(6,2,3) };
    printf("%d, %d, %d", x[0], x[1], x[2]);
}

This works for int and works in C, but it's not possible for strings without const_expr from C++. Obviously, you're in for a lot of macro-writing to support a large number of SORT_X.

Upvotes: 7

user4098326
user4098326

Reputation: 1742

Let's consider sorting numbers that can only be 0 or 1. For two numbers, SORT2 in the following code can sort them:

#define SORT2(a,b) SORT2_##a##b
#define SORT2_00 0,0
#define SORT2_01 0,1
#define SORT2_10 0,1
#define SORT2_11 1,1

This can of course be expanded to larger ranges and more arguments.

Upvotes: 3

Related Questions