Reading 08: Pointers, Arrays, Strings

Everyone:

After the break, 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 Monday, March 19 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, 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 -gdwarf-2 -std=gnu99 -o program source.c

Note: The -Wall flags enable most warnings while the -g -gdwarf-2 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 reading08           # Create reading08 branch and check it out

$ cd reading08                        # Go into reading08 folder

# Download Reading 08 Makefile
$ curl -LO https://gitlab.com/nd-cse-20289-sp18/cse-20289-sp18-assignments/raw/master/reading08/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 <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Globals */

char * PROGRAM_NAME = NULL;

/* Functions */

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

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

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

void cat_file(const char *path) {
    FILE *fs = ____(path, "r");                                                   /* 5 */
    if (fs == NULL) {
        fprintf(stderr, "%s: %s: %s\n", PROGRAM_NAME, path, ____(errno));         /* 6 */
        return;
    }
    cat_stream(fs);
    ____(fs);                                                                     /* 7 */
}

/* Main Execution */

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

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

    /* Process each file */
    if (argind == argc) {
        cat_stream(stdin);
    } else {
        while (argind < argc) {
            char *path = argv[argind++];
            if (____(path, "-") == 0) {                                           /* 9 */
                cat_stream(stdin);
            } else {
                cat_file(path);
            }
        }
    }

    return EXIT_SUCCESS;
}

/* 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 08 Quiz questions in your reading08 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 FILE...

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

$ ls | ./grep ep -                            # Search stdin (explicit)
grep
grep.c
test_grep.c

$ ./grep ep grep.c                            # Search file
/* grep.c */
void grep_stream(FILE *stream, const char *pattern) {
void grep_file(const char *path, const char *pattern) {
    grep_stream(fs, pattern);
        grep_stream(stdin, pattern);
                grep_stream(stdin, pattern);
                grep_file(path, pattern);

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 -gdwarf-2 -Wall -std=gnu99 -o sort sort.c
gcc -g -gdwarf-2 -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 /etc/group         ... Success
  grep root FAKEFILE                       ... Success
  grep root /etc/passwd (stdin)            ... Success
  grep root /etc/passwd (-)                ... Success
  grep root /etc/passwd (valgrind)         ... Success
    Score 1.00

Submission

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

$ 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 reading08           # Create reading08 branch and check it out

$ cd reading08                        # Go into reading08 folder

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

$ ../.scripts/submit.py               # Check reading08 quiz
Submitting reading08 assignment ...
Submitting reading08 quiz ...
      Q1 0.25
      Q2 0.25
      Q3 0.25
      Q4 0.25
      Q5 1.00
   Score 2.00

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

$ $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 08: Code"    # Commit work

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

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