Computer Science 381
Programming Unix in C

Fall 2013, The College of Saint Rose

Lab 7: Structures in C
Due: 11:59 PM, Thursday, October 24, 2013

In this week's lab you will learn about the make utility, then about C structures, a simple mechanism that allows heterogeneous data fields to be grouped into a single entity.

Using the make Utility

Any non-trivial software development involves many iterations of editing, compiling, linking, and running your programs. The code will be spread across multiple files. The most common mechanism for managing this process when programming in C in a Unix environment is the make utility. The actions of make are specified by rules in a Makefile.

Copy the following example to your account:

See Example:

You should find a small C program that demonstrates the use of multiple source files and a Makefile. Compile the program by issuing the make command. Capture the output of the command in make.out:

make > make.out

Output Capture: make.out for 2 point(s)

Now, look at the contents of make.out, then at the rules and the description in the Makefile.

Question 1: Briefly describe how make uses the rules in the Makefile to produce the executable main. Be sure to include the series of targets, their dependencies, and the commands used to satisfy those dependencies for each target. (5 points)

From this point forward, you should write a Makefile for each of your programs. You are strongly encouraged to do this when you first start each program rather than at the end - it is intended to be a tool to speed your development process, so use it that way!

Programs in Multiple Files

The make example above also demonstrated a very simple case of C code being separated into multiple .c (implementation) and/or .h (header) files.

We next consider an unnecessarily complicated C program that computes the greatest common denominator of two integer values that further illustrates this idea.

See Example:

There are lots of things to notice here:

Question 4: Draw a memory diagram for this program for the case where the numbers entered are 9 and 24. Your diagram should show the state of memory (including all copies of the parameters to each gcd recursive call that exist on the call stack) at the point where the "return b" statement is about to be executed during the base case of the recursion. (7 points)

C structs

In addition to the readings from Chapter 6 of K&R, the following (somewhat silly) example should help you understand structures in C.

See Example:

Again, we have a number of C source code (.c) and header (.h) files. We will consider each in turn.

The files gcd.h and gcd.c are the same as the ones you saw earlier in this lab.

The files ratio.h and ratio.c define a structure and a number of functions that have to do with storing a ratio of two integer values.

In ratio.h, we have the definition of the structure that will hold our ratios:

typedef struct ratio {
  int numerator;
  int denominator;
} ratio;

There are two important things happening here. First, a structure called a struct ratio is defined. It consists of two int values: numerator and denominator. In many ways, these are like the instance variables of a Java class, but there are no access protections (i.e., they are not "private" or "protected", but the equivalent of "public"). Second, we are giving another (shorter) name to our struct ratio: simply ratio. This is being accomplished by the typedef. In general, a typedef can define a new name for any type:

typedef x y;

would define a new type named y which is just another name for an already-existing type named x.

In our case, the typedef just means we can refer to variables and parameters of type struct ratio as simply ratio.

The rest of the contents of ratio.h defines function prototypes for the functions that will be defined in ratio.c that can be called from elsewhere.

As a whole, the information in ratio.h tells a C source file that would like to work with these ratio structures everything it needs to know to compile.

In ratio.c, the four functions that operate on ratios are defined: create_ratio constructs a new ratio given a numerator and a denominator, add_ratios takes two existing ratios, adds them and constructs and returns a new ratio that represents their sum in lowest terms, reduce_ratio takes an existing ratio and reduces it to lowest terms, and finally, print_ratio takes an existing ratio and prints it in a reasonably nice format.

There are a number of things to consider in these functions. The first two functions return a value of type ratio *. This indicates a pointer to a ratio structure. The last three functions take one or two parameters of this same type, ratio *.

Perhaps the most important thing to note here is how we allocate the memory for these structures. In both create_ratio and add_ratios, we see the line:

  ratio *r = (ratio *)malloc(sizeof(ratio));

You have already seen malloc, but this usage is C's way of doing the equivalent of a Java new operation. This line:

  1. declares a variable r of type ratio *
  2. initializes r to the return of the function malloc
  3. malloc reserves a chunk of memory of the requested number of bytes and returns a pointer to the start of the memory segment
  4. the sizeof operator determines the number of bytes in the type to which it applies - in this case ratio, which should be a total of 8 bytes
  5. since malloc does not return a ratio * (it returns a void *, which is a generic pointer), we need the cast to tell the compiler that we will be treating this newly-allocated chunk of memory as a ratio *

Note also the way we refer to the fields of the ratio structure when the variable r contains a pointer to a ratio:

  r->numerator = numerator;

This is functionally the equivalent of the Java statement:

  r.numerator = numerator;

However, since C allows a variable referring to a structure to be either a pointer or the structure itself, there are two different notations. If we had a variable r of type ratio rather than ratio *, we would use the "dot" notation like we use in Java. But here, since we have pointers, we use the "arrow" notation.

Recall the very important difference between C and Java that dynamically allocated memory in C is not garbage collected. That means that every chunk of memory we obtain with malloc must be returned to the system for reuse by a call to the function free. In our case, these free calls are made in ratio_example.c. For each call to create_ratio or add_ratios, which each contain a call to malloc, there must be a corresponding call to free.

This brings us to the file ratio_example.c, which is a main function that makes use of the ratio structure and functions to demonstrate the complexities of C memory management.

Read over the comments in ratio_example.c and see if you can understand how the memory is being allocated and managed.

Question 5: Draw a series of memory diagrams showing the contents of memory (both stack variables and the memory allocated in the heap) right before the return statement in each call to add_ratios (so, 2 separate diagrams), and then right before the return statement at the end of main. (12 points)

Programming Assignment

Write a new driver program (C file with a main function) sum_ratios.c that reads in a series of lines representing ratios from an input file and prints the sum of those ratios in lowest terms at the end.

The program is worth 20 points.

The executable for the reference solution to this program is available on mogul in /home/cs381/labs/structs.


Please submit all required files as email attachments to terescoj AT by 11:59 PM, Thursday, October 24, 2013. Be sure to check that you have used the correct file names and that your submission matches all of the submission guidelines listed on the course home page.


Grading Breakdown

Lab questions and output captures 30 points
sum_ratios.c correctness 10 points
sum_ratios.c error checking 2 points
sum_ratios.c memory management 2 points
sum_ratios.c documentation 3 points
sum_ratios.c style 2 points
Makefile for ratios program 1 point