Sign in to follow this  

Linked List Problems

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

If you intended to correct an error in the post then please contact us.

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.

[code]

#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
[/code]
It is being called here
[code]

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

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);
}
[/code]

Thanks for any help ! Edited by mcgrane66

Share this post


Link to post
Share on other sites
First of all, you've got a memory leak. Every time you draw, you call [b]getArray[/b] 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 [i]every single time you draw something[/i]? 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 this post


Link to post
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 [img]http://public.gamedev.net//public/style_emoticons/default/dry.png[/img], i had pointers and all set up for it. [quote name='JTippetts' timestamp='1336699378' post='4939179']Second... ew.[/quote] 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 [quote name='JTippetts' timestamp='1336699378' post='4939179']
[left][background=rgb(250, 251, 252)]roll-your-own syndrome[/background][/left]
[/quote], 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 [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
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 this post


Link to post
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.

[url="http://www.cplusplus.com/reference/stl/vector/"]std::vector[/url] is such an array type, but one that is dynamically managed. It supports the operation [b]push_back[/b] (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,[url="http://www.cplusplus.com/reference/stl/list/"] std::list[/url] is already implemented, well-supported, and probably bug free.

Your getArray() seems kind of suspicious to me, at any rate.
[code]
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;
}
[/code]

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 [b]while(ptr!=NULL){[/b]. That way, the last element isn't skipped, and you are not trying to access a NULL pointer to get its Next member.

Your [b]Drop[/b] 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 this post


Link to post
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
[code]
for( ... ) {
Add( ... )
Add( ... )
}
Drop(); // Last excess item
[/code]
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
[quote name='FLeBlanc' timestamp='1336752017' post='4939329']
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.
[/quote]


Chill out.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this