CS211: Struct

C provides only a select few predefined types: char, int, float, double. Some of these types can be further modified to represent long and short versions, as well as be made signed or unsigned. Every element type can be represented as a pointer using the * delcarator. There's even a type that represents the "absence" of a type with void. For many programmers, this simply isn't enough. C also furnishes space for those wish to go a bit further with the addition of structs.

A struct is an aggregate data type defined by the programmer which combines other predefined data types into one larger grouping. From the C specification:

A structure type describes a sequentially allocated nonempty set of member objects (and, in certain circumstances, an incomplete array), each of which has an optionally specified name and possibly distinct type.

The above technical definition sounds a bit scarier than it is. Here is an example of a struct declaration:

1:   struct frac{
2:   int n;   // Numerator
3:   int d;   // Denominator
4: };

Here, I declare a new data type called struct frac which contains two member variables, n and d. I can declare a variable of type struct frac like this (assuming the struct has already been declared above):

1: int main(){
2:   struct frac f; // Declaring a variable "f" of type "struct frac"
3:   f.n = 1;       // Using "." to reference member "n"
4:   f.d = 2;       // Using "." to reference member "d"
5: }
6: 

The code above shows the declaration of a variable f of type "struct frac" and the setting of both of its member variables.

Much like arrays, initialization lists can be used to set the members:

1: int main(){
2:   struct frac f = {1, 2};
3: }

Above, n and d are set using the initilization list. Initilization lists will set the values in the same order in which they were defined ({1,2} will match {n,d}).

In order for structs to function as data types in C there size must be known at compile time. This can be seen in Line 9 of 5 which shows that the built-in gcc macro sizeof is capable of being applied to the user-defined struct symbol. The size of structs are not always obvious a priori. For example, take the following struct definitions and the results of sizeof on each of them:

 1: #include <stdio.h>
 2: struct padded {
 3:     char  a;  // 1 byte  -- offset 0
 4:               // 3 bytes padding
 5:     int   b;  // 4 bytes -- offset 4
 6:     char  c;  // 1 byte  -- offset 8
 7:               // 7 bytes padding
 8:     double d; // 8 bytes -- offset 16
 9: };            // total: 24 bytes
10: 
11: struct packed {
12:     double d; // 8 bytes -- offset 0
13:     int    b; // 4 bytes -- offset 8
14:     char   a; // 1 byte  -- offset 12
15:     char   c; // 1 byte  -- offset 13
16:               // 2 bytes padding
17: };            // total: 16 bytes
18: 
19: int main(){
20:   printf("%lu\n", sizeof(struct padded));  // 24
21:   printf("%lu\n", sizeof(struct packed));  // 16
22: }

1: josephraskind@stargazer:/tmp/struct$ gcc struct_size.c -o size; ./size
2: 24
3: 16

These results are for my x86-64 machine—it could be different depending on the architecture. The padding is a result of the natural word size of x86-64 machines being 8 bytes long. The architecture expects each variable to be aligned 4/8 byte boundaries, so the C compiler which targets x86-64 will comply by stuffing "padding" bits in the slots in between.

There are ways of overriding bit padding, but they are well outside the scope of this class.

1. Implement the following functions for the frac struct defined in Listing 3:

   • print_frac — prints the fraction in the form n/d
   • add_frac — adds two fractions and returns the result
   • mul_frac — multiplies two fractions and returns the result
   • simplify — divides numerator and denominator by their GCD

   Test each with at least two examples and verify the results by hand.

2. Using typedef as shown in Listing 4, rewrite your solutions from exercise 1 so that struct frac is replaced with the alias frac throughout. How does this change the readability of your code?

3. Extend the frac struct with two more functions:

   • sub_frac — subtracts one fraction from another
   • div_frac — divides one fraction by another by multiplying by the reciprocal

   Verify that div_frac(add_frac(f1, f2), f2) returns the same value as f1 for a few test cases.

4. Using malloc and the -> operator as shown in Listing 5, allocate a frac on the heap, set its members, pass it to print_frac, and free it. Run the program under valgrind to confirm there are no memory leaks.
5. Write a program that declares an array of five frac structs, initializes each using an initialization list, and prints them all using print_frac. Then write a function sum_all that takes an array of frac structs and its length and returns their sum as a single frac.
6. Compile Listing 10 on your machine and verify the sizeof outputs match those shown in Listing 11. Then use offsetof from <stddef.h> to print the byte offset of each member in both struct padded and struct packed. Do the offsets match the comments in the listing?
7. Design a new struct struct packed_frac that reorders the members of struct frac to minimize padding. Is it possible to reduce the size below what the default layout produces? Use sizeof and offsetof to verify your answer.
8. The lecture shows in Listing 6 that using a plain array instead of a struct loses type information. Reproduce this example and compile it. Then alter it to use the frac struct as in Listing 8 and compare the compiler output. In your own words, explain what the struct provides that the array does not.

9. Consider the following attempted self-referencing struct:

   struct frac {
       int n;
       int d;
       struct frac next;
   };
   

   Try to compile it and record the error. Explain why C cannot allow a struct to contain a member of its own type directly. Then fix it by replacing struct frac next with struct frac *next and explain why the pointer version works where the direct member does not.

10. Implement a simple family tree using a self-referencing struct:

    struct person {
        char name[50];
        int  age;
        struct person *parent;
    };
    

    Create at least three generations, link them together using the parent pointer, and write a function print_ancestors that walks up the chain printing each person's name and age until it reaches a NULL parent pointer.