Homework 4 Implementing an arraylist

Homework 4 CS 2200 - Systems and Networks 
1 Introduction
In this homework, you will be implementing an arraylist and debugging code for a ”Random Message
Generator”.
Before you begin, we heavily recommend using an Ubuntu virtual machine to test your code locally. You
are responsible for making sure your code works on Ubuntu, as C may work slightly differently on different
OSes. A guide for installing the virtual machine is on Canvas.
The files we provided include:
• main.c: main functions that generate the random message
• main.h: header file of the main function
• arraylist.c: functions that are used to manipulate the Arraylist
• arraylist.h: header file of Arraylist data structure
• arraylist test.h: header file for the tests for the arraylist data structure.
• arraylist test.c: functions for testing the the arraylist data structure
• Makefile: A script that can be used for compiling the code (optional).
You will be modifying Arraylist.c, main.c, and main.h for this homework.
2 Part 1: Implement to take in parameters from command lines
First lets knock out taking in arguments from the command line. There will be two command line arguments
for this program. This code should be written in the main method in the main.c file. Look for inline comments
will describe where you should implement your code. The arguments are are:
• t triggers the program to run the unit tests on the arraylist rather than generating a random message.
• l sets the length of the message that the program will generate.
We highly recommend using the getopt() function. The method head looks like this:
getopt(int argc, char *const argv[], const char *optstring)
where argc is the argument count, argv is argument array, and optstring is the specified list of characters,
each representing a single character option. If the character in opstring is followed by ’:’, the corresponding
option will take in an argument, and that argument will be pointed by optarg.
This function will return the next option character (if one is found) from argv that matches a character in
optstring. If no character in argv is in optstring or there is a missing argument, it will return ’?.’ If we
set the first character of optstring to be ’:’ and we encounter a missing argument situation, it will return
’:’ instead. Otherwise, it will return -1 which indicates that all option characters have been parsed.
2.1 Deliverable 2 GDB Snapshot
Once we implement the taking in the command line arguments we want to test to ensure the program is
taking the input in correctly. Use GDB to get the values of the variables test and length. Take a screenshot
of your GDB program showing that you got the values of the variables through GDB and submit that with
your code on Gradescope. You can pass in any value for l as you wish as long as it is not 0. Your GDB test
should show that length ̸= 0 and tests = 1 A guide to using GDB is located in Section 4 of this PDF.
2.2 Compiling and Running
In the future, we will provide you with a Makefile for compiling your programs. However, for this assignment,
we want you to be aware of how C programs are actually compiled. To compile a program you’ll use the gcc
Homework 4 CS 2200 - Systems and Networks Spring 2022
compiler. To use the gcc compiler use the following format:
• gcc PATH/TO/C/FILE PATH/TO/C/FILE ... -o PROGRAM NAME
Replace the capitalized words with the appropriate values. The program name can be anything you would
like, since we will compile your programs on our own during grading. However, we will call the program
Word Generator if you would like to use that name. You will need to compile all the .c files that will be
used in your program. In this case you will need to compile all the .c files provided.
If that seems like a lot to type whenever you want to compile you can use the Makefile provided. Essentially,
add your gcc command to the line under ”final:” and now typing make should compile your code. Please
note that the line after ”final:” needs to be indented. The Makefile is not turned in and is optional. Makefiles
in the future will be provided and will have more functionality.
To run the program you will simply need to type the path to your program. One thing to not is that you
will have to put ./ if you are in the same directory as your program. For example if you use the name
Word Generator:
• From same directory: ./Word Generator -l 10
• From same directory: ./Word Generator -t
• From different directory: ./PATH/.../Word Generator -t
3 Part 2: Implement the Arraylist methods
Next, implement the functions for the Arraylist data structure in Arraylist.c:
• create arraylist: Taking the capacity of the arraylist as an input, create an Arraylist using the
backing array with type ** char. Remember should use malloc() to allocate space for the storage of
the Arraylist. The function should return a pointer to the Arraylist you created.
• add at index: Add a word to Arraylist at a specific index. If the length of the Arraylist is going to
exceed the capacity, resize the Arraylist to twice its original capacity. You can call resize(), which is
also a function you will implement, to do this.
• append: Add a word to the end of the Arraylist. Remember to resize as required in add at index.
• remove from index: Remove a word from the Arraylist at a certain index and return the word removed.
Make sure to maintain the Arraylist contiguous.
• resize: Resize the backing array to hold twice its original capacity. It should now support arraylist->capacity∗
2 elements.
Please refer to the comments in arraylist.h for further guide lines. Also note that arraylist.c is almost blank.
In short, you need to implement the functions defined in arraylist.h. Think of arraylist.h as the interface
that your code is expected to comply to. If your code passes the arraylist tests sanity tests and your word
generator gives the expected output, then in your code should be good. We reserve the right to review the
code to ensure that your implementation is not hard coded or incorrect (i.e. implemented a link list instead
of an array list).
4 Part 3: Debug the main file
For the last part of the project, you will need to debug the provided code in main.c and main.h. This code
is used to create a ”random word generator” that, in short, draws a number of random words from an array
called ”Dictionary”. There are 3 problematic lines of code that are causing problems located somewhere
throughout the provided code. If you get stuck look for the comments for hints! This section is to prepare
you for debugging C code on your projects that are much larger and more complex than this code.
Homework 4 CS 2200 - Systems and Networks Spring 2022
Please note, this code almost works! By eliminating the mistakes causing segmentation faults, the code
should run properly. All 3 errors in the code should cause segmentation faults and no other errors. If you
are unclear if your fix changes the intended functionality of the code, please refer to the comments.
The intended output from the program is:
• -l 5: Message: go yellow Half jackets piano
• -l 10: Message: go yellow jackets piano science Half this is correct congratulations
• -l 15: Message: go yellow jackets piano science this is Half correct congratulations unruly red viola
potato carrot
The output shown above should be the only output onto stdout (or stderr) that your program makes when
the l argument is used. When the t argument is used only the outputs of the arraylist tests should be shown
on stdout (or stderr). We will not run your program with both the t and l arguments used simultaneously.
If this part seems tedious, often small bugs that are easily overlooked lead to headaches on the projects.
Hopefully, this practice allows you to locate them easier in the future.
4.1 GDB Debugging Tips
If your program is crashing or misbehaving, you can use GDB to locate the bug. GDB is a command line interface that will allow you to set breakpoints, step through your code, see variable values, and identify segfaults.
There are tons of online guides, click here (http://condor.depaul.edu/glancast/373class/docs/gdb.html) for
one.
Within GDB, you can run your program with the run command:
$ (gdb) r -i <# of words>
You may find it useful to set a breakpoint inside the main loop of the simulator to debug specific simulator
commands in your implementation. You can do this either by finding the line number inside main.c and
breaking there:
$ (gdb) break main.c:53 ! set breakpoint at call to system init
$ (gdb) r -i <# of words>
! (wait for breakpoint)
$ (gdb) s ! step into the function call
or by using the actual function name being called from the main loop:
$ (gdb) break sim cmd ! set breakpoint at call to sim c
$ (gdb) r -i <# of words>
! (wait for breakpoint)
$ (gdb) s ! step into the function call
Sometimes, you may want to examine a large area of memory. To do this in GDB, you can use the x
command (short for examine). For example, to examine the first 24 bytes of the frame table, we could do
the following:
$ (gdb) x/24xb frame table
0x1004000aa: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x1004000b2: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x1004000ba: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
The format of this command is x/nfu [memory location], where n is teh number of items to print, f is a
formatting identifier, and u is the specifier for the units you would like to print. b specifies 1 byte, h specifies
2 bytes, w specifies 4 bytes, and g specifies 8 bytes.
Homework 4 CS 2200 - Systems and Networks Spring 2022
If you use the corruption checker, you can set a breakpoint on panic() and use a backtrace to discover the
context in which the panic occurred:
$ (gdb) break panic
$ (gdb) r -i <# of words>
! (wait for GDB to stop at the breakpoint)
$ (gdb) backtrace
$ (gdb) frame N ! where N is the frame number you want to examine
Homework 4 CS 2200 - Systems and Networks Spring 2022
5 Submission
Files you will submit on Gradescope:
• Arraylist.c
• main.c
• main.h