Skip to main content
Logo image

An Introduction to Imperative Programming

Sebastian Hack

Section 4.13 Structs

The second aggregate data type in C that we consider is the struct. Structs are also commonly referred to as record. A struct has \(n\) fields of possibly distinct types \(T_1,\dots, T_n\text{.}\) A container for a struct is the combination of containers for the \(n\) fields. For an example, consider a struct that represents aspects of a person. We want to consider for each person a date of birth, a first name, and a last name.
A date consists of a day, a month, and a year:
struct date {
    unsigned day, month, year;
};
Run
We can use composition (“is part of”) or aggregation (“refers to”) to define our struct:
struct person {
    struct date date_of_birth;
    char name[16];
    char surname[16];
};
Run
Listing 4.13.1. Composition
struct person {
    struct date date_of_birth;
    char const *name;
    char const *surname;
};
Run
Listing 4.13.2. Aggregation
In both declarations, the date_of_birth field is added through composition. We could also implement the field via aggregation with a pointer to a date struct. However, the struct date is a small struct, therefore referencing it with a pointer saves little space in the person struct. Reusing struct date objects provides therefore little benefit for this case.
We can access the individual fields of a struct container with the . operator:
struct person p;
/* ... */
printf("%s %s\n", p.name, p.surname);
Run
In contrast to arrays, structs can be passed to functions by value in C. With small structs, this can be sensible. In practice however, we usually pass structs via pointer as in the following example:
void init_date(struct date *d, unsigned day,
                unsigned month, unsigned year)
{
    d->day = day;
    d->month = month;
    d->year = year;
}
Run
The expression A->B is an abbreviation for (*A).B.

Remark 4.13.3.

In C, suffix operators have higher precedence than prefix operators. Therefore, *A.B is not the same as (*A).B: The former accesses a struct field and loads from the address contained there, the latter loads the field of a struct whose address is given. In practice, it is best to use parentheses to make non-obvious precedences explicit.

Subsection 4.13.1 typedef

Types in C can easily become long, like struct person, or complex, like int *(*)[10]. C provides the means to define shorter, more meaningful names for such types:
typedef struct {
    /* see above */
} person_t;

/* ptr_table_t ist a pointer to an array
    of 10 pointers to ints */
typedef int *(*ptr_table_t)[10];
Run

Example 4.13.4. Initialization.

It is a common pattern to define for each struct a function that properly initializes it. The following function initializes the version of struct person where name and surname are aggregated:
person_t *person_init(person_t *p, date_t const *d,
                      char const *name, char const *surname)
{
    p->date = *d;
    p->name = name;
    p->surname = surname;
    return p;
}
Run
Such initialization functions, which are also called constructors, usually expect a pointer to an uninitialized struct container. This makes the constructor independent of how the struct is allocated: as a local variable, a global one, or dynamically:
person_t global_p;
void person_test() {
    person_t local_p;
    person_t *heap_p;

    heap_p = malloc(sizeof(*heap_p));

    person_init(&global_p, /* ... */);
    person_init(&local_p, /* ... */);
    person_init(heap_p, /* ... */);

    free(heap_p);
}
Run
If we incorporate the name and surname fields by composition instead of aggregation, we need to copy the character sequences into the struct:
person_t *person_init(person_t *p, date_t const *d,
                      char const *name, char const *surname)
{
    p->date = *d;
    snprintf(p->name,    sizeof(p->name),    "%s", name);
    snprintf(p->surname, sizeof(p->surname), "%s", surname);
    return p;
}
Run
It is important to not copy more characters than fit into the field. We realize this here with the snprintf function with the size sizeof(p->name). If we copied the string without ensuring that the field size is respected, we would encounter undefined behavior (see Section 4.15) when the function is called with too large strings. We can use sizeof here because the type of p->name here is char[16] and not char *. The value of sizeof(p->name) is therefore \(16\text{,}\) rather than the size of a pointer.

Example 4.13.5. Polynomials.

The following struct represents a polynomial of degree n:
typedef struct {
  unsigned degree;
  int *coeffs;
} poly_t;
Run
The coefficients are implemented through aggregation. This is necessary, since we do not want to assume a statically known fixed length for the polynomials. Therefore, an array for the coefficients need to be allocated separately (see Exercise 4.13.3.1).

Subsection 4.13.2 Incomplete Structs

We use a technique called encapsulation to separate large software systems into modules. By encapsulation, we hide the implementation details of a module from code that uses it. The benefit of this technique is that we can then change the module's implementation without affecting the code parts that use the module.
C supports encapsulation through incomplete structs. They allow to hide the specific structure of a struct from other code. We will discuss encapsulation in more detail in the Java part of this book.
Consider Example 4.13.5. Let us assume that we want to hide how polynomials are represented from using code parts. We achieve this with an incomplete struct that we declare in a header file (see poly.h in Figure 4.13.6). The values of the data type are then only accessible through a set of functions, a so-called Application Programming Interface (API). The API of such a data type only uses pointers to the incomplete type as the encapsulation ensures that its contents, and therefore the necessary container size, are not known to the outside. 
#ifndef POLY_H
#define POLY_H

/* incomplete struct */
typedef struct poly_t poly_t;

poly_t *poly_alloc(unsigned degree);
void poly_free(poly_t *p);
void poly_set_coeff(poly_t *p, unsigned deg,
                    int coeff);
int poly_eval(poly_t const *p, int x);
unsigned poly_degree(poly_t const *p);

#endif /* POLY_H */
Run
(a) poly.h
#include "poly.h"

struct poly_t {
    unsigned degree;
    int *coeffs;
};
Run
(b) poly.c. Continuation: Exercise 4.13.3.1
#include <stdlib.h>
#include <stdio.h>
#include "poly.h"

int main(int argc, char *argv[])
{
    if (argc < 3) {
        fprintf(stderr, "syntax: %s x coeffs...",
                argv[0]);
        return 1;
    }

    poly_t *p = poly_alloc(argc - 3);
    for (int i = 2; i < argc; i++) {
        int coeff = atoi(argv[i]);
        poly_set_coeff(p, i - 2, coeff);
    }
    int x = atoi(argv[1]);
    int y = poly_eval(p, x);
    poly_free(p);
    printf("%d\n", y);
    return 0;
}
Run
(c) main.c
Figure 4.13.6. Implementation of polynomials with encapsulation. The internal structure of the struct poly_t is only visible in the translation unit poly.c.

Exercises 4.13.3 Exercises

1. Polynomial.

We consider the API for polynomials defined in Figure 4.13.6. Complete the file poly.c: Implement the functions declared in the header file poly.h in.
  1. Implement a function poly_alloc allocating the space for a polynomial on the heap.
  2. Implement the function poly_free, that frees a polynomial that was constructed on the heap.
  3. Implement the function poly_set_coeff that sets the coefficients of an polynomial.
  4. Implement the evaluation of a polynomial using the Horner schema.
  5. Implement the function poly_degree that returns the degree of a polynomial.
202412201714
Solution.
#include <stdlib.h>
#include <assert.h>

#include "poly.h"

struct poly_t {
    unsigned degree;
    int *coeffs;
};

poly_t *poly_alloc(unsigned degree) {
    poly_t *p = malloc(sizeof(*p));
    p->degree = degree;
    p->coeffs = malloc((degree + 1)
              * sizeof(p->coeffs[0]));
    return p;
}

void poly_free(poly_t *p) {
    free(p->coeffs);
    free(p);
}

void poly_set_coeff(poly_t *p, unsigned i,
                    int val) {
    assert(i <= p->degree);
    p->coeffs[i] = val;
}

int poly_eval(poly_t const *p, int x) {
    int res = p->coeffs[0];
    for (unsigned i = 1; i <= p->degree; i++)
        res = res * x + p->coeffs[i];
    return res;
}
Run
<Prev^TopNext>