review: stacks

Last In, First Out (LIFO)

we can only
add, see, or remove
(“push”, “peek”, or “pop”)
the top-most element

review: concrete stacks

in stack.h:

typedef struct _stack {
    char elements[STACK_SIZE];
    int size;
    int items;
} stack;

char stackTop (stack s);
stack stackPush (stack s, char elt);

review: concrete stacks

in stack.c:

// returns the topmost element
char stackTop (stack s) {
    return s.elements[s.items];
}

// this is our add function, 'char elt' = character element.
stack stackPush (stack s, char elt) {
    s.items++;
    s.elements[s.items] = elt;

    return s;
}

review: concrete stacks

in teststack.c

#include "stack.h"

int main (int argc, char *argv[]) {
    stack s = {
        .elements = {0},
        .size = STACK_SIZE,
        .items = 0
    };

    assert (stackTop (s) == 0);
    s = stackPush (s, 'z');
    assert (stackTop (s) == 'z');
    s = stackPop (s);
    assert (stackTop (s) == 0);

    printf ("All tests passed. You are Awesome!\n");
    return EXIT_SUCCESS;
}

review: Stack ADT

in Stack.h

// Will determine how big stackData will be.
#define STACK_SIZE 1000

// An ADT, at last!
typedef struct _stack *Stack;

// create a new Stack
Stack newStack (void);

// destroy a stack
void destroyStack (Stack s);

// this is our add function, 'char elt' = character element.
void stackPush (Stack s, char elt);

// returns the topmost element
char stackTop (Stack s);

// this is our pop function -- takes an element off.
char stackPop (Stack s);

review: Stack ADT

in testStack.c

#include "Stack.h"

int main (int argc, char *argv[]) {
    Stack s = newStack ();

    assert (stackTop (s) == 0);
    stackPush (s, 'z');
    assert (stackTop (s) == 'z');
    assert (stackPop (s) == 'z');
    assert (stackTop (s) == 0);

    // etc etc ...

    destroyStack (s);

    printf ("All tests passed. You are Awesome!\n");
    return EXIT_SUCCESS;
}

review: Stack ADT

in Stack.c

#include "Stack.h"

typedef struct _stack {
    char elements[STACK_SIZE];
    int size;
    int items;
} stack;

Stack newStack (void) {
    Stack s = calloc (1, sizeof (stack));
    if (s == NULL) {
        err (EXIT_FAILURE, "couldn't allocate memory");
    }
    s->size = STACK_SIZE;
    return s;
}

Stack ADT: changing the implementation

ADTs are powerful because you can
change the implementation
without affecting your ADT users

Stack ADT: Linked List

what if we used a linked list instead of an array?

what changes do we need to make?
where do we need to make them?

Stack ADT: Linked List

in Stack.c:

typedef struct _stack {
    // char elements[STACK_SIZE];
    // some sort of linked list?
    int size;
    int items;
} stack;

Stack newStack (void) {
    Stack s = calloc (1, sizeof (stack));
    if (s == NULL) {
        err (EXIT_FAILURE, "couldn't allocate memory");
    }
    // does this have to be fixed?
    s->size = STACK_SIZE;

    // set up the linked list, too
    return s;
}

Queues

First In, First Out (FIFO)

we can only
add
(“enqueue”)
to the end of the queue

we can only
see/remove
(“dequeue”, “peek”)
from the front of the queue

FAQ: why ban things?

our goal here is not to learn C…
our goal here is to learn to program

everything you’ve seen
can be transplanted into other languages

C has lots of syntax…
limiting it makes it easy to learn,
easy to debug and reason about,
and easy to get everyone to the same level

FAQ: why ban things?

“programming in the small”

what’s important?
primitive data and operators
means of combination
means of abstraction

“programming in the large”

exploring ways to solve problems

type casts

this syntax is explicitly banned by the style guide
you should not use it.

void *calloc (size_t nItems, size_t itemSize);

void cannot exist
void * cannot be dereferenced…
the compiler is okay with this,
and lets us cast it on assignment

struct _game *g = calloc (1, sizeof (struct _game));
int *g2 = g;
// warning: incompatible pointer types
//     initializing 'int *' with
//     an expression of type 'struct _game *'
//     [-Wincompatible-pointer-types]
int *g3 = (int *) g;
// ... no warning. what does `g3` point to?

usually a bad idea to overrule the type system.

the ternary operator

this syntax is explicitly banned by the style guide
you should not use it.

result = condition ? true expr : false expr;

equivalent to

if (condition) {
    result = true expr;
} else {
    result = false expr;
}

goto

this syntax is explicitly banned by the style guide
you should not use it.

jump to arbitrary locations in your code!!!!!111!111
(this cannot possibly be a bad idea)

promotes “unstructured code”… spaghetti, yo.

extern int f();

int g() {
    int ret = 1;

    goto out;
    ret = f();

out:
    return ret;
}

blocks without braces

this syntax is explicitly banned by the style guide
you should not use it.

game *g = calloc (1, sizeof (game));
if (g == NULL)
    err (EX_OSERR, "couldn't allocate memory");

“optimistic indentation”

game *g = calloc (1, sizeof (game));
if (g == NULL)
    fprintf (stderr, "couldn't allocate memory: %s", strerror(errno));
    exit (EXIT_FAILURE);

switch, case, break, default

this syntax is explicitly banned by the style guide
you should not use it.

switch (expression) {
case constant:
    // statements
    break;

case constant:
    // statements
    // no break? fall through.

default:
    // statements;
}

loops: break

this syntax is explicitly banned by the style guide
you should not use it.

while (true) {
    // do stuff
    if (expr) {
        break;
    }
}

why bother? restructure your logic

loops: continue

this syntax is explicitly banned by the style guide
you should not use it.

while (true) {
    // do stuff
    if (expr) {
        continue;
    }
    // do stuff

    // `continue` lands here.
}

why bother? restructure your logic

you may lose an increment!

loops: do/while

this syntax is explicitly banned by the style guide
you should not use it.

do {
    // do stuff
} while (expr);

why bother? restructure your logic

loops: for

this syntax is explicitly banned by the style guide
you should not use it.

for (initialiser; condition; increment) {
    // do stuff
}

why bother? do it all with while

non-linear flow of control;
easy to construct confusing mess

the comma operator

this syntax is explicitly banned by the style guide
you should not use it.

expr, expr;
do both; the value is the last one.

often used in for increments…
a confusing mess.

function pointers

this syntax is explicitly banned by the style guide
you should not use it.

int op_add (int a, int b) { return a + b; }
int op_sub (int a, int b) { return a - b; }
int op_mul (int a, int b) { return a * b; }
int op_div (int a, int b) { return a / b; }

int (*op)(int, int);
switch (operator) {
case '+': op = &op_add; break;
case '-': op = &op_sub; break;
case '*': op = &op_mul; break;
case '/': op = &op_div; break;
}

op (a, b);

poor-man’s generic programming;
often used to implement OOP in C

multiple returns

this syntax is explicitly banned by the style guide
you should not use it.

long long factorial (long long n) {
    if (n == 0) {
        return 1;
    }

    return n * factorial (n - 1);
}

non-linear flow of control…
will this piece of code get executed? when?

const, static

this syntax is explicitly banned by the style guide
you should not use it.

type modifiers

static: this function won’t escape
const: this variable’s value can’t change
static: this variable’s value should persist
volatile: this variable should always be reloaded
inline: inject function at call site
extern: this is defined elsewhere
restrict: this pointer will be used

easy to do horrible, nasty, evil things

pointer arithmetic

this syntax is explicitly banned by the style guide
you should not use it.

char *s = "Hello, world!\n";
while (*s++) len++;

ye gods, what?

SecureTransport

static OSStatus
SSLVerifySignedServerKeyExchange (
    SSLContext *ctx, bool isRsa, SSLBuffer signedParams,
    uint8_t *signature, UInt16 signatureLen)
{
    OSStatus  err;
    // ... do stuff

    if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
        goto fail;
        goto fail;
    if ((err = SSLHashSHA1.final(&hashCtx, &hashOut)) != 0)
        goto fail;

    // ... do stuff

fail:
    SSLFreeBuffer(&signedHashes);
    SSLFreeBuffer(&hashCtx);
    return err;
}