Double Free problem

I am getting a double free error when I run my code and don't know why. The relevant code is just an a* traversal and the double free is happening when I delete my tree. To get the code out of the way, here it is. (tried to get rid of as much irrelevant stuff as I could).

a* traversal -

Code:

---

Path Agent::traverse(Position& end) {

    //std::cout<<"\nTraversing from "<<pos.toString()<<" to "<<end.toString();
    //make tree and add the start position as the root node
    Tree* tree = new Tree(pos);

    //set root node values
    tree->getRoot()->setGValue(0);
    tree->getRoot()->setHValue(getSLDistance(pos,end));
    tree->getRoot()->setFValue();
    tree->getRoot()->setParent(tree->getRoot());

    //make priority queue of todo nodes and add root
    PriorityQueue nodes;
    nodes.push(tree->getRoot());

    //make path to return
    Path result;

    //flag to stop
    bool done = false;

    Tree::Node* parent = tree->getRoot();    //the parent to current for robot tracing
    Tree::Node* current = tree->getRoot();  //best node
    //**grid->setPos(current->getValue().getRow(), current->getValue().getCol(), 'x');  //set initial spot on grid

    //start traversing
    while(!done) {

        //if the queue is empty, there is no path
        if(nodes.isEmpty()) {
            Position temp = find_next_best(*tree, end);
            goal = temp;
            delete tree;
            return traverse(temp);
        }

        //else there are more positions to try
        else {

            //std::cout<<"\nTREE WHEN CURRENT IS "<<current->getValue().toString()<<tree->toString();
            //set the new parent
            parent = current;


            //else, set grid and set current to best node
            //**grid->setPos(current->getValue().getRow(), current->getValue().getCol(), ' ');
            current = nodes.top();
            //**grid->setPos(current->getValue().getRow(), current->getValue().getCol(), 'x');
            //**std::cout<<grid->toString();

            //if agreed to best move, pop off node
            if(current == nodes.top())
                nodes.pop();

            //if we are at the goal, end loop
            if(current->getValue().equals(end))
                done = true;


            //else, traverse further
            else {

                //get successor nodes for current
                std::vector<Position> successors = adjacentPositions(current->getValue());
                //for each successor
                for(int i=0;i<successors.size();i++) {

                    //if not equal to an ancestor node
                    if(!tree->contains(successors.at(i))) {

                        //make temp node for the tree
                        Tree::Node temp(successors.at(i), current);
                        //set the g value to current.gvalue + step cost (step cost is always 1)
                        temp.setGValue(current->getGValue() + 1);
                        //set h value
                        temp.setHValue(getSLDistance(temp.getValue(), end));
                        //set f value
                        temp.setFValue();

                        //make a node* for queue
                        Tree::Node* t = tree->add(temp.getValue(), current);
                        //set function values
                        t->setGValue(temp.getGValue());
                        t->setHValue(temp.getHValue());
                        t->setFValue();

                        //push into queue
                        nodes.push(t);

                    }  //end if successor not an ancestor node
                }  //end for
            }  //end else not at goal
        }  //end else still positions to try
    }  //end while


    //TRACE BACK UP THE NODES TO GET THE PATH
    while(!(current->getValue().equals(tree->getRoot()->getValue()))) {
        result.add(current->getValue());
        current = current->getParent();
    }

    //push root position
    result.add(current->getValue());


    result.reverse();
    delete tree;
    return result;
}  //END TRAVERSE



Position Agent::find_next_best(Tree tree, Position e) {

    Position result;
    Tree::Node* nb = tree.getNodes().at(0);
    for(int i=1;i<tree.getNodes().size();i++) {

        //check straight line distance
        if( tree.getNodes().at(i)->getHValue() < nb->getHValue() )
            nb = tree.getNodes().at(i);

        //if straight line distance is equal, check step cost
        else if( tree.getNodes().at(i)->getHValue() == nb->getHValue() )
            if( tree.getNodes().at(i)->getGValue() < nb->getGValue() )
                nb = tree.getNodes().at(i);

    }  //end for

    result = nb->getValue();
    //std::cout<<"\nFIND NEXT BEST RETURNING: "<<result.toString();
    return result;
}

---

tree.h -

Code:

---

class Tree {

public:

        class Node {

        public:

        Node() {}

        Node(const Node&);

        //! A Constructor
        /*!
        * Sets value to v and parent to p
        */
                Node(Position&, Node*&);
                //! A Destructor
                ~Node();

        //! Clones a Node
        /*!
        * Returns a Node instance whose members are equal to this Node's members
        */
                Node clone(Node*&);

        //! Check if Node is a leaf
        /*!
        * Returns true if Node has zero children
        */
                bool isLeaf();

        //! Getter function for value member
        /*!
        * Returns a reference of the value member
        */
                Position& getValue();

        //! Setter function for value member
        /*!
        * Sets value to v
        */
                void setValue(Position&);

        //! Getter function for parent member
        /*!
        * Returns a reference of the parent member
        */
                Node*& getParent();

        //! Setter function for parent member
        /*!
        * Sets parent to p
        */
        void setParent(Node*&);

        //! Getter function for gvalue member
        /*!
        * Returns value of gvalue member
        */
        double getGValue();

        //! Setter for gvalue member
        /*!
        * Sets gvalue to v
        */
        void setGValue(double);

        //! Getter function for hvalue member
        /*!
        * Returns value of hvalue member
        */
        double getHValue();

        //! Setter function for hvalue member
        /*!
        * Returns value of hvalue member
        */
        void setHValue(double);

        //! Getter function for fvalue member
        /*!
        * Returns value of fvalue member
        */
        double getFValue();

        //! Setter function for fvalue member
        /*!
        * Sets fvalue to v
        */
        void setFValue();

        //! Getter function for children member
        /*!
        * Returns reference of the children member
        */
                std::vector<Node*>& getChildren();

        //! Returns a printable string of the Node
                std::string toString();

                Tree::Node clone();


        Node& operator=(const Node&);

        private:
                double gvalue;
                double hvalue;
                double fvalue;

                Position value;
                Node* parent;
                std::vector<Node*> children;
        };        //END NODE CLASS

    //! Exception class for when a Node is not found
        class NodeNotFoundException : public std::exception {
        public:
                virtual const char* what() const throw();
        };        //end exception


    //! A Constructor
    /*! Sets root to p */
        Tree(Position&);
        //! A Destructor
        ~Tree();

    //! Getter function for root member
    /*! Returns a reference of root member */
        Node*& getRoot();

        std::vector<Node*> getNodes();

    //! Checks if a Position is in the tree
    /*! Returns true if a Position in the tree is equal to p */
    bool contains(Position&);

    //! Add a Position to the tree
    /*! Makes a node for value and adds that node to the tree as one of parent's children */
        Node* add(Position&, Node*&);


    //! Returns a printable string for the root node of the tree
        std::string rootToString();
        //! Returns a printable string of a subtree
        /*!
        * Returns a printable string of a subtree\n
        * Treats t as the root
        */
        std::string toString(Node*&);
        //! Returns a printable string of the while tree
        std::string toString();
private:

        //root of tree
        Node* dummyroot;
        Node* root;

        std::vector<Node*> nodes;

};

#endif

---

tree.cpp with some irrelevant stuff taken out -

Code:

---


Tree::Node::Node(const Node& right) {

    gvalue = right.getGValue();
    hvalue = right.getHValue();
    fvalue = right.getFValue();
    value = right.getValue();
    parent = right.getParent();
    children = right.getChildren();
}


/*Constructor*/
Tree::Node::Node(Position& v, Node*& p) : value(v), parent(p), gvalue(0), hvalue(0), fvalue(0) {}


/*Destructor*/
Tree::Node::~Node() {}



Tree::Node Tree::Node::clone() {return *this;}


Tree::Node& Tree::Node::operator=(const Tree::Node& right) {

        if(this != &right) {

            gvalue = right.getGValue();
            hvalue = right.getHValue();
            fvalue = right.getFValue();
            value = right.getValue();
            parent = right.getParent();
            children = right.getChildren();
        }

        return *this;
}


/*Constructor that sets p as the root value*/
Tree::Tree(Position& p) {
        Node* temp = new Node(p, dummyroot);
        root = temp;
        nodes.push_back(temp);
}  //END CONSTRUCTOR

/*Destructor*/
Tree::~Tree() {
    for(int i=0;i<nodes.size();i++)
        delete nodes.at(i);
}


/*Returns true if p is in the tree*/
bool Tree::contains(Position& p) {
    for(int i=0;i<nodes.size();i++)
        if(p.equals(nodes.at(i)->getValue()))
            return true;
    return false;
}  //END CONTAINS


Tree::Node* Tree::add(Position& value, Node*& parent) {
        Node* temp = new Node(value, parent);
        parent->getChildren().push_back(temp);
        //std::cout<<"\n"<<temp->getValue().toString()<<" added to "<<parent->getValue().toString();
        nodes.push_back(temp);
    return temp;
}  //END ADD

---

When I run the code, I get an error of -

Code:

---

*** glibc detected *** /home/sterling/Desktop/irobot_driverprac/go: double free or corruption (out): 0xb59004d0 ***
======= Backtrace: =========
/lib/i686/cmov/libc.so.6(+0x6b281)[0xb7b7d281]
/lib/i686/cmov/libc.so.6(+0x6cad8)[0xb7b7ead8]
/lib/i686/cmov/libc.so.6(cfree+0x6d)[0xb7b81bbd]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0xb7d57701]
/home/sterling/Desktop/irobot_driverprac/go[0x804f83e]
/home/sterling/Desktop/irobot_driverprac/go[0x804bc4d]
/home/sterling/Desktop/irobot_driverprac/go[0x8059b27]
/home/sterling/Desktop/irobot_driverprac/go[0x8059849]
/lib/i686/cmov/libpthread.so.0(+0x5955)[0xb7fbb955]
/lib/i686/cmov/libc.so.6(clone+0x5e)[0xb7bdde7e]
======= Memory map: ========
08048000-08063000 r-xp 00000000 08:01 2113591    /home/sterling/Desktop/irobot_driverprac/go
08063000-08064000 rw-p 0001b000 08:01 2113591    /home/sterling/Desktop/irobot_driverprac/go
08064000-08085000 rw-p 00000000 00:00 0          [heap]
b5900000-b5921000 rw-p 00000000 00:00 0
b5921000-b5a00000 ---p 00000000 00:00 0
b5a30000-b5a31000 ---p 00000000 00:00 0
b5a31000-b6231000 rw-p 00000000 00:00 0
b6231000-b6232000 ---p 00000000 00:00 0
b6232000-b6a32000 rw-p 00000000 00:00 0
b6a32000-b6a33000 ---p 00000000 00:00 0
b6a33000-b7233000 rw-p 00000000 00:00 0
b7233000-b7234000 ---p 00000000 00:00 0
b7234000-b7a35000 rw-p 00000000 00:00 0
b7a35000-b7a39000 r-xp 00000000 08:01 12913515  /usr/lib/libXdmcp.so.6.0.0
b7a39000-b7a3a000 rw-p 00003000 08:01 12913515  /usr/lib/libXdmcp.so.6.0.0
b7a3a000-b7a3b000 rw-p 00000000 00:00 0
b7a3b000-b7a3d000 r-xp 00000000 08:01 12913513  /usr/lib/libXau.so.6.0.0
b7a3d000-b7a3e000 rw-p 00001000 08:01 12913513  /usr/lib/libXau.so.6.0.0
b7a3e000-b7a56000 r-xp 00000000 08:01 12913517  /usr/lib/libxcb.so.1.1.0
b7a56000-b7a57000 rw-p 00017000 08:01 12913517  /usr/lib/libxcb.so.1.1.0
b7a57000-b7a7b000 r-xp 00000000 08:01 12911203  /usr/lib/libexpat.so.1.5.2
b7a7b000-b7a7d000 rw-p 00023000 08:01 12911203  /usr/lib/libexpat.so.1.5.2
b7a7d000-b7a90000 r-xp 00000000 08:01 12912908  /usr/lib/libz.so.1.2.3.4
b7a90000-b7a91000 rw-p 00013000 08:01 12912908  /usr/lib/libz.so.1.2.3.4
b7a91000-b7a99000 r-xp 00000000 08:01 12913527  /usr/lib/libXrender.so.1.3.0
b7a99000-b7a9a000 rw-p 00007000 08:01 12913527  /usr/lib/libXrender.so.1.3.0
b7a9a000-b7a9b000 rw-p 00000000 00:00 0
b7a9b000-b7b0e000 r-xp 00000000 08:01 12913496  /usr/lib/libfreetype.so.6.6.0
b7b0e000-b7b12000 rw-p 00073000 08:01 12913496  /usr/lib/libfreetype.so.6.6.0
b7b12000-b7c52000 r-xp 00000000 08:01 8307784    /lib/i686/cmov/libc-2.11.2.so
b7c52000-b7c54000 r--p 0013f000 08:01 8307784    /lib/i686/cmov/libc-2.11.2.so
b7c54000-b7c55000 rw-p 00141000 08:01 8307784    /lib/i686/cmov/libc-2.11.2.so
b7c55000-b7c58000 rw-p 00000000 00:00 0
b7c58000-b7c75000 r-xp 00000000 08:01 8290307    /lib/libgcc_s.so.1
b7c75000-b7c76000 rw-p 0001c000 08:01 8290307    /lib/libgcc_s.so.1
b7c76000-b7c9a000 r-xp 00000000 08:01 8307768    /lib/i686/cmov/libm-2.11.2.so
b7c9a000-b7c9b000 r--p 00023000 08:01 8307768    /lib/i686/cmov/libm-2.11.2.so
b7c9b000-b7c9c000 rw-p 00024000 08:01 8307768    /lib/i686/cmov/libm-2.11.2.so
b7c9c000-b7d85000 r-xp 00000000 08:01 12912463  /usr/lib/libstdc++.so.6.0.13
b7d85000-b7d89000 r--p 000e9000 08:01 12912463  /usr/lib/libstdc++.so.6.0.13
b7d89000-b7d8a000 rw-p 000ed000 08:01 12912463  /usr/lib/libstdc++.so.6.0.13
b7d8a000-b7d91000 rw-p 00000000 00:00 0
b7d91000-b7eaa000 r-xp 00000000 08:01 12913521  /usr/lib/libX11.so.6.3.0
b7eaa000-b7eae000 rw-p 00118000 08:01 12913521  /usr/lib/libX11.so.6.3.0
b7eae000-b7eaf000 rw-p 00000000 00:00 0
b7eaf000-b7eb1000 r-xp 00000000 08:01 8307776    /lib/i686/cmov/libdl-2.11.2.so
b7eb1000-b7eb2000 r--p 00001000 08:01 8307776    /lib/i686/cmov/libdl-2.11.2.so
b7eb2000-b7eb3000 rw-p 00002000 08:01 8307776    /lib/i686/cmov/libdl-2.11.2.so
b7eb3000-b7eb5000 r-xp 00000000 08:01 12915615  /usr/lib/libXinerama.so.1.0.0
b7eb5000-b7eb6000 rw-p 00001000 08:01 12915615  /usr/lib/libXinerama.so.1.0.0
b7eb6000-b7ee3000 r-xp 00000000 08:01 12913509  /usr/lib/libfontconfig.so.1.4.4
b7ee3000-b7ee5000 rw-p 0002c000 08:01 12913509  /usr/lib/libfontconfig.so.1.4.4
b7ee5000-b7ef7000 r-xp 00000000 08:01 12915587  /usr/lib/libXft.so.2.1.13
b7ef7000-b7ef8000 rw-p 00011000 08:01 12915587  /usr/lib/libXft.so.2.1.13
b7ef8000-b7f06000 r-xp 00000000 08:01 12915603  /usr/lib/libXext.so.6.4.0
b7f06000-b7f07000 rw-p 0000d000 08:01 12915603  /usr/lib/libXext.so.6.4.0
b7f07000-b7f08000 rw-p 00000000 00:00 0
b7f08000-b7fad000 r-xp 00000000 08:01 418614    /usr/lib/libfltk.so.1.1
b7fad000-b7fb2000 rw-p 000a4000 08:01 418614    /usr/lib/libfltk.so.1.1
b7fb2000-b7fb6000 rw-p 00000000 00:00 0
b7fb6000-b7fcb000 r-xp 00000000 08:01 8307773    /lib/i686/cmov/libpthread-2.11.2.so
b7fcb000-b7fcc000 r--p 00014000 08:01 8307773    /lib/i686/cmov/libpthread-2.11.2.so
b7fcc000-b7fcd000 rw-p 00015000 08:01 8307773    /lib/i686/cmov/libpthread-2.11.2.so
b7fcd000-b7fcf000 rw-p 00000000 00:00 0
b7fde000-b7fe2000 rw-p 00000000 00:00 0
b7fe2000-b7fe3000 r-xp 00000000 00:00 0          [vdso]
b7fe3000-b7ffe000 r-xp 00000000 08:01 8290329    /lib/ld-2.11.2.so
b7ffe000-b7fff000 r--p 0001a000 08:01 8290329    /lib/ld-2.11.2.so
b7fff000-b8000000 rw-p 0001b000 08:01 8290329    /lib/ld-2.11.2.so
bffeb000-c0000000 rw-p 00000000 00:00 0          [stack]

---

with a backtrace of -

Code:

---

#0  0xb7fe2424 in __kernel_vsyscall ()
#1  0xb7b3c751 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#2  0xb7b3fb82 in *__GI_abort () at abort.c:92
#3  0xb7b7318d in __libc_message (do_abort=2,
    fmt=0xb7c37738 "*** glibc detected *** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:189
#4  0xb7b7d281 in malloc_printerr (action=<value optimized out>,
    str=0x6 <Address 0x6 out of bounds>, ptr=0xb59004d0) at malloc.c:6267
#5  0xb7b7ead8 in _int_free (av=<value optimized out>, p=<value optimized out>)
    at malloc.c:4795
#6  0xb7b81bbd in *__GI___libc_free (mem=0xb59004d0) at malloc.c:3739
#7  0xb7d57701 in operator delete(void*) () from /usr/lib/libstdc++.so.6
#8  0x0804f83e in __gnu_cxx::new_allocator<Tree::Node*>::deallocate (this=0x8066900,
    __in_chrg=<value optimized out>) at /usr/include/c++/4.4/ext/new_allocator.h:95
#9  std::_Vector_base<Tree::Node*, std::allocator<Tree::Node*> >::_M_deallocate (
    this=0x8066900, __in_chrg=<value optimized out>)
    at /usr/include/c++/4.4/bits/stl_vector.h:146
#10 ~_Vector_base (this=0x8066900, __in_chrg=<value optimized out>)
    at /usr/include/c++/4.4/bits/stl_vector.h:132
#11 ~vector (this=0x8066900, __in_chrg=<value optimized out>)
    at /usr/include/c++/4.4/bits/stl_vector.h:313
#12 ~Node (this=0x8066900, __in_chrg=<value optimized out>) at tree.cpp:24
#13 ~Tree (this=0x8066900, __in_chrg=<value optimized out>) at tree.cpp:108
#14 0x0804bc4d in Agent::traverse (this=0x8066710, end=...) at agent.cpp:189
#15 0x08059b27 in ServerControl::update_path_thread_i (this=0xbffff38c, client=1)
    at servercontrol.cpp:69
#16 0x08059849 in ServerControl::update_path1_thread (threadid=0xbffff38c)
    at servercontrol.cpp:27
#17 0xb7fbb955 in start_thread (arg=0xb6a31b70) at pthread_create.c:300
#18 0xb7bdde7e in clone () at ../sysdeps/unix/sysv/linux/i386/clone.S:130

---

What I want to do when I delete a tree is just go through the vector of Node* and delete each one.
I have read that not having a copy constructor and overloaded assignment operator can cause this problem with vectors. But I added those and nothing (visible to me) changed.
I think the problem has to with the recursive call in traverse somehow, but if I take out the delete before the recursion call I will have a memory leak because I will not be deleting the tree.
Any help would be very appreciated.

Ouch, I thought those code boxes might give a sliding bar...

Oh and the lines in the trace are -

#12 ~Node (this=0x8066900, __in_chrg=<value optimized out>) at tree.cpp:24

Code:

---

Tree::Node::~Node() {}

---

#13 ~Tree (this=0x8066900, __in_chrg=<value optimized out>) at tree.cpp:108

Code:

---

/*Destructor*/
Tree::~Tree() {
    for(int i=0;i<nodes.size();i++)
        delete nodes.at(i);  //HERE
}

---

#14 0x0804bc4d in Agent::traverse (this=0x8066710, end=...) at agent.cpp:189

Code:

---

        //if the queue is empty, there is no path
        if(nodes.isEmpty()) {
            Position temp = find_next_best(*tree, end);
            goal = temp;
            delete tree;  //HERE
            return traverse(temp);
        }

---

I'm pegging your Tree::Node::clone() as prime suspect. Primarily because it will result in several pointers to the same address.

I would start by deleting these functions:

Code:

---

Tree::Node::Node(const Node& right) {

    gvalue = right.getGValue();
    hvalue = right.getHValue();
    fvalue = right.getFValue();
    value = right.getValue();
    parent = right.getParent();
    children = right.getChildren();
}

Tree::Node::~Node() {}

Tree::Node Tree::Node::clone() {return *this;}

Tree::Node& Tree::Node::operator=(const Tree::Node& right) {

        if(this != &right) {

            gvalue = right.getGValue();
            hvalue = right.getHValue();
            fvalue = right.getFValue();
            value = right.getValue();
            parent = right.getParent();
            children = right.getChildren();
        }

        return *this;
}

---

That code has several no-no's...
Do not check for self-assignment. Any class that requires such a check is clearly not exception safe, and upon being made exception safe such a check is redundant. Read the article on "GotW" about self-assignment.

Secondly, do not even implement the copy-constructor, assignment operator, or destructor when the built in thing will already do the right thing, and in this case it will certainly do it more efficiently than you have here. The default copy-constructor copy-constructs each member. The default assignment operator calls the assignment operator on each member etc. Or if you really do need different behaviour for some of these such as defaulting the new item's list of children to empty, then make the behaviour different.

Thirdly, you appear to have picked up on the virtual clone idiom, but your implementation completely misses the point and as such fails to solve the problem at all. If in fact you wish your clone function to do something other than copy-construction, then you probably do want to modify the copy-constructor afterall.

Fourth, I'd like to introduce you to the idea of const methods. Putting const after the method name is used to indicate that a function does not modify any of its members. As your code is, I cannot believe it compiles because it calls several non-const methods on const objects.

Your tree class also fails to follow the "rule of three". If you don't ever intend the copy-constructor or assignment operator to be called then they should be declared as private and left unimplemented. This prevents their accidental use which would otherwise lead to disaster.