Queue Copy Constructor - segfault?

I'm relatively new to C++, so maybe I'm missing something very obvious, but I can't figure out why I am getting a segmentation fault when I run my program after implementing the copy constructor for a queue. I have the following code for the copy constructor:

Code:

---

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 anyone have any hints/suggestions about why this is causing a segfault? I have been staring at it and playing around with it for hours and just can't seem to figure it out. :-( Any help would be much appreciated. Thanks!

Quote:

---

Originally Posted by mayabelle

I'm relatively new to C++, so maybe I'm missing something very obvious, but I can't figure out why I am getting a segmentation fault when I run my program after implementing the copy constructor for a queue.

---

1) Let's see the program that uses this Queue class that causes the error. This includes a main() program/

2) Post the Queue class, not just the function.

3) That code that is supposed to be a copy constructor doesn't look like it makes copies. When you code a copy constructor it is supposed to make copies. This means that if you were to take two Queue cobjects one is a copy of the other, the program must behave exactly the same way, regardless of which Queue object is used.

4) It looks like, your copy constructor has "side-effects", and coding side-effects in copy constructors is to be avoided. The reason for this is that you don't know when that copy constructor will actually be called. What if the object that is being copied from has a NULL original.first, and a non-NULL last, and in addition, size is not 0?

One object will have NULL first and last pointers, and the other doesn't have these values. You have two distinct objects that are bogus copies of each other. Your program will believe they are copies, but they are not really logical copies. This leads to very hard-to-find bugs, as the logic of the program becomes twisted and almost impossible to follow when you have these psuedo-copies floating around.

5) What do those functions do inside the copy constructor in the else clause? Do they actually work correctly?

Regards,

Paul McKenzie

For example:

Code:

---

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

---

If put() places a new item in the queue, there is no need for checking up front for anything.

Secondly, if you code a copy constructor, you should also code an assignment operator -- if you don't code an assignment operator, this will not work correctly:

Code:

---

Queue q1;
Queue q2;
//...
q2 = q1;

---

Regards,

Paul McKenzie

Quote:

---

1) Let's see the program that uses this Queue class that causes the error. This includes a main() program/

---

The main() program is an automatically generated file called runner.cpp which is generated by the CxxTest package, and I haven't touched it. I know that it worked fine before I used the copy constructor, so that isn't the issue. The file runner.cpp takes a bunch of test cases from the included file QueueTest.h and checks if the assertions pass or fail. Essentially, the QueueTest.h is the program that causes the error. Here is the code for QueueTest.h:

Code:

---

#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, *node2;
                // 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, *node2, *node3, *node4;
                // 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, *node2, *node3, *node4;
                // 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, *node2;
                // 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, *node2, *node3, *node4;
                // 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, *node2, *node3, *node4;
                // 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(q2.size(), 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 q1 and nodes
                Queue q1 = Queue();
                Node *node1, *node2, *node3, *node4;
                // 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 sizes of q1 and q2
                int q1_orig_size = q1.size();
                int q2_orig_size = q2.size();
                // Remove 2 elements from q2
                q2.get();
                q2.get();
                // Check that q1 is still the original size
                TS_ASSERT_EQUALS(q1.size(), q1_orig_size);
                // Check that q2 is the new size
                TS_ASSERT_EQUALS(q2.size(), q2_orig_size - 2);
        }


};

#endif /*QUEUETEST_H_*/

---

The last 2 tests (functions) above are the ones that call the copy constructor (Queue q2 = Queue(q1)) and seem to be causing the issues.

Quote:

---

2) Post the Queue class, not just the function.

---

Ok, here is the entire Queue class:

Code:

---

#include "Queue.h"
#include <cstdlib>

const int QUEUE_SIZE_INC = 0;

Queue::Queue() {
        first_ = (Queue_NodeHolder*)NULL;
        last_ = (Queue_NodeHolder*)NULL;
        size_ = QUEUE_SIZE_INC;
}

// copy-constructor has to replicate the node holders
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();
                }
        }
}

Queue::~Queue() {
        if (first_ != NULL) {
                delete(first_);
        }
}

void Queue::put(Node* item) {
        Queue_NodeHolder* next = new Queue_NodeHolder(item);
        if (first_ == NULL) {
                first_ = next;
        } else {
                last_->setNext(next);
        }
        last_ = next;
        size_ += 1;
}

Node* Queue::get() {
        if (last_ == NULL) {
                return NULL;
        }

        Node* result = first_->getContent();

        if (first_ == last_) {
                last_ = (Queue_NodeHolder*)NULL;
        }

        Queue_NodeHolder* tmp = first_;
        first_ = first_->getNext();
        tmp->setNext((Queue_NodeHolder*)NULL);
        delete tmp;
        size_ -= 1;

        return result;
}

int Queue::size() {
        return size_;
}

// -- Queue_NodeHolder implementation --

Queue::Queue_NodeHolder::Queue_NodeHolder(Node* initialContent) {
        content_ = initialContent;
}

Queue::Queue_NodeHolder::~Queue_NodeHolder() {
        if (next_ != NULL) {
                delete next_;
        }
}

Node* Queue::Queue_NodeHolder::getContent() {
        return content_;
}

Queue::Queue_NodeHolder* Queue::Queue_NodeHolder::getNext() {
        return next_;
}

void Queue::Queue_NodeHolder::setNext(Queue::Queue_NodeHolder* holder) {
        next_ = holder;
}

---

Quote:

---

3) That code that is supposed to be a copy constructor doesn't look like it makes copies. When you code a copy constructor it is supposed to make copies. This means that if you were to take two Queue cobjects one is a copy of the other, the program must behave exactly the same way, regardless of which Queue object is used.

---

Yes, that is the goal, but I'm not sure how I'm not doing that...

Quote:

---

4) It looks like, your copy constructor has "side-effects", and coding side-effects in copy constructors is to be avoided. The reason for this is that you don't know when that copy constructor will actually be called. What if the object that is being copied from has a NULL original.first, and a non-NULL last, and in addition, size is not 0? You have two distinct objects that are bogus copies of each other.

---

I'm not sure how the object being copied could have a NULL original.first_ without being empty, because objects are always removed from the queue in a FIFO way and objects are only added into the last slot (which is also the first slot if the queue is empty). What I'm trying to do with the copy constructor is just a deep copy of all the nodes, so that, after the copy, changing the copy does not change the original.

Quote:

---

5) What do those functions do inside the copy constructor in the else clause? Do they actually work correctly?

---

I'm pretty sure they work correctly. The implementation is included in the code that I posted above for the Queue class, in the implementation of the Queue_NodeHolder subclass at the bottom of the Queue class.

Quote:

---

Originally Posted by Paul McKenzie

For example:

Code:

---

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

---

If put() places a new item in the queue, there is no need for checking up front for anything.

---

I tried that, but I still got the segfault at run time. :(

Quote:

---

Originally Posted by Paul McKenzie

Secondly, if you code a copy constructor, you should also code an assignment operator -- if you don't code an assignment operator, this will not work correctly:

Code:

---

Queue q1;
Queue q2;
//...
q2 = q1;

---

Regards,

Paul McKenzie

---

I didn't code an assignment operator, but read somewhere that I can use this syntax instead (without needing to code an assignment operator, since it just calls the copy constructor directly):

Code:

---

// makes copy of q2 and puts it into q1
Queue q1 = Queue(q2);

---

So I still don't know what is causing the segfault. :(

I appreciate you trying to help, by the way. :)

I responded to your first post too, but it said that a moderator had to approve it before it would be posted... weird...

Already responded to this but it didn't post for some reason, so let me try again, this time in smaller chunks just in case...

Quote:

---

Originally Posted by Paul McKenzie

1) Let's see the program that uses this Queue class that causes the error. This includes a main() program/

---

The program that uses the Queue class is "QueueTest.h":

Code:

---

#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, *node2;
                // 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, *node2, *node3, *node4;
                // 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, *node2, *node3, *node4;
                // 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, *node2;
                // 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, *node2, *node3, *node4;
                // 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, *node2, *node3, *node4;
                // 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(q2.size(), 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 q1 and nodes
                Queue q1 = Queue();
                Node *node1, *node2, *node3, *node4;
                // 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 sizes of q1 and q2
                int q1_orig_size = q1.size();
                int q2_orig_size = q2.size();
                // Remove 2 elements from q2
                q2.get();
                q2.get();
                // Check that q1 is still the original size
                TS_ASSERT_EQUALS(q1.size(), q1_orig_size);
                // Check that q2 is the new size
                TS_ASSERT_EQUALS(q2.size(), q2_orig_size - 2);
        }


};

#endif /*QUEUETEST_H_*/

---

The usage of the copy constructor is in the form of

Code:

---

Queue q2 = Queue(q1);

---

Again, I already responded but it didn't post, so re-posting in smaller chunks...

Quote:

---

2) Post the Queue class, not just the function.

---

Here it is:

Code:

---

#include "Queue.h"
#include <cstdlib>

const int QUEUE_SIZE_INC = 0;

Queue::Queue() {
        first_ = (Queue_NodeHolder*)NULL;
        last_ = (Queue_NodeHolder*)NULL;
        size_ = QUEUE_SIZE_INC;
}

// copy-constructor has to replicate the node holders
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();
                }
        }
}

Queue::~Queue() {
        if (first_ != NULL) {
                delete(first_);
        }
}

void Queue::put(Node* item) {
        Queue_NodeHolder* next = new Queue_NodeHolder(item);
        if (first_ == NULL) {
                first_ = next;
        } else {
                last_->setNext(next);
        }
        last_ = next;
        size_ += 1;
}

Node* Queue::get() {
        if (last_ == NULL) {
                return NULL;
        }

        Node* result = first_->getContent();

        if (first_ == last_) {
                last_ = (Queue_NodeHolder*)NULL;
        }

        Queue_NodeHolder* tmp = first_;
        first_ = first_->getNext();
        tmp->setNext((Queue_NodeHolder*)NULL);
        delete tmp;
        size_ -= 1;

        return result;
}

int Queue::size() {
        return size_;
}

// -- Queue_NodeHolder implementation --

Queue::Queue_NodeHolder::Queue_NodeHolder(Node* initialContent) {
        content_ = initialContent;
}

Queue::Queue_NodeHolder::~Queue_NodeHolder() {
        if (next_ != NULL) {
                delete next_;
        }
}

Node* Queue::Queue_NodeHolder::getContent() {
        return content_;
}

Queue::Queue_NodeHolder* Queue::Queue_NodeHolder::getNext() {
        return next_;
}

void Queue::Queue_NodeHolder::setNext(Queue::Queue_NodeHolder* holder) {
        next_ = holder;
}

---

Quote:

---

Originally Posted by mayabelle

I tried that, but I still got the segfault at run time. :(

---

So those functions that supposedly places objects inside the queue is faulty.

Quote:

---

I didn't code an assignment operator, but read somewhere that I can use this syntax instead (without needing to code an assignment operator, since it just calls the copy constructor directly):

---

That syntax is not intuitive to any C++ programmer.

When a C++ programmer wants to apply assignment, they want to see/do this:

Code:

---

object1 = object2;

---

If they're jumping through hoops making assignments, then that is not a good design. Secondly, many internal libraries require assignment to be coded for a class to make it copyable.

Third, and probably most important, nothing stops me, you, or someone else who uses your Queue class from doing this:

Code:

---

Queue q1;
Queue q2;
//..
q2 = q1;

---

Do you get a syntax error? No. Do you get a linker error? No. Do you get a buggy program? YES.

If your class makes copies, it is mandatory to code an assignment operator along with copy constructor. If not, then both copying and assigning should be "turned off" by making these functions private and unimplemented. A half-and-half approach to coding copying and assigning is not acceptable (read up on the "rule of three").

Quote:

---

So I still don't know what is causing the segfault. :(

---

And neither will any one of us know until we see your program.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by mayabelle

Again, I already responded but it didn't post, so re-posting in smaller chunks...

---

So where is the main() program? Where is the sample data that causes the error? Did you try something simple, such as adding two or three items to the queue? If so, did that work?

Finally, are you using a debugger?

Regards,

Paul McKenzie

As before, already responded but it didn't work, so replying again in pieces...

Quote:

---

Originally Posted by Paul McKenzie

3) That code that is supposed to be a copy constructor doesn't look like it makes copies. When you code a copy constructor it is supposed to make copies. This means that if you were to take two Queue cobjects one is a copy of the other, the program must behave exactly the same way, regardless of which Queue object is used.

---

Yes, that was the goal. In what way is it not making copies (other than the segfault)?

Quote:

---

Originally Posted by Paul McKenzie

4) It looks like, your copy constructor has "side-effects", and coding side-effects in copy constructors is to be avoided. The reason for this is that you don't know when that copy constructor will actually be called. What if the object that is being copied from has a NULL original.first, and a non-NULL last, and in addition, size is not 0?

One object will have NULL first and last pointers, and the other doesn't have these values. You have two distinct objects that are bogus copies of each other. Your program will believe they are copies, but they are not really logical copies. This leads to very hard-to-find bugs, as the logic of the program becomes twisted and almost impossible to follow when you have these psuedo-copies floating around.

---

Again, not sure what the side effects of my copy constructor are... I was attempting to make a copy...

Quote:

---

Originally Posted by Paul McKenzie

5) What do those functions do inside the copy constructor in the else clause? Do they actually work correctly?

---

put() adds to the queue, and getContent() and getNext() are part of the Queue_NodeHolder subclass (implementation already posted at the bottom of the Queue class posted above). I'm pretty sure they work correctly; the other tests in QueueTest.h [that do not call the copy constructor] work fine and I know that getContent() and getNext() is used in places besides the copy constructor. But the problem only arose when I had to call the copy constructor...

Quote:

---

Originally Posted by mayabelle

The program that uses the Queue class is "QueueTest.h":

---

We need a main() program and data that you used. A class doesn't just live by itself -- it needs to be instantiated and member functions called. That's why we need to see a main() program and data that reproduces the problem.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by mayabelle

Yes, that was the goal. In what way is it not making copies (other than the segfault)?

---

I stated how your original code may not work. You test original.first_ for NULL, and then you assumed that you must set your object's last_ to NULL along with size being 0. Then you return from the constructor.

What if original.first_ was NULL, but original.last_ wasn't NULL, or original.size_ was not 0? What would happen? Your code would have erroneously created an object that isn't a copy of the original.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

So those functions that supposedly places objects inside the queue is faulty.
That syntax is not intuitive to any C++ programmer.

When a C++ programmer wants to apply assignment, they want to see/do this:

Code:

---

object1 = object2;

---

If they're jumping through hoops making assignments, then that is not a good design. Secondly, many internal libraries require assignment to be coded for a class to make it copyable.

Third, and probably most important, nothing stops me, you, or someone else who uses your Queue class from doing this:

Code:

---

Queue q1;
Queue q2;
//..
q2 = q1;

---

Do you get a syntax error? No. Do you get a linker error? No. Do you get a buggy program? YES.

If your class makes copies, it is mandatory to code an assignment operator along with copy constructor. If not, then both copying and assigning should be "turned off" by making these functions private and unimplemented. A half-and-half approach to coding copying and assigning is not acceptable (read up on the "rule of three").
And neither will any one of us know until we see your program.

Regards,

Paul McKenzie

---

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

Quote:

---

So where is the main() program? Where is the sample data that causes the error? Did you try something simple, such as adding two or three items to the queue? If so, did that work?

---

Oops, the explanation got cut in the post that didn't get posted for some reason, sorry. The main program is in a file called runner.cpp, which is generated by the CXXTest (a framework for constructing robust test cases) and not written or touched by me, but what it does is run a bunch of tests (using assertions) that are written by me... these tests that it runs are in the file QueueTest.h, which I posted above.

This file QueueTest.h is also the file that has the sample data (I know it's weird to have the implementation in a .h file, but CXXTest prefers it that way). Calling the copy constructor is what causes the segfault (and it goes away if the copy constructor and any later operations on the copied queue are commented out).

Yes, adding and removing items to a queue works perfectly, as this is tested in the other test cases (not the copy constructor test, which causes the segfault), all in QueueTest.h which is posted in an earlier post above. Creating an empty queue works correctly as well. So, based on the other test cases working, I know that first_, last_, and size_ are all updated correctly, and that put() and get() are working.

Quote:

---

Finally, are you using a debugger?

---

Yes, I'm using Eclipse debugger, but I couldn't find anything that pointed to what the problem is.

Code:

---

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.

Code:

---

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

---

Regards,

Paul McKenzie

Quote:

---

Originally Posted by mayabelle

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:

Code:

---

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

Quote:

---

Originally Posted by Paul McKenzie

Code:

---

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.

Code:

---

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:

Code:

---

#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. :-(

Quote:

---

Originally Posted by Paul McKenzie

To make sure your program isn't making assignments:

Code:

---

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.

Quote:

---

Originally Posted by Paul McKenzie

Code:

---

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.

Code:

---

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:

Code:

---

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

---

instead of:

Code:

---

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! :-)

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

Code:

---

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().