Using qsort to sort an array of strings

This is a discussion on Using qsort to sort an array of strings within the C Programming forums, part of the General Programming Boards category; Originally Posted by matsp pointers to different types may well need suitable conversion before you can use a void * ...

  1. #16
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Quote Originally Posted by matsp
    pointers to different types may well need suitable conversion before you can use a void *
    standard says: cast to pointer to void and back doesn't change it and when function has a prototype the call will cast types of its arguments to types of prototype parameters
    and there is an example in K&R where he does a qsort and uses char * in numcmp (with qsort( , , , int (*)(void *, void *)); prototype and definition)
    are you think it depends from level of pointer ?
    what problem with level if casting to void * doesn't change any quality of a data ?

    about const there are obvious rules too

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,306
    Quote Originally Posted by nonoob
    I don't see a need to define new variables/pointers inside the compare function.
    It can improve readability and is unlikely to make a difference, especially after the compiler applies optimisation.

    By the way, your implementation of the comparison by year contains a potential bug due to possible overflow error, though it is unlikely to surface given the expected range of values for years. If we use a more generally correct implementation:
    Code:
    int compare_cars(const void *a, const void *b)
    {
        const CAR_T *lhs = a;
        const CAR_T *rhs = b;
        return lhs->year < lhs->year ? -1 : lhs->year > rhs->year;
    }
    The benefit of the local pointer variables becomes more pronounced.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    Quote Originally Posted by c.user View Post
    standard says: cast to pointer to void and back doesn't change it and when function has a prototype the call will cast types of its arguments to types of prototype parameters
    and there is an example in K&R where he does a qsort and uses char * in numcmp (with qsort( , , , int (*)(void *, void *)); prototype and definition)
    are you think it depends from level of pointer ?
    what problem with level if casting to void * doesn't change any quality of a data ?

    about const there are obvious rules too
    The problem is that, with qsort(), the compiler doesn't know it has to convert between one pointer type and void*. When you have something like this:
    Code:
    void f(int *n);
    void *p = NULL;
    f(p);
    the compiler sees the prototype for f() and converts p accordingly. This is perfectly fine. But with qsort(), you're passing a pointer to a function. You're not passing a prototype, so the compiler doesn't know what your function looks like. It must assume that your function matches what it asked for. That is, it will pass a void* as a void*, not as an int*; and while, as matsp pointed out, that often works, there is no guarantee. void* and int* (or whatever*) might be different sizes, have different representations, be passed different ways, etc. The compiler passes a void*, but no conversion occurs; that is the important point here.
    Last edited by cas; 05-13-2009 at 10:49 AM. Reason: Typo fix

  4. #19
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Quote Originally Posted by cas
    You're not passing a prototype, so the compiler doesn't know what your function looks like.
    How does qsort knows about a function, how does it call the function, how does you think ?
    It calls it, passes arguments to it, and when it calls it, qsort goes to the prototype and makes casts.
    Because without prototype it wouldn't use the function. Maybe compiler will not check the function prototype from the pointer to the comparison function, but it will be work correctly by imlicit operations (casts) which compiler must have.
    Yesterday I tested memset for zeroing structure (all bytes), I used char ponter to go left from structure address (to three steps) and then pass this pointer to the memset call, then I compiled this source in dev-cpp and in lcc under win98 (it doesn't matter, but if you would want know) and program from dev-cpp didn't zero first three bytes, but it zeroed fourth byte and other, and lcc zeroed all bytes in the structure (which consisted three ints)
    I want say by this I don't care which level of the standard conforming compiler uses, knows it standards or doesn't know, if dev-cpp thinks some weird about char pointers or it thinks that swprintf uses only three parameters (it uses four in the standard), I don't care
    I am use standard and if it will not work in some compilers under some systems, those are compilers problems
    When it uses the function it must look at the prototype or if it does not have the prototype it must have the definition before the call

    Code:
        f(p);
    when you will use this it will do implicit assign the argument value to the parameter (local) of the function, when it will do assign it will do implicit type cast of the right part to the type of the left part
    update:
    oh, there is no cast for void pointers there (it does it for only arithmetic types), in assign to local parameters of call void pointer assignes simply (in/from any side of assign)

    Quote Originally Posted by cas
    as matsp pointed out, that often works, there is no guarantee. void* and int* (or whatever*) might be different sizes, have different representations, be passed different ways
    Code:
    static int compar(const void *l, const void *r)
    {
        const struct car *left = l;
        const struct car *right = r;
        ...
    you don't using cast l or r (you are use the rule of implicit cast of void to struct car * from standard)
    by your and matsps words it should not be work for this way
    Last edited by c.user; 05-13-2009 at 08:14 PM.

  5. #20
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    Quote Originally Posted by c.user View Post
    How does qsort knows about a function, how does it call the function, how does you think ?
    It calls it, passes arguments to it, and when it calls it, qsort goes to the prototype and makes casts.
    OK, let me try this from another angle, because you seem to be confused by how void* works. Yes, object pointers can be converted to and from void*. No, that does not mean that your interpretation of qsort() is right. Here's an analogy.
    Code:
    #include <stdio.h>
    
    static void f_long(long long a, long long b)
    {
      printf("%lld %lld\n", a, b);
    }
    
    static void f_short(int a, int b)
    {
      printf("%d %d\n", a, b);
    }
    
    static void q(void (*f)(long long, long long))
    {
      f(15LL, 20LL);
    }
    
    int main(void)
    {
      q(f_long);
      q((void(*)(long long, long long))f_short);
    
      return 0;
    }
    Now, you must agree that an int can be converted to a long long, and will be if f_long() is called such as f_long(15, 20). C does this conversion the way it converts int* to void*; that is, it's legal, and implicit.

    Next, the q() function is like qsort(); it takes a pointer to the compare function (which is a simple print function here), and calls it with a couple of arguments, which are long longs that fit into an int. So there's no problem here of representation. Converting 15LL to an int gives you 15.

    According to your argument about void*, when f_short() is passed to q(), it will be called correctly because a conversion from long long->int is valid. But in reality, this code is undefined. On four of my five available compilers (gcc, klcc, suncc, clang), the output is a line "15 20" (as it should be), and a line "15 0"--whoops. Only icc printed "15 20" both times. Both results are "correct", because the code is undefined.
    you don't using cast l or r (you are use the rule of implicit cast of void to struct car * from standard) y your and matsps words it should not be work for this way
    We're not saying that you can't convert between them. We're saying they might be different sizes, or might have different semantics when being passed to a function, etc. That does not preclude a void* from being able to hold a struct car*. An implementation might make void* twice as big as other pointers, so it can store extra information, for example. The conversion to void* is still fine, because void* is definitely large enough to store a smaller size; and the implementation would ensure that conversion back only stores the relevant bits from void* (that is, the non-extra information).

  6. #21
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Quote Originally Posted by cas
    According to your argument about void*, when f_short() is passed to q(), it will be called correctly because a conversion from long long->int is valid.
    No, I updated when reread info for void pointers and assign operation in the book
    There is simply assign of void pointer even without cast

    qsort gets a void pointer to the first element of array, hence it will use this void pointer inside itself
    it will pass same void pointer to the call of passed function
    in other words it will call (*ptr)(p1, p2) => Func(char **s1 = p1, char **s2 = p2) where p1, p2 are void pointers
    then Func is do strcmp(*s1, *s2)
    can you prove it will work wrong somewhere ?

    Quote Originally Posted by cas
    We're saying they might be different sizes, or might have different semantics when being passed to a function
    when they passes to a function standard says: it will be assign
    even if it will be casted by prototype the standard says: any pointer can be casted to void pointer and back without changes of this data (which it points to)
    you can't only cast another pointers like int * to char * and otherwise

    qsort:
    it takes char **, puts it to void *, then inside takes this void * and passes it to (*ptr), then (*ptr) assignes it to char ** and it returns back to char **, then char ** goes into Func and strcmp takes it and derefrences char ** to char *
    ok ?
    Last edited by c.user; 05-13-2009 at 09:01 PM.

  7. #22
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Code:
        f(15LL, 20LL);
    and it will be undefined when (*f) will have arguments int, int
    because cast from big signed to small signed is undefined behaviour
    for unsigned I don't remember quite (it may throw out left bits, but it is conform to the compiler maybe, I don't remember now)

  8. #23
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    a) Conversion from long long to int is not undefined. See C99 6.3.1.3.

    b) You are incorrect about qsort(). Unfortunately, due to the language barrier, I'm not entirely sure how you see it as correct, but I can assure you it is not. It's as simple as this: qsort() will pass void pointers. Your function expects non void pointers. The prototype that qsort() uses to call your function says that it expects void pointers. qsort() passes void pointers as void pointers. This is the very important part. It does not convert them before it calls, because the function declaration it is using says not to convert them. void* is being passed as void*.

    When you have a function (like memset()) that expects a void*, you can pass, say, an int*, because---and this is the important part---the prototype for memset() tells the compiler to convert to void* before the function is called; so the proper type gets passed. In qsort(), the conversion cannot happen before your compare function is called, because qsort() has no idea what your compare function looks like---it has to assume it expects void*. The conversion will not happen when qsort() calls your function.

    If you provide a false declaration for memset, such as
    Code:
    void *memset(int *s, int c, size_t n);
    when you call it, you have undefined behavior. This is the same thing as with qsort(). Once the wrong thing is passed, it's too late to fix the problem.

  9. #24
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Quote Originally Posted by cas
    because qsort() has no idea what your compare function looks like
    yes, but when it calls the compare function, this call looks to the prototype (what is it call ? function, how is it call a function ? by the looking for prototype or definition, what is it do with definition ? it will assign arguments to parameters, which arguments are it have ? void pointers --- look at the prototype of qsort in stdlib.h --- because qsort takes the address of the first element of the array as a void pointer)

    if it will find the prototype it will cast void pointer to char **, because char ** there is, but there is a rule in the standard "casting void pointer to another kind of pointer will be true if there was the casting from that kind of pointer to this void pointer"
    if you have
    Code:
        int n = 5;
    you can do
    Code:
        void *p;
        int *ip;
    
        p = &n;
        printf("%d\n", *((int *) p));
        ip = p;
        printf("%d\n", *ip);
    and it will be true for both
    Last edited by c.user; 05-13-2009 at 10:08 PM.

  10. #25
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Quote Originally Posted by cas
    If you provide a false declaration for memset, such as
    I provide it by the line
    #include <string.h>
    everytime

  11. #26
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    Quote Originally Posted by c.user View Post
    yes, but when it calls the compare function, this call looks to the prototype
    No. It can't. The code for qsort() was compiled long ago by your C library vendor. How can it know what your prototype looks like? As I said, it uses the declaration that is in the prototype of qsort(); the declaration that says your function takes two void pointers.

    If you dispute this, please explain how qsort() finds your prototype. To see that it doesn't, you can look at a free implementation. OpenBSD's is available here as an example.
    Quote Originally Posted by c.user View Post
    I provide it by the line
    #include <string.h>
    everytime
    I wasn't saying you improperly use memset(). I was showing, using memset() as an example, what happens when you incorrectly use qsort().

  12. #27
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Code:
    6.3.1.3  Signed and unsigned integers
    
           [#1]  When a value with integer type is converted to another
           integer  type  other  than  _Bool,  if  the  value  can   be
           represented by the new type, it is unchanged.
    that compiler which didn't cast your 15LL to int correctly doesn't know standard just like dev-cpp for swprintf
    ok, I confused a little

  13. #28
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Code:
        cmp(pl - es, pl) > 0
    it will take the address of the function and call it as Func(char **s1 = (char **) (pl - es)..., where pl is a char pointer (simplest), because Func has the prototype

    I commented the prototype and got this
    Code:
    [guest@station tmp]$ cc -Wall *.c -o test
    qsort_strparray.c:11: предупреждение: по умолчанию возвращаемый тип функции - ‘int’
    qsort_strparray.c: In function ‘main’:
    qsort_strparray.c:31: ошибка: ‘Func’ undeclared (first use in this function)
    qsort_strparray.c:31: ошибка: (Each undeclared identifier is reported only once
    qsort_strparray.c:31: ошибка: for each function it appears in.)
    [guest@station tmp]$
    for this line in qsort call
    Code:
            (int (*)(const void *,  const void *)) Func
    do you know why ? because it uses it
    think, how it may not use it if it was qualified by the standard (for all function calls) ?

  14. #29
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Now I think if the pointer in qsort may be not a void pointer (because it casts void to char) and it doesn't break the standard, then it will cast char * to char ** by prototype rule, or it will assign char * to char ** by definition rule
    hence
    it is incorrect if we write a function for any other type of qsort fourth argument int (*)(const void *, const void *)
    maximally, we can use int (*)(void *, void *) that's all

    (in K&R there is no casting of void * to char * in the non-standard qsort)

  15. #30
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    No, though, I don't see the difference

    The example qsort casts void * to char * inside, but if the void pointer was made from char **, it will break the standard (we can't cast char ** to char *)
    If it will work correctly, then it will work correctly in Func, if it will not work correctly in Func, it will not work correctly inside qsort even if Func will be int Func(const void *, const void *)

    Code:
    static int compar(const void *l, const void *r)
    {
        const struct car *left = l;
        const struct car *right = r;
        ...
    how does it will work if const void *l and const void *r was made from char ** ?
    and if it will work, how does it differ from the direct declaration in the definition ?

    so I'm at first point

    remove .txt extension from zip file and look for the code
    Attached Files Attached Files
    Last edited by c.user; 05-17-2009 at 12:20 AM.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 11:43 AM
  2. Replies: 2
    Last Post: 07-11-2008, 08:39 AM
  3. How to sort an array of pointers to structure
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 06-30-2008, 03:52 PM
  4. Sorting strings in an array
    By JLan in forum C Programming
    Replies: 4
    Last Post: 11-29-2003, 05:10 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 01:04 PM

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