administrivia

• hw1 out
  • start early
  • can use up to 2 late days on it
  • you really don’t want to
• today: the last lecture on C & CSE 351 review
• next lecture: system calls
  • unix paper questions: try your best
  • upload your answers early
  • hands-on

today’s plan

• vectors
• singly linked lists

why data structures in C

control: performance, resource

low-level & error-prone (cache, concurrency)

vector v0

typedef int T;

struct vector {
    size_t size;
    T *data;
};

struct vector *vector_alloc(size_t n, T initial_val);
void vector_free(struct vector *s);

example use:

int main(void) {
    size_t i, n = 10;
    struct vector *s = vector_alloc(n, 42);
    /* ... */
    vector_free(s);
}

vector v0: problems?

struct vector {
    size_t size;
    T *data;
};

struct vector *vector_alloc(size_t n, T initial_val) {
    struct vector *s = malloc(sizeof(struct vector));
    s->size = n;
    s->data = malloc(n * sizeof(T));
    for (size_t i = 0; i < n; ++i)
        s->data[i] = initial_val;
    return s;
}

void vector_free(struct vector *s) {
    free(s);
    free(s->data);
}

problems

• double free (wrong order)
• malloc may fail
• allocation size may overflow

see vector_0.c

performance?

vector v1: flexible array member

struct vector {
    size_t size;
    T data[];
};

struct vector *vector_alloc(size_t n, T initial_val) {
    struct vector *s = malloc(sizeof(struct vector) + n * sizeof(T));
    s->size = n;
    for (size_t i = 0; i < n; ++i)
        s->data[i] = initial_val;
    return s;
}

void vector_free(struct vector *s) {
    free(s);
}

vector v1: one malloc

• out of memory
• malloc size overflow

see vector_1.c

flexible array member

struct vector_0 {
    size_t size;
    T *data;
};

struct vector_1 {
    size_t size;
    T data[];
};

sizeof(struct vector_0) vs sizeof(struct vector_1)?

try printf the results

sum up

• be careful with allocation
  • out of memory
  • size overflow
• flexible array member
  • useful for reducing mallocs/footprint/dereferences
  • old fashion: zero- or one-length array

bug example

struct snap_context {
    ...
    size_t num_snaps;
    uint64_t snaps[];
};

struct snap_context *ctx;
size_t num = ...;

if (num > SIZE_MAX / sizeof(uint64_t) - sizeof(*ctx))
    goto fail;
ctx = malloc(sizeof(*ctx) + num * sizeof(uint64_t));

see bug & fix

singly linked list

typedef int T;

struct slist {
    T elem;
    struct slist *next;
};

struct slist *slist_push(struct slist *lst, T e);

slist_push

struct slist *slist_push(struct slist *lst, T e) {
    struct slist *n = malloc(sizeof(struct slist));
    /* TODO: check if n is NULL */
    n->elem = e;
    n->next = lst;
    return n;
}

int main(void) {
    struct slist *lst = NULL;
    lst = slist_push(lst, 12);
    lst = slist_push(lst, 34);
    lst = slist_push(lst, 56);
}

more data structures

Example: Linux kernel

• doubly linked list: list.h
• red-black tree: rbtree.h
• radix tree: radix-tree.h
• hash table: hashtable.h
• lock-free slist: llist.h
• …

example: linux kernel’s list

struct person {
    char name[32];
    long ident;
    struct list_head list;
};

int main(void) {
    struct person alice = {"alice", 42}, bob = {"bob", 24}, *p;
    LIST_HEAD(lst);
    list_add(&alice.list, &lst);
    list_add(&bob.list, &lst);

    list_for_each_entry(p, &lst, list) {
        printf("%s:\t%ld\n", p->name, p->ident);
    }
}

see list.h and test_list.c

C final details

• macros
• .h files: headers, to be #include’d
  • declarations, inline functions
  • avoid double inclusion: include guard
• .c files: definitions
• build process: preprocessing - AST - IR - .o files - executable

review CSE 351 / tomorrow’s sections

self-exercise 1

complete the singly linked list:

• add a function that returns the number of elements in a list
• implement a program that builds a list of lists
  • i.e., it builds a linked list
  • but each element in the list is a (different) linked list
• design and implement slist_pop
  • removes an element from the head of the list
  • make sure your linked list code, and customers’ code that uses it, contains no memory leaks

solution

self-exercise 2

implement and test a binary search tree

• don’t worry about making it balanced
• implement key insert() and lookup() functions
• implement a key delete() function
• implement it as bst.c and bst.h
• implement test_bst.c: main() to test out your BST

solution