This Is Not The Course Website You Are Looking For

This course website is from a previous semester. If you are currently in the class, please make sure you are viewing the latest course website instead of this old one.

Reading 10: Pointers, Arrays, Strings

Everyone:

Next week, we will transition from high-level scripting languages such as Bourne Shell and Python to the ubiquitious C systems programming language. We shall descend down the software stack, away from user applications, and towards the lower level system calls that power our programs.

That is, rather than focusing on how to use or compose tools such as cat, grep, or sort, we will instead learn how to build these basic components, while adhering to the Unix philosophy.

TL;DR

The focus of this reading is to introduce you to programming the C programming language. In particular, you should become familiar with pointers, arrays, and strings.

Readings

The readings for this week are:

  1. Beej's Guide to C Programming

    Most of this should be review from Fundamentals of Computing, so skim through Chapter 1 through Chapter 10. In particular, focus on Chapter 7. Pointers, Chapter 9. Arrays, and Chapter 10. Strings.

  2. Notes for new Make users

    Again, most of this should be review from Fundamentals of Computing and Data Structures, so skim this document and make sure you understand how to write and use a Makefile.

Optional References

Propaganda

C Language

Pointers and Arrays

Makefiles

Compiler Flags

We will be using C99 version of the C programming language. This means that when you compile your programs with gcc, you should include the -std=gnu99 compiler flag:

$ gcc -Wall -g -std=gnu99 -o program source.c

Note: The -Wall flags enable most warnings while the -g flags enable debugging symbols, which will come in handy when we need to use tools such as gdb and valgrind.

Quiz

This week, the reading is split into two sections: the first part is a dredd quiz, while the second part involves two C programs: sort.c and grep.c.

To test the C program, you will need to download the Makefile and test scripts:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading10           # Create reading10 branch and check it out

$ cd reading10                        # Go into reading10 folder

# Download Reading 10 Makefile
$ curl -LO https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/reading10/Makefile

# Download, build, and execute tests
$ make test

Questions

Given the following C program, sum.c, which computes the sum of all the integers read from standard input:

/* sum.c */

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

/* Constants */

#define MAX_NUMBERS (1<<10)

/* Functions */

size_t read_numbers(FILE *stream, int numbers[], size_t n) {
    size_t i = 0;

    while (i < n && scanf("%d", numbers[i]) != EOF) {
        i++;
    }

    return i;
}

int sum_numbers(int numbers[]) {
    int total = 0;
    for (size_t i = 0; i < sizeof(numbers); i++) {
        total += numbers[i];
    }

    return total;
}

/* Main Execution */

int main(int argc, char *argv[]) {
    int numbers[MAX_NUMBERS];
    int total;
    size_t nsize;

    nsize = read_numbers(stdin, numbers, MAX_NUMBERS);
    total = sum_numbers(numbers);
    printf("{}\n", total);

    return EXIT_SUCCESS;
}

And the following C program, cat.c, which implements the cat command:

/* cat.c */

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

/* Globals */

char * PROGRAM_NAME = NULL;

/* Functions */

void usage(int status) {
    ____(stderr, "Usage: %s\n", PROGRAM_NAME);                                    /* 1 */
    ____(status);                                                                 /* 2 */
}

bool cat_stream(FILE *stream) {
    char buffer[BUFSIZ];

    while (____(buffer, BUFSIZ, stream)) {                                        /* 3 */
        ____(buffer, stdout);                                                     /* 4 */
    }

    return true;
}

/* Main Execution */

int main(int argc, char *argv[]) {
    int argind = 1;

    /* Parse command line arguments */
    PROGRAM_NAME = ____;                                                          /* 5 */
    while (argind < argc && ____(argv[argind]) > 1 && argv[argind][0] == '-') {   /* 6 */
        char *arg = argv[argind++];
        switch (arg[1]) {
            case 'h':
                usage(0);
                break;
            default:
                usage(1);
                break;
        }
    }

    /* Process each file */
    return !cat_stream(stdin);
}

/* vim: set sts=4 sw=4 ts=8 expandtab ft=c: */

Code is not Literature

For these types of questions, your first instinct should be to play with the code. As a computer scientist, your approach to any new body of code is to study and investigate it by taking it apart, modifying it, breaking it, and putting it back together.

As Peter Seibel writes, code is not literature:

We don’t read code, we decode it. We examine it. A piece of code is not literature; it is a specimen ... and we are naturalists.

If you truly want to understand something, simply looking up an answer on Google or StackOverflow is insufficient. For true mastery, you need to apply the principle of the Hands-On Imperative:

Hackers believe that essential lessons can be learned about the systems—about the world—from taking things apart, seeing how they work, and using this knowledge to create new and more interesting things.

TL;DR: Download the code. Compile it. Break it. Fix it. Happy Hacking.

Record the answers to the following Reading 10 Quiz questions in your reading10 branch:

Programs

You are to write two simple C programs based on the examples above.

sort.c

Use sum.c as the basis for a C program called sort.c, which uses qsort to implement a basic version of sort:

$ shuf -i 1-10 | ./sort
1
2
3
4
5
6
7
8
9
10

Note: You should use the provided read_numbers function and simply call qsort of numbers and print out each element in the array.

grep.c

Use cat.c as the basis for a C program called grep.c, which uses strstr to implement a basic version of grep:

$ ./grep -h                                   # Display Usage
Usage: ./grep PATTERN

$ ls | ./grep ep                              # Search stdin
grep
grep.c
test_grep.c

$ ls | ./grep NOPE ; echo $?                  # Exit code on failure
1

Note: Use the strstr function to search for strings (you do not need to support regular expressions).

Makefile

To build your programs, you need to update the provided Makefile to include rules or recipes for the sort and grep targets. Be sure to use the CC and CFLAGS variables in your rules.

Once you have a working Makefile, you should be able to use the make command to run your recipes:

$ make clean                                  # Remove targets
rm -f sort grep

$ make                                        # Build targets
gcc -g -Wall -std=gnu99 -o sort sort.c
gcc -g -Wall -std=gnu99 -o grep grep.c

$ make test                                   # Test programs
Testing sort ...
 sort 1                                   ... Success
 sort 1 10                                ... Success
 sort 1 100                               ... Success
 sort 1 1000                              ... Success
 sort 1 1000 (valgrind)                   ... Success
   Score 1.00

Testing grep ...
 grep usage (-h)                          ... Success
 grep usage (no arguments)                ... Success
 grep root /etc/passwd                    ... Success
 grep root /etc/passwd (valgrind)         ... Success
 grep login /etc/passwd                   ... Success
 grep login /etc/passwd (valgrind)        ... Success
 grep asdf /etc/passwd                    ... Success
 grep asdf /etc/passwd (valgrind)         ... Success
   Score 1.00

Submission

To submit you work, follow the same process outlined in Reading 01:

#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS ABOVE
#--------------------------------------------------

$ cd reading10                        # Go into reading10 folder

$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/submit.py               # Check reading10 quiz
Submitting reading10 assignment ...
Submitting reading10 quiz ...
      Q1 0.25
      Q2 0.25
      Q3 0.25
      Q4 0.25
      Q5 0.60
      Q6 0.20
      Q7 0.20
   Score 2.00

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 10: Quiz"    # Commit work

$ $EDITOR Makefile                    # Edit source code
$ $EDITOR sort.c                      # Edit source code
$ $EDITOR grep.c                      # Edit source code

$ make                                # Build programs

$ make test                           # Run tests

$ git add Makefile                    # Add Makefile to staging area
$ git add sort.c grep.c               # Add source code to staging area
$ git commit -m "Reading 10: Code"    # Commit work

$ git push -u origin reading10        # Push branch to GitLab

Merge Request

Remember to create a merge request and assign the appropriate TA from the Reading 10 TA List.

DO NOT MERGE your own merge request. The TAs use open merge requests to keep track of which assignments to grade. Closing them yourself will cause a delay in grading and confuse the TAs.