Thread: Using qsort to sort an array of strings

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.

Originally Posted by c.user

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.

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)

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

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 ?

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 ?

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

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