C++

Forum

 
The Final SegFault; Hashtable for an Unordered_Set

Ispil (788)
Well, I've eliminated segfault after segfault, only having one more left- and this one's a doozy. Again, it is clearly labeled in the code Graph.cpp.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#ifndef CONNECTOR_H
#define CONNECTOR_H
#include <memory>
#include <utility>
#include <unordered_set>
#include <unordered_map>

class Vertex;

class Connector
{
    public:
        Connector();
        Connector(Vertex*,Vertex*);
        ~Connector();
        Connector(const Connector& other);
        Connector& operator=(const Connector& other);
        std::pair<Vertex*,Vertex*> vertex_pair;
        unsigned int get_state() const {return state;}
        void set_state(unsigned int state) {this->state = state;}
        void coboundary(const unsigned int);
        void update_pointers(std::unordered_multimap<Vertex*,Connector*>,Vertex*,Vertex*);
    protected:
    private:
        unsigned int state;
};

namespace std
{
    template <>
        class hash<Connector>{
        public :
        size_t operator()(const Connector &c ) const{
            return hash<Vertex*>()(c.vertex_pair.first) ^ hash<Vertex*>()(c.vertex_pair.second);
        }
    };
}
#endif // CONNECTOR_H 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#ifndef GRAPH_H
#define GRAPH_H
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include "Connector.h"
#include "Vertex.h"

class Graph
{
    public:
        Graph();
        ~Graph();
        Graph(const Graph& other);
        Graph& operator=(const Graph& other);
        Vertex* create_vertex();
        void copy_vertex(Vertex&);
        void create_connector(Vertex*,Vertex*);
        void delete_connector(Connector*);
        void delete_vertex(Vertex*);
        void coboundary();
        void boundary();
        unsigned int get_base_state() const {return base_state;}
        Vertex* find_vertex(std::pair<int,int>);
    protected:
    private:
        std::unordered_multimap<Vertex*,Connector*> graph_map;
        std::unordered_set<Vertex*> vertex_holder;
        const unsigned int base_state;
};

#endif // GRAPH_H 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#ifndef VERTEX_H
#define VERTEX_H
#include <memory>
#include <utility>
#include <unordered_set>

class Connector;

class Vertex
{
    public:
        Vertex();
        ~Vertex();
        Vertex(const Vertex& other);
        Vertex& operator=(const Vertex& other);
        bool operator==(const Vertex&) const;
        std::unordered_set<Connector*> connection_set;
        unsigned int get_state() const {return state;}
        void set_state(unsigned int state) {this->state = state;}
        void boundary(const unsigned int);
        std::pair<int,int> get_coordinates() const {return coordinates;}
        void set_coordinates(std::pair<int,int> coordinates) {this->coordinates = coordinates;}
    protected:
    private:
        unsigned int state;
        std::pair<int,int>coordinates;

};



namespace std
{
    template <>
        class hash<Vertex>{
        public :
        size_t operator()(const Vertex &v ) const{
            return hash<int>()(v.get_coordinates().first ^ v.get_coordinates().second)/sizeof(Vertex);
        }
    };
}
#endif // VERTEX_H 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include "Connector.h"
#include "Vertex.h"

Connector::Connector()
    : vertex_pair(std::make_pair(nullptr,nullptr))
    , state(0) {}

Connector::Connector(Vertex* v1,Vertex* v2)
    : vertex_pair(std::make_pair(v1,v2))
    , state(0)
{

}
Connector::~Connector()
{
    if(vertex_pair.first == nullptr)
        return;
    if(vertex_pair.second == nullptr)
        return;
    auto * a = vertex_pair.first;
    auto * b = vertex_pair.second;
    for ( auto p = a->connection_set.begin(); p != a->connection_set.end(); p = a->connection_set.begin())
        if (*p == this)
            a->connection_set.erase(p);
    for ( auto p : b->connection_set)
        if (p == this)
            b->connection_set.erase(p);
}

Connector::Connector(const Connector& other)
    : vertex_pair(other.vertex_pair)
    , state(other.state) {}

Connector& Connector::operator=(const Connector& rhs)
{
    if (this == &rhs) return *this; // handle self assignment
    this->state = rhs.state;
    return *this;
}

void Connector::coboundary(const unsigned int base)
{
    auto * a = vertex_pair.first;
    auto * b = vertex_pair.second;
    this->set_state((a->get_state() + b->get_state()) % base);
}

void Connector::update_pointers(std::unordered_multimap<Vertex*,Connector*> graph_map,Vertex* vert1,Vertex* vert2)
{
    vertex_pair.first = graph_map.find(vert1)->first;
    vertex_pair.second = graph_map.find(vert2)->first;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include "Vertex.h"
#include "Connector.h"

Vertex::Vertex()
    : state(0)
    , coordinates(0,0)
{
    //ctor
}

Vertex::~Vertex()
{
    connection_set.clear();
}

Vertex::Vertex(const Vertex& other)
    : state(other.state)
    , coordinates(other.coordinates)
{

}

Vertex& Vertex::operator=(const Vertex& rhs)
{
    if (this == &rhs) return *this; // handle self assignment
    this->state = rhs.state;
    return *this;
}

bool Vertex::operator==(const Vertex& rhs) const
{
    if(this->state == rhs.get_state())
    {
        if(this->connection_set.size() == rhs.connection_set.size())
        {
            for(std::unordered_set<Connector*>::const_iterator i = this->connection_set.begin(); i != this->connection_set.end();i++)
                {
                    if(rhs.connection_set.find(*i) == rhs.connection_set.end())
                        return false;
                    return true;
                }
        }
        else
            return false;
    }
    return false;
}

void Vertex::boundary(const unsigned int base)
{
    unsigned int temp_state = state;
    for(std::unordered_set<Connector*>::const_iterator i = this->connection_set.begin(); i != this->connection_set.end();i++)
        temp_state += (*i)->get_state();
    this->set_state(temp_state % base);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
#include "Graph.h"
#include "Vertex.h"
#include "Connector.h"

using namespace std;

int main()
{
    Vertex* vert1;
    Vertex* vert2;
    Graph graph;
    vert1 = graph.create_vertex();
    vert1->set_coordinates(std::pair<int,int>(1,0));
    vert2 = graph.create_vertex();
    graph.create_connector(vert1,vert2);
    vert1 = graph.find_vertex(std::pair<int,int>(1,0));
    vert1->set_state(1);
    graph.coboundary();
    graph.boundary();

}


Graph.cpp is in the next post due to length.
Ispil (788)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
#include "Graph.h"

Graph::Graph()
    : base_state(2)
{
    //ctor
}

Graph::~Graph()
{
    for(auto p = graph_map.begin(); p != graph_map.end(); p = graph_map.begin())
        delete_vertex(p->first);
    for(auto p = vertex_holder.begin(); p != vertex_holder.end(); p = vertex_holder.begin())
        delete_vertex(*p); //When this function is called, it causes a segmentation fault- deleting the other vertex works fine
}

Graph::Graph(const Graph& other)
    : base_state(other.get_base_state())
{
    //copy ctor
}

Graph& Graph::operator=(const Graph& rhs)
{
    if (this == &rhs) return *this; // handle self assignment
    //assignment operator
    return *this;
}

Vertex* Graph::create_vertex()
{
    Vertex * vert = new Vertex;
    vertex_holder.emplace(vert);
    auto iter = vertex_holder.find(vert);
    return *iter;
}

void Graph::create_connector(Vertex* vert1, Vertex* vert2)
{
    Connector * connect = new Connector(vert1,vert2);
    graph_map.emplace(vert1, connect);
    graph_map.emplace(vert2, connect);
    connect->update_pointers(graph_map, vert1, vert2);
    if(vertex_holder.count(vert1))
        vertex_holder.erase(vert1);
    if(vertex_holder.count(vert2))
        vertex_holder.erase(vert2);
}

void Graph::delete_connector(Connector* connect)
{
    if((connect->vertex_pair.first == nullptr)||(connect->vertex_pair.second == nullptr))
        return;
    auto * a = connect->vertex_pair.first;
    auto * b = connect->vertex_pair.second;
    auto p = graph_map.equal_range(a);
    for(auto iter = p.first; iter != p.second; iter++)
        if(iter->second == connect)
        {
            graph_map.erase(iter);
            break;
        }
    p = graph_map.equal_range(b);
    for(auto iter = p.first; iter != p.second; iter++)
        if(iter->second == connect)
        {
            graph_map.erase(iter);
            break;
        }
    if (graph_map.find(a) == graph_map.end())
        vertex_holder.emplace(a);
    if (graph_map.find(b) == graph_map.end())
        vertex_holder.emplace(b);
    delete connect;
}

void Graph::delete_vertex(Vertex* vert)
{
    auto test1 = graph_map.find(vert);
    if(test1 == graph_map.end())
    {
        auto test2 = vertex_holder.find(vert);
        if (test2 == vertex_holder.end())
            return;
        vertex_holder.erase(test2);
        delete vert; //Segmentation Fault!
        return;
    }
    auto p = graph_map.equal_range(vert);
    for(auto iter = p.first; iter != p.second;iter = p.first)
    {
        delete_connector(iter->second);
        p = graph_map.equal_range(vert);
    }
    delete vert;
}

void Graph::coboundary()
{
    for(auto p : graph_map)
        p.second->coboundary(base_state);
    for(auto p : graph_map)
        p.first->set_state(0);
}

void Graph::boundary()
{
    for(auto p : graph_map)
        p.first->boundary(base_state);
    for(auto p : graph_map)
        p.second->set_state(0);
}

Vertex* Graph::find_vertex(std::pair<int,int> coordinates)
{
    for(auto p : graph_map)
        if(p.first->get_coordinates() == coordinates)
            return p.first;
        else
            for(auto p : vertex_holder)
                if(p->get_coordinates() == coordinates)
                    return p;
    return nullptr;
}


Now, the issue that I've tracked down using the debugger is that a segfault is called within the hashtable for the unordered_set for connection_set, if that helps.
norm b (337)
Lines 85 & 86 in Graph.cpp:
1
2
 
        vertex_holder.erase(test2);
        delete vert; //Segmentation Fault!

From std::unordered_set::erase() - http://www.cplusplus.com/reference/unordered_set/unordered_set/erase/
This effectively reduces the container size by the number of elements removed, calling each element's destructor.

Looks like a double delete to me.
Ispil (788)
Indeed, that appears to be the issue. Let me do a quick debug check to make sure...

Elements = 0; huzzah, my code is functional! Thank you!
Last edited on
ne555 (10692)
Given that you've got several files it would be nice if you could provide an easy method for us to copy your setup. Like a zip or a github project.

> Now, the issue that I've tracked down using the debugger is that a segfault
> is called within the hashtable for the unordered_set for connection_set, if that helps.
I think that a backtrace would be more helpful.


@norm b: the destructor of a raw pointer would not perform a delete on it.
Ispil (788)
...indeed, while the elements in the multimap may be zero, it doesn't mean they don't exist. Damn.

EDIT: Download for the whole project folder is here: https://app.box.com/s/3yl65pq4mr64mwowrl9z
Last edited on
norm b (337)
ne555 wrote:
the destructor of a raw pointer would not perform a delete on it.
Doh! I knew that. Sorry for the false alarm.
LB (13399)
@Ispil your last two posts make absolutely no sense to me.
Ispil (788)
Ignore them- they're really me just blabbering nonsense to myself. Anyway, the download isn't identical to the code here- I added a bit more to main, and removed the comments where the segmentation fault is. However, that's the only difference.
Topic archived. No new replies allowed.