**************************
Debugging Data Structures
**************************

.. topic:: Outcome

    Debug structs, dynamically allocated arrays, linked lists and trees using
    printf statements and gdb.

.. topic:: Introduction

    There are several ways of debugging data structures: going through the code on paper, 
    using carefully placed *printf()* statements, printing the data struture manually using gdb 
    and using *.gdbinit* files to automate the printing proccess.

.. topic:: Applicable subjects

    COMP1511, COMP1521, COMP2521, COMP3231

----

Debugging a linked list on paper
============================================

I remember coming out of my first programming exam, and being disheartened that I couldn't do one of the linked list questions.
I knew *conceptually* how to complete the question, but it just wasn't able to make it work.
I went and talked to Andrew Bennet about this, and he showed me this method, which I have used ever since to help students debug their code.

When learning to write linked list code, learning to debug with nothing but pen and paper is an indispensable skill to develop.



The main idea of this concept is to find input values that cause your code to break,
then to use those to go through your code line by line,
writing down how the variables change and drawing the linked list.

An example of this is given in the following video: 


.. raw:: html

    <iframe width="560" height="315" src="https://www.youtube.com/embed/0FhkiqRq1Eg" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>


This technique is not limited to linked lists, but can also be applied to arrays etc.

Debugging a linked list using *printf()*
============================================

Sometimes debugging large, complex linked data structures by hand can be time consuming.
For COMP1511 and COMP2521 labs, debugging a linked list on paper is helpful for building an understanding.
For COMP1511 assignment 2, there will be situations where it is easier and clearer to debug via printing.

You can create a print statement for not only the entire list, but also for your node structure. 
One common use for this node print function is printing the curr pointer within a loop. 
Furthermore, can check that structures are changing as they should by printing them 
before and after particular changes are made.




Debugging Linked Data Structures using GDB (without a script)
================================================================

Printing a linked list in GDB is a lot like printing 
GDB can be used to print a linked list.
You can dereference each node one by one, using the *next* field to access each successive node.
It will most likely look something like this: ::

        (gdb) print *(curr)
        (gdb) print *(curr->next)
        (gdb) print *(curr->next->next)

There is an example of debugging a linked list using GDB in the :ref:`call_stack` module.


Writing GDB Scripts in *.gdbinit*
=========================================

Debugging data structures in GDB can become tedious.
You can write scripts to automate certain debugging tasks
like printing out trees and linked lists.
See the :ref:`GDB_init` module for more details on writing GDB scripts.



.. moduleauthor:: Liz Willer <e.willer@unsw.edu.au>
		  
:Date: 2020-01-22