Jump to content

  • Log In with Google      Sign In   
  • Create Account

Linked List Problems


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 McGrane   Members   -  Reputation: 1090

Like
0Likes
Like

Posted 10 May 2012 - 07:00 PM

Hey, i am having problems with converting a list into an array in c++,
Any ideas whats gone wrong? Its causing segment faults.


#ifndef _CARRAY_H
#define _CARRAY_H
#include <fstream>

using namespace std;

template <class ALLTYPE> class cDataType {  
	 public:	  
	 ALLTYPE  Data;
	 cDataType *p_Next;
	 cDataType(): p_Next( NULL ) {
	 }
};
template <class ALLTYPE> class cArray {
	 int m_Size;
	 cDataType<ALLTYPE> *p_Head;
	 cDataType<ALLTYPE> *p_Tail;
	 public:
	 cArray() : m_Size( 0 ), p_Head( NULL ), p_Tail( NULL ) {
	 }
	 void Drop( ) {

		  cDataType<ALLTYPE> *ptr = p_Head;
		  while( ptr->p_Next != p_Tail ) {
				 ptr = ptr->p_Next;	
		  }
		  cDataType<ALLTYPE> *deleteNode = ptr->p_Next;
		  p_Tail = ptr;
		  m_Size--;
		  delete deleteNode;		
	 }
	 void Add( ALLTYPE l_firstPoint ) {
		  if( p_Head == NULL ) {
			   cDataType<ALLTYPE> *newNode = new cDataType<ALLTYPE>;
			   newNode->Data   = l_firstPoint;
			   newNode->p_Next = NULL;
			   p_Head = newNode;
			   p_Tail = newNode;
			   m_Size++;
		  }
		  else {
			   cDataType<ALLTYPE> *newNode = new cDataType<ALLTYPE>;
			   newNode->Data   = l_firstPoint;
			   newNode->p_Next = NULL;
			   p_Tail->p_Next = newNode;
			   p_Tail = newNode;		  
			   m_Size++;
		  }
	 }	
	 ALLTYPE *getArray() {
		   int index = 0;
		   ALLTYPE *array = new ALLTYPE[m_Size];
		   cDataType<ALLTYPE> *ptr = NULL;
		   ptr = p_Head;
		   while( ptr->p_Next != NULL ) {  // !#### Causes error here, or if set to ptr == NULL
				array[index] = ptr->Data;     // !#### Causes error here
				ptr = ptr->p_Next;
				index++;
		   }
		   return array;
	 }
	 int getSize() { return m_Size; }
};
#endif
It is being called here

glDrawElements( GL_TRIANGLE_STRIP, (indexArray->getSize()) -256, GL_UNSIGNED_INT, indexArray->getArray() );
and initialized here

indexArray   = new cArray<unsigned int>();


indexArray->Add( 0 );

	 int ySize = TERRAIN_DEPTH - 1;	   // Height of array
	 int xSize = TERRAIN_DEPTH * 2;	   // Width of array
	 unsigned int index  = TERRAIN_DEPTH;		  // First, Third, Fifth ... etc row
	 unsigned index2 = (TERRAIN_DEPTH*3)-1;	// Secound, Fourth Sixth ... etc row
	 // Fill the array
	 for( int y = 0; y < ySize; y+=2 ) {
		  for( int x = 0; x < xSize; x+=2 ) {							  
			   indexArray->Add( index++ );
			   indexArray->Add( index-TERRAIN_DEPTH );
		  }
		  indexArray->Drop();
		  for( int x = 0; x < xSize; x+=2 ) {			  
			   indexArray->Add( index2-- );
			   indexArray->Add( index2-TERRAIN_DEPTH );		  
		  }
		  indexArray->Drop();

		  index  = index  + TERRAIN_DEPTH;
		  index2 = index2 + (TERRAIN_DEPTH*3);
	 }

Thanks for any help !

Edited by mcgrane66, 10 May 2012 - 07:04 PM.


Sponsor:

#2 JTippetts   Moderators   -  Reputation: 8492

Like
3Likes
Like

Posted 10 May 2012 - 07:22 PM

First of all, you've got a memory leak. Every time you draw, you call getArray which allocates a chunk of data using new. That memory is never deleted, and a new chunk is allocated each time. This is going to blow up in your face. Any time you want to do something along the lines of function(foo->getArray()), if foo->getArray() allocates using new and returns the allocated pointer, you will leak. You always, always want to assign to a temporary first, so that you can delete the temporary: temp=foo->getArray(); function(temp); delete[] temp;

Second... ew. Are you sure you want to do a (possibly large) memory allocation plus an iteration of a pointer-based linked list every single time you draw something? Because surely you could figure out a better approach than that? Even if you just implemented it as a std::vector-style dynamically managed array, at least the allocation penalty would be amortized over time if the array was added to, rather than occurring every single frame. And iterating a pointer-based list is just not something you should be doing in every draw call and every frame, if you can possibly avoid it. Drawing is still one of the most highly performance-sensitive parts of the loop, and you really ought to streamline it.

Third, what is wrong with using the rigorously tested standard library? Are you on a platform that has poor/no support for it, or are you just suffering from roll-your-own syndrome?

Edited by JTippetts, 10 May 2012 - 07:27 PM.


#3 McGrane   Members   -  Reputation: 1090

Like
0Likes
Like

Posted 11 May 2012 - 04:33 AM

Thanks for the reply JTippetts! I feel abit thick about the memory leak, this is something i had fixed previously, then seem to have back tracked at some stage that i don't remember Posted Image, i had pointers and all set up for it.

Second... ew.

I thought it was funny that my code disgusted you ha, What i am using this for is for loading heightmaps, i have all the heights stored in an array, and was just making a function that would calculate the indices of all the triangles in a triangle strip. I was only planning to do this once at Initialize time - are using linked lists for this a bad idea for this?? And no this isint a case of

roll-your-own syndrome

, its more a case of 'know no better syndrome'. I have never used vectors before, and may look into them by the sounds of it Posted Image
For a learning curve anyway, i thought that maybe the excess memory was causing the Access Violation, but it is still happening in the while loop.. Why would this be, am i doing this incorrectly?

Edited by mcgrane66, 11 May 2012 - 04:37 AM.


#4 JTippetts   Moderators   -  Reputation: 8492

Like
4Likes
Like

Posted 11 May 2012 - 06:39 AM

If you only build the heightmap at initialize time, then just allocate an array once and don't worry about the linked list. Linked lists are meant to solve a particular class of problems that involve fast insertions and deletions. If you're not going to be inserting and deleting all the time, then a linked list probably isn't appropriate. glDrawElements wants an array, so you should build an array right from the start.

std::vector is such an array type, but one that is dynamically managed. It supports the operation push_back (similar to your Add method) and it will dynamically resize itself if you try to push to a full array. You can either set the size of the vector manually (if you know before-hand how many elements you will need) or you can just let it manage itself, though this might result in some wasted space. Either way, using it with glDrawElements is easy, and you don't have to worry about it leaking.

Finally, if you do actually need a linked list for something, std::list is already implemented, well-supported, and probably bug free.

Your getArray() seems kind of suspicious to me, at any rate.
ALLTYPE *getArray() {
				   int index = 0;
				   ALLTYPE *array = new ALLTYPE[m_Size];
				   cDataType<ALLTYPE> *ptr = NULL;
				   ptr = p_Head;
				   while( ptr->p_Next != NULL ) {  // !#### Causes error here, or if set to ptr == NULL
								array[index] = ptr->Data;	 // !#### Causes error here
								ptr = ptr->p_Next;
								index++;
				   }
				   return array;
		 }

To me, it looks like it will always drop the last element in the list, since when you get to that last element, ptr->Next will be null, so that element doesn't get added to the array. The fact that your segfault occurs at the while() line tells me that ptr is Null when you are trying to access it. A more appropriate way to structure that would be while(ptr!=NULL){. That way, the last element isn't skipped, and you are not trying to access a NULL pointer to get its Next member.

Your Drop method seems dodgy since you don't handle the special case of calling Drop on an empty list, which will segfault as it stands. Also, if you call Drop on a list with only one element, Head is never set to NULL; it will always stay pointing at the first node inserted, even after that node is removed and deleted. Segfault sandwich, baby.

I have to get to work soon, so I can't really look at it a whole lot longer, but I suspect you probably have problems in Add as well. (Just a first glance tells me that if you Drop from a 1-node list then call Add, you'll get a segfault, since Head won't be NULL, thus triggering the else clause, but Tail will be null, thus triggering a segfault when you try to assign to Tail->Next.)

While I highly recommend using std::list over your own implementation, if you are interested (as an academic exercise) in implementing a link list, you ought to brush up on how the operations are supposed to work. You should be able to find pseudocode for the common operations easily enough on the net. When implementing abstract data types, always pay particular attention to the edge cases and exceptions. They will get you every time. If you ever attempt to access ptr->Next, make danged sure that ptr is not NULL, since that triggers a segfault. Make sure, too, that ptr is never pointing at memory that has been deleted. Because, again, segfault.

Edited by JTippetts, 11 May 2012 - 06:44 AM.


#5 McGrane   Members   -  Reputation: 1090

Like
0Likes
Like

Posted 11 May 2012 - 08:19 AM

Thanks again, i know there are problems with the drop methods, as at the minute it was only used after the for loops had filled in the indexArray, to just delete one excess entry
for( ... ) { 
    Add( ... )
    Add( ... )
}
Drop(); // Last excess item
But thats just laziness, on my behalf. As for the while loop, i originally was using while( ptr != NULL ), but then i was getting a segmant fault on the last line, ptr = ptr->next; Presumably if i just used an if statment so as to not asign it to null, this may stop it, but would that not cause an infinite loop, considering its waiting for ptr to be NULL ?

Thanks for the help anyway, i will just look into the methods you said and use them, it was just to learn from my mistakes that i wanted to know.

#6 FLeBlanc   Crossbones+   -  Reputation: 3101

Like
0Likes
Like

Posted 11 May 2012 - 08:29 AM

The mistakes here seem to be sloppy programming and laziness. Your ptr doesn't have to be null in order to raise a segfault; if it's an invalid pointer such as would be the case, as JTippetts pointed out, in a number of circumstances then it'll still segfault, even though the pointer is not null.

Take the time to do things right, check your conditions, stop being lazy. It's lazy programming that leads to mistakes. How much time did you save yourself by being lazy, considering the debugging time you've wasted, the forum posting time you've wasted, etc?

#7 McGrane   Members   -  Reputation: 1090

Like
0Likes
Like

Posted 11 May 2012 - 08:53 AM

I dont feel that i wasted anytime, the debug literally took 10 seconds, and by posting to the boards i learned something that would have took me alot longer to figure out myself if ever. All i consider here for lazy programming is not checking for empty list when dropping a node, but as i just said i only left them out because at the minute this will never be the case, it is only used to remove one unused element added by a for loop. I was making this more as a proof of concept for myself, and something to learn from, your comment however does not add to this topic, clear up anything, nor in anyway is help-full, it to me just seems you've wasted your time writting a message to say stop being lazy. This is an obvious suggestion.
Thanks anyway

#8 FLeBlanc   Crossbones+   -  Reputation: 3101

Like
-2Likes
Like

Posted 11 May 2012 - 10:00 AM

I didn't mean that as an attack, just more along the lines of advice from someone who has made plenty of mistakes by being lazy. I still make mistakes. But here's the thing: if you come on here posting code that you know is sloppy (you admitted it) then you a) waste someone elses time, who points out mistakes you already know are mistakes and b) hide the bug you are trying to find behind a whole slew of other bugs. The problem you ask about needs to be pared down to the actual problem, not the problem disguised by a raft of other problems. You asked about why you would be getting a segfault in your while loop, when it is immediately obvious that there are so many places in your code where invalid pointers could slip through the cracks that narrowing in on the specific time and place that it happens is kind of difficult, made more difficult by the fact that you admittedly posted lazy code, rather than posting code that you made the effort to write as correctly as possible.

#9 ApochPiQ   Moderators   -  Reputation: 15728

Like
0Likes
Like

Posted 11 May 2012 - 11:44 AM

I didn't mean that as an attack, just more along the lines of advice from someone who has made plenty of mistakes by being lazy. I still make mistakes. But here's the thing: if you come on here posting code that you know is sloppy (you admitted it) then you a) waste someone elses time, who points out mistakes you already know are mistakes and b) hide the bug you are trying to find behind a whole slew of other bugs. The problem you ask about needs to be pared down to the actual problem, not the problem disguised by a raft of other problems. You asked about why you would be getting a segfault in your while loop, when it is immediately obvious that there are so many places in your code where invalid pointers could slip through the cracks that narrowing in on the specific time and place that it happens is kind of difficult, made more difficult by the fact that you admittedly posted lazy code, rather than posting code that you made the effort to write as correctly as possible.



Chill out.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS