basicnumerics.com Blog

In an earlier entry, we developed a generic array in C and a way to loop through that array. The idea behind this is simple: if we have a standard way to working with arrays, we can eliminate common errors (like writing outside array bounds) while providing great flexibility. In playing with this tool, I found that I need a function for writing an element to an array. I quickly whipped something out and hit a roadblock.

Imagine a function, ListAppend, that adds a new element onto the end of a generic array. Its declaration might look like this:

int ListAppend(AList *list, void *item)

(The name ListAppend might seem odd in the context of C arrays, but I am picturing a python list, that you can easily manipulate without worries.) This function takes the list, and a pointer to the item to be added and returns the array index of this new item. The problem comes when we try to copy the data in item to its slot in the array. Imagine some code like this

void *pData = list->Data + list->NumEl * list->ElSize;  //calc where to write data
*pData = *item;      //  Write data  <--  illegal!  Can't deref void ptr.

The first line determines where to write the data (at the end of the array) and the second line writes it. Unfortunately, the compiler doesn’t like this. Because both pointers are of type void, the compiler doesn’t know how many bytes to copy from *item and doesn’t know how many *pData can safely hold. For this to work right, both pointers need to be of the correct type. The compiler needs this information at compile time, so we can’t be setting it at run time. What to do?

Solutions

I have thought of three ways to approach this, none totally satisfactory.

- User defined assignment function
- memcopy
- macros

In the first method, we have a single ListAppend function of the form:

int ListAppend(AList *list, void *item)

like before. But we add a function pointer to the list structure. This pointer points to a user written function that copies the data from item to the correct slot at the end of the array. Here is an example of such a function:

int AssignFuncVert(void *src, void *dest)
{
	VERT_TYPE *pdest = (VERT_TYPE *)dest;
	VERT_TYPE *psrc = (VERT_TYPE *)src;
	*pdest = *psrc;
	return 0;
}

This code first casts the pointers into the appropriate type (VERT_TYPE in this case) and then does the assignment. This approach is in the opposite direction of where we are trying to go with these generic arrays. We want our generic structures to be easy to use. Function pointers have complex syntax and are scary for some people.

The memcpy approach takes advantage of the memcpy function in the string.h file. This function copies n bytes from one location to the other. You don’t have to worry about types. As long as you copy the correct number of bytes, all is well. Since we are already storing the size of an element, this is no problem. The memcpy function is called like so:

memcpy(pData, item, list->ElSize)

This approach requires no additional work on the part of the user, which makes it very attractive. On the downside, we are circumventing the type checking the compiler does, which may set us up for problems.

In the third approach, we mimic templates in C++. A macro is used to generate a ListAppend function for each data type of interest. You would call the macro like so:

LIST_APPEND(ListAppendVert, VERT_TYPE)

and get a function that looks like:

int ListAppendVert(ALIST *list, VERT_TYPE *item)

The nice thing about this approach is it is type safe. If you pass the wrong thing to the ListAppendVert function, the compiler will complain. The downside is it is a bit unclear, just from looking at an include file containing this macro, what you are supposed to do. There would have to be some good comments included.

Pros and Cons

All three approaches have pros and cons. In my view, the most important criteria in deciding which approach is best are simplicity and robustness. We all have limited bandwidth, and we don’t want to waste it on stupid stuff. A generic array is nice, but if it takes too long to come up to speed each time we use it, we will just use ordinary arrays. Robustness is more subtle. Will the code stand up to typos and other errors, either by flagging them early or gracefully doing the right thing? Not being a strong C programmer, it is hard for me to anticipate what might go wrong.

Approach       Simplicity      Robustness
--------------------------------------------------------------------------- --------------------------------------------
User Func         low             med
memcpy            high            med
Macros            med             high
--------------------------------------------------------------------------- -------------------------------------------

The table is a stab at rating the three approaches. The memcpy approach doesn’t require any extra work by the user, so it ranks well simplicity. I think it should be safe, but can’t be positive. Copying bytes, regardless of type seems a bit risky. The user function approach could be a turn off to people. Function pointers are tricky enough to scare many off. The macro approach is very attractive from a robustness point of view, but I think there is a high potential for forgetting how to use them. Given all this, I think I will go with memcpy and see how it works out.

A small program that implements each of these three methods is in the file WriteToArray. It can be compiled with the command gcc -Wall WriteToArray.c.