CS 208 s21 — Learning Block #3

Table of Contents

1 Practice

  • how would you declare an array of three strings (i.e., what is the type signature)?1
  • how many bytes does it take to represent the string "strangelove" in C?2
  • how would you define a struct to represent a 2D point?3

2 typedef

It's common to use typedef to give the struct type a more concise alias. A typedef statement introduces a shorthand name for a type. The syntax is… 

typedef <type> <name>;

The following defines Fraction type to be the type (struct fraction). C is case sensitive, so fraction is different from Fraction. It's convenient to use typedef to create types with upper case names and use the lower-case version of the same word as a variable. 

typedef struct fraction Fraction;
Fraction fraction;      // Declare the variable "fraction" of type "Fraction"
                        // which is really just a synonym for "struct fraction".

The following typedef defines the name Tree as a standard pointer to a binary tree node where each node contains some data and "smaller" and "larger" subtree pointers. 

typedef struct treenode* Tree;
struct treenode {
    int data;
    Tree smaller, larger;        // equivalently, this line could say
};                               // "struct treenode *smaller, *larger"

3 Passing a struct

struct foo {
    long id;
    char arr[11];
};

char get(struct foo f, int i) {
    return f.arr[i];
}

char get_v2(struct foo *f, int i) {
    return f->arr[i];
}

char set(struct foo f, int i, char v) {
    return f.arr[i] = v;
}

char set_v2(struct foo *f, int i, char v) {
    return f->arr[i] = v;
}

int main() {
    struct foo x = {42, {'h', 'e', 'l', 'l', 'o', 'c', 's', '2', '0', '8', '\0'}};
    char c = get(x, 4);
    char c2 = get_v2(&x, 4);

    set(x, 1, '@');
    set_v2(&x, 1, '@');
}

This example shows the importance of using a pointer to pass a struct to a function rather than passing the struct itself. I've created a struct foo that contains a long and an array of 11 char. There's a function get that takes a struct foo and an index, and returns the char at that index. There's another function set that takes a struct foo, an index, and a char and sets the char at that index.

There are two versions of each of these functions, one that takes a struct foo and one that takes at struct foo*. Notice how with get, passing a struct foo results in the entire structure being copied. With set, it doesn't even work when passing a struct foo because the modification is done to the local copy.

4 Bringing It All Together

Here's an extended example playing around with a struct and heap vs stack allocation. Plug in into C Tutor or compile and run it yourself. 

/* A demonstration of pointers and pass-by-value semantics in C
 * CS 208
 * Aaron Bauer, Carleton College
 * compile with "gcc -Og -g -o point_test point_test.c"
 * to get consistent address values, run with "setarch x86_64 -R ./point_test"
 */

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

typedef struct point {
  int x;
  int y;
} point_t;

void f(point_t p) {
  p.x++;
  printf("\nf: &p = %p\n", &p); // different address than &p in main, p has been copied
  printf("f: p = (%d, %d)\n\n", p.x, p.y);
}

void g(point_t *q) {
  q->x++;
  printf("\ng: &q = %p\n", &q); // different address than &q in main, q has been copied
  printf("g: q = %p\n", q); // but the value of q is the same (same heap address), the structure hasn't been copied
  printf("g: q = (%d, %d)\n\n", q->x, q->y);
}

int main() {
  // code stored at low addresses
  printf("&main = %p\n", &main);
  printf("&f = %p\n", &f);
  printf("&g = %p\n\n", &g);

  // p is stack-allocated (does not use malloc)
  point_t p = {5, 6};
  printf("&p = %p\n", &p);
  printf("p = (%d, %d)\n", p.x, p.y);
  f(p);
  printf("p = (%d, %d)\n\n", p.x, p.y); // mutation in f does not affect p, as p was copied

  point_t *q = (point_t*)malloc(sizeof(point_t));
  q->x = 3; // q->x is shorthand for (*q).x
  q->y = 4;
  printf("&q = %p\n", &q); // q is stack-allocated, &q is high in memory
  printf("q = %p\n", q); // q points to heap data, so it's value is a much lower address (higher than code)
  printf("q = (%d, %d)\n", q->x, q->y);
  g(q);
  printf("q = (%d, %d)\n", q->x, q->y); // mutation in g affects *q, same heap address in main and g
  free(q);
  printf("q = (%d, %d)\n", q->x, q->y); // undefined behavior to access freed memory
}

5 Lab 0

Follow along with the writeup: lab 0.

  • Download the starter code
  • Extract the tar file
  • Run make test, all tests start out failing
    • ERROR: Freed queue, but 3 blocks are still allocated, let's fix q_free
      • check for uninitialized queue and empty queue
      • loop through nodes, freeing each one
        • what should be freed? One call to free for each call to malloc
      • careful not to dereference a freed pointer!

Footnotes:

1

an array of three strings would be declared by char *str_array[3];. This would only allocate space for the three pointers, however, not for the strings themselves. You could use malloc to allocate space on the heap for the actual char arrays.

2

It would take 12 bytes: 11 characters at 1 byte each, plus the null terminator

3 
struct point {
  int x;
  int y;
};