diff options
| -rw-r--r-- | CMakeLists.txt | 4 | ||||
| -rw-r--r-- | src/core/dom/Managed.cpp | 367 | ||||
| -rw-r--r-- | src/core/dom/Managed.hpp | 681 | ||||
| -rw-r--r-- | test/core/dom/ManagedTest.cpp (renamed from test/core/dom/NodeTest.cpp) | 132 |
4 files changed, 1116 insertions, 68 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 0462460..73e2fb8 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -96,7 +96,7 @@ ADD_DEFINITIONS( # ousia_script library (containing the bindings needed for script engines) ADD_LIBRARY(ousia_core - src/core/dom/Node + src/core/dom/Managed src/core/script/Function src/core/script/Object src/core/script/ScriptEngine @@ -132,7 +132,7 @@ IF(TEST) # Add all unit test files ADD_EXECUTABLE(ousia_test_core - test/core/dom/NodeTest + test/core/dom/ManagedTest test/core/script/FunctionTest test/core/script/ObjectTest test/core/script/VariantTest diff --git a/src/core/dom/Managed.cpp b/src/core/dom/Managed.cpp new file mode 100644 index 0000000..ec3849f --- /dev/null +++ b/src/core/dom/Managed.cpp @@ -0,0 +1,367 @@ +/* + 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 <queue> + +#include "Managed.hpp" + +namespace ousia { +namespace dom { + +/* 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 */ + +int ObjectDescriptor::refInCount() const +{ + int res = 0; + for (const auto &e : refIn) { + res += e.second; + } + return res + rootRefCount; +} + +int ObjectDescriptor::refOutCount() const +{ + int res = 0; + for (const auto &e : refOut) { + res += e.second; + } + return res; +} + +int ObjectDescriptor::refInCount(Managed *o) const +{ + if (o == nullptr) { + return rootRefCount; + } + + const auto it = refIn.find(o); + if (it != refIn.cend()) { + return it->second; + } + return 0; +} + +int ObjectDescriptor::refOutCount(Managed *o) const +{ + const auto it = refOut.find(o); + if (it != refOut.cend()) { + return it->second; + } + return 0; +} + +void 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 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; + } + } +} + +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->refInCount() == 0) { + 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(); + } +} +} +} + diff --git a/src/core/dom/Managed.hpp b/src/core/dom/Managed.hpp new file mode 100644 index 0000000..fc4d489 --- /dev/null +++ b/src/core/dom/Managed.hpp @@ -0,0 +1,681 @@ +/* + 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_MANAGED_HPP_ +#define _OUSIA_DOM_MANAGED_HPP_ + +#include <iostream> +#include <map> +#include <type_traits> +#include <unordered_map> +#include <unordered_set> + +namespace ousia { +namespace dom { + +class Managed; + +template <class T> +class Handle; + +template <class T> +class Rooted; + +template <class T> +class Owned; + +/** + * Enum used to specify the direction of a object reference (inbound or + * outbound). + */ +enum class RefDir { in, out }; + +/** + * The ObjectDescriptor struct is used by the Manager for reference counting and + * garbage collection. It describes the reference multigraph with adjacency + * lists. Each ObjectDescriptor instance represents a single managed object and + * its assocition to and from other managed objects (nodes in the graph). + */ +struct ObjectDescriptor { +public: + /** + * Contains the number of references to rooted handles. A managed objects + * whith at least one rooted reference is considered reachable. + */ + int rootRefCount; + + /** + * Map containing all references pointing at this managed object. The + * map key describes the object which points at this object, the map + * value contains the reference count from this object. + */ + std::map<Managed *, int> refIn; + + /** + * Map containing all references pointing from this managed object to + * other managed objects. The map key describes the target object and + * the map value the reference count. + */ + std::map<Managed *, int> refOut; + + /** + * Default constructor of the ObjectDescriptor class. + */ + ObjectDescriptor() : rootRefCount(0){}; + + /** + * Returns the total input degree of this managed object. 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 managed object. + * + * @param o 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(Managed *o) const; + + /** + * Returns the output degree for the given node. + * + * @param o 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(Managed *o) const; + + /** + * Increments the input or output degree for the represented managed + * object. + * + * @param dir describes the direction of the association. A value of + * "in", increments the input degree, otherwise increments the output + * degree. + * @param o is the managed object for which the input or output degree + * should be incremented. If the given object is null, the rootRefCount + * is incremented, independent of the dir parameter. + */ + void incrDegree(RefDir dir, Managed *o); + + /** + * Decrements the input or output degree for the given managed object. + * + * @param dir describes the direction of the association. A value of + * "in", increments the input degree, otherwise increments the output + * degree. + * @param o is the managed object for which the input or output degree + * should be incremented. If the given object is null, the rootRefCount + * is incremented, independent of the dir parameter. + * @param all specifies whether the degree of the reference to this + * object should be set to zero, no matter what the actual degree is. + * This parameter is used when the given object is deleted and all + * references to it should be purged, no matter what. + * @return true if the degree was sucessfully decremented. + */ + bool decrDegree(RefDir dir, Managed *o, bool all = false); +}; + +class Manager { +private: + /** + * Default sweep threshold. If the number of managed objects marked for + * sweeping reaches this threshold a garbage collection sweep is performed. + */ + static constexpr size_t SWEEP_THRESHOLD = 128; + +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 descriptors for all managed objects. Every object + * that has at least one root, in or out reference has an entry in this map. + */ + std::unordered_map<Managed *, ObjectDescriptor> objects; + + /** + * Set containing the objects marked for sweeping. + */ + std::unordered_set<Managed *> marked; + + /** + * Set containing objects marked for deletion. + */ + std::unordered_set<Managed *> deleted; + + /** + * Recursion depth while performing deletion. This variable is needed + * because the deletion of an object may cause further objects to be + * deleted. Yet the actual deletion should only be performed at the + * uppermost recursion level. + */ + int deletionRecursionDepth = 0; + + /** + * Returns the object ObjectDescriptor for the given object from the objects map. + */ + ObjectDescriptor *getDescriptor(Managed *o); + + /** + * Purges the objects in the "deleted" set. + */ + void purgeDeleted(); + + /** + * Function used internally to delete a object and clean up all references + * in the object manager still pointing at it. + * + * @param o is the object that should be deleted. + * @param descr is a reference to the ObjectDescriptor of the given object. + */ + void deleteObject(Managed *o, ObjectDescriptor *descr); + + /** + * Internal version of the deleteRef function with an additional "all" + * parameter. Removes a reference to the given target object from the source + * object. + * + * @param tar is the target object for which the reference from the given + * source object should be removed. + * @param src is the source object from which the target object was + * referenced or nullptr if the target object 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 object is deleted and all references to it should be purged, no + * matter what. + */ + void deleteRef(Managed *tar, Managed *src, bool all); + +public: + Manager() : threshold(SWEEP_THRESHOLD) {} + + Manager(size_t threshold) : threshold(threshold) {} + + /** + * Deletes all objects managed by this class. + */ + ~Manager(); + + /** + * Registers an object for being managed by the Manager. The Manager now has + * the sole responsibility for freeing the managed object. Under no + * circumstances free the object manually, this will result in double frees. + * + * @param o is the object which is registered for being used with the + * Manager. + */ + void manage(Managed *o); + + /** + * Stores a reference to the given target object from the given source + * object. If the source pointer is set to nullptr, this means that the + * target object is rooted (semantic: it is reachable from the current + * scope) and should not be collected. + * + * @param tar is the target object to which the reference from src should be + * stored. + * @param src is the source object from which the target object is + * referenced or nullptr if the target object is referenced from the local + * scope. + */ + void addRef(Managed *tar, Managed *src); + + /** + * Removes a reference to the given target object from the source object. + * + * @param tar is the target object for which the reference from the given + * source object should be removed. + * @param src is the source object from which the target object was + * referenced or nullptr if the target object is referenced from the local + * scope. + */ + void deleteRef(Managed *tar, Managed *src) { deleteRef(tar, src, false); } + + /** + * Performs garbage collection. + */ + void sweep(); +}; + +/** + * The Managed class represents a garbage collected object. Instances of the + * Managed class are managed (e.g. freed) by an instance of the Manager class. + * Never free instances of this class yourself (even by playing an instance of + * this class on the steck). Create any new instance of any managed object with + * the makeRooted and makeOwned functions. + */ +class Managed { +protected: + Manager &mgr; + +public: + Managed(Manager &mgr) : mgr(mgr) { mgr.manage(this); }; + + virtual ~Managed(){}; + + Manager &getManager() { return mgr; } + + template <class T> + Owned<T> acquire(const Handle<T> &h) + { + return Owned<T>{h, this}; + } + + template <class T> + Owned<T> acquire(Handle<T> &&h) + { + return Owned<T>{h, this}; + } + + template <class T> + Owned<T> acquire(T *t) + { + return Owned<T>{t, this}; + } +}; + +/** + * The Handle class is the base class for handles pointing at managed objects. + * It implements methods for comparing handles to each other and to pointers + * of the represented managed object type. Furthermore all other handle types + * and pointers can be conveniently converted to a Handle instance. However, + * the Handle class does not qualify the represented pointer for garbage + * collection. Thus the Handle class should only be used as type for input + * parameters in methods/functions and at no other ocasion. Use the Rooted or + * the Owned class if the represented object should actually be garbage + * collected. + */ +template <class T> +class Handle { +protected: + friend class Rooted<T>; + friend class Owned<T>; + + static_assert(std::is_base_of<Managed, T>::value, "T must be a Managed"); + + /** + * Reference to the represented managed object. + */ + T *ptr; + +public: + /** + * Constructor of the base Handle class. + * + * @param ptr is the pointer to the managed object the Handle should + * represent. + */ + Handle(T *ptr) : ptr(ptr) {} + + /** + * Copies the given Handle to this Handle instance. + * + * @param h is the Handle that should be asigned to this instance. + */ + Handle(const Handle<T> &h) : ptr(h.get()) {} + + /** + * Copies the given Handle for a managed object of a derived class to this + * Handle instance. + * + * @param h is the Handle that should be asigned to this instance. + */ + template <class T2> + Handle(const Handle<T2> &h) + : ptr(h.get()) + { + } + + /** + * Returns the underlying pointer. + */ + T *get() const { return ptr; } + + /** + * Provides access to the underlying managed object. + */ + T *operator->() { return ptr; } + + /** + * Provides access to the underlying managed object. + */ + T &operator*() { return *ptr; } + + /** + * Comparison operator between base Owned and base Owned. + */ + bool operator==(const Handle &h) const { return ptr == h.ptr; } + + /** + * Comparison operator between base Owned and pointer. + */ + friend bool operator==(const Handle &h, const Managed *o) + { + return h.ptr == o; + } + + /** + * Comparison operator between base Owned and pointer. + */ + friend bool operator==(const Managed *o, const Handle &h) + { + return h.ptr == o; + } + + /** + * Returns true if the handle is the null pointer. + */ + bool isNull() const { return ptr == nullptr; } + + /** + * Returns true if the handle is the null pointer. + */ + bool operator!() const { return isNull(); } +}; + +/** + * Null represents a null handle. + */ +static const Handle<Managed> Null{nullptr}; + +/** + * A Rooted represents a directed, garbage collected pointer at a managed + * object. The lifetime of the represented managed object is guaranteed to be at + * least as long as the lifetime of the Rooted handle instance. + */ +template <class T> +class Rooted : public Handle<T> { +private: + void addRef() + { + if (Handle<T>::ptr) { + Handle<T>::ptr->getManager().addRef(Handle<T>::ptr, nullptr); + } + } + + void deleteRef() + { + if (Handle<T>::ptr) { + Handle<T>::ptr->getManager().deleteRef(Handle<T>::ptr, nullptr); + } + } + +public: + /** + * Creates an empty Owned. + */ + Rooted() : Handle<T>(nullptr){}; + + /** + * Copies the given Rooted to this Rooted instance. Both handles + * are indistinguishable after the operation. + * + * @param h is the Owned that should be asigned to this instance. + */ + Rooted(const Rooted<T> &h) : Handle<T>(h.ptr) { addRef(); } + + /** + * Move constructor. Moves the given rvalue Rooted to this instance. + * + * @param h is the Rooted to be moved to this instance. + */ + Rooted(Rooted<T> &&h) : Handle<T>(h.ptr) { h.ptr = nullptr; } + + /** + * Constructor of the Rooted class. + * + * @param ptr is the managed object the Rooted handle should represent. + */ + Rooted(T *ptr) : Handle<T>(ptr) { addRef(); } + + /** + * Constructor of the Rooted class. + * + * @param h is another Rooted whose managed object should be used. + */ + template <class T2> + Rooted(const Handle<T2> &h) + : Handle<T>(h.get()) + { + addRef(); + } + + /** + * Assignment operator. Assigns the given Owned to this Owned instance. + * Both handles are indistinguishable after the operation. + * + * @param h is the Owned that should be asigned to this instance. + */ + Rooted<T> &operator=(const Rooted<T> &h) + { + deleteRef(); + this->ptr = h.ptr; + addRef(); + return *this; + } + + /** + * Move assignment operator. Moves the given rvalue Owned into this + * instance. + * + * @param h is the Owned to be moved to this instance. + */ + Rooted<T> &operator=(Rooted<T> &&h) + { + deleteRef(); + this->ptr = h.ptr; + h.ptr = nullptr; + return *this; + } + + /** + * Assignment operator. Assigns the given Owned to this Owned instance. + * Both handles are indistinguishable after the operation. + * + * @param h is the Owned that should be asigned to this instance. + */ + template <class T2> + Rooted<T> &operator=(const Handle<T2> &h) + { + deleteRef(); + this->ptr = h.get(); + addRef(); + return *this; + } + + /** + * Move assignment operator. Moves the given rvalue Owned into this + * instance. + * + * @param h is the Owned to be moved to this instance. + */ + Rooted<T> &operator=(Handle<T> &&h) + { + deleteRef(); + this->ptr = h.ptr; + h.ptr = nullptr; + return *this; + } + + /** + * Destructor of the Rooted class, deletes all refrences the class is + * still holding. + */ + ~Rooted() { deleteRef(); } +}; + +/** + * The Owned class represents a directed, garbage collected pointer at a managed + * instance. The lifetime of the represented managed object is guaranteed to be + * at last as long as the lifetime of the Managed instance which owns this + * reference. + */ +template <class T> +class Owned : public Handle<T> { +private: + Managed *owner; + + void addRef() + { + if (Handle<T>::ptr && owner) { + owner->getManager().addRef(Handle<T>::ptr, owner); + } + } + + void deleteRef() + { + if (Handle<T>::ptr && owner) { + owner->getManager().deleteRef(Handle<T>::ptr, owner); + } + } + +public: + /** + * Creates an empty Owned. + */ + Owned() : Handle<T>(nullptr), owner(nullptr){}; + + /** + * Copies the given Owned to this Owned instance. Both handles are + * indistinguishable after the operation. Note that especially the Owned + * owner is copied. + * + * @param h is the Owned that should be asigned to this instance. + */ + Owned(const Owned<T> &h) : Handle<T>(h.get()), owner(h.getOwner()) + { + addRef(); + } + + /** + * Copies the given Owned of another derived type to this Owned instance. + * Both handles are indistinguishable after the operation (except for the + * type). Note that especially the Owned owner is copied. + * + * @param h is the Owned that should be asigned to this instance. + */ + template <class T2> + Owned(const Owned<T2> &h) + : Handle<T>(h.get()), owner(h.getOwner()) + { + addRef(); + } + + /** + * Move constructor. Moves the given rvalue Owned to this instance. + * + * @param h is the Owned to be moved to this instance. + */ + Owned(Owned<T> &&h) : Handle<T>(h.get()), owner(h.getOwner()) + { + h.ptr = nullptr; + } + + /** + * Assignment operator. Assigns the given Owned to this Owned instance. + * Both handles are indistinguishable after the operation. Note that + * especially the Owned owner is copied. + * + * @param h is the Owned that should be asigned to this instance. + */ + Owned<T> &operator=(const Owned<T> &h) + { + deleteRef(); + this->ptr = h.ptr; + this->owner = h.getOwner(); + addRef(); + return *this; + } + + /** + * Move assignment operator. Moves the given rvalue Owned into this + * instance. + * + * @param h is the Owned to be moved to this instance. + */ + Owned<T> &operator=(Owned<T> &&h) + { + deleteRef(); + this->ptr = h.ptr; + this->owner = h.getOwner(); + h.ptr = nullptr; + return *this; + } + + /** + * Constructor of the Owned class. + * + * @param ptr is a pointer at the managed object the Owned handle should + * represent. + * @param owner is the managed object which owns this Owned handle instance. + * The managed object pointed to in the handle is guaranteed to live at + * least as long as the owner. + */ + Owned(T *ptr, Managed *owner) : Handle<T>(ptr), owner(owner) { addRef(); } + + /** + * Constructor of the Owned class. + * + * @param h is another Owned whose managed object should be used. + * @param owner is the managed object which owns this Owned handle instance. + * The managed object pointed to in the handle is guaranteed to live at + * least as long as the owner. + */ + template <class T2> + Owned(const Handle<T2> &h, Managed *owner) + : Handle<T>(h.get()), owner(owner) + { + addRef(); + } + + /** + * Destructor of the Owned class, deletes all refrences the class is still + * holding. + */ + ~Owned() { deleteRef(); } + + /** + * Returns the reference to the owner of the Owned. + * + * @return the Owned owner. + */ + Managed *getOwner() const { return owner; } +}; +} +} + +#endif /* _OUSIA_DOM_MANAGED_HPP_ */ + diff --git a/test/core/dom/NodeTest.cpp b/test/core/dom/ManagedTest.cpp index 54bcc21..9637756 100644 --- a/test/core/dom/NodeTest.cpp +++ b/test/core/dom/ManagedTest.cpp @@ -22,68 +22,68 @@ #include <gtest/gtest.h> -#include <core/dom/Node.hpp> +#include <core/dom/Managed.hpp> namespace ousia { namespace dom { -/* Class NodeDescriptor */ +/* Class ObjectDescriptor */ -TEST(NodeDescriptor, nodeDegree) +TEST(ObjectDescriptor, Degree) { - // Do not use actual Node in this test -- we don't want to test their + // Do not use actual Managed in this test -- we don't want to test their // behaviour - NodeDescriptor nd; - Node *n1 = reinterpret_cast<Node *>(intptr_t{0x10}); - Node *n2 = reinterpret_cast<Node *>(intptr_t{0x20}); + ObjectDescriptor nd; + Managed *n1 = reinterpret_cast<Managed *>(intptr_t{0x10}); + Managed *n2 = reinterpret_cast<Managed *>(intptr_t{0x20}); // Input degree ASSERT_EQ(0, nd.refIn.size()); ASSERT_EQ(0, nd.refInCount(n1)); - nd.incrNodeDegree(RefDir::in, n1); + nd.incrDegree(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); + nd.incrDegree(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); + nd.incrDegree(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); + nd.incrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(RefDir::in, nullptr)); ASSERT_EQ(0, nd.refInCount()); ASSERT_EQ(0, nd.refInCount(n1)); ASSERT_EQ(0, nd.refInCount(n2)); @@ -93,64 +93,64 @@ TEST(NodeDescriptor, nodeDegree) ASSERT_EQ(0, nd.refOut.size()); ASSERT_EQ(0, nd.refOutCount(n1)); - nd.incrNodeDegree(RefDir::out, n1); + nd.incrDegree(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); + nd.incrDegree(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); + nd.incrDegree(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); + nd.incrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(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_TRUE(nd.decrDegree(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) +TEST(ObjectDescriptor, rootRefCount) { - NodeDescriptor nd; + ObjectDescriptor nd; ASSERT_EQ(0, nd.rootRefCount); - nd.incrNodeDegree(RefDir::in, nullptr); + nd.incrDegree(RefDir::in, nullptr); ASSERT_EQ(1, nd.rootRefCount); - nd.incrNodeDegree(RefDir::out, nullptr); + nd.incrDegree(RefDir::out, nullptr); ASSERT_EQ(2, nd.rootRefCount); ASSERT_EQ(2, nd.refInCount(nullptr)); @@ -158,13 +158,13 @@ TEST(NodeDescriptor, rootRefCount) ASSERT_EQ(0, nd.refOutCount(nullptr)); ASSERT_EQ(0, nd.refOutCount()); - ASSERT_TRUE(nd.decrNodeDegree(RefDir::out, nullptr)); + ASSERT_TRUE(nd.decrDegree(RefDir::out, nullptr)); ASSERT_EQ(1, nd.rootRefCount); - ASSERT_TRUE(nd.decrNodeDegree(RefDir::in, nullptr)); + ASSERT_TRUE(nd.decrDegree(RefDir::in, nullptr)); ASSERT_EQ(0, nd.rootRefCount); - ASSERT_FALSE(nd.decrNodeDegree(RefDir::in, nullptr)); + ASSERT_FALSE(nd.decrDegree(RefDir::in, nullptr)); ASSERT_EQ(0, nd.rootRefCount); } @@ -172,14 +172,14 @@ TEST(NodeDescriptor, rootRefCount) TEST(Owned, equalsAndAssign) { - NodeManager mgr(1); + Manager mgr(1); - Node *n1 = new Node(mgr), *n2 = new Node(mgr); + Managed *n1 = new Managed(mgr), *n2 = new Managed(mgr); - Rooted<Node> rh1{n1}; - Rooted<Node> rh2{n2}; + Rooted<Managed> rh1{n1}; + Rooted<Managed> rh2{n2}; - Owned<Node> h2{n2, n1}; + Owned<Managed> h2{n2, n1}; // Equals operator ASSERT_TRUE(rh1 == n1); @@ -189,7 +189,7 @@ TEST(Owned, equalsAndAssign) ASSERT_TRUE(h2 == rh2); // Assignment operator - Rooted<Node> rh2b; + Rooted<Managed> rh2b; ASSERT_FALSE(rh2b == rh2); rh2b = rh2; @@ -199,27 +199,27 @@ TEST(Owned, equalsAndAssign) rh2b = h2; ASSERT_TRUE(rh2b == h2); - Owned<Node> h2b; + Owned<Managed> h2b; ASSERT_FALSE(rh2 == h2b); ASSERT_FALSE(h2 == h2b); h2b = h2; ASSERT_TRUE(rh2 == h2b); ASSERT_TRUE(h2 == h2b); - Owned<Node> h2c{h2b, n1}; + Owned<Managed> h2c{h2b, n1}; ASSERT_TRUE(h2b == h2c); } -/* Class NodeManager */ +/* Class Manager */ -class TestNode : public Node { +class TestNode : public Managed { private: bool &alive; - std::vector<Owned<Node>> refs; + std::vector<Owned<Managed>> refs; public: - TestNode(NodeManager &mgr, bool &alive) : Node(mgr), alive(alive) + TestNode(Manager &mgr, bool &alive) : Managed(mgr), alive(alive) { //std::cout << "create TestNode @" << this << std::endl; alive = true; @@ -231,9 +231,9 @@ public: alive = false; } - void addRef(Handle<Node> h) { refs.push_back(acquire(h)); } + void addRef(Handle<Managed> h) { refs.push_back(acquire(h)); } - void deleteRef(Handle<Node> h) + void deleteRef(Handle<Managed> h) { for (auto it = refs.begin(); it != refs.end();) { if (*it == h) { @@ -245,11 +245,11 @@ public: } }; -TEST(NodeManager, linearDependencies) +TEST(Manager, linearDependencies) { std::array<bool, 4> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1, *n2, *n3; n1 = new TestNode(mgr, a[1]); @@ -277,11 +277,11 @@ TEST(NodeManager, linearDependencies) } } -TEST(NodeManager, cyclicDependencies) +TEST(Manager, cyclicDependencies) { std::array<bool, 4> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1, *n2, *n3; n1 = new TestNode(mgr, a[1]); @@ -310,11 +310,11 @@ TEST(NodeManager, cyclicDependencies) } } -TEST(NodeManager, selfReferentialCyclicDependencies) +TEST(Manager, selfReferentialCyclicDependencies) { std::array<bool, 2> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1; n1 = new TestNode(mgr, a[1]); @@ -331,11 +331,11 @@ TEST(NodeManager, selfReferentialCyclicDependencies) } } -TEST(NodeManager, doubleRooted) +TEST(Manager, doubleRooted) { std::array<bool, 4> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1, *n2; n1 = new TestNode(mgr, a[1]); @@ -372,11 +372,11 @@ TEST(NodeManager, doubleRooted) } } -TEST(NodeManager, disconnectSubgraph) +TEST(Manager, disconnectSubgraph) { std::array<bool, 4> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1, *n2, *n3; n1 = new TestNode(mgr, a[1]); @@ -411,11 +411,11 @@ TEST(NodeManager, disconnectSubgraph) } } -TEST(NodeManager, disconnectDoubleRootedSubgraph) +TEST(Manager, disconnectDoubleRootedSubgraph) { std::array<bool, 5> a; - NodeManager mgr(1); + Manager mgr(1); { TestNode *n1, *n2, *n3; n1 = new TestNode(mgr, a[1]); @@ -450,12 +450,12 @@ TEST(NodeManager, disconnectDoubleRootedSubgraph) // Remove the reference from n1 to n2 n1->deleteRef(n2); - // Node 2 must be dead, all others alive + // Managed 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 + // Managed 2, 3, hr2 must be dead, all others alive ASSERT_FALSE(a[2] || a[3] || a[4]); ASSERT_TRUE(a[0] && a[1]); } @@ -467,7 +467,7 @@ TEST(NodeManager, disconnectDoubleRootedSubgraph) } } -Rooted<TestNode> createFullyConnectedGraph(NodeManager &mgr, int nElem, +Rooted<TestNode> createFullyConnectedGraph(Manager &mgr, int nElem, bool alive[]) { std::vector<Rooted<TestNode>> nodes; @@ -487,12 +487,12 @@ Rooted<TestNode> createFullyConnectedGraph(NodeManager &mgr, int nElem, return nodes[0]; } -TEST(NodeManager, fullyConnectedGraph) +TEST(Manager, fullyConnectedGraph) { constexpr int nElem = 64; std::array<bool, nElem> a; - NodeManager mgr(1); + Manager mgr(1); { Rooted<TestNode> n = createFullyConnectedGraph(mgr, nElem, &a[0]); for (bool v : a) { @@ -508,24 +508,24 @@ TEST(NodeManager, fullyConnectedGraph) class HidingTestNode : public TestNode { private: - Rooted<Node> hidden; + Rooted<Managed> hidden; public: - HidingTestNode(NodeManager &mgr, bool &alive) : TestNode(mgr, alive) {}; + HidingTestNode(Manager &mgr, bool &alive) : TestNode(mgr, alive) {}; - void setHiddenRef(Handle<Node> t) { + void setHiddenRef(Handle<Managed> t) { hidden = t; } }; -TEST(NodeManager, hiddenRootedGraph) +TEST(Manager, hiddenRootedGraph) { constexpr int nElem = 16; std::array<bool, nElem> a; bool b; - NodeManager mgr(1); + Manager mgr(1); { Rooted<HidingTestNode> n{new HidingTestNode{mgr, b}}; |