I don't understand the following line of code

In the following code:

Code:

---

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

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int * pItem;
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
  {
    printf ("%d ",values[n]);
  }
  return 0;
}

---

I don't understand the

Code:

---

  return ( *(int*)a - *(int*)b );

---

construction. Can someone break this line of code down.

Thanks

The compiler doesn't know how to perform arithmetics on something of void type. In fact you can't use void in any way at all so you need to tell the compiler that it's an int, int pointer in this case since it's an adress that was being sent to the function and since it's also an adress it needs to be dereferenced

Then why use void* in the function parameters in the first place?

And before you get too chummy with this particular construct, note that it will fail to produce correct results if there is integer overflow.

A less confusing and correct version might be like this.

Code:

---

int compare (const void *a, const void *b)
{
  const int *x = a; /* 'x' points to a read-only integer given by 'a' */
  const int *y = b; /* 'y' points to a read-only integer given by 'b' */
  if ( *x < *y )
  {
      /* the int pointed to by 'x' is less than the int pointed to by 'y' */
      return -1;
  }
  if ( *x > *y )
  {
      /* the int pointed to by 'x' is greater than the int pointed to by 'y' */
      return 1;
  }
  return 0;
}

---

Quote:

---

Originally Posted by cdalten

Then why use void* in the function parameters in the first place?

---

Because qsort takes a function pointer declared as shown.

"note that it will fail to produce correct results if there is integer overflow."

Seriously? I've seen a lot of experienced computer programmers use the construct, hence why I asked about it.

Yes qsort is designed to work with any datastructure such as int, float, some struct or even a class but it doesn't know how to deal with the different types so it leaves that up to the function you gave it which uses void pointers as a parameter. A pointer as a parameter is good because all pointers have a common size, usually 4 bytes so all these different possible types can be sent as pointers to the function you provided.

Quote:

---

Originally Posted by cdalten

"note that it will fail to produce correct results if there is integer overflow."

Seriously? I've seen a lot of experienced computer programmers use the construct, hence why I asked about it.

---

Yes.

So at the risk of going off topic, could either one of you give me an example where the original code that I posted produces an integer overflow? Or at least point me in the right direction and leave it as an academic excercise for me.

Code:

---

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

int compare1 (const void *a, const void *b)
{
  const int *x = a; /* 'x' points to a read-only integer given by 'a' */
  const int *y = b; /* 'y' points to a read-only integer given by 'b' */
  if ( *x < *y )
  {
      /* the int pointed to by 'x' is less than the int pointed to by 'y' */
      return -1;
  }
  if ( *x > *y )
  {
      /* the int pointed to by 'x' is greater than the int pointed to by 'y' */
      return 1;
  }
  return 0;
}

int compare2 (const void *a, const void *b)
{
  return *(int*)a - *(int*)b;
}

void print (int *array, size_t size)
{
  while ( size-- )
  {
      printf ("%d ", *array++);
  }
  putchar('\n');
}

int main ()
{
  int values[] = { INT_MIN + 1, 0, 1, INT_MAX - 1 };
  qsort ( values, sizeof values / sizeof *values, sizeof *values, compare1);
  print ( values, sizeof values / sizeof *values);
  qsort ( values, sizeof values / sizeof *values, sizeof *values, compare2);
  print ( values, sizeof values / sizeof *values);
  return 0;
}

/* my output
-2147483647 0 1 2147483646
0 1 2147483646 -2147483647
*/

---

Cool. Thank you both for clarifying this for me.

Quote:

---

Originally Posted by cdalten

Then why use void* in the function parameters in the first place?

---

Think of it this way...

If the qsort function did not use a pointer to a compare function that itself uses void pointers, then it would need to have a specific type of pointer, i.e. int, float, double, char, etc... one for each possible type that could ever be used to compare two "things" to one another. This goes beyond the everyday predefined types and would need to lead into user defined types as well. The declaration of the qsort function would need to look like:

void qsort(int* base, size_t num, size_t width, int (*compare)(const int* elem1, const int* elem2) );
for ints and...

void qsort(float* base, size_t num, size_t width, int (*compare)(const float* elem1, const float* elem2) );
for floats and...

void qsort(double* base, size_t num, size_t width, int (*compare)(const double* elem1, const double* elem2) );
for doubles etc...

You'd need one declaration for every single type possible. And these above are just for a few of the predefined types. What about user defined types that can be named anything? What about them? A big problem is that the above requires a concept known as function overloading (functions with the same name but different argument types that behave differently depending on the argument type) which is possible in C++ but not plain ol' C. Even though it is possible to use function overloading in C++ you still wouldn't be able to account for all the various user defined types in this manner. You could also use a single templated function but again, that only applys to C++ and any user defined objects being compared would need to have the > and < operators defined for them in order for a generic "compare" function to work.

So, you need to use a generic pointer which then gets type cast into the particular pointer type required by that particular compare function and then dereferenced. This is what void* is for.