CODEWITHSUNDEEP
cpointers
iceman
iceman

Reputation: 2130

C: Is it possible to have a recursive function that takes an array of function-pointers as one of its arguments?

Here's the longer version. (The TL;DR version is in my post title.)

Let's consider a recursive quick_sort function which is currently set up as follows: (i) it takes one argument - a linked-list, (ii) it sorts elements in ascending order, and (iii) it returns a sorted linked-list. Illustrative code below (I can post actual code - which is obv longer - upon request). 

#include "list.h"  /*our linked-list implementation which includes definitions
                     for `concatenate`, which we use below*/

typedef int (*ordinal(int referenceValue, int currentValue));

int smaller(int referenceValue, int currentValue)
{
  return currentValue <= referenceValue ? 1 : 0;
}

int larger(int referenceValue, int currentValue)
{
  return currentValue > referenceValue ? 1 : 0;
}

List *getElements(List *fullList, ordinal compare)  /*let's assume this function exists*/
  /*implementation of getElements*/

List* quickSort(List* originalList)
{
  /*code to handle the two base cases, i.e., the cases
    in which the input list has either 0 or 1 elements */

  List *pivotElement = List_create();
  List_push(pivotElement, originalList->first->value);

  /*we're simply using the first element in the list as the pivot-point*/

  List *prePivotElements = quickSort( getElements(originalList, smaller) );
  List *postPivotElements = quickSort ( getElements(originalList, larger) );
  List *newList = concatenate(prePivotElements, pivotElement, postPivotElements);

  return newList;
}

Now let's say we wanted to modify our quick_sort function so that it takes two arguments: a linked-list AND an array of function pointers. The idea is to use the second argument (i.e., the array of function pointers) to specify the sort order. The syntax for the function call would look something like this: quick_sort(linked_list, increasing[]) or quick_sort(linked_list, decreasing[]).

I should mention that my focus is on understanding the feasibility of/the correct syntax for recursively passing arrays of function pointers and not so much on efficiency of algorithm, etc. In other words, let's try to ignore the horrible efficiency/memory-management aspects of this particular implementation of quick-sort :)

In order to modify quick_sort as described above, I thought that the following code might work...

#include "list.h" 

typedef int (*ordinal(int referenceValue, int currentValue));

int smaller(int referenceValue, int currentValue)
{
  return currentValue <= referenceValue ? 1 : 0;
}

int larger(int referenceValue, int currentValue)
{
  return currentValue > referenceValue ? 1 : 0;
}

/*two new global arrays of function pointers*/
int (*increasing[2]) (int referenceValue, int currentValue) = {smaller, larger};
int (*decreasing[2]) (int referenceValue, int currentValue) = {larger, smaller};

List *getElements(List *fullList, ordinal compare)
  /*implementation of getElements*/

/*updated argument list*/
List* quickSort(List* originalList, ordinal compare[])
{
  /*base cases*/
  List *pivotElement = List_create();
  List_push(pivotElement, originalList->first->value);

  /*updated recursive function call*/
  List *prePivotElements = 
              quickSort( getElements(originalList, compare[0]), compare );
  List *postPivotElements = 
              quickSort ( getElements(originalList, compare[1]), compare );
  List *newList = concatenate(prePivotElements, pivotElement, postPivotElements);

  return newList;
}

...but it results in the following errors: 

error: declaration of ‘compare’ as array of functions
   List* quickSort(List* originalList, ordinal compare[])
                                               ^
error: type of formal parameter 2 is incomplete
   List *prePivotElements = quickSort( getElements(originalList, compare[0]), compare );
   ^
error: type of formal parameter 2 is incomplete
   List *postPivotElements = quickSort ( getElements(originalList, compare[1]), compare );
   ^

To recap my question(s): Does C allow us to pass arrays of function pointers to other functions? What about doing so recursively? If it's allowed, what is the correct syntax?

Please pardon length of post, I'm sure one of you SO veterans would have been far more succinct!

(Regarding the SO rule that all posted code must compile: I thought that it made sense to stick to the conceptually relevant code in this case. However, if folks prefer, I can post the full .c file and .h file.)

Update: As requested here are the relevant files for the working version of quick_sort. I've also included the shell output, including commands for compiling/linking. FYI, code-pad is giving some weird errors that don't make any sense (e.g., on lines with correct/compilable function headers, it's claiming that I'm missing a parenthesis):

Upvotes: 2

Views: 103

Answers (1)

Jan Hudec
Jan Hudec

Reputation: 76346

typedef int (*ordinal(int referenceValue, int currentValue));

is incorrect. It is syntactically valid, but the parenthesis have no effect and it just defines a function type instead of pointer to function. The correct way to typedef a function pointer is

typedef int (*ordinal)(int, int);

that is the parenthesis go around the identifier and the * only (and the argument names are irrelevant).

And the function arrays would be better declared using that typedef instead of repeating the definition.

ordinal increasing[2] = {smaller, larger};

Upvotes: 5

Related Questions