Description
1 Overview
In this assignment, you will be implementing a generalized tree (i.e., a tree where each node can have any number of children).
2 Tree Implementation
We are implementing a generalized tree. You are given a Tree which contains a pointer to a root Node. Each Node contains a pointer to its parent, a list of pointers to its children, a unique (integer) id, and a char* to a string.
3 Instructions
You have been given one C file – tree.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. NOTE: You canNOT assume data passed to a function is always valid.
Our Unit Tests will be pass invalid args.
• char* dynamic_string_copy(const char* str): Allocate a new string, copy the passed-in string over to it, and return the new string
• Tree* create_tree(void): Allocate a new Tree, and return a pointer to it. You should initialize it to have a NULL root and num_nodes = 0
• Node* create_node(const char* str): Allocate and initialize a new Node with a copy of the given data, and return a pointer to it. Make sure to use the global id counter (increment this counter for every new node)! For example, if you call create_node(…) one time, the node returned should have an ID of 0. If you call it a second time, the node returned should have an ID of 1
• void destroy_tree(Tree*): Completely destroy the given Tree. This means freeing everything that the Tree references (all Nodes)
• void destroy_node(Node*): Completely destroy the given Node. This function should probably be recursive
• Node* find_node(Tree*, int id): Traverse the given Tree, and return a pointer to the Node with the given id. Return NULL if it does not exist
• int insert_node(Tree*, int parent_id, char* new_child_data): Create a new Node, and insert it as the last child of the existing Node in the Tree with the id parent_id. Return 0 if this method fails, and 1 if it succeeds
• char* update_node(Tree*, int id, char* new_data): Update the data of the Node with the given id. Return the old data
• char* remove_node(Tree*, int id): Remove the Node with the given id. Assign all of the removed Node’s children to its parent, and return the removed Node’s data. Do not worry about removing the root of a tree. NOTE: the autograder will output tips for the implementation of this method since there are some rather interesting edge cases.
• void sort_children(Tree*, int id, int (*compare_func)(char*, char*)): Sort the array of children of the Node with the the given id. Use the given comparison function for sorting. You can use any sorting algorithm you like
• Tree* build_tree(FILE* file): Build a Tree from a specification in a file, and return a pointer to it. The file will contain text in a format like:
a:( bb:( ccc:() ddd:() ) ee:( fff:() ) gg:() )
Each node starts with a string of non-colon characters (at least length 1). This is the node’s data. Following the colon is a a set of parentheses containing a list of whitespace-separated child nodes. A node will no children will have an empty set of parentheses. Of course, the outermost node is the root of the tree
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.
4 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 main.o and one called tree_suite.o. These contain the 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.
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 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:
1. To clean your working directory (use this command instead of manually deleting the .o files): make clean
2. To run your own main.c file: make student:
3. To run the tests without valgrind or gdb: make run-tests
4. To run a specific test-case: make TEST=test_name run-case
5. To run your tests with valgrind: make run-valgrind
6. To debug a specific test with valgrind: make TEST=test_name run-valgrind
7. To debug a specific 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 specific test using gdb” instructions above.
5 Deliverables
Submit ONLY tree.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.
6 Demos
7 Rules and Regulations
7.1 General Rules
2. Please read the assignment in its entirety before asking questions.
4. 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.
7.2 Submission Conventions
2. 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.
7.3 Submission Guidelines
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 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.
4. Projects turned in late receive partial credit within the first 48 hours. We will take off 30% of the points for a project submitted between 0 and 24 hours late, and we will take off 50% of the points for a project submitted between 24 and 48 hours late. We will not accept projects turned in over 48 hours late. This late policy is also in the syllabus.
7.4 Syllabus Excerpt on Academic Misconduct
Academic misconduct is taken very seriously in this class.
3. A student must submit an assignment or project as his/her own work (this is what is expected of the students).
7.5 Is collaboration allowed?
