Casting function pointers

问题:

I am writing a function that receives a pointer to a comparison function and an array of MyStructs and is supposed to sort the array according to the comparison function:

void myStructSort(
                  struct MyStruct *arr,
                  int size,
                  int (*comp)(const struct MyStruct *, const struct MyStruct *)) {
  qsort(arr, size, sizeof(struct MyStruct), comp);
}

Unfortunately this doesn't compile because qsort expects the comparator to receive void * arguments and not const struct MyStruct *. I thought of several bad solutions and was wondering what the correct solution is.

Option 1

Cast comp to int (*)(const void *, const void*). This compiles but is undefined behavior (see this SO question).

Option 2

Create a global variable int (*global_comp)(const struct MyStruct *, const struct MyStruct *) and set global_comp=comp inside myStructSort. Then create a function:

int delegatingComp(const void *a, const void *b) {
  return globalComp((const struct MyStruct *)a, (const struct MyStruct *)b);
}

And in myStructSort call qsort(arr, size, sizeof(struct MyStruct), delegatingComp). The problem with this is the icky global variable.

Option 3

Reimplement qsort. This is functionally safe but very bad practice.

Is there a magical perfect fourth option?

Edit

I can't change the API of myStructSort and I am compiling my code using gcc c99 -Wall -Wextra -Wvla.

回答1:

Option 2 breaks thread-safety, so I wouldn't choose that one.

Option 3 is just plain wrong as you point out. There is no reason to re-implement quicksort and potentially make a mistake.

Option 1 is UB but it will work on any sane compiler. If you choose this option be sure to add a comment.

I would also consider:

Option 4. Redesign the interface of myStructSort to take int (*)(const void *, const void*) or scrap it entirely and call qsort directly. Basically send it back to the architecht, because he made a poor design choice.

回答2:

following approach only works for gcc. It's a part of gnu extension. further please reference to https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Nested-Functions.html#Nested-Functions

first let's make sure the prototype of qsort is in such a form:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

then you can:

void myStructSort(
                  struct MyStruct *arr,
                  int size,
                  int (*comp)(const struct MyStruct *, const struct MyStruct *)) {
  int comparator(const void * a, const void *b) {
    return comp((const struct MyStruct *)a, (const struct MyStruct *)b);
  }
  qsort(arr, size, sizeof *arr, comparator);
}

But again, since it uses gnu extension, don't expect too much portability.

ABOUT YOUR COMMENT: for modern gcc, gnu standard is default instead of iso ones. specifically, lastest gcc should use gnu11 standard. older ones are using gnu89. so, I don't know about your command line params, but if -std is not set, this will work.

following is an example taken from info gcc, just in case the link is dead. it shows a closure-like usage of nested function:

 bar (int *array, int offset, int size)
 {
   int access (int *array, int index)
     { return array[index + offset]; }
   int i;
   /* ... */
   for (i = 0; i < size; i++)
     /* ... */ access (array, i) /* ... */
 }

回答3:

If you are using gcc, then you can use the qsort_r function in glibc since 2.8, which allows you to specify a comparator function with an additional user-supplied argument:

void qsort_r(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *, void *),
             void *arg);

This is not portable, of course, and it requires you to define the feature-test macro:

#define _GNU_SOURCE

(On FreeBSD -- and, presumably, Mac OS X -- there is a similar but incompatible qsort_r; the difference is that the user-supplied context argument is provided as the first argument to the comparison function, rather than the last argument.)

But if you have it, it allows you to avoid the global in option 2:

/* This struct avoids the issue of casting a function pointer to
 * a void*, which is not guaranteed to work. It might not be
 * necessary, but I know of no guarantees.
 */
typedef struct CompContainer {
   int (*comp_func)(const struct MyStruct *, const struct MyStruct *);
} CompContainer;

int delegatingComp(const void *a, const void *b, void* comp) {
  return ((CompContainer*)comp)->comp_func((const struct MyStruct *)a,
                                           (const struct MyStruct *)b);
}

void myStructSort(
              struct MyStruct *arr,
              int size,
              int (*comp_func)(const struct MyStruct *,
                               const struct MyStruct *)) {
  const CompContainer comp = {comp_func};
  qsort_r(arr, size, sizeof(struct MyStruct), delegatingComp, &comp);
}

(Live on ideone)

回答4:

The correct approach is to cast from void const * to MyStruct const * in the comparison function.

This is well-defined for the first object, because the pointer that was passed to the comparison function was created by a cast from MyStruct const * to void const *, and casting a pointer to void back to its original type is allowed (and it's really the only thing that is).

For the other array members, it is assumed that casting void const * to char const *, adding the offset of the object, generated by multiplying the object size with the position of the object in the array, and casting that back to void const * will give a pointer that can be cast back to MyStruct const *.

That is a bold assumption, but usually works out. There may be corner cases where this doesn't work, but in general compilers pad any struct foo to a multiple of its alignment to ensure that array members' start addresses have a distance of sizeof(struct foo).

Casting function pointers is generally unsafe and needs to be avoided, as different data types may have different representations -- for example, a void * must be able to express every possible address as it could have been converted from a char *, while a MyStruct * is guaranteed to have a few of the least significant bits clear as any valid object would be aligned -- so it is entirely possible that the calling convention for these types could be different.

回答5:

The only sane option is to re-write the interface you've created, or make a new one.

I've done something very similar with bubble sort on another answer of mine.

In short, with C, you want your sort function to be of the form:

void* bubbleSort(void* arr, int (*compareFcn)(void*, void*),
    size_t sizeOfElement, size_t numElements)

And your comparison function to be of the form:

int compareFunction(void *a, void *b);