Thread: qsort() and pointer problem

I still don't like the idea of your function returning the same value for an invalid and a valid match. Additionally, your function now requires the use of another specifically named external variable. That's a poor choice in my opinion.


Quzah.

Originally Posted by c.user

I am recommend to control the program, and you are recommend to debug the program

Yes. This is like choosing between the use of an assertion and the use of an exception, except that a native exception mechanism is not available. I am asserting that this particular pre-condition should be checked with an assertion, making it the caller's responsibility to check that the arguments will be valid.

Actually, this would be more accurate:

Code:

int critter_cmp_namn(const void *a, const void *b)
{
    const person *lhs;
    const person *rhs;
    assert(a && b && "Person comparator arguments must not be null pointers.");
    lhs = *(const person**)a;
    rhs = *(const person**)b;
    assert(lhs && rhs && "Null pointers not allowed for person comparison.");
    return strcmp(lhs->fnamn, rhs->fnamn);
}

Or with respect to C99:

Code:

int critter_cmp_namn(const void *a, const void *b)
{
    assert(a && b && "Person comparator arguments must not be null pointers.");
    const person *lhs = *(const person**)a;
    const person *rhs = *(const person**)b;
    assert(lhs && rhs && "Null pointers not allowed for person comparison.");
    return strcmp(lhs->fnamn, rhs->fnamn);
}

Originally Posted by c.user

if it will be turned off what will happen if there will an incorrect data in that array ?

There would be undefined behaviour. In your case, there would be unexpected behaviour since the user would not know about nullflag. If the user would read the documentation for critter_cmp_namn and know that nullflag should be used, the user would then also know what are the pre-conditions and ensure that they are met, making nullflag redundant. That said, you perhaps could force the user to know about nullflag by not defining it in your library, but then you would be placing an extra burden on the users of your library.

The main problem here (and what quzah refers to) is that there is no way for the user to distinguish between an error and valid output. Contrast this to errno, where the caller would be notified of an error by the return value (or possibly an out parameter), and then would check errno as a secondary step.

Originally Posted by quzah

I still don't like the idea of your function returning the same value for an invalid and a valid match.

Neither do I.

Okay, it's time I showed you a way do it that doesn't involve returning problematic values that make item ordering inconsistent:

Code:

int critter_cmp_namn (person **p1, person **p2)
{
    if (!p1) {
        if (!p2)
            return 0;
        return 1;
    } else if (!p2)
        return -1;
    if (!*p1) {
        if (!*p2)
            return 0;
        return 1;
    } else if (!*p2)
        return -1;
    return strcmp ((*p1)->fnamn, (*p2)->fnamn);
}

Tada - NULL pointers are no longer a problem here!
This comparison method causes all non-null items to be sorted first in the array (in order of course), followed by any items where the person* is NULL, followed by any items where the person** is NULL.
So after sorting you can simply check the last item to see if the person** or person* is NULL, to see if there are any NULL items.
You could still set an error flag if the comparison function ever returns before reaching the strcmp, but you probably don't need to now.

Originally Posted by c.user

if he wants to delete structure from the array when it filled, he frees the pointer and then write the NULL to the array to that pointer place
now he can print all structures with skipping NULLs and for the array size

That is a good point. If you think that comparing something with nothing makes sense because of the practical benefit of allowing the user to maintain a sorted array after removing elements in the middle, then go ahead and allow null pointers in the pre-condition to the comparator.

Originally Posted by c.user

how you can prevent implementation of this operator if asserts are turned off ?

You are missing the point. My point is that I think that it makes sense for the pre-condition of the comparator to forbid null pointers. Consequently, it is not the comparator's job to check for such null pointers. The comparator should do so as a debugging aid by using asserts, but that is all.

Originally Posted by c.user

and what is your advise ? just to make an assert ? no, just to change his algorithm, or programme will fall

Precisely. If it makes sense for the pre-condition of the comparator to disallow null pointers, then the user of that comparator should obey the pre-condition.

Originally Posted by c.user

I am recommend to control the program, and you are recommend to debug the program
if it will be turned off what will happen if there will an incorrect data in that array ?

Your program will malfunction.

The purpose of assertions is to catch conditions which SHOULD NEVER OCCUR. Other code should exist which helps to ensure that these "impossible" conditions are truly impossible. Assertions are not included in release mode, because presumably, your testing has already uncovered all situations where the assertions can be triggered, and you have implemented solutions which prevent it from happening.

Once again, assertions are not checks, they are statements of fact. A statement "assert(x)" means "x is true. I know it's true. It has to be true. If it is not true, explode violently, because the world is falling apart."

Originally Posted by c.user

My comparator doesn't need new function which will move this NULLs to the end of the array before the sorting

That is true. Your comparator also does more work by having to check for null pointers. That is fine, because the pre-conditions are different. In cases where the caller can prove that null pointers are not present (e.g., the user always swaps with the last remaining element when removing an element), my version of the comparator would be better.

Originally Posted by c.user

And it is possible to realise such that it will save their places without moving to the end

That statement combined with your last post leads me to believe that you think you can use qsort and guarantee that it will not move the NULL elements.
That is simply impossible. You have no control over absolute position of the entries.
Sorting from this
B - A - C - NULL - E - G - F - NULL - D ...
to this:
A - B - C - NULL - D - E - F - NULL - G ...
cannot be done simply through a call to qsort. The closest attempt you could make at that would be for your comparison function to sort based on the position of each item when either one of them contains NULL.
However your example above helps me illustrate why that is not possible. Consider items D, G, and the NULL between them. This comparison function would return values indicating the following:
G < NULL
NULL < D
D < G
Which if we combine those all together we can obtain:
G < D < G
and viola - you're breaking transitivity again.

I shall revise what I posted earlier though. p1 and p2 should really be checked by an assert if anything:

Code:

int critter_cmp_namn (person **p1, person **p2)
{
    assert(p1 && p2);
    if (!*p1) {
        if (!*p2)
            return 0;
        return 1;
    } else if (!*p2)
        return -1;
    return strcmp ((*p1)->fnamn, (*p2)->fnamn);
}

But you're really not fully understanding the role of a comparison function. You have got to stop thinking of it in terms of the array of items itself, and start thinking of it as a function that will give a consistent (transitive) answer for every possible pair of items in the array, according to how you want every pair of items to be ordered. You have no control what two items are ever compared to each other during the sort, so every possible comparison between two items must give the desired result.

If you wanted to maintain the position of the NULLs, you'd have to have a preprocessing step that recorded their position and moved them to the end, and a post-processing step that put them back.

Originally Posted by c.user

when he has 1000000 elements he deletes 500000th element it needs to move 500000 elements to the left
and if he uses pointers it is easier to delete them by assigning NULL to 500000th

That is not required, and the very text of mine that you quoted presented an alternative: swap the element to be removed with the remaining last element. If the elements are pointers, the removed element could be set to be a null pointer, perhaps after deallocating associated memory. This could of course lead to the array being no longer in sorted order, but in some situations that could be fine, possibly with a sort being performed after a series of such removals to restore the order.

Of course, yet another case where the caller can prove that null pointers are not present is when the array simply has no "holes" because each pointer points to an object and no element has been removed in any way.