The readings for Monday, March 20 are:
Note: This is from the Stanford CS Education Library.
GCC and Make - Compiling, Linking and Building C/C++ Applications
Note: Just skim what you need; we will explore this more deeply in class.
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.
Propaganda
C Language:
Pointers and Arrays:
Note: This is from the author of PuTTY.
Makefiles:
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.
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; }
In your reading07/README.md
file, answer the following questions:
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.
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.
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.
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!
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; }
In your reading07/README.md
file, answer the following questions:
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
.
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.
Explain how the cat_stream
function works. What are the purposes of
fgets and fputs?
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; }
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!
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!
If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your response.
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:
README.md
Makefile
grep.c
sort.c