Project 5: Linked List Solution

Overview



In this assignment, you will be implementing a list data structure whose underlying implementation is a singly-linked list. If you have taken CS 1331/32 (don’t worry if you haven’t taken 32), then you should be familiar with this data structure.




Linked List Implementation



We are implementing a single-linked list. You are given a list which has a head pointer pointing to the first node in the list. Each node contains a next pointer to the next node in the list and a data pointer to a Crab. Refer to the following diagram for a visual representation to help you out when implementing your linked list!


















































































Instructions



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







ListNode *create_node(Crab *): Takes in a crab, creates a ListNode containing that crab as its data, and returns the ListNode.



List *create_list(): creates an empty list and returns it



void push_back(List *, ListNode *): adds a ListNode to the back of the List



int remove(List *, Crab **, crabbiness): finds and removes the Crab whose crabtitude is equal to crabbiness. The Crab data will be returned via the Crab** parameter and the ListNode containing the crab will be removed completely.



int copy_crab(Crab *, Crab **): creates a deep copy of a crab and returns the deep copy through the Crab ** parameter.






2
List *copy_list(List *): creates a deep copy of the list. This includes creating a new list, new nodes, and new crabs in the nodes.



void destroy_crab(Crab *): completely destroys all data in the crab and the crab itself.



void destroy(List *): destroys the list itself. This will destroy the list, all nodes within the list, and the crabs within the nodes.



int compare_crabtitude(Crab *, Crab *): Compares the two crabs based off of crabtitude.



int compare_name(Crab *, Crab *): Compares two crabs based on their name



int swap_nodes(ListNode *, ListNode *, List *): Swaps the two nodes in the list in place.



int sort(List *, int (*compare_func)(Crab *, Crab *b)): Utilizes the compare function pointer to sort the list (in place) in ascending order.



Crab **list_to_array(List *, int): Convert the linked list data structure to an array of crabs.



You should not be leaking memory in any of the functions. For any functions utilizing malloc, if malloc returns null, return either 0 or null (based on the function header) and ensure that no memory is leaked.




Be sure not to modify any other files. Doing so may result in point deductions that the tester will not reflect.










Checker/Makefile 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 Makefile.




Note: There is a file 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 file as you will need to redownload the assignment. Also keep in mind that this file 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 Makefile 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 final 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.







3
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 infinitely, 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 Makefile section for running an individual test with gdb.




If your code generates a segmentation fault then you should first run gdb before asking questions. We will not look at your code to find your segmentation fault. This is why gdb was written to help you find your 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 Makefile




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




Here are the commands you should be using with this Makefile:




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



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



To run your tests with valgrind: make run-valgrind



To debug a specific test with valgrind: make TEST=test_name run-valgrind



To debug a specific test using gdb: make TEST=test_name run-gdb Then, at the (gdb) prompt:

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
Run the test with run



If you set breakpoints: you can step line-by-line (including into function calls) with s or step over function calls with n
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.










4
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 specific test using gdb” instructions above.




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




Deliverables



Submit ONLY list.c.




Your files must compile with our Makefile, which means it must compile with the following gcc flags:




-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 Makefile as described below.




Please check your submission after you have uploaded it to Gradescope to ensure you have submitted the correct file.




Rules and Regulations



6.1 General Rules




Although you may ask TAs for clarification, 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.



Please read the assignment in its entirety before asking questions.



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



If you find 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




When preparing your submission you must submit the files individually to Gradescope.



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



6.3 Submission Guidelines




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-



5
tion (i.e. note from the dean, doctors 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.




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 files, 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.



Projects turned in late receive zero credit. You alone are responsible for submitting your project before the assignment is due; neither Canvas/Gradescope, nor your flaky 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 after the assignment is due is non-negotiable.



6.4 Syllabus Excerpt on Academic Misconduct




Academic misconduct is taken very seriously in this class.




Students are expected to have read and agreed to the Georgia Tech Honor Code, see http://osi.gatech.edu/content/honor-code.



Suspected plagiarism will be reported to the Division of Student Life office. It will be prosecuted to the full extent of Institute policies.



A student must submit an assignment or project as his/her own work (this is what is expected of the students).



Using code from GitHub, via Googling, from Stack Overflow, etc., is plagiarism and is not permitted. Do not publish your assignments on public repositories (i.e., accessible to other students). This is also a punishable offense.



Although discussion among the students through piazza and other means are encouraged, the sharing of work is plagiarism. If you are not sure about it, please ask a TA or stop by the instructor’s office during the office hours.



TAs and Instructor determine whether the project is plagiarized. Trust us, it is really easy to determine this....






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 should not 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 figure 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 youre not in the same room.




























6






































































































































































































7