Table of Contents
mdarrays is a library to simplify using multidimensional arrays in C.
The three most important reasons to use mdarrays are:
easy to allocate arrays of pointers to pointer of any dimension
arrays are dynamically allocated
off-by-one errors in any dimension are guaranteed to be detected by a good memory checker such as Valgrind (http://valgrind.org).
Example code, showing creation of a 4D array of doubles, the dimension sizes being decided at run-time:
// uint is typedef to unsigned int void a_function(uint dimension1_size, uint dimension2_size, uint dimension3_size, uint dimension4_size) { double ****cc; cc = MDARRAYS_ALLOCATE(double, dimension1_size, dimension2_size, dimension3_size, dimension4_size); cc[1][2][1][3] = 5.0; MDARRAYS_FREE(cc); }
Two of the biggest pitfalls creating mathematical software in C are the lack of array bounds checking, and the difficulty in working with multidimensional arrays. Bounds checking is desirable during debugging, but lack of bounds checking is desirable after a program has been debugged, because the speed penalty for bounds checking is enormous. This package addresses these two problems.
Several solutions are currently available:
A C language interpreter would easily monitor run-time exceptions including bounds violations. EiC ( http://eic.sourceforge.net [link currently broken] ) is a freely available C interpreter. However, in the case of a large or complex project, this is not a good solution for bounds checking.
gcc has been patched to include bounds checking [jones] [brugge]. However, this does not catch all bounds violations for multidimensional arrays. Also, it is not yet part of the official gcc distribution.
Many different run-time memory checking schemes have been developed over the years. There are none that can detect all bounds violations for all multidimensional arrays, because basic multidimensional arrays in C are allocated as a single block of memory.
As of the writing of this paper (December 2003), I know of no other Free software that easily implements bounds checking for all dimensions of a multidimensional array in C.
This package adds bounds-checking to C programs by allocating arrays as pointers to pointers and using a memory checking program such as Valgrind. Unfortunately, Valgrind currently only works on i386 processors, so another memory checking library must be used for other architectures.
mdarrays has the following features:
provides complete bounds checking for multi-dimensional arrays
has very low overhead (normally < 10%) when the memory-checker isn't running
simplifies allocation of high-dimensional arrays
simplifies saving and loading high-dimensional arrays to files
simplifies passing high-dimensional arrays to functions and pointers
able to check bounds for an array by adding a simple macro function. This allows runtime bounds checking for some arrays even when the program is not running under the memory checker.
mdarrays works by allocating a chunk of memory large enough to hold a metadata structure plus the pointer array for the highest dimension. It then recurses through the array allocating as needed. The pointer returned to the user is moved forward to the start of the array, so the user can access the array like a normal array, but the metadata is still sitting there behind it. mdarrays functions move back and read the metadata, so that's how mdarrays can keep track of things like array dimensions and formatting styles. So if you don't use MDARRAYS_FREE() to free your arrays, you'll leak memory, even for 1D arrays.
In C, multidimensional arrays can be implemented in at least two ways:
The built-in multidimensional array mechanism:
int aa[3][4];
An array of pointers to arrays:
int **bb; (some code here to allocate storage for bb)
Both of these methods can access elements using index notation:
aa[1][1] = 4; bb[1][1] = 4;
However, from the compiler's point of view, they are quite different.
Assume aa and bb are defined as above. A "true" array (int aa[3][4]) is allocated a single block of memory before the program starts if the variable is global, or at the start of the function if the variable is local. Let's say you want to know the value of aa[1][2]. The compiler first has to find the memory location holding the value. The compiler knows that each "column" has 4 elements, so it finds the memory location from the base aa pointer using &aa + 1*4 + 2. Now you can probably see why a function which receives array parameters must know the dimensions of the array. If it didn't, the compiler wouldn't know how to calculate the offsets when accessing the array.
In the case of a "true" array, the compiler asks for a single block of memory, so a machine-code memory checker like Valgrind will not realize if you go past a bound, as long as the resulting pointer points within the block of memory for the whole array. For example aa[1][5] will not cause an error with Valgrind.
A "pointer" 2D array, on the other hand, is a pointer to a pointer. At the ** (pointer to pointer) level, bb points to the base of a 1D array of pointers. For example, bb[2] would be the third pointer in that array. bb[2] would point to a 1D array of integers. bb[2][1] would point to the second integer in that array.
In the case of a 2D "pointer" array, each "column" is a separately-allocated block of memory, so if any dimension is accessed out of bounds Valgrind will catch it.
Advantages of "true" arrays:
Faster
Simpler to allocate
Advantages of "pointer" arrays:
Bounds checking using a memory checker works for multidimensional arrays
Simpler to pass to functions and other pointers
Easier to change bounds at run-time
Multi-dimensional arrays can have odd sizes (they don't have to be rectagular)
The speed advantage of using "true" arrays can be significant (200%) in some cases, but a typical simplified test is included in this distribution as array_access_test.c. On my 366 Mhz Pentium II laptop, the speed difference was about 10%. Based on this result I decided to focus entirely on pointer arrays.
Because arrays based on pointers to pointers have a separate memory allocation for each element in all but the last dimension, an off-by-one error at the boundary of any dimension will be detected by a good runtime memory checker.
Table of Contents
returns a void pointer to a new array. See below for a description of type. Dimension sizes are the sizes of the first, second, and so on dimension.
same as MDARRAYS_ALLOCATE, but fill the array with value zero.
same as MDARRAYS_ALLOCATE, but fill the array with the value pointed to by value_pointer. value_pointer must point to the same type as the array, and this is not checked at compile-time or run-time!
free array cc.
The type parameter is actually used two ways internally by the library. The first is as a macro stringification, which means that the macro compares what you use in the type parameter to a list of strings. The strings allowed are: char, int, bool, unsigned int, uint, long int, float, double, long double, real. Internally the bool type is really unsigned char type. The second way is to use sizeof(type) to determine the allocation needed for each array element.
If you are creating an array of pointers to objects, use MDARRAYS_ALLOCATE_OBJECT, MDARRAYS_ALLOCATE_AND_CLEAR_OBJECT, MDARRAYS_ALLOCATE_AND_FILL_OBJECT, which are identical to the above routines except that they allow type to be anything (internally, mdarrays just creates an array of void pointers and allocates space based on what sizeof(type) says).
Return 1 if array is an allocated mdarray pointer array, 0 otherwise
Check that the indices given by ... are within bounds for array. Abort with error if not.
If all the elements in array1 are the same as the elements in array2, return true, otherwise return false. Use DM_*_EQUALS() functions for comparing floating types. Only works for basic types.
Save an mdarray to a file.
Load an array from a file into array.
Load a 2D array from a file, and creates a new 2D mdarray with the correct sizes. Type is the type such as "unsigned int" or "real", much like the type used in MDARRAYS_ALLOCATE(). Type is stringified by the preprocessor, so it is whitespace-sensitive (so don't put two spaces between "long" and "int" in "long int". The number of rows and columns loaded is returned in *rows and *columns.
Save a normal array to a file. type is one of the types from mdarrays.h such as MDARRAYS_DOUBLE_TYPE. sizes is an array of the dimension sizes. type_size should be "sizeof(type)". See the section called “Formatting” for info on the rest of the parameters.
Load a normal array from a file. type is one of the types from mdarrays.h such as MDARRAYS_DOUBLE_TYPE. sizes is an array of the dimension sizes.
For the special case of arrays to type gpointer, a direct memory image of each array element is written sequentially to a binary file. Note that this could case non-portability problems for several reasons.
All other arrays are represented as ASCII text numbers, with enough decimal places to hold their type. For all the file storage functions, the order of array output is the same as the order of array elements in memory for C. A simple example will probably make this clear. Assume a 2D array with dimensions [2][2]. The output will be:
aa[1][1] aa[1][2] aa[2][1] aa[2][2]
If you write a function to read these files, assume that the separator between each array element is "any amount of whitespace".
The printing functions are very similar to the save functions in the previous section, although they are modified to make arrays look better to humans. Also, the GPOINTER type is printed instead of writing a memory image like with the save functions. There are currently no non-mdarray print functions.
Print an mdarray to a file. Notice that a FILE* is used here, and not a filename as in the save functions. Normally you would just use stdout, but this gives you the option to save to a file if you want.
Print an mdarray to a file with tags (1D only).
If the default print or save formatting style is not what you want, use the style macro functions. For style macros, the following definitions apply:
the character to be placed between elements of the last index.
the character to the placed between elements of the next to last index. For example, with a 2d array, setting delimiter to space and line_delimiter to a line feed will create a square grid like you would expect.
These parameters mirror the printf type, width, and precision. For example, type=MDARRAYS_PRINTF_TYPE_f, width=4, precision=2 will end up printing with "%4.2f". MDARRAYS_PRINTF_TYPEs are in mdarrays.h.
The style functions are:
Set the print style to the default. The style defaults are located in mdarrays/mdarrays.h. When a new array is allocated, it is set to the default style, so this function is only needed if you have changed the style and want to revert back to defaults.
Same as MDARRAYS_SET_PRINT_STYLE_DEFAULTS except that it sets the save style instead of the print style.
Set the print styles for array.
Set the save styles for array.
void MDARRAYS_FOREACH(void *array, mdarrays_foreach_function foreach_function, void *user_data);
where mdarrays_foreach_function is defined:
typedef void (*mdarrays_foreach_function)(void *array, uint *indices, void *user_data);
Call the user-defined foreach_function once for each element of array. user_data is passed directly to foreach_function. Note that foreach_function should not assume anything about the order it will receive the elements of the array.
An example using MDARRAYS_FOREACH:
void foreach_function(void *array, uint *indices, void *user_data) { // Assign the value pointed to by user_data for all elements where the // array indices are the same for both dimensions if (indices[0] == indices[1]) array[indices[0]][indices[0]] = *((double *)user_data); } void main(void) { double **aa; double value = 3; aa = (double **)MDARRAYS_ALLOCATE(double, 5, 6); MDARRAYS_FOREACH(aa, foreach_function, &value); }