Node.cpp and Node.hpp now containts the new Node base class (which always is a named node). Node instances implement the complex logic for being resolved with a path of names relative to another node

1 files changed, 44 insertions, 317 deletions

diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp
index cdf8137..df5bfcb 100644
--- a/src/core/dom/Node.cpp
+++ b/src/core/dom/Node.cpp
@@ -16,349 +16,76 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-#include <cassert>
-#include <queue>
-
 #include "Node.hpp"
 
 namespace ousia {
 namespace dom {
 
-/* Class NodeDescriptor */
+/* Class Node */
 
-int NodeDescriptor::refInCount() const
+void Node::path(std::vector<std::string> &p) const
 {
-	int res = 0;
-	for (const auto &e : refIn) {
-		res += e.second;
+	if (!isRoot()) {
+		parent->path(p);
 	}
-	return res + rootRefCount;
+	p.push_back(name);
 }
 
-int NodeDescriptor::refOutCount() const
+std::vector<std::string> Node::path() const
 {
-	int res = 0;
-	for (const auto &e : refOut) {
-		res += e.second;
-	}
+	std::vector<std::string> res;
+	path(res);
 	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)
+void Node::doResolve(std::vector<Rooted<Node>> &res,
+                     const std::vector<std::string> &path, Filter filter,
+                     void *filterData, unsigned idx, VisitorSet &visited)
 {
-	// 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++;
-	}
+	// Do nothing in the default implementation
 }
 
-bool NodeDescriptor::decrNodeDegree(RefDir dir, Node *n, bool all)
+int Node::resolve(std::vector<Rooted<Node>> &res,
+                   const std::vector<std::string> &path, Filter filter,
+                   void *filterData, unsigned idx, VisitorSet &visited,
+                   const std::string *alias)
 {
-	// 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--;
+	// Abort if this node was already visited for this path index
+	std::pair<const Node *, int> recKey = std::make_pair(this, idx);
+	if (visited.find(recKey) != visited.end()) {
+		return res.size();
+	}
+	visited.insert(recKey);
+
+	// Check whether the we can continue the path
+	if (path[idx] == name || (alias && *alias == name)) {
+		// If we have reached the end of the path and the node is successfully
+		// tested by the filter function, add it to the result. Otherwise
+		// continue searching along the path
+		if (idx + 1 == path.size()) {
+			if (!filter || filter(this, filterData)) {
+				res.push_back(this);
 			}
-			return true;
+		} else {
+			doResolve(res, path, filter, filterData, idx + 1, visited);
 		}
-		return false;
 	}
 
-	// Fetch a reference to either the input or the output reference map
-	auto &m = dir == RefDir::in ? refIn : refOut;
+	// Restart the search from here in order to find all possible nodes that can
+	// be matched to the given path
+	doResolve(res, path, filter, filterData, 0, visited);
 
-	// 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;
+	return res.size();
 }
 
-/* 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()
+std::vector<Rooted<Node>> Node::resolve(const std::vector<std::string> &path,
+                                        Filter filter = nullptr,
+                                        void *filterData = nullptr)
 {
-	// Perform a final sweep
-	sweep();
-
-	// All nodes should have been deleted!
-	assert(nodes.empty());
-
-	// Free all nodes managed by the node manager (we'll get here if assertions
-	// are disabled)
-	if (!nodes.empty()) {
-		ScopedIncrement incr{deletionRecursionDepth};
-		for (auto &e : nodes) {
-			delete e.first;
-		}
-	}
-}
-
-NodeDescriptor *NodeManager::getDescriptor(Node *n)
-{
-	if (n) {
-		auto it = nodes.find(n);
-		if (it != nodes.end()) {
-			return &(it->second);
-		}
-	}
-	return nullptr;
-}
-
-void NodeManager::registerNode(Node *n)
-{
-	nodes.emplace(std::make_pair(n, NodeDescriptor{}));
-}
-
-void NodeManager::addRef(Node *tar, Node *src)
-{
-	// Fetch the node descriptors for the two nodes
-	NodeDescriptor *dTar = getDescriptor(tar);
-	NodeDescriptor *dSrc = getDescriptor(src);
-
-	// Store the tar <- src reference
-	assert(dTar);
-	dTar->incrNodeDegree(RefDir::in, src);
-	if (src) {
-		// Store the src -> tar reference
-		assert(dSrc);
-		dSrc->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::deleteRef(Node *tar, Node *src, bool all)
-{
-	// Fetch the node descriptors for the two nodes
-	NodeDescriptor *dTar = getDescriptor(tar);
-	NodeDescriptor *dSrc = getDescriptor(src);
-
-	// 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) {
-			deleteNode(tar, dTar);
-		} else if (dTar->rootRefCount == 0) {
-			// Insert the node into the list of nodes to be inspected by garbage
-			// collection
-			marked.insert(tar);
-		}
-	}
-
-	// Call the tracing 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
-	// 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()) {
-			deleteRef(descr->refOut.begin()->first, n, true);
-		}
-
-		// Remove the node from the "marked" set
-		marked.erase(n);
-	}
-
-	purgeDeleted();
-}
-
-void NodeManager::purgeDeleted()
-{
-	// Perform the actual deletion if the recursion level is zero
-	if (deletionRecursionDepth == 0 && !deleted.empty()) {
-		// Increment the recursion depth so this function does not get called
-		// again while deleting nodes
-		ScopedIncrement incr{deletionRecursionDepth};
-
-		// Deleting nodes might add new nodes to the deleted list, thus the
-		// iterator would get invalid and we have to use this awkward
-		// construction
-		while (!deleted.empty()) {
-			auto it = deleted.begin();
-			Node *n = *it;
-			deleted.erase(it);
-			marked.erase(n);
-			nodes.erase(n);
-			delete n;
-		}
-	}
-}
-
-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;
-
-	// 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);
-				if (!descr) {
-					continue;
-				}
-
-				// If this node is rooted, the complete visited subgraph is
-				// rooted
-				if (descr->rootRefCount > 0) {
-					isReachable = true;
-					break;
-				}
-
-				// Iterate over all nodes leading to the current one
-				for (auto &src : descr->refIn) {
-					Node *srcNode = src.first;
-
-					// Abort if the node already in the reachable list,
-					// otherwise add the node to the queue if it was not visited
-					if (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) {
-					deleteNode(n, getDescriptor(n));
-				}
-			}
-		}
-
-		// Now purge all nodes marked for deletion
-		purgeDeleted();
-	}
+	std::vector<Rooted<Node>> res;
+	VisitorSet visited;
+	resolve(res, path, filter, filterData, 0, visited, nullptr);
+	return res;
 }
 }
 }