diff options
| -rw-r--r-- | CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/core/dom/Node.cpp | 328 | ||||
| -rw-r--r-- | src/core/dom/Node.hpp | 549 | ||||
| -rw-r--r-- | test/core/dom/NodeTest.cpp | 256 |
4 files changed, 1135 insertions, 0 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 8d06b4a..abf143b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -96,6 +96,7 @@ ADD_DEFINITIONS( # ousia_script library (containing the bindings needed for script engines) ADD_LIBRARY(ousia_core + src/core/dom/Node src/core/script/Function src/core/script/Object src/core/script/ScriptEngine @@ -131,6 +132,7 @@ IF(test) # Add all unit test files ADD_EXECUTABLE(ousia_test_core + test/core/dom/NodeTest test/core/script/FunctionTest test/core/script/ObjectTest test/core/script/VariantTest diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp new file mode 100644 index 0000000..627ee74 --- /dev/null +++ b/src/core/dom/Node.cpp @@ -0,0 +1,328 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include <cassert> +#include <iostream> + +#include <queue> + +#include "Node.hpp" + +namespace ousia { +namespace dom { + +/* Class NodeDescriptor */ + +int NodeDescriptor::refInCount() const +{ + int res = 0; + for (const auto &e : refIn) { + res += e.second; + } + return res + rootRefCount; +} + +int NodeDescriptor::refOutCount() const +{ + int res = 0; + for (const auto &e : refOut) { + res += e.second; + } + return res; +} + +int NodeDescriptor::refInCount(Node *n) const +{ + if (n == nullptr) { + return rootRefCount; + } + + const auto it = refIn.find(n); + if (it != refIn.cend()) { + return it->second; + } + return 0; +} + +int NodeDescriptor::refOutCount(Node *n) const +{ + const auto it = refOut.find(n); + if (it != refOut.cend()) { + return it->second; + } + return 0; +} + +void NodeDescriptor::incrNodeDegree(RefDir dir, Node *n) +{ + // If the given node is null it refers to an input rooted reference + if (n == nullptr) { + rootRefCount++; + return; + } + + // Fetch a reference to either the input or the output reference map + auto &m = dir == RefDir::in ? refIn : refOut; + + // Insert a new entry or increment the corresponding reference counter + auto it = m.find(n); + if (it == m.end()) { + m.emplace(std::make_pair(n, 1)); + } else { + it->second++; + } +} + +bool NodeDescriptor::decrNodeDegree(RefDir dir, Node *n, bool all) +{ + // If the given node is null it refers to an input rooted reference + if (n == nullptr) { + if (rootRefCount > 0) { + if (all) { + rootRefCount = 0; + } else { + rootRefCount--; + } + return true; + } + return false; + } + + // Fetch a reference to either the input or the output reference map + auto &m = dir == RefDir::in ? refIn : refOut; + + // Decrement corresponding reference counter, delete the entry if the + // reference counter reaches zero + auto it = m.find(n); + if (it != m.end()) { + it->second--; + if (it->second == 0 || all) { + m.erase(it); + } + return true; + } + return false; +} + +/* Class NodeManager */ + +/** + * The ScopedIncrement class is used by the NodeManager to safely increment a + * variable when a scope is entered and to decrement it when the scope is left. + */ +class ScopedIncrement { +private: + /** + * Reference to the variable that should be incremented. + */ + int &i; + +public: + /** + * Constructor of ScopedIncrement. Increments the given variable. + * + * @param i is the variable that should be incremented. + */ + ScopedIncrement(int &i) : i(i) { i++; } + + /** + * Destructor of ScopedIncrement. Decrements the referenced variable. + */ + ~ScopedIncrement() { i--; } +}; + +NodeManager::~NodeManager() +{ + // Perform a final sweep + sweep(); + + // Free all nodes managed by the node manager + if (!nodes.empty()) { + std::cout << "[NodeManager] Warning: " << nodes.size() + << " nodes have not been deleted!" << std::endl; + ScopedIncrement incr{deletionRecursionDepth}; + for (auto &e : nodes) { + delete e.first; + } + } +} + +NodeDescriptor *NodeManager::getDescriptor(Node *n, bool create) +{ + if (n) { + auto it = nodes.find(n); + if (it != nodes.end()) { + return &(it->second); + } else if (create) { + return &(nodes.emplace(std::make_pair(n, NodeDescriptor{})) + .first->second); + } + } + return nullptr; +} + +void NodeManager::addRef(Node *tar, Node *src) +{ + getDescriptor(tar, true)->incrNodeDegree(RefDir::in, src); + if (src) { + getDescriptor(src, true)->incrNodeDegree(RefDir::out, tar); + } else { + // We have just added a root reference, remove the element from the + // list of marked nodes + marked.erase(tar); + } +} + +void NodeManager::delRef(Node *tar, Node *src, bool all) +{ + // Fetch the node descriptors for the two nodes + NodeDescriptor *dTar = getDescriptor(tar, false); + NodeDescriptor *dSrc = getDescriptor(src, false); + + // Decrement the output degree of the source node first + if (dSrc) { + dSrc->decrNodeDegree(RefDir::out, tar, all); + } + + // Decrement the input degree of the input node + if (dTar && dTar->decrNodeDegree(RefDir::in, src, all)) { + // If the node has a zero in degree, it can be safely deleted, otherwise + // if it has no root reference, add it to the "marked" set which is + // subject to tracing garbage collection + if (dTar->refInCount() == 0) { + delNode(tar, dTar); + } else if (dTar->rootRefCount == 0) { + marked.insert(tar); + } + } + + // Call the tracing garbage collector if the number of marked nodes is + // larger than the threshold value and this function was not called from + // inside the delNode function + if (deletionRecursionDepth == 0 && marked.size() >= threshold) { + sweep(); + } +} + +void NodeManager::delNode(Node *n, NodeDescriptor *descr) +{ + // Increment the recursion depth counter. The "delRef" function called below + // may descend further into this function and the actual deletion should be + // done in a single step. + { + ScopedIncrement incr{deletionRecursionDepth}; + + // Add the node to the "deleted" set + deleted.insert(n); + + // Remove all output references of this node + while (!descr->refOut.empty()) { + delRef(descr->refOut.begin()->first, n, true); + } + } + + // Perform the actual deletion if the recursion level is zero + if (deletionRecursionDepth == 0) { + purgeDeleted(); + } +} + +void NodeManager::purgeDeleted() +{ + ScopedIncrement incr{deletionRecursionDepth}; + for (Node *n : deleted) { + marked.erase(n); + nodes.erase(n); + delete n; + } + deleted.clear(); +} + +void NodeManager::sweep() +{ + // Set containing nodes which are reachable from a rooted node + std::unordered_set<Node *> reachable; + + // Deletion of nodes may cause other nodes to be added to the "marked" list + // so we repeat this process until nodes are no longer deleted + while (!marked.empty()) { + // Repeat until all nodes in the "marked" list have been visited + while (!marked.empty()) { + // Increment the deletionRecursionDepth counter to prevent deletion of nodes + // while sweep is running + ScopedIncrement incr{deletionRecursionDepth}; + // Fetch the next node in the "marked" list and remove it + Node *curNode = *(marked.begin()); + + // Perform a breadth-first search starting from the current node + bool isReachable = false; + std::unordered_set<Node *> visited{{curNode}}; + std::queue<Node *> queue{{curNode}}; + while (!queue.empty() && !isReachable) { + // Pop the next element from the queue, remove the element from + // the marked list as we obviously have evaluated it + curNode = queue.front(); + queue.pop(); + marked.erase(curNode); + + // Fetch the node descriptor + NodeDescriptor *descr = getDescriptor(curNode, false); + if (!descr) { + continue; + } + + // Iterate over all nodes leading to the current one + for (auto &src : descr->refIn) { + Node *srcNode = src.first; + + // Abort if the node is nullptr or already in the reachable + // list + if (srcNode == nullptr || + reachable.find(srcNode) != reachable.end()) { + isReachable = true; + break; + } else if (visited.find(srcNode) == visited.end()) { + visited.insert(srcNode); + queue.push(srcNode); + } + } + } + + // Insert the nodes into the list of to be deleted nodes or + // reachable nodes depending on the "isReachable" flag + if (isReachable) { + for (auto n : visited) { + reachable.insert(n); + } + } else { + for (auto n : visited) { + delNode(n, getDescriptor(n, false)); + } + } + } + + // Decrement deletionRecursionDepth + deletionRecursionDepth--; + + // Now purge all nodes marked for deletion + purgeDeleted(); + } +} +} +} + diff --git a/src/core/dom/Node.hpp b/src/core/dom/Node.hpp new file mode 100644 index 0000000..a564868 --- /dev/null +++ b/src/core/dom/Node.hpp @@ -0,0 +1,549 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#ifndef _OUSIA_DOM_NODE_HPP_ +#define _OUSIA_DOM_NODE_HPP_ + +#include <iostream> +#include <map> +#include <type_traits> +#include <unordered_map> +#include <unordered_set> + +namespace ousia { +namespace dom { + +class Node; + +/** + * Enum used for specifying the Reference direction. + */ +enum class RefDir { in, out }; + +/** + * The NodeDescriptor class is used by the NodeManager for reference counting + * and garbage collection. It describes the node reference multi graph with + * adjacency lists. + */ +class NodeDescriptor { +public: + /** + * Contains the number of references to rooted handles. A node whith at + * least one rooted reference is considered reachable. + */ + int rootRefCount; + + /** + * Map containing all references pointing at this node. The map key + * describes the node which points at this node, the map value contains the + * reference count from this node. + */ + std::map<Node *, int> refIn; + + /** + * Map containing all references pointing from this node at other nodes. The + * map key describes the target node and the map value the reference count. + */ + std::map<Node *, int> refOut; + + /** + * Default constructor of the NodeDescriptor class. + */ + NodeDescriptor() : rootRefCount(0){}; + + /** + * Returns the total input degree of this node. The root references are also + * counted as incomming references and thus added to the result. + * + * @return the input degree of this node, including the root references. + */ + int refInCount() const; + + /** + * Returns the total output degree of this node. + * + * @return the output degree of this node. + */ + int refOutCount() const; + + /** + * Returns the input degree for the given node. + * + * @param n is the node for which the input degree should be returned, + * nullptr if the number of root references is returned. + * @return the input degree of the node or the rootRefCount if nullptr is + * given as node. If the node is not found, zero is returned. + */ + int refInCount(Node *n) const; + + /** + * Returns the output degree for the given node. + * + * @param n is the node for which the output degree should be returned. + * @return the output degree of the node. If the node is not found, zero is + * returned. + */ + int refOutCount(Node *n) const; + + /** + * Increments the input or output degree for the given node. + * + * @param dir is "in", increments the input degree, otherwise increments the + * output degree. + * @param n is the node for which the input or output degree should be + * incremented. If the given node is null, the rootRefCount is incremented, + * independent of the in parameter. + */ + void incrNodeDegree(RefDir dir, Node *n); + + /** + * Decrements the input or output degree for the given node. + * + * @param dir is "in", decrements the input degree, otherwise decrements the + * output degree. + * @param n is the node for which the input or output degree should be + * decremented. If the given node is null, the rootRefCount is decremented, + * independent of the in parameter. + * @param all specifies whether the node degree of the reference to this + * node should be set to zero, no matter what the actual degree is. This + * is set to true, when the given node is deleted and all references to it + * should be purged, no matter what. + * @return true if the node degree was sucessfully decremented. + */ + bool decrNodeDegree(RefDir dir, Node *n, bool all = false); +}; + +/** + * Default sweep threshold used in the node manager. If the number of nodes + * marked for sweeping reaches this threshold a garbage collection sweep is + * performed. + */ +constexpr size_t NODE_MANAGER_SWEEP_THRESHOLD = 128; + +class NodeManager { +protected: + /** + * Threshold that defines the minimum number of entries in the "marked" + * set until "sweep" is called. + */ + const size_t threshold; + + /** + * Map used to store the node descriptors for all managed nodes. Every node + * that has at least one root, in or out reference has an entry in this map. + */ + std::unordered_map<Node *, NodeDescriptor> nodes; + + /** + * Set containing the nodes marked for sweeping. + */ + std::unordered_set<Node *> marked; + + /** + * Set containing nodes marked for deletion. + */ + std::unordered_set<Node *> deleted; + + /** + * Recursion depth while performing deletion. This variable is needed + * because the deletion of a node may cause further nodes to be deleted. + * Yet the actual deletion should only be performed at the uppermost + * recursion level. + */ + int deletionRecursionDepth = 0; + + /** + * Returns the node descriptor for the given node from the nodes map. + * Creates it if it does not exist and the "create" parameter is set to + * true. + */ + NodeDescriptor *getDescriptor(Node *n, bool create); + + /** + * Purges the nodes in the "deleted" set. + */ + void purgeDeleted(); + + /** + * Function used internally to delete a node and clean up all references in + * the node manager still pointing at it. + * + * @param n is the node that should be deleted. + * @param + */ + void delNode(Node *n, NodeDescriptor *descr); + + /** + * Internal version of the delRef function with an additional "all" + * parameter. Removes a reference to the given target node from the source + * node. + * + * @param tar is the target node for which the reference from the given + * source node should be removed. + * @param src is the source node from which the target node was referenced + * or nullptr if the target node is referenced from the local scope. + * @param all specifies whether all (src, tar) references should be deleted, + * independent of the actual cardinality. This is set to true, when the + * given node is deleted and all references to it should be purged, no + * matter what. + */ + void delRef(Node *tar, Node *src, bool all); + +public: + NodeManager() : threshold(NODE_MANAGER_SWEEP_THRESHOLD) {} + + NodeManager(size_t threshold) : threshold(threshold) {} + + /** + * Deletes all nodes which are managed by this class. + */ + ~NodeManager(); + + /** + * Stores a reference to the given target node from the given source node. + * If the source pointer is set to nullptr, this means that the target node + * is rooted (semantic: it is reachable from the current scope) and should + * not be collected. + * + * @param tar is the target node to which the reference from src should be + * stored. + * @param src is the source node from which the target node is referenced or + * nullptr if the target node is referenced from the local scope. + */ + void addRef(Node *tar, Node *src); + + /** + * Removes a reference to the given target node from the source node. + * + * @param tar is the target node for which the reference from the given + * source node should be removed. + * @param src is the source node from which the target node was referenced + * or nullptr if the target node is referenced from the local scope. + */ + void delRef(Node *tar, Node *src) { delRef(tar, src, false); } + + /** + * Performs garbage collection. + */ + void sweep(); +}; + +template<class T> +class BaseHandle; + +template<class T> +class RootedHandle; + +template<class T> +class Handle; + +/** + * The Node class builds the main class in the DOM graph. The Node class + * instances are managed by a NodeManager which performs garbage collection of + * the Node instances. Do not pass raw Node pointers around, always wrap them + * inside a RootedHandle or Handle class. + */ +class Node { +protected: + NodeManager &mgr; + +public: + Node(NodeManager &mgr) : mgr(mgr){}; + + virtual ~Node(){}; + + NodeManager &getManager() { return mgr; } + + template <class T> + Handle<T> acquire(const BaseHandle<T> &h) { + return Handle<T>(h, this); + } + + template <class T> + Handle<T> acquire(BaseHandle<T> &&h) { + return Handle<T>(h, this); + } + + template <class T> + Handle<T> acquire(T *t) { + return Handle<T>(t, this); + } + +}; + +template <class T> +class BaseHandle { +protected: + friend class RootedHandle<T>; + friend class Handle<T>; + + static_assert(std::is_base_of<Node, T>::value, "T must be a Node"); + + /** + * Reference to the represented node. + */ + T *ptr; + +public: + + /** + * Constructor of the base handle class. + * + * @param ptr is the pointer to the node the handle should represent. + */ + BaseHandle(T *ptr) : ptr(ptr) {} + + /** + * Provides access to the underlying node. + */ + T *operator->() { return ptr; } + + /** + * Provides access to the underlying node. + */ + T &operator*() { return *ptr; } +}; + +/** + * A RootedHandle represents a directed, garbage collected pointer at a Node + * instance. The lifetime of the represented node is guaranteed to be at least + * as long as the lifetime of the RootedHandle instance. + */ +template <class T> +class RootedHandle : public BaseHandle<T> { + +private: + void addRef() + { + if (BaseHandle<T>::ptr) { + BaseHandle<T>::ptr->getManager().addRef(BaseHandle<T>::ptr, + nullptr); + } + } + + void delRef() + { + if (BaseHandle<T>::ptr) { + BaseHandle<T>::ptr->getManager().delRef(BaseHandle<T>::ptr, + nullptr); + } + } + +public: + /** + * Creates an empty handle. + */ + RootedHandle() : BaseHandle<T>(nullptr){}; + + /** + * Copies the given handle to this handle instance. Both handles are + * indistinguishable after the operation. + * + * @param h is the handle that should be asigned to this instance. + */ + RootedHandle(const RootedHandle<T> &h) : BaseHandle<T>(h.ptr) { addRef(); } + + /** + * Move constructor. Moves the given rvalue handle to this instance. + * + * @param h is the handle to be moved to this instance. + */ + RootedHandle(RootedHandle<T> &&h) : BaseHandle<T>(h.ptr) + { + h.ptr = nullptr; + } + + /** + * Assignment operator. Assigns the given handle to this handle instance. + * Both handles are indistinguishable after the operation. + * + * @param h is the handle that should be asigned to this instance. + */ + RootedHandle<T> &operator=(const BaseHandle<T> &h) + { + delRef(); + this->ptr = h.ptr; + addRef(); + return *this; + } + + /** + * Move assignment operator. Moves the given rvalue handle into this + * instance. + * + * @param h is the handle to be moved to this instance. + */ + RootedHandle<T> &operator=(BaseHandle<T> &&h) + { + delRef(); + this->ptr = h.ptr; + h.ptr = nullptr; + return *this; + } + + /** + * 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. + */ + ~RootedHandle() { delRef(); } +}; + +/** + * The handle class represents a directed, garbage collected pointer at a Node + * instance. The lifetime of the represented node is guaranteed to be at last + * as long as the lifetime of the Node instance which owns this reference. + */ +template <class T> +class Handle : public BaseHandle<T> { +private: + Node *owner; + + void addRef() + { + if (BaseHandle<T>::ptr && owner) { + owner->getManager().addRef(BaseHandle<T>::ptr, owner); + } + } + + void delRef() + { + if (BaseHandle<T>::ptr && owner) { + owner->getManager().delRef(BaseHandle<T>::ptr, owner); + } + } + +public: + /** + * Creates an empty handle. + */ + Handle() : BaseHandle<T>(nullptr), owner(nullptr){}; + + /** + * Copies the given handle to this handle instance. Both handles are + * indistinguishable after the operation. Note that especially the handle + * owner is copied. + * + * @param h is the handle that should be asigned to this instance. + */ + Handle(const Handle<T> &h) : BaseHandle<T>(h.ptr), owner(h.owner) + { + addRef(); + } + + /** + * Move constructor. Moves the given rvalue handle to this instance. + * + * @param h is the handle to be moved to this instance. + */ + Handle(Handle<T> &&h) : BaseHandle<T>(h.ptr), owner(h.owner) + { + h.ptr = nullptr; + } + + /** + * Assignment operator. Assigns the given handle to this handle instance. + * Both handles are indistinguishable after the operation. Note that + * especially the handle owner is copied. + * + * @param h is the handle that should be asigned to this instance. + */ + Handle<T> &operator=(const Handle<T> &h) + { + delRef(); + this->ptr = h.ptr; + this->owner = h.owner; + addRef(); + return *this; + } + + /** + * Move assignment operator. Moves the given rvalue handle into this + * instance. + * + * @param h is the handle to be moved to this instance. + */ + Handle<T> &operator=(Handle<T> &&h) + { + delRef(); + this->ptr = h.ptr; + this->owner = h.owner; + h.ptr = nullptr; + return *this; + } + + /** + * Constructor of the handle class. + * + * @param ptr is the node the handle should represent. + * @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(T *ptr, Node *owner) : BaseHandle<T>(ptr), 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(const BaseHandle<T> &h, Node *owner) + : BaseHandle<T>(h.ptr), 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() { delRef(); } +}; + +} +} + +#endif /* _OUSIA_DOM_NODE_HPP_ */ + diff --git a/test/core/dom/NodeTest.cpp b/test/core/dom/NodeTest.cpp new file mode 100644 index 0000000..fa7b804 --- /dev/null +++ b/test/core/dom/NodeTest.cpp @@ -0,0 +1,256 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include <array> +#include <string> +#include <iostream> + +#include <gtest/gtest.h> + +#include <core/dom/Node.hpp> + +namespace ousia { +namespace dom { + +TEST(NodeDescriptor, nodeDegree) +{ + NodeManager mgr; + NodeDescriptor nd; + Node n1{mgr}, n2{mgr}; + + // Input degree + ASSERT_EQ(0, nd.refIn.size()); + ASSERT_EQ(0, nd.refInCount(&n1)); + + nd.incrNodeDegree(RefDir::in, &n1); + ASSERT_EQ(1, nd.refInCount()); + ASSERT_EQ(1, nd.refInCount(&n1)); + ASSERT_EQ(0, nd.refInCount(&n2)); + ASSERT_EQ(1, nd.refIn.size()); + + nd.incrNodeDegree(RefDir::in, &n1); + ASSERT_EQ(2, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(&n1)); + ASSERT_EQ(0, nd.refInCount(&n2)); + ASSERT_EQ(1, nd.refIn.size()); + + nd.incrNodeDegree(RefDir::in, &n2); + ASSERT_EQ(3, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(&n1)); + ASSERT_EQ(1, nd.refInCount(&n2)); + ASSERT_EQ(2, nd.refIn.size()); + + nd.incrNodeDegree(RefDir::in, nullptr); + ASSERT_EQ(4, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(&n1)); + ASSERT_EQ(1, nd.refInCount(&n2)); + ASSERT_EQ(2, nd.refIn.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, &n1)); + ASSERT_EQ(3, nd.refInCount()); + ASSERT_EQ(1, nd.refInCount(&n1)); + ASSERT_EQ(1, nd.refInCount(&n2)); + ASSERT_EQ(2, nd.refIn.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, &n1)); + ASSERT_EQ(2, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(&n1)); + ASSERT_EQ(1, nd.refInCount(&n2)); + ASSERT_EQ(1, nd.refIn.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, &n2)); + ASSERT_EQ(1, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(&n1)); + ASSERT_EQ(0, nd.refInCount(&n2)); + ASSERT_EQ(0, nd.refIn.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, nullptr)); + ASSERT_EQ(0, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(&n1)); + ASSERT_EQ(0, nd.refInCount(&n2)); + ASSERT_EQ(0, nd.refIn.size()); + + // Output degree + ASSERT_EQ(0, nd.refOut.size()); + ASSERT_EQ(0, nd.refOutCount(&n1)); + + nd.incrNodeDegree(RefDir::out, &n1); + ASSERT_EQ(1, nd.refOutCount()); + ASSERT_EQ(1, nd.refOutCount(&n1)); + ASSERT_EQ(0, nd.refOutCount(&n2)); + ASSERT_EQ(1, nd.refOut.size()); + + nd.incrNodeDegree(RefDir::out, &n1); + ASSERT_EQ(2, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(&n1)); + ASSERT_EQ(0, nd.refOutCount(&n2)); + ASSERT_EQ(1, nd.refOut.size()); + + nd.incrNodeDegree(RefDir::out, &n2); + ASSERT_EQ(3, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(&n1)); + ASSERT_EQ(1, nd.refOutCount(&n2)); + ASSERT_EQ(2, nd.refOut.size()); + + nd.incrNodeDegree(RefDir::out, nullptr); + ASSERT_EQ(3, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(&n1)); + ASSERT_EQ(1, nd.refOutCount(&n2)); + ASSERT_EQ(2, nd.refOut.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, &n1)); + ASSERT_EQ(2, nd.refOutCount()); + ASSERT_EQ(1, nd.refOutCount(&n1)); + ASSERT_EQ(1, nd.refOutCount(&n2)); + ASSERT_EQ(2, nd.refOut.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, &n1)); + ASSERT_EQ(1, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(&n1)); + ASSERT_EQ(1, nd.refOutCount(&n2)); + ASSERT_EQ(1, nd.refOut.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, &n2)); + ASSERT_EQ(0, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(&n1)); + ASSERT_EQ(0, nd.refOutCount(&n2)); + ASSERT_EQ(0, nd.refOut.size()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, nullptr)); + ASSERT_EQ(0, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(&n1)); + ASSERT_EQ(0, nd.refOutCount(&n2)); + ASSERT_EQ(0, nd.refOut.size()); +} + +TEST(NodeDescriptor, rootRefCount) +{ + NodeDescriptor nd; + ASSERT_EQ(0, nd.rootRefCount); + + nd.incrNodeDegree(RefDir::in, nullptr); + ASSERT_EQ(1, nd.rootRefCount); + + nd.incrNodeDegree(RefDir::out, nullptr); + ASSERT_EQ(2, nd.rootRefCount); + + ASSERT_EQ(2, nd.refInCount(nullptr)); + ASSERT_EQ(2, nd.refInCount()); + ASSERT_EQ(0, nd.refOutCount(nullptr)); + ASSERT_EQ(0, nd.refOutCount()); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, nullptr)); + ASSERT_EQ(1, nd.rootRefCount); + + ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, nullptr)); + ASSERT_EQ(0, nd.rootRefCount); + + ASSERT_FALSE(nd.decrNodeDegree(RefDir::in, nullptr)); + ASSERT_EQ(0, nd.rootRefCount); +} + +class TestNode : public Node { +private: + bool &alive; + + std::vector<Handle<Node>> refs; + +public: + TestNode(NodeManager &mgr, bool &alive) : Node(mgr), alive(alive) + { + alive = true; + } + + ~TestNode() override { alive = false; } + + void addRef(BaseHandle<Node> h) + { + refs.push_back(acquire(h)); + } +}; + +TEST(NodeManager, linearDependencies) +{ + std::array<bool, 4> a; + a.fill(false); + + 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> hr{new TestNode(mgr, a[0])}; + + // All nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Create a linear dependency chain + hr->addRef(n1); + n1->addRef(n2); + n2->addRef(n3); + } + + // All nodes must have set their "alive" flag to false + for (bool v : a) { + ASSERT_FALSE(v); + } + } +} + +TEST(NodeManager, cyclicDependencies) +{ + std::array<bool, 4> a; + a.fill(false); + + 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> hr{new TestNode(mgr, a[0])}; + + // All nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Create a linear dependency chain + hr->addRef(n1); + n1->addRef(n2); + n2->addRef(n3); + n3->addRef(n1); + } + + // All nodes must have set their "alive" flag to false + for (bool v : a) { + ASSERT_FALSE(v); + } + } +} + +} +} + |