Rex Jaeschke is an independent computer consultant, author and seminar leader. He participates in both ANSI and ISO C Standards meetings and is the editor of The Journal of C Language Translation, a quarterly publication aimed at implementers of C language translation tools. Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA, 22091 or via UUCP at uunet!aussie!rex.
This column started out as an example of using a void pointer to point at an object having one of a set of possible types. The intent was to also record the type to which it currently pointed and to discuss an efficient way of accessing the underlying object at a later time. I did achieve these goals but along the way, digressed into a number of other interesting areas as you shall see.
Void Pointers
ANSI C adopted the notion of a generic pointer from C++. A generic pointer is declared as void *pv and may point to any object or function. C does not require pointers to different types to have the same representation, and on word and segmented architectures there are often two or more different pointer representations. Since a generic pointer must be able to store an address with the smallest resolution and a char is the smallest addressable object in C, a void pointer must be at least as big as a char pointer. (In fact, ANSI C requires they have exactly the same representation.)A void pointer may contain any arbitrary address and at different times, could point to a char, a double, or a structure of some type, for example. A void pointer does not record any information about the object (or function) to which it currently points — it is the programmer's responsibility to keep track of this (just like the current contents of a union).
Since the compiler knows nothing about the object (or function) to which a void pointer points, such a pointer has several restrictions: You cannot dereference a void pointer, and you cannot do arithmetic on it — both operations require knowledge of the underlying object type.
The Linked List Problem
In some applications, it is useful to have a linked list where each link describes an object whose type may be different from that of other objects described by other links. An example might be a linked list of device control blocks in an operating system. The format of control blocks for different devices will likely vary.If each link in a list has a different format, how can the linked list be declared? This would require the forward and backward pointers (assuming a doubly-linked list) in a link to be of type void * (so they could point to any object type) and it would also require a flag in the link to indicate the type of the forward and backward objects. This can be cumbersome particularly if a link points to more than two places. (You may have multiple linked lists linked to each other, for example.)
The approach I have taken is somewhat similar but it avoids the flag field for forward and backward pointers. Essentially, each link contains a void pointer that points to some underlying object and the type of that object is stored in a field in the link. When you point to an object of type A, the flag is updated to record that. And a special flag value is used to indicate when the pointer does not point to an object.
The Switch Solution
There are several ways to implement the code. One uses the switch construct, as in Listing 1.The five macros TYPE* represent the five possible states of the flag field objtype. Their values must be distinct but otherwise are immaterial, as is the fact that objtype is unsigned — it could just as easily have been signed.
To simplify the example, I have allocated space for only one link and have ignored the possibility of malloc returning NULL.
Each link contains a pointer (pfwd) to the next link in the list, a pointer (pbwd) to the previous link, a pointer (pobject) to some generic object, and a flag (objtype) indicating the type of the object to which pobject points.
The link is initialized to point to a double object and the forward and backward pointers are set to NULL to indicate the end of the list. You might well ask, "Why not use calloc to allocate the space so it's initialized and the pointers need not be set to NULL in the program?"
Certainly, that approach will succeed on some systems. However, it is not maximally portable. calloc initializes the allocated space to all-bits-zero and while that's the representation of integer zero it need not represent floating-point zero, or in this case, the null pointer constant. ANSI C does not require that NULL be represented internally as all-bits-zero. It simply requires that the null pointer be a value that is not the address of an object or function, and that comparing and assigning pointers with integer zero actually works.
Once the list has been constructed, it becomes necessary to process the objects to which each link points. The problem here is how to do this efficiently? In this example, the switch construct is used and the correct answer is produced — the link does indeed point to a double object. But is this approach efficient?
The real question comes down to "How is a switch implemented?" ANSI C does not specify this; it simply requires that in the absence of a break statement (or similar) that you drop through from one case to the next. And if each case is mutually exclusive, the ordering of the cases (including default) can be arbitrary.
A lot of programmers believe (not necessarily for any good reason) that the order in which they specify the case labels, is important. This may or may not be true depending on your implementation and the set of case label values. For example, if the set of labels is dense (as in this case), the compiler might generate a jump table of addresses. (It might even be able to take advantage of a hardware case instruction such as exists on the VAX.) Certainly, this would make for efficient code.
If, on the other hand, the set of label values is sparse the compiler may generate a series of nested if/else constructs and it may do them in the order in which the cases are specified, the reverse order, or possibly in some other order. (As an exercise, if your compiler can produce a machine-code listing, do so for each of the three solutions shown in this article. Compare the code generated for the switch, if/else, and jump table approaches.)
The bottom line is that you are never guaranteed (by C) that the first case is tested for before the second (and the third, etc.) so specifying the most common case label value first need not be the most efficient approach. And if nested if/elses are used, the number of tests made to resolve the branch will be proportional to the number of cases defined.
The casts are needed since you cannot dereference a void pointer directly.
The if/else Solution
Whereas the switch construct provides no guaranteed order of case value matching, the if/else construct does. For example:
if (pnode-objtype == TYPECHAR) printf ("char: %c\n", *(char *)pnode-pobject); else if (pnode-objtype == TYPEINT) printf("int: %d\n", *(int *)pnode-pobject); else if (pnode-objtype == TYPELONG) printf("long: %ld\n", *(long *)pnode-pobject); else if (pnode-objtype == TYPEDOUBLE) printf("double: %f\n", *(double *)pnode-pobject); else if (pnode-objtype == TYPENONE) printf("none:\n");Now we have complete control of the order in which the tests are done. However, this ordering is fixed and favors those values near the front of the set of tests. It also cannot take advantage of any jump table generation the compiler might be able to do (unless the compiler has a very, very clever optimizer).
The Jump Table Solution
It so happens this problem can be solved and in a manner that involves no priority of testing. That is, the underlying object can be processed efficiently without regard to its type. (More correctly, I should say the code to do the processing is dispatched without favoritism.) Of course, there are always trade-offs and in this case, the code to process each object type must be in a function. That is, we must call a function to do the work whereas with the switch and if/else approaches, the work could be done inline(Listing 2) .The key to the solution is the object funtable. It's an array of five objects each of which is a pointer to a function that has no return value and has one argument, of type pointer to void. The array is initialized with the addresses of the five object type processing functions pro*. An array of function pointers is often referred to as a jump table.
It is absolutely critical that the order of the initializer expressions for funtable exactly match the values assigned in the TYPE* macros since we will use these macros to index into the funtable array. That is, the macro corresponding to pronone (TYPENONE) must have a value of zero since that is the first subscript value.
The expression
(*funtable[pnode-objtype]) (pnode-pobject);actually dispatches the type processing code. Following the operator precedence table, funtable is first subscripted using the type flag giving the address of the appropriate function. Then that function is called with the generic address of the underlying object being passed as the only argument.Regardless of the number of possible values for pobject, you only need this one statement to call the processing function — all type processing functions take equally long to dispatch since they all require one lookup in funtable. To change the number of types, you simply need to define the new processing functions and add them to the table initializer list. The concept of controlling the order in which types are tested for no longer exists since using the flag as a subscript you intuitively know the function to be used each time.
The messy looking cast expressions are still present in each processing function. Why couldn't proint (for example) be defined as
void proint(int *parg) { printf("int: %d\n", *parg); }instead of
void proint(void *parg) { printf("int: %d\n", *(int *)parg); }Again, this may work on some systems but, according to ANSI C, the behavior is undefined. Specifically, in main a void pointer is passed yet in proint an int pointer is expected. As stated earlier, these two pointer types are not required to have the same size and representation. (On a word machine such as a Cray supercomputer such mismatching will likely result in the wrong answer for all characters except the first in a given memory word.)The function prochar is a special case since it could be defined to expect a char pointer. And since char pointers and void pointers are required to have the same representation, this would work. However, in both cases (proint and prochar) the formal argument list in the definition would not match the prototypes for these functions. And if you change the prototypes to match, the table initializer will be erroneous. By definition, every function pointer must point to a function having the same argument list as well as return type.
You could bypass the strict checking rules by leaving the argument information out of the table declaration but this still won't help you. In the absence of a prototype in the table declaration, the actual void pointer argument will be passed as is, giving rise to the mismatch problem with the formal argument as discussed earlier.
In short, the functions must all have the exact same argument list thus requiring the explicit cast before dereferencing. Even pronone must have an argument despite the fact it is never used.
Just what is the cost of a cast anyway? None at all on systems where all pointers are created equal. (This is typically the case on byte architectures having a linear address space.) On word and segmented architectures, most pointer conversions are also nonevents except where either the cast operand or the cast type is a char (or possibly short int) pointer. So don't be too concerned about the cast generating code.
It was implied earlier that requiring each type's processing code to be a function might be inefficient since we have added the overhead of calling a function. Depending on this cost, it may or may not be significant. Also, an increasing number of compilers are adding the ability to automatically inline functions in each place they are called. (VAX C recently added this in V3 and C++ supports it explicitly using the inline keyword.)
Enumerations Versus Macros
In all three solutions, macros were used to come up with a set of unique integer values. The same result can be achieved using an enumerated type as follows:
enum {TYPENONE, TYPECHAR, TYPEINT, TYPELONG, TYPEDOUBLE};Not only do we get a set of unique int values, they also start at zero (as required by the jump table approach). And we are relieved from having to assign the numbers explicitly.Regarding the spelling of the enumerations constant identifiers; should they be in upper- or lower-case? If you follow the rule "All upper-case for macros and all lower- or mixed case for other identifiers" then they should be all lower-case. When I see an identifier written in upper-case I immediately understand that identifier might expand into an arbitrarily complex expression and I should take care how it's used. Since an enumeration constant "expands" to a simple integer constant the connotations of spelling it in upper-case are unwarranted. In the final analysis though, I don't think your choice will have significant stylistic ramifications.
One final thing about the enum declaration; it has no tag and as such, no objects can later be declared to have that type. And although tagless structure and union declarations declared like this are useless, this is not so for enumerations. The scope of the enumeration constants declared inside the braces goes beyond the use of objects of that enumerated type. These constants have type int and can be used even though no enumerated objects of that type are actually declared. From my experience, enums are mostly used in just this manner.