labs/lab02/index.html

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
  <meta charset="utf-8" />
  <meta name="generator" content="pandoc" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
  <title>PDR: Laboratory 2: Linked Lists</title>
  <style>
    code{white-space: pre-wrap;}
    span.smallcaps{font-variant: small-caps;}
    span.underline{text-decoration: underline;}
    div.column{display: inline-block; vertical-align: top; width: 50%;}
    div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
    ul.task-list{list-style: none;}
    .display.math{display: block; text-align: center; margin: 0.5rem auto;}
  </style>
  <link rel="stylesheet" href="../../markdown.css" />
  <!--[if lt IE 9]>
    <script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
  <![endif]-->
</head>
<body>
<h1 id="pdr-laboratory-2-linked-lists">PDR: Laboratory 2: Linked
Lists</h1>
<p><a href="../index.html">Go up to the Labs table of contents
page</a></p>
<h3 id="objective">Objective</h3>
<p>This laboratory introduces you to some advanced class development in
C++, creating and using iterators, manipulating pointers, and linked
data structures. It also addresses some issues involving testing and
software development.</p>
<h3 id="background">Background</h3>
<p>The linked list is a basic data structure from which one can
implement stacks, queues, sets, and many other data structures. Lists
may be singly- or doubly-linked. In this lab we will implement a
doubly-linked list.</p>
<h3 id="tutorial">Tutorial</h3>
<p>In this lab, you will have to make a choice as to which debugger to
use; this will affect which tutorial you carry out. You can choose the
LLDB debugger (you would then complete <a
href="../../tutorials/02-lldb/index.html">Tutorial 2: LLDB</a>) or the
GDB debugger (you would then complete <a
href="../../tutorials/02-gdb/index.html">Tutorial 2: GDB</a>). The
source code provided for each tutorial is exactly the same, and the
deliverable (i.e., what you turn in) is likewise the exact same.</p>
<p>The LLDB debugger is preferred as it was built with the
<code>clang++</code> compiler that we are using; however, the GDB
tutorial is offered if LLDB doesn’t work for you.</p>
<p>Just remember which one you choose, as you will end up using that
debugger throughout this course. And if you ever have to switch between
them, you can use our <a href="../../docs/gdb_vs_lldb.html">GDB vs
LLDB</a> page to see the (relatively few) commands that are different
between the two.</p>
<p>Ultimately, this is a low stress choice. Choose LLDB, and only switch
over to GDB if you run into issues.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ul>
<li>Pointers and Linked Lists sections on the <a
href="../../docs/readings.html">Readings</a> page</li>
<li>The <a
href="http://umich.edu/~eecs381/generalFAQ/Debugging.html">Debugging FAQ
from UMich</a></li>
</ul>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Finish the subset of methods that allow you to use the test harness
(see requirements in detailed write-up below).</li>
<li>Files to download: <a href="List.h.html">List.h</a> (<a
href="List.h">src</a>), <a href="ListNode.h.html">ListNode.h</a> (<a
href="ListNode.h">src</a>), <a href="ListItr.h.html">ListItr.h</a> (<a
href="ListItr.h">src</a>), <a href="ListTest.cpp.html">ListTest.cpp</a>
(<a href="ListTest.cpp">src</a>)</li>
<li>Files to submit: ListNode.h/cpp, ListItr.h/cpp, List.h/cpp,
ListTest.cpp</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Use the debugger to find and correct the errors in debug.cpp in part
II of the debugger tutorial</li>
<li>Continue to work on your List and debug any issues with the debugger
as necessary</li>
<li>Files to download: <a
href="../../tutorials/02-lldb/prog1.cpp.html">prog1.cpp</a> (<a
href="../../tutorials/02-lldb/prog1.cpp">src</a>), <a
href="../../tutorials/02-lldb/debug.cpp.html">debug.cpp</a> (<a
href="../../tutorials/02-lldb/debug.cpp">src</a>)</li>
<li>Files to submit: debug.cpp</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Make sure your development environment is set up to be able to test
for memory leaks, as described in the post-lab section</li>
<li>Finish the implementation of your List and ensure it is free of any
memory errors</li>
<li>Files to download: no additional files beyond the pre-lab and
in-lab</li>
<li>Files to submit: ListNode.h/cpp, ListItr.h/cpp, List.h/cpp,
ListTest.cpp</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<h3 id="code-description">Code Description</h3>
<p>Linked lists are described in the online <a
href="../../docs/readings.html">Readings</a>.</p>
<p>You will be implementing a doubly linked list, and you will be using
“dummy” nodes as well. You will want two dummy nodes – <strong>one for
the head</strong> and <strong>one for the tail</strong>. A benefit of
doing your implementation using dummy nodes is that there are fewer
special cases to check for – for example you never have to update the
head pointer on an insertBefore() or a remove() – the head pointer
always points to the dummy header node. A dummy tail pointer would help
out in the same respect. The downside is that you use two extra “empty”
nodes.</p>
<p>For this lab you will need to implement three classes:</p>
<ul>
<li>ListNode</li>
<li>List</li>
<li>ListItr</li>
</ul>
<p>For the pre-lab however, you are only required to implement a subset
of the required methods. For your pre-lab to get full credit, the
following methods must be working:</p>
<ol type="1">
<li>All of ListNode (so…the constructor)</li>
<li>List constructor</li>
<li><code>List::insertAtTail</code></li>
<li>All of ListItr</li>
<li><code>List::first</code></li>
<li><code>List::size</code></li>
<li><code>printList</code> (forward, not backward)</li>
</ol>
<p>For simplicity we will just create a list that holds integers (your
code could easily later be templated (i.e. made generic) to allow it to
contain objects of other types). You must not modify any of the provided
declarations in the header files, though you may add onto the header
files as you see fit.</p>
<h3 id="uml-diagram">UML Diagram</h3>
<p>Below is a UML diagram showing how these classes interact with each
other.</p>
<figure>
<img src="list-diagram.png" alt="UML diagram" />
<figcaption aria-hidden="true">UML diagram</figcaption>
</figure>
<p>This diagram shows a list containing two elements, the integers 3 and
7. Note that there are more methods in the List and ListItr classes than
what is shown above. The head and tail pointers in the List class point
to dummy nodes – they are put there to make inserting elements into the
list easier. It doesn’t matter what the value of the dummy nodes is set
to, as it won’t be used. Each ListNode points to the nodes before and
after it (although the dummy nodes each have one pointer pointing to
NULL).</p>
<p>Thus, our doubly linked list will have only one List object and many
ListNode objects (2 more than the number of elements in the list). A
ListItr is a separate object, which points to one element in the list
(possibly a dummy node). As you call the various methods in ListItr to
move the iterator forward and backward, the node that it points to will
change.</p>
<h3 id="listnode">ListNode</h3>
<p>A ListNode contains an integer value, as well as next and previous
pointers to other ListNodes. View the <a
href="ListNode.h.html">ListNode.h</a> (<a href="ListNode.h">src</a>)
code for details.</p>
<h3 id="list">List</h3>
<p>This class represents the list data structure containing ListNodes.
It has a pointer to the first (head) and last (tail) ListNodes of the
list, as well as a count of the number of ListNodes in the List. View
the <a href="List.h.html">List.h</a> (<a href="List.h">src</a>) code for
details.</p>
<h3 id="listitr">ListItr</h3>
<p>A ListItr maintains a pointer to a current position in a List to
allow for easy traversal through the List. View the <a
href="ListItr.h.html">ListItr.h</a> (<a href="ListItr.h">src</a>) code
for details.</p>
<h3 id="test-harness">Test Harness</h3>
<p>We have provided a test harness for testing your whole
implementation: <a href="ListTest.cpp.html">ListTest.cpp</a> (<a
href="ListTest.cpp">src</a>) <strong><em>Your List must work with this
test harness.</em></strong></p>
<h3 id="hints">Hints</h3>
<p>There are a few things that always cause students some headache.
We’ve tried to explain some of them here, in an effort to lessen the
frustration it causes.</p>
<h4 id="getting-started">Getting started</h4>
<p>To start, create all three .cpp files (List.cpp, ListNode.cpp,
ListItr.cpp) and include the relevant .h files. Fill the files with
empty method bodies (with a dummy return value for non-<code>void</code>
methods) and get that to compile. Then start implementing <em>one method
at a time, testing as you go</em>.</p>
<p>Here are the functions you need to have implemented for this pre-lab,
which will allow you to start using the ListTest harness (listed in
suggested implementation order):</p>
<ol type="1">
<li>All of ListNode (so…the constructor)</li>
<li>List constructor</li>
<li><code>List::insertAtTail</code></li>
<li>All of ListItr</li>
<li><code>List::first</code></li>
<li><code>List::size</code></li>
<li><code>printList</code> (forward, not backward)</li>
</ol>
<h4 id="segmentation-faults">Segmentation faults</h4>
<p>When beginning to test your code, chances are your program will crash
unexpectedly with a message similar to <code>Segmentation fault (core
dumped)</code>, commonly referred to as a <em>segfault</em>. Get
prepared to see these often throughout the course, as unlike other
programming languages like Java, C++ does not give any extra debugging
information on a crash. In order to determine where and why your program
is crashing, run your code through the debugger and look at the
backtrace. Segfaults generally indicate that you are trying to
dereference a NULL or invalid pointer, so those are good things to look
out for.</p>
<h4 id="the-constructor">The constructor</h4>
<p>By the time the constructor finishes, we should have a functioning
(but empty) list. This means that <code>head</code> and
<code>tail</code> need to be set appropriately! What should they point
to if the list is empty?</p>
<p>Make sure you are initializing the variables that are specified in
the .h file and <strong>not</strong> declaring new variables that have
the same name as those in the header file. Take a look back at
lifecycle.cpp’s constructors from Lab 1 if you need a refresher.</p>
<h4 id="the-copy-constructor-and-the-copy-assignment-operator">The copy
constructor and the copy assignment operator</h4>
<p>The code for the copy constructor and the <code>operator=()</code>
method in the List class are shown below. Although we are providing you
with this code, you must understand how it works by the end of the lab,
as you will have to implement these types of methods on future labs and
exams. It also might help you with some of the other methods! (Hint
hint.)</p>
<pre><code>// Copy constructor
// Called when the code looks something like List list2 = list1;
// (In other words, it is called when you are trying to construct a **new** list from an existing one)
List::List(const List&amp; source) {
    head=new ListNode();
    tail=new ListNode();
    head-&gt;next=tail;
    tail-&gt;previous=head;
    count=0;

    // Make a deep copy of the list
    ListItr iter(source.head-&gt;next);
    while (!iter.isPastEnd()) {
        insertAtTail(iter.retrieve());
        iter.moveForward();
    }
}

// Copy assignment operator
// Called when the code looks something like list2 = list1;
// (In other words, it is called when you are trying to set an **existing** list equal to another one)
List&amp; List::operator=(const List&amp; source) {
    if (this == &amp;source) {
        // The two are the same list; no need to do anything
        return *this;
    } else {
        // Clear out anything this list contained
        // before copying over the items from the other list
        makeEmpty();

        // Make a deep copy of the list
        ListItr iter(source.head-&gt;next);
        while (!iter.isPastEnd()) {
            insertAtTail(iter.retrieve());
            iter.moveForward();
        }
    }
    return *this;
}</code></pre>
<p>Note that these two methods are correctly implemented. However, they
depend on the other methods working properly. If you are seeing crashes
in these methods, it is likely because some of the other supporting
methods are not working properly.</p>
<h4 id="insert-methods">Insert methods</h4>
<p>When implementing the three insert functions, we have found it
helpful to draw out the pointers on paper and determine the order in
which to update the pointers <em>before</em> beginning to code the
function itself. Take the time to reason about how many next and
previous pointers you should be updating!</p>
<p>For <code>insertAfter</code> and <code>insertBefore</code>, the
ListItr you are given is already pointing to a ListNode. You should
insert the new ListNode after or before that ListNode, respectively. If
you find yourself thinking about loops or iteration, that is
unnecessary! Double-check the ListItr header file.</p>
<h4 id="find-and-remove">Find and remove</h4>
<p>Since <code>find</code> needs to return a ListItr, it might make
sense to also implement it using iterators, though that is not
required.</p>
<p>As <code>remove</code> takes in an integer rather than a ListItr, we
first need to determine whether or not that integer exists in our
list.</p>
<h4 id="makeempty-and-the-destructor">makeEmpty and the destructor</h4>
<p><code>makeEmpty</code> should clear the list of all elements
(<code>isEmpty</code> should return true after calling
<code>makeEmpty</code>). It should also make sure that <code>head</code>
and <code>tail</code> no longer point to those deleted elements (what
should they point to instead in an empty list?).<br />
Since we have been dynamically allocating ListNodes, we must also be
responsible for deleting them to ensure we do not leak memory. There are
multiple ways to iterate through the list and <code>delete</code> each
ListNode – experiment and see what makes the most sense to you.<br />
<strong>Important:</strong> once you delete a ListNode, you can no
longer reliably access any of its data, such as its <code>next</code> or
<code>previous</code> pointers! To make sure you don’t do this
accidentally, we recommend setting each ListNode to NULL as soon as you
delete it.</p>
<p>The destructor should delete <em>all</em> dynamically-allocated
memory, as we no longer need this List instance. Thus, it makes sense
that we should delete all the elements we inserted (hint: do we already
have a method for that?). However, what else do we dynamically allocate
that we need to delete?</p>
<h4 id="printlist">printList</h4>
<p>This one’s interesting becaus it’s a <em>non-member</em> function,
which means it doesn’t have access to any private variables.</p>
<p>As we’ve been using private variables heavily up until this point,
try taking a step back and looking at the bigger picture. If you can’t
use anything private, that means you’re limited to only public
methods.</p>
<p>Is there anything that helps you create a ListItr that points to the
first or last node in the List? What about a way to retrieve each node’s
value from the iterator?</p>
<p><strong>When printing out the elements of the list, separate them
with a space and use a newline after the last element. If the list
happens to be empty, just print out a newline.</strong> See the sample
output section for an example of the formatting.</p>
<h4 id="compiling">Compiling</h4>
<p>When compiling your code, you must remember to compile all of your
.cpp files in one line:</p>
<pre><code>clang++ List.cpp ListItr.cpp ListNode.cpp ListTest.cpp</code></pre>
<p>There are ways to compile these programs in pieces, but we will see
this later in the semester.</p>
<p>Linker errors are commonly caused by one of two problems:</p>
<ul>
<li><code>Undefined symbols for architecture...</code> or
<code>Undefined reference to...</code> means that you forgot to
implement some functions, or that you forgot to compile all four files
together. Here’s an example:</li>
</ul>
<pre><code>/tmp/ListTest-8ea7aa.o: In function `main&#39;:
ListTest.cpp:(.text+0x37c): undefined reference to `List::List()&#39;
ListTest.cpp:(.text+0x116d): undefined reference to `List::insertBefore(int, ListItr)&#39;
ListTest.cpp:(.text+0x1d34): undefined reference to `List::List()&#39;
clang: error: linker command failed with exit code 1 (use -v to see invocation)</code></pre>
<p>Looks like we forgot to implement the List constructor and
insertBefore!</p>
<ul>
<li><code>Duplicate symbol...</code> or <code>Multiple definition
of...</code> means that you have defined the same function more than
once. Make sure you’re only including <code>.h</code> files and that you
haven’t accidentally redefined a function somewhere. Here’s an
example:</li>
</ul>
<pre><code>/tmp/ListItr-6e3849.o: In function `List::insertBefore(int, ListItr)&#39;:
ListItr.cpp:(.text+0x120): multiple definition of `List::insertBefore(int, ListItr)&#39;
/tmp/List-2e4fcd.o:List.cpp:(.text+0x5d0): first defined here
clang: error: linker command failed with exit code 1 (use -v to see invocation)</code></pre>
<p>This time, we defined insertBefore twice – once in ListItr, and once
in List. The one in ListItr must be a mistake!</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>In order to make autograding easier, we expect you to follow the
output formats specified in these write-ups. Although the test harness
handles most of the output formatting for you, the
<code>printList()</code> method output must be written by you, and as
was mentioned above, you should print the list elements separated with a
space, following with a newline after the last element. If the list is
empty, only print out a newline. An example run is shown below to
demonstrate how your output should look. This sample output applies to
all sections of this lab.</p>
<pre><code>--------------------------------------------------
    This test harness operates with one List
    object and one ListItr object.

    Use the menu options to manipulate these
    objects.
     - - - - - -  MENU - - - - - -

        1 - Quit
        2 - New List
        3 - Show List elements
        4 - Set ListItr with first()
        5 - Set ListItr with find()
        6 - Set ListItr with last()
        7 - Move ListItr forward
        8 - Move ListItr backward
        9 - Retrieve element at ListItr
        10 - Insert element before
        11 - Insert element after
        12 - Insert element at tail
        13 - Remove element
        14 - Cardinality (size)
        15 - Copy list w/copy constructor
        16 - Copy list with operator=
        17 - Make list empty

     - - - - - - - - - - - - - - -
     Enter number of choice &gt; 2
        You have created an empty list
        Do you want to initialize it with elements? (y/n) &gt; y
            Enter elements one by one as integers.
            Any non-numeric character, e.g. #, will terminate input
    Enter first element: 1
    Enter next element: 2
    Enter next element: q

The elements in forward order: 
1 2 
     - - - - - -  MENU - - - - - -

        1 - Quit
        2 - New List
        3 - Show List elements
        4 - Set ListItr with first()
        5 - Set ListItr with find()
        6 - Set ListItr with last()
        7 - Move ListItr forward
        8 - Move ListItr backward
        9 - Retrieve element at ListItr
        10 - Insert element before
        11 - Insert element after
        12 - Insert element at tail
        13 - Remove element
        14 - Cardinality (size)
        15 - Copy list w/copy constructor
        16 - Copy list with operator=
        17 - Make list empty

     - - - - - - - - - - - - - - -
     Enter number of choice &gt; 17
The list is (forward): 1 2 
The list is (backward): 2 1 
The list was made empty (forward): 
The list was made empty (backward): </code></pre>
<p>In the example output, you can see that the list elements are printed
out separated by a space: 1 2. After the last element (2 in this case),
a newline was printed. Furthermore, when the list was made empty, only a
newline was printed out. Make sure to follow these two formatting
constrains when implementing the <code>printList</code> method,
otherwise Gradescope will not give you any credit.</p>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<p>Complete Part II of <a href="../../tutorials/02-lldb/index.html">the
tutorial</a> for this lab and submit your debugged version of debug.cpp;
we are not submitting prog1.cpp. Remember the standard identifying
header information.</p>
<p>Going forward, if you have a post-compilation problem with your
program (crash, etc.), the TAs will not help you until you have run it
through the debugger and learned all that can be learned from this. So
make sure you understand the tutorial!</p>
<p>Verify to yourself that your methods are working properly with your
linked list code using the debugger that you just learned about. If you
have not yet completed your linked list implementation, use the debugger
to help you identify the issues/problems with parts of your current
implementation. Consult with a TA if you have questions.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>For the post-lab, your goal is to submit a fully-functional version
of your doubly-linked list.</p>
<h3 id="complete-the-linkedlist-code">Complete the LinkedList code</h3>
<p>Finish any methods that you haven’t completed yet, and then move on
to checking for memory errors.</p>
<h3 id="memory-leaks-and-corruption">Memory Leaks and Corruption</h3>
<p>Even though your code might appear to work correctly, it might still
be leaking or corrupting memory!</p>
<ul>
<li>A <em>memory leak</em> occurs when you forget to deallocate some
memory that you dynamically allocated earlier, which causes your program
to hold onto that memory forever until it exits!</li>
<li><em>Memory corruption</em> occurs when your code attempts to access
some memory address that it does not have access to, for example,
attempting to read or write to a previously-deleted pointer. C++ will
blindly dereference a pointer without checking its validity. Clearly,
this can cause your program to do unexpected things!</li>
</ul>
<p>These types of errors can cause your host machine to run out of
memory and crash, or edit some other file that your program shouldn’t
have access to! We will be checking that your code does not contain any
memory errors because of their potential severity.</p>
<p>If you are using Mac OS X (and ONLY if you are using Mac OS X), then
you will need to run the following commands (the Linux VirtualBox image
is all set up to do this properly):</p>
<pre><code>/usr/bin/ruby -e &quot;$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)&quot;
brew install llvm
PROFILE_FILE=$(if [[ -n $ZSH_VERSION ]]; then echo ~/.zshrc; else echo ~/.bash_profile; fi)
echo &#39;ASAN_OPTIONS=detect_leaks=1\nexport PATH=&quot;/usr/local/opt/llvm/bin:${PATH}&quot;&#39; &gt;&gt; $PROFILE_FILE
source $PROFILE_FILE</code></pre>
<p>Now you can compile your code with <a
href="https://clang.llvm.org/docs/AddressSanitizer.html">AddressSanitizer</a>
enabled:</p>
<pre><code>clang++ List.cpp ListItr.cpp ListNode.cpp ListTest.cpp -fsanitize=address -fno-omit-frame-pointer -g</code></pre>
<p>The flags are the following:</p>
<ul>
<li><code>-fsanitize=address</code> turns on AddressSanitizer, which
ensures that your code never attempts to reference deleted memory or
memory that you do not have access to (i.e., it checks for invalid
addresses). It also enables LeakSanitizer, which ensures that anything
that is dynamically allocated is also deallocated.</li>
<li><code>-fno-omit-frame-pointer</code> helps us obtain better stack
traces, so we include it just in case.</li>
<li>We use the <code>-g</code> flag from earlier to indicate that we
want to include debugging information such as line numbers.</li>
</ul>
<p>Run the executable with <code>./a.out</code> as usual, but make sure
you are not running it in the debugger – AddressSanitizer is
incompatible with debuggers.</p>
<p>AddressSanitizer will <strong>immediately crash upon any invalid
behavior</strong>. This is helpful because AddressSanitizer detects when
we try to use addresses that we do not control, and thus, we have no
idea what will happen when we use them! AddressSanitizer crashes the
program because there is no guarantee of what will happen next. If this
happens, carefully inspect the stack trace, attempt to fix the error,
and recompile.</p>
<p>Here’s an example of an AddressSanitizer crash:</p>
<pre><code>==28315==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000003a8 at pc 0x000000519188 bp 0x7ffff83e7910 sp 0x7ffff83e7908
READ of size 8 at 0x6030000003a8 thread T0
    #0 0x519187 in List::makeEmpty() /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/List.cpp:68:20
    #1 0x51db77 in main /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/ListTest.cpp:446:23
    #2 0x7f07bba91b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310
    #3 0x41bbe9 in _start (/mnt/c/Users/Winston/Documents/GitHub/computer-science/cs2150/labs/lab-2/postlab/a.out+0x41bbe9)

0x6030000003a8 is located 8 bytes inside of 24-byte region [0x6030000003a0,0x6030000003b8) freed by thread T0 here:
    #0 0x514dc8 in operator delete(void*) (/mnt/c/Users/Winston/Documents/GitHub/computer-science/cs2150/labs/lab-2/postlab/a.out+0x514dc8)
    #1 0x51915e in List::makeEmpty() /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/List.cpp:67:3
    #2 0x51db77 in main /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/ListTest.cpp:446:23
    #3 0x7f07bba91b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310

previously allocated by thread T0 here:
    #0 0x514050 in operator new(unsigned long) (/mnt/c/Users/Winston/Documents/GitHub/computer-science/cs2150/labs/lab-2/postlab/a.out+0x514050)
    #1 0x518bf8 in List::insertAtTail(int) /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/List.cpp:111:22
    #2 0x51bc1d in main /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/ListTest.cpp:121:27
    #3 0x7f07bba91b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310

---snip---</code></pre>
<p>Here, we are trying to use a pointer after it has been deleted.<br />
The first stack trace shows where we try to use it – in this case, in
<code>List::makeEmpty()</code> on line 68, column 20.<br />
The second stack trace shows where we deleted the pointer – right before
we used it, on line 67.<br />
The third stack trace is generally less useful, but shows where we
allocated memory in the first place.</p>
<p>After fixing all of the bugs AddressSanitizer caught, we can move on
to LeakSanitizer, which will print out any leaks that it detected when
the program exits. If you exit and there is no extra output,
congratulations! That means your program is leak-free.</p>
<p>Otherwise, you can look at the stack trace to see what memory you are
leaking. Here is an example of a List implementation that forgets to
delete <code>head</code> and <code>tail</code> in the destructor:</p>
<pre><code>==28454==ERROR: LeakSanitizer: detected memory leaks

Indirect leak of 48 byte(s) in 2 object(s) allocated from:
    #0 0x514050 in operator new(unsigned long) (/mnt/c/Users/Winston/Documents/GitHub/computer-science/cs2150/labs/lab-2/postlab/a.out+0x514050)
    #1 0x5184b5 in List::List() /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/List.cpp:11:15
    #2 0x51b777 in main /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/ListTest.cpp:102:28
    #3 0x7f7c97c91b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310

Indirect leak of 48 byte(s) in 2 object(s) allocated from:
    #0 0x514050 in operator new(unsigned long) (/mnt/c/Users/Winston/Documents/GitHub/computer-science/cs2150/labs/lab-2/postlab/a.out+0x514050)
    #1 0x518465 in List::List() /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/List.cpp:10:15
    #2 0x51b777 in main /home/winston/github/computer-science/cs2150/labs/lab-2/postlab/ListTest.cpp:102:28
    #3 0x7f7c97c91b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: 96 byte(s) leaked in 4 allocation(s).</code></pre>
<p>LeakSanitizer will print out where the leaking memory was allocated
so that you can figure out what you forgot to delete. In this case, we
can see we forgot to delete the objects we created on lines 11 and 10 in
the constructor, which just happen to be <code>tail</code> and
<code>head</code>, respectively. Now that we know <em>what</em> we are
leaking, we can start to think about <em>where</em> in our program we
should delete those objects.</p>
<p>Having a program run successfully under AddressSanitizer and
LeakSanitizer adds strong assurances towards code correctness!</p>
</body>
</html>