Question about casting (relating to qsort and pointers to structures)

This is a discussion on Question about casting (relating to qsort and pointers to structures) within the C Programming forums, part of the General Programming Boards category; Hi everyone, I've managed to write a working program in response to Exercise 6.4 in K&R (2nd Ed, p. 143) ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    5

    Question Question about casting (relating to qsort and pointers to structures)

    Hi everyone,

    I've managed to write a working program in response to Exercise 6.4 in K&R (2nd Ed, p. 143) ('Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.') but only after much difficulty in getting qsort to work with my comparison function. Here's the code with the irrelevant bits cut out:

    Code:
    typedef struct wordc {
    	char *word;
    	unsigned int count;
    } Word;
    
    ...
    
    int treecount(Treeptr); /* Treeptr is a pointer to a node in a binary tree */
    
    int main (void)
    {
    	unsigned int nwords;
    
    	...
    
    	nwords = treecount(root); /* count no. of words in binary tree */
    
    	...
    
    	Word *freqlist[nwords-1];
    
    	...
    
    	qsort(freqlist, nwords, sizeof(Word *), wcountcmp);
    	
    	...
    
    	return 0;	
    }
    
    int wcountcmp (const void *w1, const void *w2)
    {
    	Word *nw1 = *(Word * const *)w1;
    	Word *nw2 = *(Word * const *)w2;
    	
    	if (nw1->count == nw2->count) {
    		return 0;
    	}
    	
    	return nw1->count < nw2->count ? -1 : 1;	
    }
    The program worked after modifying wcountcmp() based on information from this page: http://c-faq.com/lib/qsort2.html.

    However, I still don't understand the method of casting i.e. of the form:
    struct mystruct *sp1 = *(struct mystruct * const *)p1;

    On the right side, what do the asterisks after 'mystruct' and 'const' do? And what about the asterisk outside the brackets i.e. before (struct ... ?

    Any help much appreciated.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    Word *nw1 = *(Word * const *)w1;
    The const is saying that the "pointer isn't going to be used to modify the content" which allows the compiler to do some optimizations if it likes to. [And the compiler will tell you if you start modifying when you shouldn't, which means that you can have "contracts" between functions that something declared const ISN'T going to change].

    Since you are sorting a list of pointers to a structure, the qsort function passes the address of the pointer, which is why you need to use the complex for. I'll explain what each portion does:
    Code:
    Word *nw1 = *(Word * const *)w1;
    Declare a pointer to a Word struct
    Take what is being pointed to
    Cast the void pointer to A pointer to pointer of Word, where the stuff pointed to is constant [not allowed to change it]
    The input void * pointer.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    5
    Mats,
    Thanks for the reply — bit clearer now! Bear with me here:
    1. Doesn't w1 need to be a pointer to Word (as opposed to a pointer to pointer of Word)?
    2. In terms of syntax, to cast w1 to a const pointer to pointer of Word, why isn't it just:
      Code:
      Word *nw1 = (Word const **)w1;

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by kuda View Post
    Mats,
    Thanks for the reply — bit clearer now! Bear with me here:
    1. Doesn't w1 need to be a pointer to Word (as opposed to a pointer to pointer of Word)?
    2. In terms of syntax, to cast w1 to a const pointer to pointer of Word, why isn't it just:
      Code:
      Word *nw1 = (Word const **)w1;
    1. You're forgetting the dereference -- the * in front. After the dereference, you must have a pointer to Word, so before the dereference, you must have a pointer to pointer of Word.

    2. Same thing: you've forgotten the * in front. If you think of the * in front and the first * in parentheses as "cancelling", then you've got what you expect, I think.

    I'm assuming that the reason for the oddness is that w1 is in fact a pointer to a pointer, so any cast on the right that doesn't have two * in it can't be right. Since we want nw1 to have one less level of indirection, we have to dereference (hence the * in front), and we want nw1 to point to something that can't be changed, hence the "const" inside one level, where it will be in the right place once we actually do the dereference. Hence nw1 "sees" Word const * (a pointer to a constant Word).

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    5
    Thanks tabstop, that makes sense.

    Here's my understanding so far:
    Code:
    Word *nw1 = *(Word * const *)w1;
    • nw1 is a pointer to what w1 points to. In other words, nw1, a pointer to Word, points to the same Word pointed to by w1.
    • For this to happen, w1 has to be cast into the right form and then dereferenced, so that nw1 points to w1's Word, not to the pointer w1 itself.


    Correct?

    Now, just to get a bit clearer on the syntax and the use of const, I tried running a few alternatives through gcc, with the following results:

    Case 1
    Code:
    Word *nw1 = *(Word **)w1;
    Result: Compiled without error and coincidentally or otherwise, program seemed to work.

    Case 2:
    Code:
    Word *nw1 = *(Word const **)w1;
    Result: gcc produces the following message: warning: initialization discards qualifiers from pointer target type

    Case 3:
    Code:
    Word *nw1 = *(const Word **)w1;
    Result: Same as Case 2

    In light of the above:
    • Is the const in the 'correct' version (i.e. the coloured one at the top of this post) just there as a safeguard?
    • Also in the 'correct' version, does const make the pointer read-only, or does it make the Word struct that it points to read-only?
    • What is the difference between (Word * const *), (Word const **) and (const Word **)?
    Last edited by kuda; 01-22-2008 at 05:28 AM.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by kuda View Post
    Thanks tabstop, that makes sense.

    Here's my understanding so far:
    Code:
    Word *nw1 = *(Word * const *)w1;
    • nw1 is a pointer to what w1 points to. In other words, nw1, a pointer to Word, points to the same Word pointed to by w1.
    • Not quite: w1 is a pointer to a pointer to a Word. This is because your list itself contains pointers, and qsort passes the address of the element you are sorting, in this case the pointer to a Word - address of a pointer to Word -> pointer to pointer to Word.

      To get back to a pointer to word, you need to dereference (use one *).
    • For this to happen, w1 has to be cast into the right form and then dereferenced, so that nw1 points to w1's Word, not to the pointer w1 itself.

  7. Correct?

    Now, just to get a bit clearer on the syntax and the use of const, I tried running a few alternatives through gcc, with the following results:

    Case 1
    Code:
    Word *nw1 = *(Word **)w1;
    Result: Compiled without error and coincidentally or otherwise, program seemed to work.

    Case 2:
    Code:
    Word *nw1 = *(Word const **)w1;
    Result: gcc produces the following message: warning: initialization discards qualifiers from pointer target type

    Case 3:
    Code:
    Word *nw1 = *(const Word **)w1;
    Result: Same as Case 2
    The form "const Word" and "Word const" are the same thing - you can put "const" on either side of the type, with the same effect. This form means that the pointer itself is a constant value, so you are not changing the pointer - this would be correct if you also put "const Word *nw1" - which would work fine for your code - you are just comparing the data inside your structure, so you CAN (should[1]) use "const Word *nw1".

    So as a conclusion:
    Code:
    const Word *nw1 = *(const Word * const *)w1;
    is the preferred code.


    In light of the above:
    • Is the const in the 'correct' version (i.e. the coloured one at the top of this post) just there as a safeguard?
    • Also in the 'correct' version, does const make the pointer read-only, or does it make the Word struct that it points to read-only?
    • What is the difference between (Word * const *), (Word const **) and (const Word **)?
    [1] Whilst some people would disagree, I think most would agree that WHENEVER POSSIBLE, const should be there.

    --
    Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.

  • #7
    Registered User
    Join Date
    Jan 2008
    Posts
    5
    I think that I've got it, or at least that I understand enough of it for now.
    My conclusion:

    Code:
    Word * nw1 = *(Word * const *)w1;
    w1 is cast as a const pointer, to a pointer to Word. It is then dereferenced using the * operator to match the type of nw1 i.e. pointer to Word. Since only the pointer w1 is const, it is acceptable for nw1 to access what it points to without nw1 itself needing to be const.

    Code:
    const Word * nw1 = *(Word const **)w1;
    Even though this might appear to cast w1 as ‘const pointer to pointer, of Word’, ‘Word const’ is the same as ‘const Word’ and w1 is actually cast as ‘pointer to pointer to, const Word’. Since w1 (which is not const in this case) ultimately points to type const Word, the compiler produces a warning if nw1 does not point to type const Word as well.

    Tick?

  • #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yup, that's how it works.

    As I said earlier, you could add another const on either side of the equal sign, making the code more "const correct".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  • #9
    Registered User
    Join Date
    Jan 2008
    Posts
    5

    Thumbs up

    Thanks for all your help!

  • Popular pages Recent additions subscribe to a feed

    Similar Threads

    1. qsort - newbie trouble with pointers
      By aze in forum C Programming
      Replies: 4
      Last Post: 03-10-2003, 02:38 PM

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21