0000142: alphasort prototype incompatible with qsort comparison function

Austin Group Defect Tracker

Aardvark Mark IV

Viewing Issue Simple Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Category

Severity

Type

Date Submitted

Last Update

0000142

[1003.1(2008)/Issue 7] System Interfaces

Objection

Error

2009-09-03 18:45

2009-09-17 16:15

Reporter

cjwatson

View Status

public

Assigned To

ajosey

Priority

normal

Resolution

Rejected

Status

Resolved

Name

Colin Watson

Organization

Canonical Ltd.

User Reference

Section

alphasort

Page Number

Line Number

Interp Status

---

Final Accepted Text

Summary

0000142: alphasort prototype incompatible with qsort comparison function

Description

IEEE Std 1003.1-2008 declares alphasort as:

  int alphasort (const struct dirent **, const struct dirent **);

Most pre-standard implementations of alphasort declared it as:

  int alphasort (const void *, const void *);

This includes 4.3BSD, the BSDs in general, and GNU libc. (Linux libc 4 and 5 used const struct dirent **, according to the alphasort manual page on GNU/Linux, but the GNU C library 2.0 and later returned to the BSD prototype.)

alphasort has often been used as a qsort comparison function, and its pre-standard type was amenable to this. Unfortunately, the type given in 1003.1-2008 is not. According to my best reading of C99, pointers to functions taking pointer arguments of different types are not of compatible type, and GCC issues a diagnostic.

The effect of this is to require previously-correct (albeit non-standard) programs to either tolerate a diagnostic or use a wrapper function to mediate between qsort and alphasort. Neither seems very elegant.

Note that the standard's page for qsort and alphasort refer to each other in their SEE ALSO sections, suggesting that they are intended to be used together. The qsort(3) manual page on at least my implementation (GNU/Linux) goes further and gives alphasort as an example of a function suitable for use as the comparison function. As such, it is likely that a reasonable body of code has been written with this assumption, and indeed the incompatible types were brought to my attention by a maintainer of a package including such code.

As a test case, the following transcript shows a program (which omits error-checking for brevity) to write a sorted list of directory entries in the current directory to standard output. The transcript also includes the diagnostic produced using GCC 4.4.1 and glibc 2.10.1.

<cjwatson@sarantium ~>$ cat sort.c
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <dirent.h>

int main (int argc, char *argv[])
{
        DIR *dir;
        struct dirent *entry, **entries;
        int n_entries = 0, max_entries = 16, i;

        dir = opendir (".");
        entries = malloc (max_entries * sizeof *entries);
        while ((entry = readdir (dir)) != NULL) {
                if (n_entries >= max_entries) {
                        max_entries *= 2;
                        entries = realloc (entries,
                                           max_entries * sizeof *entries);
                }
                entries[n_entries] = malloc (sizeof *entry);
                memcpy (entries[n_entries], entry, sizeof *entry);
                ++n_entries;
        }
        closedir (dir);

        qsort (entries, n_entries, sizeof *entries, alphasort);

        for (i = 0; i < n_entries; ++i)
                printf ("%s\n", entries[i]->d_name);

        return 0;
}
$ gcc -Wall -o sort sort.c
sort.c: In function 'main':
sort.c:26: warning: passing argument 4 of 'qsort' from incompatible pointer type
/usr/include/stdlib.h:710: note: expected '__compar_fn_t' but argument is of type 'int (*)(const struct dirent **, const struct dirent **)'

Desired Action

Ideally, POSIX should return to the BSD prototype so that alphasort and qsort are compatible again. This would also involve a change to scandir to avoid the same problem in reverse. Implementations might need to use feature test macros to use different declarations depending on the version of POSIX requested.

Less ideally, a standard typedef for qsort's comparison function would help, to make it easier to use casts. However, casts are of course a good way to bypass type-safety and so this would not be a particularly good solution in itself.

Notes
(0000215) cjwatson (reporter) 2009-09-03 19:42	Oh, also, a rationale entry about the differences with traditional implementations would be nice. (I understand that some implementations, e.g. Solaris, have historically used the stricter prototypes.)

(0000233) msbrown (manager) 2009-09-17 16:15	The alphasort function must be made typesafe, so we do not intend to change this.

Issue History
Date Modified	Username	Field	Change
2009-09-03 18:45	cjwatson	New Issue
2009-09-03 18:45	cjwatson	Status	New => Under Review
2009-09-03 18:45	cjwatson	Assigned To	=> ajosey
2009-09-03 18:45	cjwatson	Name	=> Colin Watson
2009-09-03 18:45	cjwatson	Organization	=> Canonical Ltd.
2009-09-03 18:45	cjwatson	Section	=> alphasort
2009-09-03 18:45	cjwatson	Page Number	=> ?
2009-09-03 18:45	cjwatson	Line Number	=> ?
2009-09-03 19:42	cjwatson	Note Added: 0000215
2009-09-17 16:15	msbrown	Interp Status	=> ---
2009-09-17 16:15	msbrown	Note Added: 0000233
2009-09-17 16:15	msbrown	Status	Under Review => Resolved
2009-09-17 16:15	msbrown	Resolution	Open => Rejected

Relationships