implemented garbage collecting node graph

git-svn-id: file:///var/local/svn/basicwriter@91 daaaf23c-2e50-4459-9457-1e69db5a47bf

2 files changed, 877 insertions, 0 deletions

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_ */
+