Implementing a Vector in C With Pointers: Taming the Beast

It was an unusually cold spring morning, that fateful April day, and the air was tense. The village had been bracing for a hard year, and the threat of a pointed menace was lurking about. But enough was enough. After decades of living in terror of this undefined horror, one man had the courage to say no more!

Chris set out to slay the beast.

The C programming language has these terrible things called pointers. Pointers are declared like so:

int * foo;
foo = malloc(sizeof(int));
*foo = 1;

… and used like …

printf("foo points to %d", *foo);

… outputting …

foo points to 1

Miss any of that, and things go off the rails. Miss the first line and your program won’t compile. Miss the second, and your pointer is null, resulting in a Undefined Behavior if you try to use it. Miss the third, and you haven’t assigned a value to your pointer. If you try to dereference this pointer, you’ll get Undefined Behavior.

Having had this undefined creature get the drop on him more often than he’s proud of, Chris gave himself an exercise: create a “generic” vector in C using void pointers. This vector should have all the usual resizing fanciness, and should take any type. This being C, and not having access to C++ templates, makes it a bit more difficult. Chris created the following struct to represent his vector:

typedef struct
{
void * contents;
int length;
int increment_by;
size_t size;
} vector;

Going down the list: contents is the array backing the vector, length is the size of the contents array, increment_by is how much vector_resize() should increase the array size by, and size is the sizeof() the type contained by this vector. By itself, this struct contains all the bits required to make this vector work, but as it stands it’s just an annoying to use array. Chris couldn’t even trust himself to not mess this up, what chance did the villagers have? He created helper functions.

This function populates the initial values of all the vector members, and returns a pointer to this newly created vector.

vector * vector_new(size_t type_size, int initial_size, int resize_inc)
{
vector * new_vec = malloc(sizeof(vector));
new_vec->length = initial_size;
new_vec->size = type_size;
new_vec->contents = malloc(new_vec->size * new_vec->length);
new_vec->increment_by = resize_inc;
return new_vec;
}

This function handles freeing all allocated memory.

void vector_delete(vector * to_delete)
{
free(to_delete->contents);
free(to_delete);
}

This function handles accessing the vector. Were this C++ Chris would just overload the [] operator. if to_get is greater than or equal to to_get_from->length it calls vector_resize() to increase the size of the vector. The pointer returned by this function needs to be casted to a pointer of the appropriate type.

void * vector_access(int to_get, vector * to_get_from)
{
while (to_get >= to_get_from->length)
vector_resize(to_get_from);
return accessor(to_get_from->contents, to_get, to_get_from->size);
}

This function resizes the contents array. It creates a new larger array, and copies the contents of the old array to the new one.
Since you can’t use pointer arithmetic on a void pointer, accessor() is used to access the array. The pointer returned by accessor() is casted to char*, and copied byte-for-byte into the new array.

void vector_resize(vector * to_resize)
{
int count;
int pointer_count;
void * new_cont = malloc (to_resize->size * (to_resize->length + to_resize->increment_by));

for (count = 0; count length; count++)
{
char * old = vector_access(count, to_resize);
char * new = accessor(new_cont, count);
for (pointer_count = 0; pointer_count size; pointer_count++)
{
*(new + pointer_count) = *(old + pointer_count);
}
}

free(to_resize->contents);
to_resize->contents = new_cont;
to_resize->length = to_resize->length + to_resize->increment_by;
}

Finally, this function handles indexing into the void pointer array. This is accomplished by casting the pointer to char*, and accessing the correct index by multiplying the index by to_access->size.

void * accessor(void * to_access, int index)
{
char * working = (char*) to_access;
void * return_value = (void*) (working + (index * to_access->size));
return return_value;
}

Together with his vector, Chris heroically sets off to make the night just a little bit less terrifying…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: