CS 70

Rules for Drawing Memory Diagrams

  • LHS Cow speaking

    This page has a comprehensive set of rules for drawing our CS 70-style memory diagrams.

  • RHS Cow speaking

    It might be intimidating to see it laid out at once!

  • LHS Cow speaking

    But remember: the whole point is that you can take things step-by-step.

  • RHS Cow speaking

    You don't need to see the whole picture before you start drawing. You just need to know what to do next.

  • LHS Cow speaking

    These rules can help you do that!

What to Do When You…

Reach the Opening Curly Brace of a Function

  • Allocate space after the current stack frame for every non-reference local variable (including parameters).
    • Addresses should start with S and be sequential as the stack grows: S1, S2, ...
  • Label the group of local variables as belonging to this function's stack frame.
  • Initialize the parameters using the values of the arguments to the function call.

Reach a Variable Declaration

  • Initialize the variable.
  • If it is not a reference, label the variable's slot with its name.
    • If the variable is an object, label the group of member variables with its name.

Encounter the new Keyword

  • Allocate space on the heap for the type given after new.
    • Label the first memory address with address HX, where X is an arbitrary number that hasn't been used yet.
    • If there are multiple pieces of data (i.e. in an array or an object) there should be slots for all the elements.
      • Address these slots sequentially following the first one: e.g. H(X+1), H(X+2), ...
  • Initialize the new memory.
  • The return value of new is the first address of the allocated block.
    • Assign this address to whatever variable is receiving the return value.
    • (Follow the rules for initializing/changing a pointer as appropriate).

Access a Variable or Dereferenced Pointer

  • Look up the name on the diagram.
    • The variable or dereferenced pointer evaluates to the value next to the name.

Assign a New Value to a Variable or Dereferenced Pointer

  • Find the slot next to that name on the diagram.
  • If the type there is a primitive:
    • Cross out the old value in the slot, and write the new value.
  • If the type there is an object:
    • Execute the member function operator=().
  • If the type there is a pointer:
    • Cross out all dereferenced versions of the pointers name on the diagram.
    • Cross out the old value in the slot, and write the new value.
    • Follow instructions to initialize a pointer (though this isn't an initialization).

Encounter the delete Keyword

  • The delete keyword is given a memory address on the heap.
  • Destroy the contents of the memory at that address.
  • Deallocate the block of memory at that address.

Reach a Closing Curly Brace

  • Destroy each variable declared within the code block being closed in reverse order of declaration.
  • Cross out the name of each variable as it is destroyed to indicate that the name may no longer be used.
    • If crossing out the name of a pointer, also cross out all dereferenced versions of that pointers name on the diagram.

Reach the Closing Curly Brace of a Function

  • First, follow the rules for reaching a closing curly brace.
  • Deallocate every variable in the stack frame.
  • Cross out the label for the stack frame, indicating that the previous frame is now the current frame.

How to Represent Object Lifetime Events

Allocation

  • Draw a slot for every piece of data being allocated.
    • For an array, make contiguous space for all elements of the array
    • For an object:
      • Make contiguous space for all member variables
      • Label the group of member variables as belonging to an object of the appropriate type
  • Label each slot with its type and its memory address

Initialization

  • If initializing a reference, write its name next to its referent.
  • If initializing a primitive, put its value in its slot (or leave it blank if it is indeterminate).
  • If initializing a pointer:
    • Write its value (an address) in its slot, or leave blank if it is indeterminate
    • If given an initial value, write the variable's dereferenced name next to the address now held by the pointer.
      • e.g. if the variable's name is p, then label the memory at the address it holds with at least one of *p, p[0], *(p+0), whatever is most helpful for the code you are reading.
      • (If the type at that address is also a pointer, do the same for that pointer's address and so on.)
  • If initializing an object, execute the appropriate constructor.
    • Treat the member initialization list like a list of variable declarations in order of declaration in the class definition.
      • If a member is not mentioned in the member initialization list, it is default initialized.
  • If initializing an array, initialize each element from front to back.

Destruction

  • If the memory being destroyed is an object:
    • Execute its destructor.
    • Destroy each member variable (in reverse order of declaration) at the closing brace of the destructor.
      • Cross each member variable's name out as it is destroyed to indicate that the name may no longer be used.
        • If crossing out the name of a pointer, also cross out all dereferenced versions of that pointers name on the diagram.
  • If the memory being destroyed is an array:
    • Destroy each element in the array (from back to front).
  • If the memory is a primitive or a pointer: do nothing.

Deallocation

  • Cross out the type on each slot that is being deallocated to indicate that it is now free for future use.

(When logged in, completion status appears here.)