Starting from:
$30
CS2110-Homework 8 Linked List Solved
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.
Be sure not to modify any other files. Doing so will result in point deductions that the tester will not reflect. You may feel free to modify the files for the tester however you like though for debugging purposes (namely list suite.c).
All #include directives have been included for you. Do not add any more includes. Doing so will result in point deductions that the tester will not reflect.
1.1 Dependencies
There are some dependencies for running the tests.
If you are using Docker, re-run cs2110docker.sh to stop the old container, download updates to the image (which include these dependencies), and restart the container.
If you are using a VM, run
$ sudo apt install build-essential gdb valgrind pkg-config check
1.2 Linked List Implementation
data pointer references what is being stored, and the next pointer references the next list node along the chain. Do not change the definition of the list node struct. Do not use sentinel or dummy nodes in your list.
3 Background
3.1 Linked Lists, Continued
A linked list is an ordered list of nodes. Each node in the list is comprised of two consecutive values in memory: a pointer to the next node and a pointer to the data being stored by that node. Since both of these values are addresses, each value is 64 bits or 8 bytes on a 64-bit architecture.
Consider an example list with a head (starting node) at address x4000.
Address | Contents | Comments
---------+----------+--------------
x4000 |
x4010 | Node 1: next
x4008 |
x0035 | Node 1: data
x4010 |
x4030 | Node 2: next
x4018 |
x0101 | Node 2: data
x4020 |
x0000 | Node 4: next
x4028 |
x9040 | Node 4: data
x4030 |
x4020 | Node 3: next
x4038 |
x7000 | Node 3: data
Observe that Node 1 points to Node 2 (at address x4010). Node 2 points to Node 3 (at address x4030). Node 3 points to Node 4 (at address x4020). Finally, Node 4 points to address x0000 (i.e. NULL), signaling that this node is the tail node at the end of the list!
Also notice that consecutive nodes need not be next to each other in memory. This quality is what makes it easy to dynamically allocate additional nodes without needing to reallocate the entire list when we need more space.
3.2 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 person structs from the list and frees the nodes that contained pointers to the person structs. Finally, you must free the list structure yourself so that no memory is leaked by your function.
3.3 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.
Your process for doing this 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.
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.
3.4 Makefile
We have provided a Makefile for this t 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 the tests without valgrind or gdb: make run-tests
3. To run your tests with valgrind: make run-valgrind
4. To debug a specific test with valgrind: make TEST=test name run-valgrind
5. 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.
Be sure not to modify any other files. Doing so will result in point deductions that the tester will not reflect. You may feel free to modify the files for the tester however you like though for debugging purposes (namely list suite.c).
All #include directives have been included for you. Do not add any more includes. Doing so will result in point deductions that the tester will not reflect.
1.1 Dependencies
There are some dependencies for running the tests.
If you are using Docker, re-run cs2110docker.sh to stop the old container, download updates to the image (which include these dependencies), and restart the container.
If you are using a VM, run
$ sudo apt install build-essential gdb valgrind pkg-config check
1.2 Linked List Implementation
data pointer references what is being stored, and the next pointer references the next list node along the chain. Do not change the definition of the list node struct. Do not use sentinel or dummy nodes in your list.
3 Background
3.1 Linked Lists, Continued
A linked list is an ordered list of nodes. Each node in the list is comprised of two consecutive values in memory: a pointer to the next node and a pointer to the data being stored by that node. Since both of these values are addresses, each value is 64 bits or 8 bytes on a 64-bit architecture.
Consider an example list with a head (starting node) at address x4000.
Address | Contents | Comments
---------+----------+--------------
x4000 |
x4010 | Node 1: next
x4008 |
x0035 | Node 1: data
x4010 |
x4030 | Node 2: next
x4018 |
x0101 | Node 2: data
x4020 |
x0000 | Node 4: next
x4028 |
x9040 | Node 4: data
x4030 |
x4020 | Node 3: next
x4038 |
x7000 | Node 3: data
Observe that Node 1 points to Node 2 (at address x4010). Node 2 points to Node 3 (at address x4030). Node 3 points to Node 4 (at address x4020). Finally, Node 4 points to address x0000 (i.e. NULL), signaling that this node is the tail node at the end of the list!
Also notice that consecutive nodes need not be next to each other in memory. This quality is what makes it easy to dynamically allocate additional nodes without needing to reallocate the entire list when we need more space.
3.2 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 person structs from the list and frees the nodes that contained pointers to the person structs. Finally, you must free the list structure yourself so that no memory is leaked by your function.
3.3 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.
Your process for doing this 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.
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.
3.4 Makefile
We have provided a Makefile for this t 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 the tests without valgrind or gdb: make run-tests
3. To run your tests with valgrind: make run-valgrind
4. To debug a specific test with valgrind: make TEST=test name run-valgrind
5. 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.
1 file (135.7KB)
