Abort signal received for Invalid next free when using topological_sort
BOOST: 1.33.1 GCC: 4.1.1 OS: Fedora Core 6 I am receiving a abort signal from glibc when I am running the test program that is attached. You will find that the program is suppose to create a directed graph of five vertexes. I have printed out how the edges are structured so you will have a picture of the graph. I hope someone is able to help me figure out what is going wrong with this test program. So far I am stumped as to what is wrong. Figuring out the problem and its solution will help me figure out a much larger problem. So the questions I have are: 1. Is there a problem with the definition of the graph? 2. Did I fail to do something in the initialization of the graph? 3. Is this the right forum for me asking my questions? Stephen ----------------------------------------- OUTPUT ----------------------------------------- [storri@localhost infrastructure]$ ./test_dag Added edge: 1 -> 20 Added edge: 1 -> 30 Added edge: 1 -> 40 Added edge: 1 -> 5 Added edge: 20 -> 5 Added edge: 30 -> 5 Added edge: 40 -> 5 *** glibc detected *** ./test_dag: free(): invalid next size (fast): 0x09f08780 *** ======= Backtrace: ========= /lib/libc.so.6[0x47c1709d] /lib/libc.so.6(cfree+0x90)[0x47c1a6f0] /usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0x48058ef1] ./test_dag[0x8053357] ./test_dag[0x8053381] ./test_dag[0x80533bb] ./test_dag[0x8053db1] ./test_dag[0x805f2bd] ./test_dag[0x805f3e9] ./test_dag[0x805f434] ./test_dag[0x805f468] ./test_dag[0x804a858] /lib/libc.so.6(__libc_start_main+0xdc)[0x47bc6f2c] ./test_dag(_ZNSt15basic_streambufIcSt11char_traitsIcEE6xsputnEPKci +0x7d)[0x804a251] ======= Memory map: ======== 003e3000-003e4000 r-xp 003e3000 00:00 0 [vdso] 08048000-08068000 r-xp 00000000 fd:00 3178562 /home/storri/src/libreverse/src/infrastructure/test_dag 08068000-08069000 rwxp 0001f000 fd:00 3178562 /home/storri/src/libreverse/src/infrastructure/test_dag 09f08000-09f29000 rwxp 09f08000 00:00 0 47b94000-47bad000 r-xp 00000000 fd:00 458769 /lib/ld-2.5.so 47bad000-47bae000 r-xp 00018000 fd:00 458769 /lib/ld-2.5.so 47bae000-47baf000 rwxp 00019000 fd:00 458769 /lib/ld-2.5.so 47bb1000-47ce8000 r-xp 00000000 fd:00 458776 /lib/libc-2.5.so 47ce8000-47cea000 r-xp 00137000 fd:00 458776 /lib/libc-2.5.so 47cea000-47ceb000 rwxp 00139000 fd:00 458776 /lib/libc-2.5.so 47ceb000-47cee000 rwxp 47ceb000 00:00 0 47cf0000-47d15000 r-xp 00000000 fd:00 458802 /lib/libm-2.5.so 47d15000-47d16000 r-xp 00024000 fd:00 458802 /lib/libm-2.5.so 47d16000-47d17000 rwxp 00025000 fd:00 458802 /lib/libm-2.5.so 47f97000-47fa2000 r-xp 00000000 fd:00 458837 /lib/libgcc_s-4.1.1-20070105.so.1 47fa2000-47fa3000 rwxp 0000a000 fd:00 458837 /lib/libgcc_s-4.1.1-20070105.so.1 47fa5000-48085000 r-xp 00000000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 48085000-48088000 r-xp 000e0000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 48088000-4808a000 rwxp 000e3000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 4808a000-48090000 rwxp 4808a000 00:00 0 b7e00000-b7e21000 rw-p b7e00000 00:00 0 b7e21000-b7f00000 ---p b7e21000 00:00 0 b7f4c000-b7f4e000 rw-p b7f4c000 00:00 0 b7f60000-b7f62000 rw-p b7f60000 00:00 0 bfa5e000-bfa73000 rw-p bfa5e000 00:00 0 [stack] Aborted ----------------------------------------- GDB OUTPUT ----------------------------------------- (gdb) bt #0 0x009af402 in __kernel_vsyscall () #1 0x47bd9d40 in raise () from /lib/libc.so.6 #2 0x47bdb591 in abort () from /lib/libc.so.6 #3 0x47c0f33b in __libc_message () from /lib/libc.so.6 #4 0x47c1709d in _int_free () from /lib/libc.so.6 #5 0x47c1a6f0 in free () from /lib/libc.so.6 #6 0x48058ef1 in operator delete () from /usr/lib/libstdc++.so.6 #7 0x08053357 in __gnu_cxx::new_allocator<boost::default_color_type>::deallocate (this=0xbfcf7974, __p=0x97fe780) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/ext/new_allocator.h:94 #8 0x08053381 in std::_Vector_base<boost::default_color_type, std::allocator<boost::default_color_type> >::_M_deallocate (this=0xbfcf7974, __p=0x97fe780, __n=5) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:133 #9 0x080533bb in ~_Vector_base (this=0xbfcf7974) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:119 #10 0x08053db1 in ~vector (this=0xbfcf7974) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:272 #11 0x0805f2bd in boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, void*, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, vis= {<boost::dfs_visitor<boost::null_visitor>> = {m_vis = {<> = {<No data fields>}, <No data fields>}}, m_iter = {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}}, start_vertex=0x97fe220, params=@0xbfcf7a34) at /usr/include/boost/graph/depth_first_search.hpp:246 #12 0x0805f3e9 in boost::depth_first_search<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, params=@0xbfcf7a34) at /usr/include/boost/graph/depth_first_search.hpp:324 #13 0x0805f434 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >, int, boost::buffer_param_t, boost::no_property> ( g=@0xbfcf7ac4, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}, params=@0xbfcf7a74) at /usr/include/boost/graph/topological_sort.hpp:64 #14 0x0805f468 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > > (g=@0xbfcf7ac4, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}) at /usr/include/boost/graph/topological_sort.hpp:70 #15 0x0804a858 in main () at test_dag.cpp:256 ------------------------------- TEST PROGRAM -------------------------------- #include <boost/graph/adjacency_list.hpp> #include <boost/shared_ptr.hpp> #include <boost/cstdint.hpp> #include <boost/format.hpp> #include <boost/graph/topological_sort.hpp> #include <iostream> #include <map> class Component; class Graph_Base { public: typedef boost::property< boost::vertex_index_t, boost::uint32_t, boost::property< boost::vertex_name_t, boost::shared_ptr<Component> > > VertexProperty_t; typedef boost::adjacency_list< boost::setS, // OutEdgeList boost::setS, // VertexList boost::directedS, // Directed VertexProperty_t > // VertexProperties Graph_t; typedef boost::adj_list_vertex_property_map<Graph_Base::Graph_t, boost::shared_ptr<Component>, const boost::shared_ptr<Component>&, boost::vertex_name_t> Property_Map_const_t; }; class Component { public: typedef boost::shared_ptr<Component> ptr_t; Component ( boost::uint32_t id ) : m_id ( id ) {} ~Component () { m_source_list.clear(); } // Now part of Component_Data void set_Data_Source ( uint32_t id ) { if ( ! m_source_list.insert ( std::make_pair ( id, false ) ).second ) { std::cerr << "WARNING: Attempted to add a duplicate component id."; std::cerr << std::endl; std::cerr << "Ignoring component id." << std::endl; } } std::map<boost::uint32_t, bool>::const_iterator get_Source_List_Begin() const { return m_source_list.begin(); } std::map<boost::uint32_t, bool>::const_iterator get_Source_List_End() const { return m_source_list.end(); } boost::uint32_t get_ID (void) const { return m_id; } private: boost::uint32_t m_id; std::map<boost::uint32_t, bool> m_source_list; }; class Component_Graph { public: typedef boost::graph_traits<Graph_Base::Graph_t>::vertex_descriptor Vertex_t; typedef boost::graph_traits<Graph_Base::Graph_t>::edge_descriptor Edge_t; typedef std::map<uint32_t, Vertex_t> IdVertexMap_t; Component_Graph () {} void add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node; if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; return; } boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node)); if ( no_duplicate ) { // Insertion was successful // Make a new vertex and return handle to 'node' node = add_vertex(m_graph); // Get list of Components boost::property_map<Graph_Base::Graph_t, boost::vertex_name_t>::type clist = boost::get(boost::vertex_name, m_graph); // Assign component to vertex position clist[node] = obj_ptr; // Add vertex handle to map position pos->second = node; // Get list of indexes boost::property_map<Graph_Base::Graph_t, boost::vertex_index_t>::type ilist = get(boost::vertex_index, m_graph); ilist[node] = obj_ptr->get_ID(); for ( std::map<boost::uint32_t,bool>::const_iterator cpos = obj_ptr->get_Source_List_Begin(); cpos != obj_ptr->get_Source_List_End(); ++cpos ) { this->add_Child ( (*cpos).first, obj_ptr ); } } else { std::cerr << "ERROR: Duplicate source found. Skipping Component" << std::endl; return; } } void add_Child ( uint32_t parent_id, Component::ptr_t obj_ptr ) { IdVertexMap_t::iterator pos; IdVertexMap_t::iterator cpos; if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; return; } pos = m_index.find (parent_id); cpos = m_index.find ( obj_ptr->get_ID() ); if (pos == m_index.end()) { std::cerr << "ERROR: Cannot find parent. Skipping adding component #" << obj_ptr->get_ID() << std::endl; return; } // Add edge from parent to child Edge_t link; if (! (add_edge ( pos->second, cpos->second, m_graph).second)) { std::cerr << "ERROR: Duplicate edge exists from " << parent_id << " to " << obj_ptr->get_ID() << std::endl; return; } else { std::cout << boost::format("Added edge: %d -> %d") % parent_id % obj_ptr->get_ID() << std::endl; } } Graph_Base::Graph_t const& get_Graph () const { return m_graph; } Component::ptr_t get_Component (const Vertex_t& node) const { Graph_Base::Property_Map_const_t clist = get(boost::vertex_name, m_graph); return clist[node]; } private: Graph_Base::Graph_t m_graph; IdVertexMap_t m_index; }; int main (int, char**) { // CREATE Component_Graph Component_Graph m_graph; // Create Components Component::ptr_t node_one ( new Component ( 1 ) ); Component::ptr_t node_twenty ( new Component ( 20 ) ); node_twenty->set_Data_Source ( 1 ); Component::ptr_t node_thirty ( new Component ( 30 ) ); node_thirty->set_Data_Source ( 1 ); Component::ptr_t node_forty ( new Component ( 40 ) ); node_forty->set_Data_Source ( 1 ); Component::ptr_t node_five ( new Component ( 5 ) ); node_five->set_Data_Source ( 1 ); node_five->set_Data_Source ( 20 ); node_five->set_Data_Source ( 30 ); node_five->set_Data_Source ( 40 ); // Add Components to Graph m_graph.add_Component ( node_one ); m_graph.add_Component ( node_twenty ); m_graph.add_Component ( node_thirty ); m_graph.add_Component ( node_forty ); m_graph.add_Component ( node_five ); // Call topological_sort on graph typedef std::vector<Component_Graph::Vertex_t> m_container; m_container comp_list; boost::topological_sort ( m_graph.get_Graph(), std::back_inserter ( comp_list ) ); std::cout << "A topological ordering: "; for ( m_container::reverse_iterator ii = comp_list.rbegin(); ii != comp_list.rend(); ++ii ) { Component::ptr_t comp_ptr = m_graph.get_Component ( *ii ); std::cout << comp_ptr->get_ID() << " "; } std::cout << std::endl; return 0; }
Stephen Torri wrote:
void add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node;
if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl;
return; }
boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node));
MSVC 8 says that you're using an uninitialized 'node' variable here. Is this intended?
Peter Dimov wrote:
Stephen Torri wrote:
void add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node;
if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl;
return; }
boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node));
MSVC 8 says that you're using an uninitialized 'node' variable here. Is this intended?
Not likely since this leads to a fault in property_map.hpp:351 where iter is advanced past the end of the sequence. You might want to investigate how to activate the debug mode of your standard library implementation, if it supports one; this is invaluable in hunting down such iterator errors. Your compiler probably warned about the uninitialized variable, too; it's easy to miss an important warning if it's buried in a flood of harmless ones, but spotting the problem early because of it can be a real time saver.
On Fri, 2007-04-13 at 00:02 +0300, Peter Dimov wrote:
Peter Dimov wrote:
MSVC 8 says that you're using an uninitialized 'node' variable here. Is this intended?
Not likely since this leads to a fault in property_map.hpp:351 where iter is advanced past the end of the sequence.
You might want to investigate how to activate the debug mode of your standard library implementation, if it supports one; this is invaluable in hunting down such iterator errors. Your compiler probably warned about the uninitialized variable, too; it's easy to miss an important warning if it's buried in a flood of harmless ones, but spotting the problem early because of it can be a real time saver.
I have very strict compiler flags: g++ -O0 -g3 -Wall -Werror -Wextra -ansi -pedantic -o test_dag test_dag.cpp This ran without reporting back an unitiailized variables. I use these same flags in building the main program. This way the compiler aborts when it get a warning so I have to deal with it. The gcc compiler flag for warning about uninitialized variables, -Wuninitialized, is call in the -Wall. Stephen
On Thu, 2007-04-12 at 23:50 +0300, Peter Dimov wrote:
void add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node;
if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl;
return; }
boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node));
MSVC 8 says that you're using an uninitialized 'node' variable here. Is this intended?
The code needs to be changed to creating and fully initializing a node before adding it. If you read the rest of the function you will notice that I add the unitialized Vertex, grab a handle to it and then fill it in. I see the add_vertex function that takes in a const VertexProperties. So I can probably do something like: // CREATE property A to contain vertex_index and integer for id // CREATE property B to contain vertex_name and obj_ptr and A reference as base // CALL add_vertex ( property B, m_graph ) void add_Component ( Component::ptr_t obj_ptr ) { if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; return; } // Search to see if the ID is already in the index map IdVertexMap_t::iterator pos = m_index.find ( obj_ptr->get_ID() ); if ( pos == m_index.end() ) { // Insertion was successful VertexProperty_t comp_index_property ( obj_ptr->get_ID() ); boost::property< boost::vertex_name_t, boost::shared_ptr<Component> > comp_property ( obj_ptr, comp_index_property ); // Make a new vertex and return handle to 'node' node = add_vertex ( comp_index_property, m_graph ); // Add vertex to id map m_index.insert ( std::make_pair ( obj_ptr->get_ID(), node ) ); for ( std::map<boost::uint32_t,bool>::const_iterator cpos = obj_ptr->get_Source_List_Begin(); cpos != obj_ptr->get_Source_List_End(); ++cpos ) { this->add_Child ( (*cpos).first, obj_ptr ); } } else { std::cerr << "ERROR: Duplicate source found. Skipping Component" << std::endl; return; } } } Now I have not compiled this since I am unsure I am understanding the boost::property constructors correctly. If my VertexProperties_t is define as follows am I correct or do I have the order reverse? Is this the best way to initialize a property? typedef property< vertex_index_t, uint32_t, property< vertex_name_t, boost::shared_ptr<Component> > > VertexProperty_t; Stephen
Stephen Torri wrote:
On Thu, 2007-04-12 at 23:50 +0300, Peter Dimov wrote:
MSVC 8 says that you're using an uninitialized 'node' variable here. Is this intended?
The code needs to be changed to creating and fully initializing a node before adding it. If you read the rest of the function you will notice that I add the unitialized Vertex, grab a handle to it and then fill it in.
testbed8.exe!std::_Vector_const_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type>
::operator+=(int _Off=20) Line 148 + 0x50 bytes C++ testbed8.exe!std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ::operator+=(int _Off=20) Line 363 C++ testbed8.exe!std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ::operator+(int _Off=20) Line 369 + 0xc bytes C++ testbed8.exe!boost::iterator_property_map<std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ,boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,unsigned long,unsigned long const &,enum boost::vertex_index_t>,enum boost::default_color_type,enum boost::default_color_type &>::operator[](void * v=0x00c76338) Line 351 + 0x67 bytes C++ testbed8.exe!boost::put<boost::iterator_property_map<std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ,boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,unsigned long,unsigned long const &,enum boost::vertex_index_t>,enum boost::default_color_type,enum boost::default_color_type &>,enum boost::default_color_type &,void *,enum boost::default_color_type>(const boost::put_get_helper<enum boost::default_color_type &,boost::iterator_property_map<std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ,boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,unsigned long,unsigned long const &,enum boost::vertex_index_t>,enum boost::default_color_type,enum boost::default_color_type &> > & pa={...}, void * k=0x00c76338, const boost::default_color_type & v=white_color) Line 321 + 0xc bytes C++ testbed8.exe!boost::depth_first_search<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > ,boost::iterator_property_map<std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ,boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,unsigned long,unsigned long const &,enum boost::vertex_index_t>,enum boost::default_color_type,enum boost::default_color_type &> >(const boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> & g={...}, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > > vis={...}, boost::iterator_property_map<std::_Vector_iterator<enum boost::default_color_type,std::allocator<enum boost::default_color_type> ,boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,unsigned long,unsigned long const &,enum boost::vertex_index_t>,enum boost::default_color_type,enum boost::default_color_type &> color={...}, void * start_vertex=0x00c761c8) Line 197 + 0x26 bytes C++ testbed8.exe!boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,void *,boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > ,boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > >,enum boost::graph_visitor_t,boost::bgl_named_params<int,boost::buffer_param_t,boost::no_property> (const boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> & g={...}, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > > vis={...}, void * start_vertex=0x00c761c8, const boost::bgl_named_params<boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > >,enum boost::graph_visitor_t,boost::bgl_named_params<int,boost::buffer_param_t,boost::no_property> & params={...}, boost::detail::error_property_not_found __formal={...}) Line 254 + 0xa6 bytes C++ testbed8.exe!boost::depth_first_search<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS>,boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > >,enum boost::graph_visitor_t,boost::bgl_named_params<int,boost::buffer_param_t,boost::no_property> (const boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> & g={...}, const boost::bgl_named_params<boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > >,enum boost::graph_visitor_t,boost::bgl_named_params<int,boost::buffer_param_t,boost::no_property> & params={...}) Line 337 + 0xf8 bytes C++ testbed8.exe!boost::topological_sort<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> const ,std::back_insert_iterator<std::vector<void *,std::allocator<void *> > ,int,boost::buffer_param_t,boost::no_property>(const boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> & g={...}, std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > result={...}, const boost::bgl_named_params<int,boost::buffer_param_t,boost::no_property> &
I see; so the error in property_map is caused by something else then. Here's the complete call stack at the time I get an assertion from the standard library... hopefully it can give you some clues as to why it attempts to create an invalid vector iterator. I can't help you more since I know nothing about the Graph library, maybe someone more familiar with it will take a look? params={...}) Line 64 + 0x77 bytes C++ testbed8.exe!boost::topological_sort<boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property>
,boost::no_property,boost::no_property,boost::listS> const ,std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > (const boost::adjacency_list<boost::setS,boost::setS,boost::directedS,boost::property<enum boost::vertex_index_t,unsigned long,boost::property<enum boost::vertex_name_t,boost::shared_ptr<Component>,boost::no_property> ,boost::no_property,boost::no_property,boost::listS> & g={...}, std::back_insert_iterator<std::vector<void *,std::allocator<void *> > > result={...}) Line 71 + 0x31 bytes C++ testbed8.exe!main(int __formal=1, int __formal=1) Line 256 + 0x43 bytes C++ testbed8.exe!__tmainCRTStartup() Line 318 + 0x19 bytes C testbed8.exe!mainCRTStartup() Line 187 C kernel32.dll!7c816fd7()
On Fri, 2007-04-13 at 00:30 +0300, Peter Dimov wrote:
I see; so the error in property_map is caused by something else then. Here's the complete call stack at the time I get an assertion from the standard library... hopefully it can give you some clues as to why it attempts to create an invalid vector iterator. I can't help you more since I know nothing about the Graph library, maybe someone more familiar with it will take a look?
I build the test program with the -D_GLIBCXX_DEBUG defined. This is suppose to turn on debugging for the standard template library in GCC 4.1.1. Here is the error report when I run the simple program along with the gdb output: [storri@localhost infrastructure]$ ./test_dag Added edge: 1 -> 20 Added edge: 1 -> 30 Added edge: 1 -> 40 Added edge: 1 -> 5 Added edge: 20 -> 5 Added edge: 30 -> 5 Added edge: 40 -> 5 /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c ++/4.1.1/debug/safe_iterator.h:277: error: attempt to advance a dereferenceable (start-of-sequence) iterator 20 steps, which falls outside its valid range. Objects involved in the operation: iterator @ 0x0xbfe4f8fc { type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPN5boost18default_color_typeEN10__gnu_norm6vectorIS4_SaIS4_EEEEEN15__gnu_debug_def6vectorIS4_S8_EEEE (mutable iterator); state = dereferenceable (start-of-sequence); references sequence with type `N15__gnu_debug_def6vectorIN5boost18default_color_typeESaIS2_EEE' @ 0x0xbfe4f8fc } Aborted Program received signal SIGABRT, Aborted. 0x00aa5402 in __kernel_vsyscall () (gdb) bt #0 0x00aa5402 in __kernel_vsyscall () #1 0x47bd9d40 in raise () from /lib/libc.so.6 #2 0x47bdb591 in abort () from /lib/libc.so.6 #3 0x47fef8a5 in __gnu_debug::_Error_formatter::_M_error () from /usr/lib/libstdc++.so.6 #4 0x0805e876 in __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<boost::default_color_type*, __gnu_norm::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, __gnu_debug_def::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >::operator+= (this=0xbfc9f6dc, __n=@0xbfc9f6f0) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/debug/safe_iterator.h:275 #5 0x0805ec9b in __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<boost::default_color_type*, __gnu_norm::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, __gnu_debug_def::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >::operator+ (this=0xbfc9f890, __n=@0xbfc9f6f0) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/debug/safe_iterator.h:286 #6 0x0805ef4c in boost::iterator_property_map<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<boost::default_color_type*, __gnu_norm::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, __gnu_debug_def::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, unsigned int, unsigned int const&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>::operator[] (this=0xbfc9f890, v=0x85d52f0) at /usr/include/boost/property_map.hpp:349 #7 0x0805efac in boost::put<boost::iterator_property_map<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<boost::default_color_type*, __gnu_norm::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, __gnu_debug_def::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, unsigned int, unsigned int const&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>, boost::default_color_type&, void*, boost::default_color_type> (pa=@0xbfc9f890, k=0x85d52f0, v=@0xbfc9f7a0) at /usr/include/boost/property_map.hpp:319 #8 0x0807039d in boost::depth_first_search<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<C---Type <return> to continue, or q <return> to quit--- omponent>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > > >, boost::iterator_property_map<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<boost::default_color_type*, __gnu_norm::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, __gnu_debug_def::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, unsigned int, unsigned int const&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&> > (g=@0xbfc9fa10, vis= {<boost::dfs_visitor<boost::null_visitor>> = {m_vis = {<> = {<No data fields>}, <No data fields>}}, m_iter = {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfc9fa8c}}, color=@0xbfc9f890, start_vertex=0x85d5270) at /usr/include/boost/graph/depth_first_search.hpp:197 #9 0x08070810 in boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, void*, boost::topo_sort_visitor<std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > > >, boost::topo_sort_visitor<std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfc9fa10, vis= {<boost::dfs_visitor<boost::null_visitor>> = {m_vis = {<> = {<No data fields>}, <No data fields>}}, m_iter = {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfc9fa8c}}, start_vertex=0x85d5270, params=@0xbfc9f984) at /usr/include/boost/graph/depth_first_search.hpp:246 #10 0x0807098e in boost::depth_first_search<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfc9fa10, params=@0xbfc9f984) at /usr/include/boost/graph/depth_first_search.hpp:324 #11 0x08070a06 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > >, int, boost::buffer_param_t, boost::no_property> (g=@0xbfc9fa10, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfc9fa8c}, params=@0xbfc9f9c4) at /usr/include/boost/graph/topological_sort.hpp:64 #12 0x08070a3a in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<__gnu_debug_def::vector<void*, std::allocator<void*> > > > (g=@0xbfc9fa10, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfc9fa8c}) at /usr/include/boost/graph/topological_sort.hpp:70 #13 0x0804c436 in main () at test_dag.cpp:256 Stephen
participants (2)
-
Peter Dimov -
Stephen Torri