1 files changed, 333 insertions, 0 deletions
diff --git a/src/core/managed/Manager.cpp b/src/core/managed/Manager.cpp
new file mode 100644
index 0000000..7b562a8
--- /dev/null
+++ b/src/core/managed/Manager.cpp
@@ -0,0 +1,333 @@
+/*
+    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 "Managed.hpp"
+#include "Manager.hpp"
+
+namespace ousia {
+
+/* Private Class ScopedIncrement */
+
+/**
+ * The ScopedIncrement class is used by the Manager 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--; }
+};
+
+/* Class ObjectDescriptor */
+
+bool Manager::ObjectDescriptor::hasInRef() const
+{
+	return rootRefCount > 0 || !refIn.empty();
+}
+
+void Manager::ObjectDescriptor::incrDegree(RefDir dir, Managed *o)
+{
+	// If the given Managed is null it refers to an input rooted reference
+	if (o == 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(o);
+	if (it == m.end()) {
+		m.emplace(std::make_pair(o, 1));
+	} else {
+		it->second++;
+	}
+}
+
+bool Manager::ObjectDescriptor::decrDegree(RefDir dir, Managed *o, bool all)
+{
+	// If the given Managed is null it refers to an input rooted reference
+	if (o == 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(o);
+	if (it != m.end()) {
+		it->second--;
+		if (it->second == 0 || all) {
+			m.erase(it);
+		}
+		return true;
+	}
+	return false;
+}
+
+/* Class Manager */
+
+Manager::~Manager()
+{
+	// Perform a final sweep
+	sweep();
+
+	// All objects should have been deleted!
+	assert(objects.empty());
+
+	// Free all objects managed by the Managed manager (we'll get here if
+	// assertions
+	// are disabled)
+	if (!objects.empty()) {
+		ScopedIncrement incr{deletionRecursionDepth};
+		for (auto &e : objects) {
+			delete e.first;
+		}
+	}
+}
+
+Manager::ObjectDescriptor *Manager::getDescriptor(Managed *o)
+{
+	if (o) {
+		auto it = objects.find(o);
+		if (it != objects.end()) {
+			return &(it->second);
+		}
+	}
+	return nullptr;
+}
+
+void Manager::manage(Managed *o)
+{
+	objects.emplace(std::make_pair(o, ObjectDescriptor{}));
+}
+
+void Manager::addRef(Managed *tar, Managed *src)
+{
+	// Fetch the Managed descriptors for the two objects
+	ObjectDescriptor *dTar = getDescriptor(tar);
+	ObjectDescriptor *dSrc = getDescriptor(src);
+
+	// Store the tar <- src reference
+	assert(dTar);
+	dTar->incrDegree(RefDir::IN, src);
+	if (src) {
+		// Store the src -> tar reference
+		assert(dSrc);
+		dSrc->incrDegree(RefDir::OUT, tar);
+	} else {
+		// We have just added a root reference, remove the element from the
+		// list of marked objects
+		marked.erase(tar);
+	}
+}
+
+void Manager::deleteRef(Managed *tar, Managed *src, bool all)
+{
+	// Fetch the Managed descriptors for the two objects
+	ObjectDescriptor *dTar = getDescriptor(tar);
+	ObjectDescriptor *dSrc = getDescriptor(src);
+
+	// Decrement the output degree of the source Managed first
+	if (dSrc) {
+		dSrc->decrDegree(RefDir::OUT, tar, all);
+	}
+
+	// Decrement the input degree of the input Managed
+	if (dTar && dTar->decrDegree(RefDir::IN, src, all)) {
+		// If the Managed 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->hasInRef()) {
+			deleteObject(tar, dTar);
+		} else if (dTar->rootRefCount == 0) {
+			// Insert the Managed into the list of objects 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 Manager::deleteObject(Managed *o, ObjectDescriptor *descr)
+{
+	// Abort if the Managed already is on the "deleted" list
+	if (deleted.find(o) != 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 Managed to the "deleted" set
+		deleted.insert(o);
+
+		// Remove all output references of this Managed
+		while (!descr->refOut.empty()) {
+			deleteRef(descr->refOut.begin()->first, o, true);
+		}
+
+		// Remove the Managed from the "marked" set
+		marked.erase(o);
+	}
+
+	purgeDeleted();
+}
+
+void Manager::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 objects
+		ScopedIncrement incr{deletionRecursionDepth};
+
+		// Deleting objects might add new objects 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();
+			Managed *o = *it;
+			deleted.erase(it);
+			marked.erase(o);
+			objects.erase(o);
+			delete o;
+		}
+	}
+}
+
+void Manager::sweep()
+{
+	// Only execute sweep on the highest recursion level
+	if (deletionRecursionDepth > 0) {
+		return;
+	}
+
+	// Set containing objects which are reachable from a rooted Managed
+	std::unordered_set<Managed *> reachable;
+
+	// Deletion of objects may cause other objects to be added to the "marked"
+	// list
+	// so we repeat this process until objects are no longer deleted
+	while (!marked.empty()) {
+		// Repeat until all objects in the "marked" list have been visited
+		while (!marked.empty()) {
+			// Increment the deletionRecursionDepth counter to prevent deletion
+			// of objects while sweep is running
+			ScopedIncrement incr{deletionRecursionDepth};
+
+			// Fetch the next Managed in the "marked" list and remove it
+			Managed *curManaged = *(marked.begin());
+
+			// Perform a breadth-first search starting from the current Managed
+			bool isReachable = false;
+			std::unordered_set<Managed *> visited{{curManaged}};
+			std::queue<Managed *> queue{{curManaged}};
+			while (!queue.empty() && !isReachable) {
+				// Pop the next element from the queue, remove the element from
+				// the marked list as we obviously have evaluated it
+				curManaged = queue.front();
+				queue.pop();
+				marked.erase(curManaged);
+
+				// Fetch the Managed descriptor
+				ObjectDescriptor *descr = getDescriptor(curManaged);
+				if (!descr) {
+					continue;
+				}
+
+				// If this Managed is rooted, the complete visited subgraph is
+				// rooted
+				if (descr->rootRefCount > 0) {
+					isReachable = true;
+					break;
+				}
+
+				// Iterate over all objects leading to the current one
+				for (auto &src : descr->refIn) {
+					Managed *srcManaged = src.first;
+
+					// Abort if the Managed already in the reachable list,
+					// otherwise add the Managed to the queue if it was not
+					// visited
+					if (reachable.find(srcManaged) != reachable.end()) {
+						isReachable = true;
+						break;
+					} else if (visited.find(srcManaged) == visited.end()) {
+						visited.insert(srcManaged);
+						queue.push(srcManaged);
+					}
+				}
+			}
+
+			// Insert the objects into the list of to be deleted objects or
+			// reachable objects depending on the "isReachable" flag
+			if (isReachable) {
+				for (auto o : visited) {
+					reachable.insert(o);
+				}
+			} else {
+				for (auto o : visited) {
+					deleteObject(o, getDescriptor(o));
+				}
+			}
+		}
+
+		// Now purge all objects marked for deletion
+		purgeDeleted();
+	}
+}
+}
+