Intro to Dynamic Allocation


  1. Static allocation:

    Static allocation is when the amount of space for an array or some other construct is determined at compile-time. The disadvantage of this is that we don't always know how big an array we need until the program is run.

    With static allocation, if we wanted a char array label to be able to hold various strings, then we would have to determine the length of all of the strings that would be held in label and then make that array large enough to accommodate the largest string.

    For example, if we need to store labels like: "Single", "Married (J)", "Married (S)", and "Head of Household"... What would the size of the array needed to hold these things be?

    char label[??];
    

    In some cases, we can't determine the maximum size at compile-time. For example, suppose labels are entered by user when the program is run. There is no size that we can choose for the array while ensuring that the user doesn't type in something longer.

  2. Array local variables must be of a static size:

    Sometimes, we need to create a string whose size we won't know until the program runs (i.e., until run-time).

    Suppose we want to make a copy of a string that was passed to a function. The following is illegal.

    void foo(char text[])
    {
      char copy[strlen(text) + 1];  /* WRONG--Not valid! */
    
      /* copy 'text' into 'copy' */
    
      copy[0] = 'A';
    
      ...
    }
    

    because the length of the string, i.e., strlen(text), cannot be determined at compile-time.

  3. Library routines for dynamic allocation:

    C provide a set of routines for allocating space for any type of object at run-time. Generally, we use use a pair of functions (prototyped in stdlib.h) named malloc() and free().

    These functions work as follows:

    For example, we want to dynamically allocate an array of integers. Suppose, the variable n holds the number of integers we need. Remember, we could not do something like:

    int grades[n];  /* WRONG!! n is a variable. */
    ...
    grades[2] = 10;
    ...
    

    because n is a variable, and thus, its value is not known until the program runs.

    Instead, we'd use malloc(), as in:

    int *grades;
    ...
    grades = (int *)malloc(sizeof(int) * n);
    ...
    if (grades == NULL) {
      printf("Cannot allocate memory for grades\n");
      exit(1);  /* End program, returning error status. */
    }
    ...
    grades[2] = 10;
    ...
    free(grades);  /* Deallocate the space since */
                   /* we're done with it.        */
    ...
    grades[3] = 15;  /* BAD!! Don't use space that */
                     /* has been freed!!!          */
    

    Remember, malloc() always takes the number of bytes needed. So, we need n int's, where the number of bytes used by an int is given by sizeof(int). Thus, we need sizeof(int) * n bytes in total.

    The pointer returned from malloc() is a generic pointer, so we cast it to the right type (here, int *), although strictly this is not necessary in C.

    When we are done with the dynamic array, we free() it. We should not use that space afterwards.

  4. Making a copy of a string:

    Now, suppose we wanted to make a copy of a string passed to a function, here's how we could use dynamic allocation to do so:

    #include <stdlib.h>
    
    void foo(char text[])
    {
      int num_chars;
      char *copy;
    
      num_chars = strlen(text) + 1;
    
      /* Allocate room for the string. */
      copy = (char *)malloc(sizeof(char) * num_chars);
    
      /* Copy the contents of the string. */
      strcpy(copy, text);
    
      ...
    
      /* Use the copy. */
    
      copy[0] = 'A';
    
      ...
    
      /*
       * Don't waste memory.  We are done with the
       * dynamically-allocated string, so free it.
       */
      free(copy);
    }
    

    Writing code like this every time we need a dynamically-allocated string is a hassle. Let's think about writing a library with functions that handle this task for us.

  5. Our string library:

    Let's write a string library for this task. We call the string library mystrlib. This means we should have two source code files named what?

    The string library will consist of 3 functions: NewStr, ConcatStr and FreeStr. Here is how the library functions should work:

    We've provided a header file and file for the function definitions for you. There is also a test program that you may use to test the library. Finally, there is a Makefile that generates the executable strtest.

    Download those files and fill in the function definitions.

    Note that we include the system header file stdlib.h where we need malloc() and free() (it also provides the NULL pointer).

    The output from the program should be the following:

    str1 is: This is the value
    str2 is: This is the value of the new string
    


BU CAS CS - Intro to Dynamic Allocation
Copyright © 1993-2000 by Robert I. Pitts <rip at bu dot edu>. All Rights Reserved.