Double free problem (linked list)

[red vintage]

Hi there!

I implemented a linked list as a class in C++. Such a linked list just contains three pointers (to the first, the last and the current element, an element is implemented as another class and keeps the reference to its preceding and subsequent elements) as protected variables and some member functions.

The destructor frees all the elements 'between' the first and the last element.

Now if I dublicate such a linked list, that is, the pointers from the one linked list are replaced by the pointers from the other one, I can work perfectly with both lists.
But in the end, the program terminates due to a segmentation fault. Using valgrind I found out that a double free might be the problem.

Do you have any suggestions how I can avoid the double free of the two lists?

The dustructor is implemented as follows:

Element_List::~Element_List() {

	deleteList();
}

where

int Element_List::deleteList (void) {

	Element *deleteElement;
	Element *deleteNextElement;

	if (mem_pFirst != 0) {

		deleteElement = mem_pFirst;

		while (deleteElement) {

			deleteNextElement = deleteElement->getNext();
			delete(deleteElement);
			deleteElement = deleteNextElement;
		}

	mem_pFirst = 0;
	mem_pEnd = 0;
	mem_pCurrent = 0;

	return (0);
	}
	else return (1);
}

Thanks in advance!

[LaboPie]

If you duplicate a list simply copying the pointer from a variable to another, then it's a called crash, beacuse the second time that delete it's called on the previous deleted memory, the program crash.
You should declare a new pointer and then assign the value of the first to the new created (but this way it's pretty expensive memory side).

[discofire]

Just so I'm sure I understand how you are "copying" your lists.

You are creating two lists:
Element_List A;
Element_List B;

puplating list A with some stuff
Then making a "copy" of A into B?

ie. B = A is effectively doing the following?

B.mem_pFirst = A.mem_pFirst;
B.mem_pEnd = A.mem_pEnd;
B.mem_pCurrent = A.mem_pCurrent;

If that is the case, I have to ask a few questions first.

1) Why are you doing this? If you already have the contents in A, shouldn't you just reference that object directly?

2) What happens if you iterate through B to element 5 (just assuming you have a bunch of stuff in your list)
Then you iterate through A to element 5 and remove it from the list. At that point presumably you would free that memory as well.
B.mem_pCurrent is now pointing to an invalid memory space and will seg fault if you try to access it.

Even more simply, what happens if you now add an element to A? B.mem_pEnd will still be pointing to the old end of the list, and won't see the new element.

Basically what you are doing is very dangerous, and the double-free problem you are running into is only the tip of the ice berg. I suspect you will run into a lot of seg faults if you continue to link two instances of your list together like this.

Your list copy should be copying the actual contents of the list from one to the other. Effectively building a new list from the contents of the old. That way you can do whatever you want to list A (including delete it) without affecting list B.

[red vintage]

Hi LaboPie and discofire,

what I really need to do in my program is to swap the pointers of the lists A and B, which can be simply done by

void Element_List::swapList(Element_List &swap) {

	Element *temp_mem_pFirst;
	Element *temp_mem_pEnd;
	Element *temp_mem_pCurrent;

	temp_mem_pFirst = mem_pFirst;
	temp_mem_pEnd = mem_pEnd;
	temp_mem_pCurrent = mem_pCurrent;

	mem_pFirst = swap.mem_pFirst;
	mem_pEnd = swap.mem_pEnd;
	mem_pCurrent = swap.mem_pCurrent;

	swap.mem_pFirst = temp_mem_pFirst;
	swap.mem_pEnd = temp_mem_pEnd;
	swap.mem_pCurrent = temp_mem_pCurrent;
}

.

So the answer to your first question, discofire, is that the problem that I described in my opening post only occured when I implemented the destructor. But it made me curious.

I should have emphasized that I don't really have a programming problem but I wondered which solution there might be if I had some kind of this problem. (That is, how to prevent such a double free.)

Concerning your second question: Yes, I could not work with both lists in parallel. I thought that this linked is just a good example for the problem I mentioned above.

[discofire]

You can use smart pointers to handle the cleanup. They're available in C++11, but you'll have to look up the details since I don't have much experience with them. Effectively they do reference counting, and will auto-delete when there are no more references.

Look at the section on shared_ptr here:
http://en.wikipedia.org/wiki/Smart_pointer