Arrays of Structures

Part I · Module 10 · Chapter 10.6 · Arrays of Structures

1. Nothing New Is Required

    struct reading table[4];

That is an array declaration from Chapter 6.2 whose element type happens to be a structure. Everything Module 6 established applies without amendment: the elements are contiguous, indices run from 0 to n-1, the array cannot be assigned as a whole, and it decays to a pointer to its first element when passed to a function (Chapter 7.6).

Everything Chapter 10.5 established applies too, and it is the fact that makes the array work: the distance from one element to the next is sizeof(struct reading), tail padding included. That was measured in Chapter 10.5 §4 and it is why table[i] can be computed at all.

So this chapter has no new syntax to teach. It has combinations to teach, and they are the ones C programs are built out of.

2. Declaring and Initialising a Table

    struct reading table[] = {
        { .id = 7, .value = 70, .grade = 'a' },
        { .id = 3, .value = 30, .grade = 'b' },
        { .id = 9, .value = 90, .grade = 'c' },
        { .id = 1, .value = 10, .grade = 'd' },
    };
    size_t n = sizeof table / sizeof table[0];

n = 4, sizeof table = 48, sizeof table[0] = 12

Four things are being reused at once.

The size is omitted and derived from the initialiser — Chapter 6.2's int a[] = {...} rule, which applies to any element type.

Each element uses designated initialisers — Chapter 10.2 §6's discipline, and it matters more here than anywhere, because a table has the initialiser repeated many times. If a member is reordered, every row is silently permuted at once.

The element count comes from sizeof table / sizeof table[0] — Chapter 6.1's idiom. 48 / 12 = 4, and note that it works correctly even though each element has three bytes of padding in it, because both halves of the division include the padding.

The trailing comma after the last element is legal and worth keeping. Adding a row later then touches one line instead of two.

Any member you leave out of a row is zero-initialised, and so is any row you leave out entirely:

    struct reading sparse[4] = {
        [2] = { .id = 9, .value = 90 },      /* rows 0, 1 and 3 are all zero */
    };

The [2] = form is a designated initialiser for an array index, the array counterpart of .member. It is useful when a table is indexed by something meaningful — an error code, a small enumeration — and most entries are defaults.

3. Two Ways to Traverse

Both of these are idiomatic C and you will read both constantly.

    /* by index */
    for (size_t i = 0; i < n; i++) {
        printf(" %d", table[i].value);
    }

    /* by pointer */
    for (const struct reading *p = table; p != table + n; p++) {
        printf(" %d", p->value);
    }

They do the same thing. p++ advances by one whole struct reading — 12 bytes here — because Chapter 7.8 established that pointer arithmetic is in units of the pointed-to type, and Chapter 10.5 established that the unit includes padding.

Use the index form when the position means something — printing a row number, correlating with another array, computing a neighbour. Use the pointer form when you are simply visiting each record. Neither is faster in any way you can rely on; both compile to much the same thing.

Note the pointer form's bound. table + n is the one-past-the-end pointer, which Chapter 9.11 §2 established may be formed and compared but never dereferenced. The loop never dereferences it, because p != table + n fails first.

4. Passing a Table to a Function

#include <stdio.h>

struct reading { int id; int value; char grade; };

static void print_table(const char *tag, const struct reading *t, size_t n)
{
    printf("%-10s", tag);
    for (size_t i = 0; i < n; i++) {
        printf(" %d/%d/%c", t[i].id, t[i].value, t[i].grade);
    }
    printf("\n");
}

static int total_value(const struct reading *t, size_t n)
{
    int sum = 0;
    for (const struct reading *p = t; p != t + n; p++) {
        sum += p->value;
    }
    return sum;
}

static const struct reading *find_by_id(const struct reading *t, size_t n, int id)
{
    for (size_t i = 0; i < n; i++) {
        if (t[i].id == id) { return &t[i]; }
    }
    return NULL;                       /* a deliberate "not found" — Chapter 7.4 */
}

int main(void)
{
    struct reading table[] = {
        { .id = 7, .value = 70, .grade = 'a' },
        { .id = 3, .value = 30, .grade = 'b' },
        { .id = 9, .value = 90, .grade = 'c' },
        { .id = 1, .value = 10, .grade = 'd' },
    };
    size_t n = sizeof table / sizeof table[0];

    print_table("table:", table, n);
    printf("total value = %d\n", total_value(table, n));

    const struct reading *hit = find_by_id(table, n, 9);
    if (hit != NULL) {
        printf("found id 9 at index %td, value %d\n", hit - table, hit->value);
    }
    if (find_by_id(table, n, 42) == NULL) {
        printf("id 42 is not in the table\n");
    }

    printf("address gap between table[0] and table[1] = %td bytes\n",
           (char *)&table[1] - (char *)&table[0]);

    return 0;
}

Output:

table:     7/70/a 3/30/b 9/90/c 1/10/d
total value = 200
found id 9 at index 2, value 90
id 42 is not in the table
address gap between table[0] and table[1] = 12 bytes

Four habits in that program are the ones to copy.

Every table parameter is a pointer and a count, together, always — Chapter 7.7's pairing. There is no other way to tell a function how long a table is.

Every read-only table parameter is const. Chapter 7.11's promise and Chapter 9.8 §7's borrow signal. In a function taking several tables it is the only thing distinguishing the one being written from the ones being read.

find_by_id returns a pointer, or NULL for "not found". This is Chapter 7.4's null pointer used as a deliberate value rather than a failure, and it is better than returning an index because there is no sentinel index to invent and no ambiguity about -1 in a size_t.

hit - table recovers the index. Chapter 7.8's pointer difference, which is exactly what you want when a caller needs the position after all. Its type is ptrdiff_t, printed with %td.

5. The One Place the Count Idiom Breaks

sizeof table / sizeof table[0] is correct in the scope where table is declared as an array. It is wrong anywhere the array has decayed.

#include <stdio.h>
struct reading { int id; int value; char grade; };

static void wrong(const struct reading t[])       /* looks like an array; is a pointer */
{
    printf("  inside: sizeof t = %zu, sizeof t[0] = %zu, quotient = %zu\n",
           sizeof t, sizeof t[0], sizeof t / sizeof t[0]);
}

int main(void)
{
    struct reading table[4] = { {1,10,'a'}, {2,20,'b'}, {3,30,'c'}, {4,40,'d'} };
    printf("in main: sizeof table = %zu, sizeof table[0] = %zu, quotient = %zu\n",
           sizeof table, sizeof table[0], sizeof table / sizeof table[0]);
    wrong(table);
    return 0;
}

in main: sizeof table = 48, sizeof table[0] = 12, quotient = 4
  inside: sizeof t = 8,  sizeof t[0] = 12, quotient = 0

Inside the function the quotient is zero — 8 divided by 12. A loop bounded by it runs no iterations at all, which is the quiet kind of wrong: no crash, no warning at run time, just a function that silently does nothing.

The parameter was even written as const struct reading t[]. Chapter 7.7 §3 established that the brackets are cosmetic — a parameter declared as an array is a pointer — and this is the measurement that makes the consequence concrete.

The compiler does help here:

warning: sizeof on array function parameter will return size of
         'const struct reading *' instead of 'const struct reading[]'
         [-Wsizeof-array-argument]
warning: 'sizeof t' will return the size of the pointer, not the array itself
         [-Wsizeof-pointer-div]

Three warnings on two lines, at -Wall -Wextra, and -Wsizeof-pointer-div fires for a plainly-declared const struct reading *p parameter too. So this is a trap the standard warning level catches — unlike most of the ones in Module 9 — provided you are reading your warnings.

Compute the count once, in the scope that declares the array, and pass it everywhere. That rule makes the warning unnecessary rather than merely heeded.

6. A Second Arrangement: An Array of Pointers

A table of records can also be approached through an array of pointers to records, which is Chapter 7.9's array of pointers with a structure as the target.

#include <stdio.h>

struct reading { int id; int value; char grade; };

int main(void)
{
    struct reading table[4] = {
        { 7, 70, 'a' }, { 3, 30, 'b' }, { 9, 90, 'c' }, { 1, 10, 'd' },
    };

    struct reading *view[4] = { &table[0], &table[1], &table[2], &table[3] };

    printf("sizeof table = %zu  (4 x %zu, contiguous)\n", sizeof table, sizeof table[0]);
    printf("sizeof view  = %zu  (4 x %zu, pointers)\n",   sizeof view,  sizeof view[0]);

    for (int i = 0; i < 3; i++) {                     /* sort the view by id */
        for (int j = 0; j < 3 - i; j++) {
            if (view[j]->id > view[j + 1]->id) {
                struct reading *t = view[j]; view[j] = view[j + 1]; view[j + 1] = t;
            }
        }
    }

    printf("table order (untouched):");
    for (int i = 0; i < 4; i++) { printf(" %d", table[i].id); }
    printf("\nview order  (sorted)   :");
    for (int i = 0; i < 4; i++) { printf(" %d", view[i]->id); }
    printf("\n");

    for (int i = 0; i < 3; i++) {              /* re-sort the view by value, desc */
        for (int j = 0; j < 3 - i; j++) {
            if (view[j]->value < view[j + 1]->value) {
                struct reading *t = view[j]; view[j] = view[j + 1]; view[j + 1] = t;
            }
        }
    }
    printf("view by value desc     :");
    for (int i = 0; i < 4; i++) { printf(" %d", view[i]->value); }
    printf("\n");

    return 0;
}

Output:

sizeof table = 48  (4 x 12, contiguous)
sizeof view  = 32  (4 x 8, pointers)
table order (untouched): 7 3 9 1
view order  (sorted)   : 1 3 7 9
view by value desc     : 90 70 30 10

The records never moved. table is still in its original order, and the view was sorted twice by two different keys.

The interesting property is not that a swap moves 8 bytes instead of 12. It is that the records have one home and the orderings are separate objects. You can hold several views of one table at once — by id, by value, filtered to the ones that matter — and any pointer anybody else is holding into the table stays valid, because nothing was rearranged.

The trade is real and runs the other way too:

Default to the array of structures. It is simpler, it is denser, it has no extra lifetime to manage, and a traversal walks straight through memory. Reach for the pointer array when you need several orderings at once, when records must keep their addresses because something else points at them, or when the records are large enough that moving them is genuinely the cost.

And note the Module 9 obligation that comes with the second form: if those records were allocated individually, the pointer array holds borrows and something else owns them — Chapter 9.8's distinction, and freeing through a view is how a double free gets written.

7. A Table Whose Size Is Not Known in Advance

Nothing new here either; it is Chapter 9.6 and Chapter 9.7 with a structure as the element type.

#include <stdio.h>
#include <stdlib.h>

struct reading { int id; int value; char grade; };

/* 9.7 §7's shape exactly: new variable, check, then commit */
static int grow(struct reading **t, size_t new_count)
{
    struct reading *attempt = realloc(*t, new_count * sizeof **t);
    if (attempt == NULL) { return 0; }
    *t = attempt;
    return 1;
}

int main(void)
{
    size_t cap = 2, used = 0;

    struct reading *t = malloc(cap * sizeof *t);
    if (t == NULL) { return 1; }

    for (int k = 1; k <= 5; k++) {
        if (used == cap) {
            if (!grow(&t, cap * 2)) { free(t); return 1; }
            cap *= 2;
            printf("capacity now %zu (%zu bytes)\n", cap, cap * sizeof *t);
        }
        t[used].id    = k;
        t[used].value = k * 11;
        t[used].grade = (char)('a' + k - 1);
        used++;
    }

    printf("%zu records:", used);
    for (size_t i = 0; i < used; i++) {
        printf(" %d/%d/%c", t[i].id, t[i].value, t[i].grade);
    }
    printf("\n");

    free(t);
    return 0;
}

Output:

capacity now 4 (48 bytes)
capacity now 8 (96 bytes)
5 records: 1/11/a 2/22/b 3/33/c 4/44/d 5/55/e

Everything load-bearing was established in Module 9 and is used here unchanged: sizeof *t rather than sizeof(struct reading) (9.6 §4), check every allocation (9.6 §3), grow puts realloc's result in a new variable and commits only on success (9.7 §7), and one owner, one free (9.8). The element type being a structure changes none of it.

8. What You Should Be Able to Say Now

1. An array of structures is an ordinary array — contiguous, zero-based, decays to a pointer, cannot be assigned whole.
2. The stride is sizeof the structure, padding included — measured, 12 bytes.
3. struct T table[] = { ... } derives the size; use designated initialisers in every row, and [i] = { ... } to place a row by index.
4. Two traversal idioms: by index when the position means something, by pointer when you are simply visiting each record.
5. The pointer form's bound is one past the end — may be compared, never dereferenced.
6. Pass a pointer and a count, always; mark read-only tables const.
7. Return a pointer or NULL from a search; recover the index with hit - table.
8. Measured: the count idiom gave 4 in main and 0 inside the function — and -Wsizeof-array-argument / -Wsizeof-pointer-div do report it.
9. Compute the count once, where the array is declared.
10. An array of pointers gives one set of records several orderings at once, with records never moved and their addresses stable — measured, two different sorts of one untouched table.
11. Default to the array of structures; it is denser, simpler and contiguous.
12. Growing a table invalidates every pointer into it — hold indices across a growth.

9. Exercises

Exercise 1 — declare the tables. Write the declaration and initialiser for each, using designated initialisers and deriving the size.

• three points: (0,0), (1,2), (3,5)
• a four-entry table of error records where only entry [2] is filled in
• an empty table of eight readings, all members zero

Exercise 2 — both traversals. Write a function that returns the highest value in a table, twice: once with the index idiom and once with the pointer idiom. Say which you would ship and why.

Exercise 3 — find the silent no-op. This compiles and never does anything. Explain why, give the measured quotient from §5, and fix it.

void scale_all(struct reading t[], int k)
{
    for (size_t i = 0; i < sizeof t / sizeof t[0]; i++) { t[i].value *= k; }
}

Exercise 4 — fix the signatures. Add const and a count wherever they belong, and say what each corrected signature now promises.

int  sum_values(struct reading *t);
void sort_table(struct reading *t, size_t n);
int  count_grade(struct reading *t, size_t n, char g);

Exercise 5 — return a pointer. Rewrite find_by_id to return an index instead of a pointer. Give two problems that creates, and say which chapter's rule the pointer version is using instead.

Exercise 6 — choose the arrangement. For each, say whether you would use an array of structures or an array of pointers, and why.

• 10,000 sensor readings, summed once per second
• 200 records displayed in four user-selectable sort orders
• 50 records, each of which a scheduler elsewhere holds a pointer to
• 3 configuration blocks, read at startup and never changed

Exercise 7 — the growth hazard. This has a bug that appears only when the table grows. Name it, name the two chapters that explain it, and give the fix that does not require re-running the search.

struct reading *hit = find_by_id(t, used, 9);
if (!grow(&t, cap * 2)) { return -1; }
cap *= 2;
hit->value = 0;

Exercise 8 — count the bytes. A table holds 100,000 records of struct reading as declared in §2. Give its total size, the number of bytes that are padding, and the size after applying Chapter 10.5's reordering advice.

10. Summary

• An array of structures is an ordinary array; the stride is sizeof, padding included.
• Derive the size with [], and use designated initialisers in every row.
• Index form when the position matters; pointer form when visiting each record. The bound is one past the end.
• Pointer plus count, always; const on every read-only table.
• A search returns a pointer or NULL; hit - table gives the index.
• Measured: the count idiom gave 4 outside and 0 inside — and the compiler does warn. Compute it once, where the array is declared.
• An array of pointers gives several orderings of one table, records unmoved and addresses stable — measured.
• Default to the array of structures; reach for pointers for multiple orderings or stable addresses.
• Allocation is Module 9 unchanged: sizeof *t, check, commit on success, one owner.
• Growing invalidates every pointer into the table — hold indices.

Every structure so far has been a thing with several parts, all present at once: a reading has an id and a value and a grade. There is a second shape that real data takes, and C has a separate construct for it — a thing that is one of several possibilities, never more than one at a time. A message that is either a status or an error. A value that is either an integer or a float, depending on a tag that travels with it. Declaring that as a structure wastes the space of every alternative you did not take, and C's answer is a type whose members all begin at offset zero and share the same storage. It saves exactly what you would expect, it introduces exactly one hard question — how you are supposed to know which member is currently valid — and the rules about reading a member you did not write are the subject of the next chapter, where they differ between C and C++ and between one C standard and the next.