Implement generic swap macro in C

Question

Possible Duplicate:
is there an equivalent of std::swap() in c

Hi folks,

I was attempting a problem to write a generic swap macro in C and my macro looks like this:

#define swap(x,y) { x = x + y; y = x - y; x = x - y; }

It works fine for integers and floats but I am unsure if there is any catch in it. What if by generic macro they mean swapping pointers, characters etc ? Can anyone help me with writing a generic macro for swapping every input ?

Thanks

Solution 1

This works well only with integers.

For floats it will fail (e.g. try running it with a very large float and a very small one).

I would suggest something as follows:

#define swap(x,y) do \ 
   { unsigned char swap_temp[sizeof(x) == sizeof(y) ? (signed)sizeof(x) : -1]; \
     memcpy(swap_temp,&y,sizeof(x)); \
     memcpy(&y,&x,       sizeof(x)); \
     memcpy(&x,swap_temp,sizeof(x)); \
    } while(0)

memcpy is pretty optimized when the amount to copy is known at compilation time. Also, there's no need to manually pass a type name or use compiler specific extensions.

Solution 2

You can do something like this:

#define SWAP(x, y, T) do { T SWAP = x; x = y; y = SWAP; } while (0)

which you would then invoke like this:

SWAP(a, b, int);

or:

SWAP(x, y, float);

If you are happy to use gcc-specific extensions then you can improve on this like so:

#define SWAP(x, y) do { typeof(x) SWAP = x; x = y; y = SWAP; } while (0)

and then it would just be:

SWAP(a, b);

or:

SWAP(x, y);

This works for most types, including pointers.

Here is a test program:

#include <stdio.h>

#define SWAP(x, y) do { typeof(x) SWAP = x; x = y; y = SWAP; } while (0)

int main(void)
{
    int a = 1, b = 2;
    float x = 1.0f, y = 2.0f;
    int *pa = &a;
    int *pb = &b;

    printf("BEFORE:\n");
    printf("a = %d, b = %d\n", a, b);
    printf("x = %f, y = %f\n", x, y);
    printf("pa = %p, pb = %p\n", pa, pb);

    SWAP(a, b);     // swap ints
    SWAP(x, y);     // swap floats
    SWAP(pa, pb);   // swap pointers

    printf("AFTER:\n");
    printf("a = %d, b = %d\n", a, b);
    printf("x = %f, y = %f\n", x, y);
    printf("pa = %p, pb = %p\n", pa, pb);

    return 0;
}

Solution 3

GMan started this attempt, to code this in combination of an inline function and a macro. This solution supposes that you have modern C compiler that supports C99, since it uses a compound literal:

inline void swap_detail(void* p1, void* p2, void* tmp, size_t pSize)
{
   memcpy(tmp, p1, pSize);
   memcpy(p1, p2, pSize);
   memcpy(p2 , tmp, pSize);
}
#define SWAP(a, b) swap_detail(&(a), &(b), (char[(sizeof(a) == sizeof(b)) ? (ptrdiff_t)sizeof(a) : -1]){0}, sizeof(a))

This has the following properties:

• It evaluates each of a and b only once.
• It has a compile time check for the correct sizes.
• It has no naming issue with a hidden variable.
• The size of the temporary variable is computed at compile time, so the compound literal is not a dynamic array.

The cast (ptrdiff_t) is needed such that the -1 is not silently promoted to SIZE_MAX.

This solution still suffers from two drawbacks:

1. It is not type safe. It only checks for the sizes of the types, not their semantics. If the types differ, say a double of size 8 and a uint64_t, you are in trouble.

2. The expressions must allow the & operator to be applicable. Thus it will not work on variables that are declared with the register storage class.

Solution 4

Simply put: you cannot make a generic swap macro in C, at least, not without some risk or headache. (See other posts. Explanation lies below.)

Macros are nice, but the problem you'll run into with actual code would be data type issues (as you've stated). Furthermore, macros are "dumb" in a way. For example:

With your example macro #define swap(x,y) { x = x + y; y = x - y; x = x - y; }, swap(++x, y) turns into { ++x = ++x + y; y = ++x - y; ++x = ++x - y;}.

If you ran int x = 0, y = 0; swap(++x, y); you'd get x=2, y=3 instead of x=0, y=0. On top of this, if any of the temp variables in your macro appear in your code, you could run into some annoying errors.

The functionality you're looking for were introduced in C++ as templates. The closest you can get in C is using an inline function for each data type imaginable or a decently complex macro (see previous macro issues and previous posts).

Here's what that the solution using templates in C++ looks like:

template<typename T>
inline void swap(T &x, T &y)
{
    T tmp = x;
    x = y; y = tmp;
}

In C you'd need something like:

inline void swap_int(int *x, int *y) { /* Code */ }
inline void swap_char(char *x, char *y) { /* Code */ }
// etc.

or (as mentioned a few times) a fairly complex macro which has potential to be hazardous.

View more solutions

Comments

[Oliver Charlesworth]

-1 purely on the basis that the XOR swap algorithm is never the correct answer...

[JaredPar]

@Oli, that is in fact a terrible reason to downvote. It is a completely valid answer to the problem of swapping integers.

[nmichaels]

Fast, clear, correct. +1

[Oliver Charlesworth]

@JaredPar: I agree it works, but it doesn't solve the OP's problem of a generic swap macro, and using XOR to swap is a really grim idea, unless you're writing ultra-optimised assembler on particular platforms. The other answers that suggest using temp variables are far more appropriate...

[JaredPar]

@Oli, did I say it would solve the OP's problem? No. I pointed out that even the solution for int was incorrect (OP asserted otherwise) and gave a solution for the problem of int (and explicitly stated it was for int). Other answers being more complete (they all have their issues) is not a reason to downvote a different valid answer. It's a reason to upvote theres

[R.. GitHub STOP HELPING ICE]

+1 for the only correct answer than does not require passing the type as an argument to the macro.

[GManNickG]

Why not make that swap_temp[sizeof(x) == sizeof(y) ? sizeof(x) : -1]. You'll get a generic buffer and compile-time check that they're the same.

[GManNickG]

@Oli: Or ultra-slow assembler. Using a temporary is faster on modern CPU's.

[Oliver Charlesworth]

@GMan: Yes, it only helps on simple CPUs (but not necessarily non-modern).

[Matti Virkkunen]

@Oli: Presumably from the assumption that it will be enough for any type one would use such a macro with.

[Oliver Charlesworth]

@JaredPar: Then this would be better suited as a comment, rather than an answer, IMHO.

[adamk]

@Matti: that's what I originally meant, but it's actually not true (e.g .structs)

[You]

I'm curious; why the do{}while(0) construct? To combat macro expansion issues?

[Paul R]

@You: it's a canonical form for macros which addresses the problem of an invalid ; in an if/else construct. If you take away the do/while (0) then an expression such as if (foo) SWAP(x, y); else SWAP(a, b); will generate an error, as it expands to if (foo) { ... }; else { ... };, and the }; immediately before the else will generate a compile error.

[R.. GitHub STOP HELPING ICE]

By the way, is there a way with C99 compound literals to perform this operation all as a single expression with no temporary variable, exploiting return values of memcpy?

[Matti Virkkunen]

@adamk: That's why I called it an assumption.

[JaredPar]

This will silently fail if my variable name is swap_temp.

[JaredPar]

@GMan, @Oli the temporary solutions provided in other answers are flawed. They all fail silently in the case where the temporary has the same name as the decided upon name in the macro.

[Paul R]

@JaredPar: good point - I've now updated my macro to avoid this problem.

[JaredPar]

@Paul, the new code avoids this problem but only works if variables are used. It's not possible values which result from expressionsn (pointer dereference for example). The plus side though is it forces a compilation error instead of silently compiling and failing.

[Paul R]

@JaredPar: true - this can be fixed though using the token pasting technique in my solution.

[Paul R]

@JaredPar: another good point - just goes to reinforce the collective wisdom as to why macros should be avoided. ;-)

[GManNickG]

@Jared: That's only an issue because we're using macro's. There's no way around it, AFAIK, except to say "don't be stupid and use the name swap_temp".

[JaredPar]

@GMan, See @Paul`s solution. It has flaws (can't use dereferenced pointers) but it will either 1) work or 2) fail to compile. I would prefer a less functioning solution that doesn't silently fail.

[GManNickG]

@Jared: That's pretty annoying, though. I'd rather decorate the name like _swap_temp_do_not_use_this_name_ and call it good.

[strager]

@R.., Couldn't temporary void * variables be used to store &x and &y (evaluating x and y only once each)? That seems less of a hack to me. EDIT: Actually, I misread your comment; my suggestion seems to be going against what you had in mind. ;P

[JaredPar]

@GMan agreed it's annoying but C/C++ is confusing enough without introducing macros that can silently fail.

[GManNickG]

@Jared: Do you really think it's going to be a problem with such a decorated name? I added an answer regardless, attempting to solve it.

[JaredPar]

@GMan, Yes and here's a real scenario where I've seen it happen (not specifically with swap but with other macros that ended up with conflicts). Developer A: writes the solution with the name you specified. Developer B: sees Developers A solution and says "wow, great temp name" and re-uses it. Developer C uses B's macro in combination with A's. Boom.

[GManNickG]

@Jared: Then Developer B is the moron, here. Why on Earth, implementing some other thing, would I use the name _swap_temp_do_not_use_this_name_ as a "great temp name"; it has swap_temp in it! Blaming Developer A for "allowing it to silently fail" is about as backwards as it gets. It's not his job to protect against Machiavelli, only Murphy.

[JaredPar]

@GMan, I still blame developer A. They presented a solution which has a flaw and a solution but chose to check-in the flaw. The amount of time we've debated this in comments is much more than it would take to actually fix the problem.

[GManNickG]

@Jared: What's your fix? I seriously don't see a problem. The problem is your team had someone that stupid on it, to be frank.

[JaredPar]

@GMan, nitpick: not my team, bug I was tracking down in another's code base. For the fix I would choose 1) not a macro 2) your or Paul's solution. Corner cases like this, when hit are absolute nightmares to track down. IMHO it's well worth the extra few minutes to eliminate the silent failure.

[GManNickG]

I like how terse it is, I didn't know you could do that with arrays.

[ysap]

+1 for "not without some risk or headache"

[Jens Gustedt]

No, your so-said C solution at the end isn't one, references are not part of C.

[Jens Gustedt]

@adamK: as it is now, the expression of the array bound may silently promote the -1 to SIZE_MAX. You'd have to cast the second sizeof(x) to a signed type to make this trick work.

[Puppy]

@JaredPar: C/C++ is not this confusing. It's a C specific flaw. C and C++ are different languages, if you can't see how this kind of problem never happens in C++, you need to read another book on it.

[Jens Gustedt]

@Secure: sure just your snipsets perfectly demostrate the dangers. First of all it only assumes that the three types in question are assignment compatible. You easily will have loss of information if the types differ by accident. For your first snipset you should at least go with C99 and declare tmp there where you use it. This would at least document what type you expect. The second snipset is even worse, since it doesn't even permit the declaration at the same place. It shows how error prone this is.

[Jens Gustedt]

@R.: With compound literals yes, but not with the returns of memcpy (at least I didn't find one), but with an auxiliary inline function. Such a thing easily produces optimized code; see my answer (which took up the idea of GMan).

[Secure]

@Jens: When you use an argument, then try it for both sides. If assignment compatibility is an issue at the local scope I've used here, how critical and dangerous will it become at the global scope used in the other solutions? None of them does a type compatibility check for x and y except for the sizeof, as far as I've seen, swapping pointers with ints without a warning. Your solution included.

[Jens Gustedt]

@Secure: you are right that all these solutions suffer for types that have the same size but different semantics. But at least they check for size compatibility, yours doesn't. The problem I had in mind was a quite simple one, where e.g a is size_t and b is int. This may work for years until you encounter a buggy case. I'll add a remark for that to my solution.

[Secure]

@Jens: Well, these are three simple direct assignments a = b;, no complex calculations with type conversions and all that involved. Writing bugs just happens, but seriously, if you can't get this right on a regular basis, then you won't be able to write any working program beyond the complexity of Hello World, IMHO. You're talking about a general problem here, not specific to swap. How will you ever be able to guarantee the type correctness of arguments given to a function? The very same problem, but much better hidden than in the direct assignment.

[Jens Gustedt]

@Secure: I personally find function calls much more readable. Passing on wrongly typed arguments usually clearly shows up in a debugger, e.g. But it seem that we just disagree on that point. Be it so.

[Secure]

@Jens: As I've said, when using an argument then try it for both sides. ;) The wrong tmp type doesn't show up in a debugger?

[Jens Gustedt]

@Secure: yeah look at both sides ;-) Sure the tmp shows up in a debugger, if you suspect it to be the culprit. Call stacks with the arguments that the functions receive appear more directly, without asking for them. I'd call that the advantage of a modular design... But your mileage seems to be different from mine.

[JaredPar]

@DeadMG, sorry you are incorrect. C++ like C has macros and hence can have the exact same flaw.

[Mr. Llama]

Whoops! Thanks for pointing that out. Meant for those to be pointers. Will tweak it.

[Puppy]

@JaredPar: Except that you don't need or want a macro to do this in C++, thus instantly avoiding the problem. Infact, there is such a thing as std::swap(), which has none of these issues.

[JaredPar]

@DeadMG, the discussion is on how to properly implement a swap macro and my arguments hold with the language being C or C++. The discussion is not "what is the best swap routine". If it was then yes std::swap is clearly a winner.

[Puppy]

@JaredPar: A flaw in macros is only a flaw in the language if you actually use macros. Flaws in macros like this are supserseded by the template system. Trying to suggest that C++ fails because a specific macro can't be implemented easily but it's functionality could be very easily duplicated in a far superior fashion with another language feature is plain wrong. It's like complaining about doing addition in binary by hand and ignoring the in-built arithmetic datatypes. You've taken a limitation of one system that was explicitly designed around in another system and called it a language limit.

[JaredPar]

@DeadMG, no. I've taken a language feature available in 2 related languages and pointed out a flaw in the usage of that feature which is applicable to both languages. Again, this is not a discussion on what is the best approach to problem X, it is a discussion of how to best implement a solution with feature Y.

[Puppy]

The question was not "how to implement a swap macro", it's "how to implement a swap macro in C". In C++, you don't implement a swap macro. It's that simple. This question does not concern or relate to C++. Talking about C/C++, especially in this specific context when C++ takes a totally different approach to the same problem, is incredibly wrong.

[tomlogic]

The C solution is still not C. You can't have multiple definitions of a function with different parameters defined. Maybe swap_int(), swap_char(), etc.?

[Mr. Llama]

Man, they really didn't teach us this kind of stuff in school. Thanks for the tips guys.

[Ilian Zapryanov]

Why is the do{}while() loop in the code? Won`t a simple block execute?

[Sohaib]

@adamk Can you please explain why the sizeof function works here but not if I write this is as general function instead of a macro.

[ideasman42]

temp##x##y is going to cause problems for otherwise valid expressions such as SWAP(a->b, c.d); or SWAP(a[0], a[1]);

[Paul R]

@ideasman42: good point - I need to think of a better way to generate a relatively unique name for the temporary - any ideas ?

[ideasman42]

@Paul R, Call the variable SWAP, confusing but works :)

[Paul R]

@ideasman42: now that is fiendishy clever - I like it - I'll update the answer to use this instead of the token pasting kludge if you don't mind.

[ideasman42]

@Paul R, jokes aside, shadowing variables is allowed in C. so even if you get a naming collision, its not going to fail since its in a nested block, unless you explicitly enable -Werror=shadow or similar.

[Paul R]

@ideasman42: yes, it wasn't so much shadowing that this kludge was trying to address though - the problem is that if one of the parameters is called say "temp" and the local temporary variable is also called "temp" then it breaks, hence the need to use a name which is as close to unique as possible. (This could even happen with a temporary named "SWAP" of course, but it's highly unlikely that anyone would have a variable named "SWAP" in this context.)

[M.M]

sizeof *(1 ? &(a) : &(b)) would be a simpler and more type-safe option for the third argument to swap_detail . Credit here

[M.M]

This version misbehaves for SWAP( arr[n++], var ); Which is maybe acceptable if you expect the reader to understand the convention that ALL CAPS means macros, and macro arguments should not have side-effects; however there are other solutions available that solve this problem

[M.M]

This silently misbehaves if the arguments have side-effects, e.g. swap(arr[n++], var);

[Paul R]

@M.M: yes, fair point - it can probably be improved but I think there will always be corner cases with macros like this. Better not to use them in the first place.

[Jonathan Leffler]

The suggested macro runs into problems if one of the arguments is a pointer (e.g. an argument passed into the function invoking the macro) and the other is a local array of the same size as the array pointed at by the pointer. Or if both arguments are pointers and swapping the data that they're pointing at is the intended operation, not swapping the pointer value. These aren't insuperable problems with suitable alternative macros — they just require care in the use of the correct macro.