Object Orientation in C?!

Introduction

If you ever had to write code for a microprocessor or any other device which had no C++ compiler or you had to use C and not C++, you may value the layer of abstraction and structure classes provide. This project will show you that this is also possible in C. I for instance always wanted to use strings and lists in C without spreading new methods everywhere. Objects should have properties, methods and also should support polymorphism (calling different methods by the same name depending on the type).

Turns out you can do that in C by defining pointers in a struct and setting them to certain methods inside a constructor. You can even pass around any object since any struct can be passed as a void pointer.

If you just want to try it out now, feel free to test the demo or download the source code.

• Download demo
• Download source
• Download Visual Studio Project

Background

C++ started out in 1979 by Bjarme Stroustrup. At first C++ (C with classes) started out in normal C. As you will see, it is totally possible to create class like objects and work with them in C. C++ was (at the beginning at least) a convenience update for the object oriented paradigm.

Object orientation in C has some drawbacks: You have to set every method manually, private and public members are realised by using c and h files.

You will also see that polymorphism and generic template like programming is possible in C. Once you have created a class in C, you really can use it on any machine.

Strings in C

• Download String.zip

If we want to create a String class, we have to create a class which contains:
The class keyword does not exist in C so we have to define a struct of type string:

Methods

• Constructor (New_String)
• Destructor (Free)
• Append
• Print

Properties

• Length
• Content

You start by defining an "interface" in a header file.
The definitions in the header is what can be seen from a code perspective.

(public members) (String.h)

typedef struct String
{
    char* Content;                                //Properties
    int Length;

    void(*Append)(void *self,char* text);        //Method
    void(*Print)(void *self);
    void(*PrintLine)(void *self);
    void(*Free)(void *self);                    //Destructor
} String;

String *New_String(char* text);    //Constructor

Now you see that the concept of a "this" pointer does not exist in C. You have to pass the instance to every method. Think of it as if every method would be static.

Now we have to define the constructor:
The .c file cannot be seen from a code perspective.

(private members) (String.c)

String *New_String(char* text)
{
    struct String* k = malloc(sizeof(String));
    
    k->Content = _strdup(text);
    k->Length = strlen(k->Content);

    k->Append = &Append;
    k->Free = &Free_String;
    k->Print = &Print;
    k->PrintLine = &PrintLine;

    return k;
}

The constructor returns a pointer to the instance of the class. Every method like Append, Free_String (destructor) is defined in the c file above the constructor. You can see that for every instance of string, the append pointer is set to the same method. It is really important to define a constructor and to clean up for every malloc used.

(String.c)

For easier copy paste:

#include "String.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Free_String(String *Instance)
{
    free(Instance->Content);
    free(Instance);
}

void Append(String *Instance,char* text)
{
    size_t len1 = Instance->Length;
    size_t len2 = strlen(text);
    char *result = malloc(len1 + len2 + 1);//+1 for the zero-terminator
                                           
    memcpy(result, Instance->Content, len1);
    memcpy(result + len1, text, len2 + 1);//+1 to copy the null-terminator
    free(Instance->Content);
    Instance->Content = result;

    Instance->Length = strlen(Instance->Content);
}

void Print(String *Instance)
{
    printf("%s", Instance->Content);
}

void PrintLine(String *Instance)
{
    printf("%s\n", Instance->Content);
}

String *New_String(char* text)
{
    struct String* k = malloc(sizeof(String));
    
    k->Content = _strdup(text);
    k->Length = strlen(k->Content);

    k->Append = &Append;
    k->Free = &Free_String;
    k->Print = &Print;
    k->PrintLine = &PrintLine;

    return k;
}

Notice that Free also cleans up itself. No leaks are left behind.
Note that the Length property is updated after every append. This class can be expanded easily by defining a method in the .h file and the code in the .c file. Dont forget to "wire" the function pointer of the .h file to the function pointer of the .c file.

How to use in main:

(main.c)

#include "String.h"
#include "List.h"
#include <stdio.h>
#include "Main.h"

int main(int argc, char **argv)
{
    String* r = New_String("Hello");
    r->Append(r, " World");
    r->PrintLine(&r);
    r->Free(r);
    getch();
}

//append user string in main
char str[100];
gets_s(str, 100);
r->Append(r, &str);

Do not call any method after Free. This will certainly result in failure of the program. The output of this program is "Hello World".

Lists in C

• Download List.zip

Now we want a fast list in C (it is implemented as an array in the background).

A list should consist of:

Methods

• Constructor (New_List)
• Destructor (Free)
• Add
• Get
• RemoveAt

Properties

• Length
• AsArray

(public members) (List.h)

In fact, AsArrayLength should be private but I have not found a way to hide members. The Count property tells you how much data is in the List.

typedef struct List
{                                        
    int Count;                                                    //Properties
        
    void(*Add)(void *self, int value);                            //Method
    int(*Get)(void *self,int index);
    void(*RemoveAt)(void *self,int index);
    void(*Clear)(void *self);
    void(*Free)(void *self);                                    //Destructor

    int* AsArray;
    int AsArrayLength;
} List;

List *New_List();

(private members) (List.c)

You can see that the class implementation is similar to String. You set all corresponding methods in the constructor. This list is typesafe as you can only insert integers. You could also insert the pointer to any data (32 bit only). At first, the list has space for 16 elements. If you add more than 16 elements, the internal array gets resized to hold 64 elements and so on. The implementation is pretty much the same as in List<T> in the .NET Framework.

The Count property always has the right value and internally the list is very efficient because it is just an array.

#include "List.h";
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int* ResizeArray(int* Old, int oldsize, int newsize)
{
    if (oldsize < newsize)    //grow
    {
        int* newpos = malloc(newsize*sizeof(int));
        memcpy(newpos, Old, oldsize*sizeof(int));
        free(Old);
        return newpos;
    }
    else  //shrink
    {
        realloc(Old, newsize*sizeof(int));

        return Old;
    }
}

void AddMethod(List *self, int object)
{
    if (self->Count + 1 > self->AsArrayLength)    //needs to resize
    {
        self->AsArray=ResizeArray(self->AsArray,self->Count,self->Count*2);
        self->AsArrayLength = self->Count * 2;
    }

    int index = self->Count;
    self->AsArray[index] = object;
    self->Count++;
}

void* Get(List *self, int index)
{
    int nr = self->AsArray[index];

    return nr;
}

void Removeat(List *self, int index)
{
    memmove(self->AsArray + index, self->AsArray + index + 1, 
           (self->Count - index - 1)*sizeof(int)); //move one to the left
    self->Count--;

    if (self->AsArrayLength / 2 > self->Count && self->Count>16)    //needs to shrink
    {
        self->AsArray = ResizeArray(self->AsArray, self->AsArrayLength, self->AsArrayLength / 2);
        self->AsArrayLength = self->AsArrayLength / 2;
    }

    return;
}

void ClearMethod(List *self)
{
    free(self->AsArray);
    self->Count = 0;
    self->AsArray = (int*)malloc(sizeof(int) * 16);
    self->AsArrayLength = 16;
}

void FreeList(List *self)
{
    free(self->AsArray);
    free(self);
}

List *New_List()
{
    struct List* inst = malloc(sizeof(List));

    inst->Count = 0;
    
    inst->Add = &AddMethod;
    inst->Get = &Get;
    inst->RemoveAt = &Removeat;
    inst->Clear = &ClearMethod;
    inst->Free = &FreeList;

    inst->AsArray = (int*)malloc(sizeof(int) * 16);
    inst->AsArrayLength = 16;

    return inst;
}

How to use in code:

(Main.c)

This program creates a list with 100000 elements. Then it deletes the third element. The shifting of the array is as fast as it can be by using memshift. A linked list would be faster for this, but this list does not waste memory space by saving a pointer to the next element.

int main(int argc, char **argv)
{

    List* List = New_List();
    for (int i = 0; i < 1000000; i++)
    {
        List->Add(List, i);
    }
    int Size = List->Count;
    int ThirdElement = List->Get(List, 3); //really the fourth as 0 is also in there

    printf("Size of list is %d Third item is %d \n", Size, ThirdElement);
    List->RemoveAt(List, 3);
    int NowThird = List->Get(List, 3);

    printf("After remove at 3 the third element is now %d", NowThird);

    getch();
}

Dont forget to call List->Free(List) after using it. Memory leaks can be very hard to find.

Polymorphism

Polymorphism can be achieved by calling an alternative constructor. Let's try that with string:

string.h

String *New_String(char* text); //Constructor
String *New_Specialstring(char* text);  //Constructor 2

For the constructor, all we have to do is wire the method (print) to another method. Both string types will look the same from a usage point of view as all methods have the same name. Internally, different methods get called. string.h really just defines an interface with which we can do anything internally really.

string.c

String* New_String(char* text)
{
    struct String* k = malloc(sizeof(String));
    
    //...
    k->Print = &Print;
    k->PrintLine = &PrintLine;
    return k;
}

void Print(String *Instance) { printf("%s", Instance->Content); }
void PrintAlt(String *Instance){printf("%s", "I AM A SPECIAL STRING");}

String* New_Specialstring(char* text)
{
    k->Print = &PrintAlt;
}

You can create both types by calling:

String* a = New_String("LOL");
String* b = New_Specialstring("LOL");

a->Print(a);
b->Print(b);

//Output: LOL I AM A SPECIAL STRING

Templates (Generics) in C

This is a little trickier. You see it has a good preprocessor. #define inserts your snippet anywhere it is used. If we want a generic list, all we have to do is to #define a generic struct. The ##T keyword does get us the string passed to define. You can also make multi line #defines by ending the line with \.

List.h

#define GenerateList(T) ListStruct(T) \
List_##T *New_List_Generic(int size);

#define ListStruct(T) typedef struct List_##T\
{\
    int Count;\
    void(*Add)(void *self, T value);\
    T(*Get)(void *self, int index);\
    void(*RemoveAt)(void *self, int index);\
    void(*Clear)(void *self);\
    void(*Free)(void *self);\
    T* AsArray;\
    int AsArrayLength;\
} List_##T;

//If we want a list of float we call:
GenerateList(float)

GenerateList(float) turns into:

typedef struct List_float { int Count; void(*Add)(void *self, float value); 
float(*Get)(void *self, int index); void(*RemoveAt)(void *self, int index); 
void(*Clear)(void *self); void(*Free)(void *self); float* AsArray; int AsArrayLength; } 
List_float; List_float *New_List_Generic(int size);

This is really useful because you don't have to implement a list int, float, double and so on. With this, you don't lose type safety.
Warning: Although this is type safe, bugs induced by the preprocessor can be hard to detect. It is easier to just use the normal list of integers with pointers for generic lists.

This only inserts the interface for the generic list. For the implementation, you have to use yet another preprocessor macro:

List.c

You would have to define a macro like this:

New_List_Generic() List_##T *New_List_##T()
{
    struct List_##T* inst = malloc(sizeof(List_##T));
    inst->Count = 0;
    inst->Add = &AddMethod;
    inst->Get = &Get;
    inst->RemoveAt = &Removeat;
    inst->Clear = &ClearMethod;
    inst->Free = &FreeList;
    inst->AsArray = (T*)malloc(sizeof(T) * 16);
    inst->AsArrayLength = 16;
    return inst;
}

As you can see, this is not complete. For every method in the constructor, you now would have to define a generic method. (Add should accept float and so on.)

Points of Interest

This project was really fun to create. If you have questions or something interesting to share, please leave a comment.