Doubly circular linked list memory access error

Question

i've been trying to figure it out by my self but I cant figure it out, I've try to implement a doubly circular linked list template class, in purpose to create a menu for an app with SFML.

I dont know why but when i implement an instance of CDblLinkedList (int,string,sf::Text) it work without any error, but when i try to insert in CDblLinkedList an instance of CSubMenu i got an error Exception has occurred. EXC_BAD_ACCESS (code=1, address=0x170). When i debug it i've saw that at the second call of the destructor ~CDblLinkedList(), head->GetPrev()->SetNext(nullptr); generate this error because the prev pointer of the head is equal to nullptr.

CNode.h

#pragma once
template <typename T>
class CNode{

    private:
        CNode<T>*prev=nullptr;
        T data;
        CNode<T>*next=nullptr;

    public:
        CNode(T p_data);
        void SetNext(CNode<T>*p_next){next=p_next;};
        void SetPrev(CNode<T>*p_prev){prev=p_prev;};
        CNode<T>* GetNext(void){return(next);};
        CNode<T>* GetPrev(void){return(prev);};
        T* GetData(void){return(&data);};

};

template <typename T>
CNode<T>::CNode(T p_data):data(p_data){
   // data=p_data;
}

CDblLinkedList.h

#pragma once
#include "CNode.h"
#include <iostream>
template <typename T>
class CDblLinkedList{
    private:
        CNode<T>*head=nullptr,*current=nullptr;
    public:
        CDblLinkedList();
        void Insert(T p_data);
        void Next();
        void Prev();
        CNode<T>*GetCurr(void){return(current);};
        CNode<T>*GetHead(void){return(head);};
        ~CDblLinkedList();
};

template<typename T>
CDblLinkedList<T>::CDblLinkedList(){
}

template<typename T>
void CDblLinkedList<T>::Insert(T p_data){
    CNode<T> * dummy=new CNode<T>(p_data);
    if(!head){
        head=dummy;
        head->SetNext(head);
        head->SetPrev(head);
        current=head;
    }else{
        dummy->SetPrev(head->GetPrev());
        dummy->SetNext(head);
        head->GetPrev()->SetNext(dummy);
        head->SetPrev(dummy);
    }
}
template<typename T>
void CDblLinkedList<T>::Next(){
    current=current->GetNext();
}
template<typename T>
void CDblLinkedList<T>::Prev(){
    current=current->GetPrev();
}

template<typename T>
CDblLinkedList<T>::~CDblLinkedList(){
    if(head){
       head->GetPrev()->SetNext(nullptr);
        CNode<T>* dummy=nullptr;
        while(head){
            dummy=head;
            head=head->GetNext();
            delete dummy;
            dummy=nullptr;
        }
        head=nullptr;
        current=nullptr;
    }
}

main.cpp

#include<SFML/Graphics.hpp>
#include "CSubMenu.h"
int main(){
    sf::RenderWindow window({ 1600 ,900 }, "test");
    sf::Font font;
    font.loadFromFile("./assets/fonts/Oswald-Bold.ttf");
    CSubMenu left(300,450,"AlgoText",font,&window);
    left.AddChoice("1- BFS");
    left.AddChoice("2- DFS");
    left.AddChoice("3- A*");
    CDblLinkedList<CSubMenu>list;
    list.Insert(left);

    return 0;
}

I've try to create separate CSubMenu instance it work, but not when i try to insert one of them in a CDblLinkedList instance.

Thank you in advance :)

Before I even look at the code, have you tried debugging with valgrind? It helps a lot with finding memory related errors. — Refugnic Eternium
– Refugnic Eternium, Commented Mar 14, 2023 at 12:05
Another general advice: Step through your code. Keep an eye on those variables. When does the behaviour differ from what you're expecting? Once you've found that line, you're almost there. — Refugnic Eternium
– Refugnic Eternium, Commented Mar 14, 2023 at 12:07
Why don't you use std::list which is a doubly linked list and instead implement your own solution? — kiner_shah
– kiner_shah, Commented Mar 14, 2023 at 12:24
@kiner_shah because I need a circular doubly linked list, but std::list is not circular — RayanYI
– RayanYI, Commented Mar 14, 2023 at 13:15
@RayanYI -- Use Boost circular buffer. That is, if you value your time. — PaulMcKenzie
– PaulMcKenzie, Commented Mar 14, 2023 at 16:34

leosch · Accepted Answer · 2023-03-15 11:44:52Z

0

Implicit copies

You see multiple destructor calls, because copies of your type T object are created. See your modified code example that shows the constructor/destructor calls. Inserting a single element to list leads to multiple destructor calls, because multiple copies of T are made in the process.

This could explain why using type CDblLinkedList<int> works, but not CDblLinkedList<CSubMenu>. The latter most likely has no proper copy constructor.

There are plenty of ressources that explain this issue. In short: If you copy an object that holds a pointer and then at the end of its lifetime the destructor calls a delete on that pointer, you must write a copy constructor or you will end up with double delete issues. Because both - the original and the copied object - point to same address and therefore try to delete the same thing when destroyed.

Copy locations

First copy occurs when copying the argument in CNode.h:

list.Insert(left);

Second copy: p_data is copied when calling the constructor of CNode while in function CDblLinkedList<T>::Insert:

CNode<T>* dummy = new CNode<T>(p_data);

Third copy: Copy p_data argument to p_data member in CNode<T> constructor:

CNode<T>::CNode(T p_data) : data(p_data) {
    // data=p_data;
}

Solution

A) Provide a bug-free copy constructor for T similar to your modified code example.

B) Avoid copies of T that cause problems by providing a move constructor and then modify the code so that T is moved instead copied.

C) Or decouple lifetime issues from your class CDblLinkedList by only passing it a reference or a pointer to your Item, eg. use CDblLinkedList<CSubMenu&>, as demonstrated in this example on compiler-explorer. Additionally, to prevent unintended copies, explicitly delete the copy constructor: Foo(const Foo& other) = delete;

edited Mar 15, 2023 at 11:44

answered Mar 14, 2023 at 15:00

leosch

5813 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

RayanYI Over a year ago

Thanks you for your explanation, im still having some issues with it i'm still trying to debug it :)

leosch Over a year ago

The answer should be clearer after my edit. If you are stuck, I suggest you post the code for CSubMenu. It can be a reduced version though, as long as the problem can be reproduced.

RayanYI Over a year ago

Yes, it's clearer thanks. I do not know about the rule of 5 in c++, my CSubMenu has a linked list of sf::Text for attribute, i think it should be about the copy, that's why there is a double free memory at the same adress.

Red.Wave Over a year ago

Rule of 0/3/5 is the guideline for RAII. If your class initialization envolves resource aquisition, then the destructor must release it. If any of the 3 special members(copy constructor, assignment operator, destructor) are defined, then the other 2 must be properly defined too; otherwise resource management bugs appear. Rule of 5 regards optimizations involving move construction and move assignment. You have to provide either 0 or 3 or 5 of the special member functions to aviod resource bugs.

RayanYI Over a year ago

@Red.Wave Ok thanks, so even if we use c++11 it's not mandatory to use the rule of 5 we can just use rule of 3 im i right ?

|

Collectives™ on Stack Overflow

Doubly circular linked list memory access error

1 Answer 1

Implicit copies

Copy locations

Solution

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Implicit copies

Copy locations

Solution

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related