Create your repository: https://classroom.github.com/a/q4I3xmGU
Then clone the repository into your CodeAnywhere container using git clone YOUR_URL
(Click the green "Clone or Download" button to find your repository's URL).
Create all the exercise files inside your repository directory and then add, commit, and push them to GitHub when you are finished.
HW worksheet as PDF or Word -- You must add the completed worksheet to your repository with your submission.
In class Quiz and slide for quiz.

Due: Thursday 9/20 at 11:59PM, see submission instructions.

Updated 9/25: Made stack model more precise.

Objectives

The goal of this module is:

  • To go further into C with functions (methods), memory management, and data structures

As usual, to reduce clutter in the modules, our code examples will not show the "include's". Be sure to include the four in every program you write: 

// Put these at the top of every C file:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main ()
{
  // ...
}

Functions

A function in C (called a method in languages like Java) is a unit of code that can be invoked repeatedly to perform some computation.

A function can take zero or more arguments, and can optionally be declared to return a result.

Let's look at an example: 

void printHeading ()              // No arguments, no return value.
{
  printf ("Add/Sub demo: ");
}

int add (int a, int b)            // Two args, a return
{
  int c;
  c = a + b;
  return c;
}

int sub (int a, int b)
{
  return a - b;
}

int main ()
{
  int m, n;

  // No parameters
  printHeading ();

  // With direct values:
  printf ("5 + 6 = %d\n", add(5,6));

  // Capturing the return:
  m = sub (6, 5);
  printf ("6 - 5 = %d\n", m);

  // With variables.
  m = 7;
  n = 8;
  printf ("%d + %d = %d\n", m, n, add(m,n));

  // Return value into a variable:
  m = add (m, n);

  // Return value into an expression:
  m = m + add (m, n);

  // Nested application:
  m = add (m, add(m, sub(n,m)));
  printf ("m = %d\n", m);
}

HW Exercise 2.1: Without writing the program, can you predict what it will print at the end? Then, write the program in functionExample.c, and confirm.

The Stack

Previously we saw how to allocate memory on the Heap with malloc. The Heap is used for dynamically allocated memory -- memory that you don't necessarily know in advance how much you need. In contrast, the Stack is used for allocating memory regions of fixed, known in advance sizes.
  • Every time you call a function (including main) a memory region will be pushed (added) to the stack to store its local variables.
  • Every time a function returns, the memory it used will be popped (removed) from the stack.
  • How much memory is needed? The compiler determines how much space is required when it builds the executable for your code. This is why some compilers require all variables to be declared at the top of a function!
  • We will be using a simplified representation of the stack that ignores some of the intracacies!
In our model of the Stack:

  • The main function will reserve space for each local variable declared within it, in the order that it is listed. (We will ignore the fact that space is also needed for the return value of int main)

  • For every other function, we will reserve space in this order:
    • the return value (wich we will name rv or return) if necessary
    • each function parameter
    • each local variable
    Parameters and local variables are allocated in the order that they are declared. We will ignore any other meta data needed by the stack to track functions.

  • For simplicity, we will ignore the impact of any C library functions (printf(), malloc(), etc) on the stack (pretend those lines are commented out).

  • When a function returns, the stack frame (i.e., all the variables we just added), is "popped" from the stack. This means that the space all the variables were using will be reused by the next function call for its own stack frame.

  • In our diagrams, we will indicate a "popped" stack frame by erasing the names of variables, but leaving the content at those addresses the same -- C does NOT clear the memory contents when a function returns.
In the code above:
  • The add() method defined a local variable for calculation (just to demonstrate declaration and use of one): 
    int add (int a, int b)
{
  int c;
  c = a + b;
  return c;
}
    A function can declare any number of local variables, all of which will have space on the stack.
  • Note that a smart compiler could recognize that it doesn't need to allocate space for both c and the return value of the function. We will ignore this type of optimization in our model of the stack, so this function would add four integer variables to the stack (a, b, c, and rc).

  • Even though sub() does not declare a local variable 
    int sub (int a, int b)
{
  return a - b;
}
    the compiler actually creates a hidden temporary variable to hold the value of the computation a-b to return it. Thus in our model of the stack, this function would add three integer variables (a, b, and rc).

  • When a function returns, all of its stack space is freed. Note that the values in memory are NOT cleared in any way!

  • The next function to be called will overwrite any memory from the last popped stack frame.

  • The return value from a function can be placed in a variable: 
      m = add (m, n);
    or can be used in an expression: 
      m = m + add (m, n);
STOP! Now that we fully understand the stack, let's solve problem 1 from the C-1 worksheet!
Exercise 2.2: Consider this code:

  • Run the code and observe its output. Draw a memory diagram on your worksheet indicating the stack's contents just before f2() returns. (Use the stack model described above, remember to ignore printf statements and don't worry about the address column). Confirm that our stack model accurately represents the program's behavior.

  • Change the program so that f2() is called before f1(). How does the program output change?

  • Revert so that f1() is called first. Then change the program so that int m is initialized to 3 in its declaration in f2(). Does our stack model still accurately represent the program behavior? If not, can you guess what the compiler is doing differently?

  • Revert so int m is not initialized, and int n = 4. Does our stack model still accurately represent the program behavior? If not, can you guess what the compiler is doing differently?

Note:

  • The functions need to be defined before they are called.
    HW Exercise 2.3a: Move the method main() in functionExample.c to the top of the file (but after the include's) so that it's the first method. What is the compiler error generated?

    It is often convenient to use function prototypes, as this example shows: 

    // No body, just the signatures:
void printHeading ();
int add (int a, int b);
int sub (int a, int b);

int main ()
{
  int m, n;

  printHeading ();

  m = 7;
  n = 8;
  printf ("%d + %d = %d\n", m, n, add(m,n));

  m = add (m, mult (intDiv(n,m), n));
  printf ("m=%d\n", m);
}


void printHeading ()
{
  printf ("Add/Sub demo: ");
}

int add (int a, int b)
{
  int c;
  c = a + b;
  return c;
}

int sub (int a, int b)
{
  return a - b;
}

    Thus:

    • A function prototype is merely a definition or signature, describing the name, parameters and return types: 
      int add (int a, int b);

    • The actual body of the function can then come later, or even in a different file.
    HW Exercise 2.3b: Add function prototypes to the top of your functionExample.c file and verify this removes compiler messages when int main is moved to the top.

    Categories of function parameters

    There are two kinds of function parameters:

    • Call-by-value parameters, in which the original values do not get modified.

    • Call-by-reference parameters, in which they do get modified.

    All the examples we have seen so far have been call-by-value. Let's look at a classic call-by-reference example: 

    void swap (int *first, int *second)
{
  int temp = *first;
  *first = *second;
  *second = temp;
}


int main ()
{
  int i = 5, j = 6;

  printf ("i=%d j=%d\n", i, j);

  // Pass the addresses to i and j.
  swap (&i, &j);

  printf ("i=%d j=%d\n", i, j);
}
    Note:
    • The parameters to swap are pointers (addresses). 
      void swap (int *first, int *second)

    • To actually access the data, the pointer dereferencing operator must be used, e.g., 
        *first = *second;

    • The call to swap must pass the addresses of the desired target variables: 
        // Pass the addresses to i and j.
  swap (&i, &j);
    Exercise 2.4: Implement the above in swapExample.c. Draw a complete memory picture just before swap() returns. Assume that stack addresses start at 1000 and grow upwards, with integers consuming 4 bytes (32 bits) and pointers using 8 bytes (64 bits).
    STOP! Let's check our work... before continuing.
    Exercise 2.5: What happens in each of the following two modifications of the swap program? Draw a complete memory diagram on your worksheet. Explain why neither of them work in your README. 
    1. void swap1 (int *first, int *second)
{
  int temp = *first;
  *first = *second;
  *second = temp;
}

int main ()
{
  int i = 5, j = 6;
  swap1 (i, j);
  printf ("i=%d j=%d\n", i, j);
}

    2. void swap2 (int first, int second)
{
  int temp = first;
  first = second;
  second = temp;
}

int main ()
{
  int i = 5, j = 6;
  swap2 (i, j);
  printf ("i=%d j=%d\n", i, j);
}
    Keep in mind that both of these programs are legal C code (just with compiler warnings) -- the language will let you make all sorts of mistakes!

    Structs

    About C's struct's:

    • A struct is like a Java object without methods, but only data.

    • A struct lets you group variables into a single unit.

    • To access the individual members of a struct: the struct variable is followed by either
      • the -> operator, when the struct variable is a pointer, or
      • the . operator, when the struct variable is not a pointer.

  • When declaring a new struct variable, the keyword struct must be included as part of the declaration:
    • e.g., struct myStructType a;.
    • Think of the type name as two words, with the first word always being "struct"
    • This can be avoided by using more advanced C features (typedefs), which we will skip in this class.

    Let's look at an example that covers all the basic ideas: 

    struct location {
  char *name;
  float lat;
  float lon;
};

int main() {
  struct location myHouse;
  struct location *DC;
  DC = (struct location*) malloc(sizeof(struct location));
  DC->name = "Washington DC";
  DC->lat = 38.889404;
  DC->lon = -77.035194;

  myHouse.name = "Prof. Wood's Igloo";
  myHouse.lat = 77.828029;
  myHouse.lon = -88.057823;

  printf("I live at %f, %f\n", myHouse.lat, myHouse.lon);
  printf("I commute to %f, %f\n", DC->lat, DC->lon);
}

    Exercise 2.6: Implement the above in structExample.c. Define another pointer based location struct called myHousePtr and make it point to the myHouse variable. Add another print statement that outputs the values for your new struct. What errors do you get if you try to use the wrong operator to access either a pointer or non-pointer based stack?

    Note:

    • Given a pointer-to-struct variable like myHousePtr, an individual member field is read or written using the -> (arrow) operator: 
          myHousePtr->lat = 77.828029;
    • We do not need to put a * operator in front of the struct pointer, the arrow operator handles this for us. Think of the arrow as a sign that you are "following" the struct pointer to the values of its fields.

    • On the other hand, a struct variable like myHouse must use the . (dot) operator. Thus the operator used depends on the variable type (pointer or non-pointer), not on the location of the data (stack or heap).

    • Recall that malloc takes the required space (in bytes) as argument. Since we don't know how many bytes are needed, we use the sizeof operator: 
        DC = (struct location*) malloc(sizeof(struct location));
      where the struct name is passed to sizeof.

    • Similarly the pointer returned by malloc points to a block of bytes, and must be cast into the appropriate pointer type, in this case: a pointer to the struct type.

    Another struct example

    Let's look at an example that should appear vaguely familiar: 

      struct node {            // Definition of a node.
    double data;
    struct node *next;
  };


  struct node* makeNode (double d)
  {
    struct node *nodePtr;

    nodePtr = (struct node*) malloc (sizeof(struct node));  // Observe the size.
    nodePtr->data = d;
    nodePtr->next = NULL;
    return nodePtr;
  }

  void print (struct node *nodePtr)
  {
    printf ("Data= %lf\n", nodePtr->data);
  }


  int main ()
  {
    struct node *first;
    struct node *iterator;

    first = makeNode (0.1);
    print (first);

    first->next = makeNode (0.2);
    first->next->next = makeNode (0.3);
    first->next->next->next = makeNode (0.4);

    iterator = first;
    // WRITE YOUR while-loop here:

  }

    Exercise 2.7: Add a while loop at the end to print each node's data in turn using the iterator pointer so successively points to each node. Write your code in structExample2.c.

    Note:

    • Once again, we've defined the template for a chunk of heap memory: 
      struct node {
  double data;
  struct node *next;
};
      Here we see that each chunk of memory will contain a double data value and a pointer to another struct of the same type.

    • Next, let's observe how malloc was used to create space on the heap: 
        nodePtr = (struct node*) malloc (sizeof(struct node));
      Here:
      • We are giving the size (in number of bytes) to malloc by asking the sizeof-operator to compute the size of heap memory needed for the struct.
      • malloc then creates the space on the heap and returns a pointer to it.
      • Thus, the memory picture after the first call to makeNode() is:

    • Lastly, remember that when we have a pointer, the arrow operator is used to "follow the pointer and get inside to a part of a struct": 
        nodePtr->data = d;          // nodePtr is a pointer.
  nodePtr->next = NULL;

    Exercise 2.8: Fill in the worksheet memory diagram for the stack and the heap immediately before your while loop executes. You do not need to fill in addresses, but you should draw arrows showing what any pointer variables reference, or write NULL for the contents of any uninitialized pointers.
    STOP! Let's take a quiz!

    Global, static, local and parameter variables

    First, we have a new type of variable to learn about. There are four types of declarations in C:

    • Global: variables declared outside functions.

    • Local: variables declared inside functions.

    • Parameter: function parameter variables.

    • Static: variables declared as static inside functions. A static variable retains its last value each time its function is called.

    Let's look at an example: 

    int a = 0;              // Global - accessible anywhere in file.

void test (int b)       // Parameter.
{
  static int c = 0;     // Static - retains its value over successive function calls.
  int d = 0;            // Local.

  if (b >= 0) {
    int e;              // Local inside block (at top of block) - ANSI C99 only.

    e = a + b + c + d;  // a,b,c,d are accessible anywhere in test.
                        // e is accessible only after this declaration inside the if-block.

    printf ("e=%d\n", e);
  }

  c++;
  printf ("c=%d\n", c);
}


int main ()
{
  a++;                  // "a" is accessible in all functions in the file.

  test (1);
  test (2);
}

    Exercise 2.9: Hand-execute the code above and predict what gets printed out in your README. Do you think static variables are stored on the stack? Why or why not?

    Math library (HW)

    C includes a standard math library. Some examples: 

    #include <math.h>       // Must include math.h header!

int main ()
{
  double x = 1.5;
  double y = 2.0;

  printf ("x = %lf   ceil(x) = %lf\n", x, ceil(x) );            // 2.0
  printf ("x = %lf   floor(x) = %lf\n", x, floor(x) );          // 1.0 
  printf ("x = %lf   sqrt(x) = %lf\n", x, sqrt(x) );            // 1.224
  printf ("x = %lf   exp(x) = %lf\n", x, exp(x) );              // 4.481
  printf ("x = %lf   log(x) = %lf\n", x, log(x) );              // 0.405

  x = -1.5;
  printf ("x = %lf   fabs(x) = %lf\n", x, fabs(x) );            // 1.5
  printf ("x = %lf  y = %lf   x^y = %lf\n", x, y, pow(x,y) );   // 2.25
}

    HW Exercise 2.10: In mathproblem.c write a method that computes the sum
          1 + 1/2 + 1/4 + ... + 1/2n
    for any input parameter n.
    Note: To use the math library you must compile your code with the -lm flag. This should be at the end of your gcc command, e.g.: 
      gcc mathproblem.c -o mathproblem -lm

    Meta

    Having gone a bit deeper into C, you might be facing two types of challenges:

    1. Dealing with new syntax and idiosyncrasies about C memory management.
    2. The particular challenge of debugging C.

    It just takes time and practice to get accustomed to a new language, it's syntax, and unusual twists.

    Debugging in C, however, is another matter:

    • C compilers rarely provide much help.
    • It is very easy to make all kinds of errors with variables, pointers, addresses and the like.
    • And hard to find them.
    • The lesson? You need to apply an even more aggressive pro-active debugging strategy (print! print! print!) when writing C.
    • Also, write more comments, even to yourself, so that you understand what you are doing.
    • Finally, the gdb tool is an invaluable resource for understanding exactly what your code is doing -- often it will not be what you expect!

Submission Instructions

Do your work in a repository created using this link.

  • Answer all of the exercise questions above in your README.md file.
  • Add all of your source code files to your git repository. You can do this by running git add *.c when in the same directory to add all files ending in .c. You will then need to use git commit -m "some message" and git push origin master to commit and push your files. Be sure to run git status to verify that all modified files have been committed and pushed.
  • Complete the worksheet as a PDF or Word document. Alternatively you can scan or take a photo of your printed worksheet, but be sure it is clearly legible or you will lose points!
  • Add the completed worksheet to your repository. You can do this through the GitHub website by using the button to "Upload Files". After you add the file, you should use git pull origin master in CodeAnywhere to sync your changes down to your container, otherwise you will not be able to push further commits.
  • You should check the contents of the README.md file and your other C files through the GitHub website to ensure that it has all of your correct content!
Your work will be graded out of 20 points. 1 point will be for the style/formatting of your Markdown (e.g., use appropriate markdown code blocks and headings), and the remaining 19 points will be for completing the exercises fully and correctly.

Previous - Next
© 2003, Rahul Simha (revised 2017). Further revised by Tim Wood 2018.