In a previous post, I mentioned something about pointers to functions. Why would anyone need pointers to functions? In C/C++, they’re called function pointers. They also exist in other languages but the implementations are slightly different. In C#, they’re called delegates. Many OOP languages have interfaces with overrideable methods. In others, there’s the concept of lambda (anonymous) functions.
One common application of function pointers are Event Handlers. Event handlers are quite straight forward. Assign a function as an event handler and when that event is triggered, execute the corresponding function. See W3Schools for more info on JavaScript Event Handling. These functions are referred to as Callbacks.
In C#, they allow adding/subtracting of delegates. Adding a delegate simply adds that method to the list of methods that will be executed, one by one in the order they were added, when the event is triggered. Subtracting removes that method from the list. This allows having multiple listeners to a single event. See MSDN for more information.
What’s the point of pointers to functions?
Sorting
Let’s go back to C. Let’s say you wanted to make a generic quicksort for arrays of basic data types.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#define DATA_TYPE int void swap(DATA_TYPE *a, DATA_TYPE *b) { DATA_TYPE c = *a; *a = *b; *b = c; } void quicksort(DATA_TYPE arr[], int l, int r) { if (r <= l) return; /* terminating case */ int pivotIndex = l; /* pivot index, not yet final */ /* arr[r] is treated as pivot */ int i = l; while (i < r) { if (arr[i] < arr[r]) { /* list is in increasing order */ swap(&arr[i], &arr[pivotIndex]); pivotIndex++; } ++i; } swap(&arr[pivotIndex], &arr[r]); /* pivot is now in its final spot, pivot index is now correct */ quicksort(arr, l, pivotIndex - 1); /* recurse on left side */ quicksort(arr, pivotIndex + 1, r); /* recurse on right side */ } int main (int argc, char *argv[]) { int arr[] = {9, 7, 8, 6, 5, 3, 4, 2, 0, 1, 2, 3}; int size = sizeof(arr) / sizeof(int); /* print the array before sorting */ quicksort(arr, 0, size - 1); /* invoke quicksort() */ /* print the array after sorting */ return 0; } |
This would be ideal if ever you wanted to sort your lists in increasing order every time. But of course, that won’t always be the case. The line that determines the order of the elements is line #16.
1 |
if (arr[i] < arr[r]) { /* list is in increasing order */ |
If I wanted to make a quicksort that would yield a list in decreasing order, I just need to replace that “less than” to a “greater than”. That means, I need to copy the whole code except for that line. This defeats one of the purposes of functions which is modularity.
Callbacks to the Rescue
This problem can be easily solved by using callbacks. We pass an additional parameter, a pointer to a function taking 2 values and returning non-zero (true) if the former should come before the latter. Our quicksort now looks like this:
1 2 3 4 5 6 7 8 9 10 11 |
void quicksort(DATA_TYPE arr[], int l, int r, char (*comparator)(DATA_TYPE a, DATA_TYPE b)) { ... if (comparator(arr[i], arr[r])) { /* compare the two values */ ... quicksort(arr, l, pivotIndex - 1, comparator); /* recurse on left side */ quicksort(arr, pivotIndex + 1, r, comparator); /* recurse on right side */ } |
This way, we could have multiple comparators such as the following:
1 2 3 4 5 6 7 8 9 |
/* comparator for increasing order */ char less(DATA_TYPE a, DATA_TYPE b) { return a < b; } /* comparator for decreasing order */ char more(DATA_TYPE a, DATA_TYPE b) { return a > b; } |
And quicksort could be invoked like this:
1 |
quicksort(arr, 0, size - 1, more); /* for decreasing order */ |
These callbacks allow for Forward Compatibility. Meaning, I have my algorithms now and there may be new data types in the future. I implement a generic algorithm and you supply the comparator so my algorithm can work with data types that didn’t exist when the algorithm was created. To be even more generic, instead of having a DATA_TYPE define (or typedef), we could do everything in terms of pointers. See QuickSort in WikiBooks for a more generic solution.
Challenge
Create a comparator such that sorting a list would result in the following criteria:
- all odd numbers come before even numbers
- odd numbers are sorted in increasing order
- even numbers are sorted in decreasing order
Here’s an example of a sorted list: 1 3 3 5 7 9 9 11 20 14 12 10 10 2 0
Have fun!
C-style “OOP”
Before C++, C somewhat had an implementation of classes and methods by simply using structs. Of course, this is not truly OOP since there would be no inheritance or encapsulation. But it implements abstraction and polymorphism naturally.
Let’s say we want to have a Rectangle class with 2 methods: (1) compute for the area (2) compare the area with another Rectangle. The header file would contain the following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
typedef struct CRectangle* Rect_handle; /* Memory Allocation */ Rect_handle new_CRectangle(float w, float h); /* Memory Deallocation */ void delete_CRectangle(Rect_handle this); struct CRectangle { /* Properties */ float width, height; /* Methods */ float (*GetArea)(Rect_handle this); char (*IsBiggerThan)(Rect_handle this, Rect_handle other); }; |
The Rect_handle typedef there is just for convenience. It’s simply a pointer to a CRectangle structure.
The Memory Allocation is similar to the “new” keyword with a constructor, hence the function name. The Memory Deallocation is similar to memory allocation except for the parameter which is a pointer to the structure you wish to delete.
All the properties and methods are public. Unfortunately, encapsulation is not possible.
All the methods are pointers to functions where the first parameter is always a pointer to the structure under consideration. But if all the methods are just pointers, where are the implementations? Let’s check out the implementation file.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/*********************** Declarations of Methods ***********************/ /* These functions are not seen outside of this file but are attached to the class upon instantiation */ float CRectangle_GetArea(Rect_handle this); char CRectangle_IsBiggerThan(Rect_handle this, Rect_handle other); /*************** Implementations ***************/ /* Memory Allocation */ Rect_handle new_CRectangle(float w, float h) { Rect_handle newRect = malloc(sizeof(struct CRectangle)); if (!newRect) return 0; /* malloc failed */ /* Member Initialization */ newRect->width = w; newRect->height = h; /* Attach the methods */ newRect->GetArea = &CRectangle_GetArea; newRect->IsBiggerThan = &CRectangle_IsBiggerThan; return newRect; } /* Memory Deallocation */ void delete_CRectangle(Rect_handle this) { /* properly dispose of resources, if any */ /* deallocate this */ free(this); } float CRectangle_GetArea(Rect_handle this) { return this->width * this->height; } char CRectangle_IsBiggerThan(Rect_handle this, Rect_handle other) { return this->GetArea(this) > other->GetArea(other); } |
As you can see, this may be an implementation file but there are 2 function declarations there. By having functions declared inside an implementation file, we restrict those functions to be used only in this file. Therefore, those functions are not visible outside. Instead, we attach these functions to the structure so they can be used beyond the scope of this file.
You can see in the new_CRectangle() function that a memory allocation and initialization of properties and methods are executed. This is how the new keyword in many OOP languages work. It allocates memory then calls the constructor.
In the delete_CRectangle() function, it first releases any memory borrowed before deallocating the structure itself. This is how the delete keyword in many OOP languages work. It calls the destructor then it deallocates the memory.
Now, how do we use all this? The main file looks something like the following.
1 2 3 4 5 6 7 8 9 10 |
int main(int argc, const char * argv[]) { Rect_handle rectA = new_CRectangle(10, 20); Rect_handle rectB = new_CRectangle(15, 15); printf("RectA has an area of %.2f\n", rectA->GetArea(rectA)); printf("RectB has an area of %.2f\n", rectB->GetArea(rectB)); printf("RectA is %s than RectB\n", rectA->IsBiggerThan(rectA, rectB) ? "bigger" : "smaller"); return 0; } |
The usage is quite similar to what is commonly done in C++, with the exception of the first parameter of every method is a pointer to the object itself. One might ask, how does C++ actually implement these methods without the need to pass the a pointer to itself?
In C++, methods are still defined similarly as above but are not attached to the structure. Instead, whenever you invoke methods, the corresponding function is called with the first parameter being the invoking instance.
1 2 |
rectA->GetArea(); // CRectangle_GetArea(rectA); rectA->IsBiggerThan(rectB); // CRectangle_IsBiggerThan(rectA, rectB); |
(Note: name mangling is not shown)
Try to add the static keyword to make the symbols of the implementing functions as private
Pingback: Jump Table | Game Programmer + Teacher