Variations on a flexible array theme

January 31, 2010

Dan_Saks-January 31, 2010

Some months ago, I described how C++ run-time systems dynamically allocate and deallocate arrays whose elements are class objects with constructors and destructors.1 I also showed how you can implement similar behavior in C by writing your own array allocation and deallocation functions.

More recently, I presented a technique you can use to ensure that the elements in dynamically allocated arrays are properly aligned.2 Unfortunately, under some conditions, that technique wastes a little storage. This month, I'll show you a different, arguably better, approach to solving such alignment problems, which avoids that waste.

What I'm about to show you is not just about eliminating a few bytes of unnecessary padding. It's been my observation that too many embedded systems developers lay out varying length structures as arrays of (unsigned) characters and compute offsets using ad hoc pointer arithmetic and casts. The resulting code is usually very brittle--hard to get right and easy to break. I think you're much better off using structures that lay out your data as accurately as possible, and let the compiler do the alignment and padding. The resulting code will be easier to read and maintain.

Where we were
As before, I'll illustrate the problem by using arrays of widgets. In C++, you use an array new-expression such as:

pw = new widget [n];

to allocate an array with n properly initialized widgets. In C, you can implement an allocation function named new_widget_ array and call it in an expression such as:

pw = new_widget_array(n);

In C++, you use an array delete-expression such as:

delete [] pw;

to deallocate an array previously allocated by an array new-expression. In C, you can implement a deallocation function named delete_widget_array and call it in an expression such as:


Each call to delete_widget_ array passes only one argument: the base address of the allocated array. However, the function needs to know the array dimension as well. One way to solve this problem is for new_widget_array to stash the array dimension in a location just before each array that it allocates. Then delete_widget_array can use a little pointer arithmetic to locate and extract the array dimension residing just before the array to be deallocated.

The new_widget_array function uses the Standard C malloc function to allocate the dynamic storage. Each call to malloc must return a pointer that's aligned to the most strictly aligned object that could be placed in the allocated storage. If you allocate storage only for an array of widgets, the storage for the array elements will be properly aligned. However, as I explained in an earlier column, if you allocate storage for an array plus an additional integer to hold the array dimension, and you place that integer before rather than after the array, the array elements could be misaligned.

I suggested solving this problem by using a union defined as:

typedef union widget_array_header widget_array_header;
union widget_array_header
    size_t size;
    max_align_t unused;

where max_align_t is a type that's at least as strictly aligned as every other type.2 Instead of allocating storage for a size_t plus an array of widgets, the new_widget_array function should allocate storage for a widget_array_header plus the array, as shown in Figure 1.

Click on image to enlarge.

The size of the padding after the size_t member of the widget_array_header is the difference, if any, between sizeof(size_t) and sizeof(max_align_t).

Using the widget_array_header, the new_widget_ array function looks like the code in Listing 1.

Click on image to enlarge.

This approach avoids alignment errors. However, as I mentioned earlier, it might waste a little storage. In particular, if the alignment of widget is less than the alignment of max_align_t, the padding between the size_t object and the first widget array element in Figure 1 will be larger than necessary.

For example, suppose this code is compiled for a platform in which a size_t is a four-byte object with an alignment of four and a max_align_t is an eight-byte object with an alignment of eight. Then the size and alignment of the widget_array_header will be eight as well, and the first widget array element will have an offset at least eight bytes from the beginning of the allocated storage. However, if widget has an alignment of only four, forcing the first widget to an eight-byte boundary is overkill. It wastes four bytes.

< Previous
Page 1 of 3
Next >

Loading comments...