C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old October 27th, 2009, 06:15 PM
gpstanek gpstanek is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Oct 2009
Posts: 3 gpstanek User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 55 m 46 sec
Reputation Power: 0
Unhappy 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!

Reply With Quote
  #2  
Old October 28th, 2009, 05:36 AM
MaHuJa's Avatar
MaHuJa MaHuJa is offline
Contributing User
Dev Articles Beginner (1000 - 1499 posts)
 
Join Date: Dec 2007
Posts: 1,177 MaHuJa User rank is Private First Class (20 - 50 Reputation Level)MaHuJa User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 1 Week 1 Day 21 h 27 m 36 sec
Reputation Power: 12
Send a message via Skype to MaHuJa Send a message via XFire to MaHuJa
In preparation for my answer, I just want the code a bit more readable. [ highlight=cpp ] [ /highlight ] tags used.

cpp Code:
Original - cpp Code
  1. // copy constructor for Queue
  2. Queue::Queue (const Queue & Old_queue)
  3. {
  4.  
  5.   Queue * q2 = new Queue();
  6.   Node * n2 = new Node();
  7.   q2 -> tail = Old_queue.tail//set tail of new queue equal to tail of old queue
  8.   //set head of new queue equal to tail,seeing how nothing is in new queue yet
  9.   q2 -> head = q2 -> tail; 
  10.   n2 = q2 -> tail;    //set new node equal to tail
  11.   while(Old_queue.head != q2 -> head -> next){  //copies Old_queue values //to n2 queue
  12.     enqueue(n2 -> proc);
  13.     n2 -> next;
  14.     q2 -> head -> next;
  15.   }
  16. }
  17.  
  18. // enqueue
  19. // Add the given Process object pointed to by procptr to the
  20. // tail of the queue.
  21. void
  22. Queue::enqueue (Process * procptr){
  23.   Node * q3 = new Node();
  24.   q3 -> proc  = procptr;
  25.   q3 -> prev = head;    //place this new node at end of queue
  26.   q3 -> next = NULL;
  27.   tail = tail -> next;  //move tail pointer to current end of queue
  28. }
  29.  
  30.  
  31. // Dequeues the head of the queue, and returns a pointer to
  32. // the Process object dequeued.  If the queue is empty,
  33. // then there is nothing to dequeue, so the pointer will be null.
  34. Process *
  35. Queue::dequeue (){
  36.  
  37.   Node * saveHead = new Node();
  38.   if(head == NULL){     //if queue is empty
  39.     return NULL;
  40.    }
  41.   else{
  42.     saveHead = head;
  43.     head -> prev -> next = NULL;
  44.     head = head -> prev;
  45.     delete head;
  46.     return saveHead -> proc;
  47.    }
  48. }
__________________
Quote:
Programming by Coincidence
Fred types in some more code, tries it, and it still seems to work. [Then] the program suddenly stops working. [...] Fred doesnít know why the code is failing because he didnít know why it worked in the first place.
Undefined behavior results in: (worst to best)
-Erases your harddisk. Really.
-Appears to work - for now
-Delayed errors/crashes
-Crashes
-Compiler warning

Reply With Quote
  #3  
Old October 30th, 2009, 06:42 AM
MaHuJa's Avatar
MaHuJa MaHuJa is offline
Contributing User
Dev Articles Beginner (1000 - 1499 posts)
 
Join Date: Dec 2007
Posts: 1,177 MaHuJa User rank is Private First Class (20 - 50 Reputation Level)MaHuJa User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 1 Week 1 Day 21 h 27 m 36 sec
Reputation Power: 12
Send a message via Skype to MaHuJa Send a message via XFire to MaHuJa
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
Quote:
"C++ Is my favorite garbage collected language because it generates so little garbage"
--Bjarne Stroustrup, creator of C++


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.
Code:
Queue::Queue (const Queue & Old_queue) { 
  // Assuming next points towards tail
  for (Node* n = Old_queue.head; n; n=n->next) 
  { enqueue(n->procptr); } // Assumes enqueue inserts at tail
}


In particular, your code says
Code:
Node * n2 = new Node();
// lines not touching n2
n2 = q2 -> tail; // Oops!
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:
Code:
Queue::Queue(Queue&& old) {
  head = old.head; old.head = 0;
  tail = old.tail; old.tail = 0;
}


----

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,
Code:
void Queue::enqueue (Process * procptr){
  Node * q3 = new Node(); // No idea why it's called q3, but I'll just keep it up
  q3 -> proc  = procptr;
  q3 -> prev = tail; 
  q3 -> next = NULL;
  if (head && tail) {
    // not the only Node, so we need to change the Node we're attaching to
    tail->next = q3;   // changing another node than the one we're adding, so it points to this one
  } else { 
    head = q3; 
  }
  tail = q3;
}


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.
Code:
// 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();  // There you go again... see above. Remove the whole line
  if(head == NULL){
    return NULL;
  }
  else {
    Process* pr = head.proc;  // was saveHead = head;
    head -> prev -> next = NULL;  // prev is NULL if this is the last Node. segfault opportunity. For that matter, prev is NULL if you take the next-to-tail approach as I've been doing in my code above.
    head = head -> prev;   // With "next-to-tail", this is invalid.
    delete head;  // You're deleting the NEW head here, not the old one you just took out of the queue. This would be a use for savehead.
	// After this, the object may not be accessed, regardless of what pointers may contain the address of its memory location.
    return pr; // was return saveHead -> proc; 
  }

Reply With Quote
  #4  
Old April 7th, 2011, 11:35 AM
gpstanek gpstanek is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Oct 2009
Posts: 3 gpstanek User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 55 m 46 sec
Reputation Power: 0
MaHuJa,

Thank you very much for your response. I realize this post is years old now, but it will help me very much in the future as I learned a lot from it.

Thanks again

Reply With Quote
  #5  
Old April 18th, 2011, 05:07 AM
esspwebmaster esspwebmaster is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2011
Posts: 1 esspwebmaster User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 m 36 sec
Reputation Power: 0
it is amazing i found this post very informative,helpful and useful

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > General - "Segmentation Fault" in C++


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap