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 it 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 the system when the 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.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
