Memory allocation error using co/stl containers (co::vector, co::hash_map)

[piperoc]

I wrote a simple graph class using the co::vector and the co::hash_map to use a common adjacency list technique.

I then created a unit test like the the other files in your unitest source folder.

All tests pass but at the very end I get what looks like a memory allocation error (it's probably my mistake in using those structures). I tried to profile it but cannot figure it out.

Here's my class:

file: graph.h

```cpp #ifndef GRAPH_H #define GRAPH_H #include "cout.h" #include "stl.h" #include "log.h" template class Graph { public: /// @brief default constructor Graph() = default; /// @brief add a vertex to the graph /// @param IdType the vertex id to be added /// @param VertexType the vertex to be added void addVertex(const IDType& id, const VertexType& vertex) { if (vertexMap.find(id) != vertexMap.end()) { ELOG << "vertex " << id << " already exists"; return; } vertices.push_back(vertex); vertexMap[id] = vertices.size() - 1; adjacencyLists.push_back(co::vector()); } /// @brief add an edge to the graph /// @param IDType the source vertex id /// @param IDType the target vertex id void addEdge(const IDType& source, const IDType& target) { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return; } adjacencyLists[vertexMap[source]].push_back(target); } /// @brief get a node by id /// @param IDType the vertex id /// @return VertexType the vertex VertexType findNode(const IDType& id) const { if (vertexMap.find(id) == vertexMap.end()) { ELOG << "vertex " << id << " does not exist"; return VertexType(); } return vertices[vertexMap.at(id)]; } /// @brief remove a node by id /// @param IDType the vertex id void removeNode(const IDType& id) { if (vertexMap.find(id) == vertexMap.end()) { ELOG << "vertex " << id << " does not exist"; return; } size_t index = vertexMap.at(id); vertices.erase(vertices.begin() + index); vertexMap.erase(id); adjacencyLists.erase(adjacencyLists.begin() + index); for (auto& list : adjacencyLists) { for (auto& node : list) { if (node == id) { node = adjacencyLists.size(); } if (node > index) { node--; } } } } /// @brief remove an edge by id /// @param IDType the source vertex id /// @param IDType the target vertex id void removeEdge(const IDType& source, const IDType& target) { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return; } size_t sourceIndex = vertexMap.at(source); size_t targetIndex = vertexMap.at(target); for (auto& node : adjacencyLists[sourceIndex]) { if (node == target) { node = adjacencyLists.size(); } if (node > targetIndex) { node--; } } } /// @brief VertexMap getter /// @return co::map the vertex map co::hash_map VertexMap() const { return vertexMap; } /// @brief Vertices getter /// @return co::vector the vertices co::vector Vertices() const { return vertices; } /// @brief Edges getter /// @return co::vector> the adjacency lists co::vector> Edges() const { return adjacencyLists; } /// @brief function to check if an edge exists between two vertices /// @param IDType the source vertex id /// @param IDType the target vertex id /// @return bool true if the edge exists, false otherwise bool hasEdge(const IDType& source, const IDType& target) const { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return false; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return false; } size_t sourceIndex = vertexMap.at(source); for (auto& node : adjacencyLists[sourceIndex]) { if (node == target) { return true; } } return false; } private: /// @brief vertex list co::vector vertices; /// @brief vertex map co::hash_map vertexMap; /// @brief adjacency lists representing the graph co::vector> adjacencyLists; }; #endif // GRAPH_H ```

and here's the file implementing the tests:

file: graph.h

```cpp #include "co/flag.h" #include "co/cout.h" #include "co/log.h" #include "co/unitest.h" #include "co/fastring.h" #include "co/mem.h" #include "co/graph.h" #include namespace test { DEF_test(graph) { Graph myGraph = Graph(); myGraph.addVertex(1, "a"); myGraph.addVertex(2, "b"); myGraph.addVertex(3, "c"); myGraph.addVertex(4, "d"); myGraph.addEdge(1, 2); myGraph.addEdge(2, 3); myGraph.addEdge(3, 4); myGraph.addEdge(4, 1); myGraph.addEdge(2, 4); myGraph.addEdge(4, 2); DEF_case(check_vertices) { EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]],"a"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]],"b"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]],"c"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]],"d"); } DEF_case(find_node) { auto result = myGraph.findNode(3); EXPECT_EQ(result , "c"); } DEF_case(find_node_not_found) { auto result = myGraph.findNode(5); EXPECT_EQ(result, ""); } DEF_case(huge_graph) { const int NUMBER_OF_VERTICES = 2000; Graph bigGraph; auto start = std::chrono::high_resolution_clock::now(); for (int i = 0; i < NUMBER_OF_VERTICES; i++) { bigGraph.addVertex(i, "Vertex_" + std::to_string(i)); } for (int sourceID = 1; sourceID <= NUMBER_OF_VERTICES; ++sourceID) { for (int targetID = 1; targetID <= NUMBER_OF_VERTICES; ++targetID) { // add 4 edges per vertex if (targetID == (sourceID -1) || targetID == (sourceID +1) || targetID == (sourceID -2) || targetID == (sourceID +2)) bigGraph.addEdge(sourceID, targetID); } } auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast(end - start); cout << "Time taken to create the big graph: " << duration.count() << " microseconds" << std::endl; std::string halfwayVertex = "Vertex_" + std::to_string(NUMBER_OF_VERTICES/2); start = std::chrono::high_resolution_clock::now(); auto result = bigGraph.findNode(NUMBER_OF_VERTICES/2); end = std::chrono::high_resolution_clock::now(); duration = std::chrono::duration_cast(end - start); cout << "Time taken to find node: " << duration.count() << " microseconds" << std::endl; EXPECT_EQ(result, halfwayVertex); } } } // namespace test ```

When I run the unit tests I get the following

> begin test: graph
 case check_vertices:
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]], "a") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]], "b") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]], "c") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]], "d") passed
 case find_node:
  EXPECT_EQ(result, "c") passed
 case find_node_not_found:
  EXPECT_EQ(result, "") passed
 case huge_graph:
Time taken to create the big graph: 7080 microseconds
Time taken to find node: 1 microseconds
  EXPECT_EQ(result, halfwayVertex) passed
free(): invalid size
F1113 18:59:22.230] SIGABRT: aborted
Aborted

if I debug it aborts when calling void _destruct_range from the co::vector class (file include/co/vector.h line 322) as the for loop range that I'm indirectly passing (with the destructor) is probably wrong.

call stack

``` [...] libc.so.6!__GI_raise(int sig) (\build\glibc-CVJwZb\glibc-2.27\sysdeps\unix\sysv\linux\raise.c:51) libc.so.6!__GI_abort() (\build\glibc-CVJwZb\glibc-2.27\stdlib\abort.c:79) libc.so.6!__libc_message(enum __libc_message_action action, const char * fmt) (\build\glibc-CVJwZb\glibc-2.27\sysdeps\posix\libc_fatal.c:181) libc.so.6!malloc_printerr(const char * str) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:5342) libc.so.6!_int_free(int have_lock, mchunkptr p, mstate av) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:4171) libc.so.6!__GI___libc_free(void * mem) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:3134) co::vector, std::allocator >, co::default_allocator>::_destruct_range, std::allocator >, 0>(co::vector, std::allocator >, co::default_allocator> * const this, std::__cxx11::basic_string, std::allocator > * p, size_t beg, size_t end) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:322) co::vector, std::allocator >, co::default_allocator>::reset(co::vector, std::allocator >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:134) co::vector, std::allocator >, co::default_allocator>::~vector(co::vector, std::allocator >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:79) Graph, std::allocator >, unsigned int>::~Graph(Graph, std::allocator >, unsigned int> * const this) [...] ```

Sorry for the lengthy description. Thanks for any advice

[piperoc]

Just to make sure, I rewrote the graph class using std::vector and std::unorderded_map and I have no errors:

file: graph.h

```cpp #ifndef GRAPH_H #define GRAPH_H #include "co/cout.h" //#include "co/stl.h" #include #include #include "co/log.h" #include "co/json.h" #include "co/fastring.h" using namespace std; template class Graph { public: /// @brief default constructor Graph() = default; /// @brief add a vertex to the graph /// @param IdType the vertex id to be added /// @param VertexType the vertex to be added void addVertex(const IDType& id, const VertexType& vertex) { if (vertexMap.find(id) != vertexMap.end()) { ELOG << "vertex " << id << " already exists"; return; } vertices.push_back(vertex); vertexMap[id] = vertices.size() - 1; adjacencyLists.push_back(vector()); } /// @brief add an edge to the graph /// @param IDType the source vertex id /// @param IDType the target vertex id void addEdge(const IDType& source, const IDType& target) { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return; } adjacencyLists[vertexMap[source]].push_back(target); } /// @brief get a node by id /// @param IDType the vertex id /// @return VertexType the vertex VertexType findNode(const IDType& id) const { if (vertexMap.find(id) == vertexMap.end()) { ELOG << "vertex " << id << " does not exist"; return VertexType(); } return vertices[vertexMap.at(id)]; } /// @brief remove a node by id /// @param IDType the vertex id void removeNode(const IDType& id) { if (vertexMap.find(id) == vertexMap.end()) { ELOG << "vertex " << id << " does not exist"; return; } size_t index = vertexMap.at(id); vertices.erase(vertices.begin() + index); vertexMap.erase(id); adjacencyLists.erase(adjacencyLists.begin() + index); for (auto& list : adjacencyLists) { for (auto& node : list) { if (node == id) { node = adjacencyLists.size(); } if (node > index) { node--; } } } } /// @brief remove an edge by id /// @param IDType the source vertex id /// @param IDType the target vertex id void removeEdge(const IDType& source, const IDType& target) { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return; } size_t sourceIndex = vertexMap.at(source); size_t targetIndex = vertexMap.at(target); for (auto& node : adjacencyLists[sourceIndex]) { if (node == target) { node = adjacencyLists.size(); } if (node > targetIndex) { node--; } } // remove the edge from the adjacency list adjacencyLists[sourceIndex].erase( std::remove(adjacencyLists[sourceIndex].begin(), adjacencyLists[sourceIndex].end(), adjacencyLists.size()), adjacencyLists[sourceIndex].end()); } /// @brief VertexMap getter /// @return co::map the vertex map unordered_map VertexMap() const { return vertexMap; } /// @brief Vertices getter /// @return vector the vertices vector Vertices() const { return vertices; } /// @brief Edges getter /// @return vector> the adjacency lists vector> Edges() const { return adjacencyLists; } /// @brief function to check if an edge exists between two vertices /// @param IDType the source vertex id /// @param IDType the target vertex id /// @return bool true if the edge exists, false otherwise bool hasEdge(const IDType& source, const IDType& target) const { if (vertexMap.find(source) == vertexMap.end()) { ELOG << "vertex " << source << " does not exist"; return false; } if (vertexMap.find(target) == vertexMap.end()) { ELOG << "vertex " << target << " does not exist"; return false; } size_t sourceIndex = vertexMap.at(source); for (auto& node : adjacencyLists[sourceIndex]) { if (node == target) { return true; } } return false; } private: /// @brief vertex list vector vertices; /// @brief vertex map unordered_map vertexMap; /// @brief adjacency lists representing the graph vector> adjacencyLists; }; #endif // GRAPH_H ```

maybe I should use something different that co::hash_map or learn how to use it correctly...

[idealvin]

Reproduced it. Let me see..

[idealvin]

@piperoc

sorry, a little busy at work these days.It is a bug in co::vector due to SSO of std::string. You may use fastring instead of std::string to avoid this problem first. I'll try to make a fix later.

[piperoc]

@idealvin awesome! That worked right away. Thank you so much for replying so quickly.

In case some needs it, here's the tests with the fastring instead of the std::string to get rid of the error:

file: graph.cc

```cpp #include "co/flag.h" #include "co/cout.h" #include "co/log.h" #include "co/unitest.h" #include "co/fastring.h" #include "co/mem.h" #include "co/graph.h" #include namespace test { DEF_test(graph) { Graph myGraph = Graph(); myGraph.addVertex(1, "a"); myGraph.addVertex(2, "b"); myGraph.addVertex(3, "c"); myGraph.addVertex(4, "d"); myGraph.addEdge(1, 2); myGraph.addEdge(2, 3); myGraph.addEdge(3, 4); myGraph.addEdge(4, 1); myGraph.addEdge(2, 4); myGraph.addEdge(4, 2); DEF_case(check_vertices) { EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]],"a"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]],"b"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]],"c"); EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]],"d"); } DEF_case(find_node) { auto result = myGraph.findNode(3); EXPECT_EQ(result , "c"); } DEF_case(find_node_not_found) { auto result = myGraph.findNode(5); EXPECT_EQ(result, ""); } DEF_case(huge_graph) { const int NUMBER_OF_VERTICES = 2000; Graph bigGraph; auto start = std::chrono::high_resolution_clock::now(); for (int i = 0; i < NUMBER_OF_VERTICES; i++) { bigGraph.addVertex(i, "Vertex_" + std::to_string(i)); } for (int sourceID = 1; sourceID <= NUMBER_OF_VERTICES; ++sourceID) { for (int targetID = 1; targetID <= NUMBER_OF_VERTICES; ++targetID) { // add 4 edges per vertex if (targetID == (sourceID -1) || targetID == (sourceID +1) || targetID == (sourceID -2) || targetID == (sourceID +2)) bigGraph.addEdge(sourceID, targetID); } } auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast(end - start); cout << "Time taken to create the big graph: " << duration.count() << " microseconds" << std::endl; //EXPECT_EQ(bigGraph.Vertices().size(), NUMBER_OF_VERTICES); fastring halfwayVertex = "Vertex_" + std::to_string(NUMBER_OF_VERTICES/2); start = std::chrono::high_resolution_clock::now(); auto result = bigGraph.findNode(NUMBER_OF_VERTICES/2); end = std::chrono::high_resolution_clock::now(); duration = std::chrono::duration_cast(end - start); cout << "Time taken to find node: " << duration.count() << " microseconds" << std::endl; EXPECT_EQ(result, halfwayVertex); } } } // namespace test ```

[idealvin]

@piperoc Fixed in this commit.

[piperoc]

@idealvin that works. Thanks!