Оффлайн
- Регистрация
- 9 Май 2015
- Сообщения
- 1,483
- Баллы
- 155
Polymorphism—the ability to write functions whose behavior depends on the type and number of their arguments—is a feature of many modern programming languages.
In the C world, this concept is especially relevant to library writers or developers implementing the backend of a complex system: fellow programmers prefer a clean, consistent API over dozens or hundreds of closely related functions that differ only by name and signature.
Too often, APIs end up littered with near-identical functions such as:
result_type mixdown_integer_and_string(int x, char *y);
result_type mixdown_unsigned_integer_and_string(unsigned int x, char *y);
result_type mixdown_string_and_float(char *x, float *y);
// and so on ...
each variant must be remembered and called explicitly, making the interface hard to learn and easy to misuse.
How much better would it be to hide those functions (which you, still, have to write) under a single function mixdown(x,y) that would select the appropriate function based on the type of its arguments?
While C doesn’t provide built-in support for method overloading or virtual dispatch tables, you can still craft polymorphic interfaces using a handful of idioms.
In this article, I’ll focus on argument types. See , which I posted some time ago, on how to easily creating functions with a variable number of arguments.
I’ll explore four approaches:
- void pointers to tagged structures,
- function‑pointer tables,
- tagged pointers,
- the C11 _Generic keyword,
using a running example of graphical objects (points, rectangles, circles, ...) that implement operations such as scale() and translate(). I’ll try to highlight the trade-offs in safety, performance, and memory usage, and point out common pitfalls you’ll want to avoid.
1. Void Pointers to Tagged Structures
Concept
Store a type tag in each object’s struct so that functions can inspect the tag at runtime and dispatch to the correct implementation.
#define OBJ_POINT 0
#define OBJ_RECT 1
#define OBJ_CIRCLE 2
typedef struct {
int tag;
} GraphicObject;
typedef struct {
int tag; // must be OBJ_POINT
int x, y;
} Point;
typedef struct {
int tag; // must be OBJ_RECT
int x, y;
int width, height;
} Rectangle;
typedef struct {
int tag; // must be OBJ_CIRCLE
int x, y;
float radius;
} Circle;
// All structs must have the same initial sequence for this to work correctly
// The C standard only guarantees it in the context of accessing the fields
// of structures with unions but, in practice, this is often unnecessary.
typedef union {
GraphicObject object;
Point point;
Circle circle;
Rectangle rectangle;
} ObjectType;
static inline int get_tag(void *p)
{
return ((ObjectType *)p)->object.tag;
}
This relies on the C standard's guarantee that all structs in a union share the same initial sequence when they have compatible types at the beginning.
Dispatch Function
Each "high-level" functions will inspect the tag field and call the proper function.
void scale(void *obj, float sx, float sy) {
switch (get_tag(obj)) {
case OBJ_POINT:// Ignore
break;
case OBJ_RECT:
scale_rectangle((Rectangle *)obj, sx, sy);
break;
case OBJ_CIRCLE:
scale_circle((Circle *)obj, sx, sy);
break;
default:
// handle error
break;
}
}
Pros & Cons
Pros
- Simple to implement.
- Works with any pointer type uniformly.
Cons
- No compile-time type checks: passing the wrong pointer (e.g. scale(stdout, ...)) compiles fine but has undefined behavior.
- Every call incurs a switch‐dispatch overhead.
- Tags consume extra space in every object.
Concept
Embed pointers to each operation directly in the object (or point to a shared function‐pointer table), mimicking C++’s virtual table.
typedef struct GraphicOps {
void (*translate)(void *self, int dx, int dy);
void (*scale)(void *self, float sx, float sy);
// … other ops
} GraphicOps;
typedef struct {
const GraphicOps *ops;
int x, y;
} Point;
typedef struct {
const GraphicOps *ops;
int x, y;
float width, height;
} Rectangle;
typedef struct {
const GraphicOps *ops;
int x, y;
float radius;
} Circle;
Initialize per-type tables once:
static const GraphicOps point_ops = {
.translate = (void (*)(void*,int,int))translate_point,
.scale = (void (*)(void*,float,float))scale_point,
};
static const GraphicOps circle_ops = {
.translate = (void (*)(void*,int,int))translate_circle,
.scale = (void (*)(void*,float,float))scale_circle,
};
// similarly for Rectangle
Usage via Macros
#define translate(obj, dx, dy) ((obj)->ops.translate(obj, dx, dy))
#define scale(obj, sx, sy) ((obj)->ops.scale(obj, sx, sy))
Circle *new_circle(float radius) {
Circle *c = aligned_alloc(MAX_TAGS, sizeof *c); // C11 standard
if (c == NULL) return NULL;
c->x = c->y = 0;
c->radius = radius;
c->ops = &circle_ops; // point to the function table
return c;
}
Pros & Cons
Pros
- No runtime switch; dispatch is a single indirect call.
- Compile‐time type safety: if you pass a "wrong" argument to the high level function, it will give an error.
Cons
- Objects contains an additional pointer (which is usually larger that an int) per instance.
- Macro wrappers double‐evaluate the obj argument (beware side effects).
- Slightly more boilerplate on initialization (for example, you will need a scale-point() funtction even if it does nothing).
Concept
Use the low (least significant) bits of a pointer which are zero (to guarantee proper memory alignment) to store the tag instead of allocating space in every object.
#include <stdint.h>
#include <stdlib.h>
#include <stdalign.h>
// Let's pretend 4 tags are enough.
#define MAX_TAGS 4
#define TAG_MASK ((uintptr_t)(MAX_TAGS-1))
#define PTR_MASK (~TAG_MASK)
#define OBJ_POINT 0
#define OBJ_RECT 1
#define OBJ_CIRCLE 2
typedef struct {
int x, y;
} Point;
typedef struct {
int x, y;
float width, height;
} Rectangle;
typedef struct {
int x, y;
float radius;
} Circle;
// The type is defined as a structure to ensure that GraphicObject
// is different from any other type.
typedef struct { uintptr_t ptr; } TaggedPtr;
#define TAGGED_PTR_NULL ((TaggedPtr){0})
// We'll use the TaggedPtr to represen a generic objec
#define GraphicObject TaggedPtr
static inline TaggedPtr tag_ptr(void *p, int tag) {
TaggedPtr tp;
tp.ptr = (uintptr_t)p | tag ;
return tp;
}
static inline void *untag_ptr(TaggedPtr tp) {
return (void *)(tp.ptr & PTR_MASK);
}
static inline int get_tag(TaggedPtr tp) {
return (int)(tp.ptr & TAG_MASK);
}
The allocation and tagging :
GraphicObject new_circle(float radius) {
Circle *c = aligned_alloc(MAX_TAGS, sizeof *c);
if (!c) return TAGGED_PTR_NULL;
c->x = c->y = 0;
c->radius = radius;
return tag_ptr(c, OBJ_CIRCLE);
}
Dispatch:
void scale(GraphicObject obj, float sx, float sy) {
void *obj_ptr = untag_ptr(obj);
switch (get_tag(obj)) {
case OBJ_POINT: break; // ignore
case OBJ_RECT: scale_rectangle(obj_ptr, sx, sy); break;
case OBJ_CIRCLE: scale_circle(obj_ptr, sx, sy); break;
default: /* handle error */ break;
}
}
Pros & Cons
Pros
- No per‐object tag field → smaller objects.
- Compile‐time enforcement of pointer types (no scale(stdout) issue).
Cons
- Limited number of tags (bits used by alignment).
- Still a runtime switch.
If more than few tags (let's say, more than 16) are needed, a good alternative is available if we are ready to accept some portability constraint.
Counting on the fact the the vast majority of the current CPU architecture only use 48 bits for addressing virtual memory, we can store the tag in the most significant (highest) 16 bits of the pointer.
The functions get_tag(), tag_ptr(), and untag_ptr() are conceptually similar and only shift the tag from/to the highest bits.
The impact on portability and, possibly, software longevity needs to be assessed before using this method.
4. Compile-Time Dispatch with _Generic
Concept
Use C11’s _Generic keyword to select the correct function based on the static type of the expression—no runtime overhead for dispatch.
#define scale(obj, sx, sy) \
_Generic((obj), \
Circle*: scale_circle, \
Rectangle*:scale_rectangle, \
Point*: scale_point \
)(obj, sx, sy)
Now calls like:
Point *p = new_point(5, 5);
scale(p, 2.0f, 2.0f);
are resolved at compile time to scale_point(p,2,2).
Caveats
- Static‐only: _Generic cannot dispatch on runtime data; you cannot use it to iterate a heterogeneous list of GraphicObject, for example.
- Verbosity: Every operation needs its own _Generic macro.
- Limited flexibility: _Generic() has its own quirks and sometimes need extra care in how the functions are designed to accomodate its rules on the arguments type.
You can combine _Generic with void pointers to get compile-time type check:
#define scale(obj, sx, sy) \
_Generic((obj), \
GraphicObject*: scale_dispatch,\
Point*: scale_dispatch,\
Rectangle*: scale_dispatch,\
Circle*: scale_dispatch \
)(obj, sx, sy)
void scale_dispatch(void *obj, float sx, float sy) {
switch (get_tag(obj)) {
case OBJ_POINT:// Ignore
break;
case OBJ_RECT: scale_rectangle((Rectangle *)obj, sx, sy);
break;
case OBJ_CIRCLE: scale_circle((Circle *)obj, sx, sy);
break;
default: // handle error
break;
}
}
It requires some more boilerplate, but completely remove the biggest weakness of using void pointers: the scale() macro will only scale_dispatch() to be call on valid pointers.
Rather than blindly pass any pointer, if you have a void * that you are sure is a valid pointer to a graphic object, just cast it to a GraphicObject *.
Conclusion
While C lacks built-in polymorphism, thoughtful application of void‐pointer tagging, function pointers, tagged pointers, and _Generic can yield flexible, type-safe, and reasonably efficient polymorphic APIs. Each approach carries its own trade-offs between binary size, runtime cost, and safety:
- Void pointers + tags: simplest, but no compile-time checks.
- Function pointers: mirrors C++ v-tables, moderate overhead.
- Tagged pointers: memory‐efficient, but fragile portability.
- _Generic: zero‐cost dispatch, compile-time only.
As I mostly write libraries and back-end softare, I believe my duty is to balance these considerations, polishing an API so that the "real" programmer can write clear, concise, and correct code without worrying about too many underlying details.
Polymorphism in C is entirely possible—just plan for it!