C Crash Course¶

Python version¶

def fib(n):
    a, b = 0,  1
    for i in range(n):
        a, b = a+b, a
    return a

fib(100)

C version¶

%%file fib.h

double fib(int n);

%%file fib.c

double fib(int n) {
    double a = 0, b = 1;
    for (int i=0; i<n; i++) {
        double tmp = b;
        b = a;
        a += tmp;
     }
    return a;
}

%%file main.c
#include <stdio.h> // for printf()
#include <stdlib.h> // for atoi())
#include "fib.h" // for fib()

int main(int argc, char* argv[]) {
    int n = atoi(argv[1]);
    printf("%f", fib(n));
}

%%file Makefile

CC=clang
CFLAGS=-Wall

fib: main.o fib.o
     $(CC) $(CFLAGS) -o fib main.o fib.o

main.o: main.c fib.h
     $(CC) $(CFAGS) -c main.c

fib.o: fib.c
     $(CC) $(CFLAGS) -c fib.c

clean:
     rm -f *.o

! make

Run executable file¶

! ./fib 100

Ternary operator¶

The ternary operator expr = condition ? expr1 : expr2 allows an if-else statement to be put in a single line. In English, this says that if condition is True, expr1 is assigned to expr, otherwise expr2 is assigned to expr. We used it in the tutorial code to print a comma between elements in a list unless the elememnt was the last one, in which case we printed a new line ‘’.

Note: There is a similar ternary construct in Python expr = expr1 if condition else epxr2.

if-else¶

// Interpretation of grades by Asian parent
if (grade == 'A') {
    printf("Acceptable\n");
} else if (grade == 'B') {
    printf("Bad\n");
} else if (grade == 'C') {
    printf("Catastrophe\n");
} else if (grade == 'D') {
    printf("Disowned\n");
} else {
    printf("Missing child report filed with local police\n")
}

for, while, do¶

// Looping variants

// the for loop in C consists of the keyword for followed by
// (initializing statement; loop condition statement; loop update statement)
// followed by the body of the loop in curly braces
int arr[3] = {1, 2, 3};
for (int i=0; i<sizeof(arr)/sizeof(arr[0]); i++) {
    printf("%d\n", i);
}

// the while loop
int i = 3;
while (i > 0) {
    i--;
}

// the do loop is similar to the while loop but will execute the body at least once
int i = 3;
do {
    i==;
} while (i > 0);

The C standard does not require braces if the body is a singel line, but I think it is safer to always include them. Note that whitespace is not significant in C (unlike Python), so

int i = 10;
while (i > 0)
    i--;
    i++;

actually means

int i = 10;
while (i > 0) {
    i--;
}
i++;

and the use of braces even for single statement bodies prevnets such errors.

Automatic arrays¶

If you know the size of the arrays at initialization (i.e. when the program is first run), you can usually get away with the use of fixed size arrays for which C will automatically manage memory for you.

int len = 3;

// Giving an explicit size
double xs[len];
for (int i=0; i<len; i++) {
    xs[i] = 0.0;
}

// C can infer size if initializer is given
double ys[] = {1, 2, 3};

Pointers and dynamic memory management¶

Otherwise, we have to manage memory ourselves using pointers. Bascially, memory in C can be auotmatic, static or dynamic. Variables in automatic memory are managed by the computer on the stack, when it goes out of scope, the varible disappears. Static variables essentially live forever. Dynamic memory is allocated in the heap, and you manage its lifetime.

Mini-glossary: * scope: Where a variable is visible - basically C variables have block scope - variables either live within a pair of curly braces (inlucdes variables in parentheses just before block such as function arguments and the counter in a for loop), or they are visible thorughout the file. * stack: Computer memory is divided into a stack (small) and a heap (big). Automatic varianbles are put on the stack; dynamcic variables are put in the heap. Hence if you have a very large array, you would use dynamic memory allocation even if you knwe its size at initialization.

Any variable in memory has an address represented as a 64-bit integer in most operating systems. A pointer is basically an integer containing the address of a block of memory. This is what is returned by functions such as malloc. In C, a pointer is dentoed by *. However, the * notation is confusing because its interpreation depends on whehter you are using it in a declaraiton or not. In a declaration

int *p = malloc(sizeof(int)); // p is a pointer to an integer
*p = 5; // *p is an integer

To get the actual address value, we can use the & address opertor. This is often used so that a function can alter the value of an argument passed in (e.g. see address.c below).

%%file pointers.c
#include <stdio.h>

int main()
{
    int i = 2;
    int j = 3;
    int *p;
    int *q;
    *p = i;
    q = &j;
    printf("p  = %p\n", p);
    printf("*p = %d\n", *p);
    printf("&p = %p\n", &p);
    printf("q  = %p\n", q);
    printf("*q = %d\n", *q);
    printf("&q = %p\n", &q);
}

%%bash

clang -Wall -Wno-uninitialized pointers.c -o pointers
./pointers

Passing by value and passing by reference¶

%%file by_val.c
#include <stdio.h>

void change_arg(int p) {
    p *= 2;
}

int main()
{
    int x = 5;
    change_arg(x);
    printf("%d\n", x);
}

%%bash

clang -Wall by_val.c -o by_val
./by_val

%%file by_ref.c
#include <stdio.h>

void change_arg(int *p) {
    *p *= 2;
}
int main()
{
    int x = 5;
    change_arg(&x);
    printf("%d\n", x);
}

%%bash

clang -Wall by_ref.c -o by_ref
./by_ref

Pointers to pointers to pointers - just remember that a pointer is simply a name for an integer that represents an address; since it is an integer, it also has an address ...¶

%%file ptr.c
#include <stdio.h>

int main() {
    int x = 2;
    int *p = &x;
    int **q = &p;
    int ***r = &q;

    printf("%d, %p, %p, %p, %p, %p, %p, %d", x, &x, p, &p, q, &q, r, ***r);
}

%%bash
gcc ptr.c -o ptr
./ptr

Pointer arithmetic¶

If we want to store a whole sequence of ints, we can do so by simply allocating more memory:

int *ps = malloc(5 * sizeof(int)); // ps is a pointer to an integer
for (int i=0; i<5; i++) {
    ps[i] = i;
}

The computer will find enough space in the heap to store 5 consecutive integers in a contiguour way. Since C arrays are all fo the same type, this allows us to do pointer arithmetic - i.e. the pointer ps is the same as &ps[0] and ps + 2 is the same as &ps[2]. An example at this point is helpful.

%%file pointers2.c
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int *ps = malloc(5 * sizeof(int));
    for (int i =0; i < 5; i++) {
        ps[i] = i + 10;
    }

    printf("%d, %d\n", *ps, ps[0]); // remmeber that *ptr is just a regular variable outside of a declaration, in this case, an int
    printf("%d, %d\n", *(ps+2), ps[2]);
    printf("%d, %d\n", *(ps+4), *(&ps[4])); // * and & are inverses

    free(ps); // avoid memory leak
}

%%bash

clang -Wall pointers2.c -o pointers2
./pointers2

Pointers and arrays¶

An array name is actualy just a constant pointer to the address of the beginning of the array. Hence, we can derferecne an array name just like a pointer. We can also do pointer arithmetic with array names - this leads to the following legal but weird syntax:

arr[i] = *(arr + i) = i[arr]

%%file array_pointer.c
#include <stdio.h>

int main()
{
    int arr[] = {1, 2, 3};
    printf("%d\t%d\t%d\t%d\t%d\t%d\n", *arr, arr[0], 0[arr], *(arr + 2), arr[2], 2[arr]);
}

%%bash

clang -Wall array_pointer.c -o array_pointer
./array_pointer

Allocating memory for 2D arrays¶

%%file array_2d.c
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int r = 3, c = 4;

    // first allocate space for the pointers to all rows
    int **arr = malloc(r * sizeof(int *));
    // then allocate space for the number of columns in each row
    for (int i=0; i<r; i++) {
        arr[i] = malloc(c * sizeof(int));
    }

    // fill array with integer values
    for (int i = 0; i <  r; i++) {
        for (int j = 0; j < c; j++) {
             arr[i][j] =i*r+j;
        }
    }

    for (int i = 0; i <  r; i++) {
      for (int j = 0; j < c; j++) {
         printf("%d ", arr[i][j]);
        }
    }

    // every malloc should have a free to avoid memory leaks
    for (int i=0; i<r; i++) {
        free(arr[i]);
    }
    free(arr);
}

%%bash

gcc -Wall array_2d.c -o array_2d
./array_2d

More on pointers¶

Differnt kinds of nothing: There is a special null pointer indicated by the keyword NULL that points to nothing. It is typically used for pointer comparisons, since NULL pointers are guaranteed to compare as not equal to any other pointer (including another NULL). In paticular, it is often used as a sentinel value to mark the end of a list. In contrast a void pointer (void *) points to a memory location whose type is not decalred. It is used in C for generic operations - for example, malloc returns a void pointer. To totally confuse the beginning C student, there is also the NUL keyword, which refers to the '\0' character used to terminate C strings. NUL and NULL are totally differnet beasts.

Deciphering pointer idioms: A common C idiom that you should get used to is *q++ = *p++ where p and q are both pointers. In English, this says

• *q = *p (copy the variable pointed to by p into the variable pointed to by q)
• increment q
• increment p

%%file pointers3.c
#include <stdio.h>
#include <stdlib.h>

int main()
{
    // example 1
    typedef char* string;
    char *s[] = {"mary ", "had ", "a ", "little ", "lamb", NULL};
    for (char **sp = s; *sp != NULL; sp++) {
        printf("%s", *sp);
    }
    printf("\n");

    // example 2
    char *src = "abcde";
    char *dest = malloc(5); // char is always 1 byte by C99 definition

    char *p = src + 4;
    char *q = dest;
    while ((*q++ = *p--)); // put the string in src into dest in reverse order

    for (int i = 0; i < 5; i++) {
        printf("i = %d, src[i] = %c, dest[i] = %c\n", i, src[i], dest[i]);
    }
}

%%bash

clang -Wall pointers3.c -o pointers3
./pointers3