Memory allocation error using co/stl containers (co::vector, co::hash_map) #349
Description
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
#ifndef GRAPH_H
#define GRAPH_H
#include "cout.h"
#include "stl.h"
#include "log.h"
template <typename VertexType, typename IDType>
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<IDType>());
}
/// @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<IDType, size_t> the vertex map
co::hash_map<IDType, size_t> VertexMap() const {
return vertexMap;
}
/// @brief Vertices getter
/// @return co::vector<VertexType> the vertices
co::vector<VertexType> Vertices() const {
return vertices;
}
/// @brief Edges getter
/// @return co::vector<co::vector<IDType>> the adjacency lists
co::vector<co::vector<IDType>> 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<VertexType> vertices;
/// @brief vertex map
co::hash_map<IDType, size_t> vertexMap;
/// @brief adjacency lists representing the graph
co::vector<co::vector<IDType>> adjacencyLists;
};
#endif // GRAPH_H
and here's the file implementing the tests:
file: graph.h
#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 <chrono>
namespace test {
DEF_test(graph) {
Graph<std::string, uint32_t> myGraph = Graph<std::string, uint32_t>();
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<std::string, uint32_t> 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<std::chrono::microseconds>(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<std::chrono::microseconds>(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
Abortedif 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::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::_destruct_range<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, 0>(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > * p, size_t beg, size_t end) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:322)
co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::reset(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:134)
co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::~vector(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:79)
Graph<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned int>::~Graph(Graph<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned int> * const this)
[...]
Sorry for the lengthy description. Thanks for any advice