Thread: I don't understand the following line of code

  1. #1
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195

    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

  2. #2
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    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

  3. #3
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Then why use void* in the function parameters in the first place?

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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;
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    "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.

  7. #7
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    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.

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    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.

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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 
    */
    Last edited by Dave_Sinkula; 03-09-2006 at 10:17 PM. Reason: D'oh! Didn't update the output.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Cool. Thank you both for clarifying this for me.

  12. #12
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C code line, pointer declaration
    By Dedalus in forum C Programming
    Replies: 2
    Last Post: 06-10-2009, 04:34 AM
  2. help again with scrolling without wrapping
    By Dukefrukem in forum C Programming
    Replies: 8
    Last Post: 09-21-2007, 12:48 PM
  3. Greenhand want help!
    By leereg in forum C Programming
    Replies: 6
    Last Post: 01-29-2002, 06:04 AM
  4. SSCANF help
    By mattz in forum C Programming
    Replies: 7
    Last Post: 12-10-2001, 04:53 PM