Type-safe generic data structures in plain-old C?
I have done far more C++ programming than "plain old C" programming. One thing I sorely miss when programming in plain C is type-safe generic data structures, which are provided in C++ via templates.
For sake of concreteness, consider a generic singly linked list. In C++, it is a simple matter to define your own template class, and then instantiate it for the types you need.
In C, I can think of a few ways of implementing a generic singly linked list:
- Write the linked list type(s) and supporting procedures once, using void pointers to go around the type system.
- Write preprocessor macros taking the necessary type names, etc, to generate a type-specific version of the data structure and supporting procedures.
- Use a more sophisticated, stand-alone tool to generate the code for the types you need.
I don't like option 1, as it is subverts the type system, and would likely have worse performance than a specialized type-specific implementation. Using a uniform representation of the data structure for all types, and casting to/from void pointers, so far as I can see, necessitates an indirection that would be avoided by an implementation specialized for the element type.
Option 2 doesn't require any extra tools, but it feels somewhat clunky, and could give bad compiler errors when used improperly.
Option 3 could give better compiler error messages than option 2, as the specialized data structure code would reside in expanded form that could be opened in an editor and inspected by the programmer (as opposed to code generated by preprocessor macros). However, this option is the most heavyweight, a sort of "poor-man's templates". I have used this approach before, using a simple sed script to specialize a "templated" version of some C code.
I would like to program my future "low-level" projects in C rather than C++, but have been frightened by the thought of rewriting common data structures for each specific type.
What experience do people have with this issue? Are there good libraries of generic data structures and algorithms in C that do not go with Option 1 (i.e. casting to and from void pointers, which sacrifices type safety and adds a level of indirection)?
Answer
Option 1 is the approach taken by most C implementations of generic containers that I see. The Windows driver kit and the Linux kernel use a macro to allow links for the containers to be embedded anywhere in a structure, with the macro used to obtain the structure pointer from a pointer to the link field:
Option 2 is the tack taken by BSD's tree.h and queue.h container implementation:
I don't think I'd consider either of these approaches type safe. Useful, but not type safe.