CSC 180
Notes for Tutorial #11

Monday 25  November  

Wednesday 27 November  

SUMMARY OF THE TOPICS 

 1. Questions about Assignment Four.
 2. Dynamic memory allocation

 1. Questions about Assignment Four.
 ===================================

Assignment Four has been posted.  
Please ask for questions and try to answer them.

 2. Dynamic memory allocation
 ============================

There have been a few times this term when you may have wanted to
write statements like:

   int list[n];

where n has a value that was set during the execution of the program.

This sort of array is called a dynamic array - because its length 
could be different on different executions of the program.

Unfortunately, C does not allow for the declaration of dynamic arrays.

But fortunately, there is another way to accomplish this task.
The C standard library function   malloc  can be used to allocate
a block of memory.  It has the prototype:

  void *malloc(size_t size)

It returns a pointer to a block of memory that has been allocated for
your program to use. The return type "pointer to void" is C's way of 
expressing a generic pointer to a piece of data.  It can be assigned
to any pointer type.  (size_t is a type of integer)

For example, you can write :

    char *c;

    c = malloc( 19 + 1 );

    strcpy( c, "To be or not to be." );

This program segment will ask for a pointer to 20 bytes of memory,
19 for "To be or not to be." and 1 for the trailing null character. 
Once the pointer variable c refers to this block, the string can be
copied over to the requested locations.

Since the malloc function is part of the C standard library, you need
to add the statement:   #include <stdlib.h> to your C program file
so that the compiler will process the declaration of the malloc function
before you make use of it.

====

Of course, your computer will not have a limitless supply of memory,
so it may be possible that your request for memory may not be met.
In this case, the malloc function will return the null pointer, NULL,
a ``pointer to nothing''.  It is a good practice to test whether or
not requested memory was allocated before you attempt to use it.
You can do this by ``guarding'' the statements that access the memory
with an if-statements, as in:
    
    c = malloc( 19 + 1 );
    if ( c != NULL ){
        c = malloc( 19 + 1 );
    }

If you don't do this, you run the risk of ``dereferencing a null pointer''
which means that you will be attempting to access memory that does not
belong to you.  You will likely get a segmentation fault message.

====

Suppose you were writing programs that performed some linear algebra 
calculations on vectors whose length was part of the data.
You might write a program like:

    int n;
    double *v;

    scanf("%d", &n);

    v = malloc( n*sizeof(double) );
    if ( v != NULL ) {
        ...

Enough storage to hold a double array of lenth n would be allocated
and could be accessed using terms like v[2];.   Note that the sizeof(double)
function is used to get the size of a double variable so that the correct
number of bytes would be set aside.  Don't forget that char variables
take less space than int variables, which take less space than double 
variables.  Using a parameter like ``n*sizeof(double)'' ensures that enough
space is set aside to store an array of n double variables.

Since v is just a pointer variable to double, the ... statements could
be replaced by:
        for ( i = 0; i < n ; i ++ ){
            scanf( "%lg", &v[i] );
        }
if the n elements of the vector were to be read in to the program.

====

To declare space for a m-by-n matrix and read it in, you would want to write:

    int i,j;
    int n, m,
    double *matrix;

    scanf("%d %d", &m, &n);
    matrix = malloc( m*n*sizeof(double) );
    if ( matrix != NULL ) {
        for ( i = 0; i < m ; i ++ ){
            for ( j = 0; j < n ; j ++ ){
                scanf( "%lg", &matrix[i*n+j] );
            } 
        } 
    } 

Note that we still need to treat the matrix like a 1-d array
and compute the indices on our own.  In order to write references
like  matrix[i][j]  we would have to 
 (1) allocated space for the m*n elements
and 
 (2) allocate space for m pointers to ints
and
 (3) initialize the pointers so that they point to the rows of 
the matrix.

Think about how this might be done.

====

One last point:

If you repeatedly call malloc to allocate memory, you could 
eventually run out of memory!   You can "free" the memory that
you have allocated by calling the  free() function.  For example,
you might write statements like:

    int *p;

    p = malloc( 100*sizeof(int) ); /* create space for an array of 100 ints */
    .
     .    Use the array of 100 ints.
      .
    free(p);  /* deallocate the array of 100 ints. */