Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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:

  • Pure C, no C++. Staying within the C standard would be nice but established language extensions are fair game.
  • Compiler is the only tool allowed. Unix sort or home-brewed code generators are not welcome as they complicate the build step.
  • Any element type is fine. It's OK if it can sort e.g. numbers but not strings.
  • Fixed-length API is fine. Having to call SORT_5 to sort 5 elements is OK.

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

like image 988
Tomek Sowiński Avatar asked Mar 25 '15 23:03

Tomek Sowiński


2 Answers

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.

like image 188
VoidStar Avatar answered Oct 23 '22 17:10

VoidStar


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.

like image 34
user4098326 Avatar answered Oct 23 '22 18:10

user4098326