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
|
/* Icinga 2 | (c) 2012 Icinga GmbH | GPLv2+ */
#ifndef DEPENDENCYGRAPH_H
#define DEPENDENCYGRAPH_H
#include "base/i2-base.hpp"
#include "base/configobject.hpp"
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <mutex>
namespace icinga {
/**
* A graph that tracks dependencies between objects.
*
* @ingroup base
*/
class DependencyGraph
{
public:
static void AddDependency(ConfigObject* child, ConfigObject* parent);
static void RemoveDependency(ConfigObject* child, ConfigObject* parent);
static std::vector<ConfigObject::Ptr> GetParents(const ConfigObject::Ptr& child);
static std::vector<ConfigObject::Ptr> GetChildren(const ConfigObject::Ptr& parent);
private:
DependencyGraph();
/**
* Represents an undirected dependency edge between two objects.
*
* It allows to traverse the graph in both directions, i.e. from parent to child and vice versa.
*/
struct Edge
{
ConfigObject* parent; // The parent object of the child one.
ConfigObject* child; // The dependent object of the parent.
// Counter for the number of parent <-> child edges to allow duplicates.
int count;
Edge(ConfigObject* parent, ConfigObject* child, int count = 1): parent(parent), child(child), count(count)
{
}
struct Hash
{
/**
* Generates a unique hash of the given Edge object.
*
* Note, the hash value is generated only by combining the hash values of the parent and child pointers.
*
* @param edge The Edge object to be hashed.
*
* @return size_t The resulting hash value of the given object.
*/
size_t operator()(const Edge& edge) const
{
size_t seed = 0;
boost::hash_combine(seed, edge.parent);
boost::hash_combine(seed, edge.child);
return seed;
}
};
struct Equal
{
/**
* Compares whether the two Edge objects contain the same parent and child pointers.
*
* Note, the member property count is not taken into account for equality checks.
*
* @param a The first Edge object to compare.
* @param b The second Edge object to compare.
*
* @return bool Returns true if the two objects are equal, false otherwise.
*/
bool operator()(const Edge& a, const Edge& b) const
{
return a.parent == b.parent && a.child == b.child;
}
};
};
using DependencyMap = boost::multi_index_container<
Edge, // The value type we want to sore in the container.
boost::multi_index::indexed_by<
// The first indexer is used for lookups by the Edge from child to parent, thus it
// needs its own hash function and comparison predicate.
boost::multi_index::hashed_unique<boost::multi_index::identity<Edge>, Edge::Hash, Edge::Equal>,
// These two indexers are used for lookups by the parent and child pointers.
boost::multi_index::hashed_non_unique<boost::multi_index::member<Edge, ConfigObject*, &Edge::parent>>,
boost::multi_index::hashed_non_unique<boost::multi_index::member<Edge, ConfigObject*, &Edge::child>>
>
>;
static std::mutex m_Mutex;
static DependencyMap m_Dependencies;
};
}
#endif /* DEPENDENCYGRAPH_H */
|
