Globals: Best option when callback function parameters don't provide enough information in C?

Question

Lets take qsort()'s comparison callback function as an example

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

What happens when the result of the comparison function depends on the current value of a variable? It appears my only two options are to use a global var (yuck) or to wrap each element of the unsorted array in a struct that contains the additional information (double yuck).

With qsort() being a standard function, I'm quite surprised that it does not allow for additional information to be passed in; something along the lines of execv()'s NULL-terminated char *const argv[] argument.

The same thing can be applied to other functions which define a callback that leave no headroom for additional parameters, ftw() & nftw() being two others I've had this problem with.

Am I just "doing it wrong" or is this a common problem and chalked up to an oversight with these types of callback function definitions?

EDIT

I've seen a few answers which say to create multiple callback functions and determine which one is appropriate to pass to qsort(). I understand this method in theory, but how would you apply it in practice if say I wanted the comparison callback function to sort an array of ints depending on how close the element is to a variable 'x'?. It would appear that I would need one callback function for each possible value of 'x' which is a non-starter.

Here is a working example using the global variable 'x'. How would you suggest I do this via multiple callback functions?

#include <stdint.h>
#include <stdio.h>
#include <math.h>

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

int x;

int main(void)
{
    int i;
    int bins[6] = { 140, 100, 180, 80, 240, 120 };

    x = 150;

    qsort(bins, 6, sizeof(int), bin_cmp);

    for(i=0; i < 6; i++)
       printf("%d ", bins[i]);

    return 0;
}

int bin_cmp(const void* a, const void* b)
{
    int a_delta = abs(*(int*)a - x);
    int b_delta = abs(*(int*)b - x);

    if ( a_delta == b_delta )
        return 0;

    return a_delta < b_delta ? -1 : 1;
}

Output

140 180 120 100 80 240 

Answer 1

With qsort's signature being what it is, I think your options are pretty limited. You can use a global variable or wrap your elements in structs as you suggested, but I'm not aware of any good "clean" way of doing this in C. I imagine there are other solutions out there, but they won't be any cleaner than using global variables. If your application is single-threaded, I would say this is your best bet as long as you're careful with the globals.

Answer 2

Change the value of the function pointer. The whole point (no pun intended) of function pointers is that the user can pass in different functions under different circumstances. Rather that passing in a single function which acts differently based on external circumstances, pass in different functions based on the external circumstances.

This way, you only need to know about the values of variables in the context of the call to qsort() (or whatever function you're using), and write a couple different simpler comparison functions instead of one big one.

In response to your edit

To deal with the issue described in your update, just use to the global variable by name in your comparison function. This will certainly work if you are storing the variable at the global scope, and I believe qsort() will be able to find it at most other (public) scopes visible to the comparison function definition, as long as the scope is fully qualified.

However, this approach won't work if you want to pass a value straight into the sorting process without putting it in a variable.

Answer 3

You will have to prepare several function callbacks and check the value before running qsort, then send the correct one.

Answer 4

I'd listen to tlayton, and wrap that logic in a function that returns a pointer to the appropriate comparison function.

Answer 5

It sounds like you need the bsearch_s() and qsort_s() functions defined by TR 24731-1:

§6.6.3.1 The bsearch_s function

Synopsis

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
void *bsearch_s(const void *key, const void *base,
                rsize_t nmemb, rsize_t size,
                int (*compar)(const void *k, const void *y, void *context),
                void *context);

§6.6.3.2 The qsort_s function

Synopsis

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
                int (*compar)(const void *x, const void *y, void *context),
                void *context);

Note that the interface has the context that you need.

Something rather close to this should be available in the MS Visual Studio system.

Answer 6

You can write your own specialized qsort implementation and customize it to your need. To give you an idea about how short it is, this is a qsort implementation with your delta.

void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void yourQsort(int arr[], int beg, int end, int delta)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      //Here use your var something like this
      int a_delta = abs(arr[l] - delta);
      int b_delta = abs(piv - delta);
      if (a_delta <= delta)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    yourQsort(arr, beg, l, delta);
    yourQsort(arr, r, end, delta);
  }
}

More C-optimized implementations are said to be here.

Answer 7

IMO, go with the global. The problem is that you're really asking qsort to do two things, both sort and map, where it's only designed to do the first.

The other thing you could do is break it down into a couple steps. First compute an array of these (one for each element of the source array):

struct sort_element {
    int delta; // This is the delta value 
    int index; // This is the index of the value in the source array
 }

Call qsort on that array, using a sort function that compares delta values. Then you use the index'es on the sorted array to order your original array. This consumes some memory, but it may not matter that much. (Memory is cheap, and the only thing you have to store in the temporary array is the key, not the entire value.)