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.

In an earlier entry, we developed a generic way of creating and looping through arrays in C. Arrays are very useful, but for some things linked lists are better. So lets develop some general tools for them.

Decisions

First, a design decision must be made. Each element in the list needs a pointer to the next element, and optionally a pointer to the previous one. Where should these pointers reside? There are a couple of options. The most obvious approach is to add next and previous pointers to whatever structure is used to store your data. This leads to a structure like the figure.

Data Structures for Linked Lists. Direct Approach.

We have a generic container (in green). It stores the number of elements in the list, along with a pointer to the first and last elements. It is up to the user to create the structure that holds the data for each element of the list. And this structure must include the prev and next pointers. This approach is conceptually simple and provides direct access to the data. However, it lacks generality. If you want to make a list containing elements based on a structure from another library, you are out of luck, unless they contain the prev and next pointers. Also, what if you want to store these data items in multiple lists? Can’t be done with a single set of next and prev pointers.

A way around this problem is to add a level of indirection to the scheme. The figure below shows the idea. We now have two predefined structures, one for the list (green) and a new one for a generic list element (blue).

Data Structures for Linked Lists. Indirect Approach.

Now a list can store items of any data type. It could even contain different structures. This generality comes at the price of more complex data access. To retrieve an item from the list, you must do something like:

mylist.pFirst->ListEl->Data1
(green) (blue) (pink)

Instead of

mylist.pFirst->Data1
(green) (pink)

This is one extra level of indirection, compared to the first scheme. It makes the code less readable, is more error prone and is probably slower as well.

Since we are going for generality, we will use the indirect approach, and see how it works.

Another design decision is should the list be linear or circular. In other words, should the next pointer in the last element be set to NULL or to the first element? We’ll keep it simple and create a linear list

Implementation

Here are what our two generic structures look like:

//Generic list Element
struct lelement {
    LElement *next;
    LElement *prev;
    void *data;
};

//Generic List Structure
struct llist {
    int NumEl;   //Number of elements in list
    LElement *pFirst;  //Ptr to first element in list
    LElement *pLast;   //Ptr to last element in list
};

The structure for a generic element in the list contains three pointers: next and prev needed for the list, and data which points to the data we are storing. The container structure holds the number of elements in the list, as well as pointers to the first and last elements.

To create an empty list, we just initialize the items in the container:

void CreateList(LList *list)
{
    list->NumEl = 0;
    list->pFirst = NULL;
    list->pLast = NULL;
}

We assume the memory was allocated elsewhere. An element can be added to the end of the list by adjusting the pointers at the end of the list and in the new element. The code below shows an implementation of this.

LElement *AddToList(void *item, LList *list)
{
    //check inputs
    assert(item!=NULL); assert(list!=NULL);
    //Create generic element to hold item ptr
    LElement *NewEl;
    NewEl = (LElement *)malloc(sizeof(NewEl));  //create generic element
    assert(NewEl != NULL);
    list->NumEl = list->NumEl + 1;
    NewEl->data = item;
    if (list->NumEl == 1)
    {
      list->pFirst = NewEl;
      NewEl->prev = NULL;
      NewEl->next = NULL;
    }
    else
    {
      NewEl->prev = list->pLast;
      NewEl->next = NULL;
      list->pLast->next = NewEl;
    }
    list->pLast = NewEl;
    return NewEl;
}

It is also to be able to add data at the beginning or middle of the list. This can be done in a similar way, although there are a few more details to worry about. To remove an item from the list you simply bypass it, then free the memory. Because we don’t know if the data is stored in multiple lists, it is never freed, only the generic list element.

Looping

To loop through a linked list, we can create a macro similar to the one for general arrays:

#define FOR_EACH(item_ptr, list) \
     for (ListEl = myList.pFirst; ListEl != NULL; ListEl=ListEl->next)

This macro creates a for loop that initializes ListEl at the first value. It then increments this value at the end of each pass through the loop until the end of the loop is reached. This makes it handy for looping through an already existing list. It is not very helpful in looping through a list under construction.

Summing up

The list code can be found here: ListType.c. It can be compiled with the command

gcc -Wall ListType.c

In creating this example, I hit many snags. It is very easy to make a mistake when rearranging the pointers for an insertion. Then the test code would try to write to a NULL pointer and crash! In comparison, the array list was much easier to develop. If I was going to use linked lists for general storage like this, I would want a well tested library, rather than just winging it.

In numerical computations, we frequently have lists of objects we must deal with. In C, there are two types of containers commonly used for holding these lists: arrays and linked lists. Arrays are good for fast, random access to the list. However, they are a few drawbacks. It is easy to write outside of array bounds and crash the code. It is hard to add elements to the middle of the list. And if you need more space than you allocated, you need to allocate a new larger block of memory and copy everything over.

Linked lists are good for frequently changing lists. You can easily insert an element anywhere in the list. Since memory is allocated as each element is created, there is no problem running out of room. However, cycling through the list can be slower, since the elements can be scattered all over in memory, and it is time consuming to retrieve the ith element of a list. Numerical folks tend to favor arrays, but both tools are useful.

Here we will create a general array and a macro for looping through it. This will hopefully be useful for reducing coding errors.

Array Structure

Lets begin by creating a general array structure, and some functions to access it.

A generic structure, that can hold arrays of anything might look like:

typedef struct
{
    long NumEl;      //number of elements
    size_t ElSize;   //size of each element
    void *Data;      //ptr to data
} AList;

This structure stores the size of the array, the size of each item in the array and a pointer to the first element in the array. Knowing the number of elements in the array is useful to staying in array bounds. The size is important for allocating memory and when we try looping. Notice that Data is a pointer to void. That is because we don’t know what type of array we will have. It could be intergers, floats or some arbitrary structure.

A new ArrayList could be created like so:

void CreateList(AList *list, long NumEl, size_t ElSize)
{
    list->NumEl = NumEl;
    list->ElSize = ElSize;
    list->Data = (void *)malloc((NumEl + 1) * ElSize);
    if (list->Data == NULL)
        printf ("Error in CreateList: Can't allocate memory");
}

To destroy a list, we must deallocate the memory for the data array. The DestroyList function does this:

void DestroyList(AList *list)
{
    if (list->Data != NULL)
    {
        free(list->Data);
        list->Data = NULL;
    }
}

One can access an element in the array with

void *GetItem(AList list, long index)
{
    if (index >= 0 || index < list.NumEl)
        {return list.Data + index * list.ElSize;}
    else
    {
        printf ("Wrting outside array bounds");
        return NULL;
    }
}

This may look a little strange. If Data is a pointer to an array why not access the elements in the normal fashion with [] brackets? The problem is that we don’t what ahead of time what type of data is stored in the array. For something like list.Data[5] to work, the compiler must know the size of each element, so it can calculate the distance (in memory) from the starting point. Since it doesn’t know that, we do the calculation for it.

One could also envision a SetItem routine, but this would be very dependent on the nature of the element being stored. So it is best to let the user set each element as it makes sense to do so.

For Each loop

One of the first lessons I learned in programming was: Don’t write outside array bounds! Its an important lesson, and a simple one, yet I still occasionally mess up. Why? Because its easy. Here is a very simple way to screw up in C:

int i; float myArray[10]
for i=0; i<=10; i++)
{
  //some code
}

In C, arrays start at index 0, so the above declaration runs from myArray[0] to myArray[9]. Yet our loop runs to myArray[10]. Trouble!

Some languages handle the looping details for you. Consider this equivalent code in Python:

myList = [1,4,2,3,5,6,3,8,5,9]
for each item in myList:
    #some code

The For statement knows there are ten items in myList and loops over them. Each pass through the loop, it takes the current item in the list and assigns it to Item. You can then do what you want with it.

This type of high level construct frees us to focus on the job at hand while leaving the bookkeeping to the computer. Unfortunately, in the case of Python, this comes at the cost of speed.

Lets try to emulate the For statement in Python. Consider the following macro:

#define FOR_EACH(index, item_ptr, list) \
     item_ptr=list.Data; \
     for (index=0; index

The FOR_EACH macro has three arguments: an index, a pointer to the an item in the array and the list structure. Like the Python equivalent, with each pass through the loop, the item pointer is set to point to the current position in the array. To find that position, we need to know the size of the elements, as mentioned above. With a macro like this, it is impossible to write outside array bounds. Because the compiler substitutes the code in at compile time, the performance should be the same as hand coding the loop. The best of both worlds!

Trying it out

Lets try a simple example to make sure it is working. Here is a very simple structure:

typedef struct   //toy structure to play with
{
    int val1;
    double val2;
} ElType;

To loop through a list, we first create the list, then call the FOR_EACH macro. We must declare an index variable and a pointer to an element, but don’t need to initialize these. Here is the code:

int main()
{
	int i; AList mylist;
	ElType myEl; ElType *pMyEl;

	CreateList(&mylist, 100, sizeof(myEl));
	FOR_EACH(i, pMyEl, mylist)
	{
		pMyEl->val1 = i;
		pMyEl->val2 = (double)(2.*i);
		printf("i = %d, val1 = %d, val2 = %f\n", i, pMyEl->val1, pMyEl->val2);
	}
	DestroyList(&mylist);
	return 0;
}

A nice feature of this approach is one could later change the array to be 200 elements and all the loops will still work fine.

Download code here: Array Code