Bidyut Bidyut - 3 months ago 15
C++ Question

How to use destructor to clear Linked List memory, without having valgrind errors? [Update: Operator Overload help]

I'm trying to debug my code through valgrind, and I see

invalid free()
issue. It seems my
frees
are more than my
allocs
.

The valgrind output is as follows:

==11814== Memcheck, a memory error detector
==11814== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==11814== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==11814== Command: ./doublyLinkedList -v --leak-check=full
==11814==
==11814== Invalid read of size 8
==11814== at 0x400A7A: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:92)
==11814== by 0x400DD1: main (doublyLinkedList.cpp:175)
==11814== Address 0x5a87c88 is 8 bytes inside a block of size 24 free'd
==11814== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11814== by 0x400A90: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:93)
==11814== by 0x400DC5: main (doublyLinkedList.cpp:178)
==11814== Block was alloc'd at
==11814== at 0x4C2A0FC: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11814== by 0x4009B5: DLinkedList::DLinkedList(int) (doublyLinkedList.cpp:57)
==11814== by 0x400D90: main (doublyLinkedList.cpp:175)
==11814==
==11814== Invalid free() / delete / delete[] / realloc()
==11814== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11814== by 0x400A90: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:93)
==11814== by 0x400DD1: main (doublyLinkedList.cpp:175)
==11814== Address 0x5a87c80 is 0 bytes inside a block of size 24 free'd
==11814== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11814== by 0x400A90: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:93)
==11814== by 0x400DC5: main (doublyLinkedList.cpp:178)
==11814== Block was alloc'd at
==11814== at 0x4C2A0FC: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11814== by 0x4009B5: DLinkedList::DLinkedList(int) (doublyLinkedList.cpp:57)
==11814== by 0x400D90: main (doublyLinkedList.cpp:175)
==11814==
==11814==
==11814== HEAP SUMMARY:
==11814== in use at exit: 72,704 bytes in 1 blocks
==11814== total heap usage: 3 allocs, 4 frees, 72,752 bytes allocated
==11814==
==11814== LEAK SUMMARY:
==11814== definitely lost: 0 bytes in 0 blocks
==11814== indirectly lost: 0 bytes in 0 blocks
==11814== possibly lost: 0 bytes in 0 blocks
==11814== still reachable: 72,704 bytes in 1 blocks
==11814== suppressed: 0 bytes in 0 blocks
==11814== Rerun with --leak-check=full to see details of leaked memory
==11814==
==11814== For counts of detected and suppressed errors, rerun with: -v
==11814== ERROR SUMMARY: 4 errors from 2 contexts (suppressed: 0 from 0)


For reference, my Doubly Linked List code is as follows:
(I understand I'm not freeing the reverse pointers, but even before I could get to it, I can't seem to get the one way free.)

#include <iostream>

class Node {
friend class DLinkedList;
private:
Node *_pPrev;
Node *_pNext;
int _data;

public:
Node(): _pPrev(nullptr), _pNext(nullptr) { }
Node(int d): _data(d), _pPrev(nullptr), _pNext(nullptr) { }
Node(int d, Node *p, Node *n): _data(d), _pPrev(p), _pNext(n) { }

// Getters
const int getData() {
return _data;
}

const Node* getPreviousNode() {
return _pPrev;
}

const Node* getNextNode() {
return _pNext;
}
};

class DLinkedList {
private:
Node *_pHead;
Node *_pTail;

public:
DLinkedList();
DLinkedList(int d);
DLinkedList(Node *n);
DLinkedList(const DLinkedList &dLList); // Copy Constructor
~DLinkedList(); // Destructor

const DLinkedList operator+(const DLinkedList &dLList) const;
DLinkedList& operator=(const DLinkedList &dLList); // Assignment operator overload

void listDisplay();
void reverseListDisplay();
void append(int d);
void append(Node *n);
void append(const DLinkedList &dLList);
};

DLinkedList::DLinkedList() {
_pHead = _pTail = nullptr;
}

DLinkedList::DLinkedList(int d) {
_pHead = new Node(d, nullptr, nullptr);
_pTail = _pHead;
}

DLinkedList::DLinkedList(Node *n) {
_pHead = n;
_pTail = _pHead;
}

DLinkedList::DLinkedList(const DLinkedList &dLList) {
_pHead = dLList._pHead;
_pTail = dLList._pTail;
}

DLinkedList& DLinkedList::operator=(const DLinkedList &dLList) {
return *this;
}

DLinkedList::~DLinkedList() {
while (Node *currentHead = _pHead) {
Node *next = currentHead->_pNext;
_pHead = currentHead->_pNext;
delete currentHead;
}
}

const DLinkedList DLinkedList::operator+(const DLinkedList &dLList) const {
DLinkedList temp(*this);

temp._pTail->_pNext = dLList._pHead;
temp._pTail->_pNext->_pPrev = temp._pTail;
temp._pTail = dLList._pTail;

return temp;
}

void DLinkedList::listDisplay() {
if (_pHead == nullptr) {
std::cout << "List is empty!" << std::endl;
return;
}

Node *it = _pHead;
while (it != nullptr) {
std::cout << it->_data << std::endl;
it = it->_pNext;
}
std::cout << std::endl;
}

void DLinkedList::reverseListDisplay() {
if (_pHead == nullptr) {
std::cout << "List is empty!" << std::endl;
return;
}

Node *it = _pTail;
while (it != nullptr) {
std::cout << it->_data << std::endl;
it = it->_pPrev;
}
std::cout << std::endl;
}

void DLinkedList::append(int d) {
if (_pHead == nullptr) {
_pHead = new Node(d, nullptr, nullptr);
_pTail = _pHead;
return;
}

Node *n = new Node(d, _pTail, nullptr);
_pTail->_pNext = n;
_pTail = _pTail->_pNext;
}

void DLinkedList::append(Node *n) {
if (_pHead == nullptr) {
_pHead = n;
_pTail = _pHead;
return;
}

_pTail->_pNext = n;
_pTail->_pNext->_pPrev = _pTail;
_pTail = _pTail->_pNext;
}

void DLinkedList::append(const DLinkedList &dLList) {
_pTail->_pNext = dLList._pHead;
_pTail->_pNext->_pPrev = _pTail;
_pTail = dLList._pTail;
}

int main() {
DLinkedList listA(10);
listA.append(20);

DLinkedList listB(listA);
}


I'm following the Rule of Three. Can someone please point towards the right direction to understand why I'm seeing this? I've researched and tried many different implementations, but some just break it even worse. Specifically, the problem seems to occur when
DLinkedList listB(listA);
is called inside
main()
.

UPDATE:
Thanks to the help from you guys, I was able to figure out the problem. But now, in extension, I'm running into similar issues with the operator overloads. Thank you for helping me out. Would appreciate some "pointers" in the right direction. Valgrind and code posted below:

==30270== Memcheck, a memory error detector
==30270== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==30270== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==30270== Command: ./doublyLinkedList
==30270==
10
20
30

30
20
10

10
20
30
10
20
30

==30270== Invalid read of size 8
==30270== at 0x400C31: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:119)
==30270== by 0x400F83: main (doublyLinkedList.cpp:189)
==30270== Address 0x5a87da8 is 8 bytes inside a block of size 24 free'd
==30270== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30270== by 0x400C47: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:120)
==30270== by 0x400F77: main (doublyLinkedList.cpp:193)
==30270== Block was alloc'd at
==30270== at 0x4C2A0FC: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30270== by 0x400A57: DLinkedList::DLinkedList(DLinkedList const&) (doublyLinkedList.cpp:73)
==30270== by 0x400F2B: main (doublyLinkedList.cpp:189)
==30270==
==30270== Invalid free() / delete / delete[] / realloc()
==30270== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30270== by 0x400C47: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:120)
==30270== by 0x400F83: main (doublyLinkedList.cpp:189)
==30270== Address 0x5a87da0 is 0 bytes inside a block of size 24 free'd
==30270== at 0x4C2B1C6: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30270== by 0x400C47: DLinkedList::~DLinkedList() (doublyLinkedList.cpp:120)
==30270== by 0x400F77: main (doublyLinkedList.cpp:193)
==30270== Block was alloc'd at
==30270== at 0x4C2A0FC: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30270== by 0x400A57: DLinkedList::DLinkedList(DLinkedList const&) (doublyLinkedList.cpp:73)
==30270== by 0x400F2B: main (doublyLinkedList.cpp:189)
==30270==
==30270==
==30270== HEAP SUMMARY:
==30270== in use at exit: 72,704 bytes in 1 blocks
==30270== total heap usage: 11 allocs, 13 frees, 73,944 bytes allocated
==30270==
==30270== LEAK SUMMARY:
==30270== definitely lost: 0 bytes in 0 blocks
==30270== indirectly lost: 0 bytes in 0 blocks
==30270== possibly lost: 0 bytes in 0 blocks
==30270== still reachable: 72,704 bytes in 1 blocks
==30270== suppressed: 0 bytes in 0 blocks
==30270== Rerun with --leak-check=full to see details of leaked memory
==30270==
==30270== For counts of detected and suppressed errors, rerun with: -v
==30270== ERROR SUMMARY: 6 errors from 2 contexts (suppressed: 0 from 0)


Only posting the operator overloads, copy constructor, and destructor:

DLinkedList::DLinkedList(const DLinkedList &dLList){

Node *n1 = nullptr; // Current
Node *n2 = nullptr; // Next

if (dLList.pHead_ == nullptr) {
pHead_ = nullptr;
} else {
pHead_ = new Node();
pHead_->data_ = dLList.pHead_->data_;

n1 = pHead_;
n2 = dLList.pHead_->pNext_;
}

while (n2) {
Node *prev = n1;
n1->pNext_ = new Node();
n1 = n1->pNext_;
n1->pPrev_ = prev;
n1->data_ = n2->data_;

n2 = n2->pNext_;
}

pTail_ = n1;
n1->pNext_ = nullptr;
}

DLinkedList& DLinkedList::operator=(const DLinkedList &dLList) {
DLinkedList temp(dLList);
std::swap(temp.pHead_, pHead_);
return *this;
}

DLinkedList& DLinkedList::operator+=(const DLinkedList &dLList) {
(*this).pTail_->pNext_ = dLList.pHead_;
(*this).pTail_->pNext_->pPrev_ = (*this).pTail_;
(*this).pTail_ = dLList.pTail_;
return *this;
}

const DLinkedList DLinkedList::operator+(const DLinkedList &dLList) const {
DLinkedList temp = *this;

temp += dLList;
return temp;
}

DLinkedList::~DLinkedList() {

Node *currentHead = pHead_;
Node *currentTail = pTail_;
while (Node *currentHead = pHead_) {
pHead_ = currentHead->pNext_;
delete currentHead;
}
pHead_ = nullptr;
pTail_ = nullptr;
}

Answer

You are "following" the Rule of Three but you haven't understood what the rules about at all:

DLinkedList::DLinkedList(const DLinkedList &dLList) {
    _pHead = dLList._pHead;
    _pTail = dLList._pTail;
}

This implementation is what the generated default constructor would do. You need to actually copy the elements. As is, you just copy the pointers and the destructors of both the copy and the original will delete the same elements.

Comments