Memory Diagrams

A memory diagram is a picture of the state of the computer's memory at a specific point in time. There are three areas of memory, only two of which are relevant now:

• Global memory, for global constants (we don't allow you to use global variables in Comp 11). You'll sometimes here global memory referred to as static.
• Stack memory, for storing variables (and parameters) and some other information associated with functions.
• Heap memory, which we are not using yet. Since we're not using it yet, there is no need to draw it, and the following diagrams do not include the heap. You'll hear the heap referred to in C++ as free store, too.

Every variable is a location in one of these areas of memory. We draw a variable as a box. Every variable has an address and a current contents. The contents goes inside the box. The diagrams here don't show addresses, because we don't need to worry about them yet.

These notes were written for Comp 11 students before they had learned about pointers or the heap. After you've gone through the notes below, come back and read these cursory notes about the more complex diagrams you'll need to draw in Comp 15.

Draw the heap as another column to the right of the stack and label it “Heap.” Objects are allocated here whenever the program executes a new. When the program executes a delete, cross out the space that is recycled.

Note that arrays, and struct and class instances are variables that contain other variables. An array is a collection of unnamed, indexable variables stored one right after the other. A struct or class instance is a collection of named variables, which we draw rather the same as an activation record below.

A pointer value is a memory address. A pointer variable is a variable whose contents can be a memory address, just as an integer variable is a variable whose contents can be an integer value. We draw pointer variables in one of two ways:

• The variable contains the root of an arrow whose pointy end terminates at the variable pointed to. This is the more normal way to draw a pointer.
• Alternatively, the variable contains a an address (usually written in the form 0x6010), and that address is labeling the variable it's the address of (i. e., that address must label some box in the picture). This indicates that the pointer value stored in the pointer variable “points to” the location with the given address. This form can be useful when there are too many arrows and the diagram gets messy.

Do not draw arrows for other things! Dotted arrows are for function return, solid arrows are for pointers. Do not draw arrows, for example, to indicate data movement on any diagram you show us — we will assume you mean those things to be pointer values!

For purposes of these diagrams, we are assuming that get_int is defined this way:

/* * get_int * Purpose: Read an integer from standard input (cin) * Args: prompt is string sent to standard out to prompt user * Return: integer value entered in response to prompt * * Note: No error checking or recovery done. */ int get_int(string prompt) { int result; cout << prompt; cin >> result; return result; }

When a program runs, the global variables are allocated (space is set asside for them), and then initialized. After that, the main function gets called. Here is the picture of memory for golf program just before main is called. Note that there is nothing on the stack yet.

Here is the memory diagram after main has been called, but before get_int has been called the first time.

Note that the values in the variables are unknown. In C++, you cannot assume that local variables are initialized to any particular values if you didn't initialize them. Space is set aside for them, and whatever was in that memory before can still be there. (Some compilers may cause them to be initialized, but you can't count on it.)

At this point, control reaches this statement:

                  tempF = get_int("Temperature (fahrenheit)? ");
              

This causes the program to identify the variable on the left (tempF), evaluate the argument in the parentheses ("Temperature (fahrenheit)? "), and then make an activation record for get_int.

Notice that the parameter has been initialized with the argument value from the caller. Local variables (just result in this example) do not have a predictable value yet.

The prompt is printed, and suppose the user types 78. Then, just before the return, memory looks like this.

Then after the return statement, the return value is saved away, the activation record for get_int is recycled, and the return value (78) is given to the caller and the caller resumes where it left off (the caller is main in this case).

Then main completes the assignment that was in progress when it called get_int.

Then execution moves on to the next assignment statement, and all this repeats for the day of the week, etc.

A quick example with heap

This is just a very quick example to show how pointers and heap are incorporated. In this example, there are no interesting global variables, so we'll just show the stack and heap. The code looks something like this:

struct Node { string val; Node *left, *right; }; void afun(int *np, Node *node) { *np = node->val.length(); } int main() { int num = 4; Node *aNode = new Node; aNode->val = "x"; aNode->left = aNode->right = nullptr; afun(&num, aNode); return 0; }

Here is a memory diagram showing the state of the program just after afun has been called but before its single line has run. (afun is just about to modify num to contain 1.)

Note how pointers are represented as arrows. Inside afun, np contains the address of the variable num in main's activation record: This parameter is being passed by pointer (or passed by reference using a pointer). The second parameter is being passed by value, and the value is the address of a variable on the heap that holds a struct, which in turn contains 3 variables: a string and two Node pointer variables.