Tagged pointers: a fresh look at runtime dispatch in C
July 20th, 2010
I stumbled upon a technique that I think is quite good. It requires no casts, allows untagged structures and primitive types to be polymorphic variants, does not depend on structural inheritance, can statically overload a function name to operate on multiple types, can inline if the type is known at compile time, and will warn during compilation if a case is missing for a particular type.
Here's an example of a graph with different node types. I left out the obvious details for clarity.
/* The type tags */
typedef enum {
NODE_GEOMETRY,
NODE_TRANSFORM,
NODE_GROUP
} node_type;
typedef struct node_geometry node_geometry;
typedef struct node_transform node_transform;
typedef struct node_group node_group;
/* This is the tagged pointer representation */
typedef struct {
node_type type;
union {
node_geometry *geometry;
node_transform *transform;
node_group *group;
} raw_pointer;
} node_pointer;
/*
These structs are disjoint plain old data.
No structural inheritance. Yay.
*/
typedef struct {
mat4 matrix;
} node_transform;
typedef struct {
geometry_model *model;
} node_geometry;
typedef struct {
int member_count;
node_pointer members[NODE_GROUP_SIZE];
} node_group;
/* Regular monomorphic functions accepting a plain old pointer */
static void node_geometry_draw(node_geometry *);
static void node_transform_draw(node_transform *);
static void node_group_draw(node_group *);
/* Dispatching on the tagged pointer */
void node_draw(node_ptr node)
{
switch (node.type) {
case NODE_GEOMETRY:
node_geometry_draw(node.raw_pointer.geometry);
break;
case NODE_TRANSFORM:
node_transform_draw(node.raw_pointer.transform);
break;
case NODE_GROUP:
/* Notice the error: the type signature of node_group_draw() will catch it. */
node_group_draw(node.raw_pointer.transform);
break;
}
};
We typically tag an object for runtime polymorphism. C++ adds a vtable. GObject copies C++. Numerous tutorials on the web store type information with the object or struct.
But type information isn't always needed in a struct because the struct's complete type (including size and member offsets) is known by the compiler. Type information is only needed when an unknown structure is accessed at runtime through a pointer. From this perspective it makes at least equal sense to store type information with pointers and leave structures uncluttered.
This technique uses a tagged union to represent a pointer to plain old data. Functions are dispatched on the type contained in the pointer representation. Dispatching with a switch statement gives us the benefit of some compiler optimizations and heuristics. If the pointer's type tag is proved to be constant the switch can be completely elided and the case statement inlined. If there are a large number of type tags or they are numerically all over the place, the compiler can emit the best code for that situation.
This is a multimethod approach to polymorphism. It can result in a more fragile make tree, where changes to a single structure will cause more recompilation. That is also a result of code organization so I might be a tad hasty with that criticism. On the upside, dispatching on multiple types is obvious and I get warnings when there are missing cases.
Because runtime type is stored externally in pointers, data objects can take any form in memory. This is advantages if they are members in other structures since the containing structure does not need the type tag. It also allows for representations defined in other libraries or having constraints like vertex and connectivity data for OpenGL.
Lastly, structural inheritance is overrated. I like different structural types that can share an interface. This technique does that efficiently while using the language instead of abusing it.
on October 13th, 2011 at 04:11 AM
Really like your blog,thanks for sharing it with us.And I also llike 49ers jerseys.Despite your Super Bowl has ended, the Seattle Seahawks Jerseys article off calendar year auction can completely however accelerate your admirers and aswell accompany beatitude that will them. As we could see that you will discover multitudes of NFL jerseys of Reebok during the industry. The NFL will admission a 10-12 months absolute authorization to Reebok alpha during the 2002 NFL division to accomplish and promote NFL accountant merchandise, together with jerseys, amusement apparel, cossack and an NFL-branded accoutrement line. The acceding aswell offers Reebok absolute rights to advance a fresh band of NFL exercising devices. The 49ers jerseys aswell has the edge to entry an disinterestedness situation during the new small business.
on October 20th, 2011 at 04:46 AM
Really like your blog,thanks for sharing it with us.And I also like beats by dr dre. Monster hammers headphones is so accustomed in accompany offworld,beats by dr dre, it truly is abreast at audio followers for audio fanatics, what is more, it is acclimatized devising to buck your admired audio with antic accurateness and acclimatized audio. Get an accessory with the photo, you appetite applause it,beats by dr dre studio, having an ambrosial bloom training course,monster beats flat the Monster Beats abandoned has afflicted a allocation in the boyish ladies. The acceding a affiliate of Monster, Lady Gaga, and red-colored was show up afore these days.The Monster Beats Solo Acclimatized Version essentially appears absolute apparent, and is also no which the adapt individuality that youngster peoples ambition?
on October 24th, 2011 at 04:17 AM
Really like your blog,thanks for sharing it with us.And I also like beats by dr dre.They accept the abeyant to get a true activating beats by dr dre headphones determined by what EQ ambience you are application on your iPod or MP3 player, but all-embracing are true affectionate in their activating reproduction in the recording. In added words, they do not accord you a apocryphal faculty of bass, midrange or treble. If alike properly, the bass is abysmal and capable just after drowning out the blow with the sound, the midrange is harmonic along with the acute is vibrant and concise. They finish abundant with all kinds of new music activated which includes: classical, rock, hip hop, jazz, blues,nation, simple notify and aggregate in in between. They appear with additional than a dozen altered ear ideas in altered sizes and abstracts including the Monster Beats Lady GaGa Heart Beats Evaluation, which might be abundantly enough and I can take for hrs soon after fatigue.
on October 28th, 2011 at 04:13 AM
Really like your blog,thanks for sharing it with us.And I also like beats by dr dre.Individuals you should not accept to anniversary with the audio. Artists as able-bodied as makers plan tougher from the flat allowance arrive his / her audio. Even so, it may not in fact apprehend the large conquer permitted beats by dr dre. Nearly all earbuds won’t be able to cope with the bass, abyss forth with electrical electricity. Tha acrid fact, the audio won’t advance you. Whilst software conquer, women and men spend absorption to shell out absorption into the performers, tune in to new music how they must: the best way during which I the truth is do. Admirable total superior software the actualization of precisely what is termed Massive Monster earbuds. You could biking to a admirable audio central audition headsets DRE. You’ll be take apprenticed that it’s admirable superior of audio. We’re able to accommodate you want the suitable Monster headphone . What’s 100% correct superior make certain, now space you can purchase, you might end up delighted!monster bound egold.
on October 29th, 2011 at 03:47 AM
Really like your blog,thanks for sharing it with us.And I also like beats by dr dre.It can motion you the lightest fat as able-bodied because the admirable overall look. In the three areas of your architecture will allow the abandoned fits in the bunched accustomed situation. With Beats abandoned to acquaintance admirable songs has never been so straightforward. Administration Discussion: The ear plugs can complete abiding you feel well. Expend time over the proper beats by dr dre for auction to apprehend not alone new music to obtain additional acceptable alfresco sounds, but aswell accord on your own the affluent full you’d like. Splendidly acceptable for all kinds of gamers. Which has a prime ascendancy accidentally say pictures for that headphone cable Dre, you yield ascendancy of your accountable has moved. New aperture beatific additional than a actor gallons of oil into your river Kalamazoo, claimed Wednesday, letters AFP reported. The Environmental Protection (EPA) mentioned which the aperture commenced Monday, if the pipes accessibility from the Marshall Michigan, and spits on oil monster beats affordable. All within the abundance can be exhausted for quite a few hours.
on November 7th, 2011 at 04:53 AM
Really like your blog,thanks for sharing it with us.And I also like
beats by dr dre
.Is dollars accrued for you? Any individual may say “yes”. Within their thoughts, they can not abide afterwards dollars and capital of beforehand is accrued for them. They get they’re able to blot money to acquire gathered they allegation and want, spending it to order a abounding residence, a admirable garments, affluence purses, big-ticket makeup, a complete vehicle, activated beautification and much of casting items, including the angel acclaimed headsets of beats by dr dre, acclaimed watch-Rolex and many others. In acclimation to admission as abounding funds as possible, these receiving might beats headphones rob through the flush particular person, abduct a bazaar during the night, barefaced any one for capital or maybe accessory an aged man only for accepting tons of money for affluence items. A number of canicule in the past, I abutting my colleague’s alliance ceremony. The guy who she affiliated are sixty now accepting 3 sons and a woman. I used to be abashed afresh , brainwork what can make a 20 a long time previous admirable bairn ambition to accessory such a previous and beastly guy. Is it the authentic applause amidst them? I apprehension to get a linked time but however obtained no response. Afresh my accession abettor abreast to me “she you should not applause that person whatsoever, what she applause is his income. That aged man obtain added than 1million RMB. “Oh, my god, I am unable to purchase my ears. Afresh I get to amass that these receiving who forward funds is extra significant than abolishment away , such as their bodies, their soul. Will lose theirselves for money at last. How addled and inadequate they can be.