Good old 'Swap' function

This is what I have is as follows:

Code:

---

void Swap(int *Ptr_A,int *Ptr_B)
{

int Ptr_Temp;
Ptr_Temp=*Ptr_A;
*Ptr_A=*Ptr_B;
*Ptr_B=Ptr_Temp;

}

---

I would like to expand on this function so that it can be used with parameters which are pointers to any type. That is, I would like to create a function that can swap two objects of any type pointed to by two pointers. In the above example only integers can be swapped. What would be the easiest way of doing that?

Instead of pointers-to-int, you could use pointers-to-void (and you'd have to malloc space yourself for the temporary); however, you would then need to pass in to your function the size of the data objects, and use memcpy to copy.

I've thought about this too. Sure would be handy. Something like:

Code:

---

void Swap(void *Ptr_A, void *Ptr_B)
{
void * Ptr_Temp;
Ptr_Temp= Ptr_A;
Ptr_A=Ptr_B;
Ptr_B=Ptr_Temp;
}

---

would be nice.

Unfortunately, in C, that is hard to do, but something like this:

Code:

---

char *buffer = NULL;
size_t max_size = 0;
void Swap(void *Ptr_A,void *Ptr_B, size_t size)
{
    // Allocate a new buffer when we need a bigger one. Since a big buffer can hold small things,
    // there's no need to "reduce" the size of the buffer.
    if (size > max_size)
    {
      free(buffer);
      buffer = malloc(size);
      max_size = size;
    }
    if (buffer == NULL)  // Do some panicing ;
    memcpy(buffer, Ptr_A, size);
    memcpy(PtrA, Ptr_B, size);
    memcpy(Ptr_B, buffer, size);
}

---

You should of course also free the temporary buffer at some point.

Alternatively, you could use a macro:

Code:

---

#define SWAP(T, A, B)  do { T temp = (A); (A) = (B); (B) = temp; } while(0)

---

Use like this:

Code:

---

struct something
{
  // stuff here
};

...
  struct something a, b;
  ...
  SWAP(struct something, a, b);

---

--
Mats

Quote:

---

Originally Posted by tabstop

Instead of pointers-to-int, you could use pointers-to-void (and you'd have to malloc space yourself for the temporary); however, you would then need to pass in to your function the size of the data objects, and use memcpy to copy.

---

I think the whole point would be to not have to mem copy the data.

However, I suspect it might not be a simple as I would like. That's because it's not just the pointer to the area that pointer represents, but also the amount of memory that has been allocated, so free() can work too.

Todd

Quote:

---

I think the whole point would be to note have to mem copy the data.

---

No, such copying is necessary. Unless one has a swap function with a pointer to a pointer, one cannot just swap pointers (or rather, one can swap pointers, but there would be no net effect).

The point is to have a swap function that is not restricted to a particular type, like a swap template function in C++.

Say, you want to sort an array of struct widget, then you will need to swap the widgets, and to do that, you need three memcopies. If you have an array of pointer to struct widget, then you can get away with swapping pointers.

--
Mats

Quote:

---

Originally Posted by matsp

Say, you want to sort an array of struct widget, then you will need to swap the widgets, and to do that, you need three memcopies. If you have an array of pointer to struct widget, then you can get away with swapping pointers.

--
Mats

---

Yes, I think pointers to pointers are the way to go for speed in these cases.

Quote:

---

Originally Posted by Todd Burch

Yes, I think pointers to pointers are the way to go for speed in these cases.

---

Yes, that is much better - but assumes the extra overhead of a second table and/or allocating the objects from the heap instead of just using an array. And sometimes the data isn't "yours" to begin with, so you need to sort whatever was given to you "in place" [say for example you are writing a general purpose sort routine].

--
Mats

Quote:

---

Originally Posted by Todd Burch

I've thought about this too. Sure would be handy. Something like:

Code:

---

void Swap(void *Ptr_A, void *Ptr_B)
{
void * Ptr_Temp;
Ptr_Temp= Ptr_A;
Ptr_A=Ptr_B;
Ptr_B=Ptr_Temp;
}

---

would be nice.

---

That won't work.
Swapping pointers, however, is easy. In theory, anyway:

Code:

---

void Swap(void** pA, void** pB)
{
        void** pTemp = pA;
        *pA = *pB;
        *pB = *pTemp;
}

---

Otherwise, you'll have to use mats's code, since C is lacking support for these kind of things. Much easier in C++, though, since a template function would be all that is required.

Quote:

---

Originally Posted by starcatcher

I would like to expand on this function so that it can be used with parameters which are pointers to any type. That is, I would like to create a function that can swap two objects of any type pointed to by two pointers. In the above example only integers can be swapped. What would be the easiest way of doing that?

---

By switching to C++ and using templates.
Hey, it's the truth - there isn't any easier way!

Thank you everyone!
I had a bit of trouble understanding the swapping pointers method at first,
but now I think I have an idea how it works. If I have this (in the main
function of course...):

Code:

---

double a=1.23,b=2.34,*ap,*bp;
ap=&a;
bp=&b;
Swap((void **) &ap,(void **) &bp);
 
void Swap(void **App,void **Bpp)

{

void **Cpp=App;

*App = *Bpp;

*Bpp = *Cpp;

}

---

The thing is though, that afterwards a and b haven't actually been swapped,
only ap and bp (as expected), and so I can't use the variables a and b until I
do something like a=*ap,b=*bp in the main function again. Wouldn't it have
been better just to use matsp's method(s)? Are there cases you can think of
where just swapping the pointers is all that is required?
Also, would this work? Would this swap the two elements in the array?

Code:

---

double Array[2];
Swap((void **) &Array,(void **) &(Array+1))

---

That looks REALLY suspect to me. How would you do it otherwise though with the Array?
What this is all getting at, is as somebody correctly guessed, a general purpose
bubblesort. How on earth would I be able to use the swapping pointers
method for something like that?

I will try the two of Matsp's methods. Which one would you say is quicker?

Thanks in advance!;)

Right, if you want to use the "swap pointer" method, your code would have to look something like this:

Code:

---

double dvalues[10] = { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 };
double *array[10] = { &dvalues[0], &dvalues[1], &dvalues[2],  &dvalues[3],  &dvalues[4], &dvalues[5], &dvalues[6], &dvalues[7], &dvalues[8], &dvalues[9] };

Swap(&array[3], &array[4]);

---

Swapping pointers only work if you actually use pointers.

As to which of my methods is faster, it should make very little difference.

--
Mats

Quote:

---

Originally Posted by starcatcher

How on earth would I be able to use the swapping pointers
method for something like that?

---

Swap pointers only works if you're working with pointers. Otherwise you have to use mats's code. C is very limited in this regard. There's no easy or safe method to swap arguments in C. You need C++ for that.

Quote:

---

Originally Posted by Elysia

Swap pointers only works if you're working with pointers. Otherwise you have to use mats's code. C is very limited in this regard. There's no easy or safe method to swap arguments in C. You need C++ for that.

---

And, how does C++ do it "better"?

My macro would work just fine - and in compilers with "typeof" it would even be possible to write it as a simpler macro that doesn't take the type. [Although it still doesn't work on arrays].

--
Mats

Quote:

---

Originally Posted by matsp

And, how does C++ do it "better"?

---

Templates of course:

Code:

---

template<typename T> void Swap(T& Arg1, T& Arg2)
{
        T Temp = Arg1;
        Arg1 = Arg2;
        Arg2 = Temp;
}

---

Yes, but it's only (a little bit) handier than the macro I wrote:

Code:

---

#define SWAP(T, A, B)  do { T temp = (A); (A) = (B); (B) = temp; } while(0)

---

Yes, the do-while stuff is a bit ugly, but that's about it.

And of course, you have to specify the type, and it doesn't work with arrays, before anyone else points that out.

--
Mats

But then you also have to specify type and it doesn't work with arrays, so C is still somewhat limited when it comes to stuff like this :)
And as we all know, debugging macros can be a pain, for one...

Quote:

---

Originally Posted by Elysia

But then you also have to specify type and it doesn't work with arrays, so C is still somewhat limited when it comes to stuff like this :)
And as we all know, debugging macros can be a pain, for one...

---

Yeah, and debugging templates is trivial, right?

By the way gcc for example supports a typeof, so you can do:

Code:

---

#define SWAP(A, B) do { typeof(A) temp = A; A = B; B = temp } while(0)

---

--
Mats

Quote:

---

Originally Posted by matsp

Yeah, and debugging templates is trivial, right?

---

It's easier, at least...

Quote:

---

By the way gcc for example supports a typeof, so you can do:

Code:

---

#define SWAP(A, B) do { typeof(A) temp = A; A = B; B = temp } while(0)

---

---

But I'm guessing that's not standard, so if you want to rely on compiler specific extensions, then sure.

Quote:

---

Originally Posted by matsp

Yes, but it's only (a little bit) handier than the macro I wrote:

Code:

---

#define SWAP(T, A, B)  do { T temp = (A); (A) = (B); (B) = temp; } while(0)

---

Yes, the do-while stuff is a bit ugly, but that's about it.

And of course, you have to specify the type, and it doesn't work with arrays, before anyone else points that out.

--
Mats

---

That can work with arrays, you just have to use the type of item in the array for T instead of the array type, and use the [] syntax for A and B.

However, it's still far inferrior to what you would use in C++:
if A or B have side effects then they get executed twice.
No support for copying of objects since you can't define an assignment operator.
Macros are evil and polluting.
You have to tell it the type, instead of letting the compiler handle that.
Explicit specialisations of swap can be given in C++ to allow certain objects to be swapped more efficiently. The caller doesn't have to care about this.
Debugging template code is not really harder than non-templated code, but debugging macros is much worse! (It's the compile-time errors that are the tricker part when it comes to template code)

Having said that, if I were forced to use C, I would do the same as above.

I tried the following function which was suggested:

Code:

---

void Swap(void** pA, void** pB)
{
    void** pTemp = pA;
    *pA = *pB;
    *pB = *pTemp;
}

---

and found that it doesn't work as expected. I understand why too. Anyway I changed it, and now it looks like this with changes highlighted (sorry I changed variable names too):

Code:

---

void Swap_VTP(void **App,void **Bpp)
{
    // Declare variables
    void *Cpp
 
    // Perform pointer swap
    Cpp=*App;
    *App=*Bpp;
    *Bpp=Cpp;
}

---

The problem before was that in the first case, was that by doing pTemp=pA the other two lines became essentially: *pA=*pB and *pB=*pTemp=*pA=*pB (where the last two equals signs are in the mathematical sense and not assignment operators) due to the previous line and so essentially what you are doing is:

Code:

---

*pA=*pB;
*pB=*pB;

---

which doesn't achieve the swap. My changed version solves that issue. Just thought I would point that out in case someone else reads this thread in the future.

Philipp

PS It's almost impossible to format your posts how you want to with these editors!!

Code:

---

void Swap(void** pA, void** pB)
{
        void* pTemp = *pA;
        *pA = *pB;
        *pB = pTemp;
}

---

I believe that's how it should be, yes? That's what happens when you post code that you don't test...
Btw, use Firefox + Tab in Textarea extension. This will allow you to use tabs in the editor!
Otherwise just write the code in your IDE and copy it here.

As I said earlier, I am trying to take this further to write a general purpose sort routine. The swapping works fine, but another problem has arisen. I need a criteria by which the data is sorted. I'm assuming that for whatever I will be sorting the < and > operators will be defined (like for char,__intn,double etc...). The only problem is that I don't know how I am actually supposed to compare two data entries as I am only working with void pointers (Array_Ptr would be a pointer to a void so I can't do Array_Ptr[i]). Here is (basically) the normal bubblesort function/algorithm:

Code:

---

do
{
        Done=true;
        for(i=0;i<Num_of_Elem-1;i++)                               
        {
                if(Array_Ptr[i]>Array_Ptr[i+1])
                {
                        Swap(Array_Ptr+i,Array_Ptr+i+1);
                        Done=false;
                }
        }
}
while(!Done);

---

If I try to change this so that the function is compatible for any type of data to sort, I can use void pointers and add an argument 'size_t Size' so that I can still perform the swap, but I don't know what to do with the highlighted section.
Any ideas?

Thx,
Philipp :confused:

I'd say that without knowing what type of data you're sorting, you can't sort. Or at least I'm tempted to say so. It will probably behave wrong when sorting one type and right when sorting one.

The way that the library function qsort() solves this problem is by calling back to a function that compares the two items - just pass the address of your two items to the a function

Code:

---

int comparefunc(void *a, void *b);

---

This function should return an integer that is less than, equal to or greater than zero if a is less than, equal to or greater than b.

Sine the compare function is given by the caller, you don't have to pass a size, as the caller of the sort function should know what type to cast a and b into.

--
Mats

You can improve Bubblesort beyond using a mere boolean flag!

In C++ I'd do it like this:

Code:

---

template <class T>
void BubbleSort(T a[], int n) {
        int sinker = n-1;
        do {
                int floater = 0;
                for (int i = 0; i < sinker; ++i) {
                        if (a[i + 1] < a[i]) {
                                Swap(a[i], a[i + 1]);
                                floater = i;
                        }
                }
                sinker = floater;
        } while (sinker > 0);
}

---

My programming environment is C/C++, meaning that I can write a mash of the two, so I tried to create a basic test template function and it worked. That should mean that everything becomes much much easier to do and I can write my sort function. The rest of my program is still in C tho.

Quote:

---

Originally Posted by iMalc

Quote:

---

Originally Posted by starcatcher
I would like to expand on this function so that it can be used with parameters which are pointers to any type. That is, I would like to create a function that can swap two objects of any type pointed to by two pointers. In the above example only integers can be swapped. What would be the easiest way of doing that?

---

By switching to C++ and using templates.
Hey, it's the truth - there isn't any easier way!

---

Looks like that is what I did!! Never expected that I would really take that advice did you! lol!:D

Thank you everyone who helped me and I hope that that finally puts this subject to rest!

Philipp:cool:

Bear in mind that your effort to sort things will always be rather a learning experience than an improvement on anything existing - the C environment has a qsort/heapsort implemented in the standard library, and C++ has a couple of sort mechanisms "ready to use" already too. It's quite unlikely that you will improve on these two - but it's a great learning experience to try it out, especially to make it work for "all types".

--
Mats

I have realised that. I would like to compare my sort function(s) against those that are inbuilt to see really how much slower they are so I get an idea. Again, it's a formative excercise, and what do you know, I've already learnt about templates and void pointers and all that, which I think is great.

Philipp;)