Home » Various » Basic Void pointer arithmetics

Basic Void pointer arithmetics

Okay, as promissed before my last trek journey (polish only) I’ll share some C/C++ informations I found interesting.

Few hours before trip a friend of mine asked to write bubble sort. Easy. So I wondered where’s the catch – this guy created img processing tool in java. Our conversation beyond this point was something like:

I: “Why don’t you write it down yourself? You are better than me”
Bob: “I need to write it in C++”
I: “Ok, that’s some point. But Java and C++ syntaxes aren’t that different you know”
Bob: “But header for this sort function must be the same as qsort’s.”

And that was the catch. You need to work on void pointers, and that can be confusing for some.

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

Call me good-hearted but I did that. I needed to finish packing, cooking my version of „iron ration” and so on, and doing bubble sort seemed easier than explaining how to do it.

Trick is – you can’t perform any arithmetic operation on void*, because it lacks information about size of object it describes. So the only way is to cast it on char (it’s size is always smallest via 3.11.6 of C++ Standard draft n3337).
So moving pointer by X bytes can be done like this:

ptr = static_cast<char*>(ptr) + X;

But of course you must know value of X. Usually it’ll be size of element casted as void*, or it’s multiple. Now let’s create proper Bubble Sort!
As we know header will be analogical to qsort:

void bubbleSort (void * base, size_t num, size_t size, 
                int (*compare)(const void*, const void*))

Arguments are:

  • base – Array containing data to sort converted to void*
  • num – Number of elements stored inside array
  • size – Size of each element in array
  • compare – pointer to a function that compare 2 elements.

In function we need to wrote down standard bubble sort loops, with proper incrementation and swapping.

int n = num;
do{
 for(int i=0; i < n-1; ++i){
  A = static_cast<char*>(base) + i*size; // Point to base[i]
  B = static_cast<char*>(base) + (i+1)*size; // Point to base[i+1]

  if( compare( A, B) == 1)
  {
   //Swap
   memcpy (tmp, A, size);
   memcpy (A, B, size);
   memcpy (B, tmp, size);
  }
 }
 --n;
}while(n > 1);

As you can see we use memcpy instuctions for swapping objects – we can’t use simple assigments because we don’t know to what object A or B is pointing, so tmp should be void pointer
Remember to allocate enough memory for tmp, and to free it afterwards!

You can see working code at my gist

Posted in Various and tagged as ,

Comments are closed.