ESC190 Lecture Notes: Part 1
Introduction to C

See all lecture notes here.

L2: Introduction to C, pointers and dereferencing

Variables

Like Python, there are different types of variables. Unlike Python, you need to declare what type it is when you initialize. After initializing, we can only change this variable to another value of the same type.

#include <stdio.h>
int main()
{
    int a = 42; // Need to initialize the type of variable
    a = 43; // Changing the value of an already initialized variable
    // a = "hi"; will give an error or warning!

    printf("%d\n", a); // Prints 43

    return 0;
}

Why does C do this? Because compiler needs to assign the appropriate space in the memory table. Therefore, we need to think of variables in a slightly different way. When the code initializes, it stores 42 in memory, i.e. at address 3040 (nothing inherently special about this number, only here so we have a concrete example). The program associates a with this address. The table becomes,

Address	Value
3040	42 (a of type int)
3072
3104
3136

After the line a = 43; is run, the program will look at the address in which the value of a is stored, and change that value to 43. The table then changes to,

Address	Value
3040	43 (a of type int)
3072
3104
3136

Note that this is not how Python works. Changing the value of a variable will change the address of that variable. C is therefore more intuitive in the sense that variables are associated with a location in physical memory. Finally, the line printf("%d\n",a) tells us to print the value of a. The format specifier %d tells the program to interpret a as an integer, and \n tells the code to make a line break. Here is a list of format specifiers.

Pointers

We can store the address of variables using pointers. To create a variable p_a that can store the address of another variable, we use the int* type. The operator & retrieves the address of a given variable.

#include <stdio.h>
int main()
{
    int a = 42;
    int* p_a = &a; // & is the "address-of" operator
                   // int* is the type "address of int"
    printf("%ld\n", p_a); // %ld specifies a long integer
    return 0;
}

In the above code, p_a stores the address of a, which if we continue to use our earlier memory table, is equal to 3040. We can print the pointer using the type specifier %ld, as pointers are stored as long integers (which takes twice as more bits than regular integers).

Typically, long integers are 64 bits on most systems and integers are 32 bits. If you haven't noticed, this is why the addresses in our example tables go up by 32! (to make visualization easier)

The above code may give a warning (depends on system) that the formats that %ld expects and the variable given don't match, as p_a technically has type int*. However, because we can represent p_a as a long integer, we can cast it by running printf("%ld\n", (long int)p_a); instead.

Dereferencing Operator

The dereferencing operator is given by * and acts on a memory address to get the value stored in memory at that address. For example, the code int value_of_a = *p_a; tells us the program to get the value of p_a which is an address, then go to that address, and retrieve the value stored there. Suppose we run the code

#include <stdio.h>
    int main()
{
        int a = 42;
        int* p_a = &a;
        int b = *p_a; 
        return 0;
    }

we get the following memory table:

Address	Value
3040	43 (a of type int)
3072	3040 (p_a of type int*)
3104	(space taken up by above)
3136	43 (b of type int)

The symbol * is used both to define variables (i.e. as a type) and also as an operator for dereferencing. While both are used in the context of memory, they are separate. You may notice that the variable p_a takes up 64 bits instead of the standard 32 bits. This is because addresses are usually stored as long integers by most systems.

Functions

Functions generally work mostly the same way as Python. It is important to note that when an input is passed to the function, the function makes a copy of it in the sense that it uses a different locals frame. For example,

#include <stdio.h>
    int f(int x){
        return x + 1;
    }
    int main()
{
        int a = 42;
        int* p_a = &a;
        int b = *p_a; 

        int c = f(b);
        return 0;
    }

which gives the additional memory table,

Locals Frame [Function]	Value
1280	42 (x of type int)
1312
1344
1376

Therefore, if we were to change the value of x inside the function, it would only affect the value at address 1280, and the value of b (from the main memory table) will not be affected.

L3: Binary representation of ints, floats, and strings

At a fundamental level, computer memory can be seen as a physical table where in each cell, the voltage is either high (1) or low (0). It does not know anything about types. A single 0 or 1 is a bit, and

• 8 bits = byte
• kilobyte = 1024 bytes
• megabyte = 1000 kilobytes

The memory table stores a lot of information, including metadata. You will learn more about this in courses such as ECE253 and higher level 300+ courses. In this course, we will only deal with memory tables in the context of storing variables.

Binary

We can interpret the binary number \(1101\) as \[1101_\text{binary} = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 13.\] Remark: that this is also exactly how decimals work! Also, \[521 = 5\cdot 10^2 + 2 \cdot 10^1 + 1 \cdot 10^0.\] It is less obvious how to go from decimal to binary. Suppose we want to convert \(25\) to binary.

• Right-to-left:
1. 25 is odd, so last digit in binary is \(1\). We now have to represent (25-1)/2 = 12.
2. 12 is even, so 2nd last digit in binary is \(0\). We now have to represent (12-0)/2 = 6.
3. 6 is even, so 3rd last digit in binary is \(0\). We now have to represent (6-0)/2 = 3.
4. 3 is odd, so 4th last digit in binary is \(1\). We now have to represent (3-1)/2 = 1.
5. We can represent 1 by \(1\).
which gives \[11001\] A Python implementation is given below:

def get_decimal_digits(d):
  digits = []
  while d != 0:
    digits = [(d % 10)] + digits
    d //= 10
  return digits

def get_binary_digits(d):
  digits = []
  while d != 0:
    digits = [(d % 2)] + digits
    d //= 2
  return digits

print(get_decimal_digits(521))
print(get_binary_digits(25))

• Left-to-right:
• The idea is that we want to write 25 as \[25 = b_k2^k +b_{k-1}2^{k-1} + \cdots + b_12^1 + b_0\] Are we able to figure out what \(k\) is? We can determine the largest power of 2 that fits into 25, which is \(2^4=16\). We still need to represent \(25-16=9\)
• The largest power of 2 that can fit in 9 is \(2^3=8\). We then need to represent \(9-8=1\)
• The largest power of 2 that can fit in 1 is \(2^0=1\). We are now done.
We have decomposed \(25\) into powers of 2. That is, \[25 = 2^4 + 2^3 + 2^0 = 11001_\text{binary}.\]

For 8-bit binary numbers, the 0th digit is the sign and the other 7 bits are the quantity. For example, \[ b_0b_1b_2b_3b_4b_5b_6b_7 = \begin{cases} +(b_12^6 + b_22^5 + b_32^4+b_42^3 + b_52^2 + b_62^1 + b_7) & \text{if }b_0 = 0 \\ -(b_12^6 + b_22^5 + b_32^4+b_42^3 + b_52^2 + b_62^1 + b_7) & \text{if }b_0 = 1 \end{cases} \] This is not the only way to represent numbers. Different schemes exist for different types, though there are some standard conventions (i.e. IEEE 754 for floats). In Unicode, the first bit tells us whether we use ASCII characters (which we will use) or Unicode (which is more complicated).

Characters and Strings

The above discussion helps us understand how characters and strings are stored and worked with in C. Consider the following program,

#include <stdio.h>
int main()
{
    char c = 'x';
    printf("%c %d", c, (int)c);

    return 0;
}

Notice that the program outputs x 120. This is because we can interpret c as a character, so it outputs 'x'. Alternatively, we can interpret it as an integer, in which case it outputs its ASCII value 120. We can store strings by writing

#include <stdio.h>
int main()
{
    char* s = "Hello, World!";
    return 0;
}

where s is the address of the first character in the string (in this case, the address of 'H'). The last character in the string is \0 (can otherwise write it as 0 or NULL). Therefore, the program is able to read off a string by going to the address of the first character, and moving down the table (which is where the other characters are stored) until the null character is found. Explicitly, this is stored in the memory table as (only showing part of the table)

16	'H'
17	.
18	.
19	.
20	.
21	.
22	.
23	.
24	'e'
25	.
26	.
27	.
28	.
29	.
30	.
31	.
32	'l'
33	.
34	.
35	.
36	.
37	.
38	.
39	.

Here, the dot is used to denote that it takes 8 bits (1 byte) to store each character.

L4: Strings and Changing Variables in Functions

Note that in the above example, not every address was written down. In C, every address is a byte. We can use the sizeof operator, which gives the size of an object. For example, sizeof(int) gives the size of an int and sizeof(a) gives the size of the variable a. The output is represented in bits. We can print this to console using printf("%ud", sizeof(int)).

Depending on your system, you may get a warning in the above print statements. This is because sizeof returns a size_t type, that could either be an unsigned integer or an unsigned long integer (depending on your system). You may choose to use %lu or %zu instead.

Strings

Recall that each character will always be 1 byte. The reason this is important is if we recall strings can be defined using a pointer,

char *s = "xyz"

we get a memory table that looks like,

Memory	Value
1824	'x'
1832	'y'
1840	'z'
1848	\0
1856	1824 (s of type "address of char")

A few key observations:

• Each address can hold 1 byte and each character is 1 byte. Perfect!
• The null character \0 signifies the end of the string, so that we know when to stop. This is important, because we don't store the length anywhere!
• We are using double quotes here. Double quotes automatically include the null character at the end.
• The variable s gets stored elsewhere and is equal to the address of the first character.
• The variable is placed somewhere in memory that is generally not the locals frame. However, most variables are typically stored in the main locals frame. This will be important in the next subsection where we will be also working with the locals frame of a particular function.

We can treat s as just any other variable! For example,

printf("%c", *s);

will print out 'x', and

printf("%ld", (long int)s);

will print '1824'.

Changing Variables in Functions

Suppose we have the following naive attempt at changing a variable through a function. We have,

#include <stdio.h>
void f(int a) // NOTE: INCORRECT
{
  a = 12;
}

int main()
{
  int a = 5;
  f(a);
  printf("%d", a);
}

When the function is run, a locals frame for the function will be created, so after the line a=12; is run, the memory table looks like this:

Locals Frame [f]	Value
128	12 (a of type int)
160
192

Locals Frame [main]	Value
1600	5 (a of type int)
1632
1664

Therefore, when variables are defined inside a function, they are stored in a different locals frame. When we exit the function, we no longer get access to inside the function locals frame and the original value of a is unchanged.

So how do we fix this?

The standard solution is to instead pass the value of a (or else the function will just create a copy of it), we pass in the address &a. The function does not need to change what this address is, but it can read off this value and go to the proper location in memory and modify it. The correct implementation is

#include <stdio.h>
void f(int* p_a)
{
  *p_a = 12;
}

int main()
{
  int a = 5;
  f(&a);
  printf("%d", a);
}

The parameter that the function takes in is of type int* so we need to send in an address. Inside the function, the line *p_a = 12; tells us to go to the address given by p_a (via the dereference operator *) and assign the value 12 to it. The memory table then looks like

Locals Frame [f]	Value
128	1600 (p_a of type int*)
160
192

Locals Frame [main]	Value
1600	12 (a of type int)
1632
1664

How does this relate to Python? If we consider the code

def f(a):
  a = 12
def main():
  a = 5
  f(a)

then the same thing happens in C. The value of a remains unchanged. However, lists are mutable and can be changed inside a function. Consider

def f(L):
  L[0] = 12
def main():
  L = [5, 6]
  g(L)

Then passing in the variable L means having the L in the function refer to the same address as the L defined in the main function. However in Python, most variables are immutable (integers, floats, strings, Booleans, and tuples), so we cannot change them by modifying their value at a certain address! To see this concretely, feel free to run:

a = 1
print(id(a)) # prints the address
a = 2
print(id(a)) # prints the address

and see that the memory addresses are different, so behind the scenes, Python is writing 2 in a new space in memory and then associating the variable a with this new address.

Because C gives us more freedom to work directly with the memory, we can do much more powerful things and implement more complex data structures, as we will see in the coming weeks.

L5: Arrays and Pointer Arithmetic

Swapping two integers

Problem: Write a function to swap two integers.

Similar to the problem of changing the value of a variable, we need to pass in the address of two variables instead of the values. This tells the function where in the memory table to look in order to swap the two integers. We have,

#include <stdio.h>
void swap(int *p_a, int *p_b)
{
  int temp = *p_a; // Create a temp variable in the function's local frame
  *p_a = *p_b;
  *p_b = temp;
}

int main()
{
  int x = 7;
  int y = 8;
  swap(&x, &y);

  return 0;
}

Pointer Arithmetic

Recall that strings can be stored using pointers. For example, the code

char *str = "hello";
printf("%c\n", str[1]);

will print out 'e', as C will treat the variable str of type char * as an array. Behind the scenes, the code is performing pointer arithmetic. That is, the above is equivalent to:

char *str = "hello";
printf("%c\n", *(str + 1));

When we have multiple oeprations, we perform what is in the parentheses first (similar to BEDMAS). Therefore, this code tells us to get the value of str, which is the address that holds the character 'h', then increase it by 1 byte (which is the address that holds the next character, 'e'). Finally, the dereferencing operator gets the value stored at the address str + 1.

There is one subtlety here, which we will see in the next section.

Arrays

An array is a block of memory containing a sequence of elements, of the same type. Arrays always have a pre-specified size. We can initialize an array using curly braces.

int arr[5] = {1,2,3,4,5};

This is unlike Python, where we do not need to specify a size, and arrays can dynamically change in size. If you are familiar with numpy, C arrays are much more similar to numpy arrays. We are allowed to retrieve and modify array elements,

#include <stdio.h>
int main()
{
  int arr[5] = {1,2,3,4,5};
  printf("%d\n", arr[2]); // prints 3
  arr[2] = 6;

  printf("%ud, %ud\n", sizeof(arr), sizeof(arr[0])) // prints 20, 4
  printf("#of elements in arr is %d\n", sizeof(arr) / sizeof(arr[0]))
}

The first three lines in the main function will create the following memory table, where we are assuming integers take 32 bits:

Locals frame [main]	Value
1600	1 (arr of type int, size 5)
1632	2
1664	3
1696	4
1728	5

The sizeof operator gives how much space the variable takes up, in bytes. This means that sizeof(arr[0]) will give 4 bytes, since arr[0] is an integer and sizeof(arr) will give 20 bytes, since 20 = 4 x 5, where 5 is the number of elements.

When passing an array to a function, it gets converted to a pointer. For example, if we have the function

#include <stdio.h>
void set0(int *p_a)
{
  *p_a = 0; // p[0] = 0;
  printf("%ud\n", sizeof(p_a)); // prints 8
}
int main()
{
printf("%ud", 3);
  int arr[5] = {1,2,3,4,5};
  printf("%d\n",arr[0]); // prints 1
  set0(arr);
  printf("%d\n",arr[0]); // prints 0
}

Because arrays get converted to pointers, calling sizeof inside the function gives us the length of the pointer, which is 8 bytes. This is why when writing functions that deal with arrays, we typically need to pass in another parameter so the function will know how long the array is.

Because arrays are so similar to pointers, we can treat them as pointers when performing operations. For example, arr[2] = 6; is the same as *(arr + 2) = 6;

There is one slight caveat here to any eagle-eyed student! When we worked with strings, str + 2 added 2 bytes to the pointer. Here however, arr + 2 added 2 x 4 = 8 bytes to the pointer! Therefore, pointer arithmetic is conscious of the type of the pointer.

Therefore, *(arr+i) and arr[i] will always be equivalent.

Revisiting Strings

We can initialize strings the same way we initialize arrays because of how similar they are. The following are equivalent:

#include <stdio.h>
int main()
{
  char arr1[4] = "uvw";
  char arr2[4] = {'x', 'y', 'z', '\0'};
  char arr3[3] = {'a', 'b', 'c'}; // Incorrect, will produce weird results
  printf("%s\n", arr1); // uvw
  printf("%s\n", arr2); // xyz
  printf("%s\n", arr3); // something weird!
}

Some key points:

1. The size of the array should be set to 1 more than the number of characters. This is because strings always end with the null character \0.
2. The null character is automatically included when we define a string by concatenating characters, i.e. like in the definition of arr1.
3. If we forget to include the null character when defining it explicitly as an array, i.e. for arr3, then the program doesn't know when to stop. When printing (and other operations), it will only stop once it reaches a null character. On my machine, the output was abcuvw.

Alternatively, we can define arrays (and strings) without specifying a size via:

char arr[] = {'x', 'y', 'z', '\0'};

The program will automatically determine how many entries this array has.

Arrays in Functions

Initializing arrays inside functions is similar to initializing an integer inside a function, except we now allocate a block of memory. Here is incorrect code of how we can make an array.

#include <stdio.h>
int *make_array_wrong()
{
  int arr[5] = {1, 2, 3, 4, 5};
  return arr;
}

We must not access something like arr[0] outside the function. Accessing the actual address arr is not a problem, but arr is not anymore the address of anything in particular.

To properly do this, we need to allocate a block of memory on the heap (as opposed to on the stack).

• Heap: The memory table in general that's not tied to the locals frame
• Stack: In the locals frame of the function

To do this, we can use the following notation:

int *a = (int *)malloc(sizeof(int) * 12);

where a is now a pointer to a block of memory of size 12 * sizeof(int) bytes. This is enough space for 12 integers. Note that we need to cast the pointer to an integer pointer using (int *), since malloc returns a void pointer (i.e. it just knows to create this much space in the memory table, but doesn't know what this space is used for). To create an array inside a function, we can use the following code,

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

int *make_array_right()
{
    int *a = (int *)malloc(5*sizeof(int));
    a[0] = 1;
    a[1] = 2;
    a[2] = 3;
    a[3] = 4;
    a[4] = 5;

    return a;
}
int main()
{
  int *a_good = make_array_right();
  printf("%d" , a_good[0]);

  free(a_good);
}

To use malloc() we need to use the stdlib.h library (standard library). In the above code, a is a local variable, but it refers to a place in memory that doesn't go away, so we can still refer to it outside the function.

It is also important to free the memory when we no longer need the variable. This is because not using free() could result in a memory leak, i.e. blocks of memory are no longer needed but the computer still thinks are in use. Once the memory block is freed accessing it is undefined behavior.

L6: More on Strings and Double Pointers

Editing Strings

Recall that we can define strings in two ways. Both ways are similar, but there are key differences that are very important. Consider,

#include <stdio.h>
int main()
{
  // Defining string using address of character
  char *str = "abc";
  // not allowed to go str[1] = 'x';
  printf("%c\n", str[1]); // allowed to print str[1]
  printf("%zu\n", sizeof(str)); // 8 (since pointers are long ints)

  // Defining string using array
  char str2[] = "abc"; // alternatively char str2[] = {'a','b','c','\0'};
  str2[0] = 'x'; // fine
  printf("%s\n", str2); // xbc
  printf("%zu\n", sizeof(str2)); // 4 ({'a','b','c','\0'} takes up 4 bytes)
}

The main difference is that when we are defining the string using the first method, the string is placed somewhere in memory that is generally not the locals frame and thus we are not allowed to change it, only read it. But defining it as an array does place it in the main locals frame, and thus we can change it like a regular array.

Because one is an array and the other is an address, their sizes are different as well. We can also define strings a third way, using malloc, which was briefly touched upon last lecture. We can have,

#include <stdio.h>
int main()
{
  char *str3 = (char *)malloc(3*sizeof(char)); // same as malloc(3)
  str3[0] = 'b';
  str3[1] = '\0';
  printf("%s\n", str3); // b
  free(str3); // frees memory
}

which will produce the following memory table,

Locals Frame [main]	Value
32	3200 (str3 of type int *)
64
96

3200	'b''
3201	'\0'
3202

Remember that it is always best practice to free variables once they are no longer needed.

String in Functions

Similar to arrays, we cannot create strings inside a function and return the address of the local variable. Consider the following code,

#include <stdio.h>
char *make_string_wrong(int sz)
{
  char str[sz];
  return str;
}
int main()
{
  char *str = make_string_wrong(3);
  str[0]; // not allowed , might crash
  printf("%ud\n", str); // fine, prints the address where str used to be 
}

Instead, we need to use malloc again. The following code works,

#include <stdio.h>
char *make_string_right(int sz)
{
  char *str = (char *)malloc(sz*sizeof(char));
  return str;
}
int main()
{
  char *str = make_string_right(3);
  str[0]; // allowed
  printf("%lu\n", (long int)str); // 94182356746912 when I ran it
}

Double Pointers

Consider the following code,

#include <stdio.h>
int main()
{
  int *a = 0;
  int **p_a = &a;

  &a; // 3032
  *p_a // 0;
  *(&a) // a;
  &(0) // makes no sense
}

This looks like a mess, but we can look at the memory table.

Locals Frame [main]	Value
3032	0 (a of type int *)
3064	(space used by above)
3092	3032 (p_a of type int **)
3124	(space used by above)

and we can work through the above computations:

1. &a gives 3032, since that is the address of where a lives
2. *p_a gives 0, since it takes the value of p_a (which is 3032), and it looks at which value lives at that address, which happens to be 0.
3. *(&a) will always give a since it first determines the address of a and then the dereference operator tells the program to go to the value stored at that address, which is a.
4. &(0) makes no sense since we cannot take the address of a value that is not a variable.

L7: More Memory and String Operations

Initializing Pointers

Consider the following code, which initializes a pointer in three different ways:

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

int main()
{
  int *p_a = 0; // p_a is an address of an integer
                // 0 is not a valid address 
  printf("%d\n", *p_a); // error

  // METHOD 1: Use Malloc
  p_a = (int *)malloc(sizeof(int));
  printf("%d\n", *p_a); // not error, but value can be anything
  *p_a = 42; // p_a[0] = 42
  printf("%d\n", *p_a); // 42
  free(p_a) // Need to free, see comments!

  // METHOD 2: Assign it using the address
  int b = 43;
  p_a = &b;
  printf("%d\n", *p_a); // 43

  // METHOD 3: Using arrays
  int c[] = {5, 8, 10};
  p_a = c;
  p_a[0]; // 5

  p_a++; // p_a = p_a + 1
  p_a[0]; // 8
}

Some comments about the above code:

1. Initializing a pointer like int *p_a = 0; is a common thing to do, but we can't do anything since 0 is not a valid address
2. Instead, we can use malloc to free up space in memory and store that address in p_a
3. If we later store a different address in p_a (without freeing first), then the address of the memory allocated by malloc will be lost, which can lead to memory leaks.
4. To prevent memory leaks, we need to free the memory before reassigning it. If free(p_a) at the very end of the program, it will cause a crash because it will attempt to free the memory at the address &b instead, which wasn't created using malloc.
5. If we tried to run p_a++; after the malloc instead, it will crash, since we only allocated enough memory for a single integer.

We can initialize double pointers the same way,

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

int main()
{
  int **p_p_a = 0;
  // accessing *p_p_a here gives an error
  p_p_a = (int **)malloc(sizeof(int *));
  // p_p_a is valid address, so we can access *p_p_a;
  *p_p_a = (int *)malloc(sizeof(int));
  **p_p_a = 58; 
}

String Operations

Consider the following function to print an array:

void print_array(int *arr, int sz)
{
  int i;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

We can write something similar to print a string manually,

void manual_print_str(char *str)
{
  int i = 0;
  while(str[i] != '\0'){
    printf("%c", str[i]);
    i++;
  }
  printf("\n");

  /*
  // Also Valid
  for(i = 0; str[i] != '\0', i++){
    printf("%c", str[i]);
  }
  */
}

The key difference is that we don't need to pass the size of the string. We can tell when to stop when we reach the null character '\0'. An alternative way is via pointer arithmetic,

void print_str(char *str)
{
  while(*str != '\0'){
  // while(*str) works too
    printf("%c", *str);
    str++;
  }
  printf("\n");
}

We can simplify our code by sayingwhile(*str) instead, which works since *str evaluates to true whenever it is not null We can also determine the length of a string in similar ways,

int manual_strlen(char *str)
{
  int i = 0;
  while(str[i] != '\0'){
    i++;
  }
  return i;
}

or if you want to show off,

int manual_strlen2(char *str)
{
  int length = 0;
  while(*str++){
    length++;
  }
  return length;
}

Here, *str++ means first access *str then increment str. Here is a list of common shortcuts:

1. str++ puts str + 1 into str, the value of *str is str[0]
2. *++a means first increment a then access *a
3. a++ = a + 1 is undefined behaviour

L8: More Strings and Double Pointers

Copying Strings

Suppose we wish to copy a string, we can use the following code:

char *my_strcpy(char *dest, char *src)
{
  int i = 0;
  while(src[i] != '\0'){
    dest[i] = src[i];
    i++;
  }

  /* alternatively 
  for (int i = 0; src[i] != '\0'; i++){
    dest[i] = src[i];
  }
  */

  // At this point dest is not a valid string -- not null-terminated
  dest[i] = '\0';
  return dest;
}

This copies the string src to the string dest. Assume that there is enough space in dest to store src + the trailing NULL. Alternatively, we can perform a do while loop, that is:

char *my_strcpy(char *dest, char *src)
{
  int i = 0;
  do{
    dest[i] = src[i];
    i++;
  } while(src[i - 1] != '\0');

  return dest;
}

Here, the code inside the do is always run, and then the condition is checked. If the condition is false, the loop is exited. It is important to point out that this doesn't need an additional line that adds the null character: it is done automatically (since it copies before checking the condition). We can also show off by doing it the fancy way,

char *my_strcpy_fancy(char *dest, char *src)
{
  char *old_dest = dest;
  while(*dest++ = *src++);
  return old_dest;
}

This works because *dest++ = *src++ first copies *src to *dest then increments both pointers. The while loop terminates when *dest = *src, which is equal to *src is null. These programs can be called in the main function by defining an empty string that is long enough, i.e.

int main()
{
  char str1[100];
  char str2[] = "Hello";
  my_strcpy(str1, str2);
  printf("%s\n", str1);
}

This is usually not good practice because it is unreadable and show-off like.

Reading Input

To read input from the keyboard, we can use scanf. This works similar to printf where you give an input from the keyboard, and you have a format specifier to specify how to interpret the input. The second parameter is where the address in which the input is stored. Here are some common ways of receiving input:

int main()
{
    int a;
    scanf("%d", &a);
    printf("You entered: %d\n", a);


    float f;
    scanf("%f", &f);
    printf("You entered: %f\n", f);

    char s[100];
    scanf("%s", s);
    printf("You entered: %s\n", s);

    char *p_a = (char *)malloc(100);
    scanf("%s", p_a);
    printf("You entered: %s\n", p_a);

    int *p_int = (int *)malloc(sizeof(int));
    scanf("%d", p_int);
    printf("You entered: %d\n", *p_int);
}

Double Pointers

Oftentimes, we need a double pointer when reading from input. Suppose we wish to make a function that constructs an array of integers from an input. We need a double pointer because we can describe an array using its address, and we need the address to this address such that we can actually modify it. We can implement it the following way,

int *get_int_arr_from_input(int **p_arr, int *p_n)
{
  printf("Number of elements that are coming: ");
  scanf("%d", p_n);
  *p_arr = (int *)malloc(*p_n * sizeof(int));
  for (int i = 0; i < *p_n; i++){
    scanf("%d", &(*p_arr)[i]);
  }
}

int main()
{
  int *arr;
  int n;
  get_int_arr_from_input(&arr, &n);
  for (int i = 0; i < n; i++){
    printf("%d ", arr[i]);
  }

  free(arr);
}

Here, the double pointer is necessary. Some key things to note:

1. Note that &(*p_arr)[i] is equivalent to the expression *p_arr + i. We can interpret this as: *p_arr is the address of the actual array, then we want to access element i and then get its address.
2. The reason why we pass in int *p_n as well is so that we can write down the length of this array to some variable stored outside of the function's local frame.

L9: Structures

Basic Example

We can create our own data structures in C. As an illustrative example, let us create a structure that can represent UofT students. We want to represent:

1. char st_number_str[11] This is the student number (10 digits + NULL). Note that this is technically a number but we represent it this way because we don't need to do math operations on it. int faculty_num For our purposes, this will be something like 0 for FASE, 1 for Arts & Science, 2 for Kinesiology, etc.

We can create a structure, initialize it, and create a function that prints it out with the following code,

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

struct uoft_student{
  char st_number_str[11];
  int faculty_num;
};

void print_uoft_student(struct uoft_student s)
{
  printf("student number: %s\n", s.st_number_str);
  printf("faculty number: %d\n", s.faculty_num);
}

int main()
{
  struct uoft_student s;
  s.faculty_num = 0;
  // s.st_number_str = "1234567890"; // error
  strcpy(s.st_number_str, "1234567890");

  print_uoft_student(s);
}

Note that in order to initialize a string, we can't use the notation s.st_number_str = "1234567890" but instead use the strcpy function from string.h.

How does this look like in memory? We get the following memory table,

Address	Value
448	"abc" (st_number_str, part of s1)
480	0 (faculty_num, part of s1)

When we call the function print_uoft_student, we pass in the entire structure s as a parameter. This means the function then creates a copy of s and stores it in the local frame of the function.

New Types

In C, we can use typedef to define new custom types. This is useful if we have a boolean we definitely know is true or false but we're implementing it with an integer. Then we can write something like

typedef int BOOL;

which allows us to write BOOL t=0; And for our earlier example with UofT students, we can write

typedef struct uoft_student uoft_student;

So instead of writing struct uoft_student in the future, we only need to write uoft_student. An alternative way of writing this is built into the structure definition, i.e.

typedef struct uoft_student{
  char st_number_str[11];
  int faculty_num;
} uoft_student;

This is what we'll use from now on for this lecture, but there are some cases in the future where we have to be more careful. This doesn't change how the code works, but it just helps with reading the code. For example, the code we had earlier becomes slightly more readable, i.e.

#include <stdio.h>
#include <string.h>
typedef struct uoft_student{
  char st_number_str[11];
  int faculty_num;
} uoft_student;

void print_uoft_student(uoft_student s)
{
  printf("student number: %s\n", s.st_number_str);
  printf("faculty number: %d\n", s.faculty_num);
}

int main()
{
  uoft_student s;
  s.faculty_num = 0;
  // s.st_number_str `= "1234567890"; // error
  strcpy(s.st_number_str, "1234567890");

  print_uoft_student(s);
}

Functions on Structs

Suppose we wish to modify a struct inside a function. As you may have guessed, we can't just pass in the struct, as that creates a copy! Instead, we need to pass in a pointer to the struct. For example, we can write a function that changes the faculty number of a student to 1,

void drop_to_artsci(uoft_student *p_s)
{
  (*p_s).faculty_num = 1;
}

and in the main file, we can call drop_to_artsci(&s). There is another notational shortcut! Instead of writing something like (*a).b we can write down the equivalent statement a->b. The above function can then be rewritten in a more suggestive manner,

void drop_to_artsci(uoft_student *p_s)
{
  p_s->faculty_num = 1;
}

The way people usually think about it is if we pass in a pointer to the structure, we typically want to use the arrow and we pass in just the structure, we don't want to use it (or else it doesn't make sense!).

Pointers in Structures

Consider the following structure,

typedef struct waterloo_student{
  char *st_number_str;
} waterlooser;

and we wish to change the student id. There are two ways we can try to do this, with one incorrect and the other correct. They are:

void change_w_id_bad(waterlooser w)
{
  w.st_number_str = (char *)malloc(5 * sizeof(char));
  strcpy(w.st_number_str, "666");
}

void change_w_id_good(waterlooser w)
{
  strcpy(w.st_number_str, "666");
}

The reason why the first method is incorrect is because w.st_number_str is a pointer to where the string is stored. When it passes through the function, it creates a copy of the pointer, but we still have the information of where in memory this string is stored. If we try to (incorrectly) allocate space, then w.st_number_str will now point to somewhere else in memory that is big enough to store "666, but the original address of w.st_number_str will stay the same.

If we directly use strcpy, then it will copy the string "666" to the destination w.st_number_str whose value is the address in which the original string is stored.

Creating Structs

Suppose we wish to create a waterlooser with a function. To do so, we need a pointer to a pointer,

typedef struct waterloo_student{
  char *st_number_str;
} waterlooser;

void create_waterlooser(waterlooser **p_p_w)
{
  *p_p_w = (waterlooser *)malloc(sizeof(waterlooser));
  (*p_p_w)->st_number_str = (char *)malloc(5 * sizeof(char));
  // (*(*p_p_w)).st_number_str = (char *)malloc(11 * sizeof(char)); // same as above
}

int main()
{
  waterlooser *w;
  create_waterlooser(&w);
};

Inside the create_waterlooser function, we need to allocate enough space to store 1 waterlooser, and then allocate enough space to store their student number. In the first line, we wish to obtain the address of the memory block that is big enough to store 1 waterlooser, and set that as the address of the waterlooser. After that, we can go to that address, and at that address write the address of a student number string, which we can do via malloc. Remember that st_number_str is a pointer itself!

Note that in the above, we are modifying the address of st_number_str! In the earlier examples (where we didn't use a double pointer), we could only change the value at this address using strcpy but we can't change where this points to. Using a double pointer allows us greater degrees of freedom.

In the main function, we originally have a pointer to the waterlooser, but it is not a valid address. We can pass in the address of this pointer to our create_waterlooser function, which then makes it a valid address to a waterlooser.

As always, we need to free the memory we allocated once it is no longer needed. This can be done in a function that is typically called destroy. There are a few subtleties though! The below function works,

void destroy_waterlooser(waterlooser *p_w)
{
  free(p_w -> st_number_str);
  free(p_w);
}

Note that the order of these lines matter! If we try to free p_w first, we can do that, but we are no longer able to access p_w -> st_number_str.

L10: Memory Model for Structures and Header Files

Structure Padding

Suppose we have the following code,

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

typedef struct student1{
  char name[5];
  int f;
} student1;


int main()
{
  student1 s1;
  printf("%lu, %lu, %lu\n", (unsigned long)(&s1),
                         (unsigned long)(&(s1.name)),
                         (unsigned long)(&(s1.f)));
  printf("%lu\n", (unsigned long)sizeof(s1));
  return 0;
}

On my computer, this outputs:

140728275508316, 140728275508316, 140728275508324
12

These are big numbers, but note the following observations:

1. The first two numbers are the same. That is, the address of s1 corresponds to the address of s1.name.
2. The address of s1.f is 8 bytes after the address of s1.name, which should only take 3 bytes. Why is this the case? This is because the compiler is trying to align the data in memory. In this case, it is trying to align the data to 4 bytes. This process is known as structure padding.
3. The total size of the structure is \(5+3+4=12\) bytes, where 5 comes from the string, the 4 comes from the integer, and there are 3 empty bytes.

More Examples

Let's work through what the memory table looks like for the following code,

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

typedef struct student2
{
  char *name;
  int f;
} student2;

void set_name2a(student2 s)
{
  strcpy(s.name,"abc"); // s.name needs to be valid address
}

int main()
{
    student2 s2;
    // s2.name = (char *)malloc(5*sizeof(char));
    set_name2a(s2);
    printf("%s\n", s2.name);
}

If we run this code as is (with the line commented out), then the program will crash, even though we are changing the name of the student in a similar way as the previous lecture. The difference is that there will be a segmentation fault. When we write student2 s2; it creates a struct, but s.name is just some random address, so we can't write "abc" to it!

If we uncomment the line, then the program will run, since we have allocated enough space for the string and we can set s2.name to the address of this memory block.

Some Exercises

Here are a few exercises, which tests your understanding of structures and pointers, based off of some previous examples. Don't cheat!

Header Files and Command Line

First, how do we run C code through command line?

1. Open up a terminal and make sure you are in the correct directory. To do so, you can type ls or dir to see subfolders and you can move between them by typing cd folderName. To go back, you can type cd ... To see the full path of where you currently are, you can type pwd.
2. Now type gcc -Wall -std=c99 -o myprogram filename.c. Here, -Wall tells the compiler to show all warnings, -std=c99 tells the compiler to use the C99 standard, and -o myprogram tells the compiler to output the program as myprogram. You can name the program whatever you want, but it's good to name it something that is descriptive of what it does. On Windows, you will need to name it myprogram.exe instead.
3. On Linux or Mac, you can run the program by typing ./myprogram. On Windows, you can run the program by typing ./myprogram.exe.

Next, how do we use header files? Header files are a way to organize code. We can put all of our function and struct declarations in a header file, and then include it in our main program. This way, we can keep our code organized and we don't have to worry about forgetting to include a function or struct declaration in our main program. To do this, we can create a file called my_struct.h and put all of our declarations in there. Then, we can include it in our main program by typing #include "my_strct.h".

L11+ Onwards

See Part 2.