NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/c/16068

Text File | 1992-11-07 | 6.8 KB | 177 lines

Path: sparky!uunet!europa.asd.contel.com!emory!swrinde!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!agate!dog.ee.lbl.gov!horse.ee.lbl.gov!torek
From: [e-mail] (Chris Torek)
Newsgroups: comp.lang.c
Subject: qsort comparison functions (was "Help.  (Unix C)")
Date: 6 Nov 1992 09:52:25 GMT
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 164
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]>
Reply-To: [e-mail] (Chris Torek)
NNTP-Posting-Host: 128.3.112.15

First, some Network Etiquette:
    - Choose descriptive subject lines.  `Help' is rarely
      descriptive.
    - Ask Unix-specific questions in Unix-specific groups.  (The
      original question was not Unix-specific, as it turns out.)
    - Read the FAQ.

Now: the fourth argument to qsort---the pointer to a comparison
function---must be compatible with the type:

    int (*)(const void *, const void *)

This type can be described in pseudo-English as:

    pointer to function of (
        pointer to read-only generic,
        pointer to read-only generic
    ) returning int

Note that the type `pointer to generic' (whether the generic's are
read-only or read/write) is a separate type in C, quite distinct from
types such as `pointer to struct foo'.  ANSI C requires that it have
the same underlying representation as `pointer to char'---this is
required for backwards compatibility---and as a result one can often
get away with interchanging `char *' and `void *', but they are not
in fact identical.

If the comparison function is ever actually called, not only must the
type signatures of the pointers agree, but the actual function to which
the pointer points must in fact have the final agreed-upon type.  If
the function is not called, this is unnecessary (all function pointers
`fit' in all other pointers, but every actual call site must use the
same type signature as the corresponding actual callee; see the ANSI
standard for details).  It is not immediately obvious whether this
means that, e.g., `qsort(base, 0, width, (int (*)(const void *, const
void *))abort)' is OK, although I would be somewhat surprised to find
implementations that call the function if the number of elements being
sorted is less than 2.

In article <[e-mail]> [e-mail] (Larry Jones) notes:
>>An ANSI compiler will, quite properly, object to this code ...

Actually, there are (at least) two cases to consider:

    A) Old-style declarations.  In this case the compiler lacks
       the information it needs to detect errors.  For instance:

        extern int cmp();
        qsort(table, n, sizeof(int), cmp);

       Is cmp() correct?  We have no idea, and neither does the
       compiler (unless there is something else here we have not
       seen).

    B) New-style declarations.  In this case the compiler has
       the necessary information:

        extern int cmp(int *, int *);    /* oops! */
        qsort(table, n, sizeof(int), cmp);

If you give the compiler full and correct information, as in example B,
it must diagnose any error.  If the compiler fails to emit `at least
one diagnostic' for example B, it is not ANSI conformant.

Of course, you can give the compiler full but incorrect information:
If cmp() is defined in another file, you can write:

        extern int cmp(void *, void *);
        qsort(table, n, sizeof(int), cmp);

even if cmp() actually takes two `int *'s.  Alternatively, you can use
example A to withhold the full information.  In either case you have
lied to the compiler, and, to quote Henry Spencer, `it will get its
revenge.'  Maybe not today, but eventually....

>>Some implementations use the same representation for all pointer types
>>and on those implementations you can misdefine the function and it will
>>work, but this is not guaranteed and there are systems where it will
>>fail.

This is correct, although in fact `most implementations' is probably
more accurate than `some implementations', at least if we do not get
into the various memory models on IBM PCs.  The current known set of
manufacturers/models on which different pointers either use different
representations, or carry runtime checking information, is fairly small
(Prime; Honeywell-Bull; Symbolics Lisp Machines; Data General Nova and
Eclipse; IBM PCs with memory models).

(There exist interpreter-based systems (e.g., CenterLine C) that will
carry type signatures with actual objects and values and will detect
mismatches.)

In article <[e-mail]>
[e-mail] (Dave Fuller) comes back with:
>But, even on an ANSI compiler this will work. void is used to take on
>no predetermined meaning, or to actually mean return NOTHING from a
>function if used as a declaration type.

Not exactly.  `void' has two meanings in ANSI C:

    - A void value is a value from the empty set.  A value can
      be cast to void type to indicate `I really do mean to ignore
      this value; I am not ignoring it by mistake.'  Void values
      may not be used (see parallel comp.std.c discussion as to
      whether the standard defines `use').

    - A `pointer to (optionally qualified) void', or `void *', is
      a `generic pointer' type that is *assignment compatible* with
      all other object pointer types.  `Assignment compatible' means
      that it is not an error to write:

        TY *p;    /* where `TY' is any object type */
        void *q;

        p = q;    /* legal */
        q = p;    /* legal */

      It does *not* mean that `void *' values are the *same* type
      as other object pointers, although they may or may not share
      underlying representations (and, again, in the special case
      of `char *', they must in fact share representations).

>Also, the strcmp() function is used QUITE OFTEN in qsort.

Such usage is questionable.  In any case, strcmp can only be used
directly when arrays of type (array N of char) are being sorted.  I
find that most string sorts operate on arrays of type (pointer to char),
where a mediator function must be used:

    char *tab[MAX];
    ...
    qsort(tab, n, sizeof(char *), collate);

In this case collate() should be defined along the lines of:

    int
    collate(void *a, void *b)
    {
        char **x, **y;

        x = a;
        y = b;
        return strcmp(*x, *y);
    }

>And if the code were not portable, it compiles and works on a non-ansi
>compiler (and all of the ANSI ones i tried) ...

As the FAQ says:

5.12:   Why won't the Frobozz Magic C Compiler, which claims to be ANSI
    compliant, accept this code?  I know that the code is ANSI,
    because gcc accepts it.

A:      Most compilers support a few non-Standard extensions, gcc more
    so than most.  Are you sure that the code being rejected doesn't
    rely on such an extension?  It is usually a bad idea to perform
    experiments with a particular compiler to determine properties
    of a language; the applicable standard may permit variations, or
    the compiler may be wrong.

--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE ([phone])
Berkeley, CA        Domain:    [e-mail]