dimanche 27 novembre 2022

C++: free(): double free detected in tcache 2 problem when merging two linked list

I am trying merge two list in C++. My implementation are below:

listnode.h

#ifndef __LISTNODE_H
#define __LISTNODE_H

template< class NODETYPE > class List;

template <class NODETYPE>
class ListNode
{
    friend class List< NODETYPE >;
private:
    NODETYPE data;
    ListNode* next;

public:
    ListNode(const NODETYPE &);
    ~ListNode() {};
    NODETYPE getData() const;
    ListNode<NODETYPE>* getNext() const;
};

template< class NODETYPE >
ListNode<NODETYPE>::ListNode(const NODETYPE& data)
    :data(data),
     next(0)
{ }  // empty ctor body

template< class NODETYPE >
NODETYPE ListNode<NODETYPE>::getData() const { return data; }

template< class NODETYPE >
ListNode<NODETYPE>* ListNode<NODETYPE>::getNext() const { return next; }

#endif

list.h

#ifndef __LIST_H
#define __LIST_H

#include "listnode.h"
#include <iostream>
#include <new>
#include <cstdlib>

template <class NODETYPE>
class List
{
private:
    ListNode<NODETYPE>* firstPtr;
    ListNode<NODETYPE>* lastPtr;
    ListNode<NODETYPE>* getNewNode(const NODETYPE&);

public:
    List();
    ~List();
    void insertFromFront(const NODETYPE&);
    void insertAtBack(const NODETYPE&);
    bool removeFromFront(const NODETYPE&);
    bool removeFromBack(const NODETYPE&);
    bool isEmpty() const;
    void print() const;
    ListNode<NODETYPE>* getFirstNode() const;
    ListNode<NODETYPE>* getLastNode() const;
    void sort();
    void concatenate(List<NODETYPE>);
};

template< class NODETYPE >
List<NODETYPE>::List()
    : firstPtr(0),
      lastPtr(0)
{// empty ctor body}

template< class NODETYPE >
List<NODETYPE>::~List() {
    
    ListNode<NODETYPE> *iter = firstPtr, *temp;
    if(!isEmpty()) {
        while (iter) {
            temp = iter;
            iter = iter->next;
            delete temp;
        }
    }
}

template< class NODETYPE >
void List<NODETYPE>::insertFromFront(const NODETYPE& value) {

    ListNode<NODETYPE> *newNode = getNewNode(value);
    
    if (newNode) {
        if (isEmpty())
            firstPtr = lastPtr = newNode;
        else {
            newNode -> next = firstPtr; // newNode->next points whereever firstPtr points to.
            firstPtr = newNode;         // firstPtr now demonstrates the first nodeç
        }
    } else {
        std::cerr << "Allocation failed!" << std::endl;
        exit(EXIT_FAILURE);
    }
}

template< class NODETYPE >
void List<NODETYPE>::insertAtBack(const NODETYPE& value) {

    ListNode<NODETYPE> *newNode = getNewNode(value);
    if (newNode) {
        if(isEmpty())
            firstPtr = lastPtr = newNode;
        else {
            
            lastPtr -> next = newNode;
            lastPtr = newNode;
            
        }   
    } else {
        std::cerr << "Allocation fails!" << std::endl;
        exit(EXIT_FAILURE); // terminate the program
    }
}

template< class NODETYPE >
bool List<NODETYPE>::removeFromFront(const NODETYPE& value) {

    ListNode<NODETYPE>* temp;
    
    if(isEmpty()) {
        return false;
    }

    if(firstPtr == lastPtr) { // if only one node present
        value = firstPtr -> data;
        firstPtr = lastPtr = 0;
        return true;
    }

    temp = firstPtr;
    value = temp -> data;
    firstPtr = firstPtr -> next;
    delete temp;

    return true;

} 

template< class NODETYPE >
bool List<NODETYPE>::removeFromBack(const NODETYPE& value) {

    if (isEmpty())
        return false;
    
    if(firstPtr == lastPtr) { // if only one node present
        value = lastPtr->data;
        firstPtr = lastPtr = 0;
        return true;
    }

    ListNode<NODETYPE> *iter = firstPtr;
    while (iter != lastPtr)
        iter = iter->next;
    
    lastPtr = iter;             // alter the point lastPtr points to.
    value = iter->next->data;   // grab the value of last node
    delete iter->next;          // delete the last node
    
    return true;

}

template< class NODETYPE >
bool List<NODETYPE>::isEmpty() const {
    return firstPtr == 0;
}

template< class NODETYPE >
void List<NODETYPE>::print() const {
    ListNode<NODETYPE> *iter = firstPtr;
    while(iter) {
        std::cout << iter->data << ' ';
        iter = iter->next;
    }
    std::cout << std::endl << std::endl;
}

template< class NODETYPE >
void List<NODETYPE>::sort() {
    NODETYPE min = firstPtr -> data;
    for (ListNode<NODETYPE>* i = firstPtr; i != 0; i = i -> next) {
        for (ListNode<NODETYPE>* j = i -> next; j != 0; j = j -> next) {
            if(j->data < i->data){
                NODETYPE temp = i->data;
                i->data = j->data;
                j->data = temp;
            }
        }
    }
}

template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getNewNode(const NODETYPE &value) {
    return new ListNode<NODETYPE>(value);
}

template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getFirstNode() const { return firstPtr; }

template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getLastNode() const { return lastPtr; }

template< class NODETYPE >
void List<NODETYPE>::concatenate(List<NODETYPE> l) {
    
    ListNode<NODETYPE>* iter = l.getFirstNode(); // first node of the second linked list
    while (iter != 0){
        insertAtBack(iter->getData());
        iter = iter->next;
    }
    sort(); // to sort in ascending order
    //std::cout << "lastPtr->data:" << lastPtr->data << std::endl;
}

#endif

main.cpp

#include <iostream>
#include "list.h"
#include <cstdlib>
#include <ctime>

template < class NODETYPE>
List<NODETYPE> mergeHandler(List<NODETYPE> list1, List<NODETYPE> list2) {
    
    List<NODETYPE> resultList;
    NODETYPE min = list1.getFirstNode()->getData();
    for (ListNode<NODETYPE>* i = list1.getFirstNode(); i != 0; i = i -> getNext()) {
        
    }
    resultList.print();
    return resultList;
}

int main(int argc, char *argv[]) {
    
    List< int > intList1, intList2/*, mergedList*/;
    srand(time(NULL));
    
    for (size_t i = 0; i < 10; i++) 
        intList1.insertFromFront(1 + rand() % 100);
    
    for (size_t i = 0; i < 10; i++) 
        intList2.insertFromFront(1 + rand() % 100);
    
    //intList1.print();
    //intList1.sort();
    intList1.print();

    //intList2.print();
    //intList2.sort();
    intList2.print();

    intList1.concatenate(intList2);
    intList1.sort();
    intList1.print();

    return 0;
}

The problem is, as mentioned, that at the end of the program, it yields

free(): double free detected in tcache 2
Aborted (core dumped)

I couldn't understand the problem. Because I created new nodes to the first list and add the values of the second list. So even if I delete the same values, I delete the values stored exactly different addresses. In of the question, reccomends of implementing copy ctor and = operator. However, I couldn't get and implement it because I use the normal constructor, but when I implement this ctor

public:
.
.
.
List(List<NODETYPE> &rhs){std::cout << "Do nothing in copy ctor" << std::endl;}

It strangly outputs Do nothing in copy ctor even though I use the normal consturctor. How can I handle this issue? I have already a concatenate method and wanna use it, because when I use copy ctor, it throws a segmentation fault error.

Aucun commentaire:

Enregistrer un commentaire