Readings

The readings for Monday, March 20 are:

  1. Essential C

    Note: This is from the Stanford CS Education Library.

  2. GCC and Make - Compiling, Linking and Building C/C++ Applications

    Note: Just skim what you need; we will explore this more deeply in class.

TL;DR

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

Optional Resources

  1. Propaganda

  2. C Language:

  3. Pointers and Arrays:

  4. 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 flags:

$ 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.

Activities

  1. Given the following C program, sum.c:

    /* 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[], size_t n) {
        int total = 0;
        for (size_t i = 0; i < n; 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, nsize);
        printf("%d\n", total);
    
        return EXIT_SUCCESS;
    }
    

    Questions

    In your reading07/README.md file, answer the following questions:

    1. Describe what the read_numbers function does by explaining what is happening on the following line:

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

      Be sure to explain the purpose of the & in front of numbers[i] and what the constant EOF is.

      Hint: You should refer to the scanf manpage.

    2. Insteading of passing size_t n into the sum_numbers function, could we have used sizeof to get the size of the array as shown below?

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

      Explain whether or not this works and why.

    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 says, 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.

    Programming

    Use the sum.c as the basis for a C program called sort.c, which uses insertion sort to sort a sequence of numbers from standard input:

    # Sort 5 4 7 0 1
    $ echo 5 4 7 0 1 | ./sort
    0 1 4 5 7
    
    # Sort 10 random numbers
    $ shuf -n 10 -i1-10 | ./sort
    1 2 3 4 5 6 7 8 9 10
    

    Recall that insertion sort is stable sorting algorithm based on a sorted array implementation of a priority queue that is O(1) in the best case, but O(n^2) in the worst case:

    Note: You should use the provided read_numbers function and simply create and utilize your own sort_numbers function to perform the insertion sort.

    To test your sort.c program, you can use the provided test_sort.sh script:

    # Download script
    $ curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_sort.sh
    
    # # Make script executable
    $ chmod +x test_sort.sh
    
    # Run test script
    $ ./test_sort.sh
    sort test successful!
    
  2. Given the following C program, cat.c:

    /* cat.c */
    
    #include <errno.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    /* Globals */
    
    char * PROGRAM_NAME = NULL;
    
    /* Functions */
    
    void usage(int status) {
        fprintf(stderr, "Usage: %s FILES...\n", PROGRAM_NAME);
        exit(status);
    }
    
    void cat_stream(FILE *stream) {
        char buffer[BUFSIZ];
    
        while (fgets(buffer, BUFSIZ, stream)) {
            fputs(buffer, stdout);
        }
    }
    
    void cat_file(const char *path) {
        FILE *fs = fopen(path, "r");
        if (fs == NULL) {
            fprintf(stderr, "%s: %s: %s\n", PROGRAM_NAME, path, strerror(errno));
            return;
        }
        cat_stream(fs);
        fclose(fs);
    }
    
    /* Main Execution */
    
    int main(int argc, char *argv[]) {
        int argind = 1;
    
        /* Parse command line arguments */
        PROGRAM_NAME = argv[0];
        while (argind < argc && strlen(argv[argind]) > 1 && argv[argind][0] == '-') {
            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 (strcmp(path, "-") == 0) {
                    cat_stream(stdin);
                } else {
                    cat_file(path);
                }
            }
        }
    
        return EXIT_SUCCESS;
    }
    

    Questions

    In your reading07/README.md file, answer the following questions:

    1. Compare how this version of cat parses command line arguments versus the approach used in cat.py from Reading 05. Beyond the obvious differences in syntax, how is the code similar and how is it different?

      Be sure to explain the role of argc and argv.

    2. Describe how each file is processed by explaining the following code:

      while (argind < argc) {
          char *path = argv[argind++];
          if (strcmp(path, "-") == 0) {
              cat_stream(stdin);
          } else {
              cat_file(path);
          }
      }
      

      Be sure to explain what the char *path = argv[argind++] statement accomplishes and what the strcmp comparison checks for.

    3. Explain how the cat_stream function works. What are the purposes of fgets and fputs?

    4. Explain how the cat_file function works. What is the purpose of the following if statement:

      if (fs == NULL) {
          fprintf(stderr, "%s: %s: %s\n", PROGRAM_NAME, path, strerror(errno));
          return;
      }
      

      Be sure to explain what strerror and errno are.

    Programming

    Use the cat.c as the basis for a C program called grep.c, which is a simple implementation of the grep command:

    # Display usage
    $ ./grep -h
    Usage: ./grep PATTERN FILE...
    
    # Search implicit stdin
    $ ls | ./grep ep
    grep
    grep.c
    
    # Search explicit stdin
    $ ls | ./grep ep -
    grep
    grep.c
    
    # Search file
    $ ./grep ep grep.c
    /* 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 command to search for strings (you do not need to support regular expressions).

    To test your grep.c program, you can use the provided test_grep.sh script:

    # Download script
    $ curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_grep.sh
    
    # # Make script executable
    $ chmod +x test_grep.sh
    
    # Run test script
    $ ./test_grep.sh
    grep test successful!
    

Makefile

To build your programs, you need to write and use a Makefile. Here is the start of a simple Makefile:

CC=             gcc
CFLAGS=         -g -gdwarf-2 -Wall -std=gnu99
TARGETS=        sort grep

all:            $(TARGETS)

# TODO: Add rules for sort and grep

test:           test_sort.sh test_grep.sh
        ./test_sort.sh
        ./test_grep.sh

test_sort.sh:
        curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_sort.sh
        chmod +x $@

test_grep.sh:
        curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_grep.sh
        chmod +x $@

clean:
        rm -f $(TARGETS)

You will need to write the rules or recipes for the sort and grep targets. Be sure to use the CC and CFLAGS variables.

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

# Remove targets
$ make clean
rm -f sort grep

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

# Run tests
$ make test
curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_sort.sh
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                Dload  Upload   Total   Spent    Left  Speed
100   679  100   679    0     0  31348      0 --:--:-- --:--:-- --:--:-- 33950
chmod +x test_sort.sh
curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/static/sh/test_grep.sh
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                Dload  Upload   Total   Spent    Left  Speed
100  1227  100  1227    0     0  57104      0 --:--:-- --:--:-- --:--:-- 61350
chmod +x test_grep.sh
./test_sort.sh
sort test successful!
./test_grep.sh
grep test successful!

Feedback

If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your response.

Submission

To submit your assignment, please commit your work to the reading07 folder in your assignments GitLab repository. Your reading07 folder should only contain the following files: