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;
};
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];
};
struct person {
struct date date_of_birth;
char const *name;
char const *surname;
};
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);
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;
}
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];
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;
}
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);
}
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;
}
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;
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 */
poly.h#include "poly.h"
struct poly_t {
unsigned degree;
int *coeffs;
};
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;
}
main.cpoly_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.
Implement a function
poly_allocallocating the space for a polynomial on the heap.Implement the function
poly_free, that frees a polynomial that was constructed on the heap.Implement the function
poly_set_coeffthat sets the coefficients of an polynomial.Implement the evaluation of a polynomial using the Horner schema.
Implement the function
poly_degreethat returns the degree of a polynomial.
#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;
}