Lab: Structures, Unions, and Enumerations

For today’s lab you will use a combination of structs, unions, and enums to organize and process data. We’ll start using structs and enums, then look at a different data representation problem where unions are helpful. Follow the instructions below to get started:

1. Go to https://git.cs.grinnell.edu/csc161/structs-unions-enums/ and create a fork of the repository.

2. Add your group members as collaborators on the repository.

3. Navigate to ~/csc161/labs in a terminal and use git to clone your fork of the repository.

4. Open ~/csc161/labs/structs-unions-enums in VSCode.

If you’re unsure how to complete any of these steps, you can go back to our earlier labs for more details.

A. Organizing Data with Structs and Enums

We’ll start this lab by building a simple program that keeps records of connect four games and calculates some simple statistics from those records. To be clear, this is not a required part of your connect four assignment; we’re just using this as a motivation for the kind of record keeping that structs can help with.

Complete the exercises below in the connect-four-stats.c source file included with this lab’s starter code.

Exercises

1. Complete the definition of the type struct c4_game type provided in the starter code. The completed struct should have fields to keep track of the following information:
   • The name of the yellow player (a string)
   • The name of the red player (a string)
   • The number of moves (an integer)
   • The outcome of the game. You’ll need to create a new type called enum c4_result to keep track of the outcome of each game. The enum should have three possible values: C4_YELLOW_WINS, C4_RED_WINS, and C4_TIE. We’re including the C4_ prefix on enum values because so these values won’t conflict with other enums or constants from other parts of the program.

2. Move to the main function and create an array of at least five struct c4_game values. Initialize the array with test data.

3. Write the following functions to compute some basic information from the array of game outcomes, then call each of them from main to test them:
   • float average_move_count(struct c4_game games[], int num_games) should calculate the average number of moves over all the games in the array.
   • float yellow_win_rate(struct c4_game games[], int num_games) should return the win rate (between 0.0 and 1.0) for the yellow player over all games.
   • char* longest_game_winner(struct c4_game games[], int num_games) should return the name of the player who won the game with the most moves. This function should loop over the games array exactly once.

B. Using Structs as Parameters and Return Values

You may have noticed that all three of the functions you wrote to compute statistics over the array of games had a similar structure that loops over the whole array. If we were using this as part of a larger system we would likely want to compute the rate of red wins and ties over all games as well, which would add even more looping over the array of games.

Adding all of these functions may be okay from a code style standpoint, even though they do duplicate some of the looping logic. But looping over the array to compute each statistic is inefficient compared to looping over the array once to compute all the statistics. In the past we used output pointer parameters to functions that “return” multiple values, but we can do this in a cleaner way with structs, especially if we are producing many different outputs.

The exercises below will guide you through two different approaches to producing multiple outputs from a function using structs.

Exercises

1. Add the following struct type to the connect-four-stats.c file:

   struct c4_stats {
     int total_moves;
     float average_moves;
     char* longest_game_winner;
     char* shortest_game_winner;
     float yellow_win_rate;
     float red_win_rate;
     float tie_rate;
   };
   

2. Write a new function that computes statistics for all of the fields in the struct above, and then returns it. The function should have the following signature:

   struct c4_stats compute_c4_stats(struct c4_game games[], int num_games);
   

   Make sure your compute_c4_stats function loops over the games array exactly one time. When you return a struct from a function it makes a copy of the whole struct, so it’s safe to return struct values from functions the same way you can return an int variable or a computed value.

3. Call compute_c4_stats from your main function and print the results. Make sure the statistics are all computed correctly before moving on.

4. Returning a copy of a large struct can be inefficient, so you’ll sometimes see C functions (especially in the standard library) that are written to avoid this copy. Instead of returning the struct, the function will take a pointer to the struct as an output parameter. Add the following function to your code and complete its implementation (based largely on compute_c4_stats):

   void compute_c4_stats_nocopy(struct c4_game games[], int num_games, struct c4_stats* stats);
   

   Hint: It’s a good idea to zero out the stats struct before using it. You can do this with the memset function, which you’ll see used very frequently with struct pointers.

   Hint: You can write (*stats).total_moves to access the total_moves field in the struct that stats points to, but the parentheses make this inconvenient. Luckily, C gives us a new operator to access fields through struct pointers: stats->total_moves will give us the same result, but it’s easier to type and read.

C. Tagged Unions

Unions aren’t used as often as structs in C, but they allow us to do something we used to do all the time in Racket: mixing values of different types. For example, we might have a collection of values to keep track of where some are integers, some are strings, some are floating point values, and so on. We can do this using a union, plus a tag, which is a value that tells us how to interpret the union:

struct value {
  enum {CHAR, INT, FLOAT, STRING} tag;
  union {
    char c;
    int i;
    float f;
    char* s;
  };
};

The top-level type is a struct because we want the tag to be stored separately from the actual value. The stored value is in an anonymous union, which lets you access them with a single dot after a value of type struct value.

As an example, we can use this struct to store a character like this:

struct value v;
v.tag = CHAR;
v.c = 'x';

Designated initializers let us write this more concisely:

struct value v = {.tag = CHAR, .c = 'x'};

Complete the following exercises using the definition of struct value above. Write your code in the unions.c source file included with your starter code.

Exercises

1. Create a variable w of type struct value. Initialize the value so it stores the string “Hello world”.

2. Create a variable x of type struct value that stores the floating point value 3.14159.

3. Create a variable y of type struct value that stores the integer value 3819.

4. Create a variable z of type struct value that stores the string "CSC 161 is fun".

5. Write a function called print_value that takes a struct value parameter and prints it. Your implementation will need to check the value of tag to know how to print the value that was passed in. Test your implementation by printing the values v, w, x, y, and z defined above.

D. Representing Racket/Scheme/Scamper Values

We can extend our simple value type to store another useful type: a pair. If you didn’t notice already, tagged unions work similarly to the values we use in Racket programs, where you aren’t obligated to specify a type ahead of time. Adding a pair type will let us represent pair structures in our C program.

To do this, you’ll need to revise the definition of value and add a pair struct:

// Declare (but do not define) the pair struct.
// This allows us to use the name of this struct later even though we haven't defined it yet.
struct pair;

struct value {
  enum {CHAR, INT, FLOAT, STRING, PAIR, NIL} tag;
  union {
    char c;
    int i;
    float f;
    char* s;
    struct pair* p;
  };
};

struct pair {
  struct value car;
  struct value cdr;
};

This updated definition allows us to create struct value values that hold pairs, as well as a NIL value that represents an empty list. We call this value NIL in our program so its name doesn’t conflict with C’s NULL value.

Using these types, we can now create a pair value like this:

// Create a value to hold the character `a`
struct value a = {.tag = CHAR, .c = 'a'};

// Create a value to hold the value of pi:
struct value pi = {.tag = FLOAT, .f = 3.14159};

// Create a pair holding `a` and `pi`
struct pair p = {.car = a, .cdr = pi};

// Finally, wrap the pair in a value
struct value v = {.tag = PAIR, .p = &p};

While this is admittedly a lot longer than (let v (cons \#a 3.14159) ...), it does allow us to represent the same data as the equivalent Racket code. Despite the difference in verbosity, C and Racket do very similar things here; values in Racket are stored as tagged unions, and pairs will have a very similar structure to what we’re using.

You might find it convenient to write helper functions to produce values, like this one that produces characters:

struct value make_char(char c) {
  struct value v = {.tag = CHAR, .c = c};
  return v;
}

These helpers will work for everything except the PAIR tag because the .p field in struct value is a pointer. As you saw in the example above, the value assigned to .p must be the address of a struct pair, and any address you take inside of a make_pair function would be the address of a local variable that is out of scope when you return.

Use the definitions above to complete the following exercises. Write your code in the source file racket_values.c included with your starter code.

Exercises

1. Why do you think the value p inside of struct value is a pointer type? What will happen if you remove the star from its type? Try making this change to check your guess, then put the star back so your code will compile. Make sure you can explain why the star is necessary before moving on (the instructor or mentor can help if you aren’t able to figure it out).

2. Create a value that holds null in Racket. You’ll need to use the tag NIL for this in our implementation.

3. Create a value equivalent to the list produced by this Racket code:

   (list 3 "hello")
   

   Remember that a list is a pair structure. The list above is equivalent to (cons 3 (cons "hello" null)). Don’t forget that we renamed the Racket value null to the tag NIL above.

4. Write a Racket expression that produces a value containing at least two pairs, then represent it in the C structure we’ve set up.

5. Extend your print_value implementation so it can display values of type NIL and PAIR. You don’t need to print values exactly as Racket would. One good way to print pairs is to wrap them in parentheses and separate the values with a dot. For example, (cons 4 "hello") can be printed as (4 . "hello").