Sign in to follow this  
NUCLEAR RABBIT

Memory Allocation

Recommended Posts

Hello,

 

So I am editing a project I had where I was creating a queue. In my pop() method I am having an issue and I am not sure why. I am trying to free the memory of the Node I am popping from the queue and also returning the data from that Node to the user before it is deleted. When I comment out the free() method in the pop() method it works and when I uncomment the free() call I get heap memory crashes. Can anyone please help me see what I am doing wrong?

 

Queue.inl

template <typename T>
T Queue<T>::pop()
{
	if (isEmpty())
	{
		std::cout << "pop() was used, but the Queue is empty.\n\n";

		return NULL;
	}
	else
	{
		Node * temp = headNode;

		T removedItem = temp->data;

		headNode = headNode->nextNode;

		std::cout << "pop() was used and " << temp->data << " was removed from the Queue.\n\n";

		free(temp);

		size--;

		return removedItem;
	}
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop_all();
		T pop();
		T peek();
		bool isEmpty();
		int getSize();
	private:
		struct Node
		{
			T data;
			Node * nextNode;
		};

		Node LinkedList;
		Node * headNode; // front of the queue
		Node * tailNode; // End of the Queue
		int size;
};

#include "Queue.inl"
Edited by NUCLEAR RABBIT

Share this post


Link to post
Share on other sites

Is IsEmpty() working correctly?

Are objects created with malloc?

is headNode a valid value?

Are the Nodes initialized to sensible values?

 

Check all everything is initialised to a sensible value (probably NULL). 

 

yes isEmpty() is working correctly and yes the objects are created using malloc.

 

 

T is not necessarily a pointer. T* is a pointer.

 

which portion were you referring to?

Share this post


Link to post
Share on other sites

Should tailNode be updated in pop()?  What happens if tailnode is pointing at headNode?  

 

thanks, I totally forgot about that condition. No luck solving the heap corruption though :unsure:

 

 

return NULL;

 

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

 

Main.cpp

//////////////////////////////////
//                              //
//   Data Structures - Queues   //
//   ------------------------   //
//                              //
//   Creating a queue system    //
//   using linked lists and     //
//   C++ (FIFO)                 //
//                              //
//////////////////////////////////

#include "LibIncludes.h"

void displayQueueSize(Queue<int> queue)
{
	std::cout << "Queue Size = " << queue.getSize() << "\n\n";
}

int main()
{
	Queue<int> myQueue;

	myQueue.push(2);
	myQueue.push(3);
	myQueue.push(5);

	displayQueueSize(myQueue);

	int removed = myQueue.pop();

	if (removed < 0)
		std::cout << "\n*** pop() was unsuccessful. Queue is empty.\n";
	else
		std::cout << "\n*** pop() was successful. " << removed << " was removed.\n";

	system("PAUSE");

	return 0;
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop_all();
		T pop();
		T peek();
		bool isEmpty();
		int getSize();
	private:
		struct Node
		{
			T data;
			Node * nextNode;
		};

		Node LinkedList;
		Node * headNode; // front of the queue
		Node * tailNode; // End of the Queue
		int size;
};

#include "Queue.inl"

Queue.inl

#include "LibIncludes.h"

template <typename T>
Queue<T>::Queue()
{
	headNode = nullptr;
	tailNode = nullptr;

	size = 0;

	std::cout << "*** A new empty Queue was created ***\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
Queue<T>::Queue(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	headNode = temp;
	tailNode = temp;

	size = 1;

	std::cout << "*** A new Queue with starting item " << headNode->data << " was created ***\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
bool Queue<T>::isEmpty()
{
	if (headNode == NULL)
		return true;
	else
		return false;
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
T Queue<T>::peek()
{
	if (isEmpty())
		return NULL;
	else
		return headNode->data;
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
void Queue<T>::pop_all()
{
	if (isEmpty())
		std::cout << "pop_all() was used, but the Queue is already empty.\n\n";
	else
	{
		std::cout << "pop_all() was used and destroyed the Queue.\n\n";

		Node temp = headNode;

		for (int i = 0; i < size; i++)
		{
			pop();
		}

		headNode = nullptr;
		tailNode = nullptr;

		size = 0;
	}
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
void Queue<T>::push(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	if (isEmpty())
	{
		headNode = temp;
		tailNode = temp;
	}
	else
	{
		tailNode->nextNode = temp;
		tailNode = temp;
	}

	size++;
	std::cout << "push() was called and " << newItem << " was added to the Queue.\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
T Queue<T>::pop()
{
	if (isEmpty())
	{
		std::cout << "pop() was used, but the Queue is empty.\n\n";

		return -1;
	}
	else
	{
		Node * temp = (struct Node *)malloc(sizeof(struct Node *));
		
		temp = headNode;

		T removedItem = headNode->data;

		headNode = headNode->nextNode;

		std::cout << "pop() was used and " << temp->data << " was removed from the Queue.\n";

		free(temp);
		temp = nullptr;

		size--;

		if (size == 0)
		{
			free(tailNode);
			tailNode = nullptr;
		}

		return removedItem;
	}
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
int Queue<T>::getSize()
{
	return size;
}

Share this post


Link to post
Share on other sites
Your class should have a destructor, a copy constructor and assignment operator.

I'd recommend not having both a head and tail pointer to start, it should be simpler to implement a queue as a singly linked list (in reverse, push creates a new "head"). It complicates things to maintain both correctly.

Consider using new/delete for the nodes, at least to start. Complex classes like std::string will break unless you account for how malloc() separates allocation from C++ object life cycle management.

Share this post


Link to post
Share on other sites

 sizeof(struct Node *) <- isn't this wrong??

 

for a node you should allocate sizeof(struct node) otherwise you allocate only pointer size space (4 or 8 bytes?)

 

Yes, this is the problem, you should be calling malloc(sizeof(struct Node)) .

 

However, you can make life easier using new and delete, like this

// in push()
Node* temp = new Node;
 
// later, in pop()
delete temp;

 

And, I just noticed, in pop(), why are you calling malloc() on temp again, then immediately assigning temp to headNode?  Don't malloc temp in pop().

 

You need to understand memory allocation a little more, then you should be able to tackle this problem fine.

Share this post


Link to post
Share on other sites

 

return NULL;

 

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

 

Will node solve your issue but FYI, the correct solution in this case is quite simple:

template<typename T>
T returnDefault(void)
{
    return T();
}

This will return a specified default value for all types (int = 0, T* = nullptr, custom type = default-ctor, ...), so just replace return NULL by return T() and you should be fine in this regard.

Share this post


Link to post
Share on other sites

sizeof(Node)

Don't repeat the struct keyword everywhere or I will hunt you down and take all the vowels from your keyboard.

 

lol

 

 

 


 

return NULL;

 

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

 

Will node solve your issue but FYI, the correct solution in this case is quite simple:

template<typename T>
T returnDefault(void)
{
    return T();
}

This will return a specified default value for all types (int = 0, T* = nullptr, custom type = default-ctor, ...), so just replace return NULL by return T() and you should be fine in this regard.

 

 

Thank you, I never learned this

 

 

 

 sizeof(struct Node *) <- isn't this wrong??

 

for a node you should allocate sizeof(struct node) otherwise you allocate only pointer size space (4 or 8 bytes?)

 

Yes, this is the problem, you should be calling malloc(sizeof(struct Node)) .

 

However, you can make life easier using new and delete, like this

// in push()
Node* temp = new Node;
 
// later, in pop()
delete temp;

And, I just noticed, in pop(), why are you calling malloc() on temp again, then immediately assigning temp to headNode?  Don't malloc temp in pop().

 

You need to understand memory allocation a little more, then you should be able to tackle this problem fine.

 

 

Yeah I def needed to learn about memory allocation more haha I looked up some tutorials and watched some video explanations and I think I am understanding it better now.

 

 

PS - Thank you to everyone that helped me out, I got it working now!

Share this post


Link to post
Share on other sites

malloc works well with the term pod which is short for plain old data.

 

Here malloc reserve some amount of space and return it to you as a (void*). Why void* because malloc is from the days of c not c++. In those days we didn't have templates and casting was need to convert void* to something understandable. I see that you are mixing up c++ and c while it is possible, I would advise you to use the newer c++ concept instead of c, the  reason is it makes coding easier to understand and work with. 

Share this post


Link to post
Share on other sites

The only time malloc should really be used in C++ is if you're writing a specialized allocator (like overloading new or something), lol. Even 'new' should be avoided in application code, but I think OP is still learning the bare basics, so 'new' is probably okay for now.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this