i this program which runs best on Linux, can help you find both pointer errors and memory leaks. You will find this freely-available tool indispensable on all programming projects involving C or C++.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

This lab is going to introduce a critically important tool when programming in C or C++: valgrind. This program, which runs best on Linux, can help you find both pointer errors and memory leaks. You will find this freely-available tool indispensable on all programming projects involving C or C++.

So far, we have been ignoring the issue of freeing memory: our binary search tree class is allocating nodes to build trees, but never returning this memory when trees are destroyed / go out of scope. Let’s see how bad the problem is, and then fix it.

 

Step 1:

Login to Codio and open the project “cs251-lab-week05”. If you haven’t joined Codio yet, create a Codio account using your UIC email address, and join the class (“CS 251 Fall 2019”):

https://codio.com/p/join-class?token=brigade-america

Let’s make sure the valgrind tool is installed. You can install valgrind on any Linux system using the following command:

sudo apt-get install valgrind

 This will check to see if the latest version is installed, and if not, install for you. Go ahead and run this command to see if Codio is already installed.

 

Step 2:

A working main program and BST class are provided in “main.cpp” and “bst.h”. You’ll recognize these from last week when we were collecting times. Build and run the program using the provided makefile:

On the surface everything looks good. But let’s run valgrind to see if we are leaking any memory --- i.e. is the program / BST class not freeing the nodes in the trees after each timing run? The makefile is setup to run valgrind for you, so type “make build” then “make valgrind” to run. Look at the output in part #3:

Turns out we are allocating almost 3MB of memory that we are not returning. Oops.

Step 3:

The way to fix this in C++ is to implement a destructor in the BST class to delete the memory when the tree is about to be destroyed. Recall that a constructor is automatically called by C++ when a tree is being created. For example, here’s the default constructor from “bst.h”:

 

//

// default constructor:

//

// Creates an empty tree.

//

binarysearchtree()

{

Root = nullptr; Size = 0;

}

 

Much like the constructor, the destructor has the same name as the class, but is preceded by the ~ symbol and the keyword virtual. Here’s the destructor that is already defined in “bst.h”:

//

// destructor:

//

// Called automatically by system when tree is about to be destroyed;

// this is our last chance to free any resources / memory used by

// this tree.

//

virtual ~binarysearchtree()

{

//

// TODO:

//

}

 

Note that the destructor is called automatically by C++ just before a tree is destroyed, so you *never* call this function yourself. Your job is to implement this function to perform a post-order traversal of the tree, deleting every node. Since the insert function uses “new” to allocate a node, you’ll use “delete” to delete a node and return the memory to the system:

delete cur;  // where cur is a pointer to a node

Go ahead and implement the destructor… You’ll need a helper function, and the correct traversal is post- order (you’ll want to think about why that is so).

 

Step 4:

The only way to know if you have done this properly is to run valgrind. What valgrind does is run your program and monitor all the memory you allocate, and then check to see if you have freed it. Don’t be surprised if the program runs slower using valgrind, since valgrind is doing lots of work in the background to

 

monitor what you’re doing. When you’re ready, build and run your program using valgrind. If all is well, you’ll see the following:

Success! The destructor is correctly written, and the BST class is now properly freeing memory.

A handy function in data structure classes is one that “clears” the contents of the data structure --- i.e. it empties the vector or tree. A clear function is already defined in “bst.h”, with an intentional pointer error (the code is continued onto the next page):

//

// clear:

//

// Clears the contents of the tree, resetting the tree to empty.

//

void clear()

{

//

// Re-initialize root pointer and size to "empty":

//

Root = nullptr; Size = 0;

 

//

// Intentional pointer error:

//

Root->Key = 123;

}

 

At the bottom of the main() program, you’ll see code to create a tree, fill with 100 values, and then call clear to see what happens. Go ahead and uncomment this code. This will call clear and trigger the pointer error:

 

binarysearchtree T;

 

buildBST(T, 100);

 

cout << "Before clear:" << endl;

cout << " Size: " << T.size() << endl; cout << " Height: " << T.height() << endl;

 

T.clear();

 

cout << "After clear:" << endl;

cout << " Size: " << T.size() << endl; cout << " Height: " << T.height() << endl;

 

Build the program and run using valgrind --- valgrind will pin-point the line where the pointer error occurred! Much better than the usual “segmentation fault”. In my case, valgrind says the error occurred on line 244 of “bst.h”:

 

 

At this point, delete the intentional pointer error from “bst.h”, but keep the code that resets the Root and Size:

 

//

// clear:

//

// Clears the contents of the tree, resetting the tree to empty.

//

void clear()

{

//

// Re-initialize root pointer and size to "empty":

//

Root = nullptr; Size = 0;

 

    //

    // Intentional pointer error:

    //

    Root->Key = 123;

}

Build and run using valgrind. The pointer error goes away, but we still have a memory leak:

The clear function isn’t freeing the nodes, it’s just resetting the Root pointer. Oops. Fix the clear function so that it properly deletes memory… Do *NOT* call the destructor, that’s not valid. However, if appropriate, you

*can* call the same helper function that the destructor calls? That’s perfectly legal, since it’s a private helper function that any class function can call. When you think you have it, build and run with valgrind.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of