Can C sort at compile time?

Question

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

The 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 will not click on any API until it is sorted without issuing a single CPU instruction.

The requirements are pretty weak:

• Pure C, not C ++ . Staying in the C standard would be nice, but the installed language extensions were an honest game.
• The compiler is the only tool allowed . Unix sort or source code generators at home are not welcome, as they complicate the build step.
• Any type of item is great . This is normal if it can sort, for example. numbers, but not strings.
• Fixed-length APIs are great . To call SORT_5 to sort 5 items in order.

I understand that the solution is likely to resort to some language wood that barely compiles, I just want to know if this is possible.

Answer 1

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 is not possible for strings without const_expr from C ++. Obviously, you have many macro letters to support a large number of SORT_X .

Answer 2

Consider sorting numbers, which can only be 0 or 1. For two SORT2 numbers in the following code, you 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, of course, can be expanded to larger ranges and more arguments.

Answer 3

Not really, you cannot sort in C at compile time (at least if you want to sort a large enough number of constant integer compile-time values, in this case having 300 macros or functions named SORT_1 , SORT_2 , ... SORT_300 impractical, unless you generate these functions or macros that you don't want), however ....

A pragmatic approach would be to use your own or some other preprocessor (e.g. gpp ) and ask it to execute. Or simply, specify the numbers in some included file and generate this sorted file (for example, using the make rule with awk and sort )

You can also consider linking with link-time-optimization by compiling with LTO libc using LTO-optimized qsort . This is no ordinary AFAIK, and you have no guarantee that the compiler is smart enough to embed your LTO qsort , etc. (AFAIK, current C compilers do not).

If you are compiling with the recent GCC (4.8, 4.9, or soon 5.0 in March 2015), you can configure it (e.g. using MELT or with your own C ++ plugin) to define your __builtin_my_compile_time_sort (or maybe some _Pragma ) to complete the task. This is specific to the compiler (it could mean a few days of work if you don't already know MELT)

The easiest way would be to take a slightly more complicated assembly step. It's not a big problem.