1 Intro to Systems Programming

1.1 Computer Organization

Find the slides.

1.2 Memory Hierarchies

Find the slides.

1.3 Intro to C

You already know C

well, some of it anyways…

1.3.1 C constructs [if you’re familiar with Java, Python, etc.]

* no range checks!!: C will let you access an array beyond the maximum size that you have specified while creating it. The effects of such access are implementation specific – each platform/operating system will handle it differently. Note that on platforms that don’t have memory protection, this can cause some serious problems!

What’s different [from java]

• no object-oriented programming
• no function overloading
• no classes!
• we have struct instead
  • which is similar but very different
• compiled not interpreted
• pointers!!!

1.3.2 Compound types

contiguous memory layouts: objects within these data types are laid out in memory, next to each other. This becomes important when you’re trying to use pointers to access various elements.

no (built-in) boolean!

C does not have a built in boolean data type. We can mimic it by using integer values (0 is false while any other non-zero values is true).

2 Intermediate C

2.1 Objectives

• Recalling C types with a focus on pointers.
• Focus on more advanced features like void *s and function pointers.
• Practice thinking about C programs as memory.

2.2 Types

2.2.1 Basic types

• char - think “one byte”. Same as signed char.
• short int - think “two bytes”. Same as short.
• int - think “four bytes”.
• long int - think “potentially larger int”. Most commonly known solely as long.
• float, double - floating point values (not used in the class).
• void - the lack of a type. Variables cannot have this type.

/* `void` is fine to denote "no variables/return values", ... */
int
main(void)
{
    /* ...but not fine on variables */
    void a;

    return 0;
}

Program output:

inline_exec_tmp.c:6:7: error: variable has incomplete type 'void'
        void a;
             ^
1 error generated.
make[1]: *** [inline_exec_tmp] Error 1

• enum - an int or short int with some “named” values.

#include <stdio.h>

enum weekdays {
    MON, TUES, WED, THURS, FRI
};

int
main(void)
{
    printf("MON = %d, TUES = %d, ..., FRI = %d\n", MON, TUES, FRI);

    return 0;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

You can choose the values explicitly (e.g. enum grades { MON = 1, TUES = 2, WED = 3, THURS = 4, FRI = 5};).

Modifiers

• unsigned - variables that cannot be negative. Given that variables have a fixed bit-width, they can use the extra bit (“negative” no longer needs to be tracked) to instead represent numbers twice the size of signed variants.
• signed - signed variables. You don’t see this modifier as much because char, int, long all default to signed.
• long - Used to modify another type to make it larger in some cases. long int can represent larger numbers and is synonymous with long. long long int (or long long) is an even larger value!
• static - this variable should not be accessible outside of the .c file in which it is defined.
• const - an immutable value. We won’t focus much on this modifier.
• volatile - this variable should be “read from memory” every time it is accessed. Confusing now, relevant later, but not a focus.

2.2.1.1 Examples

int
main(void)
{
    char a;
    signed char a_signed;     /* same type as `a` */
    char b;                   /* values between [-128, 127] */
    unsigned char b_unsigned; /* values between [0, 256] */
    int c;
    short int c_shortint;
    short c_short;            /* same as `c_shortint` */
    long int c_longint;
    long c_long;              /* same type as `c_longint` */

    return 0;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

You might see all of these, but the common primitives, and their sizes:

#include <stdio.h>

/* Commonly used types that you practically see in a lot of C */
int
main(void)
{
    char c;
    unsigned char uc;
    short s;
    unsigned short us;
    int i;
    unsigned int ui;
    long l;
    unsigned long ul;

    printf("char:\t%ld\nshort:\t%ld\nint:\t%ld\nlong:\t%ld\n",
        sizeof(c), sizeof(s), sizeof(i), sizeof(l));

    return 0;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

2.2.2 Common POSIX types and values

• stddef.h¹:

  • size_t, usize_t, ssize_t - types for variables that correspond to sizes. These include the size of the memory request to malloc, the return value from sizeof, and the arguments and return values from read/write/… ssize_t is signed (allows negative values), while the others are unsigned.
  • NULL - is just #define NULL ((void *)0)

• limits.h²:

  • INT_MAX, INT_MIN, UINT_MAX - maximum and minimum values for a signed integer, and the maximum value for an unsigned integer.
  • LONG_MAX, LONG_MIN, ULONG_MAX - minimum and maximum numerical values for longs and unsigned longs.
  • Same for short ints (SHRT_MAX, etc…) and chars (CHAR_MAX, etc…).

2.2.3 Format Strings

Many standard library calls take “format strings”. You’ve seen these in printf. The following format specifiers should be used:

• %d - int
• %ld - long int
• %u - unsigned int
• %c - char
• %x - unsigned int printed as hexadecimal
• %lx - long unsigned int printed as hexadecimal
• %p - prints out any pointer value, void *
• %s - prints out a string, char *

Format strings are also used in scanf functions to read and parse input.

You can control the spacing of the printouts using %NX where N is the number of characters you want printed out (as spaces), and X is the format specifier above. For example, "%10ld"would print a long integer in a 10 character slot. Adding \n and \t add in the newlines and the tabs. If you need to print out a “\”, use \\.

2.2.3.1 Example

#include <stdio.h>
#include <limits.h>

int
main(void)
{
    printf("Integers: %d, %ld, %u, %c\n"
           "Hex and pointers: %lx, %p\n"
           "Strings: %s\n",
           INT_MAX, LONG_MAX, UINT_MAX, '*',
           LONG_MAX, &main,
           "hello world");

    return 0;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

2.2.4 Compound types

• struct - A collection of different values. Example: objects with many different fields.
• union - One of a set of values. Example: what if you want to represent data for one food item among others.

Unions are not very common, but are sometimes useful. The size of a union is the maximum size of its fields. In contrast, the struct is the sum of the sizes of each of its fields.

2.2.4.1 Example

#include <stdio.h>

struct hamburger {
    int num_burgers;
    int cheese;
    int num_patties;
};

union food {
    int num_eggs;
    struct hamburger burger;
};

/* Same contents as the union. */
struct all_food {
    int num_eggs;
    struct hamburger burger;
};

int
main(void)
{
    union food f_eggs, f_burger;

    /* now I shouldn't access `.burger` in `f_eggs` */
    f_eggs.num_eggs = 10;
    /* This is just syntax for structure initialization. */
    f_burger.burger = (struct hamburger) {
        .num_burgers = 5,
        .cheese      = 1,
        .num_patties = 1
    };
    /* now shouldn't access `.num_eggs` in `f_burger` */

    printf("Size of union:  %ld\nSize of struct: %ld\n",
           sizeof(union food), sizeof(struct all_food));

    return 0;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

We can see the effect of the union: The size is max(fields) rather than sum(fields). What other examples can you think of where you might want unions?

An aside on syntax: The structure initialization syntax in this example is simply a shorthand. The struct hamburger initialization above is equivalent to:

f_burger.burger.num_burgers = 5;
f_burger.burger.cheese      = 1;
f_burger.burger.num_patties = 1;

Though since there are so many .s, this is a little confusing. We’d typically want to simply as:

struct hamburger *h = &f_burger.burger;
h->num_burgers = 5;
h->cheese      = 1;
h->num_patties = 1;

More on -> in the next section.

2.2.5 Pointers & Arrays

Variables can have be pointer types (e.g. int *a). Variables with pointer types are pointers and hold an address to the a variable of the type to which they point, or to NULL. NULL denotes that the pointer is not valid. You want to imagine that variables hold data, for example int a = 6:

a---+
| 6 |
+---+

A pointer, int *b = &a should be imagined as a pointer:

b ---> a---+
       | 6 |
       +---+

Note that the “address of”, & operator takes a variable and returns its address. If you print out the pointer, printf("%p", b), you’ll get the address (i.e. the arrow) To follow the arrow, you must dereference the pointer: *b == 6.

#include <stdio.h>

static int value;

/* here, the `*` is part of the type "int *", i.e. a pointer to an `int` */
void
foo(int *ptr)
{
    /*
     * Here, the `*` is the dereference operation, and
     * gives us the value that is pointed to.
     */
    *ptr = 1;
}

int
main(void)
{
    printf("value is initialized to %d\n", value);

    foo(&value); /* `&` gives us the address of the variable `value` */
    printf("value updated to %d\n", value);

    return value - 1;
}

Program output:

MON = 0, TUES = 1, ..., FRI = 4

Pointers are necessary as they enable us to build linked data-structures (linked-lists, binary trees, etc…). Languages such as Java assume that every single object variable is a pointer, and since all object variables are pointers, they don’t need special syntax for them.

Arrays are simple contiguous data items, all of the same type. int a[4] = {6, 7, 8, 9} should be imagined as:

a ---> +---+---+---+---+
       | 6 | 7 | 8 | 9 |
       +---+---+---+---+

When you access an array item, a[2] == 8, C is really treating a as a pointer, doing pointer arithmetic, and dereferences to find offset 2.

#include <stdio.h>

int main(void) {
    int a[] = {6, 7, 8, 9};
    int n = 1;

    printf("0th index: %p == %p; %d == %d\n", a,     &a[0], *a,       a[0]);
    printf("nth index: %p == %p; %d == %d\n", a + n, &a[n], *(a + n), a[n]);

    return 0;
}

Program output:

0th index: 0x304c65fe0 == 0x304c65fe0; 6 == 6
nth index: 0x304c65fe4 == 0x304c65fe4; 7 == 7

Making this a little more clear, lets understand how C accesses the nth item. Lets make a pointer int *p = a + 1 (we’ll just simply and assume that n == 1 here), we should have this:

p ---------+
           |
           V
a ---> +---+---+---+---+
       | 6 | 7 | 8 | 9 |
       +---+---+---+---+

Thus if we dereference p, we access the 1st index, and access the value 7.

#include <stdio.h>

int
main(void)
{
    int a[] = {6, 7, 8, 9};
    /* same thing as the previous example, just making the pointer explicit */
    int *p = a + 1;

    printf("nth index: %p == %p; %d == %d\n", p, &a[1], *p, a[1]);

    return 0;
}

Program output:

0th index: 0x304e6afe0 == 0x304e6afe0; 6 == 6
nth index: 0x304e6afe4 == 0x304e6afe4; 7 == 7

We can see that pointer arithmetic (i.e. doing addition/subtraction on pointers) does the same thing as array indexing plus a dereference. That is, *(a + 1) == a[1]. For the most part, arrays and pointers can be viewed as very similar, with only a few exceptions³.

Pointer arithmetic should generally be avoided in favor of using the array syntax. One complication for pointer arithmetic is that it does not fit our intuition for addition:

#include <stdio.h>

int
main(void)
{
    int a[] = {6, 7, 8, 9};
    char b[] = {'a', 'b', 'c', 'd'};
    /*
     * Calculation: How big is the array?
     * How big is each item? The division is the number of items.
     */
    int num_items = sizeof(a) / sizeof(a[0]);
    int i;

    for (i = 0; i < num_items; i++) {
        printf("idx %d @ %p & %p\n", i, a + i, b + i);
    }

    return 0;
}

Program output:

0th index: 0x304785fe0 == 0x304785fe0; 6 == 6
nth index: 0x304785fe4 == 0x304785fe4; 7 == 7

Note that the pointer for the integer array (a) is being incremented by 4, while the character array (b) by 1. Focusing on the key part:

idx 0 @ ...0 & ...4
idx 1 @ ...4 & ...5
idx 2 @ ...8 & ...6
idx 3 @ ...c & ...7
           ^      ^
           |      |
Adds 4 ----+      |
Adds 1 -----------+

Thus, pointer arithmetic depends on the size of the types within the array. There are types when one wants to iterate through each byte of an array, even if the array contains larger values such as integers. For example, the memset and memcmp functions set each byte in an range of memory, and byte-wise compare two ranges of memory. In such cases, casts can be used to manipulate the pointer type (e.g. (char *)a enables a to not be referenced with pointer arithmetic that iterates through bytes).

2.2.5.1 Example

#include <stdio.h>

/* a simple linked list */
struct student {
    char *name;
    struct student *next;
};

struct student students[] = {
    {.name = "Penny", .next = &students[1]}, /* or `students + 1` */
    {.name = "Gabe",  .next = NULL}
};
struct student *head = students;
/*
 * head --> students+------+
 *          | Penny | Gabe |
 *          | next  | next |
 *          +-|-----+---|--+
 *            |     ^   +----->NULL
 *            |     |
 *            +-----+
 */
int
main(void)
{
    struct student *i;

    for (i = head; i != NULL; i = i->next) {
        printf("%s\n", i->name);
    }

    return 0;
}

Program output:

0th index: 0x30cf80fe0 == 0x30cf80fe0; 6 == 6
nth index: 0x30cf80fe4 == 0x30cf80fe4; 7 == 7

2.2.5.2 Generic Pointer Types

Generally, if you want to treat a pointer type as another, you need to use a cast. You rarely want to do this (see the memset example below to see an example where you might want it). However, there is a need in C to have a “generic pointer type” that can be implicitly cast into any other pointer type. To get a sense of why this is, two simple examples:

1. What should the type of NULL be?

NULL is used as a valid value for any pointer (of any type), thus NULL must have a generic type that can be used in the code as a value for any pointer. Thus, the type of NULL must be void *.

2. malloc returns a pointer to newly-allocated memory. What should the type of the return value be?

C solves this with the void * pointer type. Recall that void is not a valid type for a variable, but a void * is different. It is a “generic pointer that cannot be dereferenced*. Note that dereferencing a void * pointer shouldn’t work as void is not a valid variable type (e.g. void *a; *a = 10; doesn’t make much sense because *a is type void).

#include <stdlib.h>

int
main(void)
{
    int *intptr = malloc(sizeof(int)); /* malloc returns `void *`! */

    *intptr = 0;

    return *intptr;
}

Program output:

0th index: 0x30d4a9fe0 == 0x30d4a9fe0; 6 == 6
nth index: 0x30d4a9fe4 == 0x30d4a9fe4; 7 == 7

Data-structures often aim to store data of any type (think: a linked list of anything). Thus, in C, you often see void *s to reference the data they store.

2.2.5.3 Relationship between Pointers, Arrays, and Arrows

Indexing into arrays (a[b]) and arrows (a->b) are redundant syntactic features, but they are very convenient.

• &a[b] is equivalent to a + b where a is a pointer and b is an index.
• a[b] is equivalent to *(a + b) where a is a pointer and b is an index.
• a->b is equivalent to (*a).b where a is a pointer to a variable with a structure type that has b as a field.

Generally, you should always try and stick to the array and arrow syntax were possible, as it makes your intention much more clear when coding than the pointer arithmetic and dereferences.

2.3 Memory Allocation

Dynamic memory allocations

• void *malloc(size_t size) - allocate size memory, or return NULL.
• void *calloc(size_t nmemb, size_t size) - allocate nmemb * size bytes, and initialize them to 0.
• void *realloc(void *ptr, size_t size) - pass in a previous allocation, and either grow/shrink it to size, or allocate a new chunk of memory and copy the data in ptr into it. Return the memory of size size, or NULL on error.
• void free(void *ptr) - deallocate previously allocated memory (returned from any of the above).

A few things to keep in mind:

1. If you want to allocate an array, then you have to do the math yourself for the array size. For example, int *arr = malloc(sizeof(int) * n); to allocate an array of ints with a length of n.
2. malloc is not guaranteed to initialize its memory to 0. You must make sure that your array gets initialized. It is not uncommon to do a memset(arr, 0, sizeof(int) * n); to set the memory 0.
3. calloc is guaranteed to initialize all its allocated memory to 0.

2.3.1 Common Errors

• Allocation error. You must check the return value of memory allocation functions for NULL, and handle the error appropriately.

#include <stdlib.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    /* Error: did not check return value! */
    *a = 1;
    free(a);

    return 0;
}

Program output:

0th index: 0x3086bbfe0 == 0x3086bbfe0; 6 == 6
nth index: 0x3086bbfe4 == 0x3086bbfe4; 7 == 7

• Dangling pointer. If you maintain a pointer to a chunk of memory that you free, and then dereference that pointer, bad things can happen. The memory might have already been re-allocated due to another call to malloc, and is used for something completely different in your program. It is up to you as a programmer to avoid freeing memory until all references to it are dropped.

#include <stdlib.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (a == NULL) return -1;
    free(a);

    /* Error: accessing what `a` points to after `free`! */
    return *a;
}

Program output:

0th index: 0x309d8ffe0 == 0x309d8ffe0; 6 == 6
nth index: 0x309d8ffe4 == 0x309d8ffe4; 7 == 7

• Memory leaks. If you remove all references to memory, but don’t free it, then the memory will never get freed. This is a memory leak.

#include <stdlib.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (!a) return -1;
    a = NULL;
    /* Error: never `free`d `a` and no references to it remain! */

    return 0;
}

Program output:

• Double free. If you free the memory twice, bad things can happen. You could confuse the memory allocation logic, or you could accidentally free an allocation made after the first free was called.

#include <stdlib.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (!a) return -1;
    free(a);
    free(a);
    /* Error: yeah, don't do that! */

    return 0;
}

Program output:

valgrind will help you debug the last three of these issues, and later in the class, we’ll develop a library to help debug the first.

2.4 Exercises

2.4.1 C is a Thin Language Layer on Top of Memory

We’re going to look at a set of variables as memory. When variables are created globally, they are simply allocated into subsequent addresses.

#include <stdio.h>
#include <string.h>

void print_values(void);

unsigned char a = 1;
int b = 2;
struct foo {
    long c_a, c_b;
    int *c_c;
};
struct foo c = (struct foo) { .c_a = 3, .c_c = &b };
unsigned char end;

int
main(void)
{
    size_t vars_size;
    unsigned int i;
    unsigned char *mem;

    /* Q1: What would you predict the output of &end - &a is? */
    printf("Addresses:\na   @ %p\nb   @ %p\nc   @ %p\nend @ %p\n"
           "&end - &a = %ld\n", /* Note: you can split strings! */
           &a, &b, &c, &end, &end - &a);
    printf("\nInitial values:\n");
    print_values();
    /* Q2: Describe what these next two lines are doing. */
    vars_size = &end - &a;
    mem = &a;
    /* Q3: What would you expect in the following printout (with the print uncommented)? */
    printf("\nPrint out the variables as raw memory\n");
    for (i = 0; i < vars_size; i++) {
        unsigned char c = mem[i];
//      printf("%x ", c);
    }
    /* Q4: What would you expect in the following printout (with the print uncommented)? */
    memset(mem, 0, vars_size);
    /* memset(a, b, c): set the memory starting at `a` of size `c` equal `b` */
    printf("\n\nPost-`memset` values:\n");
//  print_values();

    return 0;
}

void
print_values(void)
{
    printf("a     = %d\nb     = %d\nc.c_a = %ld\nc.c_b = %ld\nc.c_c = %p\n",
           a, b, c.c_a, c.c_b, c.c_c);
}

Program output:

Question Answer Q1-4 in the code, uncommenting and modifying where appropriate.

2.4.1.1 Takeaways

1. Each variable in C (including fields in structs) want to be aligned on a boundary equal to the variable’s type’s size. This means that a variable (b) with an integer type (sizeof(int) == 4) should always have an address that is a multiple of its size (&b % sizeof(b) == 0, so an int’s address is always divisible by 4, a long’s by 8).
2. The operation to figure out the size of all the variables, &end - &a, is crazy. We’re used to performing math operations values on things of the same type, but not on pointers. This is only possible because C sees the variables are chunks of memory that happen to be laid out in memory, one after the other.
3. The crazy increases with mem = &a, and our iteration through mem[i]. We’re able to completely ignore the types in C, and access memory directly!

Question: What would break if we changed char a; into int a;? C doesn’t let us do math on variables of any type. If you fixed compilation problems, would you still get the same output?

2.4.2 Quick-and-dirty Key-Value Store

Please read the man pages for lsearch and lfind. man pages can be pretty cryptic, and you are aiming to get some idea where to start with an implementation. An simplistic, and incomplete initial implementation:

#include <stdio.h>
#include <assert.h>
#include <search.h>

#define NUM_ENTRIES 8
struct kv_entry {
    int key; /* only support keys for now... */
};
/* global values are initialized to `0` */
struct kv_entry entries[NUM_ENTRIES];
size_t num_items = 0;

/**
 * Insert into the key-value store the `key` and `value`.
 * Return `0` on successful insertion of the value, or `-1`
 * if the value couldn't be inserted.
 */
int
put(int key, int value)
{
    return 0;
}

/**
 * Attempt to get a value associated with a `key`.
 * Return the value, or `0` if the `key` isn't in the store.
 */
int
get(int key)
{
    return 0;
}

int
compare(const void *a, const void *b)
{
    /* We know these are `int`s, so treat them as such! */
    const struct kv_entry *a_ent = a, *b_ent = b;

    if (a_ent->key == b_ent->key) return 0;

    return -1;
}

int
main(void)
{
    struct kv_entry keys[] = {
        {.key = 1},
        {.key = 2},
        {.key = 4},
        {.key = 3}
    };
    int num_kv = sizeof(keys) / sizeof(keys[0]);
    int queries[] = {4, 2, 5};
    int num_queries = sizeof(queries) / sizeof(queries[0]);
    int i;

    /* Insert the keys. */
    for (i = 0; i < num_kv; i++) {
        lsearch(&keys[i], entries, &num_items, sizeof(entries) / sizeof(entries[0]), compare);
    }

    /* Now lets lookup the keys. */
    for (i = 0; i < num_queries; i++) {
        struct kv_entry *ent;
        int val = 0;

        ent = lfind(&queries[i], entries, &num_items, sizeof(entries[0]), compare);
        if (ent != NULL) {
            val = ent->key;
        }

        printf("%d: %d @ %p\n", i, val, ent);
    }

    return 0;
}

Program output:

You want to implement a simple “key-value” store that is very similar in API to a hash-table (many key-value stores are implemented using hash-tables!).

Questions/Tasks:

• Q1: What is the difference between lsearch and lfind? The manpages should help here (man 3 lsearch) (you can exit from a man page using ‘q’). What operations would you want to perform with each (and why)?
• Q2: The current implementation doesn’t include values at all. It returns the keys instead of values. Expand the implementation to properly track values.
• Q3: Encapsulate the key-value store behind the put and get functions.
• Q4: Add testing into the main for the relevant conditions and failures in get and put. # Pointers | Casting Slides

2.5 Pointers and Arrays

..are the same thing!

• just different conventions to access memory
• e.g., pointer arithmetic over an array of ints
• moves addresses by size of the int → 4 bytes
• no interaction with individual bytes
  • only whole ints

2.6 Pointer Arithmetic

• consider an integer array → int a[5]
• 5 ints, each of 4 bytes

• so a[0] is:

• so a[1] is → same as ++a!

• we cannot access the individual bytes, i.e., these ones:

what if we want to access the individual bytes?

2.7 Pointer Casting!

• can cast from one pointer type to another!
• between any two pointers!
• a pointer is always the same size, i.e., 4 bytes
• making it point to something else
• doesn’t change the memory underneath
  • but, changes pointer arithmetic!

2.7.1 Casting from int* to char*

• now, as before, if we have → int a[5]

• and we do, char* pc = (char*) a ;

• pc points to the same memory region as a

• but now, can treat it as characters

• i.e., one byte
  
  

• so pc[0] is:

• so pc[1] is → same as ++pc!

2.7.2 Example

Consider the following code:

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

int main()
{
    int* a = (int*)malloc( sizeof(int) ) ;
    assert(a != NULL) ; // SAME as assert (a)

    *a = 1145258561 ;

    printf( "a = %d\n", *a ) ;

    char* ppc = (char*) a ;
    for(unsigned int i = 0 ; i < sizeof(a); ++i )
        printf( "%c ", *pc++ ) ;

    printf("\n") ;
    return 0 ;
}

2.8 Pointer Casting | void*

• can cast any point to a void*
• all of these are valid:

void* pv = malloc(32);
int* pi = (int*) pv ; 
double* pd = (double*) pv ;
char* pc = (char*) pi ; 

• can cast any point to a void*
• all of these are valid:
• cannot dereference a void* directly! compiler does not know the type

3 Function Pointers

Functions have types too. E.g.,

void foo(int i, double d){...}

The “type” of this function is: * takes as input two arguments → one int and one double * returns nothing, hence return type is void * note: this is not the same as a return type of void*

Sometimes, you need to decide which function to call at run time. Why?

3.0.1 Example | Bubble Sort

[Follow along with the Generic Bubble Sort Code]

How do you write a bubble sort? Say for an array of ints?

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

// Sorting ints
void bubble_sort_int( int array[], int array_size )
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
    {
        for( unsigned int j = 0 ; j < i ; ++j )
        {
            if( array[j] > array[j+1] )
            {
                int temp = array[j] ;
                array[j] = array[j+1] ;
                array[j+1] = temp ;
            }
        }
    }
}

// printing out an array
void print_array( int array[], int array_size )
{
    printf( "array = " ) ;
    for( unsigned int i = 0 ; i < array_size ; ++i )
        printf( "%d ", array[i] ) ;
}

int main()
{
    int my_array[] = { 2341, 8632, 3, 2344, 747645 } ;
    int array_size = 5 ;

    // sort the array
    bubble_sort( my_array, array_size ) ;

    print_array( my_array, array_size ) ;

    printf( "\n" ) ;
    return 0 ;
}

Program output:

This works for an array of ints. But what if I want to sort an array of double?

Maybe, write a new function to do that?

// Sorting ints
void bubble_sort_double( double array[], int array_size )
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
    {
        for( unsigned int j = 0 ; j < i ; ++j )
        {
            if( array[j] > array[j+1] )
            {
                double temp = array[j] ;
                array[j] = array[j+1] ;
                array[j+1] = temp ;
            }
        }
    }
}

But what if I want to sort an array of char? Strings? floats? My custom structs? Do we write one function for each?

void bubble_sort_char( char array[], int array_size ){...}
void bubble_sort_strings( char* array[], int array_size ){...}
void bubble_sort_float( float array[], int array_size ){...}
void bubble_sort_struct_student( struct student array[], int array_size ){...}

But what if we don’t know which one will be needed until run time?*

So, depending on the data that we’re given, or some input from the user, we may have to pick one of the above but won’t know of the choice at compile time.

Enter function pointers!

3.0.2 Example | Generic Bubble Sort

A sorting algorithm, at its heart, has two parts:

1. compare: given two elements, let us know which is larger/greater
2. swap: given two elements, exchange their values

so, in a generic sense, we have:

if( is_greater(a, b) ) // If a is larger than b
    swap(a, b)         // swap their values

hence, we can rewrite the bubble sort function, in a “generic” form as:

// Sorting | Generic
void generic_bubble_sort(...)
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
        for( unsigned int j = 0 ; j < i ; ++j )
            if( is_greater( array[j], array[j+1]) )
                swap( array[j], array[j+1] ) ;
}

But, what are the inputs to the function?

We first need to define the type of the array. Since we won’t know the type of the data elements in the array, we can’t pick a specific array type.

But, remember: * arrays and pointers are interchangeable * can cast from any pointer type to void* and back

using this, we define the array as a void*:

void generic_bubble_sort( void* array, ... )

As before, we need to know the size of the entire array, so we can now expand the function signature more:

void generic_bubble_sort( void* array, int array_size, ...)

Remember that a void* pointer is just a pointer to a block of memory. C does not know the type of each element in the array. So, we cannot do: * array[i] → since the type is a void*

We can use pointer arithmetic with void* so this is possible: * array+i → but that moves the pointer forward by i bytes

and not by the number of bytes of the data type. Recall, * char* pc ; pc+1 ; → advances by 1 byte * int* pi ; pi+1 ; → advances by 4 bytes

Hence, we need information about the size of each element, i.e.,

void generic_bubble_sort( void* array, int array_size, 
                                        int element_size ) 

So, we can do: array + (i * element_size) to move to the next element in the array

So, for an int array, we get (element_size = 4):

and for a char array, we get (element_size = 1):

Using this information about element_size, we can rewrite the generic bubble sort function as:

// Sorting | Generic
void generic_bubble_sort( void* array, int array_size, 
                                        int element_size ) 
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
        for( unsigned int j = 0 ; j < i ; ++j )
            if( is_greater( array + (j * element_size), array + ((j+1) * element_size )) )
                swap( array + (j * element_size), array + ((j+1) * element_size )) ) ;
}

Now we see the generic version of bubble sort taking shape.

3.0.3 What is “generic”?

But we are still missing critical information, viz., what are is_greater() and swap()?

Remember that since the generic_bubble_sort() function doesn’t know which exact type it is operating on, we need to somehow provide it with the actual functions that will carry out the comparison and swapping, depending on the type of the array being passed in. For instance, if we are comparing integers, we need a comparator and swap that can operate on integers and similarly ones for structs, doubles, etc.

Wouldn’t it be great, if we could just send in the specific functions as arguments to generic_bubble_sort(), say like,

void generic_bubble_sort( void* array, int array_size, 
                          int element_size, 
                          <SOME_TYPE> is_greater,
                          <SOME_TYPE> swap ) 
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
        for( unsigned int j = 0 ; j < i ; ++j )
            if( is_greater( array + (j * element_size), array + ((j+1) * element_size )) )
                swap( array + (j * element_size), array + ((j+1) * element_size )) ) ;
}

This is precisely where function pointers come in.

We can define is_greater() and swap() to be pointers to functions, i.e., to a type of function (the signatures). Hence, a comparator function pointer would look like:

typedef int (*comparator_function_pointer)( void* l, void* r ) ;

Recall that the typedef keyword associates a name with a type. In the above example, we are saying that comparator_function_pointer is now a name that refers to the (function) type, int (*)( void*, void* ), i.e., a pointer to a function that takes two arguments, each of type void* and returns and int.

Note, that the job of a comparator function is to take two values and, * return positive (non-zero) values if l > r or * a zero if l <= r.

We can define the swap function pointer in a similar manner:

typedef void (*swap_function_pointer)( void* l, void* r ) ;

where, swap_function_pointer is a name that refers to the (function) type, void (*)( void*, void* ) since such a function doens’t need to return anything, just swap the two elements pointed to by the void* arguments.

Updating our sorting function to use the function pointers,

void generic_bubble_sort( void* array, int array_size, 
                          int element_size, 
                          comparator_function_pointer is_greater,
                          swap_function_pointer swap ) 
{
    for( unsigned int i = 0 ; i < array_size-1 ; ++i )
        for( unsigned int j = 0 ; j < i ; ++j )
            if( is_greater( array + (j * element_size), array + ((j+1) * element_size )) )
                swap( array + (j * element_size), array + ((j+1) * element_size )) ) ;
}

So, is_greater is now a function pointer of type, comparator_function_pointer and swap is a function pointer of type, swap_function_pointer.

NOTE: function pointers are invoked exactly like regular functions, i.e., is_greater(...) and swap(...). The above code will work without any changes.

3.0.4 Generic to concrete functions

Eventually, we need to decide what it is that we are sorting. Is it an array of ints, doubless, structs, etc. And at that point in time, we will need the actual, **concrete* functions for comparing and swapping ints (or doubles or whatever).

We we define the two functions (using int as an example):

// Compare and Swap functions for integers
int is_greater_than_int( void* l, void* r )
{
    // cast it from void* to relevant type, int*
    // since we cannot dereference void*
    int* left = l ;
    int* right = r ;

    // compare and return result
    if( *left > *right )
        return 1 ;
    else
        return 0 ; 

   // Can just use this one line instead but not doing so for clarity
   // return ( *l > *r ? 1 : 0 ) ; 
}

void swap_int( void* l, void* r )
{
    // cast it from void* to relevant type, int*
    // since we cannot dereference void*
    int* left = l ;
    int* right = r ;
    int temp = *left ;

    // swap
    *left = *right ;
    *right = temp ;
}

We can define equivalent functions for double,

// Compare and Swap functions for doubles 
int is_greater_than_double( void* l, void* r )
{
    double* left = l ;
    double* right = r ;

    if( *left > *right )
        return 1 ;
    else
        return 0 ; 
}

void swap_double( void* l, void* r )
{
    double* left = l ;
    double* right = r ;
    double temp = *left ;

    *left = *right ;
    *right = temp ;
}

NOTE: the type signatures of the concrete functions must exactly match that of the corresponding function pointers. Otherwise it will result in compile time errors.

3.0.5 Putting it all Together | Using Function Pointers

Now we are ready to use the concrete functions and the pointers in our code:

int main()
{
    int my_array_int[] = { 2341, 8632, 3, 2344, 747645 } ;
    int array_size = 5 ;

    // calling the INTEGER version with the concrete integer comparator and swap
    generic_bubble_sort( my_array_int, array_size, 
                         sizeof(int), /*element size*/
                         is_greater_than_int, 
                         swap_int ) ;

    // calling the DOUBLE version with the concrete DOUBLE comparator and swap
    double my_double_array[] = {1.0, 9485.2, 34.567, 9383.243, 44.1 } ;
    generic_bubble_sort( my_double_array, array_size, 
                         sizeof(double), /*element size*/
                         is_greater_than_double, 
                         swap_double ) ;

    return 0 ;
}

As we see from the above, we are using the same generic_bubble_srt function to sort both, arrays of int and double. The only difference is the different concrete versions of the comparator and swap functions that we pass to the sorting function.

3.0.6 Why bother if we need concrete functions anyways?

Using function pointers allows us to do a few things well: 1. code reuse: the code for sorting doesn’t need to be rewritten each time. In fact, when we have larger, more complex, functions, this will be a lifesaver as we can implement the main “concept” just once and then write “specialized” concrete functions (usually much smaller) as needed. 2. dynamic dispatch: oftentimes, it may not be clear which version of the concrete functions are needed, until runtime! In our example, what if we don’t know if we’re given arrays of ints or doubles until we receive the data at runtime? Then we cannot know which concrete function is to be invoked while writing the code. Hence, we can pick the appropriate function pointer at run time and the code will work correctly! 3. specialization: different data types require different handling. The way we sort numbers will not be the same way we sort strings or other, more complex, data types (e.g., user defined structs).

3.0.7 In-class Exercise | Generic Insertion Sort for struct

Fill out the missing elements in this code:

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

#define NAME_LENGTH 128

struct map{
    char _country[NAME_LENGTH] ;
    char _capital[NAME_LENGTH] ;
} ;


// DEFINE TWO FUNCTION POINTERS, ONE EACH FOR COMPARE AND SWAP


// UNCOMMENT THE TWO ARGUMENTS ONCE YOU DEFINE THE FUNCTION POINTERS
void generic_insertion_sort( void* array, int array_size, int element_size
                            /*is_greater_than my_comparator,
                            swap my_swap*/ )
{

}

// CREATE A NEW STRUCT AND RETURN A POINTER TO IT
struct map* create_new_struct(/*...*/)
{

}

// CREATE THE COMPARATOR AND SWAP FUNCTIONS HERE




// FUNCTION TO PRINT THE ARRAY OF STRUCTS AND ITS ELEMENTS
// PRINT EACH RECORD ON A NEW LINE AS FOLLOWS:
// country: USA             capital: Washington D.C.
// country: Sierra Leone    capital: Freetown
// ...
void print_array_structs(/*...*/)
{

}


int main()
{ 
    unsigned int num_countries ;
    printf( "number of countries: " ) ;
    scanf( "%d", &num_countries ) ;

    // CREATE AN ARRAY OF POINTERS TO STRUCTS
    struct map** array_countries /*= ...*/ ;



    // CREATE num_countries NUMBER OF "COUNTRIES" AND STORE IN THE ARRAY
    // ASK USER FOR INPUT ON COUNTRY/CAPITALS
    // YOU CAN PICK YOUR OWN COUNTRY/CAPITAL COMBINATIONS


    // PRINT THE ARRAY BEFORE SORT
    print_array_structs( /*...*/ ) ;


    // SORT THE ARRAY -- FIRST BY COUNTRY NAME
    generic_insertion_sort( array_countries, num_countries, sizeof(struct map*) /*,...*/) ; 

    // PRINT THE ARRAY AFTER FIRST SORT
    print_array_structs( /*...*/ ) ;


    // SORT THE ARRAY -- SECOND BY CAPITAL NAME
    generic_insertion_sort( array_countries, num_countries, sizeof(struct map*) /*,...*/) ; 

    // PRINT THE ARRAY AFTER SECOND SORT
    print_array_structs( /*...*/ ) ;

    printf( "\n" ) ;
    return 0 ;
}

4 C Memory Model, Data-structures, and APIs

C presents some unique opportunities for how to structure your code and data-structures, but also requires that you’re careful about how data is passed around a program.

4.1 Memory Allocation Options

In C, when creating a variable, you have the option of allocating it in one of multiple different types of memory:

• In another existing structure.
• In the heap using malloc or its sibling functions.
• In global memory.
• On the stack.

It might be surprising, but it is quite uncommon in programming languages to have this flexibility.

4.1.1 Internal Allocation

What does it look like to do internal allocation of one struct or array inside of another? See the following as an example.

#include <stdlib.h>

struct bar {
    /*
     * `arr` is allocated internally to `bar`, whereas `bytes` is a pointer to
     * a separate allocation. `arr` must have a *fixed size*, and `bytes` does not
     * because its allocation can be as large as you want!
     */
    int arr[64];
    unsigned char *bytes;
};

struct foo {
    /* The `bar` structure is allocated as *part of* the `struct foo` in `internal` */
    struct bar internal;
    /* But we can *also* allocate another `bar` separately if we'd prefer */
    struct bar *external;
};

int
main(void)
{
    /*
     * We didn't have to separately allocate the `struct bar internal` as
     * it was allocated with the enclosing `a` allocation. However, we do have to
     * allocate the `external` allocation. In both cases, we have access to a
     * `struct bar` from within `struct foo`.
     */
    struct foo *a = malloc(sizeof(struct foo)); /* should check return value */
    a->external   = malloc(sizeof(struct bar)); /* and this one ;-( */

    /*
     * Note the difference in needing to use `->` when `external` is a pointer
     * versus simply using `.` with `internal`.
     */
    a->internal.arr[0] = a->external->arr[0];

    return 0;
}

Program output:

One of the more interesting uses of internal allocation is in linked data-structures (e.g. like linked lists). It is common in languages like java to implement linked data-structures to have “nodes” that reference the data being tracked.

// This could be made generic across the data types it could store by instead
// using `class LinkedList<T>`, but I'm keeping it simple here.
class LinkedListOfStudents {
    Node head;

    class Node {
        Student s;
        Node next;

        Node(Student s, Node next) {
            this.s    = s;
            this.next = next;
        }
    }

    void add(Student s) {
        // The program has *previously* allocated `data`.
        // Now we have to additionally allocate the `node` separate from the data!
        Node n = new(s, this.head);

        this.head = n;
    }

    // ...
}
// This looks like the following. Note separate allocations for Node and Student
//
// head --> Node------+    ,-->Node-----+
//          | s  next |---'    | s next |---...
//          +-|-------+        +-|------+
//            v                  V
//          Student-+           Student-+
//          | ...   |           | ...   |
//          +-------+           +-------+

Lets see the same in C.

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

struct linked_list_node {
    void *data;
    struct linked_list_node *next;
};

struct linked_list {
    struct linked_list_node *head;
};

struct student {
    // student data here...
    struct linked_list_node list;
};

void
add(struct linked_list *ll, struct linked_list_node *n, void *data)
{
    n->next  = ll->head;
    n->data  = data;
    ll->head = n;
}

struct linked_list l;

int
main(void)
{
    struct student *s = malloc(sizeof(struct student));
    /* Should check that `s != NULL`... */
    add(&l, &s->list, s); /* note that `&s->list` is the same as `&(s->list)` */

    printf("student added to list!\n");

    return 0;
}

/*
 * This looks something like the following. Linked list is *internal* to student.
 *
 * head ----> student-+     ,-> student-+
 *            | ...   |    ,    | ...   |
 *            | next  |---'     | next  |--> NULL
 *            +-------+         +-------+
 */

Program output:

A few interesting things happened here:

1. We’re using void * pointers within the linked_list_node so that the linked list can hold data of any pointer type. You can see that in our list implementation, there is nothing that is student-specific.
2. The list is inline-allocated inside the student structure, which completely avoids the separate node allocation.

Most serious data-structure implementations enable this inlining of data-structure nodes even without requiring the data pointer in the node. We won’t cover that, but you can see a sample implementation.

4.1.2 Heap Allocation

We’ve already seen malloc, calloc, realloc, and free which are our interface to the heap. These provide the most flexibility, but require that you track the memory and free it appropriately⁴

4.1.3 Global Allocation

We have already seen global allocations frequently in examples so far.

#include <stdio.h>

/* A globally allocated array! No `malloc` needed! */
int arr[64];
struct foo {
    int a, b;
    struct foo *next;
};
/* A globally allocated structure! */
struct foo s;

/* Globally allocated *and* initialized integer... */
int c = 12;
/* ...and array. */
long d[] = {1, 2, 3, 4};

int
main(void)
{
    printf("What is uninitialized global memory set to?\n"
           "Integer: %d\nPointer: %p (as hex: %lx)\n",
           arr[0], s.next, (unsigned long)s.next);
    /* Note that we use `.` to access the fields because `s` is not a pointer! */

    return 0;
}

Program output:

Global variables are either initialized where they are defined, or are initialized to 0. Note that they are intialized to all 0s regardless their type. This makes more sense than it sounds because pointers set to 0 are NULL (because, recall, NULL is just (void *)0 – see the “hex” output above), and because strings (see later) are terminated by \0 which is also 0! Thus, this policy initializes all numerical data to 0, all pointers to NULL, and all strings to "".

4.1.4 Stack Allocation

Variables can also be allocated on the stack. This effectively means that as you’re executing in a function, variables can be allocated within the context/memory of that function. An example that allocates a structure and an array on the stack:

#include <stdio.h>
#include <assert.h>

#define ARR_SZ 12

/*
 * Find an integer in the array, reset it to `0`, and return its offset.
 * Nothing very interesting here.
 */
int
find_and_reset(int *arr, int val)
{
    int i;

    /* find the value */
    for (i = 0; i < ARR_SZ; i++) {
        if (arr[i] == val) {
            arr[i] = 0;
            return i;
        }
    }
    /* Couldn't find it! */
    return -1;
}

int
fib(int v)
{
    /* Allocate an array onto the stack */
    int fibs[ARR_SZ] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}; /* looks like a suspicious sequence... */
    int ret;

    ret = find_and_reset(fibs, v);
    /* should have been set to `0`, so this should return `-1` */
    assert(find_and_reset(fibs, v) == -1);

    return ret;
}

int
main(void)
{
    printf("Should find 8 @ 6: %d\n", fib(8));
    /* if the array was the same array for these two calls, it would be found at offset -1 (error) */
    printf("Should find 8 @ 6: %d (-1 is wrong here)\n", fib(8));

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

Key points to realize:

• fibs in fib is allocated on the stack and is initialized in fib!
• We are passing the array into find_and_reset which modifies the array directly as it is passed as a pointer.
• The first time that fib is called, it creates the arr. After we return from fib, the fibs goes away (strictly: its memory is reclaimed as part of returning from fib).
• The second time we call fib, it effectively is a new execution of fib, thus a new allocation of fibs that is now initialized a second time.

4.1.4.1 Stack Usage Example

How do we think about this? The stack starts out in main:

stack          |
|              |
+-main---------+
|              | <--- main's local data (note: no local variables)
+--------------+

What we’re drawing here is a “stack frame” for the main function. This includes all of the local data allocated within the function, and (at least conceptually) also includes the arguments passed into the function (main has none). When it calls fib, a stack frame is allocated for fib, the argument is passed in, and fibs variables are allocated:

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| arg: v       | <--- argument to fib
| fibs[ARR_SZ] | <-+- local variables, allocated here!
| ret          | <-'
+--------------+

fib calls find_and_reset:

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| v            |
| fibs[ARR_SZ] |<--+
| ret          |   | pointer to fibs passed as argument, and used to update arr[v]
+find_and_reset+   |
| arg: arr     |---+
| arg: val     |
| i            |
+--------------+

Since find_and_reset updates the array in fib’s stack frame, when it returns, the array is still properly updated. Importantly, once we return to main, we have deallocated all of the variables from the previous call to fib…

stack          |
|              |
+-main---------+
|              | <--- returning to main, deallocates the fibs array in fib
+--------------+

…thus the next call to fib allocates a new set of local variables including fibs.

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| arg: v       |
| fibs[ARR_SZ] | <--- new version of fibs, re-initialized when we fib is called
| ret          |
+--------------+

4.1.4.2 Common Errors in Stack Allocation

A few common errors with stack allocation include:

• Uninitialized variables. You must always initialize all variables allocated on the stack, otherwise they can contain seemingly random values (see below).
• Pointers to stack allocated variables after return. After a function returns, its stack allocated variables are no longer valid (they were deallocated upon return). Any pointers that remain to any of those variables are no longer pointing to valid memory!

We discuss these next.

Initializing stack-allocated variables. For global memory, we saw that variables, if not intentionally initialized, would be set to 0. This is not the case with stack allocated variables. In fact, the answer is “it depends”. If you compile your code without optimizations, stack allocated variables will be initialized to 0; if you compile with optimizations, they are not initialized. Yikes. Thus, we must assume that they are not automatically initialized (similar to the memory returned from malloc). An example:

#include <stdio.h>

void
foo(void)
{
    /* don't manually initialize anything here */
    int arr[12];
    int i;

    for (i = 0; i < 12; i++) {
        printf("%d: %d\n", i, arr[i]);
    }
}

int
main(void)
{
    foo();

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

Yikes. We’re getting random values in the array! Where do you think these values came from?

References to stack variables after function return.

#include <stdio.h>

unsigned long *ptr;

unsigned long *
bar(void)
{
    unsigned long a = 42;

    return &a;            /* Return the address of a local variable. */
}

void
foo(void)
{
    unsigned long a = 42; /* Allocate `a` on the stack here... */

    ptr = &a;             /* ...and set the global pointer to point to it... */

    return;               /* ...but then we deallocate `a` when we return. */
}

int
main(void)
{
    unsigned long val;

    foo();
    printf("Save address of local variable, and dereference it: %lu\n", *ptr);
    fflush(stdout); /* ignore this ;-) magic sprinkles here */
    ptr = bar();
    printf("Return address of local variable, and dereference it: %lu\n", *ptr);

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

You can see a few interesting facts from the output.

1. The value referenced by *ptr after foo is a random value, and dereferencing the return value frombar causes a segmentation fault.
2. foo and bar contain logic that feels pretty identical. In either case, they are taking a local variable, and passing its address to main where it is used. foo passed it through a global variable, and bar simply returns the address. Despite this, one of them causes a segmentation fault, and the other seems to return a nonsensical value! When you try and use stack allocated variables after they are been freed (by their function returning), you get unpredictable results.
3. The C compiler is aggressive about issuing warnings as it can tell that bad things are afoot. Warnings are your friend and you must do your development with them enabled.

Stack allocation is powerful, can be quite useful. However, you have to always be careful that stack allocated variables are never added into global data-structures, and are never returned.

4.1.5 Putting it all Together

Lets look at an example that uses inlined, global, and stack allocation. We’ll avoid heap-based allocation to demonstrate the less normal memory allocation options in C.

#include <stdio.h>
#include <search.h>
#include <assert.h>

struct kv_entry {
    unsigned long key;
    char *value;
};

struct kv_store {
    /* internal allocation of the key-value store's entries */
    struct kv_entry entries[16];
    size_t num_entries;
};

int
kv_comp(const void *a, const void *b)
{
    const struct kv_entry *a_ent = a;
    const struct kv_entry *b_ent = b;

    /* Compare keys, and return `0` if they are the same */
    return !(a_ent->key == b_ent->key);
}

int
put(struct kv_store *store, unsigned long key, char *value)
{
    /* Allocate a structure on the stack! */
    struct kv_entry ent = {
        .key = key,
        .value = value
    };
    struct kv_entry *new_ent;
    /* Should check if the kv_store has open entries. */

    /* Notice we have to pass the `&ent` as a pointer is expected */
    new_ent = lsearch(&ent, store->entries, &store->num_entries, sizeof(struct kv_entry), kv_comp);
    /* Should check if we found an old entry, and we need to update its value. */

    if (new_ent == NULL) return -1;

    return 0;
}

int
main(void)
{
    /* Allocated the data-store on the stack, including the array! */
    struct kv_store store = { .num_entries = 0 };

    unsigned long key = 42;
    char *value = "secret to everything";
    put(&store, key, value);

    /* Validate that the store got modified in the appropriate way */
    assert(store.num_entries == 1);
    assert(store.entries[0].key == key);

    printf("%ld is the %s\n", store.entries[0].key, store.entries[0].value);

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

In this program you might notice that we’ve used no dynamic memory allocation at all! The cost of this is that we had to create a key-value store of only a fixed size (16 items, here).

4.1.6 Comparing C to Java

C enables a high-degree of control in which memory different variables should be placed. Java traditionally has simple rules for which memory is used for variables:

• Primitive types are stored in objects and on the stack.
• Objects are always allocated using new in the heap, and references to objects are always pointers.
• The heap is managed by the garbage collector, thus avoiding the need for free.

Many aspects of this are absolutely fantastic:

• The programmer doesn’t need to think about how long the memory for an object needs to stick around – the garbage collector instead manages deallocation.
• The syntax for accessing fields in objects is uniform and simple: always use a . to access a field (e.g. obj.a) – all object references are pointers, so instead of having -> everywhere, just replace it with the uniform ..

However, there are significant downsides when the goal is to write systems code:

• Some systems don’t have a heap! Many embedded (small) systems don’t support dynamic allocation.
• Garbage collection (GC) isn’t free! It has some overhead for some applications, can result in larger memory consumption (as garbage is waiting to be collected), and can causes delays in processing when GC happens. That said, modern GC is pretty amazing and does a pretty good job at minimizing all of these factors.
• Many data-structures that might be allocated globally or on the stack, instead must be allocated on the heap, which is slower. Similarly, many objects might want other objects to be part of their allocation, but that isn’t possible as each must be a separate heap allocation, which adds overhead.

4.2 Strings

String don’t have a dedicated type in C – there is no String type. Strings are

1. arrays of chars,
2. with a null-terminator (\0) character in the last array position to denote the termination of the string.

In memory, a simple string has this representation:

char *str = "hi!"

str ---> +---+---+---+---+
         | h | i | ! |\0 |
         +---+---+---+---+

Note that \0 is a single character even though it looks like two. We can see this:

#include <stdio.h>
#include <assert.h>

int
main(void)
{
    int i;
    char *str = "hi!";
    char str2[4] = {'h', 'i', '!', '\0'};        /* We can allocate strings on the stack! */

    for (i = 0; str[i] != '\0'; i++) {           /* Loop till we find the null-terminator */
        assert(str[i] == str2[i]);               /* Verify the strings are the same. */
        printf("%c", str[i]);
    }
    assert(str[3] == str2[3] && str[3] == '\0'); /* Explicitly check that the null-terminator is there */
    printf("\n");
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

So strings aren’t really all that special in C. They’re just arrays with a special terminating character, and a little bit of syntax support to construct them (i.e. "this syntax"). So what’s there to know about strings in C?

4.2.1 string.h Functions

Working with strings is not C’s strong point. However, you have to handle strings in every language, and C provides a number of functions to do so. You can read about each of these functions with man 3 <function>.

4.2.1.1 Core String Operations

• strlen - How many characters is a string (not including the null-terminator)?
• strcmp - Compare two strings, return 0 if they are the same, or -1 or 1, depending on which is lexographically less than the other. Similar in purpose to equals in Java.
• strcpy - Copy into a string the contents of another string.
• strcat - Concatenate, or append onto the end of a string, another string.
• strdup - Duplicate a string by mallocing a new string, and copying the string into it (you have to free the string later!).
• snprintf - You’re familiar with printf, but snprintf enables you to “print” into a string! This gives you a lot of flexibility in easily constructing strings. A downside is that you don’t really know how big the resulting string is, so the n in the name is the maximum length of the string you’re creating.

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

int
main(void)
{
    char result[256] = {'\0', };                /* initialize string to be "" */
    char *a = "hello", *b = "world";
    int c = 42;
    int ret;
    char *d;

    assert(strcmp(a, b) != 0);                  /* these strings are different */

    strcat(result, a);
    strcat(result, " ");
    strcat(result, b);
    assert(strcmp(result, "hello world") == 0); /* should have constructed this string properly */

    d = strdup(result);
    assert(strcmp(d, result) == 0);             /* a duplicate should be equal */
    free(d);

    strcpy(result, "");                         /* reset the `result` to an empty string */

    ret = snprintf(result, 255, "%s %s and also %d", a, b, c);
    printf("\"%s\" has length %d\n", result, ret);
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

Many of these functions raise an important question: What happens if one of the strings is not large enough to hold the data being put into it? If you want to strcat a long string into a small character array, what happens? This leads us to a simple fact…

It is easy to use the string functions incorrectly. Many of these functions also have a strnX variant where X is the operation (strnlen, strncmp, etc..). These are safer variants of the string functions. The key insight here is that if a string is derived from a user, it might not actually be a proper string! It might not, for example, have a null-terminator – uh oh! In that case, many of the above functions will keep on iterating past the end of the buffer

#include <string.h>
#include <stdio.h>

char usr_str[8];

int
main(void)
{
    char my_str[4];

    /*
     * This use of `strcpy` isn't bugged as we know the explicit string is 7 zs,
     * and 1 null-terminator, which can fit in `usr_str`.
     */
    strcpy(usr_str, "zzzzzzz");

    /*
     * Also fine: lets limit the copy to 3 bytes, then add a null-terminator ourself
     * (`strlcpy` would do this for us)
     */
    strncpy(my_str, usr_str, 3);
    my_str[3] = '\0';

    printf("%s\n", my_str);
    fflush(stdout);  /* don't mind me, making sure that your print outs happen */

    /*
     * However, note that `strlen(usr_str)` is larger than the size of `my_str` (4),
     * so we copy *past* the buffer size of `my_str`. This is called a "buffer overflow".
     */
    strcpy(my_str, usr_str);

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

4.2.1.2 Parsing Strings

While many of the previous functions have to do with creating and modifying strings, computers frequently need to “parse”, or try to understand the different parts of, a string. Some examples:

• The code we write in .c or .java files is just a long string, and the programming language needs to parse the string to understand what commands you’re trying to issue to the computer.
• The shell must parse your commands to determine which actions to perform.
• Webpages are simply a collection of html code (along with other assets), and a browser needs to parse it to determine what to display.
• The markdown text for this lecture is parsed by pandoc to generate a pdf and html.

Some of the core functions that help us parse strings include:

• strtol - Pull an integer out of a string. Converts the first part of a string into a long int, and also returns an endptr which points to the character in the string where the conversion into a number stopped. If it cannot find an integer, it will return 0, and endptr is set to point to the start of the string.
• strtok - Iterate through a string, and find the first instance of one of a number of specific characters, and return the string leading up to that character. This is called multiple times to iterate through the string, each time extracting the substring up to the specific characters. See the example in the man page for strtok for an example.
• strstr - Try and find a string (the “needle”) in another string (the “haystack”), and return a pointer to it (or NULL if you don’t find it). As such, it finds a string in another string (thus strstr).
• sscanf - A versatile function will enables a format string (e.g. as used in printf) to specify the format of the string, and extract out digits and substrings.

Some examples:

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

int
main(void)
{
    char *input = "1 42 the secret to everything";
    char *inputdup;
    char *substr;
    char *substr_saved;
    long int extracted;
    char sec[32];

    extracted = strtol(input, &substr, 10);                               /* pull out the first two integers */
    printf("extracted %ld, remaining string: \"%s\"\n", extracted, substr);
    extracted = strtol(substr, &substr, 10);
    printf("extracted %ld, remaining string: \"%s\"\n", extracted, substr);
    substr_saved = substr;

    /* what happens when we cannot extract a long? */
    extracted = strtol(substr_saved, &substr, 10);
    assert(extracted == 0 && substr_saved == substr);                     /* verify that we couldn't extract an integer */

    assert(strcmp(strstr(input, "secret"), "secret to everything") == 0); /* find secret substring */

    sscanf(input, "1 %ld the %s to everything", &extracted, sec);         /* extract out the number and the secret */
    printf("%ld and \"%s\"\n", extracted, sec);

    printf("Using strtok to parse through a string finding substrings separated by 'h' or 't':\n");
    inputdup = strdup(input);                                            /* strtok will modify the string, lets copy it */
    for (substr = strtok(inputdup, "ht"); substr != NULL; substr = strtok(NULL, "ht")) {
        printf("[%s]\n", substr);
    }

    return 0;
}

Program output:

extracted 1, remaining string: " 42 the secret to everything"
extracted 42, remaining string: " the secret to everything"
42 and "secret"
Using strtok to parse through a string finding substrings separated by 'h' or 't':
[1 42 ]
[e secre]
[ ]
[o every]
[ing]

4.2.2 Bonus: Explicit Strings

When you use an explicit string (e.g. "imma string") in your code, you’re actually asking C to allocate the string in global memory. This has some strange side-effects:

#include <stdio.h>
#include <string.h>

char c[5];

int
main(void)
{
    char *a = "blah";
    char *b = "blah";

    strncpy(c, a, 5);

    printf("%s%s%s\n", a, b, c);
    /* compare the three pointers */
    printf("%p == %p != %p\n", a, b, c);

    return 0;
}

Program output:

extracted 1, remaining string: " 42 the secret to everything"
extracted 42, remaining string: " the secret to everything"
42 and "secret"
Using strtok to parse through a string finding substrings separated by 'h' or 't':
[1 42 ]
[e secre]
[ ]
[o every]
[ing]

The C compiler and linker are smart enough to see that if you have already used a string with a specific value (in this case "clone"), it will avoid allocating a copy of that string, and will just reuse the previous value. Generally, it doesn’t make much sense to look at the address of strings, and certainly you should not compare them. You can see in this example how you must compare strings for equality using strncmp, and not to compare pointers.

4.3 API Design and Concerns

Slides

When programming in C, you’ll see quite a few APIs. Throughout the class, we’ll see quite a few APIs, most documented in man pages. It takes some practice in reading man pages to get what you need from them. One of the things that helps the most is to understand a few common patterns and requirements that you find these APIs, and in C programming in general.

4.3.1 Return Values

Functions often need to return multiple values. C does not provide a means to return more than one value, thus is forced to use pointers. To understand this, lets look at the multiple ways that pointers can be used as function arguments.

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

/*
 * `arg` is used to pass an argument that happens to be an array here. In contrast,
 * `ret` is a *second return value*. This function will set the value that `ret` points
 * to -- which happens to be `retval` in the `main` stack frame -- to the value we are
 * getting from the array.
 */
int
get(int *arg, int offset, int *ret)
{
    if (arg == NULL) return -1;

    *ret = arg[offset];

    return 0;
}

/*
 * Again, the array is passed in as the first argument, but this time it is used to
 * store the new value.
 */
int
set(int *ret_val, int offset, int value)
{
    if (ret_val == NULL) return -1;

    ret_val[offset] = value;

    return 0;
}

/*
 * `arrdup`'s job is to duplicate an array by allocating and populating
 * a new array. It will return `0` or not `0` on success/failure. Thus
 * the new array must be returned using pointer arguments. `ret_allocated`
 * is a pointer to a pointer to an array in the calling function, and it
 * is used to return the new array.
 */
int
arrdup(int **ret_allocated, int *args, size_t args_size)
{
    size_t i;
    int *newarr;

    if (ret_allocated == NULL) return -1;

    newarr = calloc(args_size, sizeof(int)); /* 1 below */
    if (newarr == NULL) return -1;

    for (i = 0; i < args_size; i++) {
        newarr[i] = args[i];
    }
    *ret_allocated = newarr; /* 2 and 3 below */

    return 0;
}
/*
 * Lets draw this one. The stack setup when we call `arrdup`:
 *
 * |               |
 * +-main----------+
 * | arr           |<---+
 * | dup           |<-+ |
 * | ...           |  | |
 * +-arrdup--------+  | |
 * | ret_allocated |--+ |
 * | args          |----+
 * | ...           |
 * +---------------+
 *
 * `ret_allocated` points to `dup` in `main`.
 *
 *
 *    3. *ret_allocated = newarr
 *                          ^
 *                          |
 *            ,-------------'
 *           |
 * |         |     |
 * +-main----|-----+
 * | arr     |     |
 * | dup ---'  <------+
 * | ...           |  | -- 2. *ret_allocated
 * +-arrdup--------+  |
 * | ret_allocated ---+
 * | args          |
 * | newarr --------------> 1. calloc(...)
 * +---------------+
 *
 * 1. `arrdup` calls `calloc` to allocate on the heap
 * 2. Dereferencing `ret_allocated` gives us access to `dup`
 * 3. thus we can set dup equal to the new heap memory
 *
 * This effectively enables us to return the new memory into the
 * `dup` variable in main.
 */



int
main(void)
{
    int arr[] = {0, 1, 2, 3};
    int *dup;
    int retval;

    assert(get(arr, 2, &retval) == 0 && retval == 2);
    assert(set(arr, 2, 4) == 0);
    assert(get(arr, 2, &retval) == 0 && retval == 4);
    assert(arrdup(&dup, arr, 4) == 0);
    assert(get(dup, 2, &retval) == 0 && retval == 4);
    free(dup);

    printf("no errors!");

    return 0;
}