• Create Account

### #ActualJTippetts

Posted 11 May 2012 - 06:44 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;
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.

### #1JTippetts

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;
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.

PARTNERS