TIGCC Programming Lessons

The following is part of a series of lessons designed to help teach people to program in C for the TI-89, 92+, and V200 calculators using the TIGCC development environment.

If you wish, you can download the program source code, project files, and binaries here.

Lesson 6: Dynamic Memory Allocation

Step 1 - An Introduction to Dynamic Memory Allocation

Up until this time, we have used what is referred to as static memory. Static memory means we reserve a certain amount of memory by default inside our program to use for variables and such. While there is nothing wrong with this, it means that once we reserve this memory, no other program can use it, even if we are not using it at the time. So, if we have two programs that reserve 1000 bytes of memory each, but neither program is running, then we have 2000 bytes of memory that is being completely wasted. Suppose we only have 3000 bytes of memory, but we already have our two programs that take 1000 bytes each. Now we want to load a program that needs 1500 bytes of memory. Well, we just hit a wall, because we only have 3000 bytes of memory and 2000 bytes are already reserved. We can't load our third program even though we have 2000 bytes of memory that isn't even being used. How could we possibly remedy this situation?

If you said Dynamic Memory Allocation, then you must have read the title of this lesson. That's right. We are going to use dynamic memory to share the memory among all three programs.

Dynamic memory won't fix everything. We will always need an amount of finite static memory, but this amount is usually much less than we need. This is why we still have static memory.

So, let us imagine a new scenario. We have changed our first two programs to use dynamic memory allocation. Now they only need to reserve 100 bytes of memory each. This means we are now only using 200 bytes of our 3000 total memory bytes available. Our third program, which requires 1500 bytes of memory can now run fine.

Step 2 - The Basics of Dynamic Memory Allocation

Now that we have covered why we would want to use dynamic memory allocation, how do we go about doing it? Well, that's easy! We have predefined functions that let us perform these tasks.

The two functions we will be employing in our dynamic memory allocation tasks are malloc() and free(). malloc() meaning memory allocation, and free, well, that should be obvious. Our malloc() function returns a pointer to the memory block we requested. Remember pointers from the last lesson? I told you we weren't done with them yet.

Let's discuss the syntax of malloc(). It takes a single argument, a long integer representing the number of bytes we want to allocate from the heap. (Note: the heap is what we call all the memory we don't reserve by default) So, for example, to allocate memory for an array of characters for a 40 character string, we would do malloc(40); There's more to it, obviously, but we'll cover that.

To allocate memory though, we must have a pointer so we can know where the memory will be at when it gets allocated. Let's look at a small code example:

char *str = (char *)malloc(40);	// allocate memory for a 40 character string

This may look a little weird, because it uses a concept we haven't worked with before called "type casting". C has the ability to convert from one type of variable to another by using what are called type cast operators. The syntax is simple, put the variable type you want to convert to inside parentheses. See, it's easy. So, because we want to convert the memory into a character pointer, which is specified by the type char *, we put char * in parentheses. Then C will give us a character pointer to the memory. This is very easy to do when a character pointer is involved. The important thing to note here is what malloc() returns to us. Because malloc() doesn't care how the memory we allocate will be used, malloc() just returns a pointer to a series of bytes. It does this by using a void pointer. Void pointers are just like character pointers, or integer pointers, or any other kind of pointer with one special difference: we do not know what the size of the void pointer is. There is no way to increment or decrement a void pointer. In fact, we can't do much of anything with a void pointer except acknowledge its existence until we convert (type cast) it to another variable type.

Characters are by definition 1 byte, and malloc always allocates in multiples of a single byte. Other types are more than 1 byte. Rather than remembering how many bytes an int variable takes on a system, we can use the sizeof operator. Let's see an example.

char *str = (char *)malloc(40 * sizeof(char));	// allocate memory for a 40 character string

This looks very similar to what we had above, with one important exception, the sizeof(char) multiplier. This is a new operator, and another very important one in C. The sizeof() operator will tell us the size of any variable or structure in our program. The one thing to keep in mind when using sizeof() is that the size of a pointer is how many bytes it takes to store the pointer, not the size of the memory block the pointer is pointing at. There is no need to know that information. In allocating memory like this, we know we have 40 characters instead of 40 bytes (even though they are technically the same). There is a difference between 40 integers and 40 bytes, and 40 long integers especially.

Now that we have taken a look at how the malloc() function works, let's take a look at its companion function, free(). The free() function is basically the exact opposite of malloc(). So, instead of assigning a pointer the value returned, we give the function the pointer we got from malloc(). So, if we have the *str pointer we allocated above, to free that memory, we just need to call free with the pointer as an argument.

free(str);	// free the memory allocated by malloc()

You may be wondering how the free() function knows how much memory to free up, since we didn't tell it how much memory we allocated. Well, the short answer is: you don't need to worry about that. The system will take care of such minutia for us. The long answer is, well, long, and complicated, so I don't want to talk about it.

Most modern systems will free allocated memory at the completion of the program. The AMS is not one of these systems. If you don't free the memory you allocate, your calculator will lose memory until it is reset.

Step 3 - The Many Uses of malloc()

Start TIGCC and create a new project. Create a new C Source File called malloc. Edit the file so that it looks like this:

malloc.c

#include <tigcclib.h>

void _main(void) {
    int loop;
    unsigned long int *array;   // the integer array pointer

    // clear the screen for printf()
    clrscr();

    // allocate the array or exit with an error
    if ((array = (unsigned long int *)malloc(45 * sizeof(unsigned long int))) == NULL) {
        DlgMessage("DMA Failure","Unable to allocate integer array space",BT_OK,BT_NONE);
        return;
    }

    // get the first two numbers in the Fibonacci sequence -- I start at 1, not 0
    array[0] = 1;
    array[1] = 1;

    // setup the array with the first 45 numbers in the sequence
    for (loop = 2; loop < 45; loop++) {
        array[loop] = array[loop - 1] + array[loop - 2];
    }

    // display the intro message
    printf("The Fibonacci Sequence:\n");
    printf("Press a key to begin!\n\n");
    ngetchx();

    // loop through the array and print out the numbers in the sequence
    for (loop = 0; loop < 45; loop++) {
        // print the number - lu = long unsigned
        printf("%lu\n",array[loop]);

        // if we've printed 8 numbers, pause to see the result
        if (((loop % 8) == 0) && loop != 0) {
            printf("Press any key...\n");
            ngetchx();
        }
    }

    // free up the memory used by the integer array
    free(array);

    // wait for user input before exiting the program
    ngetchx();
}

Step 3a - Compile and Run the Program

Build the project and send it to TiEmu. It will look like this:

Step 3b - Programmatic Analysis

Okay. I know this wasn't the best example, but I couldn't think of anything good to do. Anyway, let's try to get through it. Although thinking about how many computer science classes I took that used factorial as an example program, maybe it's not that bad.

int loop;
unsigned long int *array;	// the integer array pointer

We have our variable declarations. Remember that there is very little difference between arrays and pointers, so once we have space for our pointer, it will be an array.

// allocate the array or exit with an error
if ((array = (unsigned long int *)malloc(45 * sizeof(unsigned long int))) == NULL) {
	DlgMessage("DMA Failure","Unable to allocate integer array space",BT_OK,BT_NONE);
	return;
}

One thing I forgot to mention about Dynamic Memory Allocation is, unlike static memory which is reserved by default (so you won't be able to send the program unless you have enough memory), dynamic memory must be allocated at runtime. That being said, there may not be enough memory available to fill the request. So, we must always check that our memory was actually allocated to us by checking the pointer against a NULL value. The NULL value basically says, "I am not pointing at anything". And, if we are not pointing at anything after we finish our malloc() call, then we don't have enough memory to run this program. We should display some kind of error message and exit the program.

To exit a program from the main() method, we can use the return keyword. You have seen return when we are sending back a value from a function. The main function is no different, except that we do not return a value because the return type of the main function is void. So, we can use return without returning any specific value.

This being done, if we haven't exited our program, then we must have gotten the memory we requested. So, let us continue.

// get the first two numbers in the Fibonacci sequence -- I start at 1, not 0
array[0] = 1;
array[1] = 1;

Since this example deals with the Fibonacci Sequence, we need to initialize the base cases of that sequence. If you haven't seen the Fibonacci sequence before, it runs like this. The first two numbers are 1 and 1. Every number after the first two numbers are the sum of the previous two numbers. So we have 1, 1, 2 (1 + 1), 3 (1 + 2), 5 (2 + 3), 8 (3 + 5), 13 (5 + 8), etc. Remember that since arrays are just a special way of using pointers, we can use array notation for accessing our pointer memory. We could have done the same thing by using this code:

*array = 1;	// set the first array node to 1
*++array = 1; // set the second array node to 1

But array notation is more readable.

// setup the array with the first 45 numbers in the sequence
for (loop = 2; loop < 45; loop++) {
	array[loop] = array[loop - 1] + array[loop - 2];
}

Okay, our first big loop sets up all the values in our limited segment of the Fibonacci sequence (the first 45 values). Since we allocated space for a 45 node array, we will have no problem storing this. As per our definition of the sequence, each value is the sum of the previous two values, so we use a simple assignment statement (=).

// display the intro message
printf("The Fibonacci Sequence:\n");
printf("Press a key to begin!\n\n");
ngetchx();

You should know how printf() works by now, especially in this limited example. We are just displaying a short message on the screen.

// loop through the array and print out the numbers in the sequence
for (loop = 0; loop < 45; loop++) {
	// print the number - lu = long unsigned
	printf("%lu\n",array[loop]);
		
	// if we've printed 8 numbers, pause to see the result
	if (((loop % 8) == 0) && loop != 0) {
		printf("Press any key...\n");
		ngetchx();
	}
}

Our next big loop prints out all the values in our sequence. We could have done this while we were assigning our values to the sequence, but a real program would store the values in the array and access them later, so, this is a little closer to something real (okay, that's a stretch, but stay with me).

The loop is fairly simple, we use printf() to display our values on the screen because printf() is easy to use and will scroll the lines on the screen for us automatically. Remember that the %lu format specifier is used for printing long unsigned integers, which is what we have in our array. The \n is our key for a new line.

The last segment of this loop pauses the screen after 8 lines of output. We want to give the user a chance to see the results. We introduce another operator here, the modulo operator. Modulo gives us the remainder part of integer division. So, if a number is evenly divided by 8 (loop modulo 8), then we will enter our if-clause. But we have to take care of one more condition. Remember that 0 modulo anything is always 0, and we don't want to pause after we print the first number, so we will make the condition also require that the loop counter is not 0 (the first node in the array). So, if both of these conditions are satisfied, then we print a short pause message and wait for the user to press a key. Simple, no?

// free up the memory used by the integer array
free(array);

Okay, the last line of our program is possibly the most important when dealing with dynamic memory allocation. Never ever forget that you must always free up the memory you allocated before you exit the program. If the program exits without freeing up the memory, it will be reserved forever. Worse than that, on the TI-89/92+/V200, there are a limited number of handles available to dynamic memory allocation, and once those handles are gone, we can't allocate any more dynamic memory. The only way to get these handles and memory free if you don't free them before you exit the program is to reset the calculator, because the AMS does not do garbage collection for you.

As long as you remember that one important rule, you shouldn't have a problem with dynamic memory allocation.

Continue in Part II