I have written a Red Black tree implementation in C language. To allow it to use variable types, it only handles const void * elements, and initialisation of a tree must be given a comparison function with a signature int (*comp)(const void *, const void *). So far, so good, but I now try to use that C code to build an extension module for Python. It looks simple as first sight, because Python languages always pass references to objects which are received as pointers by C routines.
Python objects come with rich comparison operators. That means that from a C extension module, comparing 2 arbitrary objects is trivial: just a matter of using int PyObject_RichCompareBool(PyObject *o1, PyObject *o2, int opid).
But the comparison may return -1 to indicate that the objects are not comparable. In Python or C++ it would be simple enough to throw an exception to signal an abnormal condition. Unfortunately C has no notion of exception, and I could not find a way using setjmp-longjmp because:
longjmp time, when the internal function does not know what has been allocatedA simple solution is to give a third parameter to the comparison function for it to signal an abnormal condition. But when the library is used in a plain C environment, that third parameter just does not make sense. I then remembered that in the 80', I had learned that in C language, parameters were passed in the stack in reversed order and unstacked by the caller to allow functions with a variable number of parameters. That means that provided the first 2 parameters are correct passing a third parameter to a function expecting 2 should be harmless.
#include <stdio.h>
// declares a type for the comparison functions
typedef int (*func)();
// A simple function for comparing integers - only 2 params
int f1(int a, int b) {
return a - b;
}
/* Inserts a value into an increasing array
* By convention 0 denotes the end of the array
* No size control implemented for brievety
* The comp function recieves a pointer to an int
* to be able to signal abnormal conditions
* */
int insert(int* arr, int val, func comp) {
int err = 0;
while ((0 != *arr) && (comp(*arr, val, &err) < 0)) { // 1
if (err) return 0;
++arr;
}
do {
int tmp = *arr;
*arr = val;
val = tmp;
} while (0 != *arr++);
return 1;
}
int main() {
func f = &f1;
// a simple test with 3 parameters
int cr = f(3, 1, 5); // 2
printf("%d\n", cr);
// demo usage of the insert function
int arr[10] = {0};
int data[] = { 1,5,3,2,4 };
for (int i = 0; i < sizeof(data) / sizeof(*data); i++) {
insert(arr, data[i], f1);
}
for (int i = 0; i < sizeof(data) / sizeof(*data); i++) {
printf("%d ", arr[i]);
}
return 0;
}
At (1) and (2) the 2 parameter function is called with 3 parameters. Of course, this code compiles without even a warning in Clang or MSVC, and runs fine giving the expected result.
While this code works fine on common implementations, I wonder whether actually passing a third parameter to a function expecting only two is really legit or does it invokes Undefined Behaviour?
stdcall calling convention would not allow itThe originality of this question is that it uses function pointers conversions.
I think it invokes Undefined Behavior.
From 6.5.2.2p6:
If the expression that denotes the called function has a type that does not include a prototype, the integer promotions are performed on each argument, and arguments that have type float are promoted to double. These are called the default argument promotions. If the number of arguments does not equal the number of parameters, the behavior is undefined.
The proper solution is redesign the Red Black tree implementation to allow passing a context as a third parameter.
int (*comp)(const void *, const void *, void *);
It is highly recommended to add a context argument to any function pointer type to allow emulate closures.
As a workaround, you could use a global variable.
static int err;
int f1(int a, int b) {
err = 0;
return a - b;
}
int insert(int* arr, int val, int comp(int,int)) {
err = 0;
while ((0 != *arr) && (comp(*arr, val) < 0)) { // 1
if (err) return 0;
++arr;
}
...
}
It is not the best solution because it is not re-entrant. Only a single instance of insert()/f1() can run at a time.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With