General - "Segmentation Fault" in C++

Hello,

I am new to c++ but have worked with java some. I have been assigned to complete a program by writing 3 functions: A "copy constructor" function for a queue, an enqueue function, and a dequeue function. I am writing, compiling, and running my code on a UNIX machine. I have code that compiles, but when I run it i get a "Segmentation Fault". I do not know what part of my code produced this fault, so I am hoping that one of you may. The code that I wrote is as follows (this is the code that should have the error):

// copy constructor for Queue
Queue::Queue (const Queue & Old_queue)
{

Queue * q2 = new Queue();
Node * n2 = new Node();
q2 -> tail = Old_queue.tail; //set tail of new queue equal to tail of old queue
//set head of new queue equal to tail,seeing how nothing is in new queue yet
q2 -> head = q2 -> tail;
n2 = q2 -> tail; //set new node equal to tail
while(Old_queue.head != q2 -> head -> next){ //copies Old_queue values //to n2 queue
enqueue(n2 -> proc);
n2 -> next;
q2 -> head -> next;
}
}

// enqueue
// Add the given Process object pointed to by procptr to the
// tail of the queue.
void
Queue::enqueue (Process * procptr){
Node * q3 = new Node();
q3 -> proc = procptr;
q3 -> prev = head; //place this new node at end of queue
q3 -> next = NULL;
tail = tail -> next; //move tail pointer to current end of queue
}


// Dequeues the head of the queue, and returns a pointer to
// the Process object dequeued. If the queue is empty,
// then there is nothing to dequeue, so the pointer will be null.
Process *
Queue::dequeue (){

Node * saveHead = new Node();
if(head == NULL){ //if queue is empty
return NULL;
}
else{
saveHead = head;
head -> prev -> next = NULL;
head = head -> prev;
delete head;
return saveHead -> proc;
}
}

Thanks for any help offered!

In preparation for my answer, I just want the code a bit more readable. [ highlight=cpp ] [ /highlight ] tags used.

I'm finding this post hard to answer. The problem is that there's so much wrong I don't know where to begin or how to weave the "red thread" to a coherent piece of text. This is my 3rd attempt.

First, a couple pieces of advice:
- The debugger is as important a tool as the compiler. The only unix debugger I'm aware of is gdb, but I have no clue on how to use it; the only try I've had, an IDE covered the details for me.
- Instead of creating your own buggy stuff, just use the standard library ones. Goes double if you don't have the competence with pointers to handle creating your own. (Unless that is the assignment................. )
- Don't litter. At least unless you hire a GC to work for you. I know, this is particularly hard when you're used to a lax language like java, which encourages littering.
- Stay away from pointers. Pointers are evil, and should only be used as a last resort. Particularly if you don't understand them very well.
- When programming in C++, leave your Java experience behind. It brings too many bad (in c++) habits with it.


More on Segfaults

A segfault (in windows, the term for the same error is "access violation") is trying to access a memory position not allocated. The only java equivalent is a nullpointer exception. Except you're not always guaranteed it will happen, general weirdness ("undefined behavior") may occur instead. (Worst of all, undefined behavior may intersect desired behavior under a limited set of circumstances present when tested.)

----

Pointers, Resource Management and Littering


The problem with pointers (particularly "raw" pointers) is that they're intimately tied to resource management. You want to avoid resource management when you don't absolutely have to.

Some bad habits from java shows. You create garbage, and then expect a GC to clean up after you. Except... C++ doesn't (by default) provide GC. Most C++ programming is based on not creating that garbage to begin with.
In your copy constructor, you create a new Queue which you use for some pointless stuff, and then forget to delete. Even if you needed to use it, it would be better to declare a Queue x; rather than a Queue* x=new Queue; - but you don't even need that.


In particular, your code says At which point it loses track of the Node allocated at the first line - including losing the ability to delete it. You just littered.

Also, I just wanted to raise the question - who/what is responsible for deleting the Process objects? Worse, how do you deal with the fact that you'll likely end up running it from both queues?

It is perhaps intended as a "move" type operation? (As in, doing this to allow returning from a function or similar?) Then you should be working with a compiler that supports r-value references. g++ does that since 4.3, provided you use the -std=c++0x option (source). That is, remove the copy constructor and add this move constructor:

----

Know your data structures

head -> node <-> node <-> node <- tail

Each < or > represents a pointer that must be set to something other than 0. Your enqueue function doesn't. I would usually assume that following "next" would move you towards the right, but it seems your code at least sometimes (your dequeue function) tries to go left (towards the head) when following nexts. I will write my code by next-to-tail.

Assuming that insertions are to happen at the tail,

In your implementation of enqueue()
- You don't handle the case that there isn't a node there already, in which case you need to set the head and tail. In particular, you even dereference tail when it's supposed to be null. That's an instant segfault.
- prev=head is a line that would create a graph like
head -> first <- second
<- third
That is, from the third node on, you're not connecting to the last Node, but to the first in the queue. Worse, there's nothing pointing back to the third. (Or even the second.)
- You need to change the Node you're attaching to, either prev or next. (See how the arrow between first and second above is not also pointing right?)
- I won't even pretend that this list is complete. I think the biggest problem is more fundamental: The function doesn't know what it wants to do. (That is, it's not possible to read from it what it's meant to do. Is it supposed to insert at the head or tail? Which direction does next go?) This usually means the programmer himself did not have a clear idea of what to do with it. Who said pen and paper was obsolete?


Your dequeue function isn't much better.