Use these debugging warmup exercises to practice with the tools and skills that will arm you to successfully manage the tricky aspects of linked lists. Unsurprisingly, the common pitfalls for linked lists come down to mistakes with memory and pointers. These are difficult concepts in C++ and you can never get too much practice!
Using SimpleTest to find memory leaks
A memory leak is created when a program allocates memory using new but does not call delete to deallocate the memory when finished with it. A leak is analogous to forgetting to check out of your hotel room, causing the hotel staff to believe your room is still occupied and not reassign it to a new customer.
Unlike a memory error which can cause a program to crash or behave erratically, a memory leak has fairly benign consequences. The only side effect of a memory leak is that the leaked memory is not available for recycling. If a program had many leaks and each was a large amount of memory, it could eventually exhaust all of the system memory and be unable to proceed further, but this only happens in extreme cases.
If you use a tool such as Activity Viewer or top to watch a long-running application, you'll likely see its memory usage creep upwards over time, in some part due to unresolved memory leaks. Even professionals slip up sometimes! Memory leaks are endemic to any program written in a language where the programmer is responsible for explicit deallocation (as opposed to a language such as python which has automatic garbage collection. Oh those halcyon days of CS106A)
Tracking down memory leaks by hand is painstaking and difficult; almost all developers rely on memory debugging tools such as Valgrind or memcheck. Our SimpleTest framework also has a basic facility to count the number of new and delete calls for a particular type and reports when the two counts don't match up to identify leaks.
To enable allocation counting for a specific type, you add the macro TRACK_ALLOCATIONS_OF within the type declaration, like this:
struct ListNode {
int data;
ListNode *next
TRACK_ALLOCATIONS_OF(ListNode);
};
Once ListNode is configured in this way, its allocation and deallocations are tracked by SimpleTest. Each test case counts the new and delete operations and any mismatch in the counts is flagged as part of the test result.
Observing a memory leak
There are four provided test cases in warmup.cpp that test allocation counting on ListNodes. Examine the code in each of these test cases and match the new/delete calls. If you believe there is a mismatch, categorize the problem as a memory error (dangerous) or a memory leak (more benign). Run the cases and observe the test results as reported by SimpleTest to confirm your understanding is correct.
When working with test cases that are known to have planted errors, it is best to comment them out after you have finished examining them. In this way you can proceed onto other tests without that corruption/interference of those planted errors.
Answer the following questions in short_answer.txt:
Accessing deallocated memory
The warmup.cpp file has a provided function badDeallocate that attempts to deallocate the nodes of a linked list, but has a bug lurking within.
void badDeallocate(ListNode* list)
{
while (list != nullptr) {
delete list;
list = list->next; // BAD: accesses next field from deallocated memory
}
}
After deallocating the memory for the ListNode pointed to by list, the subsequent statement accesses that deallocated memory to read the list->next field. This is clearly a wrong thing to do, but even this blatant mistake may manage to pass unnoticed and unpunished. Why is that? Remember how Chris reminds us in lecture that delete doesn't really "delete" anything? You use delete to tell the system that you are done using that memory. delete marks the memory as available for recycling, but doesn't wipe the contents or make the memory inaccessible.
Continuing the hotel room analogy, if you were to rush back to the hotel room you just checked out of to grab your forgotten toothbrush, well, you just might get away with it. But what is going to happen if housekeeping has already come and swept the room, or even worse, the room has been re-assigned to a new customer who will be most surprised when you come barging in? Being sloppy about accessing deallocated memory is not a habit you want to adopt!
Observing a memory error
The warmup.cpp file has two test cases for badDeallocate. The first deallocates a list of 3 elements. Despite the memory error, this test case will likely "pass" on many systems. The second test case does many trials of deallocating much longer lists. By repeating the same mistake many more times, it becomes more likely that one will trigger a more visible consequence. Run the tests a few times as-is and note if you see any consequences of the bug. Running the exact code unchanged a second time can sometimes produce different result than the previous run. If you see no consequences, try doubling the number of trials or increasing the lengths of the list. On your system, you may find it easy to trigger the bug or completely impossible. These experiments will demonstrate that getting definitive evidence of a memory error can be elusive indeed!
Answer the following question in short_answer.txt:
The next time you are puzzling how it makes no sense for code to fail only one isolated test when all others pass all test cases, remember back to this result and how slippery memory errors can be. Your finest testing and debugging tactics will come in handy.
Debugging a segmentation fault
A common experience when debugging code that uses pointers is the dreaded Segmentation Fault. This is a fatal error or crash that will stop your program immediately. A segmentation fault indicates that the program attempted to access an invalid address, i.e. tried to read from or write to a memory location that cannot be accessed. A segmentation fault is a symptom of the bug, but it is not the bug itself. The bug is that your program uses an invalid address, and that bug causes a crash. You must work backwards from the symptom to figure how and why you ended up with that invalid address so you can correct the bug.
One frustrating thing about a segmentation fault is that the presentation can vary because the memory error itself confuses the system/debugger. In the best of situations, the program halts and provides a clear and descriptive error message, perhaps via a alert dialog or a text message in the console. In some situations, a program might suddenly stop but be silent on the error message. In another, the program may exit and its windows disappear, leaving no trace of what happened. In yet another, the program might lock up, as though stuck in an infinite loop.
To complicate matters even further, running the program under the debugger may produce a different result than running outside the debugger. Even running the same program twice in a row in the exact same context can produce different results. Working with memory errors can cause you to doubt your own eyes and sanity. We want you to be aware that any and all of the above may be part of the landscape when it comes to memory woes.
One possible root cause for an address to be invalid is when a pointer was not properly initialized. We will have you debug such an example so you can observe a segmentation fault in action.
Uncomment the "Segmentation fault" test case at the end of warmup.cpp and rebuild. Set a breakpoint in this test case and run the program in Debug mode.
The test code allocates memory for a new ListNode and stores that address into the pointer variable p. p now holds that address of memory where the ListNode is stored. In the Variables panel, the value of p is shown as a longish hexadecimal number prefixed with @0x. Look for it now.
Turn down the triangle of p to see the two fields in the ListNode: data and next. Neither of these fields were initialized so their contents are unpredictable/garbage.
Let's observe the consequence of using a garbage integer value. Step through the statement that increments p->data and watch the value of data update. What is the value before and after? Adding to a garbage value doesn't make much sense but doesn't appear to cause the program to halt or fail.
Not all garbage is created equal. The pointer variable p->next is also not initialized. Accessing a garbage address can cause a runtime error. An uninitialized/garbage address could happen to be a valid location, but more often that not, it won't be. It is somewhat analogous to picking up your phone and dialing digits at random - does the call go through and you talk to a stranger or do you get an error because the number is out of service? Either way, the random dialing was a bad idea, but the observed consequence can differ depending on your "luck". This variation adds a layer of challenge to debugging memory errors.
Use the Variables pane to see the garbage address stored in the p->next field. Does it look like a valid address (compare its value to the valid address stored in p)?
Step though the statement that attempts dereference p->next . This dereference will likely cause a segmentation fault. The debugger should halt the program. It may produce an alert or error message or might stay mum. After a segmentation fault, the debugger will refuse to step further. The yellow arrow in the editor pane will indicate the offending line that caused the crash and you can read the values in the Variables pane to see the invalid address. These are the clues that help you diagnose the symptom.
Observing a segmentation fault
A segmentation fault might present itself differently depending on the context:
Answer the following question in short_answer.txt:
Recognizing a segmentation fault can itself be tricky, but this is only the first step. From there, you must work backwards from the symptom to figure how and why you ended up with that invalid address so you can correct the bug. There is no simple one-size-fits-all fix for segmentation faults; resolving one is an adventure that will draw upon your finest debugging skills. Drawing pictures of the memory and its connections is often a good start. Tracing the execution by using the debugger to step and observe the state may help confirm whether your code is doing what you intend.
One of the advantages of a linked list over an array is its flexibility and efficiency when rearranging elements. Unlike arrays, which occupy contiguous memory locations and require shuffling (remember how arduous it was to shift all the elements over by one when implementing PQSortedArray?), reordering an element in a linked list is simply a matter of rewiring a few pointers. A task like sorting, which rearranges many elements in the collection, can have an distinct advantage when operating on a linked list instead of an array.
For this task, you are to write the function
void sort(ListNode*& list)
which rearranges the nodes of list into sorted order. You have the choice of implementing either the Mergesort or the Quicksort algorithm to do the sort.
In addition to implementing the sort function, you will write any helper functions you need along with test code that helps you test your work.
Sorting algorithms
Rather than repeat the background information on sorting algorithms, please review the lecture for the explanation and diagrams of the sorting algorithms. The rest of this handout assumes familiarity with that content.
Both Mergesort and Quicksort are examples of recursive "divide and conquer" algorithms. Each divides the input list into two sublists, recursively sorts the sublists, and then joins the sorted sublists into one combined whole. The two algorithms differ in what work is required to divide into sublists and what needs to happen in the join step. Mergesort is referred to as "easy-split-hard-join" because it has a simple division step and a complex join. Quicksort is "hard-split-easy-join" because the bulk of its work goes into the complex division step with a trivial join to follow.
Mergesort
The classic Mergesort algorithm divides the input list into two sublists, recursively sorts the two lists, and applies a binary merge to join the two sorted lists into one combined whole. Linked lists are a natural for this sort. Each level of the recursion moves elements to one of two sides and later rejoins the sides, the flexible wiring of the list supports this with ease. Also note that the existing nodes can re-distributed into sublists. This is another advantage over the array/vector version which copies the sublists over and over again.
In the split step, rather than separating into front half and back half, we want you to do an even-odd distribution, where every other element goes to one side. The 1st, 3rd, 5th, elements are placed in one sublist, the 2nd, 4th, and so on are placed in the other. The order that the elements are placed into the sublist is of no consequences, you may do whatever is most convenient for your algorithm.
The merge operation must be implemented iteratively. Although it is possible and even quite elegant to solve recursively, the cost of one stack frame per element being processed is much too high to bear and the function would be unable to handle larger lists. For similar reasons, the divide step must also be implemented iteratively.
Quicksort
The classic Quicksort algorithm divides the input list into sublists that are less than or greater than a chosen pivot. After recursively sorting the sublists, they are joined in sequence.
Linked lists also work well for Quicksort. Distributing the elements into sublists is a more straightforward task that the contortions required to rearrange those same elements within an array.
The partition step is where a lot of the magic happens. Choose the first element of the list as the pivot. Divide the elements into three sublists: those elements that are strictly less than the pivot, those that are equal to the pivot, and those that are strictly greater. Note that the existing nodes are re-distributed into the sublists, there is no need to allocate new nodes or make copies. The order that the elements are placed into the sublist is of no consequences, you may do whatever is most convenient for your algorithm.
The less and greater sublists are recursively sorted. The sublist of elements equal to the pivot is already trivially sorted.
The join step attaches the three sorted sublists in one combined list by adding the missing links need to concatenate them.
As noted above, an operation such as partition that examines every element, must be implemented iteratively, not recursively. This is necessary to ensure you can process larger lists without exhausting the call stack.
Notes for either sort
Answer the following questions in short_answer.txt:
Testing
For this assignment, you will take on much greater responsibility for writing your own test cases. The only provided test case is a sample time operation to get you started.
Although the overall goal is that your sort function work according to its top-level specification, e.g. confirming the list is rearranged into sorted order, test cases that operate at top-level will not helpful early in your development.
Instead, you should start by constructing student tests of your own that can be used to test your helper functions. For example, after you have written your split or partition helper, add test cases that specifically exercise the helper to verify its correctness. Similarly the merge or join helper can be tested on its own. Once you have confirmed the correctness of your helpers, you can move on to testing their use in the context of the sort operation.
Another recommendation is that you consider writing test helper functions that translate from Vector to linked list or vice versa, or perhaps compare a linked list to a Vector. This allows you to construct test cases in convenient form as Vector and translate/compare to linked list as needed. If you are looking for guidance on how to do so, we highly recommend checking out the testing code used for this week's section problems.
Some test cases to be sure that you include in your test suite would be:
You should also take care to avoid memory leaks in your tests by properly deallocating all ListNodes used temporarily during a test. Although your sort function does not allocate nor deallocate nodes, your test cases may need to allocate and deallocate memory for testing purposes. Any memory that is allocated for the test case should be deallocated at the end of the test case.
An important component of the grading for this assignment will be the quality of your test cases. Show us that you have learned from the example we have set in earlier assignments with our provided tests!
An important component of the grading for this assignment will be the quality of your test cases. Show us that you have learned from the example we have set in earlier assignments with our provided tests!
Timing your sort
Both Mergesort and Quicksort should run in O(NlogN) time in the common case. Our Vector class uses the C++ std::sort to sort its internal array which is also an O(NlogN) algorithm. You can prepare the same input sequence once in array form and again as a linked list, and then time the operation of Vector sort versus your linked list sort on that sequence to compare the relative performance of sorting linked lists versus array. What do you predict will be the outcome of the great sorting race? Try it and find out!
Answer the following questions in short_answer.txt:
Advice
Extensions
Here are some ideas for further exploration of list sorting:
Some of these are more suited to linked lists than others, so do some background research on the algorithm before deciding whether it would be a good one to tackle.
Where am I?
You are trapped in a labyrinth, and your only hope of escape is to cast the magic spell that will free you from its walls. To do so, you will need to explore the labyrinth to find three magical items:
Once you have all three items, you can cast the spell to escape to safety.
A pointer labyrinth
This is, of course, no ordinary labyrinth. It's a pointer labyrinth. It is a linked arrangement of locations defined as a MazeCell:
struct MazeCell {
string contains; // Either "", "Spellbook", "Potion", or "Wand"
MazeCell *north; // The cell to the north, or nullptr if can't go north.
MazeCell *south; // The cell to the south, or nullptr if can't go south.
MazeCell *east; // The cell to the east, or nullptr if can't go east.
MazeCell *west; // The cell to the west, or nullptr if can't go west.
};
Figure: see image.
This diagram shows an example 4 4 labyrinth. The starting location is marked with a smiley face and the location of the three items with similarly cute emojis. The MazeCell containing the smiley face has north, south, east, and west pointers pointing to the MazeCell located one step in each of those directions. The MazeCell containing the book has north, east, and west pointers set to nullptr, and only its south pointer would point to another MazeCell (specifically, to the cell in the bottom-left corner)
Each MazeCell has a field named contains that indicates the item at that location. If the cell contains no item, then its contains field will hold the empty string. A cell that holds the Spellbook, Potion, or Wand item would contain the string "Spellbook", "Potion", or "Wand", respectively.
Once dropped into this labyrinth at the starting location, you can roam around to find the items you need to cast the escape spell. There are many paths you can take; here are three of them:
Each path is represented as a sequence of letters (N for north, W for west, etc.) that, when followed from left to right, trace out the steps. For example, assuming that we start from the smiley-face in the diagram, the first sequence steps east, then south (getting to the cell with the Potion), then north, then west, etc.
Trace these paths through the labyrinth and confirm that you understand how each is a legal path that gathers all three needed items.
Confirm path to freedom
Your first task is to write a function that, given a starting cell and a path, checks whether that path is legal and picks up all needed items. In the file labyrinth.cpp, implement the function
bool isPathToFreedom(MazeCell *start, string path, Set< string> needed)
This function takes as input a pointer to a MazeCell, a string made purely from the characters 'N', 'S', 'E', and 'W', and a Set of items, expressed as strings. If the path trace a valid sequence of steps that gather all of the needed items, the function returns true, false otherwise.
A path successfully escapes if:
You can assume that start is not nullptr. However, if a step attempts to walk through a nullptr link, such as trying move E from the cell containing the wand in the above example, the function should stop and return false. In particular, your function should not crash if the path tries to traverse a link that does not exist. If the input path contains an invalid character (any character other than 'N', 'S', 'E', or 'W'), use the error() function to report an error.
Notes
Testing
Escape from your personal labyrinth
Your next task is to escape from a labyrinth that's specifically constructed for you. The starter code provides a function that that build you a personalized labyrinth. By "personalized" we mean that no one else in the course is going to have the exact same labyrinth as you. Your job is to figure out a path through your labyrinth that picks up all the three items, allowing you to escape.
At the top of labyrinth.cpp are two constants marked with a "TODO" message. The first one, kYourName, is a spot for your name. Edit this constant so that it contains your name. The second constant kPathOutOfNormalMaze needs to be assigned to a path that escapes your labyrinth. Your job will be to find that escape path.
The last provided test cases tests the escape from your personal labyrinth. This test case generates the custom labyrinth for the kYourName constant and confirms that your kPathOutOfNormalMaze is a valid path to escape it. It is your job to come up with that path.
Debugging linked structures
To find that path, you will use your old friend the debugger! Set a breakpoint on the test case for your personal labyrinth escape. Run the program under the debugger. When stopped at the breakpoint, look to the Variables pane to see the state of the local variables. The variable start is a pointer to the MazeCell where we've dropped you into the labyrinth. Clicking the dropdown triangle in the debugger window will let you view the contains field of start (itll be empty), as well as the four pointers leading out of the cell.
Depending on your labyrinth, you may find yourself in a location where you can move in all four cardinal directions, or you may find that you can only move in some of them. The pointers in directions you can't go are all equal to nullptr, which will show up as 0x0 in the debugger window. The pointers that indicate directions you can go will all have dropdown arrows near them. Clicking one of these arrows will show you that the neighbor cell. You can navigate further by choosing one of its dropdown arrows, or you could back up to the starting cell and explore in other directions. Its really up to you!
Draw a lot of pictures. Grab a sheet of paper and map out your labyrinth you're in. Theres no guarantee where you start - you could be in the upper-left corner, dead center, etc. The items are scattered randomly, and youll need to seek them out. Once youve mapped it out, work out the steps in your escape path and assign those steps as string to the constant kPathOutOfNormalMaze, then see if you pass the escape test. If so, fantastic! Youve escaped! If not, you have lots of options. You could step through your isPathToFreedom function to see if one of the letters you entered isnt what you intended and accidentally tries to move in an illegal direction. Or perhaps the issue is that you mis-drew the map of your personal labyrinth and youve ended up somewhere without all the items. You could alternatively set the breakpoint at the test case again and walk through things a second time, seeing whether the diagram of the labyrinth you drew was incorrect.
To summarize, here's what you need to do:
Advice
Moving on
At this point, you have a good command of how to use the debugger to examine linked structures. You know how to recognize a null pointer, how to manually follow links between objects, and how to reconstruct the shape of a linked data structure. We hope you find these skills useful as you continue to write code that works on linked lists and other linked structures!