This topic is 2082 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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

##### Share on other sites
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 , 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

[background=rgb(250, 251, 252)]roll-your-own syndrome[/background]

, 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
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

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
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

Chill out.