Reading 09: Pointers, Arrays, Strings

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.

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:

Beej's Guide to C Programming

Most of this should be review from Fundamentals of Computing, so skim through Chapter 1 through Chapter 7. In particular, focus on Chapter 5. Pointers, Chapter 6. Arrays, and Chapter 7. Strings.
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¶

The 5 Minute Guide to C Pointers
- Basics of Pointers and Arrays in C
- Basics of Memory Addresses in C

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 GitHub

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

$ cd reading09                        # Go into reading09 folder

# Download Reading 09 Makefile
$ curl -LO https://raw.githubusercontent.com/nd-cse-20289-sp21/cse-20289-sp21-assignments/master/reading09/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 09 Quiz questions in your reading09 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).

Note: Make sure you return with an non-zero exit code if the PATTERN is not found in the input stream.

`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 reading09                        # Go into reading09 folder

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

$ ../.scripts/check.py                # Check reading09 quiz
Checking reading09 quiz ...
     Q01 0.25
     Q02 0.25
     Q03 0.25
     Q04 0.25
     Q05 0.60
     Q06 0.20
     Q07 0.20
   Score 2.00 / 2.00
  Status Success

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 09: 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 09: Code"    # Commit work

$ git push -u origin reading09        # Push branch to GitHub

Pull Request¶

Remember to create a Pull Request and assign the appropriate TA from the Reading 09 TA List.

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