Queue Copy Constructor - segfault?

[Paul McKenzie]

Ok, point understood. I will fix that, but in the meantime I want to at least be able to run the program...

To make sure your program isn't making assignments:

class Queue
{
   private:
      Queue& operator=(const Queue&);
//...
};

Recompile your code with this added definition (it must be private:). If you get a compiler or linker error that something is attempting to assign, then guess what? Your program was doing assignments, and you never knew it. If that's the case, then you were silently running a buggy program all along.

But even if you get no such error, keep that definition in the Queue class.

Regards,

Paul McKenzie

[mayabelle]

Node *node1, *node2;
// Put 2 nodes in queue
q2.put(node1);
q2.put(node2);

node1 and node2 are uninitialized pointers. They point to la-la land, but you're using them in the function call. This is not correct, as your put() function is now operating with bogus pointers.

void Queue::put(Node* item) // item is a bogus pointer value
{
	Queue_NodeHolder* next = new Queue_NodeHolder(item); // bogus

Regards,

Paul McKenzie

Oops, not sure how I missed that! I think I fixed that problem; here is the new QueueTest.h:

#ifndef QUEUETEST_H_
#define QUEUETEST_H_

#include <cxxtest/TestSuite.h>
#include "Queue.h"
//#include <algorithm>
using namespace std;

class QueueTest : public CxxTest::TestSuite {
public:

	// Test for default queue constructor
	// A queue should be empty, size 0, when first created
	void test_global_Queue_Queue() {
		Queue q = Queue();
		TS_ASSERT_EQUALS(q.size(), 0);
	}

	// Getting an item from an empty queue should return NULL.
	// Getting the third item from a queue that originally had 
	// 2 items put into it should also return NULL.
	void testGet_EmptyQueue() {
		Queue q = Queue();
		TS_ASSERT(q.get() == NULL);
	}

	// Getting an item from a queue should decrement size by 1, 
	// unless the queue is empty.
	void testGet_Size() {
		// Test if queue is empty:
		// Create queue
		Queue q1 = Queue();
		// Call get on empty queue
		q1.get();
		// Check that size of queue is still 0
		TS_ASSERT_EQUALS(q1.size(), 0);
		// Test if queue is not empty:
		// Create queue and nodes
		Queue q2 = Queue();
		Node *node1 = new Node();
		Node *node2 = new Node();
		// Put 2 nodes in queue
		q2.put(node1);
		q2.put(node2);
		// Store old size of queue
		int oldSize = q2.size();
		// Remove one node from queue
		q2.get();
		// Store new size of queue
		int newSize = q2.size();
		// Check that the new size = old size minus 1
		TS_ASSERT_EQUALS(newSize, oldSize - 1);
	}
	
	// Getting an item should return the first item in the queue, 
	// no matter how many items you put in. 
	void testGet_FIFO() {
		// Create queue and nodes
		Queue q = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		Node *node3 = new Node();
		Node *node4 = new Node();
		// Put first 2 nodes into queue
		q.put(node1);
		q.put(node2);
		// Check that get() removes the first node
		TS_ASSERT(q.get() == node1);
		// Add 2 more nodes into the queue
		q.put(node3);
		q.put(node4);
		// Check that get() removes the new first node
		TS_ASSERT(q.get() == node2);
	}
	
	// Getting an item should return an item that has the same 
	// values as the items that were put into the queue. 
	// Try putting a few items in the queue, then getting them 
	// and checking that they are returning the correct items.
	void testGet_Values() {
		// Create queue and nodes
		Queue q = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		Node *node3 = new Node();
		Node *node4 = new Node();
		// Add nodes into queue
		q.put(node1);
		q.put(node2);
		q.put(node3);
		q.put(node4);
		// Check that get() returns the correct items
		TS_ASSERT(q.get() == node1);
		TS_ASSERT(q.get() == node2);
		TS_ASSERT(q.get() == node3);
		TS_ASSERT(q.get() == node4);
	}
	
	// Putting an item into a queue should increment size by 1.
	void testPut_Size() {
		// Create queue and nodes
		Queue q = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		// Check that initial queue size is 0
		TS_ASSERT_EQUALS(q.size(), 0);
		// Add a node
		q.put(node1);
		// Check that size is now 1
		TS_ASSERT_EQUALS(q.size(), 1);
		// Add another node
		q.put(node2);
		// Check that size is now 2
		TS_ASSERT_EQUALS(q.size(), 2);
	}
	
	// Should always return the size of the queue (>= 0). 
	// A queue should have size 0 when created with default constructor. 
	// The size can be expressed as max(0, (# of puts) - (# of gets)).
	void testSize() {
		// Create queue and nodes
		Queue q = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		Node *node3 = new Node();
		Node *node4 = new Node();
		// Check that queue created with default constructor has size 0
		TS_ASSERT_EQUALS(q.size(), 0);
		// Initialize counters for puts and gets
		int numPuts = 0;
		int numGets = 0;
		// Execute a total of 5 puts and 3 gets
		q.put(node1);
		numPuts++;
		q.put(node2);
		numPuts++;
		q.get();
		numGets++;
		q.put(node3);
		numPuts++;
		q.put(node4);
		numPuts++;
		q.get();
		numGets++;
		q.put(node1);
		numPuts++;
		q.get();
		numGets++;
		// Check that queue size is max(0, (# of puts) - (# of gets))
		TS_ASSERT_EQUALS(q.size(), max(0, numPuts - numGets));
	}
	 
	// This is a test for the queue copy constructor. The copy 
	// constructor should perform a deep copy of any given queue. 
	// To determine that the copy is being done correctly, add some elements, 
	// make a copy, then take a few elements off the first queue and make 
	// sure the second queue is still the original size.
	void test_global_Queue_QueueCopy_Size() {
		// Create q1 and nodes
		Queue q1 = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		Node *node3 = new Node();
		Node *node4 = new Node();
		// Add 4 nodes to q1
		q1.put(node1);
		q1.put(node2);
		q1.put(node3);
		q1.put(node4);
		// Make a copy of q1 and call the copy q2
		Queue q2 = Queue(q1);
		// Store size of q2
		int q2_orig_size = q2.size();
		// Remove 2 elements from q1
		q1.get();
		q1.get();
		// Check that q2 is still the original size
		TS_ASSERT_EQUALS(4, q2_orig_size);
	}

	// The copy constructor should perform a deep copy of any given queue. 
	// Add some elements, make a copy, then take elements off the second queue. 
	// Make sure they are the same nodes that were on the first queue and 
	// track sizes on both queues.
	void test_global_Queue_QueueCopy_Contents() {
		// Create q3 and nodes
		Queue q3 = Queue();
		Node *node1 = new Node();
		Node *node2  = new Node();
		Node *node3 = new Node();
		Node *node4 = new Node();
		// Add 4 nodes to q3
		q3.put(node1);
		q3.put(node2);
		q3.put(node3);
		q3.put(node4);
		// Make a copy of q3 and call the copy q4
		Queue q4 = Queue(q3);
		// Store sizes of q3 and q4
		int q3_orig_size = q3.size();
		int q4_orig_size = q4.size();
		// Remove 2 nodes from q4, and store them
		Node *q4_node1 = q4.get();
		Node *q4_node2 = q4.get();
		// Check that the 2 nodes removed from q4 were the same 2 nodes that were first stored on q3
		TS_ASSERT(q4_node1 == node1);
		TS_ASSERT(q4_node2 == node2);
		// Check that q1 is still the original size
		TS_ASSERT_EQUALS(q3.size(), q3_orig_size);
		// Check that q2 is the new size
		TS_ASSERT_EQUALS(q4.size(), q4_orig_size - 2);
	}


};

#endif /*QUEUETEST_H_*/

But I'm still getting a segfault when I try to run it. :-(

[mayabelle]

To make sure your program isn't making assignments:

class Queue
{
   private:
      Queue& operator=(const Queue&);
//...
};

Recompile your code with this added definition (it must be private. If you get a compiler or linker error that something is attempting to assign, then guess what? Your program was doing assignments, and you never knew it. If that's the case, then you were silently running a buggy program all along.

But even if you get no such error, keep that definition in the Queue class.

Regards,

Paul McKenzie

That didn't produce any compiler/linker errors. However I will keep it in the definition.

[mayabelle]

Node *node1, *node2;
// Put 2 nodes in queue
q2.put(node1);
q2.put(node2);

node1 and node2 are uninitialized pointers. They point to la-la land, but you're using them in the function call. This is not correct, as your put() function is now operating with bogus pointers.

void Queue::put(Node* item) // item is a bogus pointer value
{
	Queue_NodeHolder* next = new Queue_NodeHolder(item); // bogus

Regards,

Paul McKenzie

Oops, nevermind my other post about the segfault still being there (in my eager attempt to try the fix, I forgot to rebuild, oops!). Anyway, initializing the pointers did fix it after all. So, for example, before I had:

BuggyQueue q = BuggyQueue();
Node *node1, *node2;
q.put(node1);
q.put(node2);

instead of:

BuggyQueue q = BuggyQueue();
Node *node1 = new Node();
Node *node2 = new Node();
q.put(node1);
q.put(node2);

Changing it to the latter method fixed the segfault problem. I can't believe I didn't see that before... I guess I was looking for the problem in the wrong place. Surprisingly, the first method didn't break my other tests (which is somewhat concerning, so I'll need to go back and check on those).

Thank you so much for your help, Paul! :-)

[Arjay]

Say, I might have missed this earlier in the discussion, but is there any reason not to use a std::queue?

[Lindley]

Queue::Queue(const Queue& original) {
    if (original.first_ == NULL) {
        first_ = (Queue_NodeHolder*) NULL;
        last_ = (Queue_NodeHolder*) NULL;
        size_ = 0;
    } else {
        Queue_NodeHolder* nh = original.first_;
        while (nh != NULL) {
            put(nh->getContent());
            nh = nh->getNext();
        }
    }
}

Does the put() function make any assumptions about first_, last_, and size_? If so, then this is wrong---because you don't define what those values are before calling put().