Opaque Type Oriented Programming in C

Non-C / Non-C++ programmers usually tend to confuse both languages with one another. Even though C++ is (in general) a superset of C, they are at their root very different programming languages.

One of the main reasons C is so different from C++ is that C does not include classes and thus would be -in principle- not object oriented.

The fact that the language does not include provisions for creating classes does not preclude adopting some sort of object-oriented programming style, however. In this post I’m going to introduce Opaque-Type Oriented Programming, a technique that allows our C programs to be structured as if they were populated with objects.

Opaque-Type oriented programming is a great programming paradigm that fits perfectly on structured programming. Ever since the first time I discovered this programming style, I keep finding in every piece of C code I come across.

As usual, I’m going to introduce this concept using examples. In this case, let’s suppose we want to build a dynamic array type for the C programming language.

Opaque Type Declaration and Interface

Here are some operations we might want our dynamic array to include:

1. Initialization (with a given capacity).
2. Adding an object (we’ll stick to real numbers for this example).
3. Random access.
4. Destruction.

Structured programming would dictate that we have some sort of static array allocated on the heap and that we have functions that work on said array.

In Opaque-Type oriented programming, the idea is fundamentally the same, but instead of dealing with the array directly, we are going to hide it in a struct together with all the attributes that are related to it, namely, its current size and capacity.

typedef float real; //change this to double for double precision

typedef struct dynarray
{
    real* pdata;
    size_t size;
    size_t capacity;
} dynarray;

Size and capacity are different things. Size denotes the current number of elements stored in our dynamic array, whereas capacity denotes the maximum number of elements that could be stored in this array.

Note: if you don’t know what size_t is, you can think of it as being an “unsigned long int”. It is 32 bits wide when compiled for a 32-bit OS, 64-bits wide when compiled for a 64-bit OS and it doesn’t have a sign bit.

Operations

Now that we have a struct to hold our dynamic array’s state and data, we need a set of functions that operate on this array. The idea behind Opaque-Type oriented programming is that we are able to use this dynamic array without having to know anything about its inner state or data.

The “contract” for operating on the dynamic array is given by the functions that we develop that know how to work on it.

Let’s start with initialization. In this example, we are going to have the initialization function allocate all inner state but the struct must be allocated by the user. This gives the programmer the option to create the array in the stack or in the heap.

void dynarray_init(dynarray* parray, size_t capacity) 
{
     parray->pdata = (real *)malloc(capacity*sizeof(real));
     parray->capacity = capacity;
     parray->size = 0;
}

It is usually a good idea to prefix all the functions with the name of the opaque type. This helps the code be auto-documentative and hels prevent name clashes (remember that C doesn’t have namespaces).

Now that the init function has initialized all the state and prepared the array to be used by the other functions, let’s have a look at the rest of them.

One of the hardest issues to solve when dealing with dynamic arrays is handling the case where we need reallocate the inner data because we are out of space (i.e. the capacity is exhausted).

While in structured programming this logic may very well pollute all of our algorithms, in Opaque-Type programming we can just hide this mechanism in our “add” function and have the programmer completely isolated from it.

void dynarray_add(dynarray* parray, real elem)
{
    if ((parray->size + 1) == parray->capacity)
    {
        // out of space, expand the array 
        // to hold 10 more elements:

        parray->pdata = (real *)realloc(parray->pdata, (parray->capacity + 10)*sizeof(real));
        assert(parray->pdata);
        parray->capacity += 10;

    }

    parray->pdata[parray->size] = elem;
    parray->size += 1;

}

There it is. From the outside world, no one needs to know how our dynamic array expands to fit as many elements as we want to store.

The only constraint that we have is if we run out of memory, and a real-world implementation of a dynamic array should handle this case. Another possible improvement would be not to allocate a fixed 10 more reals but a variable number that depends on how fast the array is actually growing (just to prevent lots of calls to realloc, which is kind of expensive).

Up to this point you can imagine how the “at” function would work. You would be surprised to learn how many of my students actually get this function wrong the first time just because they don’t pause and consider that the dynamic array doesn’t have the actual data but a pointer to it.

I’m going to present this function here just for the sake of completeness:

real dynarray_at(dynarray parray*, size_t position)
{
    assert(position < parray->size); //sanity check

    return parray->pdata[position]; // of course parray[position] compiles too, but it's a gross logic error!

}

Finally, I’m going to present how to deallocate our dynamic array. Remember we didn’t allocate the struct, so we are going to free the inner data only. I completely subscribe to Objective-C’s trail of though of “whoever allocates something should also release it”.

void dynarray_free(dynarray* parray)
{
    free(parray->pdata);
    parray->capacity = 0;
    parray->size = 0;
}

Putting it all together

Now that our opaque-type dynamic array is ready, I’m going to show you how we can use it in practice.

An exercise for the reader would be to compare how much easier this is compared to trying to handle the same data structure without any wrapping (consider this homework ; ))

#include <stdio.h>
int main()
{
    dynarray darray; //alloc'd in the stack, no free needed
    dynarray_init(&darray, 10); // initialize our array
    for (size_t i = 0; i < 100; i++)
    {
        dynarray_add(&darray, i); // it will automatically grow
    }
    for (size_t i = 0; i < 100; i++)
    {
        printf("%f ", dynarray_at(&darray, i));
    }
    printf("\n");
    dynarray_free(&darray); // remember to free inner data!
    return 0;
}

There we go. We now have a dynamic array implementation that automatically expands to accomodate new elements that would not fit in the current allocated storage.

Just as we wrapped the dynamic array, you might wrap any concept: matrices, hashmaps, semaphores, threads, you name it. You can actually find many opaque types in the UNIX standard C library (the pthread and BSD sockets libraries are great examples).

I hope this post gave you a good first impression on Opaque-Type oriented programming and that you find it useful in your structured software designs.