CSE logo University of Washington Computer Science & Engineering
 CSE 374 Programming Concepts and Tools - Homework 4 - Winter 2011
  CSE Home   About Us    Search    Contact Info 

Due: Thursday, Feb. 3, at 11 pm.

Assignment goal

The purpose of this assignment is to gain some experience with C programming by implementing a utility program that is similar to grep, but without the ability to process regular expressions (i.e., a lot like a simple version of fgrep). In particular, in this assignment, you will:

This assignment does not include any particularly complicated logic or algorithms, but it will require you to organize your code well and make effective use of the C language and libraries. You will also have to explore the details of the C string and file I/O libraries to discover how to do various operations that should already be familiar from your programming experience in other languagesm although the details in C will be different, or course. It is meant as an orientation to the Unix/Linux C programming environment. You should do this assignment by yourself.

Synopsis

Implement in C a Unix utility program gasp. The command

        gasp [options] STRING FILE...

should read the listed files (FILE...) and copy each line from the input to stdout if it contains STRING. Each output line should be preceded by the name of the file that contains it. The argument STRING may be any sequence of characters (as expanded, of course, by the shell depending on how it is quoted). There are two available options, which may appear in any order if both are present:

Your program does not need to be able to handle combinations of option letters written as a single multi-character option like -in or -ni. But it does need to be able to handle any combination of either or both (or neither) option when they appear separately on the command line.

(This is basically the same output produced by grep if the STRING argument is treated as literal data and not as a regular expression. You should pretty much match the output format of grep, although your program's output does not need to be byte-for-byte identical. One difference, though, is that a file name should be printed on every output line, even if only one file is specified on the gasp command line.)

Technical Requirements

Besides the general specification given above, your program should meet the following requirements to receive full credit.

  1. Be able to handle input lines containing up to 500 characters (including the terminating \0). This number should not be hard-wired everywhere in the code, but should be specified with an appropriate #define preprocessor command so it can be changed easily. Your program is allowed to produce incorrect results or fail if presented with input data containing lines longer than this limit.
  2. You may assume that the string pattern on the command line is no longer than 100 characters (including the terminating \0). This length should also be specified by an appropriate #define.
  3. Use standard C library functions where possible; do not reimplement operations available in the basic libraries. For instance, strncpy in <string.h> can be used to copy \0-terminated strings; you should not be writing loops to copy such strings one character at a time.
    Exception: there is a getopt function in the Linux library that provides simplified handling of command line options. For this assignment, only, you may not use this function. You should implement the processing of command line options yourself, of course using the string library functions when these are helpful.
  4. You should use "safe" versions of file and string handling routines such as fgets and strncpy instead of routines like gets and strcpy. The safe functions allow specification of maximum buffer or array lengths and will not overrun adjacent memory if used properly.
  5. For the -i option, two characters are considered to be equal ignoring case if they are the same when translated by the tolower(c) function (or, alternatively, toupper(c)) in <ctype.h>.
  6. If an error occurs when opening or reading a file, the program should write an appropriate error message to stderr and continue processing any remaining files on the command line.
  7. Your code must compile and run without errors or warnings when compiled and executed on the CSE Linux VM using gcc with the -Wall option. Since this assignment should not need to use any unusual or system-dependent code you can almost certainly develop and test your code on any recent Linux system or other system that supports a standard C compiler. However, we will test your submissions using the CSE VM, so you may want to verify your program there before the submission deadline.

Code Quality Requirements

As with any program you write, your code should be readable and understandable to anyone who knows C. In particular, for full credit your code must observe the following requirements.

  1. Divide your program into suitable functions, each of which does a single well-defined task. For example, there should almost certainly be a function that processes a single input file, which is called as many times as needed to process the list of files on the command line (and which, in turn, might call other functions to perform identifiable subtasks). Your program most definitely may not consist of one huge main function that does everything. If you wish, you may include all of your functions in a single C source file, since the total size of this program will be fairly small. Be sure to include appropriate function prototypes near the beginning of the file so the actual function definitions can appear in whatever order is most appropriate for presenting the code in the remainder of the file.
  2. Comment sensibly, but not excessively. You should not use comments to repeat the obvious or explain how the C language works -- assume that the reader knows C at least as well as you. Your code should, however, include the following minimum comments:
  3. Use appropriate names for variables and functions: nouns or noun phrases suggesting the contents of variables or the results of value-returning functions; verbs or verb phrases for void functions that perform an action without returning a value. Variables of local significance like loop counters, indices, or pointers should be given simple names like i, k, n, or p, and do not require further comments.
  4. No global variables. Use parameters (particularly pointers) appropriately. Exception: if you wish, you may have two global variables that indicate whether the -i or -n options are selected or not.
  5. No unnecessary computation. For example, if you need to translate the STRING argument to lower- or upper-case, translate it (or a copy of it) once; don't do this repeatedly for each input line or even for each input file. Don't make unnecessary copies of large data structures; use pointers. (Copies of ints, pointers, and similar things are cheap; copies of arrays and large structs are expensive.) Don't read the input by calling a library function to read each individual character. Read the input a line at a time (it costs just about the same to call an I/O function to read an entire line into a char array as it does to read a single character). But don't overdo it. Your code should be simple and clear, not complex containing lots of micro-optimizations that don't matter.

Implementation Hints

  1. There are a lot of things to get right here; the job may seem overwhelming if you try to do all of it at once. But if you break it into small tasks, each one of which can be done individually by itself, it should be quite manageable. For instance, figure out how to process a single file before you implement the logic to process all of the files on the command line. Figure out how to open, read, and copy all of a file to stdout before you add the code to search for the STRING argument and selectively print lines containing it. Be able to search for exact matches before adding the -i option to ignore case. Add the -n option separately when you're not trying to do something else.
  2. Every time you add something new to your code (see hint #1), test it. Right Now! Immediately! BEFORE YOU DO ANYTHING ELSE!!! (Did we mention that you should test new changes right away?) It is much easier to find and fix problems if you can isolate the potential bug to a small section of code you just added or changed. printf is your friend here to print values while debugging. The debugger is also your friend -- learn how to use it.
  3. The standard C library contains many functions that you will find useful. In particular, look at the <stdio.h>, <string.h>, <ctype.h> and <stdlib.h> libraries.
  4. An easy way to implement the -i option is to translate both the STRING argument and each input line to lowercase, then search for the translated STRING in the translated input line. (Translating a string to lower-case sure sounds like a well-defined operation that should be in a separate function!) However, if the string is found, the original line from the input file should be printed, not the translated one.
  5. Be sure to test for errors like trying to open or read a nonexistent file to see if your error handling is working properly.
  6. Once you're done, read the instructions again to see if you overlooked anything.
  7. See #6.

Debugging

Learning how to use a debugger effectively can be a big help in getting your programs to work (although it is no substitute for thinking and careful programming). To encourage you to gain a basic familiarity with gdb, you are required to do the following.

  1. Be sure your program is compiled with the -g option, to include debugging information in the executable file.
  2. Run the script program to capture the following console session in a text file named debug.txt.
  3. Start gdb with your executable program as an argument.
  4. Set two breakpoints: one at the beginning of main, and the other at the point in your program right after the fopen function call that opens the input files.
  5. Start your program with the gdb run command, providing a search string and at least one file name as arguments.
  6. When the program hits the breakpoint at the beginning of main, use the appropriate gdb command to display the contents of the variable containing the search string (the first argument to the program following any options that are present). When you've done that, continue execution of the program.
  7. When the program hits the second breakpoint immediately after opening an input file, use the appropriate gdb commands to display (i) a backtrace showing the functions active at the time the breakpoint was reached, (ii) source code showing the line containing the breakpoint and a couple of surrounding lines, (iii) the name of the file that was supplied to the fopen function (this string should be in a variable somewhere), and (iv) the pointer value returned by fopen (presumably just a hex address, although it might be NULL if the file can't be opened).
  8. Continue execution of the program until it stops, then quit gdb and exit from the script program's shell. Save the debug.txt output file from script to turn in later.

Extra Credit

A small amount of extra credit will be awarded for adding the following extensions to an already complete, working assignment. No extra credit will be awarded if the basic program is not fully implemented and substantially bug-free.

If you do any extra credit parts, you should turn in both your original program without the extra credit and your extended program. The extra credit version should be in a separate file whose name ends with "-extra", like gasp-extra.c.

Turn-in Instructions

Use the regular online dropbox to turn in the source code to your program and a copy of the script (console) output file debug.txt from the Debugging exercise above. If you did any extra credit, you should turn in a separate source file with your additions. You should also turn in a plain text file named README that describes any extra credit that you added to your program, or contains a brief note that you did not implement any of the extra credit parts. Be sure your name is included in the source code and README files.


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]