Pat LaBrocca is the author of ReCalc(TM), a set of rational expression calculators that never give answers (well, almost never), and run identically on PCs, Macintoshes and Apples. He has a BS and MA in Chemistry and teaches computer science at Peter Rouget Middle School 88 in Brooklyn, NY. You can contact him at plabrocc@nycenet.edu.
The size of declared arrays in C is fixed at compile time. If you declare an array in C, you must ensure that it is big enough to hold the maximum number of elements that the program will need to store. As a result, unused memory is often tied up during a large portion of the program's execution. Therefore, a useful feature to add to C is the ability to allocate and deallocate two-dimensional (2-D) arrays as needed. Naturally, you would prefer the feature to handle all the details, and work in a convenient way. In this article I develop a function that lets you allocate 2-D arrays at run time. When they are no longer needed, they can be removed by calling the standard library function free.
I start by examining some characteristics of regular 2-D arrays to determine those features I'd like my dynamic arrays to have. Starting with these characteristics is important because I want my dynamic arrays to work just like conventional arrays, and when they can't, I'd like to be aware of the differences. I present a function, dyn2darray, that allocates 2-D arrays dynamically. Finally, I present several examples of allocating arrays, and use a macro, Dyn2dArray, in a demonstration program, MAGIC.EXE, which solves arbitrary magic square puzzles. I also present a program to push Dyn2dArray to its limit.
Two-Dimensional Arrays in C
When you declare a two-dimensional (2-D) array, A, in C, such as:
int A[5][4];you specify 1) a type for the array elements, 2) the number of dimensions, and 3) the number of items in each dimension. The type of A is array of arrays of ints.The numbers in the brackets are called repetition counts. They must evaluate to constant expressions, that is, their values must be fixed at compile time. This need for fixed repetition counts is the restriction I want to eliminate. The first repetition count specifies the number of rows in the array. The second specifies the number of columns (the length of a row). The number of elements in a 2-D array is the number of rows times the number of columns, which is often referred to as the array's rank. The size of an array in bytes, then, is its rank times the size of an element. Array A's rank is 20, and its size is 40 (assuming sizeof( int ) == 2). You determine the size of an array by applying the sizeof operator to the array's name. In my example, sizeof( A ) yields 40.
The first repetition count is required in the definition of an array. It is used to calculate how much memory needs to be allotted for the array elements. It isn't used again by the C compiler. It may be omitted from subsequent declarations. The second repetition count is always required. It is used to evaluate expressions like A [1] [2].
2-D arrays are set up row by row, progressing from lower to higher contiguous memory locations. Even though the elements are stored sequentially, we usually think of them as being arranged in a rectangular grid or matrix. When the array elements are accessed in the order they appear in memory, the right subscript varies fastest. Sometimes this layout is referred to as row-major order.
In an expression, an array name is converted to a pointer. It has the type of the first item of the array. In the previous example, A is a pointer to an array of four ints. A[i] is a pointer to int — in this case, the first element of the ith row. Finally, A[i][j] is an int whose value is stored at the jth position in the ith row.
Arrays or pointers followed by numbers in brackets are subscript expressions. (The subscript operator is the pair of brackets.) When C expands a subscript expression it uses pointer arithmetic. Pointer arithmetic involves the automatic scaling of integral values to the size of the pointed-to type. For example, if p is a pointer to int, then in the expression
p = p + 3six (i.e., 3 * sizeof( int )) is added to the value of p; in other words, the new value of p points three ints beyond the original value. The value of a subscript expression is either another array or pointer, or an object of the type specified in the declaration.The value of the int stored at, say, A[2][3] is
*( *(A + 2) + 3 )The pointer arithmetic C performs goes like this: A is converted to a pointer to an array of four ints. The integral value two is multiplied by the size of an array of four ints (4 * sizeof( int )) and added to A. The subexpression (A + 2) is a pointer to the third array of four ints. *(A + 2) is a pointer to int. Three multiplied by sizeof( int ) is added to this pointer, resulting in a pointer to the fourth int element, ( *(A + 2) + 3 ). Finally, dereferencing this last pointer yields the int value stored in the fourth position of the third row. Later I use these steps to build a 2-D array from pointers.To pass a 2-D array to a function, it must be declared as a parameter, as in:
void func1( int ap[][4] ) { ... }or, equivalently,
void func2( int (*ap)[4]) { ... }In either case, ap is a pointer variable, not an array. Since no new storage is allocated for the array by the function definition, the first repetition count is optional. The second repetition count is required for evaluating subscript expressions. func1 and func2 can take array arguments with any number of rows, but each row must have four columns.
2-D Arrays Using Pointers
What is the pointer equivalent of a 2-D array? Since array names are converted to pointers in expressions, the pointer equivalent must have the same type. As I previously discussed, arrays are converted to pointers to the first object in the array. In my example, the equivalent pointer is a pointer to an array of four ints. You declare such a pointer by writing
int (*ap) [4];The parentheses are necessary. Without them ap is an array of four pointers to int. The bracketed 4 tells C how long a row is, the piece of information that C uses to adjust ap by the right amount when expanding subscript expressions. The statement
ap = A;points ap at the first row of A. After the assignment, ap may be subscripted exactly as if it had been declared as an array. In fact, the major difference between A and ap in most expressions is that ap is a variable and A becomes a constant address.If, instead of assigning an array address to ap, I use malloc to allocate the same amount of memory, and assign that address to ap:
ap = malloc( ... );then an expression like
ap[2][1] = 4works fine. ap isn't the pointer I want, though, because the number in the declaration still has to be a constant expression at compile-time.In the expansion of the subscript expression above, the dereferencing operator is applied twice. The two dereference operations lead me to try to use a pointer to a pointer, such as:
int **p;The compiler issues a warning if I try
p = A; /* compiler warning */because p and A have different types. Using malloc, I can assign a block of memory to p, as I did above:
p = malloc( ... );and C will let me subscript p once or twice.Unfortunately, subscripting p yields garbage. Referring again to the expansion of the subscript expression above, reveals why. C interprets p[i] as *(p + i). What pointer is being dereferenced? No pointer! (p + i) is a location within the area where the array's elements are supposed to be. Why does it work for A but not for p? It doesn't work for p because arrays and pointers are not the same. C treats arrays in a special way. Information about arrays is retained internally by C; pointers don't have access to such information, even when they are assigned the address of a conventional array. So, to manage my own arrays, I need to set up and keep track of the pointers C expects to find when expanding subscript expressions.
From the previous discussion, you can see that p[0] is interpreted as a pointer to the first array of ints, p[1] as a pointer to the second array of ints, and so on, for each of the five rows of my example. I need to allocate storage for five pointers to int. If I assign the start of this block of memory to p, as in
p = malloc( ... );I get a warning (in C++) because I'm assigning a void * to an int **, but I can suppress the warning with a cast. Now p[0], p[1], ..., p[n] reference void-pointer-sized portions of allocated memory.In this block of memory I store the pointers C needs to evaluate subscript expressions like p[2][3]. These pointers are the addresses of each of the rows of the array. First, though, I have to allocate some memory for them to point at. This time I need a block that is the actual size of the array.
p[0] = malloc( ... )Then I calculate offsets into this memory that correspond to the start of each row and assign their addresses to the pointers in the first block of memory. To summarize, I have a pointer to pointer to int, p, that points to an array of pointers to int; each of these pointers to int, p[i], refers to the first element of an array of ints, p[i][0].What happens when I write p[2][3] now? Since p is an int **, C allows me to subscript it twice. (p + 2) is now a location in memory that I allocated, and where I stored the address of the third row of my dynamic array. If I follow the steps above for expanding subscript expression I get
*(*p + 2) + 3 )This expression works for my pointer to pointer because I carefully calculated and assigned addresses in just the sequence C uses to expand subscript expressions. For conventional arrays the intermediate pointers are implied. What I've done is manage them explicitly. Now I am ready to present my function.
Allocation and Memory Layout
My dynamic array allocation function is called dyn2darray. It returns a pointer to pointer to void (void **). I pass it the number of rows and columns I want, and the size of one element. The function declaration appears as:
void **dyn2darray( unsigned row, unsigned col, unsigned el_size )This declaration contains the same information I would give the compiler in a normal array definition, although it is in a somewhat different form. Later, I'll use a preprocessor macro to make it prettier.Instead of allocating separate blocks of memory for the pointers and the array elements, I allocate just one block, and use the block as a mixed data structure. The memory block consists of an array of pointers followed by an array of elements. I also add a feature to my dynamic arrays to make them a little more convenient to use. A disadvantage of conventional arrays as they are typically defined is that they don't carry any size information. When the program passes such an array to a function,
void f( int array[][5] ) { ... }the program must specify the length of the array's rows in the function's declaration. To avoid this limitation, I allocate a few extra bytes and store the number of rows and columns with the array. Figure 1 shows the memory layout of my dynamic arrays.
How dyn2darray Works
dyn2darray is shown in Listing 1. In the call to calloc, I allocate storage for the pointers, for the array elements, and two unsigned ints to hold the repetition counts. I compute the storage requirements for each of these components and sum them together to form the first argument to calloc. The second argument to calloc is size of (char), which is guaranteed to be 1 specifies the size of a basic allocation unit, while the first specifies how many units to allocate. Therefore, I am simulating the allocation of an array of bytes, though I intend to use the memory as a mixed data structure. This practice might present a portability problem because of differing storage boundary requirements; however, as dyn2darray is defined, I need make only one call to calloc, and have one relatively neat package to deal with.void **arr receives the pointer returned from calloc. I check whether the allocation succeeds and return NULL if it doesn't. This allocation technique parallels the behavior of the malloc group of functions. I use calloc because I want to zero the arrays; it's easy to switch to malloc if the situation warrants it.
I make p point just past the array of pointers in the memory block by assigning it the sum of two values: the start address of the block, arr, and the size of the array of pointers, row * sizeof( void * ). The cast on arr is necessary to defeat the scaling process which would be applied by normal pointer arithmetic. I want to store the number of rows and columns just before the actual array elements (so they're easy to find and out of the way). First I cast p to a pointer to unsigned, then store row to the memory block through the recast pointer. Second, to move p past the newly stored value of row I add sizeof( unsigned ) to p. (A cast is not necessary here because p is a pointer to char — there is no pointer arithmetic to contend with.) I repeat these two steps to store col. Both the numbers of rows and columns are now tucked away in arr as unsigned ints, and p points to the first byte of memory that will hold the array elements.
Next, the for loop assigns the addresses of each row of elements to the corresponding pointer, arr[c]. The offset added to p is the length, in bytes, of a row, (col * el_size), times the row number, c. The last step is to return arr, which points to the whole structure.
Using Dyn2dArray
The header file DYN2DARR.H (Listing 2) contains the prototype for dyn2darray and several macros. Include the header when you want to allocate dynamic two-dimensional (D2D) arrays.In the source file, start by declaring pointers to pointers for each D2D array you want. Here are some examples.
/* D2D arrays of ... */ double **DDa; /* double */ double * **DDap; /* pointers-to-double */ typedef struct S { ... } SS; struct S **Sa; /* struct S */ SS **Sal; /* typedef SS */ struct S * **Sap /* pointers-to-struct S */I make calling dyn2darray a little easier by wrapping it in a macro, Dyn2dArray. The macro automatically calculates the size of the array elements. Using it allows you to write the type name directly in the function call. For a D2D array of double write
DDa = Dyn2dArray( 3, 8, double );and for a D2D array of pointers to double
DDap = Dyn2dArray( 4,7,double * );Setting one of the asterisks a little off from the other two in the declaration looks just odd enough to remind you you're doing something different. (Don't accidentally fix it.) You can create D2D arrays for fundamental, aggregate, and user-defined types, as I have shown in the preceding sample declarations. Remember to check for a NULL return value. After allocating the D2D array, you can forget that you're using a pointer to pointer; you use it like a regular array, with a couple of exceptions (explained later). When you're done with the array, you can reuse the array name for a different size array by calling the standard library function free, and then allocating a new D2D array with Dyn2dArray. For an example see TEST.C in Listing 4.
Passing D2D Arrays
To pass D2D arrays to a function, declare the function's argument as a pointer to pointer to the array element's type. For example,
void f( int **d ) { ... }can be passed any D2D array of ints.
Other Useful Macros
The macro Dyn2dRows returns the number of rows in the array. It finds the first array element, backs up by four bytes, and accesses an unsigned int. A[0] is the address of the first byte of the element array. The cast to unsigned * scales the 2 to sizeof( unsigned * ) and, more important, causes the dereference operator to treat its operand as an unsigned int, rather than as an element of the type specified in the original declaration. Similarly, Dyn2dCols returns the number of columns. Dyn2dRows and Dyn2dCols save you the trouble of having to pass the number of rows and columns to functions.
Some Cautions
The names of D2D arrays are variables. You can change them by assignment, or by applying the increment or decrement operators. (By contrast, C generates an error if you try to do the same to a conventional array.) But if you don't preserve the original pointer to the array you'll be unable to access the array or free it properly when you're done with it.For conventional arrays, sizeof( A ) yields the size of the whole array. But D2D array names are pointer variables; you don't have direct access to the size of the whole array. The formula,
Dyn2dRows( A ) * Dyn2dCols( A ) * sizeof( **A )yields the number of bytes required by the array elements, but not the total size of the D2D array. If you need the size of the whole D2D array you can write a macro; the information you need is in the source code.Table 1 contains a comparison of the characteristics of a regular two-dimensional array and a D2D array.
Magic Squares
Pointers are often used to access an array's elements sequentially because they're so convenient to increment and decrement. Subscripting is usually more convenient when you need to access elements out of order. The demonstration program, MAGIC.C (See Listing 3) uses D2D arrays to hold the solutions to magic square puzzles. The algorithm hops around the array as it decides where to place numbers.MAGIC.EXE takes an odd positive integer, n, as a command-line argument, which it interprets as the length of one side of a magic square. MAGIC.EXE then inserts the numbers from 1 to n * n, in the square's cells, so that each row, column, and diagonal adds up to the same number. MAGIC.EXE prints the solution to the screen, along with the "magic" total.
Magic number puzzles are good examples of when D2D arrays come in handy. (I've also used D2D arrays for multiplying matrices, evaluating determinants, and determining LCDs and GCDs.) Progressing to more challenging puzzles requires larger and larger arrays to hold the solutions.
MAGIC.EXE starts by allocating a D2D array of ints, arr, one cell wider and longer than requested. This extra space allows magic to move off the magic square but stay within the bounds of the array. The function magic solves the puzzle. magic takes a pointer to pointer to int as a parameter.
The solution to a magic square is as follows. Put 1 in the middle cell of the top row. Move up and to the left one box. If you run off the top or side of the magic square, wrap around to the corresponding cell on the opposite side of the square. If you arrive at an empty cell, put the next number from the sequence 1 .. n * n in the cell. If the cell already contains a number, move one cell right and down, and then down another cell. Put the next number from the sequence in this cell and then continue up and left, depositing the next number in each cell until you run out of cells (or patience).
In magic, count keeps track of which number in the sequence it has reached. r starts as 1, for the first row, and c starts as (size + 1) / 2, for the middle cell of the row. mag[r][c] gets count. To move up and left, decrement r and c. If mag[r][c] doesn't equal zero (there's a number there already), or if both r and c equal zero (a special case, you're in the upper left hand corner of the square), move back a column, ++c, and down two rows, r += 2. Otherwise, if r or c equal zero, wrap around by setting r or c to size. Finally, put count in mag[r][c] and go to the top of the loop.
show_mag prints the solution to the screen making use of some of the features I built into my D2D arrays. Since show_mag accepts a pointer to pointer to int, any size array can be passed to it. Dyn2dRows and Dyn2dCols are used for the limits in the two for loops. You don't have to worry about limits because the D2D arrays carry their bounds with them. show_mag also totals up the "magic" number and displays it.
The call to free isn't necessary in MAGIC.EXE, since the program ends, but it demonstrates how a D2D array is cleaned up.
TEST. C (See Listing 4) is a torture test for D2D arrays. (It's also torture to watch it run.) It allocates and frees lots of D2D arrays, and checks for leaky memory.
The outer loop varies the first repetition count from one to nine, and the next loop varies the second repetition count from ten to one. This produces a complete set of D2D arrays, with every combination of repetition counts possible up to the value of high. Increase high to add further stress to the system.
For each set of repetition counts, a D2D array of structures and pointers to structures is allocated. If an allocation fails, an error message is displayed and the program halts. You can examine the last couple of lines to see the condition that caused the failure. To force a failure, increase any variable that causes an increase in the amount of memory requested. (If you remove the comment from the array of double variable in the structure declaration you'll succeed in failing.)
The first pair of inner loops assigns a value to the double member, dd, of each D2D array element. It's helpful to assign the sum of the loop indices to the current element, because then you always know what its value should be. Said another way, an element's value will equal the sum of its subscripts. This technique has the further advantage of producing a distinctive pattern when printed out in row-major order.
The next pair of loops assigns the addresses of the structures in d, to the pointers to structures in pd. The final pair of loops prints values accessed through the pointers in pd to the screen. If the sum of the loop indices ever does not equal the value stored in the corresponding element, the program halts.
Once the program has written to and read all of the elements, it releases both of the D2D arrays by calls to free.
The amount of memory available after freeing the D2D arrays should be constant while the program runs. To check this I make two calls to _memmax per pair of repetition counts. _memmax is a nonstandard function in the Microsoft C run-time library. It returns the size of the largest contiguous memory block available from the near heap. The first call is made while no D2D arrays are allocated. The return values should be the same for each iteration. (The difference between the first and second call is because of overhead incurred with the first call to calloc.) After allocating a D2D array _memmax returns a smaller number, whose size varies with the magnitude of the product of the repetition counts.
Compiling
Listing 5 contains a MAKEFILE for Microsoft's NMAKE.EXE. It should work with other versions of make with few or no changes. I've compiled various versions of DYN2DARR.C with Microsoft C 6.x, C/C++ 7.0, and Visual C++ 1.0, with the C/C++ compilers from Zortech and Borland, and Symantec THINK C 5.0 for Macintosh.
Conclusion
You can dynamically allocate 2-D arrays in C; it just takes a little extra work. I have presented a way to dynamically allocate 2-D arrays, pass them to functions, and use them in a program. Once you get past the preliminaries, you may find that these arrays behave much like their more conventional counterparts in C.