summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/core/dom/Node.cpp20
-rw-r--r--src/core/dom/Node.hpp92
-rw-r--r--test/core/dom/NodeTest.cpp193
3 files changed, 247 insertions, 58 deletions
diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp
index 8df0787..7c4852a 100644
--- a/src/core/dom/Node.cpp
+++ b/src/core/dom/Node.cpp
@@ -187,7 +187,6 @@ void NodeManager::addRef(Node *tar, Node *src)
// Store the tar <- src reference
assert(dTar);
dTar->incrNodeDegree(RefDir::in, src);
-
if (src) {
// Store the src -> tar reference
assert(dSrc);
@@ -222,15 +221,23 @@ void NodeManager::deleteRef(Node *tar, Node *src, bool all)
// is larger than the threshold value and this function was not
// called from inside the deleteNode function
marked.insert(tar);
- if (marked.size() >= threshold) {
- sweep();
- }
}
}
+
+ // Call the garbage collector if the marked size is larger than the actual
+ // value
+ if (marked.size() >= threshold) {
+ sweep();
+ }
}
void NodeManager::deleteNode(Node *n, NodeDescriptor *descr)
{
+ // Abort if the node already is on the "deleted" list
+ if (deleted.find(n) != deleted.end()) {
+ return;
+ }
+
// Increment the recursion depth counter. The "deleteRef" function called
// below
// may descend further into this function and the actual deletion should be
@@ -277,6 +284,11 @@ void NodeManager::purgeDeleted()
void NodeManager::sweep()
{
+ // Only execute sweep on the highest recursion level
+ if (deletionRecursionDepth > 0) {
+ return;
+ }
+
// Set containing nodes which are reachable from a rooted node
std::unordered_set<Node *> reachable;
diff --git a/src/core/dom/Node.hpp b/src/core/dom/Node.hpp
index ce1e7f1..6869253 100644
--- a/src/core/dom/Node.hpp
+++ b/src/core/dom/Node.hpp
@@ -280,19 +280,19 @@ public:
template <class T>
Handle<T> acquire(const BaseHandle<T> &h)
{
- return Handle<T>(h, this);
+ return Handle<T>{h, this};
}
template <class T>
Handle<T> acquire(BaseHandle<T> &&h)
{
- return Handle<T>(h, this);
+ return Handle<T>{h, this};
}
template <class T>
Handle<T> acquire(T *t)
{
- return Handle<T>(t, this);
+ return Handle<T>{t, this};
}
};
@@ -318,6 +318,11 @@ public:
BaseHandle(T *ptr) : ptr(ptr) {}
/**
+ * Returns the underlying pointer.
+ */
+ T *get() const { return ptr; }
+
+ /**
* Provides access to the underlying node.
*/
T *operator->() { return ptr; }
@@ -398,6 +403,25 @@ public:
}
/**
+ * Constructor of the handle class.
+ *
+ * @param ptr is the node the handle should represent.
+ */
+ RootedHandle(T *ptr) : BaseHandle<T>(ptr) { addRef(); }
+
+ /**
+ * Constructor of the handle class.
+ *
+ * @param h is another handle whose Node should be used.
+ */
+ template <class T2>
+ RootedHandle(const BaseHandle<T2> &h)
+ : BaseHandle<T>(h.get())
+ {
+ addRef();
+ }
+
+ /**
* Assignment operator. Assigns the given handle to this handle instance.
* Both handles are indistinguishable after the operation.
*
@@ -454,20 +478,6 @@ public:
}
/**
- * Constructor of the handle class.
- *
- * @param ptr is the node the handle should represent.
- */
- RootedHandle(T *ptr) : BaseHandle<T>(ptr) { addRef(); }
-
- /**
- * Constructor of the handle class.
- *
- * @param h is another handle whose Node should be used.
- */
- RootedHandle(BaseHandle<T> h) : BaseHandle<T>(h.ptr) { addRef(); }
-
- /**
* Destructor of the RootedHandle class, deletes all refrences the class is
* still holding.
*/
@@ -511,7 +521,20 @@ public:
*
* @param h is the handle that should be asigned to this instance.
*/
- Handle(const Handle<T> &h) : BaseHandle<T>(h.ptr), owner(h.owner)
+ Handle(const Handle<T> &h) : BaseHandle<T>(h.get()), owner(h.getOwner())
+ {
+ addRef();
+ }
+
+ /**
+ * Copies the given handle of another derived type to this handle instance.
+ * Both handles are indistinguishable after the operation (except for the
+ * type). Note that especially the handle owner is copied.
+ *
+ * @param h is the handle that should be asigned to this instance.
+ */
+ template<class T2>
+ Handle(const Handle<T2> &h) : BaseHandle<T>(h.get()), owner(h.getOwner())
{
addRef();
}
@@ -521,7 +544,7 @@ public:
*
* @param h is the handle to be moved to this instance.
*/
- Handle(Handle<T> &&h) : BaseHandle<T>(h.ptr), owner(h.owner)
+ Handle(Handle<T> &&h) : BaseHandle<T>(h.get()), owner(h.getOwner())
{
h.ptr = nullptr;
}
@@ -537,7 +560,7 @@ public:
{
deleteRef();
this->ptr = h.ptr;
- this->owner = h.owner;
+ this->owner = h.getOwner();
addRef();
return *this;
}
@@ -552,7 +575,7 @@ public:
{
deleteRef();
this->ptr = h.ptr;
- this->owner = h.owner;
+ this->owner = h.getOwner();
h.ptr = nullptr;
return *this;
}
@@ -573,34 +596,31 @@ public:
* @param owner is the node which owns this handle instance. The ptr node
* is guaranteed to live at least as long as the owner.
*/
- Handle(const BaseHandle<T> &h, Node *owner)
- : BaseHandle<T>(h.ptr), owner(owner)
+ template <class T2>
+ Handle(const BaseHandle<T2> &h, Node *owner)
+ : BaseHandle<T>(h.get()), owner(owner)
{
addRef();
}
/**
- * Constructor of the handle class.
- *
- * @param h is another handle whose Node should be used.
- * @param owner is the node which owns this handle instance. The ptr node
- * is guaranteed to live at least as long as the owner.
- */
- Handle(BaseHandle<T> &&h, Node *owner) : BaseHandle<T>(h.ptr), owner(owner)
- {
- h.ptr = nullptr;
- }
-
- /**
* Destructor of the Handle class, deletes all refrences the class is still
* holding.
*/
~Handle() { deleteRef(); }
+
+ /**
+ * Returns the reference to the owner of the handle.
+ *
+ * @return the handle owner.
+ */
+ Node* getOwner() const {
+ return owner;
+ }
};
using RootedNode = RootedHandle<Node>;
using NodeHandle = Handle<Node>;
-
}
}
diff --git a/test/core/dom/NodeTest.cpp b/test/core/dom/NodeTest.cpp
index 3c50cda..ce49bfe 100644
--- a/test/core/dom/NodeTest.cpp
+++ b/test/core/dom/NodeTest.cpp
@@ -176,10 +176,10 @@ TEST(Handle, equalsAndAssign)
Node *n1 = new Node(mgr), *n2 = new Node(mgr);
- RootedNode rh1{n1};
- RootedNode rh2{n2};
+ RootedHandle<Node> rh1{n1};
+ RootedHandle<Node> rh2{n2};
- NodeHandle h2{n2, n1};
+ Handle<Node> h2{n2, n1};
// Equals operator
ASSERT_TRUE(rh1 == n1);
@@ -189,7 +189,7 @@ TEST(Handle, equalsAndAssign)
ASSERT_TRUE(h2 == rh2);
// Assignment operator
- RootedNode rh2b;
+ RootedHandle<Node> rh2b;
ASSERT_FALSE(rh2b == rh2);
rh2b = rh2;
@@ -199,14 +199,14 @@ TEST(Handle, equalsAndAssign)
rh2b = h2;
ASSERT_TRUE(rh2b == h2);
- NodeHandle h2b;
+ Handle<Node> h2b;
ASSERT_FALSE(rh2 == h2b);
ASSERT_FALSE(h2 == h2b);
h2b = h2;
ASSERT_TRUE(rh2 == h2b);
ASSERT_TRUE(h2 == h2b);
- NodeHandle h2c{h2b, n1};
+ Handle<Node> h2c{h2b, n1};
ASSERT_TRUE(h2b == h2c);
}
@@ -221,17 +221,24 @@ private:
public:
TestNode(NodeManager &mgr, bool &alive) : Node(mgr), alive(alive)
{
+ //std::cout << "create TestNode @" << this << std::endl;
alive = true;
}
- ~TestNode() override { alive = false; }
+ ~TestNode() override
+ {
+ //std::cout << "delete TestNode @" << this << std::endl;
+ alive = false;
+ }
- void addRef(BaseHandle<Node> h) { refs.push_back(acquire(h)); }
+ template<class T>
+ void addRef(T n) { refs.push_back(acquire(n)); }
- void deleteRef(BaseHandle<Node> h)
+ template<class T>
+ void deleteRef(T n)
{
for (auto it = refs.begin(); it != refs.end();) {
- if (*it == h) {
+ if (*it == n) {
it = refs.erase(it);
} else {
it++;
@@ -243,7 +250,6 @@ public:
TEST(NodeManager, linearDependencies)
{
std::array<bool, 4> a;
- a.fill(false);
NodeManager mgr(1);
{
@@ -276,7 +282,6 @@ TEST(NodeManager, linearDependencies)
TEST(NodeManager, cyclicDependencies)
{
std::array<bool, 4> a;
- a.fill(false);
NodeManager mgr(1);
{
@@ -307,10 +312,30 @@ TEST(NodeManager, cyclicDependencies)
}
}
+TEST(NodeManager, selfReferentialCyclicDependencies)
+{
+ std::array<bool, 2> a;
+
+ NodeManager mgr(1);
+ {
+ TestNode *n1;
+ n1 = new TestNode(mgr, a[1]);
+
+ {
+ RootedHandle<TestNode> hr{new TestNode(mgr, a[0])};
+ ASSERT_TRUE(a[0] && a[1]);
+ hr->addRef(n1);
+ n1->addRef(n1);
+ }
+
+ // All nodes must have set their "alive" flag to false
+ ASSERT_FALSE(a[0] || a[1]);
+ }
+}
+
TEST(NodeManager, doubleRooted)
{
std::array<bool, 4> a;
- a.fill(false);
NodeManager mgr(1);
{
@@ -328,13 +353,13 @@ TEST(NodeManager, doubleRooted)
ASSERT_TRUE(v);
}
- // Create cyclical dependency between n2 and n1
- n1->addRef(n2);
- n2->addRef(n1);
-
// Reference n1 and n2 in the rooted nodes
hr1->addRef(n1);
hr2->addRef(n2);
+
+ // Create cyclical dependency between n2 and n1
+ n1->addRef(n2);
+ n2->addRef(n1);
}
// hr2 is dead, all other nodes are still alive
@@ -352,7 +377,6 @@ TEST(NodeManager, doubleRooted)
TEST(NodeManager, disconnectSubgraph)
{
std::array<bool, 4> a;
- a.fill(false);
NodeManager mgr(1);
{
@@ -388,6 +412,139 @@ TEST(NodeManager, disconnectSubgraph)
}
}
}
+
+TEST(NodeManager, disconnectDoubleRootedSubgraph)
+{
+ std::array<bool, 5> a;
+
+ NodeManager mgr(1);
+ {
+ TestNode *n1, *n2, *n3;
+ n1 = new TestNode(mgr, a[1]);
+ n2 = new TestNode(mgr, a[2]);
+ n3 = new TestNode(mgr, a[3]);
+
+ {
+ RootedHandle<TestNode> hr1{new TestNode(mgr, a[0])};
+ {
+ RootedHandle<TestNode> hr2{new TestNode(mgr, a[4])};
+
+ // Create a cyclic dependency chain with two rooted nodes
+ hr1->addRef(n1);
+ n1->addRef(n2);
+ n2->addRef(n3);
+ n3->addRef(n1);
+ hr2->addRef(n3);
+
+ // All nodes must have set their "alive" flag to true
+ for (bool v : a) {
+ ASSERT_TRUE(v);
+ }
+
+ // Remove the reference from n3 to n1
+ n3->deleteRef(n1);
+
+ // Still all nodes must have set their "alive" flag to true
+ for (bool v : a) {
+ ASSERT_TRUE(v);
+ }
+
+ // Remove the reference from n1 to n2
+ n1->deleteRef(n2);
+
+ // Node 2 must be dead, all others alive
+ ASSERT_FALSE(a[2]);
+ ASSERT_TRUE(a[0] && a[1] && a[3] && a[4]);
+ }
+
+ // Node 2, 3, hr2 must be dead, all others alive
+ ASSERT_FALSE(a[2] || a[3] || a[4]);
+ ASSERT_TRUE(a[0] && a[1]);
+ }
+
+ // All nodes must have set their "alive" flag to false
+ for (bool v : a) {
+ ASSERT_FALSE(v);
+ }
+ }
+}
+
+RootedHandle<TestNode> createFullyConnectedGraph(NodeManager &mgr, int nElem,
+ bool alive[])
+{
+ std::vector<RootedHandle<TestNode>> nodes;
+
+ // Create the nodes
+ for (int i = 0; i < nElem; i++) {
+ nodes.push_back(RootedHandle<TestNode>{new TestNode{mgr, alive[i]}});
+ }
+
+ // Add all connections
+ for (int i = 0; i < nElem; i++) {
+ for (int j = 0; j < nElem; j++) {
+ nodes[i]->addRef(nodes[j]);
+ }
+ }
+
+ return nodes[0];
+}
+
+TEST(NodeManager, fullyConnectedGraph)
+{
+ constexpr int nElem = 64;
+ std::array<bool, nElem> a;
+
+ NodeManager mgr(1);
+ {
+ RootedHandle<TestNode> n = createFullyConnectedGraph(mgr, nElem, &a[0]);
+ for (bool v : a) {
+ ASSERT_TRUE(v);
+ }
+ }
+ for (bool v : a) {
+ ASSERT_FALSE(v);
+ }
+}
+
+class HidingTestNode : public TestNode {
+
+private:
+ RootedHandle<Node> hidden;
+
+public:
+
+ HidingTestNode(NodeManager &mgr, bool &alive) : TestNode(mgr, alive) {};
+
+ template<class T>
+ void setHiddenRef(T t) {
+ hidden = t;
+ }
+
+};
+
+TEST(NodeManager, hiddenRootedGraph)
+{
+ constexpr int nElem = 16;
+ std::array<bool, nElem> a;
+ bool b;
+ NodeManager mgr(1);
+
+ {
+ RootedHandle<HidingTestNode> n{new HidingTestNode{mgr, b}};
+ n->setHiddenRef(createFullyConnectedGraph(mgr, nElem, &a[0]));
+
+ ASSERT_TRUE(b);
+ for (bool v : a) {
+ ASSERT_TRUE(v);
+ }
+ }
+
+ ASSERT_FALSE(b);
+ for (bool v : a) {
+ ASSERT_FALSE(v);
+ }
+}
+
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-01 09:36:54 +0000