IDevResource.com - ATR Articles: Virtual Functions and their implementation in C

The Developer's Resource & Community Site

COM	XML	ASP	Java & Misc.	NEW: VS.NET
International	This Week	Forums	Author Central	Find a Job

Virtual Functions and their implementation in C

By Shivesh V.

What are virtual functions?

First, a quick introduction to virtual functions. Virtual functions are a concept in C++, which enable runtime binding of function calls to actual function implementations. What runtime binding means, will be discussed under the next heading. Another way to put it will be that a virtual functions call is dependant on the context in which it is dependant. Or still better, is dependant on the object on which it is invoked and not on the object's type, as it is in the case of non-virtual functions. Invoking on object's type is virtually trivial for a compiler. It is fairly evident from the fact that non-virtual function invokations in C++ are hardly ever discussed, much less written about.

What is runtime binding?

So what does this term mean? Runtime binding means, at least in our context of discussion, the resolution of a function call at runtime. Meaning, when you call a (virtual) function, the call is not resolved until at runtime.

Runtime binding in C through vtable structure

If our goal is to resolve the function at the time of execution, let us find out if we can do it without the help of the compiler. In other words, let's try runtime binding in a program written in C. So let's write two structs. I will take the shape example.


typedef struct Shape_t
{
void (*pDraw)();
int (*pCalculateArea)();
int (*pCalculateVolume)();
int (*pCalculatePerimeter)();
void (*pRotate)();
} Shape;

We put member functions as pointer to functions inside a struct for obvious reasons.


// A global function to draw a shape... Say there is a default functionality 
// for draw for argument's sake
// A global function to draw a shape...
void DrawShape()
{
// Drawing logic.
printf( "Draw of Shape\n" );
}

int CalculateAreaShape()
{
printf( "CalculateArea of Shape\n" );
return 0; // shape has no area...
}

int CalculateVolumeShape()
{
printf( "CalculateVolume of Shape\n" );
return 0; // shape has no volume...
}

int CalculatePerimeterShape()
{
printf( "CalculatePerimeter of Shape\n" );
return 0; // shape has no Perimeter...
}

void RotateShape()
{
printf( "Rotate of Shape\n" );
}

// A global function to initialize a shape...
void InitShape( Shape* s )
{
s->pDraw = DrawShape;
s->pCalculateArea = CalculateAreaShape;
s->pCalculateVolume = CalculateVolumeShape;
s->pCalculatePerimeter = CalculatePerimeterShape;
s->pRotate = RotateShape;
}

The Rectangle struct would look like this:


// Rectangle class (supposed to be derived from shape, but here it is a totally different struct
typedef struct Rectangle_t
{
void (*pDraw)();
int (*pCalculateArea)();
int (*pCalculateVolume)();
int (*pCalculatePerimeter)();
void (*pRotate)();
} Rectangle;

// A global function to draw a rectangle...
void DrawRectangle()
{
printf( "Draw of Rectangle\n" );
}

int CalculateAreaRectangle()
{
int n = 20;

printf( "CalculateArea of Rectangle\n" );
return n; // rectangle's area...
}

int CalculatePerimeterRectangle()
{
int n = 30;

printf( "CalculatePerimeter of Rectangle\n" );
return n; // rectangle's perimeter...
}

// A global function to initilaize a rectangle...
void InitRectangle( Rectangle* r )
{
r->pDraw = DrawRectangle;
r->pCalculateArea = CalculateAreaRectangle;
// Note: Shape function because Rectangle chose not to override the Shape functionality.
r->pCalculateVolume = CalculateVolumeShape;
r->pCalculatePerimeter = CalculatePerimeterRectangle;
// Note: Shape function because Rectangle chose not to override the Shape functionality.
r->pRotate = RotateShape;
}

// Using the above two structs
int main()
{
Rectangle rect;
Shape* pShape;

InitRectangle( &rect );

pShape = (Shape*) ▭

pShape->pDraw();
pShape->pCalculateArea();
pShape->pCalculateVolume();
pShape->pCalculatePerimeter();
pShape->pRotate();
}

It is plain as to what will happen. When you compiler and run the above file, the output will be:


Draw of Rectangle
CalculateArea of Rectangle
CalculateVolume of Shape
CalculatePerimeter of Rectangle
Rotate of Shape

For functions which have been written for Rectangle, the member function pointers point to those functions. If the *derived* implementation is not provided, the base one is used (Now haven't I heard that before?) and hence they point to the *base* implementation. Now why the base and derived are within those funny asterisk marks is because the inheritance here is purely artificial. But nevertheless, it works!

I am not mocking inheritance here. That is not the topic I am discussing. If you want to know how the entire shape example can be written in C, in an object-oriented fashion, refer to Programming in C++ by Nabajyoti Barkakati, Prentice Hall. The point I am trying to make here is that this is not *runtme binding* as it is known. You have manipulated all the pointers here. But this goes a long way in understanding how a C++ compiler implements virtuality. Now, the way it is exactly done might vary from compiler to compiler, but the end result is the same and that is those 5 lines you see in the output window. Tidying it up a little, you can define Shape and Rectangle like this:


typedef struct ShapefunctionsTable_t
{
void (*pDraw)();
int (*pCalculateArea)();
int (*pCalculateVolume)();
int (*pCalculatePerimeter)();
void (*pRotate)();
} ShapefunctionsTable;

typedef struct Shape_t
{
ShapefunctionsTable* pTable;
} Shape;

To have one instance of your *vtable*, declare a global ShapefunctionsTable instance.


ShapefunctionsTable g_pTableForShape;
void InitShapesTable()
{
g_pTableForShape.pDraw = DrawShape;
g_pTableForShape.pCalculateArea = CalculateAreaShape;
g_pTableForShape.pCalculateVolume = CalculateVolumeShape;
g_pTableForShape.pCalculatePerimeter = CalculatePerimeterShape;
g_pTableForShape.pRotate = RotateShape;
}

Every shape object's vtable pointer, now has to point to this instance. So the InitShape() function looks like this:


// A global function to initialize a shape...
void InitShape( Shape* s )
{
s->pTable = &g_pTableForShape;
}

Now, the things are quite similar for Rectangle class.


typedef struct RectanglefunctionsTable_t
{
void (*pDraw)();
int (*pCalculateArea)();
int (*pCalculateVolume)();
int (*pCalculatePerimeter)();
void (*pRotate)();
} RectanglefunctionsTable;

typedef struct Rectangle_t
{
RectanglefunctionsTable* pTable;
} Rectangle;

RectanglefunctionsTable g_pTableForRect;
void InitRectanglesTable()
{
g_pTableForRect.pDraw = DrawRectangle;
g_pTableForRect.pCalculateArea = CalculateAreaRectangle;
g_pTableForRect.pCalculateVolume = CalculateVolumeShape;
g_pTableForRect.pCalculatePerimeter = CalculatePerimeterRectangle;
g_pTableForRect.pRotate = RotateShape;
}

// A global function to initilaize a rectangle...
void InitRectangle( Rectangle* r )
{
r->pTable = &g_pTableForRect;
}

What you have done is that you have separated the vtable out of the actual classes. After all, if vtable is not shared between different objects of same class, you will end up wasting a whole lot of memory for no reason. Using the newborn vtable, we can use this *hierarchy* as follows:


// Using the above two structs
int main()
{
Shape* pShape = 0;

// Intialize the vtable for rectangle class.
InitRectanglesTable();

Rectangle rect;
InitRectangle( &rect );

pShape = (Shape*) ▭

pShape->pTable->pDraw();
pShape->pTable->pCalculateArea();
pShape->pTable->pCalculateVolume();
pShape->pTable->pCalculatePerimeter();
pShape->pTable->pRotate();
}

This is about what your C++ compiler does for you when it has to "call a function at runtime". He replaces calls to virtual functions with a piece of code similar to this. And you have your *runtime binding*.

Nothing, except executuion of machine instructions, can happen at *runtime*. Your program is out there, all alone, at the hands of the CPU. There is no compiler, no linker, no *executor* for your program while it executes. It runs by itself. No one else, except your program, is responsible for anything and everything that happens during it's execution. So who does this runtime binding? Your program? Yes. Do you write code for runtime binding? In a way, yes. Why in a way? Because you ask the compiler to add code for you. By means of the virtual keyword. In C++, you do not write the kind of code you see above. But all this code is generated. The above code might be (and is) a simplistic version of what the compiler does. But it does convey a point. Right?

Runtime binding in C through vtable array

If you notice the above code carefully, you will see that each virtual function call is indirected once (through the pTable pointer). For a class hierarchy that is filled with virtual functions, this can spell doom. Can we get rid of this indirection? Let's see.

Instead of a struct, let's put a global array as the shapes vtable.


// This is an array of function pointers (vtable?).
int(*gvtblShape[5])();

and inside the Shape struct, put a similar pointer.


typedef struct Shape_t
{
// Declare a pointer to an array of function pointers.
int(*(*vtbl))();
} Shape;

InitShapesTable() function changes to this. It initializes the shapes vtable with the global functions.


void InitShapesTable()
{
gvtblShape[0] = (int(*)()) DrawShape;
gvtblShape[1] = (int(*)()) CalculateAreaShape;
gvtblShape[2] = (int(*)()) CalculateVolumeShape;
gvtblShape[3] = (int(*)()) CalculatePerimeterShape;
gvtblShape[4] = (int(*)()) RotateShape;
}

We have typecasted all the function pointers to this standard type as arrays are homogeneous structures. The next change is in InitShape().


void InitShape( Shape* s )
{
// Initialize the vtable in Shape to the global vtable for shape.
s->vtbl = gvtblShape;
}

We do the same thing for the Rectangle struct.


int(*gvtblRectangle[5])();

typedef struct Rectangle_t
{
// Declare a pointer to an array of function pointers.
int(*(*vtbl))();
} Rectangle;

void InitRectanglesTable()
{
gvtblRectangle[0] = (int(*)()) DrawRectangle;
gvtblRectangle[1] = (int(*)()) CalculateAreaRectangle;
gvtblRectangle[2] = (int(*)()) CalculateVolumeShape;
gvtblRectangle[3] = (int(*)()) CalculatePerimeterRectangle;
gvtblRectangle[4] = (int(*)()) RotateShape;
}

// A global function to initilaize a rectangle...
void InitRectangle( Rectangle* r )
{
r->vtbl = gvtblRectangle;
}

The call from main() become slightly different. You call these functions through the function pointers in the vtable. So, in main() the calling of these functions will become:


int main(int argc, char* argv[])
{
Shape* pShape = 0;

InitRectanglesTable();

Rectangle rect;
InitRectangle( &rect );

pShape = (Shape*) ▭

(*pShape->vtbl[0])();
(*pShape->vtbl[1])();
(*pShape->vtbl[2])();
(*pShape->vtbl[3])();
(*pShape->vtbl[4])();
}

So, you have an array implementation of vtable. But array implementation means that the vtable has to be filled up with homogeneous entries, which means that the function pointers have to be typecasted to one type before putting it into the array.

Runtime binding in C through treating struct as an array

This is a combination of the two implementations just discussed. Let the vtable be a struct. So, you will have the structures, ShapefunctionsTable_t and RectanglefunctionsTable_t. And everything will as in case of struct, but the calling will have to be different. The calling should be like this:


#define ANYTHING void // or int or float or Shape, doesn't matter :-)

int main(int argc, char* argv[])
{
Shape* pShape = 0;

InitRectanglesTable();

Rectangle rect;
InitRectangle( &rect );

pShape = (Shape*) ▭

(*((void(*)()) (((ANYTHING**)pShape->pTable)[0]) ))();
(*((void(*)()) (((ANYTHING**)pShape->pTable)[1]) ))();
(*((void(*)()) (((ANYTHING**)pShape->pTable)[2]) ))();
(*((void(*)()) (((ANYTHING**)pShape->pTable)[3]) ))();
(*((void(*)()) (((ANYTHING**)pShape->pTable)[4]) ))();
}

What you are doing is, you are typecasting the vtbl struct to a pointer to pointer (to anything) and then, when you increment this typeacasted value, you jump forward by a pointer size (which is what you want). So you go into the correct offset in the vtbl struct and are able to call the appropriate function. It's a little tricky, but just try and get comfortable with the above code. It is very powerful.

NOTE: In all the cases, what you typecast to when you call the function is also something that the compiler does and it does the correct typecast before calling the function. But that is actually immaterial since the compiler actually can see your function call and figure out what it should typecast to when calling the address stored in the vtable.

Contribute to IDR:

To contribute an article to IDR, a click here.

To contact us at IDevResource.com, use our feedback form, or email us.

To comment on the site contact our webmaster.