Lesson 6 - Multiple Inheritance

by Zoran Horvat
September 05, 2012

In previous lessons we have intensively used types derived from base type. In each case, objects of derived type have had base type's methods readily available, or in object-oriented terms: inherited. The same was true with value members declared in the base type, as all of them were also present within instances of derived type. In this lesson we plan to push inheritance concept one step further. We are going to allow more than one type to be base for a given derived type.

This can be demonstrated easily on our geometrical shapes example. Suppose that we want to store shapes in a double linked list. Linking facility is a well defined functionality, more general than geometrical shapes, so why not implementing it in a separate class? Furthermore, suppose that we want to paint shapes on some kind of a drawing surface. Painting facility is another well defined feature more general than shapes, so there's another class to contain it. Consequently, Shape type would naturally have two base types - Linked (which implements linking facility) and Paintable (which implements painting facility). This proves that multiple base types are not much of the exotic kind as one may think of them.

Now that we are steadily on the path of adding another base to an already derived class, we must think about the fundamental question of subtyping: object layout. In single inheritance subobject, which represents base type content, was placed first in the object memory layout because then we were free to convert pointers from subtype to supertype and vice versa. When things come to inheriting more than one base type, layout question begins to complicate. Obviously, one subobject must come first, then followed by another subobjects, and ultimately followed by fields declared in subtype itself.

Picture below shows class hierarchy after Linked and Paintable base classes are added. Right-hand objects layout shows positions of subobjects within Shape and Ellipse types. In case of the Shape, which used to be the ultimate base class in our hierarchy, its starting segments are occupied by newly defined base types - Linked and Paintable. Only after these two subobjects are placed does the Shape type position its own fields. In case of Ellipse type, things are almost the same - complete Shape subobject, with all its internal complexities, is copied at the beginning of the object, again followed by fields proposed by the Ellipse itself.

This organization of derived objects looks handy but it gains complexity quickly when polymorphism comes into play. Remember that every method receives this pointer as its first argument. This requires special attention when applied to virtual methods because this pointer does not mean the same in base and derived type any more when applied to multiple inheritance. Since only one subobject can occupy beginning of the object, this pointers are not necessarily equal any more. The following picture shows actual pointers to different types inherited by Ellipse. What is of critical importance in this case is that Paintable subobject is actually the only one which does not fall to the beginning of the Ellipse object. Converting pointer to Ellipse to pointer to Shape or Linked is a no-brainer as Shape and Linked subobjects are positioned at the beginning of the object. Paintable, unfortunately, is somewhere in the middle and simple conversion of the Ellipse pointer to Paintable pointer would be a disaster.

Virtual method declared and implemented in the Paintable type can be freely called on instance of the Ellipse and on the instance of Shape type (which inherit the method), as well as on pointer to Paintable (which declares the method). When Paintable object is at hand and call is made to virtual method not overridden in derived type, then pointer offset is zero. When Shape or Ellipse objects are used, again to call not overridden method, then positive offset is required to move this pointer to the beginning of the Paintable subobject. Conversely, suppose that method is overridden in subtype and then called on a pointer to subtype - obviously, there is no offset to apply; but if called on pointer to supertype then negative offset may be reqiured to move pointer to subobject back to the beginning of the whole object!

This analysis leads to a conclusion that virtual method call carries uncertainty about this pointer offset. Researchers have thought about this problem and initially came up with a simple solution. Each entry in virtual method table would now accommodate pointer to function and this pointer offset. But then we encounter another problem. Virtual method table for Paintable's virtual methods is shared between Shape object and Paintable subobject and it can be accessed with two distinct this pointers that require distinct offsets. Conclusion is that every pointer must be turned into pointer to beginning of the whole object before resolving this pointer through the virtual method table. Pointer to beginning of the whole object can be resolved by storing subobject offset at a predefined entry in virtual method table (e.g. in first entry).

This short analysis shows that virtual method and this pointer resolution can work perfectly for any method and any object or subobject pointer. Having a pointer to polymorphic object and index in virtual method table for the desired function, it is quite simple to produce actual function pointer and this pointer to make a call. This leads to a couple of changes to make to virtual methods subsystem defined in vtable.h and vtable.c files. When virtual method tables are populated with function pointers, we also have to specify subobject offsets and this pointer offsets in additional integer field. Here is the modified code:

/* Listing of vtable.h */
#ifndef VTABLE_H
#define VTABLE_H

struct vtable_entry
{
    void *fptr;
    int ptr_offset;
};

typedef struct vtable_entry* vtable_ptr;

void vtable_abstract_method_called();
void *vtable_ResolvePointer(void *obj, int vtableIndex, void **thisPtr);
void vtable_Initialize();

#endif

Virtual method table entry is now a structure which contains function pointer and this pointer offset. There is also a new method, called ResolvePointer, which receives pointer to object and index in virtual method table for desired virtual method and returns pointer to function and modified this pointer (the latter one returned through a double pointer received as the last argument). Here is the implementation:

void *vtable_ResolvePointer(void *obj, int vtableIndex, void **thisPtr)
{

    /* Polymorphic object begins with pointer to virtual method table */
    struct vtable_entry *table = (struct vtable_entry*)obj;

    if (obj)
    {
        /* First entry in virtual method table is subobject offset */
        int subobjectOffset = table[0].ptr_offset;

        /* this pointer offset is stored in virtual method table entry */
        int thisPtrOffset = table[vtableIndex].ptr_offset;

        /* Exact this pointer is resolved by applying offsets to object/subobject pointer */
        *thisPtr = (void*)((unsigned char*)obj - subobjectOffset + thisPtrOffset);
    }
    else
    {
        *thisPtr = 0; /* null pointer remains null regardless of offsets */
    }

    /* Virtual method table entry contains desired function pointer */
    return table[vtableIndex].fptr;

}

In this method implementation observe that all pointer offsets are expressed in bytes (unsigned chars in C terms) to allow pointer arithmetic operations. In addition, offsetting is not applied to zero pointers - they simply remain zero.

Demonstrating Multiple Inheritance

We are now going to apply multiple inheritance and virtual methods discussed throughout this lesson. All code given will be in C programming language because we want to demonstrate the concepts in their native form. Only after all issues are resolved at low level shall we step into C++ and C# to uncover higher level counterparts. In that way we plan to make a parallel between object-oriented languages and actual implementation of multiple inheritance, so that all elements silently added by the object-oriented compiler can be identified and fully understood.

In geometric shapes example which we have been developing throughout previous chapters, there was a single type named Shape from which all other types are deriving. Subtypes Ellipse and Rectangle both derived from base type Shape. Now suppose that we want to broaden the functionality provided by this hierarchy. We want to provide means to draw shapes on a rectangular surface (referred to as the canvas). Since canvas requires ability to add and remove shapes dynamically, we will provide a facility to gather shapes into double linked list. Next, shapes will receive border and fill colors and also provide the functionality to paint themselves. Finally, painting will be applied to paintable objects, but those objects would have to use another entity, which we would call paint provider. This type is required because paintable objects need a medium to paint on. Final touch is then to make canvas a paint provider.

And these are the new types. Canvas, which contains shapes and offers methods to add and remove them. PaintProvider, which exposes virtual primitives used to draw horizontal and vertical lines of specified color. Paintable, which exposes colors of border and body of whatever is painted and a method to perform painting. Linked to provide double linking facility to any type that derives from it. As of this moment, Shape will derive from Linked and from Paintable which makes it the only type with two bases. Canvas will derive from PaintProvider, which means that pointer to canvas will be provided to shapes when these need be painted on its surface. The new hierarchy of types is presented on the picture below, which contains all types and their fields and methods. Arrows are pointing towards base types.

We will first implement the PaintProvider type because it is simplest of all and also required by thePaintable type to operate. Below are the listings of paint_provider.h and paint_provider.c files which define this type. This source code is quite simple, since only the constructor has its body. Remaining two methods (HorLine and VertLine) are abstract, which means that they only appear at their appointed locations in the virtual method table; for both methods signatures are defined, so that callers and derived types know details about these methods.

/* Listing of paint_provider.h */
#include "vtable.h"

#ifndef PAINT_PROVIDER
#define PAINT_PROVIDER

#define VT_PAINTPROVIDER_RTTI 0 /* contains subobject offset by now */
#define VT_PAINTPROVIDER_HORLINE 1
#define VT_PAINTPROVIDER_VERTLINE 2
#define VT_PAINTPROVIDER_END 3


vtable_entry vtable_PaintProvider[VT_PAINTPROVIDER_END];

struct PaintProvider
{
    vtable_ptr vptr;
};

typedef void (*vcall_PaintProvider_HorLine)(struct PaintProvider*, int, int, int, int);
typedef void (*vcall_PaintProvider_VertLine)(struct PaintProvider*, int, int, int, int);

void PaintProvider_Constructor(struct PaintProvider *_this);

#endif

Note that virtual method indices in the virtual method table now start from 1. The first entry (with index 0) is now dedicated to Runtime Type Identification (RTTI), which will at this stage only consist of subobject offset required to resolve this pointer in calls to virtual functions.

/* Listing of paint_provider.c */
#include "paint_provider.h"

void PaintProvider_Constructor(struct PaintProvider *_this)
{
    _this->vptr = vtable_PaintProvider;
}

Paintable type is also fairly easy to implement. Apart from having an abstract method, there is nothing special about it. Method Paint itself is the only virtual method in the type, but even that is sufficient reason to define a virtual method table for the whole type. Below are the listings of paintable.h and paintable.c source files which contain definition of the Paintable type in C programming language.

/* Listing of paintable.h */
#include "vtable.h"
#include "paint_provider.h"

#ifndef PAINTABLE_H
#define PAINTABLE_H

#define VT_PAINTABLE_RTTI 0
#define VT_PAINTABLE_PAINT 1
#define VT_PAINTABLE_END 2

vtable_entry vtable_Paintable[VT_PAINTABLE_END];

struct Paintable
{
    vtable_ptr vptr;
    int borderColor;
    int fillColor;
};

typedef void (*vcall_Paintable_Paint)(struct Paintable*, struct PaintProvider*);

void Paintable_Constructor(struct Paintable *_this);
void Paintable_set_BorderColor(struct Paintable *_this, int value);
int Paintable_get_BorderColor(const struct Paintable *_this);
void Paintable_set_FillColor(struct Paintable *_this, int value);
int Paintable_get_FillColor(const struct Paintable *_this);

#endif

/* Listing of paintable.c */
#include "paintable.h"

void Paintable_Constructor(struct Paintable *_this)
{

    _this->vptr = vtable_Paintable;

    _this->borderColor = 0;
    _this->fillColor = 0;

}

void Paintable_set_BorderColor(struct Paintable *_this, int value)
{
    _this->borderColor = value;
}

int Paintable_get_BorderColor(const struct Paintable *_this)
{
    return _this->borderColor;
}

void Paintable_set_FillColor(struct Paintable *_this, int value)
{
    _this->fillColor = value;
}

int Paintable_get_FillColor(const struct Paintable *_this)
{
    return _this->fillColor;
}

Linked base type is providing functionality to insert object into existing double linked list or to remove instance from the list. Double linked list will be maintained as a circular list with specially dedicated anchor node as shown in the picture below. Anchor node does not contain actual data but only points to first and last element in the list. Object which controls the list must know the anchor element at all times, or otherwise it would not be able to iterate through the list and to recognize its head and tail nodes.

Below are the listings of linked.h and linked.c source code files in which Linked type is defined. Observe that this type does not have virtual methods and therefore it does not contain virtual table pointer.

/* Listing of linked.h */

#ifndef LINKED_H
#define LINKED_H

struct Linked
{
    struct Linked *prev;
    struct Linked *next;
};

void Linked_Constructor(struct Linked *_this);
void Linked_InsertBefore(struct Linked *_this, struct Linked *node);
void Linked_InsertAfter(struct Linked *_this, struct Linked *node);
void Linked_Remove(struct Linked *_this);
struct Linked *Linked_get_Prev(const struct Linked *_this);
struct Linked *Linked_get_Next(const struct Linked *_this);

#endif

/* Listing of linked.c */

#include "linked.h"

void Linked_Constructor(struct Linked *_this)
{
    _this->prev = _this->next = _this;
}

void Linked_InsertBefore(struct Linked *_this, struct Linked *node)
{
    _this->next = node;
    _this->prev = node->prev;
    _this->next->prev = _this;
    _this->prev->next = _this;
}

void Linked_InsertAfter(struct Linked *_this, struct Linked *node)
{
    _this->next = node->next;
    _this->prev = node;
    _this->next->prev = _this;
    _this->prev->next = _this;
}

void Linked_Remove(struct Linked *_this)
{
    _this->next->prev = _this->prev;
    _this->prev->next = _this->next;
    _this->prev = _this->next = _this;
}

struct Linked *Linked_get_Prev(const struct Linked *_this)
{
    return _this->prev;
}

struct Linked *Linked_get_Next(const struct Linked *_this)
{
    return _this->next;
}

And so we come to the point where Canvas type is about to be implemented. Canvas is here defined as a rectangular surface which contains shapes. It exposes methods to get and set the canvas size and also methods to manipulate the list of contained shapes. List of shapes is implemented as a static instance of the list node, which is actually the list anchor. With all shapes in place, canvas can be ordered to draw them by calling the PaintShapes method. To implement drawing, canvas will internally maintain a matrix of pixels, each element of the matrix containing color code of one pixel on the rectangular canvas. At this moment, color codes will be captured in integer values. Supposing that code is compiled on a 32-bit system, this is quite sufficient to store true colors.

Below is the listing of canvas.h header file, followed by canvas.c implementation file. Canvas derives from polymorphic type PaintProvider and implements its abstract methods HorLine and VertLine. The fact that Canvas has a virtual method table to initialize is sufficient to add constructor to the type.

/* Listing of canvas.h */

#include "vtable.h"
#include "paint_provider.h"
#include "linked.h"
#include "shape.h"

#ifndef CANVAS_H
#define CANVAS_H

vtable_entry vtable_PaintProvider_Canvas[VT_PAINTPROVIDER_END];

struct Canvas
{
    struct PaintProvider _base;
    int width;
    int height;
    struct Linked shapes;
    int **pixels;
};

void Canvas_Constructor(struct Canvas *_this);
void Canvas_Destructor(struct Canvas *_this);
int Canvas_get_Width(const struct Canvas *_this);
void Canvas_set_Width(struct Canvas *_this, int value);
int Canvas_get_Height(const struct Canvas *_this);
void Canvas_set_Width(struct Canvas *_this, int value);
void Canvas_AddShape(struct Canvas *_this, struct Shape *shape);
int Canvas_RemoveShape(struct Canvas *_this, const char *shapeName);
void Canvas_RemoveAllShapes(struct Canvas *_this);
int Canvas_get_ShapesCount(const struct Canvas *_this);
void Canvas_PaintShapes(struct Canvas *_this);
void Canvas_HorLine(struct Canvas *_this, int x1, int x2, int y, int color);
void Canvas_VertLine(struct Canvas *_this, int y1, int y2, int x, int color);
void Canvas_pvt_ReallocatePixels(struct Canvas *_this);
void Canvas_pvt_FreePixels(struct Canvas *_this);

#endif

/* Listing of canvas.c */

#include "canvas.h"
#include "paintable.h"
#include "linked.h"
#include "shape.h"
#include <stdlib.h>
#include <memory.h>
#include <string.h>

void Canvas_Constructor(struct Canvas *_this)
{

    /* First calling base type constructor */
    PaintProvider_Constructor((struct PaintProvider*)_this);

    /* Then override virtual table pointer provided by the base type */
    _this->_base.vptr = vtable_PaintProvider_Canvas;

    /* Finally, initialize members either by setting them directly */
    /* or by calling appropriate constructor */
    Linked_Constructor(&_this->shapes);

    _this->width = 0;
    _this->height = 0;

    _this->pixels = 0;

}

void Canvas_Destructor(struct Canvas *_this)
{
    Canvas_RemoveAllShapes(_this);
    Canvas_pvt_FreePixels(_this);
}

int Canvas_get_Width(const struct Canvas *_this)
{
    return _this->width;
}

void Canvas_set_Width(struct Canvas *_this, int value)
{
    _this->width = value;
    Canvas_pvt_ReallocatePixels(_this);
}

int Canvas_get_Height(const struct Canvas *_this)
{
    return _this->height;
}

void Canvas_set_Height(struct Canvas *_this, int value)
{
    _this->height = value;
    Canvas_pvt_ReallocatePixels(_this);
}

void Canvas_AddShape(struct Canvas *_this, struct Shape *shape)
{

    /* Static offset applied to Shape pointer to create Linked pointer */
    struct Linked *linked =
        (struct Linked*)((unsigned char*)shape + sizeof(struct Paintable));

    /* Now add new shape to end of the list, i.e. before anchor node */
    Linked_InsertBefore(linked, &_this->shapes);

}

int Canvas_RemoveShape(struct Canvas *_this, const char *shapeName)
{

    int removed = 0;
    vcall_Shape_Destructor destructor = 0;

    struct Linked *cur = &_this->shapes;

    while (Linked_get_Next(cur) != &_this->shapes)
    {

        struct Shape *shape = (struct Shape*)Linked_get_Next(cur); /* No pointer offset */

        if (strcmp(Shape_get_Name(shape), shapeName) == 0)
        {

            void *thisPtr = 0;

            Linked_Remove(Linked_get_Next(cur));
            removed = 1;

            /* Now call virtual destructor on the shape */
            destructor = (vcall_Shape_Destructor)
                vtable_ResolvePointer(shape, VT_SHAPE_DESTRUCTOR, &thisPtr);
            destructor((struct Shape*)thisPtr);
            free(shape);

            break; /* Cancel further processing */

        }

    }

    return removed;

}

void Canvas_RemoveAllShapes(struct Canvas *_this)
{

    vcall_Shape_Destructor destructor = 0;
    void *rawThis = 0;

    while (Linked_get_Next(&_this->shapes) != &_this->shapes)
    {

        struct Linked *linked = Linked_get_Next(&_this->shapes);
        struct Shape *shape =
            (struct Shape*)((unsigned char*)linked - sizeof(struct Paintable));
        /* Static pointer offset applied */

        Linked_Remove(Linked_get_Next(&_this->shapes));

        /* Now call virtual destructor for the shape */
        rawThis = shape;
        destructor = (vcall_Shape_Destructor)
            vtable_ResolvePointer(shape, VT_SHAPE_DESTRUCTOR, &rawThis);
        destructor((struct Shape*)rawThis);
        free(shape);

    }

}

int Canvas_get_ShapesCount(const struct Canvas *_this)
{

    int count = 0;

    const struct Linked *cur = &_this->shapes;

    while (Linked_get_Next(cur) != &_this->shapes)
    {
        count++;
        cur = Linked_get_Next(cur);
    }

    return count;

}

void Canvas_PaintShapes(struct Canvas *_this)
{

    struct Linked *linked = Linked_get_Next(&_this->shapes);

    while (linked != &_this->shapes)
    {

        struct Shape *shape =
            (struct Shape*)((unsigned char*)linked - sizeof(struct Paintable));
        /* Static offset applied */

        vcall_Paintable_Paint paint = 0;

        /* Now calculate Paintable subobject pointer by applying offset from vtable*/
        void *rawThis = shape;
        paint = (vcall_Paintable_Paint)
            vtable_ResolvePointer(shape, VT_PAINTABLE_PAINT, &rawThis);

        paint((struct Paintable*)rawThis, (struct PaintProvider*)_this);

        linked = Linked_get_Next(linked);

    }

}

void Canvas_HorLine(struct Canvas *_this, int x1, int x2, int y, int color)
{

    if (y >= 0 && y < _this->height)
    {

        if (x1 < 0)
            x1 = 0;

        if (x2 >= _this->width)
            x2 = _this->width - 1;

        while (x1 <= x2)
        {
            _this->pixels[y][x1] = color;
            x1++;
        }

    }

}

void Canvas_VertLine(struct Canvas *_this, int y1, int y2, int x, int color)
{

    if (x >= 0 && x < _this->width)
    {

        if (y1 < 0)
            y1 = 0;

        if (y2 >= _this->height)
            y2 = _this->height - 1;

        while (y1 <= y2)
        {
            _this->pixels[y1][x] = color;
            y1++;
        }

    }

}

void Canvas_pvt_ReallocatePixels(struct Canvas *_this)
{

    Canvas_pvt_FreePixels(_this);

    if (_this->width > 0 && _this->height > 0)
    {

        int i;

        _this->pixels = (int**)calloc(_this->height, sizeof(int*));

        for (i = 0; i < _this->height; i++)
        {
            _this->pixels[i] = (int*)calloc(_this->width, sizeof(int));
            memset(_this->pixels[i], 0, _this->width * sizeof(int));
        }
    }

}

void Canvas_pvt_FreePixels(struct Canvas *_this)
{

    if (_this->pixels)
    {

        int i;

        for (i = 0; i < _this->height; i++)
            free(_this->pixels[i]);

        free(_this->pixels);
        _this->pixels = 0;

    }

}

Now that we have completed all the infrastructure, we can finally implement Paint abstract methods in Ellipse and Rectangle types. These are the types that know how to paint themselves and thus they provide the implementation. We will start with the rectangle because it is simpler to implement:

/* Partial listing of rectangle.h */
#include "shape.h"
#include "paintable.h"
#include "paint_provider.h"

#ifndef RECTANGLE_H
#define RECTANGLE_H
...
void Rectangle_Paint(struct Rectangle *_this, struct PaintProvider *paintProvider);
...
#endif

/* Partial listing of rectangle.c */
#include "rectangle.h"
#include <stdio.h>

...
void Rectangle_Paint(struct Rectangle *_this, struct PaintProvider *paintProvider)
{

    /* Static upcast to Shape with zero offset */
    struct Shape *shape = (struct Shape*)_this;

    /* Static upcast to Paintable with no offset required*/
    struct Paintable *paintable = (struct Paintable*)(unsigned char*)_this;

    /* Dynamic resolution of function pointer and this pointer for HorLine method */
    void *rawThisHorLine = paintProvider;
    vcall_PaintProvider_HorLine horLine = (vcall_PaintProvider_HorLine)
        vtable_ResolvePointer(paintProvider, VT_PAINTPROVIDER_HORLINE, &rawThisHorLine);
    struct PaintProvider *ppHorLine = (struct PaintProvider*)rawThisHorLine;

    /* Dynamic resolution of function pointer and this pointer for VertLine method */
    void *rawThisVertLine = paintProvider;
    vcall_PaintProvider_VertLine vertLine = (vcall_PaintProvider_VertLine)
        vtable_ResolvePointer(paintProvider, VT_PAINTPROVIDER_VERTLINE, &rawThisVertLine);
    struct PaintProvider *ppVertLine = (struct PaintProvider*)rawThisVertLine;

    int x1 = (int)(Shape_get_LocationX(shape) + 0.5F);
    int y1 = (int)(Shape_get_LocationY(shape) + 0.5F);
    int x2 = (int)(Shape_get_LocationX(shape) + _this->width + 0.5F);
    int y2 = (int)(Shape_get_LocationY(shape) + _this->height + 0.5F);

    int borderColor = Paintable_get_BorderColor(paintable);
    int fillColor = Paintable_get_FillColor(paintable);

    horLine(ppHorLine, x1, x2, y1, borderColor);
    vertLine(ppVertLine, y1 + 1, y2 - 1, x1, borderColor);
    vertLine(ppVertLine, y1 + 1, y2 - 1, x2, borderColor);
    horLine(ppHorLine, x1, x2, y2, borderColor);

    x1++;
    y1++;
    x2--;
    y2--;
    while (y1 <= y2)
        horLine(ppHorLine, x1, x2, y1++, fillColor);

}
...

Method implementation heavily relies on pointer casting. Once again, offsetting this pointers and extracting virtual function addresses dominates the function. The most complicated part of the function regards to PaintProvider which is polymorphic and thus pointers to drawing functions as well as pointer to PaintProvider itself must be calculated minutely.

Drawing ellipse is trickier than rectangle was. Task is to transform ellipse drawn in continual space (with floating point coordinates) into dots of two colors, one for border, another for interior, that fall within matrix of pixels. This problem requires quite some arithmetic and here is the implementation:

/* Partial listing of ellipse.h */
#include "shape.h"

#ifndef ELLIPSE_H
#define ELLIPSE_H
...
int Ellipse_pvt_IntersectHorLine(struct Ellipse *_this, float drx, float dry,
                                 float y, int *x1, int *x2);
void Ellipse_Paint(struct Ellipse *_this, struct PaintProvider *paintProvider);
...
#endif

/* Partial listing of ellipse.c */
#include "ellipse.h"
#include <stdio.h>
#include <math.h>
...
int Ellipse_pvt_IntersectHorLine(struct Ellipse *_this, float drx, float dry,
                                 float y, int *x1, int *x2)
{
    int intersects = 0;
    float xc = Shape_get_LocationX((struct Shape*)_this);
    float yc = Shape_get_LocationY((struct Shape*)_this);
    float rx = _this->radiusX + drx;
    float ry = _this->radiusY + dry;

    if (y >= yc - ry && y <= yc + ry)
    {
        float tmp = (y - yc) / ry;
        tmp = sqrt(1 - tmp * tmp);
        *x1 = (int)(xc - rx * tmp + 0.5F);
        *x2 = (int)(xc + rx * tmp + 0.5F);
        intersects = 1;
    }

    return intersects;

}

void Ellipse_Paint(struct Ellipse *_this, struct PaintProvider *paintProvider)
{

    float xc = Shape_get_LocationX((struct Shape*)_this);
    float yc = Shape_get_LocationY((struct Shape*)_this);

    int maxy = (int)(yc + _this->radiusY + 0.5F);
    int miny = (int)(yc - _this->radiusY - 0.5F);
    int roundy;

    /* Static upcast to Paintable with zero offset*/
    struct Paintable *paintable = (struct Paintable*)(unsigned char*)_this;

    /* Dynamic resolution of function pointer and this pointer for HorLine method */
    void *rawThis = paintProvider;
    vcall_PaintProvider_HorLine horLine = (vcall_PaintProvider_HorLine)
        vtable_ResolvePointer(paintProvider, VT_PAINTPROVIDER_HORLINE, &rawThis);
    struct PaintProvider *ppHorLine = (struct PaintProvider*)rawThis;

    int borderColor = Paintable_get_BorderColor(paintable);
    int fillColor = Paintable_get_FillColor(paintable);

    for (roundy = maxy; roundy >= miny - 1; roundy--)
    {

        float y = (float)roundy + 0.5F;

        int outerx1, outerx2;
        int intersects =
            Ellipse_pvt_IntersectHorLine(_this, 0.0F, 0.0F, y, &outerx1, &outerx2);

        if (intersects)
        {

            int innerx1, innerx2;
            intersects =
                Ellipse_pvt_IntersectHorLine(_this, -1.0F, -1.0F, y, &innerx1, &innerx2);

            if (intersects)
            {
                /* Make sure that there is a visible border */
                if (innerx1 <= outerx1)
                    innerx1 = outerx1 + 1;

                if (innerx2 >= outerx2)
                    innerx2 = outerx2 - 1;

                /* Now draw borders on left and right, and fill in the middle */
                horLine(ppHorLine, outerx1, innerx1 - 1, roundy, borderColor);
                horLine(ppHorLine, innerx1, innerx2, roundy, fillColor);
                horLine(ppHorLine, innerx2 + 1, outerx2, roundy, borderColor);

            }
            else
            {
                /* There is only a border on this line, no inner part */
                horLine(ppHorLine, outerx1, outerx2, roundy, borderColor);
            }

        }

    }

}
...

Now we are going to straighten up virtual methods subsystem which is implemented in vtable.h and vtable.c source files. We have already seen ResolvePointer function implementation before - this function came quite handy with all those function and object pointers that needed to be resolved along the route. What remains to be done is the global initializer function which populates virtual method tables for all polymorphic types. This function now becomes much more complicated than it used to be.

/* Partial listing of vtable.c */
#include "vtable.h"
#include "paintable.h"
#include "shape.h"
#include "ellipse.h"
#include "rectangle.h"
#include "paint_provider.h"
#include "canvas.h"
#include <memory.h>
...

void vtable_Initialize()
{

    /* Zero out complete vtable, including pointer offsets */
    memset(vtable_Paintable, 0, VT_PAINTABLE_END * sizeof(struct vtable_entry));
    vtable_Paintable[VT_PAINTABLE_PAINT].fptr = vtable_abstract_method_called;

    /* Zero out complete vtable, including pointer offsets */
    memset(vtable_Shape, 0, VT_SHAPE_END * sizeof(struct vtable_entry));
    vtable_Shape[VT_PAINTABLE_PAINT].fptr = vtable_abstract_method_called;
    vtable_Shape[VT_SHAPE_PRINTOUT].fptr = Shape_PrintOut;
    vtable_Shape[VT_SHAPE_PRINTOUT1].fptr = Shape_PrintOut1;
    vtable_Shape[VT_SHAPE_MOVE].fptr = Shape_Move;
    vtable_Shape[VT_SHAPE_MOVEBEYOND].fptr = Shape_MoveBeyond;
    vtable_Shape[VT_SHAPE_GETAREA].fptr = vtable_abstract_method_called;
    vtable_Shape[VT_SHAPE_DESTRUCTOR].fptr = Shape_Destructor;

    /* Copy complete vtable from base type, then override some function pointers */
    memcpy(vtable_Shape_Ellipse, vtable_Shape, VT_SHAPE_END * sizeof(struct vtable_entry));
    vtable_Shape_Ellipse[VT_PAINTABLE_PAINT].fptr = Ellipse_Paint;
    vtable_Shape_Ellipse[VT_SHAPE_PRINTOUT].fptr = Ellipse_PrintOut;
    vtable_Shape_Ellipse[VT_SHAPE_PRINTOUT1].fptr = Ellipse_PrintOut1;
    vtable_Shape_Ellipse[VT_SHAPE_MOVEBEYOND].fptr = Ellipse_MoveBeyond;
    vtable_Shape_Ellipse[VT_SHAPE_GETAREA].fptr = Ellipse_get_Area;
    vtable_Shape_Ellipse[VT_SHAPE_DESTRUCTOR].fptr = Ellipse_Destructor;

    /* Copy complete vtable from base type, then override some function pointers */
    memcpy(vtable_Shape_Rectangle, vtable_Shape, VT_SHAPE_END * sizeof(struct vtable_entry));
    vtable_Shape_Rectangle[VT_PAINTABLE_PAINT].fptr = Rectangle_Paint;
    vtable_Shape_Rectangle[VT_SHAPE_PRINTOUT].fptr = Rectangle_PrintOut;
    vtable_Shape_Rectangle[VT_SHAPE_PRINTOUT1].fptr = Rectangle_PrintOut1;
    vtable_Shape_Rectangle[VT_SHAPE_GETAREA].fptr = Rectangle_get_Area;
    vtable_Shape_Rectangle[VT_SHAPE_DESTRUCTOR].fptr = Rectangle_Destructor;

    /* Zero out complete vtable, including pointer offsets */
    memset(vtable_PaintProvider, 0, VT_PAINTPROVIDER_END * sizeof(struct vtable_entry));
    vtable_PaintProvider[VT_PAINTPROVIDER_HORLINE].fptr = vtable_abstract_method_called;
    vtable_PaintProvider[VT_PAINTPROVIDER_VERTLINE].fptr = vtable_abstract_method_called;

    /* Copy complete vtable from base type, then override some function pointers */
    memcpy(vtable_PaintProvider_Canvas, vtable_PaintProvider,
           VT_PAINTPROVIDER_END * sizeof(struct vtable_entry));
    vtable_PaintProvider_Canvas[VT_PAINTPROVIDER_HORLINE].fptr = Canvas_HorLine;
    vtable_PaintProvider_Canvas[VT_PAINTPROVIDER_VERTLINE].fptr = Canvas_VertLine;

}

Populating virtual method tables has become quite a piece of work by now. As part of efforts to contain its complexity, we have introduced memory operations like memset and memcpy. In first case, memset was used to zero out complete virtual method table. In that way we have set all pointer offsets to zero with a single instruction. After each memcpy statement, which has established initial, inherited state of the table, subtypes are providing new values for some entries. Those entries updated actually contain overridden implementations of inherited methods. Off course, every type is responsible to append its own function pointers to the table, as that part cannot be copied from the ancestor.

Test Run

Lots of code has been developed to reach the state in which we can actually draw some shapes on the canvas. Though we still lack any means to visualize the results. In this section we will first add a function which dumps content of the canvas to the screen and then use it to draw shapes. Here is the function which prints canvas content:

/* Partial listing of canvas.h */

#include "vtable.h"
#include "paint_provider.h"
#include "linked.h"
#include "shape.h"

#ifndef CANVAS_H
#define CANVAS_H
...
void Canvas_Print(struct Canvas *_this);
...
#endif

/* Partial listing of canvas.c */
...
void Canvas_Print(struct Canvas *_this)
{

    int row, col;

    putchar('+');
    for (col = 0; col < _this->width; col++)
        putchar('-');
    putchar('+');
    putchar('\n');

    for (row = 0; row < _this->height; row++)
    {
        putchar('|');
        for (col = 0; col < _this->width; col++)
        {
            int color = _this->pixels[row][col].colorValue;
            switch (color)
            {
                case 1: putchar('*');
                    break;
                case 2: putchar('.');
                    break;
                default: putchar(' ');
                    break;
            }
        }
        putchar('|');
        putchar('\n');
    }

    putchar('+');
    for (col = 0; col < _this->width; col++)
        putchar('-');
    putchar('+');
    putchar('\n');

}

This function represents color code 1 as asterisk and code 2 as a dot, all other codes replacing with space character. Quite rude solution, but very effective for simple demonstrations. And here is the code which demonstrates features of our system:

/* Listing of main.c */
#include <stdlib.h>
#include "ellipse.h"
#include "rectangle.h"
#include "shape.h"
#include "canvas.h"
#include <stdio.h>

int main(char args[])
{

    struct Canvas *canvas = (struct Canvas*)malloc(sizeof(struct Canvas));
    struct Ellipse *ellipse1 = (struct Ellipse*)malloc(sizeof(struct Ellipse));
    struct Rectangle *rectangle = (struct Rectangle*)malloc(sizeof(struct Rectangle));
    struct Ellipse *ellipse2 = (struct Ellipse*)malloc(sizeof(struct Ellipse));

    vtable_Initialize();

    Canvas_Constructor(canvas);
    Ellipse_Constructor(ellipse1);
    Rectangle_Constructor(rectangle);
    Ellipse_Constructor(ellipse2);

    Canvas_set_Width(canvas, 70);
    Canvas_set_Height(canvas, 24);

    Shape_set_LocationX((struct Shape*)ellipse1, 14.0F);
    Shape_set_LocationY((struct Shape*)ellipse1, 9.0F);
    Ellipse_set_RadiusX(ellipse1, 12.3F);
    Ellipse_set_RadiusY(ellipse1, 6.7F);
    Paintable_set_BorderColor((struct Paintable*)ellipse1, 1);
    Paintable_set_FillColor((struct Paintable*)ellipse1, 2);

    Shape_set_LocationX((struct Shape*)rectangle, 9.6F);
    Shape_set_LocationY((struct Shape*)rectangle, 6.2F);
    Rectangle_set_Width(rectangle, 56.2F);
    Rectangle_set_Height(rectangle, 12.5F);
    Paintable_set_BorderColor((struct Paintable*)rectangle, 1);
    Paintable_set_FillColor((struct Paintable*)rectangle, 2);

    Shape_set_LocationX((struct Shape*)ellipse2, 55.3F);
    Shape_set_LocationY((struct Shape*)ellipse2, 12.3F);
    Ellipse_set_RadiusX(ellipse2, 22.6F);
    Ellipse_set_RadiusY(ellipse2, 10.7F);
    Paintable_set_BorderColor((struct Paintable*)ellipse2, 1);
    Paintable_set_FillColor((struct Paintable*)ellipse2, 2);

    Canvas_AddShape(canvas, (struct Shape*)ellipse1);
    Canvas_AddShape(canvas, (struct Shape*)rectangle);
    Canvas_AddShape(canvas, (struct Shape*)ellipse2);

    Canvas_PaintShapes(canvas);

    Canvas_Print(canvas);

    Canvas_Destructor(canvas);
    free(canvas);

    /* Shapes have already been released by canvas destructor */

}

Most of the code is dedicated to setting shapes properties. Once that is done, shapes are added to the canvas and then painted in only a couple of lines. Final part of the function releases the canvas. Since all shapes are contained in it, canvas is then responsible for their release as well. Consequently, shape pointers initially created should not be released in the main function. Should one decide to release them anyway, then RemoveAllShapes method would have to be called on the canvas first, so to indicate to the canvas that it is not in charge of releasing resources occupied by shapes.

And here is the output produced by this code:

+----------------------------------------------------------------------+
|                                                                      |
|                                                                      |
|           *******                            *******************     |
|       ****.......****                    ****...................**** |
|     **...............**                **...........................*|
|    *...................*             **..............................|
|   *......****************************................................|
|  *.......*........................**.................................|
|  *.......*.......................*...................................|
|  *.......*......................**...................................|
|  *.......*......................*....................................|
|   *......*......................*....................................|
|    *.....*......................*....................................|
|     **...*......................*....................................|
|       ****......................*....................................|
|          *.......................*...................................|
|          *........................*..................................|
|          *.........................*.................................|
|          *..........................**...............................|
|          *******************************.............................|
|                                         ***........................**|
|                                            ****...............*****  |
|                                                ***************       |
|                                                                      |
+----------------------------------------------------------------------+

---