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.
