Homework 9 Linked List Solution

In this assignment, you will be implementing a list data structure whose underlying implementation is a singly-linked list. If you have taken CS1332(don’t worry if you haven’t), then you should be familiar with this data structure. Your linked list will be able to add, remove, and sort dog structs and query the data that it stores.


    • Instructions

You have been given one C le - list.c in which to implement the data structure. Implement all functions in this le. Each function has a block comment that describes exactly what it should do.

Be sure not to modify any other les. Doing so will result in point deductions that the tester will not re ect



    • Linked List Implementation

We are implemeting a very simple, single-linked list that is almost identical to the one you used in Homework

    7. You are given a struct list, which as a head pointer that points to the rst node in the list and a size. You also have a struct list node that has a next pointer to the next list node and also a data pointer that points to a struct dog. Refer to the following diagram for a visual representation of list and list node:







































2
3.1    Data Structure Design

The design of this list library is such that the person using your library does not have to deal with the details of the implementation of your library (i.e. the list node struct used to implement the list). None of these functions return a struct list node nor do any of these functions take in a struct list node. It is your responsibility to create the nodes and add them into the list yourself, not the user. When the user is done with the list, they will call empty list which removes all of the dog structs from the list and frees the nodes that contained pointers to the dog structs. Finally, you must free the list structure yourself so that no memory is leaked by your function.



    • Checker/Make le Usage

4.1    Testing & Debugging

We have provided you with a test suite to check your linked list that you can run locally on your very own personal computer. You can run these using the Make le.

Note: There is a le called test utils.o that contains some functions that the test suite needs. We are not providing you the source code for this, so make sure not to accidentally delete this le as you will need to redownload the assignment. Also keep in mind that this le does not have debugging symbols so you will not be able to step into it with gdb (which will be discussed shortly).


Your process for doing this homework should be to write one function at a time and make sure all of the tests pass for that function. Then, you can make sure that you do not have any memory leaks using valgrind. It doesn’t pay to run valgrind on tests that you haven’t passed yet. Further down, there are instructions for running valgrind on an individual test under the Make le section, as well as how to run it on all of your tests.

The given test cases are the same as the ones on Gradescope. Note that you will pass some of these tests by default. Your grade on Gradescope may not necessarily be your nal grade as we reserve the right to adjust the weighting. However, if you pass all the tests and have no memory leaks according to valgrind, you can rest assured that you will get 100 as long as you did not cheat or hard code in values.

You will not receive credit for any tests you pass where valgrind detects memory leaks or memory errors. Gradescope will run valgrind on your submission, but you may also run the tester locally with valgrind for ease of use.

Printing out the contents of your structures can’t catch all logical and memory errors, which is why we also require you run your code through valgrind.

We certainly will be checking for memory leaks by using valgrind, so if you learn how to use it, you’ll catch any memory errors before we do.

Here are tutorials on valgrind:
http://cs.ecs.baylor.edu/~donahoo/tools/valgrind/ http://valgrind.org/docs/manual/quick-start.html

Your code must not crash, run in nitely, nor generate memory leaks/errors.

Any test we run for which valgrind reports a memory leak or memory error will receive no credit.



If you need help with debugging, there is a C debugger called gdb that will help point out problems. See instructions in the Make le section for running an individual test with gdb.

If your code generates a segmentation fault then you should rst run gdb before asking questions. We will not look at your code to nd your segmentation fault. This is why gdb was written to help you nd your


3

segmentation fault yourself.

Here are some tutorials on gdb:
https://www.cs.cmu.edu/~gilpin/tutorial/ http://www.cs.yale.edu/homes/aspnes/pinewiki/C%282f%29Debugging.html http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Debug.html http://heather.cs.ucdavis.edu/~matloff/debug.html http://www.delorie.com/gnu/docs/gdb/gdb_toc.html

Getting good at debugging will make your life with C that much easier.

4.2    Make le

We have provided a Make le for this assignment that will build your project.

Here are the commands you should be using with this Make le:

    1. To clean your working directory (use this command instead of manually deleting the .o les): make clean

    2. To run the tests without valgrind or gdb: make run-tests

    3. To run your tests with valgrind: make run-valgrind

    4. To debug a speci c test with valgrind: make TEST=test name run-valgrind

    5. To debug a speci c test using gdb: make TEST=test name run-gdb Then, at the (gdb) prompt:

        (a) Set some breakpoints (if you need to | for stepping through your code you would, but you wouldn’t if you just want to see where your code is segfaulting) with b suites/list suite.c:420, or b list.c:69, or wherever you want to set a breakpoint

        (b) Run the test with run

        (c) If you set breakpoints: you can step line-by-line (including into function calls) with s or step over function calls with n

        (d) If your code segfaults, you can run bt to see a stack trace


For more information on gdb, please see one of the many tutorials linked above.

To get an individual test name, you can look at the output produced by the tester. For example, the following failed test is test list size empty:


suites/list_suite.c:906:F:test_list_size_empty:test_list_size_empty:0: Assertion failed...

^^^^^^^^^^^^^^^^^^^^

Beware that segfaulting tests will show the line number of the last test assertion made before the segfault, not the segfaulting line number itself. This is a limitation of the testing library we use. To see what line in your code (or in the tests) is segfaulting, follow the \To debug a speci c test using gdb" instructions above.

Note: The checker may not re ect your actual grade on this assignment. We reserve the right to update the checker as we see t when grading.







4
    • Deliverables

Submit ONLY list.c.

Your les must compile with our Make le, which means it must compile with the following gcc ags:

-std=c99 -pedantic -Wall -Werror -Wextra -Wstrict-prototypes -Wold-style-definition

All non-compiling homeworks will receive a zero. If you want to avoid this, do not run gcc manually; use the Make le as described below.

Please check your submission after you have uploaded it to gradescope to ensure you have submitted the correct le.


    • Rules and Regulations

6.1    General Rules

    1. Starting with the assembly homeworks, any code you write must be meaningfully commented. You should comment your code in terms of the algorithm you are implementing; we all know what each line of code does.

    2. Although you may ask TAs for clari cation, you are ultimately responsible for what you submit. This means that (in the case of demos) you should come prepared to explain to the TA how any piece of code you submitted works, even if you copied it from the book or read about it on the internet.

    3. Please read the assignment in its entirety before asking questions.

    4. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions.

    5. If you nd any problems with the assignment it would be greatly appreciated if you reported them to the author (which can be found at the top of the assignment). Announcements will be posted if the assignment changes.

6.2    Submission Conventions

    1. All les you submit for assignments in this course should have your name at the top of the le as a comment for any source code le, and somewhere in the le, near the top, for other les unless otherwise noted.

    2. When preparing your submission you may either submit the les individually to Canvas/Gradescope or you may submit an archive (zip or tar.gz only please) of the les. You can create an archive by right clicking on les and selecting the appropriate compress option on your system. Both ways (uploading raw les or an archive) are exactly equivalent, so choose whichever is most convenient for you.

    3. Do not submit compiled les, that is .class les for Java code and .o les for C code. Only submit the les we ask for in the assignment.

    4. Do not submit links to les. The autograder does not understand it, and we will not manually grade assignments submitted this way as it is easy to change the les after the submission period ends.






5
6.3    Submission Guidelines

    1. You are responsible for turning in assignments on time. This includes allowing for unforeseen circum-stances. If you have an emergency let us know IN ADVANCE of the due time supplying documenta-tion (i.e. note from the dean, doctor’s note, etc). Extensions will only be granted to those who contact us in advance of the deadline and no extensions will be made after the due date.

    2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After submitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong les, what you turn in is what we grade. In addition, your assignment must be turned in via Canvas/Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Canvas/Gradescope.

    3. There is a 6-hour grace period added to all assignments. You may submit your assignment without penalty up until 11:55PM, or with 25% penalty up until 5:55AM. So what you should take from this is not to start assignments on the last day and plan to submit right at 11:54AM. You alone are responsible for submitting your homework before the grace period begins or ends; neither Canvas/Gradescope, nor your aky internet are to blame if you are unable to submit because you banked on your computer working up until 11:54PM. The penalty for submitting during the grace period (25%) or after (no credit) is non-negotiable.

6.4    Syllabus Excerpt on Academic Misconduct

Academic misconduct is taken very seriously in this class. Quizzes, timed labs and the nal examination are individual work.

Homework assignments are collaborative, In addition many if not all homework assignments will be evaluated via demo or code review. During this evaluation, you will be expected to be able to explain every aspect of your submission. Homework assignments will also be examined using computer programs to nd evidence of unauthorized collaboration.

What is unauthorized collaboration? Each individual programming assignment should be coded by you. You may work with others, but each student should be turning in their own version of the assignment. Submissions that are essentially identical will receive a zero and will be sent to the Dean of Students’ O ce of Academic Integrity. Submissions that are copies that have been super cially modi ed to conceal that they are copies are also considered unauthorized collaboration.

You are expressly forbidden to supply a copy of your homework to another student via elec-tronic means. This includes simply e-mailing it to them so they can look at it. If you supply an electronic copy of your homework to another student and they are charged with copying, you will also be charged. This includes storing your code on any site which would allow other parties to obtain your code such as but not limited to public repositories (Github), pastebin, etc. If you would like to use version control, use github.gatech.edu

6.5    Is collaboration allowed?

Collaboration is allowed on a high level, meaning that you may discuss design points and concepts relevant to the homework with your peers, share algorithms and pseudo-code, as well as help each other debug code. What you shouldn’t be doing, however, is pair programming where you collaborate with each other on a single instance of the code. Furthermore, sending an electronic copy of your homework to another student for them to look at and gure out what is wrong with their code is not an acceptable way to help them, because it is frequently the case that the recipient will simply modify the code and submit it as their own. Consider instead using a screen-sharing collaboration app, such as http://webex.gatech.edu/, to help someone with debugging if you’re not in the same room.


6
























Figure 1: Collaboration rules, explained colorfully









































7