Something I bet you didnt know you could do with pointers #2

[sparda]

Well, I have a little free time from my studies and I see avansc at work already. So I decided to add my two cents about pointer tricks.

To all of you C++ programmers (I'm one too), you can use pseudo-templates in C, using generic pointers and the memcpy function. I think the correct term is generic functions in C.

For instance, say you want to swap two values of arbitrary data-type. You would do something like this in C++:

Code: Select all

#include <iostream>
#include <cstdlib>

template<typename T>
void swap(T &a, T &b);
int main(void)
{

	int a = 10, b = 20;
	swap(a, b);
	std::cout << "a: " << a << " and b: " << b << std::endl;

	return EXIT_SUCCESS;
}

template<class T>
void swap(T &a, T &b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

You can do the same thing in C, and more efficiently by:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void swap(void *a, void *b, int n);

int main(void)
{
	int a=0, b=10;
	swap(&a, &b, sizeof(int));
	printf("a: %d, b: %d", a, b);

	return EXIT_SUCCESS;
}

void swap(void *a, void *b, int n)
{
	void *buffer = malloc(n);

	memcpy(buffer, a, n);
	memcpy(a, b, n);
	memcpy(b, buffer, n);

	free(buffer);
}

The "n" would be used to wrap the bytes to be copied. Actually, thats the reason you can't dereference void*s, because compilers "don't" know how many bytes to "bound" in the dereferencing process.

Just remember that you can not dereference void*'s and you'll be alright This works better than templates in that, it works in analogue to an inline functions, internally at the asm level. With C++ templates, if you have a huge amount of different types (including user-defined types i.e. classes) using template functions, the implementations would expands per-type. Whereas, with generic C functions, you only have this one representation for the implementation of swap.

So those are my two cents

[avansc]

dont use int n

use size_t n

[sparda]

avansc: truth be told, it doesn't really matter.

Reason: A precondition to using the generic swap function would be that sizeof always be used. To my knowledge, sizeof never returns a negative number. The only thing I can think of is if there is a ridiculously large user-defined type, that makes sizeof(user-defined type) return a number greater than 2147483647, and it causes a bitwise wrap-around bug. Please name a sighed data-type that when passed to sizeof returns 2147483647

[avansc]

avansc: truth be told, it doesn't really matter.

Reason: A precondition to using the generic swap function would be that sizeof always be used. To my knowledge, sizeof never returns a negative number. The only thing I can think of is if there is a ridiculously large user-defined type, that makes sizeof(user-defined type) return a number greater than 2147483647, and it causes a bitwise wrap-around bug. Please name a sighed data-type that when passed to sizeof returns 2147483647

its not about that.

but with size_t you can add whatever you want to there.

with int n, you can only an int, unless you do a cast.

its just a better programming practice to use size_t
more "professional"

[avansc]

i mean im not trying to say anything bad. but malloc(n) is such a bad programming practice.

you would lose a job programming like that.

(type*)malloc(n*sizeof(type));

[Amarant]

i mean im not trying to say anything bad. but malloc(n) is such a bad programming practice.

you would lose a job programming like that.

(type*)malloc(n*sizeof(type));

I think you should reread the example, because inside the swap function there's no information about the type.

I do agree the n parameter should have the size_t type since that is what sizeof() returns.

Btw, would you consider using variable length arrays instead of malloc and free.
I believe variable length arrays just use memory on the stack so that would be a lot faster I guess.

[avansc]

i just added to show what malloc is suppose to look like.

and depending on the situatiuon arrays might be faster. but i use linked list that use malloc and free. and even with 10000 items in the list i get little to no lag. so yeah im not sure about that one.

[avansc]

Code: Select all

void swap(void *a, void *b, int n)
{
   void *buffer = malloc(n);

   memcpy(buffer, a, n);
   memcpy(a, b, n);
   memcpy(b, buffer, n);

   free(buffer);
}

also, that code might work fine on his mahine. but that code is not portable. not meaning that it wont work on another platform.

anytime you do malloc(n) you are running a risk.

[sparda]

I see what you're saying, but I don't get what you're trying to do here. I'm not applying for a job.

[Amarant]

I don't see what you're saying. What's not portable about it?

[sparda]

Also, can you explain how using malloc(n) is not portable in my example? I can only see how the casting of the return type might have something to do with it. Remember, if I go swap(&a, &b, sizeof(a)), and then do malloc(n), it is the same as if I did, malloc(sizeof(int)).

[avansc]

also assuming you wanted to swap to variables they, they would likely be the same size.

i would use an XOR swap.

Code: Select all

a = a ^ b;
b = a ^ b;
a = a ^ b;

[avansc]

malloc(n) does not return the same value on different platforms.

maybe for that specific example you'll be fine. but most likely you are gonna run into trouble with malloc(n) somewhere.

[sparda]

?

Yeah avansc, I know. I posted that same XOR example in these forums about 2 months ago. In this case though, I was trying to show some pointer stuff, i.e. the generic functions in C

[bugmenot]

If you are using C++ then always prefer using the standard library's swap function unless you can prove that it is slower then any implementation that you can provide. Generally, it is at least going to be as fast if not faster then most generic implementations.

Code: Select all

#include <algorithm>

int main()
{
	int blah = 0; 
	int foo = 10;
	
	std::swap( blah, foo );
}

This code:

Code: Select all

void swap(void *a, void *b, int n)
{
   void *buffer = malloc(n);

   memcpy(buffer, a, n);
   memcpy(a, b, n);
   memcpy(b, buffer, n);

   free(buffer);
}

Is inherently slower then the template version because of the malloc. Allocating off the heap is always slower then stack. If I was stuck with C, then I wold consider using a macro.

Below is the sample code and the results in running the release build (using ctime is inaccurate to a degree but the difference is so large it is adequate to demonstrate my point:

Code: Select all

#include <algorithm>
#include <iostream>
#include <ctime>

#define C_SWAP( a, b, t ) do{ t temp = (a); (a) = (b); (b) = temp; } while(0);

void CPointerSwap( void *a, void *b, int n)
{
   void *buffer = malloc(n);

   memcpy(buffer, a, n);
   memcpy(a, b, n);
   memcpy(b, buffer, n);

   free(buffer);
}

template<class T>
void CppSelfSwap(T &a, T &b)
{
   T tmp = a;
   a = b;
   b = tmp;
}

int main()
{
	int blah = 0; 
	int foo = 10;
	clock_t startTime;
	clock_t finishTime;
	static const int ITERATIONS = 1000000000;
	
	startTime = clock();
	for( int i = 0; i < ITERATIONS; ++i )
	{
		std::swap( blah, foo );
	}
	finishTime = clock();
	std::cout << "C++ algorithm swap " << finishTime - startTime << std::endl;
	
	size_t n = sizeof(int);
	startTime = clock();
	for( int i = 0; i < ITERATIONS; ++i )
	{
		CPointerSwap( &blah, &foo, n );
	}
	finishTime = clock();
	std::cout << "C pointer swap " << finishTime - startTime << std::endl;
	
	startTime = clock();
	for( int i = 0; i < ITERATIONS; ++i )
	{
		C_SWAP( blah, foo, int );
	}
	finishTime = clock();
	std::cout << "C macro swap " << finishTime - startTime << std::endl;
	
	startTime = clock();
	for( int i = 0; i < ITERATIONS; ++i )
	{
		blah ^= foo;
		foo ^= blah;
		blah ^= foo;
	}
	finishTime = clock();
	std::cout << "XOR swap " << finishTime - startTime << std::endl;
	
	startTime = clock();
	for( int i = 0; i < ITERATIONS; ++i )
	{
		CppSelfSwap( blah, foo );
	}
	finishTime = clock();
	std::cout << "C++ self swap function " << finishTime - startTime << std::endl;
}

Prints:

Code: Select all

[Session started at 2008-12-08 01:47:02 +0000.]
C++ algorithm swap 113
C pointer swap 12486
C macro swap 113
XOR swap 93
C++ self swap function 119

The Debugger has exited with status 0.

As a side note, XOR only inherently work with integers. You have to add some extra code to make it work with non base types which will can it slower