From 467d8d52ffda8b5d520ee0eb1e42125bdb533ff4 Mon Sep 17 00:00:00 2001 From: Andreas Stöckel Date: Sat, 13 Dec 2014 12:33:07 +0100 Subject: started to refactor Managed package --- CMakeLists.txt | 161 ++++--- src/core/Managed.cpp | 364 -------------- src/core/Managed.hpp | 743 ----------------------------- src/core/ManagedContainers.hpp | 384 --------------- src/core/managed/Managed.cpp | 27 ++ src/core/managed/Managed.hpp | 504 +++++++++++++++++++ src/core/managed/ManagedContainer.cpp | 24 + src/core/managed/ManagedContainer.hpp | 391 +++++++++++++++ src/core/managed/Manager.cpp | 333 +++++++++++++ src/core/managed/Manager.hpp | 250 ++++++++++ test/core/ManagedContainersTest.cpp | 80 ---- test/core/ManagedTest.cpp | 515 -------------------- test/core/TestManaged.hpp | 62 --- test/core/managed/ManagedContainerTest.cpp | 80 ++++ test/core/managed/ManagedTest.cpp | 22 + test/core/managed/ManagerTest.cpp | 552 +++++++++++++++++++++ test/core/managed/TestManaged.hpp | 62 +++ 17 files changed, 2327 insertions(+), 2227 deletions(-) delete mode 100644 src/core/Managed.cpp delete mode 100644 src/core/Managed.hpp delete mode 100644 src/core/ManagedContainers.hpp create mode 100644 src/core/managed/Managed.cpp create mode 100644 src/core/managed/Managed.hpp create mode 100644 src/core/managed/ManagedContainer.cpp create mode 100644 src/core/managed/ManagedContainer.hpp create mode 100644 src/core/managed/Manager.cpp create mode 100644 src/core/managed/Manager.hpp delete mode 100644 test/core/ManagedContainersTest.cpp delete mode 100644 test/core/ManagedTest.cpp delete mode 100644 test/core/TestManaged.hpp create mode 100644 test/core/managed/ManagedContainerTest.cpp create mode 100644 test/core/managed/ManagedTest.cpp create mode 100644 test/core/managed/ManagerTest.cpp create mode 100644 test/core/managed/TestManaged.hpp diff --git a/CMakeLists.txt b/CMakeLists.txt index cac6061..841d828 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -99,55 +99,57 @@ ADD_DEFINITIONS( ) ADD_LIBRARY(ousia_core - src/core/CodeTokenizer - src/core/CSS - src/core/Managed - src/core/Node - src/core/Registry - src/core/ResourceLocator - src/core/Tokenizer - src/core/common/CharReader - src/core/common/Exceptions - src/core/common/Logger - src/core/common/Utils - src/core/common/Variant - src/core/common/VariantReader +# src/core/CodeTokenizer +# src/core/CSS +# src/core/Node +# src/core/Registry +# src/core/ResourceLocator +# src/core/Tokenizer +# src/core/common/CharReader +# src/core/common/Exceptions +# src/core/common/Logger +# src/core/common/Utils +# src/core/common/Variant +# src/core/common/VariantReader + src/core/managed/Managed + src/core/managed/Manager + src/core/managed/ManagedContainer # src/core/model/Domain - src/core/model/Typesystem - src/core/parser/Parser - src/core/parser/ParserStack - src/core/parser/Scope +# src/core/model/Typesystem +# src/core/parser/Parser +# src/core/parser/ParserStack +# src/core/parser/Scope # src/core/script/Function # src/core/script/Object # src/core/script/ScriptEngine # src/core/script/Variant ) -ADD_LIBRARY(ousia_boost - src/plugins/boost/FileLocator -) +#ADD_LIBRARY(ousia_boost +# src/plugins/boost/FileLocator +#) -TARGET_LINK_LIBRARIES(ousia_boost - ousia_core - ${Boost_LIBRARIES} -) +#TARGET_LINK_LIBRARIES(ousia_boost +# ousia_core +# ${Boost_LIBRARIES} +#) -ADD_LIBRARY(ousia_css - src/plugins/css/CSSParser -) +#ADD_LIBRARY(ousia_css +# src/plugins/css/CSSParser +#) -TARGET_LINK_LIBRARIES(ousia_css - ousia_core -) +#TARGET_LINK_LIBRARIES(ousia_css +# ousia_core +#) -ADD_LIBRARY(ousia_xml - src/plugins/xml/XmlParser -) +#ADD_LIBRARY(ousia_xml +# src/plugins/xml/XmlParser +#) -TARGET_LINK_LIBRARIES(ousia_xml - ousia_core - ${EXPAT_LIBRARIES} -) +#TARGET_LINK_LIBRARIES(ousia_xml +# ousia_core +# ${EXPAT_LIBRARIES} +#) #ADD_LIBRARY(ousia_mozjs # src/plugins/mozjs/MozJsScriptEngine @@ -166,21 +168,22 @@ IF(TEST) ) ADD_EXECUTABLE(ousia_test_core - test/core/CodeTokenizerTest - test/core/CSSTest - test/core/ManagedTest - test/core/ManagedContainersTest - test/core/NodeTest - test/core/RangeSetTest - test/core/RegistryTest - test/core/ResourceLocatorTest - test/core/TokenizerTest - test/core/common/CharReaderTest - test/core/common/LoggerTest - test/core/common/VariantReaderTest - test/core/common/VariantTest - test/core/common/UtilsTest - test/core/parser/ParserStackTest +# test/core/CodeTokenizerTest +# test/core/CSSTest +# test/core/NodeTest +# test/core/RangeSetTest +# test/core/RegistryTest +# test/core/ResourceLocatorTest +# test/core/TokenizerTest +# test/core/common/CharReaderTest +# test/core/common/LoggerTest +# test/core/common/VariantReaderTest +# test/core/common/VariantTest +# test/core/common/UtilsTest + test/core/managed/ManagedTest + test/core/managed/ManagerTest + test/core/managed/ManagedContainerTest +# test/core/parser/ParserStackTest # test/core/script/FunctionTest # test/core/script/ObjectTest # test/core/script/VariantTest @@ -191,35 +194,35 @@ IF(TEST) ousia_core ) - ADD_EXECUTABLE(ousia_test_boost - test/plugins/boost/FileLocatorTest - ) +# ADD_EXECUTABLE(ousia_test_boost +# test/plugins/boost/FileLocatorTest +# ) - TARGET_LINK_LIBRARIES(ousia_test_boost - ${GTEST_LIBRARIES} - ousia_core - ousia_boost - ) +# TARGET_LINK_LIBRARIES(ousia_test_boost +# ${GTEST_LIBRARIES} +# ousia_core +# ousia_boost +# ) - ADD_EXECUTABLE(ousia_test_css - test/plugins/css/CSSParserTest - ) +# ADD_EXECUTABLE(ousia_test_css +# test/plugins/css/CSSParserTest +# ) - TARGET_LINK_LIBRARIES(ousia_test_css - ${GTEST_LIBRARIES} - ousia_core - ousia_css - ) +# TARGET_LINK_LIBRARIES(ousia_test_css +# ${GTEST_LIBRARIES} +# ousia_core +# ousia_css +# ) - ADD_EXECUTABLE(ousia_test_xml - test/plugins/xml/XmlParserTest - ) +# ADD_EXECUTABLE(ousia_test_xml +# test/plugins/xml/XmlParserTest +# ) - TARGET_LINK_LIBRARIES(ousia_test_xml - ${GTEST_LIBRARIES} - ousia_core - ousia_xml - ) +# TARGET_LINK_LIBRARIES(ousia_test_xml +# ${GTEST_LIBRARIES} +# ousia_core +# ousia_xml +# ) # ADD_EXECUTABLE(ousia_test_mozjs # test/plugins/mozjs/MozJsScriptEngineTest @@ -233,9 +236,9 @@ IF(TEST) # Register the unit tests ADD_TEST(ousia_test_core ousia_test_core) - ADD_TEST(ousia_test_boost ousia_test_boost) - ADD_TEST(ousia_test_xml ousia_test_xml) - ADD_TEST(ousia_test_css ousia_test_css) +# ADD_TEST(ousia_test_boost ousia_test_boost) +# ADD_TEST(ousia_test_xml ousia_test_xml) +# ADD_TEST(ousia_test_css ousia_test_css) # ADD_TEST(ousia_test_mozjs ousia_test_mozjs) ENDIF() diff --git a/src/core/Managed.cpp b/src/core/Managed.cpp deleted file mode 100644 index f3a68a3..0000000 --- a/src/core/Managed.cpp +++ /dev/null @@ -1,364 +0,0 @@ -/* - 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 . -*/ - -#include -#include - -#include "Managed.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 */ - -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 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 visited{{curManaged}}; - std::queue 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/Managed.hpp b/src/core/Managed.hpp deleted file mode 100644 index 25fa14b..0000000 --- a/src/core/Managed.hpp +++ /dev/null @@ -1,743 +0,0 @@ -/* - 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 . -*/ - -#ifndef _OUSIA_MANAGED_HPP_ -#define _OUSIA_MANAGED_HPP_ - -#include -#include -#include -#include -#include -#include - -namespace ousia { - -// TODO: Implement clone, getReferenced and getReferencing - -class Managed; - -template -class Handle; - -template -class Rooted; - -template -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 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 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 objects; - - /** - * Set containing the objects marked for sweeping. - */ - std::unordered_set marked; - - /** - * Set containing objects marked for deletion. - */ - std::unordered_set 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: - /** - * mgr is the reference to the managed object manager which owns this - * managed object. - */ - Manager &mgr; - -public: - /** - * Constructor of the Managed class. Associates the new instance with the - * given Manager, which is now in charge for managing this instance. Never - * manually free instances of this class (even by using stack instances). - * Always use the Rooted and Owned smart pointer classes when refering to - * types derived from Managed. - * - * @param mgr is the Manager which should take ownership of this instance. - */ - Managed(Manager &mgr) : mgr(mgr) { mgr.manage(this); }; - - /** - * Virtual destuctor which may be overwritten by child classes. - */ - virtual ~Managed(){}; - - /** - * Returns a reference ot the manager instance which owns this managed - * object. - */ - Manager &getManager() { return mgr; } - - /** - * Acquires a reference to the object wraped in the given handle. - */ - template - Owned acquire(const Handle &h) - { - return Owned{h, this}; - } - - template - Owned acquire(Handle &&h) - { - return Owned{h, this}; - } - - template - Owned acquire(T *t) - { - return Owned{t, this}; - } - - template - std::vector> acquire(const std::vector> &vec) - { - std::vector> res; - for (auto &e : vec) { - res.push_back(acquire(e)); - } - return res; - } - - template - std::vector> acquire(const std::vector &vec) - { - std::vector> res; - for (auto &e : vec) { - res.push_back(acquire(e)); - } - return res; - } -}; - -/** - * 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 Handle { -protected: - friend class Rooted; - friend class Owned; - - /** - * 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 &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 - Handle(const Handle &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 for immutable handles. - */ - const T *operator->() const { return ptr; } - - /** - * Provides access to the underlying managed object. - */ - T &operator*() { return *ptr; } - - /** - * Provides access to the underlying managed object for immutable handles. - */ - const T &operator*() const { return *ptr; } - - /** - * Comparison operator between base Owned and base Owned. - */ - template - bool operator==(const Handle &h) const - { - return ptr == h.get(); - } - - /** - * Comparison operator between base Owned and pointer. - */ - friend bool operator==(const Handle &h, const Managed *o) - { - return h.get() == o; - } - - /** - * Comparison operator between base Owned and pointer. - */ - friend bool operator==(const Managed *o, const Handle &h) - { - return o == h.get(); - } - - /** - * 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(); } - - /** - * Statically casts the handle to a handle of the given type. - */ - template - Handle cast() - { - return Handle{static_cast(ptr)}; - } -}; - -/** - * 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 Rooted : public Handle { -private: - void addRef() - { - if (Handle::ptr) { - Handle::ptr->getManager().addRef(Handle::ptr, nullptr); - } - } - - void deleteRef() - { - if (Handle::ptr) { - Handle::ptr->getManager().deleteRef(Handle::ptr, nullptr); - } - } - -public: - /** - * Creates an empty Owned. - */ - Rooted() : Handle(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 &h) : Handle(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 &&h) : Handle(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(ptr) { addRef(); } - - /** - * Constructor of the Rooted class. - * - * @param h is another Rooted whose managed object should be used. - */ - template - Rooted(const Handle &h) - : Handle(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 &operator=(const Rooted &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 &operator=(Rooted &&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 - Rooted &operator=(const Handle &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 &operator=(Handle &&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 Owned : public Handle { -private: - Managed *owner; - - void addRef() - { - if (Handle::ptr && owner) { - owner->getManager().addRef(Handle::ptr, owner); - } - } - - void deleteRef() - { - if (Handle::ptr && owner) { - owner->getManager().deleteRef(Handle::ptr, owner); - } - } - -public: - /** - * Creates an empty Owned. - */ - Owned() : Handle(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 &h) : Handle(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 - Owned(const Owned &h) - : Handle(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 &&h) : Handle(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 &operator=(const Owned &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 &operator=(Owned &&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(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 - Owned(const Handle &h, Managed *owner) - : Handle(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_MANAGED_HPP_ */ - diff --git a/src/core/ManagedContainers.hpp b/src/core/ManagedContainers.hpp deleted file mode 100644 index 9447fff..0000000 --- a/src/core/ManagedContainers.hpp +++ /dev/null @@ -1,384 +0,0 @@ -/* - 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 . -*/ - -#ifndef _OUSIA_MANAGED_CONTAINERS_H_ -#define _OUSIA_MANAGED_CONTAINERS_H_ - -#include "Managed.hpp" - -namespace ousia { - -/** - * Template class which can be used to collect "Owned" refrences to a certain - * type of managed object. Do not use this class directly, use ManagedMap or - * ManagedVector instead. This class only provides functionality which is common - * to list and map containers (iterators and state). - * - * @param T is the type of the Managed object that should be managed. - * @param Collection should be a STL container of Owned - */ -template -class ManagedContainer { -public: - using collection_type = Collection; - using value_type = typename collection_type::value_type; - using reference = typename collection_type::reference; - using const_reference = typename collection_type::const_reference; - using iterator = typename collection_type::iterator; - using const_iterator = typename collection_type::const_iterator; - using size_type = typename collection_type::size_type; - -protected: - /** - * Handle containing a reference to the owner of the collection. - */ - Handle owner; - - /** - * Underlying STL collection. - */ - collection_type c; - -protected: - /** - * Function which can be overridden by child classes to execute special code - * whenever a new element is added to the collection. - */ - virtual void addElement(value_type h) {} - - /** - * Function which can be overriden by child classes to execute special code - * whenever an element is removed from the collection. - */ - virtual void deleteElement(value_type h) {} - -public: - /** - * Constructor of the ManagedContainer class. - * - * @param owner is the managed object which owns the collection and all - * handles to other managed objects stored within. - */ - ManagedContainer(Handle owner) : owner(owner){}; - - /* State functions */ - size_type size() const noexcept { return c.size(); } - bool empty() const noexcept { return c.empty(); } - - /* Iterators */ - iterator begin() { return c.begin(); } - iterator end() { return c.end(); } - - iterator rbegin() { return c.rbegin(); } - iterator rend() { return c.rend(); } - - const_iterator begin() const { return c.cbegin(); } - const_iterator end() const { return c.cend(); } - - const_iterator cbegin() const { return c.cbegin(); } - const_iterator cend() const { return c.cend(); } - - const_iterator rbegin() const { return c.crbegin(); } - const_iterator rend() const { return c.crend(); } - - const_iterator crbegin() const { return c.crbegin(); } - const_iterator crend() const { return c.crend(); } - - /* Clear function */ - void clear() noexcept - { - for (const_iterator it = cbegin(); it != cend(); it++) { - deleteElement(*it); - } - c.clear(); - } -}; - -/** - * Template class which can be used to collect "Owned" refrences to a certain - * type of managed object. This class should be used in favour of other - * collections of handles, it takes care of acquiring an owned handle from the - * owner of this collection whenever a new element is added. - * - * @param T is the type of the Managed object that should be managed. - * @param Collection should be a STL list container of Owned - */ -template -class ManagedGenericList : public ManagedContainer { -private: - using Base = ManagedContainer; - -public: - using Base::ManagedContainer; - using collection_type = typename Base::collection_type; - using value_type = typename Base::value_type; - using reference = typename Base::reference; - using const_reference = typename Base::const_reference; - using iterator = typename Base::iterator; - using const_iterator = typename Base::const_iterator; - using size_type = typename Base::size_type; - - /** - * Initialize with an iterator from another collection. - * - * @param owner is the managed object which owns the collection and all - * handles to other managed objects stored within. - * @param first is an iterator pointing at the first element to be copied - * from some other collection. - * @param last is an iterator pointing at the last element to be copied - * from some other collection. - */ - template - ManagedGenericList(Handle owner, InputIterator first, - InputIterator last) - : ManagedContainer(owner) - { - insert(Base::c.begin(), first, last); - } - - /** - * Initialize with another collection. - * - * @param owner is the managed object which owns the collection and all - * handles to other managed objects stored within. - * @param in is a reference at some other collection with content that - * should be copied. - */ - template - ManagedGenericList(Handle owner, const InputCollection &in) - : ManagedContainer(owner) - { - for (const auto &e : in) { - push_back(e); - } - } - - /* Front and back */ - reference front() { return Base::c.front(); } - const_reference front() const { return Base::c.front(); } - reference back() { return Base::c.back(); } - const_reference back() const { return Base::c.back(); } - - /* Insert and delete operations */ - - iterator insert(const_iterator position, Handle h) - { - value_type v = Base::owner->acquire(h); - addElement(v); - return Base::c.insert(position, v); - } - - template - iterator insert(const_iterator position, InputIterator first, - InputIterator last) - { - bool atStart = true; - const_iterator pos = position; - for (InputIterator it = first; it != last; it++) { - if (atStart) { - atStart = false; - } else { - pos++; - } - pos = insert(pos, *it); - } - return pos; - } - - iterator find(const Handle h) - { - for (iterator it = Base::begin(); it != Base::end(); it++) { - if (*it == h) { - return it; - } - } - return Base::end(); - } - - const_iterator find(const Handle h) const - { - for (const_iterator it = Base::cbegin(); it != Base::cend(); it++) { - if (*it == h) { - return it; - } - } - return Base::cend(); - } - - void push_back(Handle h) - { - value_type v = Base::owner->acquire(h); - this->addElement(v); - Base::c.push_back(v); - } - - void pop_back() - { - if (!Base::empty()) { - this->deleteElement(back()); - } - Base::c.pop_back(); - } - - iterator erase(iterator position) - { - this->deleteElement(*position); - return Base::c.erase(position); - } - - iterator erase(iterator first, iterator last) - { - for (const_iterator it = first; it != last; it++) { - this->deleteElement(*it); - } - return Base::c.erase(first, last); - } -}; - -/** - * Special type of ManagedContainer based on an STL map. - */ -template -class ManagedGenericMap : public ManagedContainer { -private: - using Base = ManagedContainer; - -public: - using Base::ManagedContainer; - using collection_type = typename Base::collection_type; - using value_type = typename Base::value_type; - using key_type = typename Collection::key_type; - using reference = typename Base::reference; - using const_reference = typename Base::const_reference; - using iterator = typename Base::iterator; - using const_iterator = typename Base::const_iterator; - using size_type = typename Base::size_type; - -private: - value_type acquirePair(std::pair> val) - { - return value_type{val.first, Base::owner->acquire(val.second)}; - } - -public: - /** - * Initialize with an iterator from another collection. - * - * @param owner is the managed object which owns the collection and all - * handles to other managed objects stored within. - * @param first is an iterator pointing at the first element to be copied - * from some other collection. - * @param last is an iterator pointing at the last element to be copied - * from some other collection. - */ - template - ManagedGenericMap(Handle owner, InputIterator first, - InputIterator last) - : ManagedContainer(owner) - { - insert(first, last); - } - - /** - * Initialize with another collection. - * - * @param owner is the managed object which owns the collection and all - * handles to other managed objects stored within. - * @param in is a reference at some other collection with content that - * should be copied. - */ - template - ManagedGenericMap(Handle owner, const InputCollection &in) - : ManagedContainer(owner) - { - for (const auto &e : in) { - insert(*in); - } - } - - std::pair insert(std::pair> val) - { - value_type v = acquirePair(val); - this->addElement(v); - return Base::c.insert(v); - } - - iterator insert(const_iterator position, std::pair> val) - { - value_type v = acquirePair(val); - this->addElement(v); - return Base::c.insert(position, v); - } - - template - void insert(InputIterator first, InputIterator last) - { - for (auto it = first; it != last; it++) { - insert(acquirePair); - } - } - - iterator erase(const_iterator position) - { - this->deleteElement(*position); - return Base::c.erase(position); - } - - size_t erase(const key_type &k) - { - iterator pos = find(k); - if (pos != Base::end()) { - erase(pos); - return 1; - } - return 0; - } - - iterator erase(const_iterator first, const_iterator last) - { - for (const_iterator it = first; it != last; it++) { - this->deleteElement(*it); - } - return Base::c.erase(first, last); - } - - iterator find(const key_type &k) { return Base::c.find(k); } - const_iterator find(const key_type &k) const { return Base::c.find(k); } -}; - -/** - * Special type of ManagedGenericList based on an STL vector. - */ -template -class ManagedVector : public ManagedGenericList>> { -public: - using ManagedGenericList>>::ManagedGenericList; -}; - -/** - * Special type of ManagedGenericMap based on an STL map. - */ -template -class ManagedMap : public ManagedGenericMap>> { -public: - using ManagedGenericMap>>::ManagedGenericMap; -}; -} - -#endif /* _OUSIA_MANAGED_CONTAINERS_H_ */ - diff --git a/src/core/managed/Managed.cpp b/src/core/managed/Managed.cpp new file mode 100644 index 0000000..991f941 --- /dev/null +++ b/src/core/managed/Managed.cpp @@ -0,0 +1,27 @@ +/* + 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 . +*/ + +#include +#include + +#include "Managed.hpp" + +namespace ousia { + + +} diff --git a/src/core/managed/Managed.hpp b/src/core/managed/Managed.hpp new file mode 100644 index 0000000..04c2f84 --- /dev/null +++ b/src/core/managed/Managed.hpp @@ -0,0 +1,504 @@ +/* + 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 . +*/ + +#ifndef _OUSIA_MANAGED_HPP_ +#define _OUSIA_MANAGED_HPP_ + +#include "Manager.hpp" + +namespace ousia { + +template +class Handle; + +template +class Rooted; + +template +class Owned; + +// TODO: Implement clone, getReferenced and getReferencing + +/** + * 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: + /** + * mgr is the reference to the managed object manager which owns this + * managed object. + */ + Manager &mgr; + +public: + /** + * Constructor of the Managed class. Associates the new instance with the + * given Manager, which is now in charge for managing this instance. Never + * manually free instances of this class (even by using stack instances). + * Always use the Rooted and Owned smart pointer classes when refering to + * types derived from Managed. + * + * @param mgr is the Manager which should take ownership of this instance. + */ + Managed(Manager &mgr) : mgr(mgr) { mgr.manage(this); }; + + /** + * Virtual destuctor which may be overwritten by child classes. + */ + virtual ~Managed(){}; + + /** + * Returns a reference ot the manager instance which owns this managed + * object. + */ + Manager &getManager() { return mgr; } + + /** + * Acquires a reference to the object wraped in the given handle. + */ + template + Owned acquire(const Handle &h) + { + return Owned{h, this}; + } + + template + Owned acquire(Handle &&h) + { + return Owned{h, this}; + } + + template + Owned acquire(T *t) + { + return Owned{t, this}; + } + + template + std::vector> acquire(const std::vector> &vec) + { + std::vector> res; + for (auto &e : vec) { + res.push_back(acquire(e)); + } + return res; + } + + template + std::vector> acquire(const std::vector &vec) + { + std::vector> res; + for (auto &e : vec) { + res.push_back(acquire(e)); + } + return res; + } +}; + +/** + * 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 Handle { +protected: + friend class Rooted; + friend class Owned; + + /** + * 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 &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 + Handle(const Handle &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 for immutable handles. + */ + const T *operator->() const { return ptr; } + + /** + * Provides access to the underlying managed object. + */ + T &operator*() { return *ptr; } + + /** + * Provides access to the underlying managed object for immutable handles. + */ + const T &operator*() const { return *ptr; } + + /** + * Comparison operator between base Owned and base Owned. + */ + template + bool operator==(const Handle &h) const + { + return ptr == h.get(); + } + + /** + * Comparison operator between base Owned and pointer. + */ + friend bool operator==(const Handle &h, const Managed *o) + { + return h.get() == o; + } + + /** + * Comparison operator between base Owned and pointer. + */ + friend bool operator==(const Managed *o, const Handle &h) + { + return o == h.get(); + } + + /** + * 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(); } + + /** + * Statically casts the handle to a handle of the given type. + */ + template + Handle cast() + { + return Handle{static_cast(ptr)}; + } +}; + +/** + * 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 Rooted : public Handle { +private: + void addRef() + { + if (Handle::ptr) { + Handle::ptr->getManager().addRef(Handle::ptr, nullptr); + } + } + + void deleteRef() + { + if (Handle::ptr) { + Handle::ptr->getManager().deleteRef(Handle::ptr, nullptr); + } + } + +public: + /** + * Creates an empty Owned. + */ + Rooted() : Handle(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 &h) : Handle(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 &&h) : Handle(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(ptr) { addRef(); } + + /** + * Constructor of the Rooted class. + * + * @param h is another Rooted whose managed object should be used. + */ + template + Rooted(const Handle &h) + : Handle(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 &operator=(const Rooted &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 &operator=(Rooted &&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 + Rooted &operator=(const Handle &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 &operator=(Handle &&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 Owned : public Handle { +private: + Managed *owner; + + void addRef() + { + if (Handle::ptr && owner) { + owner->getManager().addRef(Handle::ptr, owner); + } + } + + void deleteRef() + { + if (Handle::ptr && owner) { + owner->getManager().deleteRef(Handle::ptr, owner); + } + } + +public: + /** + * Creates an empty Owned. + */ + Owned() : Handle(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 &h) : Handle(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 + Owned(const Owned &h) + : Handle(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 &&h) : Handle(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 &operator=(const Owned &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 &operator=(Owned &&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(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 + Owned(const Handle &h, Managed *owner) + : Handle(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_MANAGED_HPP_ */ + diff --git a/src/core/managed/ManagedContainer.cpp b/src/core/managed/ManagedContainer.cpp new file mode 100644 index 0000000..e7f30fa --- /dev/null +++ b/src/core/managed/ManagedContainer.cpp @@ -0,0 +1,24 @@ +/* + 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 . +*/ + +#include "ManagedContainer.hpp" + +namespace ousia { + +} + diff --git a/src/core/managed/ManagedContainer.hpp b/src/core/managed/ManagedContainer.hpp new file mode 100644 index 0000000..9ff75d5 --- /dev/null +++ b/src/core/managed/ManagedContainer.hpp @@ -0,0 +1,391 @@ +/* + 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 . +*/ + +#ifndef _OUSIA_MANAGED_CONTAINER_H_ +#define _OUSIA_MANAGED_CONTAINER_H_ + +#include +#include +#include +#include +#include +#include + +#include "Managed.hpp" + +namespace ousia { + +/** + * Template class which can be used to collect "Owned" refrences to a certain + * type of managed object. Do not use this class directly, use ManagedMap or + * ManagedVector instead. This class only provides functionality which is common + * to list and map containers (iterators and state). + * + * @param T is the type of the Managed object that should be managed. + * @param Collection should be a STL container of Owned + */ +template +class ManagedContainer { +public: + using collection_type = Collection; + using value_type = typename collection_type::value_type; + using reference = typename collection_type::reference; + using const_reference = typename collection_type::const_reference; + using iterator = typename collection_type::iterator; + using const_iterator = typename collection_type::const_iterator; + using size_type = typename collection_type::size_type; + +protected: + /** + * Handle containing a reference to the owner of the collection. + */ + Handle owner; + + /** + * Underlying STL collection. + */ + collection_type c; + +protected: + /** + * Function which can be overridden by child classes to execute special code + * whenever a new element is added to the collection. + */ + virtual void addElement(value_type h) {} + + /** + * Function which can be overriden by child classes to execute special code + * whenever an element is removed from the collection. + */ + virtual void deleteElement(value_type h) {} + +public: + /** + * Constructor of the ManagedContainer class. + * + * @param owner is the managed object which owns the collection and all + * handles to other managed objects stored within. + */ + ManagedContainer(Handle owner) : owner(owner){}; + + /* State functions */ + size_type size() const noexcept { return c.size(); } + bool empty() const noexcept { return c.empty(); } + + /* Iterators */ + iterator begin() { return c.begin(); } + iterator end() { return c.end(); } + + iterator rbegin() { return c.rbegin(); } + iterator rend() { return c.rend(); } + + const_iterator begin() const { return c.cbegin(); } + const_iterator end() const { return c.cend(); } + + const_iterator cbegin() const { return c.cbegin(); } + const_iterator cend() const { return c.cend(); } + + const_iterator rbegin() const { return c.crbegin(); } + const_iterator rend() const { return c.crend(); } + + const_iterator crbegin() const { return c.crbegin(); } + const_iterator crend() const { return c.crend(); } + + /* Clear function */ + void clear() noexcept + { + for (const_iterator it = cbegin(); it != cend(); it++) { + deleteElement(*it); + } + c.clear(); + } +}; + +/** + * Template class which can be used to collect "Owned" refrences to a certain + * type of managed object. This class should be used in favour of other + * collections of handles, it takes care of acquiring an owned handle from the + * owner of this collection whenever a new element is added. + * + * @param T is the type of the Managed object that should be managed. + * @param Collection should be a STL list container of Owned + */ +template +class ManagedGenericList : public ManagedContainer { +private: + using Base = ManagedContainer; + +public: + using Base::ManagedContainer; + using collection_type = typename Base::collection_type; + using value_type = typename Base::value_type; + using reference = typename Base::reference; + using const_reference = typename Base::const_reference; + using iterator = typename Base::iterator; + using const_iterator = typename Base::const_iterator; + using size_type = typename Base::size_type; + + /** + * Initialize with an iterator from another collection. + * + * @param owner is the managed object which owns the collection and all + * handles to other managed objects stored within. + * @param first is an iterator pointing at the first element to be copied + * from some other collection. + * @param last is an iterator pointing at the last element to be copied + * from some other collection. + */ + template + ManagedGenericList(Handle owner, InputIterator first, + InputIterator last) + : ManagedContainer(owner) + { + insert(Base::c.begin(), first, last); + } + + /** + * Initialize with another collection. + * + * @param owner is the managed object which owns the collection and all + * handles to other managed objects stored within. + * @param in is a reference at some other collection with content that + * should be copied. + */ + template + ManagedGenericList(Handle owner, const InputCollection &in) + : ManagedContainer(owner) + { + for (const auto &e : in) { + push_back(e); + } + } + + /* Front and back */ + reference front() { return Base::c.front(); } + const_reference front() const { return Base::c.front(); } + reference back() { return Base::c.back(); } + const_reference back() const { return Base::c.back(); } + + /* Insert and delete operations */ + + iterator insert(const_iterator position, Handle h) + { + value_type v = Base::owner->acquire(h); + addElement(v); + return Base::c.insert(position, v); + } + + template + iterator insert(const_iterator position, InputIterator first, + InputIterator last) + { + bool atStart = true; + const_iterator pos = position; + for (InputIterator it = first; it != last; it++) { + if (atStart) { + atStart = false; + } else { + pos++; + } + pos = insert(pos, *it); + } + return pos; + } + + iterator find(const Handle h) + { + for (iterator it = Base::begin(); it != Base::end(); it++) { + if (*it == h) { + return it; + } + } + return Base::end(); + } + + const_iterator find(const Handle h) const + { + for (const_iterator it = Base::cbegin(); it != Base::cend(); it++) { + if (*it == h) { + return it; + } + } + return Base::cend(); + } + + void push_back(Handle h) + { + value_type v = Base::owner->acquire(h); + this->addElement(v); + Base::c.push_back(v); + } + + void pop_back() + { + if (!Base::empty()) { + this->deleteElement(back()); + } + Base::c.pop_back(); + } + + iterator erase(iterator position) + { + this->deleteElement(*position); + return Base::c.erase(position); + } + + iterator erase(iterator first, iterator last) + { + for (const_iterator it = first; it != last; it++) { + this->deleteElement(*it); + } + return Base::c.erase(first, last); + } +}; + +/** + * Special type of ManagedContainer based on an STL map. + */ +template +class ManagedGenericMap : public ManagedContainer { +private: + using Base = ManagedContainer; + +public: + using Base::ManagedContainer; + using collection_type = typename Base::collection_type; + using value_type = typename Base::value_type; + using key_type = typename Collection::key_type; + using reference = typename Base::reference; + using const_reference = typename Base::const_reference; + using iterator = typename Base::iterator; + using const_iterator = typename Base::const_iterator; + using size_type = typename Base::size_type; + +private: + value_type acquirePair(std::pair> val) + { + return value_type{val.first, Base::owner->acquire(val.second)}; + } + +public: + /** + * Initialize with an iterator from another collection. + * + * @param owner is the managed object which owns the collection and all + * handles to other managed objects stored within. + * @param first is an iterator pointing at the first element to be copied + * from some other collection. + * @param last is an iterator pointing at the last element to be copied + * from some other collection. + */ + template + ManagedGenericMap(Handle owner, InputIterator first, + InputIterator last) + : ManagedContainer(owner) + { + insert(first, last); + } + + /** + * Initialize with another collection. + * + * @param owner is the managed object which owns the collection and all + * handles to other managed objects stored within. + * @param in is a reference at some other collection with content that + * should be copied. + */ + template + ManagedGenericMap(Handle owner, const InputCollection &in) + : ManagedContainer(owner) + { + for (const auto &e : in) { + insert(*in); + } + } + + std::pair insert(std::pair> val) + { + value_type v = acquirePair(val); + this->addElement(v); + return Base::c.insert(v); + } + + iterator insert(const_iterator position, std::pair> val) + { + value_type v = acquirePair(val); + this->addElement(v); + return Base::c.insert(position, v); + } + + template + void insert(InputIterator first, InputIterator last) + { + for (auto it = first; it != last; it++) { + insert(acquirePair); + } + } + + iterator erase(const_iterator position) + { + this->deleteElement(*position); + return Base::c.erase(position); + } + + size_t erase(const key_type &k) + { + iterator pos = find(k); + if (pos != Base::end()) { + erase(pos); + return 1; + } + return 0; + } + + iterator erase(const_iterator first, const_iterator last) + { + for (const_iterator it = first; it != last; it++) { + this->deleteElement(*it); + } + return Base::c.erase(first, last); + } + + iterator find(const key_type &k) { return Base::c.find(k); } + const_iterator find(const key_type &k) const { return Base::c.find(k); } +}; + +/** + * Special type of ManagedGenericList based on an STL vector. + */ +template +class ManagedVector : public ManagedGenericList>> { +public: + using ManagedGenericList>>::ManagedGenericList; +}; + +/** + * Special type of ManagedGenericMap based on an STL map. + */ +template +class ManagedMap : public ManagedGenericMap>> { +public: + using ManagedGenericMap>>::ManagedGenericMap; +}; +} + +#endif /* _OUSIA_MANAGED_CONTAINER_H_ */ + 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 . +*/ + +#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 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 visited{{curManaged}}; + std::queue 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/managed/Manager.hpp b/src/core/managed/Manager.hpp new file mode 100644 index 0000000..95d08e1 --- /dev/null +++ b/src/core/managed/Manager.hpp @@ -0,0 +1,250 @@ +/* + 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 . +*/ + +/** + * @file Manager.hpp + * + * Definition of the Manager class used for garbage collection. + * + * @author Andreas Stöckel (astoecke@techfak.uni-bielefeld.de) + */ + +#ifndef _OUSIA_MANAGER_HPP_ +#define _OUSIA_MANAGER_HPP_ + +#include +#include +#include +#include +#include +#include + +namespace ousia { + +// Forward declaration +class Managed; + +class Manager { +public: + /** + * 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 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 refOut; + + /** + * Default constructor of the ObjectDescriptor class. + */ + ObjectDescriptor() : rootRefCount(0){}; + + /** + * Returns true, if the ObjectDescriptor has at least one input + * reference. + */ + bool hasInRef() 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); + }; + +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 objects; + + /** + * Set containing the objects marked for sweeping. + */ + std::unordered_set marked; + + /** + * Set containing objects marked for deletion. + */ + std::unordered_set 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(); +}; +} + +#endif /* _OUSIA_MANAGER_HPP_ */ + diff --git a/test/core/ManagedContainersTest.cpp b/test/core/ManagedContainersTest.cpp deleted file mode 100644 index 3abbd4d..0000000 --- a/test/core/ManagedContainersTest.cpp +++ /dev/null @@ -1,80 +0,0 @@ -/* - 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 . -*/ - -#include - -#include - -#include -#include - -#include "TestManaged.hpp" - -namespace ousia { - -TEST(ManagedVector, managedVector) -{ - // TODO: This test is highly incomplete - - constexpr int nElem = 16; - std::array a; - - Manager mgr(1); - { - Rooted root{new Managed{mgr}}; - - std::vector elems; - for (int i = 0; i < nElem; i++) { - elems.push_back(new TestManaged{mgr, a[i]}); - } - - for (bool v : a) { - ASSERT_TRUE(v); - } - - ManagedVector v(root, elems); - - // Remove the last element from the list. It should be garbage collected. - v.pop_back(); - ASSERT_FALSE(a[nElem - 1]); - - // Insert a new element into the list. - v.push_back(new TestManaged{mgr, a[nElem - 1]}); - ASSERT_TRUE(a[nElem - 1]); - - // Erase element 10 - { - auto it = v.find(elems[10]); - ASSERT_TRUE(it != v.end()); - v.erase(it); - ASSERT_FALSE(a[10]); - } - - // Erase element 3 - 5 - v.erase(v.find(elems[3]), v.find(elems[5])); - ASSERT_FALSE(a[3] || a[4]); - ASSERT_TRUE(a[5]); - } - - for (bool v : a) { - ASSERT_FALSE(v); - } -} - -} - diff --git a/test/core/ManagedTest.cpp b/test/core/ManagedTest.cpp deleted file mode 100644 index ab60f04..0000000 --- a/test/core/ManagedTest.cpp +++ /dev/null @@ -1,515 +0,0 @@ -/* - 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 . -*/ - -#include -#include -#include - -#include - -#include - -#include "TestManaged.hpp" - -namespace ousia { - -/* Class ObjectDescriptor */ - -TEST(ObjectDescriptor, degree) -{ - // Do not use actual Managed in this test -- we don't want to test their - // behaviour - ObjectDescriptor nd; - Managed *n1 = reinterpret_cast(intptr_t{0x10}); - Managed *n2 = reinterpret_cast(intptr_t{0x20}); - - // Input degree - ASSERT_EQ(0, nd.refIn.size()); - ASSERT_EQ(0, nd.refInCount(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.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.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.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.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.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.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.decrDegree(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.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.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.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.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.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.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.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.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(ObjectDescriptor, rootRefCount) -{ - ObjectDescriptor nd; - ASSERT_EQ(0, nd.rootRefCount); - - nd.incrDegree(RefDir::IN, nullptr); - ASSERT_EQ(1, nd.rootRefCount); - - nd.incrDegree(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.decrDegree(RefDir::OUT, nullptr)); - ASSERT_EQ(1, nd.rootRefCount); - - ASSERT_TRUE(nd.decrDegree(RefDir::IN, nullptr)); - ASSERT_EQ(0, nd.rootRefCount); - - ASSERT_FALSE(nd.decrDegree(RefDir::IN, nullptr)); - ASSERT_EQ(0, nd.rootRefCount); -} - -/* Class Owned */ - -TEST(Owned, equalsAndAssign) -{ - Manager mgr(1); - - Managed *n1 = new Managed(mgr), *n2 = new Managed(mgr); - - Rooted rh1{n1}; - Rooted rh2{n2}; - - Owned h2{n2, n1}; - - // Equals operator - ASSERT_TRUE(rh1 == n1); - ASSERT_TRUE(n1 == rh1); - ASSERT_FALSE(rh1 == rh2); - ASSERT_TRUE(rh2 == h2); - ASSERT_TRUE(h2 == rh2); - - // Assignment operator - Rooted rh2b; - - ASSERT_FALSE(rh2b == rh2); - rh2b = rh2; - ASSERT_TRUE(rh2b == rh2); - ASSERT_TRUE(rh2b == h2); - - rh2b = h2; - ASSERT_TRUE(rh2b == h2); - - Owned h2b; - ASSERT_FALSE(rh2 == h2b); - ASSERT_FALSE(h2 == h2b); - h2b = h2; - ASSERT_TRUE(rh2 == h2b); - ASSERT_TRUE(h2 == h2b); - - Owned h2c{h2b, n1}; - ASSERT_TRUE(h2b == h2c); -} - -/* Class Manager */ - -TEST(Manager, linearDependencies) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1, *n2, *n3; - n1 = new TestManaged(mgr, a[1]); - n2 = new TestManaged(mgr, a[2]); - n3 = new TestManaged(mgr, a[3]); - - { - Rooted hr{new TestManaged(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(Manager, cyclicDependencies) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1, *n2, *n3; - n1 = new TestManaged(mgr, a[1]); - n2 = new TestManaged(mgr, a[2]); - n3 = new TestManaged(mgr, a[3]); - - { - Rooted hr{new TestManaged(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); - } - } -} - -TEST(Manager, selfReferentialCyclicDependencies) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1; - n1 = new TestManaged(mgr, a[1]); - - { - Rooted hr{new TestManaged(mgr, a[0])}; - ASSERT_TRUE(a[0] && a[1]); - hr->addRef(n1); - n1->addRef(n1); - } - - // All nodes must have set their "alive" flag to false - ASSERT_FALSE(a[0] || a[1]); - } -} - -TEST(Manager, doubleRooted) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1, *n2; - n1 = new TestManaged(mgr, a[1]); - n2 = new TestManaged(mgr, a[2]); - - { - Rooted hr1{new TestManaged(mgr, a[0])}; - { - Rooted hr2{new TestManaged(mgr, a[3])}; - - // All nodes must have set their "alive" flag to true - for (bool v : a) { - ASSERT_TRUE(v); - } - - // Reference n1 and n2 in the rooted nodes - hr1->addRef(n1); - hr2->addRef(n2); - - // Create cyclical dependency between n2 and n1 - n1->addRef(n2); - n2->addRef(n1); - } - - // hr2 is dead, all other nodes are still alive - ASSERT_FALSE(a[3]); - ASSERT_TRUE(a[0] && a[1] && a[2]); - } - - // All nodes are dead - for (bool v : a) { - ASSERT_FALSE(v); - } - } -} - -TEST(Manager, disconnectSubgraph) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1, *n2, *n3; - n1 = new TestManaged(mgr, a[1]); - n2 = new TestManaged(mgr, a[2]); - n3 = new TestManaged(mgr, a[3]); - - { - Rooted hr{new TestManaged(mgr, a[0])}; - - // Create a linear dependency chain - hr->addRef(n1); - n1->addRef(n2); - n2->addRef(n3); - - // All nodes must have set their "alive" flag to true - for (bool v : a) { - ASSERT_TRUE(v); - } - - // Remove the reference from n1 to n2 - n1->deleteRef(n2); - - // Nodes 2 and 3 must be dead, all others alive - ASSERT_FALSE(a[2] || a[3]); - ASSERT_TRUE(a[0] && a[1]); - } - - // All nodes must have set their "alive" flag to false - for (bool v : a) { - ASSERT_FALSE(v); - } - } -} - -TEST(Manager, disconnectDoubleRootedSubgraph) -{ - std::array a; - - Manager mgr(1); - { - TestManaged *n1, *n2, *n3; - n1 = new TestManaged(mgr, a[1]); - n2 = new TestManaged(mgr, a[2]); - n3 = new TestManaged(mgr, a[3]); - - { - Rooted hr1{new TestManaged(mgr, a[0])}; - { - Rooted hr2{new TestManaged(mgr, a[4])}; - - // Create a cyclic dependency chain with two rooted nodes - hr1->addRef(n1); - n1->addRef(n2); - n2->addRef(n3); - n3->addRef(n1); - hr2->addRef(n3); - - // All nodes must have set their "alive" flag to true - for (bool v : a) { - ASSERT_TRUE(v); - } - - // Remove the reference from n3 to n1 - n3->deleteRef(n1); - - // Still all nodes must have set their "alive" flag to true - for (bool v : a) { - ASSERT_TRUE(v); - } - - // Remove the reference from n1 to n2 - n1->deleteRef(n2); - - // Managed 2 must be dead, all others alive - ASSERT_FALSE(a[2]); - ASSERT_TRUE(a[0] && a[1] && a[3] && a[4]); - } - - // Managed 2, 3, hr2 must be dead, all others alive - ASSERT_FALSE(a[2] || a[3] || a[4]); - ASSERT_TRUE(a[0] && a[1]); - } - - // All nodes must have set their "alive" flag to false - for (bool v : a) { - ASSERT_FALSE(v); - } - } -} - -Rooted createFullyConnectedGraph(Manager &mgr, int nElem, - bool alive[]) -{ - std::vector> nodes; - - // Create the nodes - for (int i = 0; i < nElem; i++) { - nodes.push_back(Rooted{new TestManaged{mgr, alive[i]}}); - } - - // Add all connections - for (int i = 0; i < nElem; i++) { - for (int j = 0; j < nElem; j++) { - nodes[i]->addRef(nodes[j]); - } - } - - return nodes[0]; -} - -TEST(Manager, fullyConnectedGraph) -{ - constexpr int nElem = 64; - std::array a; - - Manager mgr(1); - { - Rooted n = createFullyConnectedGraph(mgr, nElem, &a[0]); - for (bool v : a) { - ASSERT_TRUE(v); - } - } - - for (bool v : a) { - ASSERT_FALSE(v); - } -} - -class HidingTestManaged : public TestManaged { - -private: - Rooted hidden; - -public: - - HidingTestManaged(Manager &mgr, bool &alive) : TestManaged(mgr, alive) {}; - - void setHiddenRef(Handle t) { - hidden = t; - } - -}; - -TEST(Manager, hiddenRootedGraph) -{ - constexpr int nElem = 16; - std::array a; - bool b; - Manager mgr(1); - - { - Rooted n{new HidingTestManaged{mgr, b}}; - n->setHiddenRef(createFullyConnectedGraph(mgr, nElem, &a[0])); - - ASSERT_TRUE(b); - for (bool v : a) { - ASSERT_TRUE(v); - } - } - - ASSERT_FALSE(b); - for (bool v : a) { - ASSERT_FALSE(v); - } -} - -} - diff --git a/test/core/TestManaged.hpp b/test/core/TestManaged.hpp deleted file mode 100644 index 3b93e51..0000000 --- a/test/core/TestManaged.hpp +++ /dev/null @@ -1,62 +0,0 @@ -/* - 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 . -*/ - -#ifndef _TEST_MANAGED_H_ -#define _TEST_MANAGED_H_ - -#include - -namespace ousia { - -class TestManaged : public Managed { -private: - bool &alive; - - std::vector> refs; - -public: - TestManaged(Manager &mgr, bool &alive) : Managed(mgr), alive(alive) - { - //std::cout << "create TestManaged @" << this << std::endl; - alive = true; - } - - ~TestManaged() override - { - //std::cout << "delete TestManaged @" << this << std::endl; - alive = false; - } - - void addRef(Handle h) { refs.push_back(acquire(h)); } - - void deleteRef(Handle h) - { - for (auto it = refs.begin(); it != refs.end();) { - if (*it == h) { - it = refs.erase(it); - } else { - it++; - } - } - } -}; - -} - -#endif /* _TEST_MANAGED_H_ */ - diff --git a/test/core/managed/ManagedContainerTest.cpp b/test/core/managed/ManagedContainerTest.cpp new file mode 100644 index 0000000..db72295 --- /dev/null +++ b/test/core/managed/ManagedContainerTest.cpp @@ -0,0 +1,80 @@ +/* + 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 . +*/ + +#include + +#include + +#include +#include + +#include "TestManaged.hpp" + +namespace ousia { + +TEST(ManagedVector, managedVector) +{ + // TODO: This test is highly incomplete + + constexpr int nElem = 16; + std::array a; + + Manager mgr(1); + { + Rooted root{new Managed{mgr}}; + + std::vector elems; + for (int i = 0; i < nElem; i++) { + elems.push_back(new TestManaged{mgr, a[i]}); + } + + for (bool v : a) { + ASSERT_TRUE(v); + } + + ManagedVector v(root, elems); + + // Remove the last element from the list. It should be garbage collected. + v.pop_back(); + ASSERT_FALSE(a[nElem - 1]); + + // Insert a new element into the list. + v.push_back(new TestManaged{mgr, a[nElem - 1]}); + ASSERT_TRUE(a[nElem - 1]); + + // Erase element 10 + { + auto it = v.find(elems[10]); + ASSERT_TRUE(it != v.end()); + v.erase(it); + ASSERT_FALSE(a[10]); + } + + // Erase element 3 - 5 + v.erase(v.find(elems[3]), v.find(elems[5])); + ASSERT_FALSE(a[3] || a[4]); + ASSERT_TRUE(a[5]); + } + + for (bool v : a) { + ASSERT_FALSE(v); + } +} + +} + diff --git a/test/core/managed/ManagedTest.cpp b/test/core/managed/ManagedTest.cpp new file mode 100644 index 0000000..e8a24f2 --- /dev/null +++ b/test/core/managed/ManagedTest.cpp @@ -0,0 +1,22 @@ +/* + 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 . +*/ + +namespace ousia { + +} + diff --git a/test/core/managed/ManagerTest.cpp b/test/core/managed/ManagerTest.cpp new file mode 100644 index 0000000..da42f0a --- /dev/null +++ b/test/core/managed/ManagerTest.cpp @@ -0,0 +1,552 @@ +/* + 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 . +*/ + +#include +#include +#include + +#include + +#include + +#include "TestManaged.hpp" + +namespace ousia { + +/* Class ObjectDescriptor */ + +class TestObjectDescriptor : public Manager::ObjectDescriptor { +public: + int refInCount() const + { + int res = 0; + for (const auto &e : refIn) { + res += e.second; + } + return res + rootRefCount; + } + + int refOutCount() const + { + int res = 0; + for (const auto &e : refOut) { + res += e.second; + } + return res; + } + + int 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 refOutCount(Managed *o) const + { + const auto it = refOut.find(o); + if (it != refOut.cend()) { + return it->second; + } + return 0; + } +}; + +TEST(ObjectDescriptor, degree) +{ + // Do not use actual Managed in this test -- we don't want to test their + // behaviour + TestObjectDescriptor nd; + Managed *n1 = reinterpret_cast(intptr_t{0x10}); + Managed *n2 = reinterpret_cast(intptr_t{0x20}); + + // Input degree + ASSERT_EQ(0U, nd.refIn.size()); + ASSERT_EQ(0, nd.refInCount(n1)); + + nd.incrDegree(Manager::RefDir::IN, n1); + ASSERT_EQ(1, nd.refInCount()); + ASSERT_EQ(1, nd.refInCount(n1)); + ASSERT_EQ(0, nd.refInCount(n2)); + ASSERT_EQ(1U, nd.refIn.size()); + + nd.incrDegree(Manager::RefDir::IN, n1); + ASSERT_EQ(2, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(n1)); + ASSERT_EQ(0, nd.refInCount(n2)); + ASSERT_EQ(1U, nd.refIn.size()); + + nd.incrDegree(Manager::RefDir::IN, n2); + ASSERT_EQ(3, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(n1)); + ASSERT_EQ(1, nd.refInCount(n2)); + ASSERT_EQ(2U, nd.refIn.size()); + + nd.incrDegree(Manager::RefDir::IN, nullptr); + ASSERT_EQ(4, nd.refInCount()); + ASSERT_EQ(2, nd.refInCount(n1)); + ASSERT_EQ(1, nd.refInCount(n2)); + ASSERT_EQ(2U, nd.refIn.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, n1)); + ASSERT_EQ(3, nd.refInCount()); + ASSERT_EQ(1, nd.refInCount(n1)); + ASSERT_EQ(1, nd.refInCount(n2)); + ASSERT_EQ(2U, nd.refIn.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, n1)); + ASSERT_EQ(2, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(n1)); + ASSERT_EQ(1, nd.refInCount(n2)); + ASSERT_EQ(1U, nd.refIn.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, n2)); + ASSERT_EQ(1, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(n1)); + ASSERT_EQ(0, nd.refInCount(n2)); + ASSERT_EQ(0U, nd.refIn.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, nullptr)); + ASSERT_EQ(0, nd.refInCount()); + ASSERT_EQ(0, nd.refInCount(n1)); + ASSERT_EQ(0, nd.refInCount(n2)); + ASSERT_EQ(0U, nd.refIn.size()); + + // Output degree + ASSERT_EQ(0U, nd.refOut.size()); + ASSERT_EQ(0, nd.refOutCount(n1)); + + nd.incrDegree(Manager::RefDir::OUT, n1); + ASSERT_EQ(1, nd.refOutCount()); + ASSERT_EQ(1, nd.refOutCount(n1)); + ASSERT_EQ(0, nd.refOutCount(n2)); + ASSERT_EQ(1U, nd.refOut.size()); + + nd.incrDegree(Manager::RefDir::OUT, n1); + ASSERT_EQ(2, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(n1)); + ASSERT_EQ(0, nd.refOutCount(n2)); + ASSERT_EQ(1U, nd.refOut.size()); + + nd.incrDegree(Manager::RefDir::OUT, n2); + ASSERT_EQ(3, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(n1)); + ASSERT_EQ(1, nd.refOutCount(n2)); + ASSERT_EQ(2U, nd.refOut.size()); + + nd.incrDegree(Manager::RefDir::OUT, nullptr); + ASSERT_EQ(3, nd.refOutCount()); + ASSERT_EQ(2, nd.refOutCount(n1)); + ASSERT_EQ(1, nd.refOutCount(n2)); + ASSERT_EQ(2U, nd.refOut.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::OUT, n1)); + ASSERT_EQ(2, nd.refOutCount()); + ASSERT_EQ(1, nd.refOutCount(n1)); + ASSERT_EQ(1, nd.refOutCount(n2)); + ASSERT_EQ(2U, nd.refOut.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::OUT, n1)); + ASSERT_EQ(1, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(n1)); + ASSERT_EQ(1, nd.refOutCount(n2)); + ASSERT_EQ(1U, nd.refOut.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::OUT, n2)); + ASSERT_EQ(0, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(n1)); + ASSERT_EQ(0, nd.refOutCount(n2)); + ASSERT_EQ(0U, nd.refOut.size()); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::OUT, nullptr)); + ASSERT_EQ(0, nd.refOutCount()); + ASSERT_EQ(0, nd.refOutCount(n1)); + ASSERT_EQ(0, nd.refOutCount(n2)); + ASSERT_EQ(0U, nd.refOut.size()); +} + +TEST(ObjectDescriptor, rootRefCount) +{ + TestObjectDescriptor nd; + ASSERT_EQ(0, nd.rootRefCount); + + nd.incrDegree(Manager::RefDir::IN, nullptr); + ASSERT_EQ(1, nd.rootRefCount); + + nd.incrDegree(Manager::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.decrDegree(Manager::RefDir::OUT, nullptr)); + ASSERT_EQ(1, nd.rootRefCount); + + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, nullptr)); + ASSERT_EQ(0, nd.rootRefCount); + + ASSERT_FALSE(nd.decrDegree(Manager::RefDir::IN, nullptr)); + ASSERT_EQ(0, nd.rootRefCount); +} + +/* Class Owned */ + +TEST(Owned, equalsAndAssign) +{ + Manager mgr(1); + + Managed *n1 = new Managed(mgr), *n2 = new Managed(mgr); + + Rooted rh1{n1}; + Rooted rh2{n2}; + + Owned h2{n2, n1}; + + // Equals operator + ASSERT_TRUE(rh1 == n1); + ASSERT_TRUE(n1 == rh1); + ASSERT_FALSE(rh1 == rh2); + ASSERT_TRUE(rh2 == h2); + ASSERT_TRUE(h2 == rh2); + + // Assignment operator + Rooted rh2b; + + ASSERT_FALSE(rh2b == rh2); + rh2b = rh2; + ASSERT_TRUE(rh2b == rh2); + ASSERT_TRUE(rh2b == h2); + + rh2b = h2; + ASSERT_TRUE(rh2b == h2); + + Owned h2b; + ASSERT_FALSE(rh2 == h2b); + ASSERT_FALSE(h2 == h2b); + h2b = h2; + ASSERT_TRUE(rh2 == h2b); + ASSERT_TRUE(h2 == h2b); + + Owned h2c{h2b, n1}; + ASSERT_TRUE(h2b == h2c); +} + +/* Class Manager */ + +TEST(Manager, linearDependencies) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1, *n2, *n3; + n1 = new TestManaged(mgr, a[1]); + n2 = new TestManaged(mgr, a[2]); + n3 = new TestManaged(mgr, a[3]); + + { + Rooted hr{new TestManaged(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(Manager, cyclicDependencies) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1, *n2, *n3; + n1 = new TestManaged(mgr, a[1]); + n2 = new TestManaged(mgr, a[2]); + n3 = new TestManaged(mgr, a[3]); + + { + Rooted hr{new TestManaged(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); + } + } +} + +TEST(Manager, selfReferentialCyclicDependencies) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1; + n1 = new TestManaged(mgr, a[1]); + + { + Rooted hr{new TestManaged(mgr, a[0])}; + ASSERT_TRUE(a[0] && a[1]); + hr->addRef(n1); + n1->addRef(n1); + } + + // All nodes must have set their "alive" flag to false + ASSERT_FALSE(a[0] || a[1]); + } +} + +TEST(Manager, doubleRooted) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1, *n2; + n1 = new TestManaged(mgr, a[1]); + n2 = new TestManaged(mgr, a[2]); + + { + Rooted hr1{new TestManaged(mgr, a[0])}; + { + Rooted hr2{new TestManaged(mgr, a[3])}; + + // All nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Reference n1 and n2 in the rooted nodes + hr1->addRef(n1); + hr2->addRef(n2); + + // Create cyclical dependency between n2 and n1 + n1->addRef(n2); + n2->addRef(n1); + } + + // hr2 is dead, all other nodes are still alive + ASSERT_FALSE(a[3]); + ASSERT_TRUE(a[0] && a[1] && a[2]); + } + + // All nodes are dead + for (bool v : a) { + ASSERT_FALSE(v); + } + } +} + +TEST(Manager, disconnectSubgraph) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1, *n2, *n3; + n1 = new TestManaged(mgr, a[1]); + n2 = new TestManaged(mgr, a[2]); + n3 = new TestManaged(mgr, a[3]); + + { + Rooted hr{new TestManaged(mgr, a[0])}; + + // Create a linear dependency chain + hr->addRef(n1); + n1->addRef(n2); + n2->addRef(n3); + + // All nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Remove the reference from n1 to n2 + n1->deleteRef(n2); + + // Nodes 2 and 3 must be dead, all others alive + ASSERT_FALSE(a[2] || a[3]); + ASSERT_TRUE(a[0] && a[1]); + } + + // All nodes must have set their "alive" flag to false + for (bool v : a) { + ASSERT_FALSE(v); + } + } +} + +TEST(Manager, disconnectDoubleRootedSubgraph) +{ + std::array a; + + Manager mgr(1); + { + TestManaged *n1, *n2, *n3; + n1 = new TestManaged(mgr, a[1]); + n2 = new TestManaged(mgr, a[2]); + n3 = new TestManaged(mgr, a[3]); + + { + Rooted hr1{new TestManaged(mgr, a[0])}; + { + Rooted hr2{new TestManaged(mgr, a[4])}; + + // Create a cyclic dependency chain with two rooted nodes + hr1->addRef(n1); + n1->addRef(n2); + n2->addRef(n3); + n3->addRef(n1); + hr2->addRef(n3); + + // All nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Remove the reference from n3 to n1 + n3->deleteRef(n1); + + // Still all nodes must have set their "alive" flag to true + for (bool v : a) { + ASSERT_TRUE(v); + } + + // Remove the reference from n1 to n2 + n1->deleteRef(n2); + + // Managed 2 must be dead, all others alive + ASSERT_FALSE(a[2]); + ASSERT_TRUE(a[0] && a[1] && a[3] && a[4]); + } + + // Managed 2, 3, hr2 must be dead, all others alive + ASSERT_FALSE(a[2] || a[3] || a[4]); + ASSERT_TRUE(a[0] && a[1]); + } + + // All nodes must have set their "alive" flag to false + for (bool v : a) { + ASSERT_FALSE(v); + } + } +} + +Rooted createFullyConnectedGraph(Manager &mgr, int nElem, + bool alive[]) +{ + std::vector> nodes; + + // Create the nodes + for (int i = 0; i < nElem; i++) { + nodes.push_back(Rooted{new TestManaged{mgr, alive[i]}}); + } + + // Add all connections + for (int i = 0; i < nElem; i++) { + for (int j = 0; j < nElem; j++) { + nodes[i]->addRef(nodes[j]); + } + } + + return nodes[0]; +} + +TEST(Manager, fullyConnectedGraph) +{ + constexpr int nElem = 64; + std::array a; + + Manager mgr(1); + { + Rooted n = createFullyConnectedGraph(mgr, nElem, &a[0]); + for (bool v : a) { + ASSERT_TRUE(v); + } + } + + for (bool v : a) { + ASSERT_FALSE(v); + } +} + +class HidingTestManaged : public TestManaged { +private: + Rooted hidden; + +public: + HidingTestManaged(Manager &mgr, bool &alive) : TestManaged(mgr, alive){}; + + void setHiddenRef(Handle t) { hidden = t; } +}; + +TEST(Manager, hiddenRootedGraph) +{ + constexpr int nElem = 16; + std::array a; + bool b; + Manager mgr(1); + + { + Rooted n{new HidingTestManaged{mgr, b}}; + n->setHiddenRef(createFullyConnectedGraph(mgr, nElem, &a[0])); + + ASSERT_TRUE(b); + for (bool v : a) { + ASSERT_TRUE(v); + } + } + + ASSERT_FALSE(b); + for (bool v : a) { + ASSERT_FALSE(v); + } +} +} + diff --git a/test/core/managed/TestManaged.hpp b/test/core/managed/TestManaged.hpp new file mode 100644 index 0000000..ed51c3b --- /dev/null +++ b/test/core/managed/TestManaged.hpp @@ -0,0 +1,62 @@ +/* + 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 . +*/ + +#ifndef _TEST_MANAGED_H_ +#define _TEST_MANAGED_H_ + +#include + +namespace ousia { + +class TestManaged : public Managed { +private: + bool &alive; + + std::vector> refs; + +public: + TestManaged(Manager &mgr, bool &alive) : Managed(mgr), alive(alive) + { + //std::cout << "create TestManaged @" << this << std::endl; + alive = true; + } + + ~TestManaged() override + { + //std::cout << "delete TestManaged @" << this << std::endl; + alive = false; + } + + void addRef(Handle h) { refs.push_back(acquire(h)); } + + void deleteRef(Handle h) + { + for (auto it = refs.begin(); it != refs.end();) { + if (*it == h) { + it = refs.erase(it); + } else { + it++; + } + } + } +}; + +} + +#endif /* _TEST_MANAGED_H_ */ + -- cgit v1.2.3