Jump to content
  • Advertisement
Sign in to follow this  
NUCLEAR RABBIT

Memory Allocation

This topic is 910 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement

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?)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!