From ed50d684bf212da7a7a01ddb4bc82928f238f56d Mon Sep 17 00:00:00 2001 From: Andreas Stöckel Date: Mon, 3 Nov 2014 18:20:58 +0000 Subject: fixed bugs in garbage collector, improved handle classes, added some more unit tests git-svn-id: file:///var/local/svn/basicwriter@97 daaaf23c-2e50-4459-9457-1e69db5a47bf --- src/core/dom/Node.cpp | 20 ++++- src/core/dom/Node.hpp | 92 ++++++++++++--------- test/core/dom/NodeTest.cpp | 193 ++++++++++++++++++++++++++++++++++++++++----- 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 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 Handle acquire(const BaseHandle &h) { - return Handle(h, this); + return Handle{h, this}; } template Handle acquire(BaseHandle &&h) { - return Handle(h, this); + return Handle{h, this}; } template Handle acquire(T *t) { - return Handle(t, this); + return Handle{t, this}; } }; @@ -317,6 +317,11 @@ public: */ BaseHandle(T *ptr) : ptr(ptr) {} + /** + * Returns the underlying pointer. + */ + T *get() const { return ptr; } + /** * Provides access to the underlying node. */ @@ -397,6 +402,25 @@ public: h.ptr = nullptr; } + /** + * Constructor of the handle class. + * + * @param ptr is the node the handle should represent. + */ + RootedHandle(T *ptr) : BaseHandle(ptr) { addRef(); } + + /** + * Constructor of the handle class. + * + * @param h is another handle whose Node should be used. + */ + template + RootedHandle(const BaseHandle &h) + : BaseHandle(h.get()) + { + addRef(); + } + /** * Assignment operator. Assigns the given handle to this handle instance. * Both handles are indistinguishable after the operation. @@ -453,20 +477,6 @@ public: return *this; } - /** - * Constructor of the handle class. - * - * @param ptr is the node the handle should represent. - */ - RootedHandle(T *ptr) : BaseHandle(ptr) { addRef(); } - - /** - * Constructor of the handle class. - * - * @param h is another handle whose Node should be used. - */ - RootedHandle(BaseHandle h) : BaseHandle(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 &h) : BaseHandle(h.ptr), owner(h.owner) + Handle(const Handle &h) : BaseHandle(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 + Handle(const Handle &h) : BaseHandle(h.get()), owner(h.getOwner()) { addRef(); } @@ -521,7 +544,7 @@ public: * * @param h is the handle to be moved to this instance. */ - Handle(Handle &&h) : BaseHandle(h.ptr), owner(h.owner) + Handle(Handle &&h) : BaseHandle(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 &h, Node *owner) - : BaseHandle(h.ptr), owner(owner) + template + Handle(const BaseHandle &h, Node *owner) + : BaseHandle(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 &&h, Node *owner) : BaseHandle(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; using NodeHandle = Handle; - } } 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 rh1{n1}; + RootedHandle rh2{n2}; - NodeHandle h2{n2, n1}; + Handle 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 rh2b; ASSERT_FALSE(rh2b == rh2); rh2b = rh2; @@ -199,14 +199,14 @@ TEST(Handle, equalsAndAssign) rh2b = h2; ASSERT_TRUE(rh2b == h2); - NodeHandle h2b; + Handle h2b; ASSERT_FALSE(rh2 == h2b); ASSERT_FALSE(h2 == h2b); h2b = h2; ASSERT_TRUE(rh2 == h2b); ASSERT_TRUE(h2 == h2b); - NodeHandle h2c{h2b, n1}; + Handle 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 h) { refs.push_back(acquire(h)); } + template + void addRef(T n) { refs.push_back(acquire(n)); } - void deleteRef(BaseHandle h) + template + 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 a; - a.fill(false); NodeManager mgr(1); { @@ -276,7 +282,6 @@ TEST(NodeManager, linearDependencies) TEST(NodeManager, cyclicDependencies) { std::array a; - a.fill(false); NodeManager mgr(1); { @@ -307,10 +312,30 @@ TEST(NodeManager, cyclicDependencies) } } +TEST(NodeManager, selfReferentialCyclicDependencies) +{ + std::array a; + + NodeManager mgr(1); + { + TestNode *n1; + n1 = new TestNode(mgr, a[1]); + + { + RootedHandle 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 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 a; - a.fill(false); NodeManager mgr(1); { @@ -388,6 +412,139 @@ TEST(NodeManager, disconnectSubgraph) } } } + +TEST(NodeManager, disconnectDoubleRootedSubgraph) +{ + std::array 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 hr1{new TestNode(mgr, a[0])}; + { + RootedHandle 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 createFullyConnectedGraph(NodeManager &mgr, int nElem, + bool alive[]) +{ + std::vector> nodes; + + // Create the nodes + for (int i = 0; i < nElem; i++) { + nodes.push_back(RootedHandle{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 a; + + NodeManager mgr(1); + { + RootedHandle 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 hidden; + +public: + + HidingTestNode(NodeManager &mgr, bool &alive) : TestNode(mgr, alive) {}; + + template + void setHiddenRef(T t) { + hidden = t; + } + +}; + +TEST(NodeManager, hiddenRootedGraph) +{ + constexpr int nElem = 16; + std::array a; + bool b; + NodeManager mgr(1); + + { + RootedHandle 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); + } +} + } } -- cgit v1.2.3