{%hackmd @themes/orangeheart %}

# More Control Flow, Pointers, Memory Addressing, Arrays, Pointer Arithmetic, Strings and Sorting Algorithms

## `goto` - Unconditional Code Jumping (Redundant)

`goto` enables the ability to jump to an arbitary part of ur code unconditionally within the same function.

- location is identified using a label
- label is the named location in the code
- same form as a variable followed by `:`

start:
{
    if (cond)
        goto outside;
    goto start
}
outside:
<expression>

## Spaghetti Code

Spaghetti code refers to phrases of code that are harder to maintain and debug. This type of code is extremely unstable in terms of performance and lacks essential programming rules.

**Note that excess use of** `goto` **creates spaghetti code, it also makes code harder to debug and read. Any code that can be written with** `goto` **can be written without one.**

### Error Handling

However, despite it's drastic consequences when used excessively, `goto` provides a convenient way to exit from heavily nested blocks:

for (...){
    for (...){
        if (error_cond)
            goto error;
    }
}
error:

## Input and Output (I/O)

### Preliminaries

`<stdio.h>` provides basic input and output libraries, not the language itself.

- text stream consists of a series of lines ending with `\n`, `<stdlib.h>` takes care of conversion from `'\r\n'−'\n'`
- binary stream consists of a series of raw bytes
- streams provided by standard library are buffered

### `int putchar()`

- puts the character `c` on the standard output
- automatically `\n` or line breaks to the next line
- returns character printed or EOF on error

### `int getchar()`

- returns the next character from standard input or returns EOF on error

## Arrays

### *Integer Arrays*

### Initialization and Declaration

**Assign Value to Each Element**

int mark[6];
mark[0] = 12;
mark[1] = 15;
mark[2] = 25;
mark[3] = 30;
mark[4] = 20;
mark[5] = 50;

**Assign Values During Declaration**

int mark[6] = {12,15,25,30,20,50};

Note that the number of values in `{}` **cannot be larger than the values in** `[]`. An alternative way to initialize an array without knowing how many values are there beforehand:

**Size of declaration is not necessary**

int mark[] = {12,15,25,30,20,50};
double prices[] = {100.0, 2.5, 5.5, 6.0, 50.5};

**Initialize all elements to 0**

int mark[6] = 0;

Primitive arrays implemented in C use **pointers to block of contiguous memory. They are immutable.**

Initializing the array can be done with this example:

double prices[5] = {100.0, 2.5, 5.5, 6.0, 50.5};

Accessing arrays have the same syntax as python:

prices[2]; //5.5
printf("%lf",prices[2]);

Assigning array indexes to a variable:

double shirt_price = prices[2];

### Example of Declaration, Assignment and Array Access

[Visualization](https://pythontutor.com/render.html#code=%23include%20%3Cstdio.h%3E%0A%20%0Aint%20main%20%28%29%20%7B%0A%0A%20%20%20int%20n%5B10%5D%3B%20/*%20n%20is%20an%20array%20of%2010%20integers%20*/%0A%20%20%20int%20i,j%3B%0A%20%0A%20%20%20/*%20initialize%20elements%20of%20array%20n%20to%200%20*/%20%20%20%20%20%20%20%20%20%0A%20%20%20for%20%28%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B%20%29%20%7B%0A%20%20%20%20%20%20n%5B%20i%20%5D%20%3D%20i%20%2B%20100%3B%20/*%20set%20element%20at%20location%20i%20to%20i%20%2B%20100%20*/%0A%20%20%20%7D%0A%20%20%20%0A%20%20%20/*%20output%20each%20array%20element's%20value%20*/%0A%20%20%20for%20%28j%20%3D%200%3B%20j%20%3C%2010%3B%20j%2B%2B%20%29%20%7B%0A%20%20%20%20%20%20printf%28%22Element%5B%25d%5D%20%3D%20%25d%5Cn%22,%20j,%20n%5Bj%5D%20%29%3B%0A%20%20%20%7D%0A%20%0A%20%20%20return%200%3B%0A%7D&cumulative=false&curInstr=44&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=c_gcc9.3.0&rawInputLstJSON=%5B%5D&textReferences=false)

#include <stdio.h>
 
int main () {

   int n[10]; /* n is an array of 10 integers */
   int i,j;
 
   /* initialize elements of array n to 0 */         
   for ( i = 0; i < 10; i++ ) {
      n[ i ] = i + 100; /* set element at location i to i + 100 */
   }
   
   /* output each array element's value */
   for (j = 0; j < 10; j++ ) {
      printf("Element[%d] = %d\n", j, n[j] );
   }
 
   return 0;
}

### *Digression: Character Arrays*

> **C doesn't have data type string, strings are represented as character arrays. C doesn't restrict the length of the string, end of the string is specified using `\0`.**

### Example

`'Hello'` can be represented using an array: `{'h','e','l','l','o','\0'}`

Hence, there are several declarations to declare a string:

char str[] = "hello";
char str[10] = "hello"; /* 10 is the size of the array, when using this make sure the array size is enough for the input */
char str[] = {'h','e','l','l','o',0};

### `size_t` or Any Unsigned Type

- might be seen as loop variables
- typically $>=0$
- only non-negative values
- 32 bit: `typedef` - `unsigned int`
- 64 bit: `typedef` - `unsigned long long`
- used for array indexing and looping

### Comparing Strings

`<string.h>` provides function `int strcmp(char s[], char t[])` to compare two strings in dictionary order:

- **lower cases come after capitals**
- returns `<0` if s comes before t
- returns 0 is same
- returns `>0` if s comes after t
- **case sensitive**

strcmp("a", "A"); /* returns <0 */
strcmp("SUPERMAN", "BATMAN"); /* returns >0 */
strcmp("a", "a"); /* returns ==0 */

### Formatted Input

- `scanf()`: formatted input function to take analog inputs of `printf`
- takes variable number of inputs
- separated by white space when multiple items are to be read
- returns number of items read or EOF

**Note that** `scanf` **ignores white spaces. Arguments have to be pointers (address of variables).**

- `int sprintf(char str[], char format[], arg1, arg2);`
- format specification same as `printf`
- output is written to string (doesn't check size)
- returns number of character written or negative value on error

- `int sscanf(char str[], char format[], arg1, arg2)`
- format specification is the same as `scanf`
- input is read from `str` variable
- returns the number of items read or negative value on error

## Pointers and Addresses

Pointers are a memory address of a variable, address can be used to access or modify a variable from anywhere. This is extremely useful for data structures and [obfuscating](https://en.wikipedia.org/wiki/Obfuscation_(software)) code.

### Physical and Virtual Memory

- **Physical Memory: physical resources to store data**
- cache
- RAM
- hard disk
- removable storage

- **Virtual Memory: abstraction by OS, addressable space accessible by code**

### Physical Memory Considerations

Since programs have different sizes and access speeds, memory management is a major function of the OS:

- optimization: ensure code makes best use of physical memory available
- OS moves around data in physical memory during execution
- Embedded processors: may be very limited

### Virtual Memory

Virtual memory maps to different parts of physical memory. Usable parts of virtual memory are called **stack and heap:**

- stack: where declared variables go
- heap: where dynamic memory goes

## Addressing Variables/Pointers

### Basic Syntax

We know that every variable in memory has an address/pointer, **only register variables, constants/literals/preprocessor definitions and expressions don't have an address.** Finding the address of a variable (accessing address) uses `&`, type of address can be declared using `*`:

int n = 4;
double pi = 3.14159;
int *pn = &n; //declaring a pointer integer variable pn using *, while & is the pointer of n
double *ppi = π //declaration a pointer double variable ppi

### Using Pointers

Here is an example of declaring, initializing and using pointers:

#include <stdio.h>

int main () {

   int  var = 20;   /* actual variable declaration */
   int  *ip;        /* pointer variable declaration */

   ip = &var;  /* store address of var in pointer variable*/

   printf("Address of var variable: %x\n", &var);

   /* address stored in pointer variable */
   printf("Address stored in ip variable: %x\n", ip);

   /* access the value using the pointer */
   printf("Value of *ip variable: %d\n", *ip);

   return 0;
}

Output:

Address of var variable: bffd8b3c
Address stored in ip variable: bffd8b3c
Value of *ip variable: 20

Format specifiers are extremely useful to call pointers or values associated with their variables. That being said, be careful when using formatted strings.

### Changing Values

Changing values from either the variable that the pointer is pointing to or changing directly from the variable will be the same:

int main(){
    int c = 8;
    int *cptr = &c;
    printf("c: %d cptr = %d\n", c, *cptr);
    c = 9;
    printf("c: %d cptr = %d\n", c, *cptr);
    *cptr = 10;
    printf("c: %d cptr = %d\n", c, *cptr);
    return 0;
}

Output:

c: 8 cptr = 8
c: 9 cptr = 9
c: 10 cptr = 10

### Pointers - Function Arguments

**Pass by Reference and Call by Reference**

Pass by Reference refers to passing the **address of an argument to a function (not the value)** as the parameter. **This allows value modification outside the function:**

#include <stdio.h>

void swapnum(int *i, int *j) { //pointers as parameters
  int temp = *i;
  *i = *j;
  *j = temp;
}

int main(void) {
  int a = 10;
  int b = 20;

  swapnum(&a, &b); //address of the variable, not the value
  printf("A is %d and B is %d\n", a, b);
  return 0;
}

- `swapnum` call uses `&` to pass address of the value
- parameters `*i` and `*j` are pointers

### Dereferencing Pointers

Accessing/modifying values stored at the address held by a pointer can be seen as dereferencing pointers:

printf("pi = %g\n", ∗ppi); // prints 3.14159\n
*ppi = *ppi + *pn; //pi now equals to 7.14159

Note that null pointer `NULL` doesn't reference anything.

### Casting Pointers

Let's look at an example of casting **basic variables:**

int n = 10, m = 21;
double mean;

mean = (double) n/m;
printf("Value of mean: %f\n", mean);

Based on the example given, casting of datatypes is also known as **conversion of datatypes.** Converting variables to a specific datatypes uses the cast operator:

(typename) variable

Casting pointers uses a similar approach:

ppi = (double *)pn;

### Function with Multiple Outputs

Consider the previous `ext_euclid(a, b)` function returns $gcd(a, b)$ for $ax+by=gcd(a,b)$

Since global variables `a` and `b` are used, we can create their associated pointers.

int ext_euclid(int a, int b, int *x, int *y);

When the function is called, it passes pointers to variables to receive `x` and `y`:

g = ext_euclid(a,b,&x,&y); //assume a and b are declared previously

### Accessing Caller's Variables

Here we will be writing a function to swap two integers, we need to modify variables from the caller to swap them, **pointers to variables** are used as arguments:

void swap(int *x, int){
    int temp = *x;
    *y = *x;
    *x = temp;
}

Calling to `swap` function:

int a = 5, b = 7;
printf("a is %d while b is %d\n", a, b);
swap(&a,&b); //calling of function swap() with two arguments a and b
printf("a is now %d while b is %d\n", a, b);

### Variables Passing Out of Scope

Note that pointers are invalid after variable passes out of scope:

#include <stdio.h>

char *get_message(){
    char msg[] = "Aren't pointers fun?";
    return msg;
}

int main(void){
    char *string = get_message();
    puts(string);
    return 0;
}

## Pointer Arithmetic

Pointers have valid operands in:

- arithmetic
- assignment
- comparison

Usually we use pointer arithmetic on arrays.

### Addition / Subtraction

Remember that accessing arrays using pointers the `&` operator is not needed unless it's pointing to an individual element of the array:

int v[5] = {1,2,3,4,5};
int *vptr = v;

Note that `*vptr = v` points to the first element of array `v`, knowing so allows us to access different elements by using pointer arithmetics:

printf("%d\n", *vptr+2);
printf("%d\n", *vptr+3);
printf("%d\n", *vptr+4);

Output:

3
4
5

### Assignment - Decrement / Increment

Assigning elements to a specific pointer address is similar:

for (int i = 0; i < 5; i++){
        printf("%d\n", *vptr++);
    }

Output:

1
2
3
4
5

In this case, `vptr` **points to the last element of the array which is** `5`, if u don't want to directly assign but instead just accessing the element, `*(vptr + i)` can be used instead:

for (int i = 0; i < 5; i++){
        printf("%d\n", *(vptr + i));
    }

Accessing using `*(v + i)` is the same:

for (int i = 0; i < 5; i++){
        printf("%d\n", *(v + i));
    }

Regular indexes with pointers also work (which is why C is so versatile in this case):

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

**Another Example:**

double *pr = prices; //assignment of the entire array to a pointer
double *pr = &prices[0] //assignment of an element in array to a pointer

## Arrays and Pointers

### Arrays of Pointers

Here we begin to discuss the access of pointers in arrays with **string arrays.**

Each entry in an array is a string, but in C a string is essentially a pointer to **its first character:**

const char *v[3] = {"Hi", "Hello", "How are you"};
for (int i = 0; i < 3; i++){
    printf("%s", v[i]);
    }

Output:

Hi
Hello
How are you

- `char *v[3]`: array of 3 pointers with each pointer pointing to the **1st character of each string inside**
- `const`: pointer cannot be modified in the program

Accessing individual characters in the desired string uses similar syntax as explained above:

for (int i = 0; i < 3; i++){
    printf("first character of the string %s is %c\n", v[i], *(v[i]));
}

Output:

first character of the string Hi is H
first character of the string Hello is H
first character of the string How are you is H

### Pointers to Functions

We can use pointers to access certain functions by declaring an explicit function pointer and initialize it to access different functions:

void func1(int a){
    printf("func1 is called\n");
}

void func2(int b){
    printf("func2 is called\n");
}

void func3(int c){
    printf("func3 is called\n");
}

int main(){
    void (*v[3])(int) = {func1, func2, func3};
    for (int i = 0; i < 3; i++){
        (*(v+i))(1);
    }
    return 0;
}

- `void (*v[3])(int) = {func1, func2, func3}` creates a function pointer of arrays of pointers pointing to 3 functions `func1`, `func2` and `func3`:
- `void`: return value of function `*v[3]`
- `(int)`: each function takes an int argument
- `(*(v+i))(1)` calls and passes `1` to each function

Output:

func1 is called
func2 is called
func3 is called

## Complicated Declarations

*a[] //array of pointer
(*a)[] //pointer to an array
*f() //function returning pointer
(*f)() //pointer to a function

## File I/O

All input and output are performed with streams:
- sequences of bytes
- input: bytes flow device --> memory
- output: bytes flow memory --> device

### File Open / Close

C allows us to read data from text/binary files using `fopen()`:

FILE pointer_name = fopen(char name[], char mode[])

- mode can be:
- `"r"`: read only
- `"w"`: write only
- `"a"`: append
- `"b"`: appended for binary files
- `fopen` returns a pointer to file stream if it exists or `null` otherwise
- `<stdin.h>` and `<stdout.h>` are also **FILE** datatypes
- `stderr` corresponds to standard error output (different from `stdout`)

- `int fclose(FILE*fp)`
- closes stream
- flushes any data still pending in the file
- releases any memory used for file
- `fclose()` is automatically called on all open files when program terminates

- `feof`
- End-of-File Indicator
- no more data to be processed

### File Input

- `fgetc(FILE*fp)`
- reads a single character from stream
- returns character read or EOF

- `char[] fgets(char line[], int maxlen, FILE*fp)`
- reads a single line up to maxlen characters from input stream
- returns a pointer in character array that stores the line
- return `null` if end of stream

### File Output

- `fputc(int c, FILE*fp)`
- writes a single character c to output
- returns character returned or EOF

- `int fputs(char line[], FILE*fp)`
- writes single line to output
- returns 0 on success, otherwise EOF

- `int fscanf(FILE*fp, char format[], arg1, arg2)`
- similar to `scanf`, `sscanf`
- reads items from input