As a continuation to the discussion on Purpose of Pointers to Functions, let’s step up the complexity and have an array of function pointers. This time, we’ll use C++ because we’ll need the inheritance for demonstration 🙂
Array of Callbacks
What’s the purpose of having an array of function pointers?
Let’s say you’re building a physics simulator that needs to check for collision between different geometric objects. Let’s say our objects are: point, square, circle. We can have simple declarations for these like so:
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 |
enum GeometricObject_t { POINT = 0, RECT, CIRCLE, GEOMETRIC_OBJECT_COUNT, }; class GeometricObject { GeometricObject_t type; int x, y; public: GeometricObject_t GetType(); virtual ~GeometricObject(); /* polymorphism */ /* more stuff */ }; class Point : public GeometricObject { /* more stuff */ }; class Rectangle : public GeometricObject { int width, height; /* more stuff */ }; class Circle : public GeometricObject { int radius; /* more stuff */ }; |
The virtual destructor is necessary to indicate that GeometricObject is a polymorphic class. It’s a requirement in order to use dynamic_cast<>, though we will not demonstrate it here in this post.
The destructor doesn’t do anything, for now. The GetType() is just a getter for the private member, type.
1 2 3 |
GeometricObject_t GeometricObject::GetType() { return type; } GeometricObject::~GeometricObject() {} |
Let’s say we store all the objects in a container (like std::vector).
1 |
std::vector<GeometricObject> GeomObjList; |
We add some elements in some part of our code and we do brute force collision testing.
1 2 3 4 5 6 7 8 |
/* for every pair of geometric objects, test for collision */ for (int i = 0; i < GeomObjList.size(); ++i) { for (int j = i + 1; j < GeomObjList.size(); ++j) { if (TestCollision(GeomObjList[i], GeomObjList[j])) { /* a collision was detected, do something */ } } } |
The collision test above is brute force because it checks if every pair of geometric objects are colliding. If I had 4 object instances; A, B, C, and D, there will be a total of 6 collision tests: A-B, A-C, A-D, B-C, B-D, C-D. There are optimizations for this but it’s not the point of this post. The TestCollision() function returns non-zero (true) when the two objects are colliding.
Knowing that there are 3 geometric object types, we’ll need to implement 9 different collision tests for each pair of types.
Point | Rect | Circle | |
---|---|---|---|
Point | PtPt | PtRect | PtCircle |
Rect | RectPt | RectRect | RectCircle |
Circle | CirclePt | CircleRect | CircleCircle |
I know what you’re thinking, there are duplicate functions. For example, PtRect and RectPt should be the same. Technically, they are indeed the same. The only difference is the order of the parameters. Basically, you just need to implement one, let’s say PtRect, and RectPt will call PtRect with flipped parameters. Same goes with PtCircle/CirclePt and RectCircle/CircleRect. We only need 6 collision test functionalities but we need 9 for implementation.
1 2 3 4 5 6 7 8 9 |
char CollisionTest_PtPt(GeometricObject &a, GeometricObject &b); char CollisionTest_PtRect(GeometricObject &a, GeometricObject &b); char CollisionTest_PtCircle(GeometricObject &a, GeometricObject &b); char CollisionTest_RectPt(GeometricObject &a, GeometricObject &b); /* Calls _PtRect*/ char CollisionTest_RectRect(GeometricObject &a, GeometricObject &b); char CollisionTest_RectCircle(GeometricObject &a, GeometricObject &b); char CollisionTest_CirclePt(GeometricObject &a, GeometricObject &b); /* Calls _PtCircle*/ char CollisionTest_CircleRect(GeometricObject &a, GeometricObject &b); /* Calls _RectCircle*/ char CollisionTest_CircleCircle(GeometricObject &a, GeometricObject &b); |
Let’s go back to the TestCollision() function. The intuitive way to implement the function is to have a nested if-else-if or switch statement. The outer switch statement would check the type of the first parameter and the inner switch statement would check the type of the second parameter.
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 46 47 48 49 50 51 52 53 |
char TestCollision(GeometricObject &a, GeometricObject &b) { switch (a.GetType()) { case POINT: switch (b.GetType()) { case POINT: return CollisionTest_PtPt(a, b); break; case RECT: return CollisionTest_PtRect(a, b); break; case CIRCLE: return CollisionTest_PtCircle(a, b); break; default: break; } break; case RECT: switch (b.GetType()) { case POINT: return CollisionTest_RectPt(a, b); break; case RECT: return CollisionTest_RectRect(a, b); break; case CIRCLE: return CollisionTest_RectCircle(a, b); break; default: break; } break; case CIRCLE: switch (b.GetType()) { case POINT: return CollisionTest_CirclePt(a, b); break; case RECT: return CollisionTest_CircleRect(a, b); break; case CIRCLE: return CollisionTest_CircleCircle(a, b); break; default: break; } break; default: break; } return 0; } |
Actually, it’s already optimized but it’s just not obvious.
Instead of having the TestCollision() function, we could have a collision test map. The collision test map is a 2D array of pointers to functions. This way, the table above would be more intuitive to update when the need for additional Geometric Objects arise.
1 2 3 4 5 6 7 |
typedef char (*CollisionTest)(GeometricObject &a, GeometricObject &b); /* set up collision test map */ CollisionTest collisionTest[GEOMETRIC_OBJECT_COUNT][GEOMETRIC_OBJECT_COUNT] = { { CollisionTest_PtPt, CollisionTest_PtRect, CollisionTest_PtCircle }, { CollisionTest_RectPt, CollisionTest_RectRect, CollisionTest_RectCircle }, { CollisionTest_CirclePt, CollisionTest_CircleRect, CollisionTest_CircleCircle } }; |
This is called a jump table. Instead of having conditions to determine which function to execute, you store the functions in an array and use the index as the “condition”. Notice how the assignment of the collision test functions resemble the table above? This makes updating easier when new geometric objects come about. We don’t need to change the size of the 2D array, we just need to include additional elements into the enum.
Now that we have the jump table, instead of checking via the TestCollision() function, we call the appropriate collision test based on the type.
1 2 3 |
if (collisionTest[GeomObjList[i].GetType()][GeomObjList[j].GetType()](GeomObjList[i], GeomObjList[j])) { /* a collision was detected, do something */ } |
This guarantees that no conditions need to be checked.
Now, one might ask themselves, isn’t the switch statement automatically converted to a jump table? The answer is no. A switch statement only becomes a jump table when the perfect conditions are met. The conditions are:
- No fall through (all cases end with a break)
- Case expressions are beautifully enumerated (starts with 0, increments by one)
In our case above, we set the enum GeometricObject_t to start with 0 and the succeeding values are 1 greater than the previous. Which means, we have a perfect switch statement!
In other words, I just demonstrated to you how the C/C++ compiler optimizes a perfect switch statement to a jump table.
Jump Map
What if you don’t have an ideal switch statement? Your next best bet would be a Jump Map. A jump map uses the STL container <map> instead of arrays. For single dimension, it would look like this:
1 2 3 4 5 |
typedef char (*FuncPtr)(); std::map<int, FuncPtr> mapOfFuncs; mapOfFuncs[0] = someFuncA; mapOfFuncs[10] = someFuncB; mapOfFuncs[-200] = someFuncC; |
For more than 1 dimension, it gets a bit tricky.
1 2 3 4 5 6 7 8 9 10 |
std::map<int , std::map<int, CollisionTest> > collisionTest; collisionTest[POINT][POINT] = CollisionTest_PtPt; collisionTest[POINT][RECT] = CollisionTest_PtRect; collisionTest[POINT][CIRCLE] = CollisionTest_PtCircle; collisionTest[RECT][POINT] = CollisionTest_RectPt; collisionTest[RECT][RECT] = CollisionTest_RectRect; collisionTest[RECT][CIRCLE] = CollisionTest_RectCircle; collisionTest[CIRCLE][POINT] = CollisionTest_CirclePt; collisionTest[CIRCLE][RECT] = CollisionTest_CircleRect; collisionTest[CIRCLE][CIRCLE] = CollisionTest_CircleCircle; |
It’s not pretty but this allows non-consecutive, non-zero-based indices. Running time isn’t constant like the 2D arrays but log n * log n is still fast.