Dynamic Allocation and Contiguous Lists

Objectives

• Know how to use contiguous lists in C.
• Know how to dynamically allocate a vector and a matrix
• Know how to use the realloc function

Questions

malloc

1. In a file alloc_statique.c, declare a function with an integer matrix M of size SIZE*SIZE where SIZE is a constant (for example, equal to 400 to start), and initialize the matrix. Compile and test. Increase the constant SIZE and observe the limits of stack allocation. Note at what size your code stops working, and how many bytes/kilobytes that corresponds to.
2. In the same file, now declare the matrix M as a global variable, and test the allocation limits in the data segment. Report the limits.
3. In a file alloc_dynamique.c, declare int * v, allocate and initialize a vector of SIZE integers. For this, use the malloc function which allows dynamic memory allocation; thus int * v = (int *) malloc(SIZE * sizeof(int)); allocates SIZE elements of integer size. If malloc fails (not enough memory), the returned value is NULL.
4. In the file alloc_dynamique.c, declare int ** mat, allocate and initialize a matrix of size SIZE*SIZE: the matrix is a vector of vectors. To simplify these allocations, you can use a loop that allocates a vector at each iteration and assigns it to the matrix.
5. Test the allocation limits on the heap by printing the total allocated memory size the first time malloc returns NULL. To find the limits, change the size of the vectors (for example, allocate 1 megabyte per iteration, 10 megabytes per iteration, 100 megabytes per iteration, 1 gigabyte per iteration, …).
6. Properly deallocate the matrix using the free command. For example for question 3, the statement free(v) frees the memory allocated by v. Verify there are no memory leaks using the valgrind utility¹

realloc

Given the following source code:

#include <stdio.h>
#include <ctype.h>

int main()
{
    char character = getchar();
    while ( !isspace(character) )
    {
        putchar(character);
        character = getchar();
    }
    putchar('\n');
    return 0;
}

1. What does the isspace function do? You can use page 3 of the manual (man).
2. Modify this program to store the characters in a dynamically allocated vector as they are read. Be careful not to exceed the bounds of the allocated vector (add a stopping condition in the while loop). Also be careful to properly deallocate the vector at the end of execution.
3. Consult the documentation of the realloc function (man realloc).
4. Use the realloc function to resize the vector when the bounds are reached (for example, add 8 characters to it), so that input only ends when a whitespace character (' ', '\n', '\t', …) is read. Make sure to properly deallocate the vector at the end of execution. Verify with valgrind that there are no memory leaks.

String Structure

To simplify the writing of string algorithms, and to no longer worry about dynamic allocation, we will encapsulate character strings in a structure, and write the basic functions for this structure. In a new file chaine.c:

typedef struct
{
    char *  data;
    int     alloc;
    int     size;
} chaine ;

The meaning of this structure is as follows:

• The data field holds the address of a dynamically allocated memory region containing a character string (terminated by '\0').
• The alloc field holds the number of char values allocated for data.
• The size field holds the length of the string (the '\0' is not counted)
• We always have size+1 <= alloc.

1. Declare the type chaine.
2. Write the function void init_chaine(chaine *) which initializes the alloc and size fields to 0, and data to NULL.
3. Write the function void clean_chaine(chaine *) which deallocates the dynamically allocated memory for the string.
4. Write the function void print_chaine(chaine *) which prints the string data.
5. Write a function void concat_chaine_char(chaine *, char) which appends a character to the end of the string, resizing the data field if necessary (with realloc).
6. Test these functions in the same way as before: initialization, copying characters requested from the user, then printing and finally deallocation.
7. Write a function void concat_chaine_chaine(chaine *, chaine *) which appends all characters from the second string to the end of the first, resizing the data field if necessary (with realloc). Test this new functionality.