The previous two articles introduced C pointers and showed how they related to arrays and strings. The direct equivalence *n to n[0] meant that the benefits of dynamic memory allocation could be had without the need to abandon the normal mathematical conventions. This part shows the mechanics of extending dynamic memory allocation to two dimensional arrays.
The code to be used, TUT31.C. is available from File Area 16 on the BBS.
The basic relationship is
*(n+i) = n[i]for a one dimensional array
*(*(n+i)+j) =n[i][j]for a two dimensional array
*(*(*(n+i)+j)+k) =n[i][j][k]for a three dimensional array etc
We will restrict the discussion of dynamic memory allocation to the two dimensional case. What we need is a pointer to a one dimensional array where the elements of that array are themselves pointers to one dimensional arrays. Diagramatically it will look like the diagram below.
The code to perform this operation is taken from an article by Paul Anderson - C Multidimensional Arrays at Run Time. Dr. Dobb's Journal Aug 1989.
Say you require an array with 5 rows each of 3 columns and where each element is to contain a single character, ie type char. The declaration is:
char **n;
/* n will be a two dimensional array n[ ][ ] */
and the function call would be as follows:
n = dim2(5,3,sizeof(char));
{
int i; /* A */
char **prow, *pdata; /* B */
pdata = (char *) calloc(row*column, size); /* C */
if (pdata == (char *)NULL)
{
fprintf(stderr, " No memory available for data\n"); /* D */
exit(1);
}
prow = (char **) malloc(row*sizeof(char *)); /* E */
if (prow == (char **)NULL)
{
fprintf(stderr, " No memory available for row pointers\n");
exit(1);
}
for (i=0; i<row; i++) /* F */
{
prow[i] = pdata; /* Store address in i'th pointer. */ /* G */
pdata += size*column; /* Increment address. */ /* H */
}
return prow; /* I */
}
where the function dim2() is as defined below -
char **dim2(int row, int column, unsigned size) /* Creates 2D array */Let us examine the function to see what is happening.
The input parameters are row, column and size. In this example row=5, column=3 and size=1.
At A a local variable i is declared. This will be used later as an index.
At B a pointer to a pointer prow is declared. This will be used as the return value for the function. Also a pointer pdata is declared. This will be used to hold the starting address of the memory block which will contain the 15 (5*3*1) bytes.
At C the call to the calloc function allocates row*column*size bytes with the starting address in variable pdata. If there is insufficient memory available calloc() returns a NULL and the message at D is printed before the exit from the program.
So the situation at the moment is that we have a pointer variable pdata holding the address of the first byte of a block of memory. We must now set up another block of memory to hold an array of pointers to the rows, as in the diagram above. This is done at E. The memory required will be 'row' elements each of which will contain the number of bytes needed for a pointer to char. (You may remember from Part 1 that for the Borland C++ compiler pointers to char, int and float all occupied 4 bytes.) So if we know we are going to use the Borland C++ compiler we could simply malloc(row*4) to obtain the correct amount of memory. As before it is better practice to use the sizeof function with the correct type which in this case is char * (ie char pointer). As it happens for this exercise I used an old version of Borland Turbo C 1.5. It allocates 2 bytes for the pointers, and using malloc(row*4) would have been a serious error.
Again there will be a check to see if memory is available.
Finally it is necessary to load the array of pointers with the correct addresses i.e. with the starting addresses of each row of the two dimensional array. This is done in the loop F which steps through the range from 0 to row-1. At G, the first time round prow[0] is set to the value in pdata i.e. the starting address of the large memory block which is also the start of the first row. Then at H the variable pdata is incremented by the number of bytes in a row i.e. by column*size. This new address value is put in prow[1] and so on ...
Finally at I the return is via the pointer to a pointer variable prow which holds the starting address for the array of pointers.
A full example will give the details. Note that in this case instead of a character array as in the discussion above, the array is to hold integers and the cast (int **) to the function call is the only change needed in the coding.
Consider the program TUT31.C below.
/* ANSI C code */ /* TUT31.C for use with Part 3 of 16 Bits article.*/ #includeThe output is :-#include #include char **dim2(int, int, unsigned); /* Creates 2D array */ void free2(char **); main(void) { int i, j, **pp; pp = (int **) dim2(5,3,sizeof(int)); /* To prove that the code works insert here the code from example TUT23.C in Part 2. This, as they say in all the good textbooks, is left as an exercise for the student. */ free2(pp); /* Release the memory */ return 0; } char **dim2(int row, int column, unsigned size) /* Creates 2D array */ { int i; char **prow, *pdata; printf("row = %d, column = %d, size = %d\n",row,column,size); pdata = (char *) calloc(row*column, size); if (pdata == (char *)NULL) { fprintf(stderr, " No memory available for ( data\n"); exit(1); } printf("pdata is located at %u and has value ( %u\n", &pdata, pdata); prow = (char **) malloc(row*sizeof(char *)); if (prow == (char **)NULL) { fprintf(stderr, " No memory available for row ( pointers\n"); exit(1); } printf("prow is located at %u and has value ( %u\n\n", &prow, prow); for (i=0; i<row; i++) { prow[i] = pdata; /* Store address in i'th pointer. */ printf("Row pointer #%d at location %u has ( value %u\n", i, &prow[i], prow[i]); pdata += size*column; /* Increment address. */ } return prow; } /* -----------------------------------------------*/ void free2(char **pa) /* Frees 2D heap storage. */ { /* NB The order of the following statements is significant.*/ free(*pa); /* Free the data. */ free(pa); /* Free pointer to row pointers. */ } /* ---------------------------------------------- */
row = 5, column = 3, size = 2 pdata is located at 65482 and has value 1940 prow is located at 65480 and has value 1974 Row pointer #0 at location 1974 has value 1940 Row pointer #1 at location 1976 has value 1946 Row pointer #2 at location 1978 has value 1952 Row pointer #3 at location 1980 has value 1958 Row pointer #4 at location 1982 has value 1964A diagram will show links between memory locations
Address Content Symbolic name
1940/1 0 n[0][0]
1942/3 0 n[0][1]
1944/5 0 n[0][2]
1946/7 0 n[1][0]
1948/9 0 n[1][1]
1950/1 0 n[1][2]
1952/3 0 n[2][0]
1954/5 0 n[2][1]
1956/7 0 n[2][2]
1958/9 0 n[3][0]
1960/1 0 n[3][1]
1962/3 0 n[3][2]
1964/5 0 n[4][0]
1966/7 0 n[4][1]
1968/9 0 n[4][2]
1974/5 1940 prow[0]
1976/7 1946 prow[1]
1978/9 1952 prow[2]
1980/1 1958 prow[3]
1982/3 1964 prow[4]
65480/1 1974 prow
65482/2 1940 pdata
Finally lets see how it works in practice. Consider the steps to locate the array position n[3][2]
Using the relationship
n[i][j] = *(*(n+i)+j)n (prow in the function) has the value 1974, i=3 and j=2 AND for pointers 2 bytes are required so
(n+i) = 1974 + 2*3 = 1980 *(n+i) = *(1980) = 1958 *(1958+j) = *(1958 + 2*2) = *(1962)and you will see from the table above that the address 1962 is the array position n[3][2] as required. That concludes this three part article. I would draw your attention again to the excellent article in Dr Dobbs Journal by Paul Anderson noted earlier. His article shows how to extend the code to generate three dimensional arrays.
Pointers are an intrinsic part of C and pointer misuse is a frequent problem. There are ways to erect barriers to trap some pointer problems and I will cover these topics in a future article. Some languages have pointers which do not have the full functionallity of the C pointer. A good example is the latest version of Fortran (Fortran 90) where flexibility is traded for safety.