<!--
Abstract:

CS 211
Computer Architecture
Lecture 06: File I/O and Structs
-->

# CS 211 - Lecture 07 - Structs for Queues and Stacks

Bernhard Firner

2025-09-23

---

## Review!

* File I/O
* Structs

---

## Structs

* Allow us to group related data under a new name
* A lightweight precursor to classes you've seen in other languages
* Typical of C, `struct`s also support some low level optimizations

---

## Better names with typedef

* The names of structs are awkward
  * `struct name`
* C has a way to make new names, so we can simplify things
  * `typedef <existing name> <new name>`
  * You can do this before making the struct, which is a `forward declaration`

```C
typedef struct nicePtr nicePtr;
struct nicePtr {
    unsigned long* memory;
    size_t elements;
};
```

---

## Pointer Passing

* Arguments are passed by their values
* The contents of a struct are copied
* Since pointers are just numbers, we can safely pass structs with pointers
  * Makes it simple to return something like nicePtr
* Passing as an argument is also okay 
  * Just avoid free-ing them inside of the function
    * You can use the `const` keyword to prevent this

---

## Const example

```C
/*
 * Demonstrate const with struct pointers
 */

#include <stdio.h>

typedef struct bigData bigData;
struct bigData {
    long long numbers[1000];
};

// This function modifies data's members, so it cannot be const.
void modifyData(bigData* data) {
    for (int i = 0; i < sizeof(data->numbers)/sizeof(long long); ++i) {
        data->numbers[i] = i;
    }
}

// This function does not modify data's members, so it can be const.
long long sumData(const bigData* data) {
    long long sum = 0;
    for (int i = 0; i < sizeof(data->numbers)/sizeof(long long); ++i) {
        sum += data->numbers[i];
    }
    return sum;
}

int main(void) {
    bigData data = {.numbers = {}};

// Modify the data
    modifyData(&data);

// Sum the data
    printf("Sum is %lli\n", sumData(&data));

return 0;
}
```

---

## File I/O

* New functions to work with files:
  * `FILE *fopen(const char *restrict pathname, const char *restrict mode);`
    * Open a file. Mode is 'r' for read, 'w' for write.
  * `int fclose(FILE *stream);`
    * Close the file.
  * `ssize_t getline(char **restrict lineptr, size_t *restrict n, FILE *restrict stream);`
    * Read a line from the file
    * Put the line into the string pointed to by *lineptr*.

---

## Line Parsing

* The `scanf` functions are the opposite of `printf`
* `sscanf` works on a string.
* `int sscanf(const char *restrict str, const char *restrict format, ...);`
  * Give it a string to parse, and a format string.
  * Other arguments are where the results go
    * So they are pointers, unlike with `printf`

---

## Matrix Example, Struct

```C
/*
 * Implementation of the matrix operations.
 */

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

// We include the header file for the definition of the Matrix struct.
#include "matrix_lib.h"

// Create a new matrix.
Matrix newMatrix(size_t height, size_t width) {
    Matrix nm;
    // First we allocate pointers to each row.
    nm.values = calloc(height, sizeof(float*));
    for (size_t i = 0; i < height; ++i) {
        nm.values[i] = calloc(width, sizeof(float));
    }
    nm.height = height;
    nm.width = width;
    return nm;
}

// Free the memory of a matrix.
void freeMatrix(Matrix m) {
    // Free each row, then free the pointer to the rows.
    for (size_t i = 0; i < m.height; ++i) {
        free(m.values[i]);
    }

free(m.values);
}

// Print a matrix
void printMatrix(Matrix m) {
    for (size_t row = 0; row < m.height; ++row) {
        for (size_t column = 0; column < m.width; ++column) {
            printf("%.3f", m.values[row][column]);
            // Print a comma, except print a new line on the last value.
            if (column < m.width-1) {
                printf(", ");
            }
            else {
                printf("\n");
            }
        }
    }
}

// Add two matrices.
Matrix addMatrix(Matrix left, Matrix right) {
    // If the sizes don't match, return a matrix with NULL data and 0 size.
    Matrix sum = {.values = NULL, .width = 0, .height = 0};
    if (left.height != right.height || left.width != right.width) {
        return sum;
    }
    sum = newMatrix(left.height, left.width);
    for (size_t row = 0; row < sum.height; ++row) {
        for (size_t column = 0; column < sum.width; ++column) {
            sum.values[row][column] = left.values[row][column] + right.values[row][column];
        }
    }
    return sum;
}
```

---

## Matrix Example, I/O

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

#include "matrix_lib.h"

//Read a three by three matrix from the FILE*
Matrix readMatrix(FILE* datafile) {
    Matrix m = newMatrix(3, 3);
    // Now read values from a file
    // A buffer to store lines as we read them.
    size_t buf_size = 1000;
    char* char_buffer = calloc(buf_size, sizeof(char));

// Read values into matrix a
    for (size_t row = 0; row < 3; ++row) {
        // Read a line from the file.
        getline(&char_buffer, &buf_size, datafile);
        // Now read three comma separated values from that line
        float row_data[3];
        sscanf(char_buffer, "%f, %f, %f", row_data, row_data+1, row_data+2);
        for (size_t column = 0; column < 3; ++column) {
            m.values[row][column] = row_data[column];
        }
    }
    // Finished with the buffer
    free(char_buffer);
    return m;
}

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

// Make our two new matrices
    Matrix a = readMatrix(datafile);
    Matrix b = readMatrix(datafile);

fclose(datafile);

Matrix sum = addMatrix(a, b);

printf("Sum of matrix\n");
    printMatrix(a);
    printf("And matrix\n");
    printMatrix(b);
    printf("Is matrix\n");
    printMatrix(sum);

freeMatrix(a);
    freeMatrix(b);
    freeMatrix(sum);

return 0;

}
```

---

## Matrix Comments

* Matrix math has grown in importance
* Making their matrix math faster has been a huge effort for some leading silicon valley companies
* Optimzation
  * Should matrices be stored row first, or column first?
  * Can we store them as flat, contiguous memory rather than separate chunks?
  * If we can make a matrix sparse, could we store fewer numbers?
  * What is the most memory-efficient way to handle large matrix math?
* As we get to more advanced topics, we'll revisit these questions

---

## New Example

* Let's simplify a bit, then mix in what we've learned
* Let's read in the contents of a file
  * Make everything upper case
  * Reprint
* We can go one character at a time with `fgetc` and `putchar`

---

## Example file

<pre>
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."
</pre>

---

## Making something uppercase

* We could use the `toupper` function from `ctype.h`
* I want us to do a little math, though

---

## man ascii

```
       For convenience, below are more compact tables in hex and decimal.

2 3 4 5 6 7       30 40 50 60 70 80 90 100 110 120
        -------------      ---------------------------------
       0:   0 @ P ` p     0:    (  2  <  F  P  Z  d   n   x
       1: ! 1 A Q a q     1:    )  3  =  G  Q  [  e   o   y
       2: " 2 B R b r     2:    *  4  >  H  R  \  f   p   z
       3: # 3 C S c s     3: !  +  5  ?  I  S  ]  g   q   {
       4: $ 4 D T d t     4: "  ,  6  @  J  T  ^  h   r   |
       5: % 5 E U e u     5: #  -  7  A  K  U  _  i   s   }
       6: & 6 F V f v     6: $  .  8  B  L  V  `  j   t   ~
       7: ' 7 G W g w     7: %  /  9  C  M  W  a  k   u  DEL
       8: ( 8 H X h x     8: &  0  :  D  N  X  b  l   v
       9: ) 9 I Y i y     9: '  1  ;  E  O  Y  c  m   w
       A: * : J Z j z
       B: + ; K [ k {
       C: , < L \ l |
       D: - = M ] m }
       E: . > N ^ n ~
       F: / ? O _ o DEL
```

---

## Ascii Math

* The lowercase and uppercase letters are all in a row
* The distance from 'a' to 'A' is the same as from 'z' to 'Z'
  * 'a' - 'A' = 97 - 65 = 32
* So we can just subtract that distance from a lowercase letter to get an uppercase letter

---

## Upper Case Code

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

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

// We don't need to get complicated with sscanf
    // Just read in one character at a time
    // fgetc returns some special numbers, so we read into an int rather than a char
    int input = fgetc(datafile);
    // EOF is defined in stdio.h, means "End Of File"
    while (input != EOF) {
        // Print a single char
        // Ascii characters appear in numerical order, so we can do math to capitalize
        if (input >= 'a' && input <= 'z') {
            // Increase by the distance from the lower case letters to the upper case
            input += 'A' - 'a';
        }
        putchar(input);
        // For the next loop iteration
        input = fgetc(datafile);
    }

// Finished with the file
    fclose(datafile);

return 0;
}
```

---

## Reversing

* What if we wanted to reverse the words?
  * We could make a giant array, shove the characters into it, and then loop backwards over it.
  * Not very elegant
* Instead we'll use a data structure

---

## Stack (data structure)

* We push onto the top to add
* Pop to retrieve and remove from the top
* Last in, first out
* This shows up in our architecture, so let's get experience working with one

---

## Stack Definitions

* stack.h

```C
// For the size_t type definition
#include <stddef.h>

typedef struct Stack Stack;
struct Stack {
    char *memory;
    size_t memsize;
    size_t index;
};

Stack newStack(size_t size);

void freeStack(Stack s);

void push(Stack* s, char element);

char pop(Stack* s);

size_t len(Stack s);
```

---

## Push and dynamic memory

* What if we push and there isn't enough memory?
* We are going to allocate more memory
  * Double whatever we have currently
* Then copy over the existing memory values before free-ing it

---

## Stack Functions

```C
#include <stdlib.h>
#include <string.h>

#include "stack.h"

Stack newStack(size_t size) {
    Stack s = { .memory = NULL, .memsize = 0, .index = 0 };
    s.memory = calloc(size, sizeof(char));
    s.memsize = size;
    return s;
}

void freeStack(Stack s) {
    free(s.memory);
}

void push(Stack* s, char element) {
    // Double the memory whenever it is filled
    if (s->index + 1 >= s->memsize) {
        char* new_memory = calloc(s->memsize * 2, sizeof(char));
        // Copy from the old memory into the new memory and then free the old memory
        memcpy(new_memory, s->memory, s->memsize);
        free(s->memory);
        s->memory = new_memory;
        s->memsize = s->memsize * 2;
    }
    s->memory[s->index] = element;
    s->index += 1;
}

char pop(Stack* s) {
    if (0 == s->index) {
        return '\0';
    }
    // Index is at the first empty position
    s->index -= 1;
    char output = s->memory[s->index];
    return output;
}

size_t len(Stack s) {
    return s.index;
}

```

---

## Using the stack

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

#include "stack.h"

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

Stack s = newStack(10);

// We don't need to get complicated with sscanf
    // Just read in one character at a time
    int input = fgetc(datafile);
    // EOF is defined in stdio.h, means "End Of File"
    while (input != EOF) {
        push(&s, input);
        // For the next loop iteration
        input = fgetc(datafile);
    }

// Finished with the file
    fclose(datafile);

// Reverse
    while (0 < len(s)) {
        putchar(pop(&s));
    }
    putchar('\n');

freeStack(s);

return 0;
}
```

---

## Makefile

```Makefile
example23: stack.h stack.c example23.c
	gcc $^ -o $@
```

* (The indentation should be a tab)

---

## More Fun

* Let's just print the words in their opposite order
* Switch from `fgetc` to `sscanf`

---

## Strings with sscanf

* Working with strings means working with memory
* We *could* let `sscanf` manage string memory for us, but this feels sloppy
* Instead, we will pre-allocate memory and use a sized string

---

## Sized strings in sscanf

```C
char word_buffer[101];
int success = sscanf(line, "%100s", word_buffer);
// success is the number of things read. In this case, just the string.
// word_buffer has a null terminated string inside of it
```

---

## Querying sscanf results

* Beyond success or failure, sscanf can also indicate how many characters it has read
  * Use the `%n` specifier and provide a pointer to an int
* This is weird, by the way
  * Like a back channel to pass this information

```C
char word_buffer[101];
int consumed = 0;
int success = sscanf(line, "%100s%n", word_buffer, &consumed);
// success is the number of things read. In this case, just the string.
// %n doesn't count for the returned value.
// word_buffer has a null terminated string inside of it
// Consumed has the number of characters consumed (from %n)
```

---

## Changes to stack.h

```C[|6|15|17]
// For the size_t type definition
#include <stddef.h>

typedef struct Stack Stack;
struct Stack {
    char **memory;
    size_t memsize;
    size_t index;
};

Stack newStack(size_t size);

void freeStack(Stack s);

void push(Stack* s, char *element);

char* pop(Stack* s);

size_t len(Stack s);
```

---

## Changes to stack.c

```C[|8|14-17|24-26,31-35|42,46-49]
#include <stdlib.h>
#include <string.h>

#include "strstack.h"

Stack newStack(size_t size) {
    Stack s = { .memory = NULL, .memsize = 0, .index = 0 };
    s.memory = calloc(size, sizeof(char*));
    s.memsize = size;
    return s;
}

void freeStack(Stack s) {
    // Need to verify that all held strings are freed
    for (size_t i = 0; i < s.index; ++i) {
        free(s.memory[i]);
    }
    free(s.memory);
}

void push(Stack* s, const char *element) {
    // Double the memory whenever it is filled
    if (s->index + 1 >= s->memsize) {
        char** new_memory = calloc(s->memsize * 2, sizeof(char*));
        // Copy from the old memory into the new memory and then free the old memory
        memcpy(new_memory, s->memory, s->memsize * sizeof(char*));
        free(s->memory);
        s->memory = new_memory;
        s->memsize = s->memsize * 2;
    }
    // The stack copies the string memory
    // Allocate one extra byte for '\0'
    size_t str_size = strlen(element);
    char* new_str = calloc(str_size+1, sizeof(char));
    memcpy(new_str, element, str_size);
    s->memory[s->index] = new_str;
    s->index += 1;
}

char* pop(Stack* s) {
    if (0 == s->index) {
        return NULL;
    }
    // Index is at the first empty position
    s->index -= 1;
    char* output = s->memory[s->index];
    s->memory[s->index] = NULL;
    // Transfers ownership of the string to the caller
    return output;
}

size_t len(Stack s) {
    return s.index;
}

```

---

## Word Reversing Example

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

#include "strstack.h"

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

Stack s = newStack(10);

// A buffer to store lines as we read them.
    size_t buf_size = 1000;
    char* line_buffer = calloc(buf_size, sizeof(char));
    ssize_t line_length = getline(&line_buffer, &buf_size, datafile);
    while (-1 < line_length) {
        // A buffer with space for 100 characters (plus '\0')
        char word_buffer[101];
        size_t line_offset = 0;
        int consumed = 0;
        int success = sscanf(line_buffer+line_offset, "%100s%n", word_buffer, &consumed);
        while (success == 1 && line_offset < line_length) {
            line_offset += consumed;
            // Push the word onto the stack.
            // sscanf put a '\0' at the end of the word, so the stack won't
            // see the rest of the word_buffer.
            push(&s, word_buffer);
            success = sscanf(line_buffer+line_offset, "%100s%n", word_buffer, &consumed);
        }
        // Get the next line
        line_length = getline(&line_buffer, &buf_size, datafile);
    }

// Finished with the file
    fclose(datafile);

// Reverse. Print out every word but the last with a trailing space.
    while (1 < len(s)) {
        char* word = pop(&s);
        printf("%s ", word);
        free(word);
    }
    if (1 == len(s)) {
        char* word = pop(&s);
        printf("%s\n", word);
        free(word);
    }

freeStack(s);

return 0;
}
```

---

## Debugging

* Debugging code like this quickly becomes a nightmare
  * The crashes aren't co-located with the errors
* Let's delete a single character from a file and see what happens

---

## Debugging strstack.h

```C
// For the size_t type definition
#include <stddef.h>

typedef struct Stack Stack;
struct Stack {
    char **memory;
    size_t memsize;
    size_t index;
};

Stack newStack(size_t size);

void freeStack(Stack s);

void push(Stack* s, const char *element);

char* pop(Stack* s);

size_t len(Stack s);
```

---

## Debugging strstack.c

```C
#include <stdlib.h>
#include <string.h>

#include "strstack.h"

Stack newStack(size_t size) {
    Stack s = { .memory = NULL, .memsize = 0, .index = 0 };
    s.memory = calloc(size, sizeof(char*));
    s.memsize = size;
    return s;
}

void freeStack(Stack s) {
    // Need to verify that all held strings are freed
    for (size_t i = 0; i < s.index; ++i) {
        free(s.memory[i]);
    }
    free(s.memory);
}

void push(Stack* s, const char *element) {
    // Double the memory whenever it is filled
    if (s->index + 1 >= s->memsize) {
        char** new_memory = calloc(s->memsize * 2, sizeof(char*));
        // Copy from the old memory into the new memory and then free the old memory
        memcpy(new_memory, s->memory, s->memsize * sizeof(char));
        free(s->memory);
        s->memory = new_memory;
        s->memsize = s->memsize * 2;
    }
    // The stack copies the string memory
    // Allocate one extra byte for '\0'
    size_t str_size = strlen(element);
    char* new_str = calloc(str_size+1, sizeof(char));
    memcpy(new_str, element, str_size);
    s->memory[s->index] = new_str;
    s->index += 1;
}

size_t len(Stack s) {
    return s.index;
}
```

---

## Debugging main.c

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

#include "strstack.h"

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

Stack s = newStack(10);

// Finished with the file
    fclose(datafile);

freeStack(s);

return 0;
}
```

---

## Next Topics

* A bit more about common data types
* Shifting to more architecture topics and some assembly before the midterm