Data Pointers and Arrays

When a declaration for a data object is made, the compiler will allocate memory space for it. For the compound data types this memory space may be in several disjoint but related pieces. This part of the tutorial will show how the data object is organized in memory for data objects involving only arrays and pointers, as this is frequently helpful in visualizing how to use data objects. There is no major difference from the viewpoint of data structure for any of the other fundamental types, other than the size of the fundamental type. This will keep the number of needed examples within bounds. Of course structs and unions are important parts of the language, but they would only add fields to the memory allocation diagrams.

Example 1:

A simple declaration, such as:

	int a;

would yield the following memory allocation diagram:

               +------+
    &a         |  a   |
    ---------->+======+
    int (*)    | int  |
               +------+

               +------+
    &a         |  a   |
    ---------->+======+
    int (*)    | int  |
               +------+

where the top half off the "split box" shows the identifier, a in this example, and the lower half shows the abstract type of that identifier, int in this example.

The arrow to the left, as all arrows in these diagrams, represents a pointer; in this case it is the address of the object a whose expression, &a, is shown above the arrow and the abstract type:

	int (*)

(pointer to int), is shown below. This indicates that the address of the identifier in the declaration CAN be taken. There is no ambiguity possible in this simple example.

Example 2:

The declaration:

	char *p;

is of a pointer to char, and for each pointer there is also an arrow going to the object pointed to:

                  +----------+         .........
   &p             |    p     |  (*p)   . (*p)  .
   -------------->+==========+-------->.=======.
   char (*(*))    | char (*) |  char   . char  .
                  +----------+         .........

The pointer to the identifier, &p, is again shown on the left above the upper leftmost arrow, with its abstract type, char (*(*)), below.

For the previous declaration, char *p;, it is possible and meaningful to write the expression:

	&(*p)

which means "the address of what p points to", which is the value of p.

The object pointed to, (*p), since it is a simple data type, is shown in a split box with the identifier in the top and its abstract type in the bottom half. Note that the split box is "dotted" in this case. The dots are used to indicate that the object pointed to, i.e. its memory space, is NOT allocated by this declaration. The value of "p", is the address of this object (a char in this case), the thing pointed to. The value of "p" can only be assigned to it, by an initialization of the variable or by an assignment statement executed at run time of the program. This relatively simple case is already ambiguous and has multiple possible use cases.

Case 2.1:

	char w, v, *p=&v; // initialization, or
	p = &w; // assignment
	*p = 'z'; // assign the ascii value of z to the character that p points to 
	v = *p; // change the value of v to what p points to 

Case 2.2:

	char w, v, *p;
	p = malloc(1); // assignment of dynamicaly allocated space

In both cases 2.1 an 2.2 is is valid to use the expression:

	p[0]

on either side of an assignment expression. No other index besides 0 is valid. Any other other index could cause the program to crash.

Unlike case 1.1 the memory space that p points to should be released, when no longer needed, by:

	free(p);

If this is not done then there is what is called a memory leak. This happens when variable p goes out of scope and the allocated address is lost or no longer available. The allocated memory is then no longer accessible, because its address is not available to the program.

Case 2.3:

	char w, v[12]="Happy!", *p=v; // initialization

In this case p is pointing still pointing to a single character, but that character is in an array and can be referenced as such. For example:

	w = p[4]; // assigns 'y' to w (same as v[4])

It is valid to write the expression:

	*p

on either side of an assignment expression because it is equivalent to:

	p[0]

In both cases 2.1 and 2.3 to do:

	free(p);

is a serious and fatal error, which may or may not cause a crash (segmentation fault and memory dump) at the time of the call to free(). If there is no crash at the time of the call to free() there may be a disaster at some future time when there is a call to malloc() because it will use this wrongly free'd address and corrupt dynamic memory. This is a subtle and hard to diagnose problem the first time it is encountered. This a job for valgrind. Another job for valgrind, given that p has been dynamically allocated is:

	free(p);
	free(p);

because future use of malloc() will give the same space twice causing very hard to diagnose behavior - think about it!

Case 2.4:

	char w, v, *p;
	p = malloc(100);

To follow the above with the statement:

	v = p[6];

will not cause a segmentation error because the program owns the memory pointed to by &p[6], the only problem is that its value is currently not defined and is usually not repeatable. It has a value, it is just unknown.

Like case 2.3, variable p is pointing to an array of char, but this time it is a dynamically allocated array at run time rather than array allocated at compile time. This space should be free'd before p goes out of scope.

In both cases 2.3 and 2.4 the expression:

	p[312]

is an error because it is trying to access (i.e. read or write depencing on what side of an assignment it appears on) memory which does not belong to the program. Even if this access does not cause a segmentation fault, it is only because of the limitation of the memory protection hardware. The results are unpredictable and can change as the program changes.

Although the variable p points to an array of char of size 100, it can also be used as a two dimensional array (2*50, 50*2, 4*25, 25*4, 5*20, 20*5, or 10*10) by how it is indexed. For example (4*25):

	int j=3, k=19;
	p[j*25+k]; // 0<=j<4, 0<=k<25

To write the expression:

	p[j][k]

will get a compiler error, because the program did not tell the compiler it is a two dimensional array nor the size of each dimension.

With this approach of explitly doing a multidimensional index calculation in a one dimensional array is easy to use any one dimensional array and fold a multidimensional array of any dimensionality into it by how correct of the index expression.

Case 2.5:

If instead we had the declaration and assignment of a larger type:

	int *p;
	p = malloc(120);

would this allocate space for 120 int's? The answer is no. The parameter passed to malloc is the number of bytes to allocate, so if 120 int's were wanted then malloc should be called as follows:

	p = malloc(120*sizeof(int));

Another issue is as follows:

	char *d;
	int *p, v[4];
	v[0] = 300;
	p = v;
	d = (char *)p;

The question is what is the value of the expression:

	*d

The answer depends on the "endianness" of the cpu. If the cpu is "little endian" then the value of *d is 44, but if the cpu is "big endian" the value depends also on sizeof(int). If sizeof(int) is 2 then the value of *d is 1, but if sizeof(int)>2 then *d is 0. This shown by the following table:

   p    p+1
 +-----+-----+
 |  44 |  1  |
 +-----+-----+

    p    p+1   p+2   p+3
 +-----+-----+-----+-----+
 |  44 |  1  |  0  |  0  |
 +-----+-----+-----+-----+ 

    p    p+1
 +-----+-----+
 |  1  |  44 |
 +-----+-----+

    p    p+1   p+2   p+3
 +-----+-----+-----+-----+
 |  0  |  0  |  1  |  44 |
 +-----+-----+-----+-----+

This shows a way, knowing sizeof(int), to determine the endianness of a cpu. Write a function:

	int endianness_is(void) { ... }

which will return 0 if the cpu is little endian and 1 if the cpu is big endian. Better still, return one of the following two manifest constants:

	#define ENDIAN_LITTLE 0
	#define ENDIAN_BIG    1

Example 3:

Here is a declaration for an array of 2 elements:

	float z[2];

whose memory layout is shown just below, which shows the two elements in the array.

                 /----------\
    z,&z[0]      |+--------+|
    ------------>||  z[0]  ||
    float (*)    |+========+|
                 || float  ||
                 |+--------+|
                 |+--------+|
                 ||  z[1]  ||
                 |+========+|
                 || float  ||
                 |+--------+|
                 \----------/

The fact than an array is being shown, is indicated by the border around the objects in the array. This array is allocated at compile time by the declaration.

Example 4:

The declaration:

	int b[3];

              /--------\
   b,&b[0]    |+------+|
   ---------->|| b[0] ||
   int (*)    |+======+|
              || int  ||
              |+------+|
              |+------+|
              || b[1] ||
              |+======+|
              || int  ||
              |+------+|
              |+------+|
              || b[2] ||
              |+======+|
              || int  ||
              |+------+|
              \--------/

The fact than an array is being shown, is indicated by the border around the objects in the array. This array is allocated at compile time by the declaration.

For simplicity, no more than three objects are directly shown in an array in the memory allocation diagram. When an array is of size 1, 2, or 3, then all of the objects are explicitly shown.

Example 5:

When the array contains more than 3 elements, then only the first, second and last elements are shown.The declaration is:

	double big[229];

The unshown elements in the array are indicated by the 3 vertical dots:

                   /------------\
    big,&big[0]    |+----------+|
    -------------->|| big[0]   ||
    double (*)     |+==========+|
                   || double   ||
                   |+----------+|
                   |+----------+|
                   || big[1]   ||
                   |+==========+|
                   || double   ||
                   |+----------+|
                   |      .     |
                   |      .     |
                   |      .     |
                   |+----------+|
                   || big[228] ||
                   |+==========+|
                   || double   ||
                   |+----------+|
                   \------------/

As was mentioned earlier, the arrow in the upper left hand part of the memory diagram, which points to the object declared, indicates whether the address of the identifier from the declaration can be taken. In the case of an array, it is not meaningful to take the address of the identifier because it is not an "lvalue". That is, the compiler does NOT allocate a place to put the location of the array, It only allocates space for the array itself. If there was a way to change the address of the array it would mean that the array as a whole had been moved!. This subtle point requires a few moments of thought so that many simple programming errors will be avoided.

The name of the array is itself the address of the array, e.g. big for the last array; or, equivalently, it is the address of the first element of the array: equivalent to &big[0]. Both of these two possible pointers values are shown above this upper-left most pointer in the diagram. The type of this address, shown below the pointer is always of a pointer to an element of the array (whether of a simple or compound type).

Example 6:

Remember the fundamental pointer and array identity that says that an array expression:

	y[x],

has an equivalent pointer arithmetic expression:

	(*(y+x))

This confirms that the identifier of an array, y in this case, has a value which is the location of the array. And in pointer arithmetic, when an integer is added to or subtracted from a pointer the integer is implicitly (by the compiler) multiplied by the size in bytes of an element of the array. That size is:

	sizeof(y[0])

This is why, for the array above, the expression a is equal to the address of the first element in the array &a[0]. It is of utmost importance to understand this, and the more general use of the pointer and array identity to know how arrays are used.

The index, x in this case, can be negative. This is meaningful when y, declared as int *, is pointing into the middle of a larger array.

Example 7:

Multi-dimensional arrays could be shown by visually nesting the arrays, since in a multi-dimensional array each element of the larger array is itself an array. If we had the declaration:

	 float *ww[2];

which in words is: ww is a an array of 2 elements of pointers to float, we would have the following:

                 /-----------\
    ww,&ww[0]    |+---------+|           ..........
    ------------>||  ww[0]  || *ww[0]    . *ww[0] .
    float (*(*)) |+=========+----------->.========.
                 || float * || float     . float  .
                 |+---------+|           ..........
                 |+---------+|           ..........
                 ||  ww[1]  || *ww[1]    . *ww[1] .
                 |+=========+----------->.========.
                 || float * || float     . float  .
                 |+---------+|           ..........
                 \-----------/

Example 8:

Note that when the following doubly indirect pointer is declared, the memory allocation diagram shows that, in on case, there are two memory locations implied but not allocated:

         char **argv;

            +---------+         ..........        ..........
   &argv    |  argv   | *argv   . *argv  . **argv . **argv .
   -------->+=========+-------->.========.------->.========.
   char *** | char ** | char *  . char * . char   . char   .
            +---------+         ..........        ..........

In words: argv is a pointer to a pointer to char. Only the space for the first pointer, argv itself, is allocated by the compiler.

A very common use for this exact declaration also occurs as a parameter of function main(), in which case nothing is allocated statically in memory - only an address, the value of argv is passed to the function main on the stack:

	int main(int argc, char **argv);

In words: "argv is a pointer to a pointer to char", for which their are multiple possible interpretations and implemenattions. The actual one used by the function main() is: "argv is an array of pointers to char" whose declaration can also be written as:

	char *argv[];

Thus if we had a program named "fie.exe" and invoked it from a shell command line as follows:

	./fie Data Structures

then the memory layout for argv is:

        /--------------\
        | +----------+ |     argv[0][0] argv[0][1] argv[0][2] argv[0][3] argv[0][4] argv[0][5]
argv    | | argv[0]  | |    +----------+----------+----------+----------+----------+----------+
------->| +==========+ |--->|   '.'    |   '/'    |   'f'    |   'i'    |   'e'    |     0    | 
char ** | | char (*) | |    +----------+----------+----------+----------+----------+----------+
        | +----------+ |       char       char       char       char       char       char
        |              | 
        | +----------+ |     argv[1][0] argv[1][1] argv[1][2] argv[1][3] argv[1][4]
        | | argv[1]  | |    +----------+----------+----------+----------+----------+
        | +==========+ |--->|   'D'    |   'a'    |   't'    |   'a'    |     0    | 
        | | char (*) | |    +----------+----------+----------+----------+----------+
        | +----------+ |        char       char       char       char       char
        |              |
        | +----------+ |     argv[2][0]                                                       argv[2][10]
        | | argv[2]  | |    +----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+----------+
        | +==========+ |--->|   'S'    | 't' | 'r' | 'u' | 'c' | 't' | 'u' | 'r' | 'e' | 's' |    0     | 
        | | char (*) | |    +----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+----------+
        | +----------+ |        char                                                             char  
        \--------------/

Note the terminating 0 (or NUL char) at the end of each string.

Another interpretation of char **argv is a pointer to an array of characters, which (in the above example) could also be declared as:

	char (*argv)[6];

and used in the same way. The value of (*argv)[2] is 'f'. In words: "argv is a pointer to an array of size 6 of char. Which means that the other two arrays (containing "Data" and "Structures" are no longer accessible. Which is why this declaration, although it works for the first (or actually the zeroth) array (which contains the program name and path) has no way to access the other two arrays ("Data" and "Structures"), because he memory diagram is:

           +----------+         [0]   [1]   [2]   [3]   [4]   [5]    : index
argv       | (*argv)  |       +-----+-----+-----+-----+-----+-----+  (values shown,
---------->+==========+------>| '.' | '/' | 'f' | 'o' | 'o' |  0  |   not identifier
char (*)[] | char (*) |       +-----+-----+-----+-----+-----+-----+   and type)
           +----------+

Another interpretation of char **argv is a pointer to a pointer to char, which (in the above example) could also be declared as:

	char *cp, (*(*argv)), c='.';
	cp = &c; // cp is assigned the addres of variable c
	argv = &c; // argv  is assigned the addres of variable cp

and used in the same way. The value of (*(*argv)) is '.'. The memory diagram is:

            +----------+       +-------------+
argv        | (*argv)  |       | (*(*argv))  |       +-----+
----------->+==========+------>+=============+------>| '.' |
char (*(*)) | char (*) |       | char (*(*)) |       +-----+
            +----------+       +-------------+

    // file: fie.c
    #include <stdio.h>

    int main(int argc, char **argv) { int k;
        printf("argc=%d\n", argc);
        for(k=0; k<argc; k++) {
            printf("argv[%d]=\"%s\"\n", k, argv[k]);
        }
        printf("%c\n", (*argv)[3]);
        printf("%c\n", (*argv+1)[3]);
        printf("%c\n", argv[2][4]);
        return 0;
    }

Example 9:

The declaration:

	float z[3][2];

is a multimensional array of 6 (3 rows of 2) float's. z[0], z[1], z[2] are all pointers to float.

    #include <stdio.h>

    int main(int argc, char **argv) {
    int j, k; float z[3][2];
        printf("z=%X &z=%X\n", z, &z);
        for(j=0; j<3; j++) {
            printf("z[%d]=%X :", j, z[j]);
            for(k=0; k<2; k++) {
                printf(" &z[%d][%d]=%X", j, k, &z[j][k]);
            }
            printf("\n");
        }
        return 0;
    }

z=22FF40 &z=22FF40
z[0]=22FF40 : &z[0][0]=22FF40 &z[0][1]=22FF44
z[1]=22FF48 : &z[1][0]=22FF48 &z[1][1]=22FF4C
z[2]=22FF50 : &z[2][0]=22FF50 &z[2][1]=22FF54

                 /-------------------------\
    z, &z        | +---------+ +---------+ |
    ------------>| | z[0][0] | | z[0][1] | |
    float ([][]) | +=========+ +=========+ |
                 | | float   | | float   | |
                 | +---------+ +---------+ |
                 | +---------+ +---------+ |
                 | | z[1][0] | | z[1][1] | |
                 | +=========+ +=========+ |
                 | | float   | | float   | |
                 | +---------+ +---------+ |
                 | +---------+ +---------+ |
                 | | z[2][0] | | z[2][1] | |
                 | +=========+ +=========+ |
                 | | float   | | float   | |
                 | +---------+ +---------+ |
                 \-------------------------/