Jump to content

  • Log In with Google      Sign In   
  • Create Account

NUCLEAR RABBIT

Member Since 12 Apr 2006
Offline Last Active Apr 19 2016 01:35 PM

Posts I've Made

In Topic: Memory Allocation

18 April 2016 - 10:10 PM

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!


In Topic: Memory Allocation

17 April 2016 - 10:16 PM

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;
}

In Topic: Memory Allocation

17 April 2016 - 04:40 PM

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?


In Topic: Data Structures Help!

14 April 2016 - 01:09 PM

 

You must have changed something else, but isn't this a problem too:

  linkedList.data = null;

You're assign null to an unknown data type.  It will probably work for all types, but it's not good programming.

 

and this

  headNode = linkedList;

headNode is a pointer to a node, while linkedList is a node.  That shouldn't compile. I suppose this would work though:

  headNode = &linkedList;

 

Yeah, I had to change those as well. The & always slips my mind :rolleyes: haha


In Topic: Data Structures Help!

06 April 2016 - 05:46 PM

See: C++ FAQ Lite: Why can’t I separate the definition of my templates class from its declaration and put it inside a .cpp file?

I like to separate my template classes into hpp, impl, and cpp. For template classes that have a handful of known types (such as a vector4_t<T> for T in (float, int)), then the cpp supplies all the definitions using hpp and impl for those types, and everything else won’t need to know about the impl. Otherwise, I have the hpp include the impl at the end of the file and forego having a cpp file.

 

Thanks! I was not aware of having to do this with templates!

 

 

 

You can't split up templates like that because of the way they compile.
 
You can either define the functions inline with the declaration or use a .inl file instead of a .cpp file and then include the .inl at the end of the header file.
 
Example of method A:

template <class T>
class Foo {
public:
  Foo(T bar) { //define the function inline
    baz = bar;
  }
private:
  T baz;
};
Example of method B:
//Foo.h

template <class T>
class Foo {
public:
  Foo(T bar);
private:
  T baz;
};

#include "Foo.inl" //include this at the end, not the beginning
//Foo.inl


template<typename T>
Foo<T>::Foo(T bar) {
  baz = bar;
}

ninja'd

 

 

Thanks a lot! I used the .inl file method and it worked great!


PARTNERS