diff options
| -rw-r--r-- | CMakeLists.txt | 161 | ||||
| -rw-r--r-- | src/core/managed/Managed.cpp | 27 | ||||
| -rw-r--r-- | src/core/managed/Managed.hpp (renamed from src/core/Managed.hpp) | 243 | ||||
| -rw-r--r-- | src/core/managed/ManagedContainer.cpp | 24 | ||||
| -rw-r--r-- | src/core/managed/ManagedContainer.hpp (renamed from src/core/ManagedContainers.hpp) | 13 | ||||
| -rw-r--r-- | src/core/managed/Manager.cpp (renamed from src/core/Managed.cpp) | 67 | ||||
| -rw-r--r-- | src/core/managed/Manager.hpp | 250 | ||||
| -rw-r--r-- | test/core/managed/ManagedContainerTest.cpp (renamed from test/core/ManagedContainersTest.cpp) | 4 | ||||
| -rw-r--r-- | test/core/managed/ManagedTest.cpp | 22 | ||||
| -rw-r--r-- | test/core/managed/ManagerTest.cpp (renamed from test/core/ManagedTest.cpp) | 139 | ||||
| -rw-r--r-- | test/core/managed/TestManaged.hpp (renamed from test/core/TestManaged.hpp) | 2 |
11 files changed, 526 insertions, 426 deletions
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/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 <http://www.gnu.org/licenses/>. +*/ + +#include <cassert> +#include <queue> + +#include "Managed.hpp" + +namespace ousia { + + +} diff --git a/src/core/Managed.hpp b/src/core/managed/Managed.hpp index 25fa14b..04c2f84 100644 --- a/src/core/Managed.hpp +++ b/src/core/managed/Managed.hpp @@ -19,19 +19,10 @@ #ifndef _OUSIA_MANAGED_HPP_ #define _OUSIA_MANAGED_HPP_ -#include <iostream> -#include <map> -#include <type_traits> -#include <unordered_map> -#include <unordered_set> -#include <vector> +#include "Manager.hpp" namespace ousia { -// TODO: Implement clone, getReferenced and getReferencing - -class Managed; - template <class T> class Handle; @@ -41,237 +32,7 @@ class Rooted; template <class T> class Owned; -/** - * Enum used to specify the direction of a object reference (inbound or - * outbound). - */ -enum class RefDir { IN, OUT }; - -/** - * The ObjectDescriptor struct is used by the Manager for reference counting and - * garbage collection. It describes the reference multigraph with adjacency - * lists. Each ObjectDescriptor instance represents a single managed object and - * its assocition to and from other managed objects (nodes in the graph). - */ -struct ObjectDescriptor { -public: - /** - * Contains the number of references to rooted handles. A managed objects - * whith at least one rooted reference is considered reachable. - */ - int rootRefCount; - - /** - * Map containing all references pointing at this managed object. The - * map key describes the object which points at this object, the map - * value contains the reference count from this object. - */ - std::map<Managed *, int> refIn; - - /** - * Map containing all references pointing from this managed object to - * other managed objects. The map key describes the target object and - * the map value the reference count. - */ - std::map<Managed *, int> refOut; - - /** - * Default constructor of the ObjectDescriptor class. - */ - ObjectDescriptor() : rootRefCount(0){}; - - /** - * Returns the total input degree of this managed object. The root - * references are also counted as incomming references and thus added to - * the result. - * - * @return the input degree of this node, including the root references. - */ - int refInCount() const; - - /** - * Returns the total output degree of this node. - * - * @return the output degree of this node. - */ - int refOutCount() const; - - /** - * Returns the input degree for the given managed object. - * - * @param o is the node for which the input degree should be returned, - * nullptr if the number of root references is returned. - * @return the input degree of the node or the rootRefCount if nullptr - * is given as node. If the node is not found, zero is returned. - */ - int refInCount(Managed *o) const; - - /** - * Returns the output degree for the given node. - * - * @param o is the node for which the output degree should be returned. - * @return the output degree of the node. If the node is not found, zero - * is returned. - */ - int refOutCount(Managed *o) const; - - /** - * Increments the input or output degree for the represented managed - * object. - * - * @param dir describes the direction of the association. A value of - * "in", increments the input degree, otherwise increments the output - * degree. - * @param o is the managed object for which the input or output degree - * should be incremented. If the given object is null, the rootRefCount - * is incremented, independent of the dir parameter. - */ - void incrDegree(RefDir dir, Managed *o); - - /** - * Decrements the input or output degree for the given managed object. - * - * @param dir describes the direction of the association. A value of - * "in", increments the input degree, otherwise increments the output - * degree. - * @param o is the managed object for which the input or output degree - * should be incremented. If the given object is null, the rootRefCount - * is incremented, independent of the dir parameter. - * @param all specifies whether the degree of the reference to this - * object should be set to zero, no matter what the actual degree is. - * This parameter is used when the given object is deleted and all - * references to it should be purged, no matter what. - * @return true if the degree was sucessfully decremented. - */ - bool decrDegree(RefDir dir, Managed *o, bool all = false); -}; - -class Manager { -private: - /** - * Default sweep threshold. If the number of managed objects marked for - * sweeping reaches this threshold a garbage collection sweep is performed. - */ - static constexpr size_t SWEEP_THRESHOLD = 128; - -protected: - /** - * Threshold that defines the minimum number of entries in the "marked" - * set until "sweep" is called. - */ - const size_t threshold; - - /** - * Map used to store the descriptors for all managed objects. Every object - * that has at least one root, in or out reference has an entry in this map. - */ - std::unordered_map<Managed *, ObjectDescriptor> objects; - - /** - * Set containing the objects marked for sweeping. - */ - std::unordered_set<Managed *> marked; - - /** - * Set containing objects marked for deletion. - */ - std::unordered_set<Managed *> deleted; - - /** - * Recursion depth while performing deletion. This variable is needed - * because the deletion of an object may cause further objects to be - * deleted. Yet the actual deletion should only be performed at the - * uppermost recursion level. - */ - int deletionRecursionDepth = 0; - - /** - * Returns the object ObjectDescriptor for the given object from the objects - * map. - */ - ObjectDescriptor *getDescriptor(Managed *o); - - /** - * Purges the objects in the "deleted" set. - */ - void purgeDeleted(); - - /** - * Function used internally to delete a object and clean up all references - * in the object manager still pointing at it. - * - * @param o is the object that should be deleted. - * @param descr is a reference to the ObjectDescriptor of the given object. - */ - void deleteObject(Managed *o, ObjectDescriptor *descr); - - /** - * Internal version of the deleteRef function with an additional "all" - * parameter. Removes a reference to the given target object from the source - * object. - * - * @param tar is the target object for which the reference from the given - * source object should be removed. - * @param src is the source object from which the target object was - * referenced or nullptr if the target object is referenced from the local - * scope. - * @param all specifies whether all (src, tar) references should be deleted, - * independent of the actual cardinality. This is set to true, when the - * given object is deleted and all references to it should be purged, no - * matter what. - */ - void deleteRef(Managed *tar, Managed *src, bool all); - -public: - Manager() : threshold(SWEEP_THRESHOLD) {} - - Manager(size_t threshold) : threshold(threshold) {} - - /** - * Deletes all objects managed by this class. - */ - ~Manager(); - - /** - * Registers an object for being managed by the Manager. The Manager now has - * the sole responsibility for freeing the managed object. Under no - * circumstances free the object manually, this will result in double frees. - * - * @param o is the object which is registered for being used with the - * Manager. - */ - void manage(Managed *o); - - /** - * Stores a reference to the given target object from the given source - * object. If the source pointer is set to nullptr, this means that the - * target object is rooted (semantic: it is reachable from the current - * scope) and should not be collected. - * - * @param tar is the target object to which the reference from src should be - * stored. - * @param src is the source object from which the target object is - * referenced or nullptr if the target object is referenced from the local - * scope. - */ - void addRef(Managed *tar, Managed *src); - - /** - * Removes a reference to the given target object from the source object. - * - * @param tar is the target object for which the reference from the given - * source object should be removed. - * @param src is the source object from which the target object was - * referenced or nullptr if the target object is referenced from the local - * scope. - */ - void deleteRef(Managed *tar, Managed *src) { deleteRef(tar, src, false); } - - /** - * Performs garbage collection. - */ - void sweep(); -}; +// TODO: Implement clone, getReferenced and getReferencing /** * The Managed class represents a garbage collected object. Instances of the 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 <http://www.gnu.org/licenses/>. +*/ + +#include "ManagedContainer.hpp" + +namespace ousia { + +} + diff --git a/src/core/ManagedContainers.hpp b/src/core/managed/ManagedContainer.hpp index 9447fff..9ff75d5 100644 --- a/src/core/ManagedContainers.hpp +++ b/src/core/managed/ManagedContainer.hpp @@ -16,8 +16,15 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef _OUSIA_MANAGED_CONTAINERS_H_ -#define _OUSIA_MANAGED_CONTAINERS_H_ +#ifndef _OUSIA_MANAGED_CONTAINER_H_ +#define _OUSIA_MANAGED_CONTAINER_H_ + +#include <unordered_map> +#include <unordered_set> +#include <vector> +#include <iostream> +#include <map> +#include <type_traits> #include "Managed.hpp" @@ -380,5 +387,5 @@ public: }; } -#endif /* _OUSIA_MANAGED_CONTAINERS_H_ */ +#endif /* _OUSIA_MANAGED_CONTAINER_H_ */ diff --git a/src/core/Managed.cpp b/src/core/managed/Manager.cpp index f3a68a3..7b562a8 100644 --- a/src/core/Managed.cpp +++ b/src/core/managed/Manager.cpp @@ -16,10 +16,8 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <cassert> -#include <queue> - #include "Managed.hpp" +#include "Manager.hpp" namespace ousia { @@ -52,47 +50,12 @@ public: /* 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 +bool Manager::ObjectDescriptor::hasInRef() const { - if (o == nullptr) { - return rootRefCount; - } - - const auto it = refIn.find(o); - if (it != refIn.cend()) { - return it->second; - } - return 0; + return rootRefCount > 0 || !refIn.empty(); } -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) +void Manager::ObjectDescriptor::incrDegree(RefDir dir, Managed *o) { // If the given Managed is null it refers to an input rooted reference if (o == nullptr) { @@ -112,7 +75,7 @@ void ObjectDescriptor::incrDegree(RefDir dir, Managed *o) } } -bool ObjectDescriptor::decrDegree(RefDir dir, Managed *o, bool all) +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) { @@ -153,7 +116,8 @@ Manager::~Manager() // All objects should have been deleted! assert(objects.empty()); - // Free all objects managed by the Managed manager (we'll get here if assertions + // Free all objects managed by the Managed manager (we'll get here if + // assertions // are disabled) if (!objects.empty()) { ScopedIncrement incr{deletionRecursionDepth}; @@ -163,7 +127,7 @@ Manager::~Manager() } } -ObjectDescriptor *Manager::getDescriptor(Managed *o) +Manager::ObjectDescriptor *Manager::getDescriptor(Managed *o) { if (o) { auto it = objects.find(o); @@ -212,13 +176,15 @@ void Manager::deleteRef(Managed *tar, Managed *src, bool 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 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) { + if (!dTar->hasInRef()) { deleteObject(tar, dTar); } else if (dTar->rootRefCount == 0) { - // Insert the Managed into the list of objects to be inspected by garbage + // Insert the Managed into the list of objects to be inspected by + // garbage // collection marked.insert(tar); } @@ -292,7 +258,8 @@ void Manager::sweep() // Set containing objects which are reachable from a rooted Managed std::unordered_set<Managed *> reachable; - // Deletion of objects may cause other objects to be added to the "marked" list + // 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 @@ -333,7 +300,8 @@ void Manager::sweep() 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 + // otherwise add the Managed to the queue if it was not + // visited if (reachable.find(srcManaged) != reachable.end()) { isReachable = true; break; @@ -362,3 +330,4 @@ void Manager::sweep() } } } + 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 <http://www.gnu.org/licenses/>. +*/ + +/** + * @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 <cassert> +#include <map> +#include <unordered_map> +#include <unordered_set> +#include <vector> +#include <queue> + +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<Managed *, int> refIn; + + /** + * Map containing all references pointing from this managed object to + * other managed objects. The map key describes the target object and + * the map value the reference count. + */ + std::map<Managed *, int> refOut; + + /** + * Default constructor of the ObjectDescriptor class. + */ + ObjectDescriptor() : rootRefCount(0){}; + + /** + * Returns 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<Managed *, ObjectDescriptor> objects; + + /** + * Set containing the objects marked for sweeping. + */ + std::unordered_set<Managed *> marked; + + /** + * Set containing objects marked for deletion. + */ + std::unordered_set<Managed *> deleted; + + /** + * Recursion depth while performing deletion. This variable is needed + * because the deletion of an object may cause further objects to be + * deleted. Yet the actual deletion should only be performed at the + * uppermost recursion level. + */ + int deletionRecursionDepth = 0; + + /** + * Returns the object ObjectDescriptor for the given object from the objects + * map. + */ + ObjectDescriptor *getDescriptor(Managed *o); + + /** + * Purges the objects in the "deleted" set. + */ + void purgeDeleted(); + + /** + * Function used internally to delete a object and clean up all references + * in the object manager still pointing at it. + * + * @param o is the object that should be deleted. + * @param descr is a reference to the ObjectDescriptor of the given object. + */ + void deleteObject(Managed *o, ObjectDescriptor *descr); + + /** + * Internal version of the deleteRef function with an additional "all" + * parameter. Removes a reference to the given target object from the source + * object. + * + * @param tar is the target object for which the reference from the given + * source object should be removed. + * @param src is the source object from which the target object was + * referenced or nullptr if the target object is referenced from the local + * scope. + * @param all specifies whether all (src, tar) references should be deleted, + * independent of the actual cardinality. This is set to true, when the + * given object is deleted and all references to it should be purged, no + * matter what. + */ + void deleteRef(Managed *tar, Managed *src, bool all); + +public: + Manager() : threshold(SWEEP_THRESHOLD) {} + + Manager(size_t threshold) : threshold(threshold) {} + + /** + * Deletes all objects managed by this class. + */ + ~Manager(); + + /** + * Registers an object for being managed by the Manager. The Manager now has + * the sole responsibility for freeing the managed object. Under no + * circumstances free the object manually, this will result in double frees. + * + * @param o is the object which is registered for being used with the + * Manager. + */ + void manage(Managed *o); + + /** + * Stores a reference to the given target object from the given source + * object. If the source pointer is set to nullptr, this means that the + * target object is rooted (semantic: it is reachable from the current + * scope) and should not be collected. + * + * @param tar is the target object to which the reference from src should be + * stored. + * @param src is the source object from which the target object is + * referenced or nullptr if the target object is referenced from the local + * scope. + */ + void addRef(Managed *tar, Managed *src); + + /** + * Removes a reference to the given target object from the source object. + * + * @param tar is the target object for which the reference from the given + * source object should be removed. + * @param src is the source object from which the target object was + * referenced or nullptr if the target object is referenced from the local + * scope. + */ + void deleteRef(Managed *tar, Managed *src) { deleteRef(tar, src, false); } + + /** + * Performs garbage collection. + */ + void sweep(); +}; +} + +#endif /* _OUSIA_MANAGER_HPP_ */ + diff --git a/test/core/ManagedContainersTest.cpp b/test/core/managed/ManagedContainerTest.cpp index 3abbd4d..db72295 100644 --- a/test/core/ManagedContainersTest.cpp +++ b/test/core/managed/ManagedContainerTest.cpp @@ -20,8 +20,8 @@ #include <gtest/gtest.h> -#include <core/Managed.hpp> -#include <core/ManagedContainers.hpp> +#include <core/managed/Managed.hpp> +#include <core/managed/ManagedContainer.hpp> #include "TestManaged.hpp" 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 <http://www.gnu.org/licenses/>. +*/ + +namespace ousia { + +} + diff --git a/test/core/ManagedTest.cpp b/test/core/managed/ManagerTest.cpp index ab60f04..da42f0a 100644 --- a/test/core/ManagedTest.cpp +++ b/test/core/managed/ManagerTest.cpp @@ -22,7 +22,7 @@ #include <gtest/gtest.h> -#include <core/Managed.hpp> +#include <core/managed/Managed.hpp> #include "TestManaged.hpp" @@ -30,128 +30,171 @@ 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 - ObjectDescriptor nd; + TestObjectDescriptor nd; Managed *n1 = reinterpret_cast<Managed *>(intptr_t{0x10}); Managed *n2 = reinterpret_cast<Managed *>(intptr_t{0x20}); // Input degree - ASSERT_EQ(0, nd.refIn.size()); + ASSERT_EQ(0U, nd.refIn.size()); ASSERT_EQ(0, nd.refInCount(n1)); - nd.incrDegree(RefDir::IN, 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(1, nd.refIn.size()); + ASSERT_EQ(1U, nd.refIn.size()); - nd.incrDegree(RefDir::IN, n1); + 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(1, nd.refIn.size()); + ASSERT_EQ(1U, nd.refIn.size()); - nd.incrDegree(RefDir::IN, n2); + 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(2, nd.refIn.size()); + ASSERT_EQ(2U, nd.refIn.size()); - nd.incrDegree(RefDir::IN, nullptr); + 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(2, nd.refIn.size()); + ASSERT_EQ(2U, nd.refIn.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::IN, n1)); + 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(2, nd.refIn.size()); + ASSERT_EQ(2U, nd.refIn.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::IN, n1)); + 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(1, nd.refIn.size()); + ASSERT_EQ(1U, nd.refIn.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::IN, n2)); + 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(0, nd.refIn.size()); + ASSERT_EQ(0U, nd.refIn.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::IN, nullptr)); + 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(0, nd.refIn.size()); + ASSERT_EQ(0U, nd.refIn.size()); // Output degree - ASSERT_EQ(0, nd.refOut.size()); + ASSERT_EQ(0U, nd.refOut.size()); ASSERT_EQ(0, nd.refOutCount(n1)); - nd.incrDegree(RefDir::OUT, 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(1, nd.refOut.size()); + ASSERT_EQ(1U, nd.refOut.size()); - nd.incrDegree(RefDir::OUT, n1); + 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(1, nd.refOut.size()); + ASSERT_EQ(1U, nd.refOut.size()); - nd.incrDegree(RefDir::OUT, n2); + 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(2, nd.refOut.size()); + ASSERT_EQ(2U, nd.refOut.size()); - nd.incrDegree(RefDir::OUT, nullptr); + 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(2, nd.refOut.size()); + ASSERT_EQ(2U, nd.refOut.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::OUT, n1)); + 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(2, nd.refOut.size()); + ASSERT_EQ(2U, nd.refOut.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::OUT, n1)); + 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(1, nd.refOut.size()); + ASSERT_EQ(1U, nd.refOut.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::OUT, n2)); + 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(0, nd.refOut.size()); + ASSERT_EQ(0U, nd.refOut.size()); - ASSERT_TRUE(nd.decrDegree(RefDir::OUT, nullptr)); + 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(0, nd.refOut.size()); + ASSERT_EQ(0U, nd.refOut.size()); } TEST(ObjectDescriptor, rootRefCount) { - ObjectDescriptor nd; + TestObjectDescriptor nd; ASSERT_EQ(0, nd.rootRefCount); - nd.incrDegree(RefDir::IN, nullptr); + nd.incrDegree(Manager::RefDir::IN, nullptr); ASSERT_EQ(1, nd.rootRefCount); - nd.incrDegree(RefDir::OUT, nullptr); + nd.incrDegree(Manager::RefDir::OUT, nullptr); ASSERT_EQ(2, nd.rootRefCount); ASSERT_EQ(2, nd.refInCount(nullptr)); @@ -159,13 +202,13 @@ TEST(ObjectDescriptor, rootRefCount) ASSERT_EQ(0, nd.refOutCount(nullptr)); ASSERT_EQ(0, nd.refOutCount()); - ASSERT_TRUE(nd.decrDegree(RefDir::OUT, nullptr)); + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::OUT, nullptr)); ASSERT_EQ(1, nd.rootRefCount); - ASSERT_TRUE(nd.decrDegree(RefDir::IN, nullptr)); + ASSERT_TRUE(nd.decrDegree(Manager::RefDir::IN, nullptr)); ASSERT_EQ(0, nd.rootRefCount); - ASSERT_FALSE(nd.decrDegree(RefDir::IN, nullptr)); + ASSERT_FALSE(nd.decrDegree(Manager::RefDir::IN, nullptr)); ASSERT_EQ(0, nd.rootRefCount); } @@ -436,7 +479,7 @@ TEST(Manager, disconnectDoubleRootedSubgraph) } Rooted<TestManaged> createFullyConnectedGraph(Manager &mgr, int nElem, - bool alive[]) + bool alive[]) { std::vector<Rooted<TestManaged>> nodes; @@ -474,18 +517,13 @@ TEST(Manager, fullyConnectedGraph) } class HidingTestManaged : public TestManaged { - private: Rooted<Managed> hidden; public: + HidingTestManaged(Manager &mgr, bool &alive) : TestManaged(mgr, alive){}; - HidingTestManaged(Manager &mgr, bool &alive) : TestManaged(mgr, alive) {}; - - void setHiddenRef(Handle<Managed> t) { - hidden = t; - } - + void setHiddenRef(Handle<Managed> t) { hidden = t; } }; TEST(Manager, hiddenRootedGraph) @@ -510,6 +548,5 @@ TEST(Manager, hiddenRootedGraph) ASSERT_FALSE(v); } } - } diff --git a/test/core/TestManaged.hpp b/test/core/managed/TestManaged.hpp index 3b93e51..ed51c3b 100644 --- a/test/core/TestManaged.hpp +++ b/test/core/managed/TestManaged.hpp @@ -19,7 +19,7 @@ #ifndef _TEST_MANAGED_H_ #define _TEST_MANAGED_H_ -#include <core/Managed.hpp> +#include <core/managed/Managed.hpp> namespace ousia { |