Due Date

Due by 11:59 pm, Wednesday, Nov 27, 2024

We encourage you to complete this lab by Tuesday as we will assign the next lab assignment on the Tuesday before Thanksgiving.

This lab should be done with your Lab 9 partner, listed here: Lab 9 partners

Please review our guidelines for working with partners, etiquette and expectations.

1. Lab Goals

  • Learn how to implement a C library (.h and .c files), and then use your library in a program.

  • Learn more about C strings and char types, and use and C ctype and string library functions in programs.

  • Gain more expertise with dynamic memory allocation and pointers in C.

  • Further your mastery of using gdb and valgrind for debugging C programs.

2. Lab Overview

In this assignment you and your partner will implement a C library and complete test code to test the functions in your library. Specifically, you will implement a function from the parsecmd library. It takes command line strings that it parses into an argv array that could be used by a program to pass to an exec function. It also takes a pass-by-pointer parameter (bg) that it sets to indicate if the command is run in the background or not.

You will implement the parse_cmd_dynamic function from the parsecmd library. This is a slightly different version of a parse command function from the one you used in your shell program. This version dynamically allocates the argv array (and dynamically allocates each C string pointed to by each argv[i] element) that it returns to the caller:

char **parse_cmd_dynamic(const char *cmdline, int *bg);

The parse_cmd_dynamic function takes the command line string and returns a dynamically allocated argv array of strings (an array of char *, so the return type is char \*\*). The function initializes the returned array’s bucket values to individual tokens from the cmdline string. Each token string is a dynamically alloc’ed. The caller is responsible for freeing all the memory space of the returned array.

You will use a test program that includes and links in your library to test its functionality and correctness.

Your library, once implemented, could also be linked into your shell program (modify the LIBDIR variable in its Makefile to do this) and your shell program could be modified to call parse_cmd_dyanmic and with only some minor modifications to handling the return type, work similarly to how it does when you linked in my implementation of the parscmd library! You are not required to do this, but you could try it out.

3. Starting Point Code

3.1. Getting Your Lab Repo

Both you and your partner should clone your Lab 9 repo into your cs31/Labs subdirectory:

  1. get your Lab 9 ssh-URL from the CS31 git org. The repository to clone is named Lab9-userID1-userID2 where the two user names match that of you and your Lab 9 lab partner.

  2. cd into your cs31/Labs subdirectory:

    $ cd ~/cs31/Labs
$ pwd

  3. clone your repo

    git clone [the ssh url to your your repo]
cd Lab9-userID1-userID2

There are more detailed instructions about getting your lab repo from the "Getting Lab Starting Point Code" section of the Using Git for CS31 Labs page.

As your start each lab assignment, it is good to first test that you and your partner have both successfully cloned your shared repo, and that you can share code by pushing a small change and by pulling a small change made by your partner. Follow the directions in the "Sharing Code with your Lab Partner" section of the Using Git for CS31 Labs page.

3.2. Starting Point files

$ ls
design_worksheet  Makefile  parsecmd.c  parsecmd.h  README.adoc  tester.c

  • Makefile: builds the library .o file and a tester program executable file

  • README.md: some notes to you

  • parsecmd.h: the header file for the parsecmd library. It contains the interface to the library (the function prototypes and any other definitions the library exports, like #define constants). You do not need to modify this file.

  • parsecmd.c: the implementation part of the parsecmd library. Your implementation of the library function parse_cmd_dynamic will go in here.

  • tester.c: a test program or your parsecmd library. Add code here to test the functionality of your library. There is not a lot of code that you need to add to this file. But, note the TODO comments in this file for some places where you will need to add code to fully test your library.

  • design_worksheet: start your lab assignment by filling in this worksheet with the design of each parse_cmd library function before you implement it. You should bring this filled out worksheet with you to the ninja session, and to office hours and other times you are seeking help on your lab assignment. To print a copy of this worksheet to a CS lab printer, use the lpr command:

      lpr design_worksheet

    See the "Getting Started" tips in Section 8 for information about how and when to use this worksheet.

4. Compiling and Running

You will implement the library functions in parsecmd.c and then use the tester program (source in tester.c to test your implementation.

The tester program, in a loop:

  • reads in a command line string (or quit to exit)

  • calls your parsecmd function to parse the command line

  • prints out the resulting argv string values, each string between # chars so you can see if you have any whitespace characters you didn’t remove

  • prints out if the command line has a & at the end, signifying to run in the background.

To run:

$ ./tester

5. Sample Output

Here is output from a run of my program: Sample Output

6. Lab Details

You will implement the parsecmd library function parse_cmd_dynamic that parses a command line string into its individual command line arguments and construct an argv list of strings from the command line args.

Your library function can be used by other programs that #include "parsecmd.h" and link in a binary version of your library’s implementation (parsecmd.o). For example:

gcc -g -o tester tester.c parsecmd.o

The Makefile included with the lab assignment builds parsecmd.o and links it into the tester program. You should use the tester program to test the correctness of your library functions. You will need to add more testing code to tester.c to fully test your library functions.

6.1. The interface to the parsecmd library (parsecmd.h)

The parsecmd.h file contains the interface to the library you will implement. Applications using the parsecmd library should #include it:

#include "parsecmd.h"

You do not need to modify this file but you should use some of the constants it defines in your library implementation code. Also, read the comments in parsecmd.h to ensure that you implement the two library functions correctly (i.e., your functions do what the interface says that they do).

6.2. Implementing the parsecmd library (parsecmd.c)

For this lab we are only having you implement one function in the parsecmd library (parse_cmd_dynamic), a version that is slightly different from the one you used in the shell lab assignment.

This takes in a command line string (like in the shell lab), and parse it into an argv list (an array of strings, one per command line argument), it also tests for an ampersand in the command line, which, when present, indicates a background command. For example, if the user enters the follow command line string:

cat foo.tex

Your function will be passed the string:

"cat foo.tex\n"

And will parse the command line string into the argv array:

argv [0] ---->"cat"
argv [1] ---->"foo.tex"
argv [2] ----|  (NULL)

6.2.1. The parse_cmd_dynamic function

This version of the of the function is not limited in the same way as the version you used in the shell lab (the parse_cmd function). Namely, the user is not limited to command line strings that are at most MAXLINE characters and have at most MAXARGS arguments.

/*
 * parse_cmd_dynamic - parse the passed command line into an argv array
 *
 *    cmdline: the command line string entered at the shell prompt
 *         bg: will set value pointed to 1 if command line is run in
 *             background, 0 otherwise (a pass-by-reference parameter)
 *
 *    returns: a dynamically allocated array of strings, exactly one
 *             bucket value per argument in the passed command line
 *             the last bucket value is set to NULL to signify the
 *             end of the list of argument values.
 *             or NULL on an error
 *
 *             The caller is responsible for freeing the returned argv array.
 */
char **parse_cmd_dynamic(const char *cmdline, int *bg);

This function will:

  1. Optional: make a temparary copy of the cmdline string if your code wants to modify the string as part of any processing it does to create the argv array. And, be sure to free it when done. You should not modify the caller’s passed command line string.

  2. Check for run-in-the-background: see if there is a & in the copy of the cmdline string, and treat it as the end of the string if it is not at the end of the string (you can ignore any chars after a & in a the command line string for this assignment).

  3. Count the number of tokens in the string. A token is a sequence of non-whitespace chars, each separated by at least one whitespace character (or by &). Tokens should not include &, which has special meaning in command lines. Determine how many tokens are in the cmdline string and malloc EXACTLY the right number of argv buckets for the particular cmdline string (remember an extra bucket at the end for NULL).

  4. Allocate space for the argv array.

  5. Process the the command line string to create individual string tokens from the command line string, each of which will be added as elements of the argv array. Each element in argv[i] should store a separate token string. Be sure to malloc exactly enough space for a char array to store the token as a string (remember an extra bucket for the terminating '\0' character).

  6. Finish initializing the argv array that you return to the caller. The caller is repsonsible for freeing the space malloced for the argv array returned by your parase_cmd_dynamic function.

For example, if the command line entered is the following (note the user entered a few extra spaces in this command line, and $ is the shell prompt):

$   ls  -1  -a &

The command line string associated with this entered line is (note the spaces in the string):

"  ls  -l  -a &\n"

And the string stored in memory might look like:

cmdline ------> 0 | ' ' |
                1 | ' ' |
                2 | 'l' |
                3 | 's' |
                4 | ' ' |
                5 | ' ' |
                6 | '-' |
                7 | 'l' |
                8 | ' ' |
                9 | ' ' |
               10 | '-' |
               11 | 'a' |
               12 | ' ' |
               13 | '&' |
               14 | '\n'|
               15 | '\0'|

The parse_cmd_dynamic function processes the comand line string (or a copy of it) to discover the number tokens inoder to know to malloc an argv array of 4 char * values, and to recongize that this is a run in the background command. It then processes the command line string again to extract token strings. It will malloc three arrays of char values, one for each token in command line string, the base address of each stored in a bucket of the argv array. For the example command above, the returned array would look something like this:

// local var to store dynamically allocated args array of strings
char **argv;


argv --------->[0]-----> "ls"
               [1]-----> "-l"
               [2]-----> "-a"
               [3]-----|  (NULL)

Your function cannot modify the cmdline string that is passed in to it. But you may malloc space for a local copy of the cmdline string to tokenizes if this helps. If you use this approach, your function must free this copy before it returns.

parse_cmd_dynamic requires more than a single pass through the chars of the command line string. Start with the design of it using the design_worksheet (see Section 3).

7. Lab Requirements

  1. Your function should meet the specification described above.

  2. You may not change any of the function prototypes in the parsecmd library (and don’t change the .h file). Your library code must work with our test code that makes calls to these functions as they are defined above.

  3. You may not use global variables.

  4. You should use good modular code. The library function should not be static, but you can add helper functions that are private to the .c file, and thus should be declared static (they are only in scope inside the parsecmd.c file…​they are private functions in parsecmd.c).

  5. All system and function calls that return values should have code that detects and handles error return values.

  6. Your functions should work for command lines entered with any amount of whitespace between command line options (but there should be at least one whitespace char between each). For example, all these should yield identical argv lists:

    cat foo.txt  blah.txt      &
cat foo.txt  blah.txt&
             cat          foo.txt           blah.txt          &

    TEST that your code works for command lines with any amount of whitespace between command line arguments

  7. Your code should be well commented. See my C style guide for examples of what this means.

  8. Your code should be free of valgrind errors. You will need to add code to tester.c to free the space allocated and returned by the dynamic version of the function. Any other space you malloc internally in your library functions (that it does not explicitly return to the caller) should be freed before the function returns. Still Reachable is okay.

  9. You may not use the string library strtok or strtok_r functions in your solution.

8. Tips and Hints

  • Getting started:

    1. Start by reviewing Section 2.9.6 of the textbook, and/or the "CREATING AND USING YOUR OWN LIBRARY CODE" section of the following: Building and Using libraries in C, and the weekly lab library example.

    2. Next, print out the design_worksheet from your repo and follow the directions for outlining the design of your solution of each library function before you start implementing it. See Section 3 for more details and directions.

    3. After filling out the worksheet with your design for parse_cmd, implement and test it.

    4. Next, fill out the the design_worksheet to design the parse_cmd_dynamic function.

    5. Then implement and test it.

  • Implement and test incrementally! Break up the functionality of a function into parts that you implement and test incrementally. Use valgrind as you go to catch memory access errors as you make them.

  • Review strings, char, and pointers in C. Chapter 2 of the textbook contains sections on this material. And see other references listed in Section 10.

  • Remember if you dynamically allocate space for a string (using malloc), you need to allocate a space at the end for the terminating null character ('\0'), and that you need to explicitly free the space when you are done using it (call free).

  • Use string library and ctype functions. (For more info see the textbook, my string and char documentation off my help pages, and the man pages of individual functions.) Some that may be useful include:

    strlen, strcpy, strchr, strstr, isspace

    Here is an example of using strstr and modifying a string to create a substring:

      int i;
  char *ptr, *str;
  str = malloc(sizeof(char)*64);
  if(!str) { exit(1); }
  ptr = strcpy(str, "hello there, how are you?");
  if(!ptr) { exit(1); }
  ptr = strstr(str, "how");
  if(ptr) {
     printf("%s\n", ptr);  // prints: how are you?
     ptr[3] = '\0';
     printf("%s\n", ptr);  // prints: how
  } else {
    printf("no how in str\n");
  }

    strstr may or may not be useful in this assignment, but you will need to create token strings in a way that has some similarities to this example.

  • Remember, you cannot directly compare two strings using == or other similar operators. Instead, you need to use strcmp.

  • You can directly compare the value of two char values using == and other relational operators. For example:

    char *str;
...
if(str[i] == 'a') { ... }

  • Command lines with ampersands in the middle can be handled like bash handles them (bash ignores everything after the &):

    "hello there & how are you?"

    gets parsed into an argv list that looks like this:

    argv[0]---->"hello"
argv[1]---->"there"
argv[2]----|  (NULL)

  • Use gdb (or ddd) and valgrind as you incrementally implement and test.

  • Writing string processing code can often times be tricky. Use the debugger to help you see what your code is doing. It may be helpful to step through each C statement using next If you do this and want to see the results of instructions on program variables you can use the display command to get gdb to automatically print out values every time it gains control. Here is an example of displaying two variables (ptr and i):

    (gdb) display ptr
(gdb) display i

  • Think very carefully about type. Draw pictures to help you figure out what values you need to access and what their types are.

9. Submitting your Lab

Please remove any debugging output prior to submitting.

To submit your code, commit your changes locally using git add and git commit. Then run git push while in your lab directory. Only one partner needs to run the final git push, but make sure both partners have pulled and merged each others changes.

Also, it is good practice to run make clean before doing a git add and commit: you do not want to add to the repo any files that are built by gcc (e.g. executable files). Included in your lab git repo is a .gitignore file telling git to ignore these files, so you likely won’t add these types of files by accident. However, if you have other gcc generated binaries in your repo, please be careful about this.

Here are the commands to submit your solution in the sorter.c file (from one of you or your partner’s ~/cs31/Labs/Lab9-userID1-userID2 subdirectory):

$ make clean
$ git add *.c
$ git commit -m "correct and well commented Lab9 solution"
$ git push

Verify that the results appear (e.g., by viewing the the repository on CS31-f24). You will receive deductions for submitting code that does not run or repos with merge conflicts. Also note that the time stamp of your final submission is used to verify you submitted by the due date, or by the number of late days that you used on this lab, so please do not update your repo after you submit your final version for grading.

If you have difficulty pushing your changes, see the "Troubleshooting" section and "can’t push" sections at the end of the Using Git for CS31 Labs page. And for more information and help with using git, see the git help page.

At this point, you should submit the required :labquesturl: Lab 9 Questionnaire (each lab partner must do this).

10. Handy References

General Lab Resources

C programming Resource

Specific to this assignment

General C resources