diff options
Diffstat (limited to 'src/core')
| -rw-r--r-- | src/core/CSS.hpp | 2 | ||||
| -rw-r--r-- | src/core/ManagedContainers.hpp | 384 | ||||
| -rw-r--r-- | src/core/Node.hpp | 43 | ||||
| -rw-r--r-- | src/core/managed/Managed.cpp | 55 | ||||
| -rw-r--r-- | src/core/managed/Managed.hpp (renamed from src/core/Managed.hpp) | 288 | ||||
| -rw-r--r-- | src/core/managed/ManagedContainer.hpp | 591 | ||||
| -rw-r--r-- | src/core/managed/ManagedType.cpp | 52 | ||||
| -rw-r--r-- | src/core/managed/ManagedType.hpp | 119 | ||||
| -rw-r--r-- | src/core/managed/Manager.cpp (renamed from src/core/Managed.cpp) | 160 | ||||
| -rw-r--r-- | src/core/managed/Manager.hpp | 306 | ||||
| -rw-r--r-- | src/core/model/Domain.hpp | 2 | ||||
| -rw-r--r-- | src/core/model/Typesystem.hpp | 3 |
12 files changed, 1284 insertions, 721 deletions
diff --git a/src/core/CSS.hpp b/src/core/CSS.hpp index a54d956..06ddfc8 100644 --- a/src/core/CSS.hpp +++ b/src/core/CSS.hpp @@ -24,8 +24,8 @@ #include <tuple> #include <core/common/Variant.hpp> +#include <core/managed/Managed.hpp> -#include "Managed.hpp" #include "Node.hpp" namespace ousia { 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 <http://www.gnu.org/licenses/>. -*/ - -#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<T> - */ -template <class T, class Collection> -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<Managed> 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<Managed> 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<T> - */ -template <class T, class Collection> -class ManagedGenericList : public ManagedContainer<T, Collection> { -private: - using Base = ManagedContainer<T, Collection>; - -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 <class InputIterator> - ManagedGenericList(Handle<Managed> owner, InputIterator first, - InputIterator last) - : ManagedContainer<T, Collection>(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 <class InputCollection> - ManagedGenericList(Handle<Managed> owner, const InputCollection &in) - : ManagedContainer<T, Collection>(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<T> h) - { - value_type v = Base::owner->acquire(h); - addElement(v); - return Base::c.insert(position, v); - } - - template <class InputIterator> - 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<T> h) - { - for (iterator it = Base::begin(); it != Base::end(); it++) { - if (*it == h) { - return it; - } - } - return Base::end(); - } - - const_iterator find(const Handle<T> h) const - { - for (const_iterator it = Base::cbegin(); it != Base::cend(); it++) { - if (*it == h) { - return it; - } - } - return Base::cend(); - } - - void push_back(Handle<T> 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 K, class T, class Collection> -class ManagedGenericMap : public ManagedContainer<T, Collection> { -private: - using Base = ManagedContainer<T, Collection>; - -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<K, Handle<T>> 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 <class InputIterator> - ManagedGenericMap(Handle<Managed> owner, InputIterator first, - InputIterator last) - : ManagedContainer<T, Collection>(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 <class InputCollection> - ManagedGenericMap(Handle<Managed> owner, const InputCollection &in) - : ManagedContainer<T, Collection>(owner) - { - for (const auto &e : in) { - insert(*in); - } - } - - std::pair<iterator, bool> insert(std::pair<K, Handle<T>> val) - { - value_type v = acquirePair(val); - this->addElement(v); - return Base::c.insert(v); - } - - iterator insert(const_iterator position, std::pair<K, Handle<T>> val) - { - value_type v = acquirePair(val); - this->addElement(v); - return Base::c.insert(position, v); - } - - template <class InputIterator> - 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 T> -class ManagedVector : public ManagedGenericList<T, std::vector<Owned<T>>> { -public: - using ManagedGenericList<T, std::vector<Owned<T>>>::ManagedGenericList; -}; - -/** - * Special type of ManagedGenericMap based on an STL map. - */ -template <class K, class T> -class ManagedMap : public ManagedGenericMap<K, T, std::map<K, Owned<T>>> { -public: - using ManagedGenericMap<K, T, std::map<K, Owned<T>>>::ManagedGenericMap; -}; -} - -#endif /* _OUSIA_MANAGED_CONTAINERS_H_ */ - diff --git a/src/core/Node.hpp b/src/core/Node.hpp index e0d14a8..4bc95be 100644 --- a/src/core/Node.hpp +++ b/src/core/Node.hpp @@ -25,13 +25,11 @@ #include <vector> #include <unordered_set> -#include "Managed.hpp" -#include "ManagedContainers.hpp" +#include <core/managed/Managed.hpp> +#include <core/managed/ManagedContainer.hpp> namespace ousia { -// TODO: Let Manager handle associated data - /* Forward declarations */ class Node; class Event; @@ -514,33 +512,30 @@ public: bool triggerEvent(Event &event, bool fromChild = false); }; -template <class T, class Collection> -class NodeGenericList : public ManagedGenericList<T, Collection> { -protected: - // TODO: Override addElement, deleteElement once this is necessary -public: - using ManagedGenericList<T, Collection>::ManagedGenericList; -}; +// TODO: Use a different listener here for updating name maps -template <class K, class T, class Collection> -class NodeGenericMap : public ManagedGenericMap<K, T, Collection> { -protected: - // TODO: Override addElement, deleteElement once this is necessary +template <class T, class Listener = DefaultListener<Handle<T>>> +class NodeVector + : public ManagedGenericList<T, std::vector<Handle<T>>, + ListAccessor<Handle<T>>, Listener> { public: - using ManagedGenericMap<K, T, std::vector<Owned<T>>>::ManagedGenericMap; + using Base = ManagedGenericList<T, std::vector<Handle<T>>, + ListAccessor<Handle<T>>, Listener>; + using Base::ManagedGenericList; }; -template <class T> -class NodeVector : public NodeGenericList<T, std::vector<Owned<T>>> { +template <class K, class T, + class Listener = DefaultListener<std::pair<K, Handle<T>>>> +class NodeMap + : public ManagedGenericMap<K, T, std::map<K, Handle<T>>, + MapAccessor<std::pair<K, Handle<T>>>, Listener> { public: - using NodeGenericList<T, std::vector<Owned<T>>>::NodeGenericList; + using Base = + ManagedGenericMap<K, T, std::map<K, Handle<T>>, + MapAccessor<std::pair<K, Handle<T>>>, Listener>; + using Base::ManagedGenericMap; }; -template <class K, class T> -class NodeMap : public NodeGenericMap<K, T, std::map<K, Owned<T>>> { -public: - using NodeGenericMap<K, T, std::map<K, Owned<T>>>::NodeGenericMap; -}; } diff --git a/src/core/managed/Managed.cpp b/src/core/managed/Managed.cpp new file mode 100644 index 0000000..f55cca5 --- /dev/null +++ b/src/core/managed/Managed.cpp @@ -0,0 +1,55 @@ +/* + 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" +#include "ManagedContainer.hpp" + +namespace ousia { + +/* Class Managed */ + +void Managed::storeData(const std::string &key, Handle<Managed> h) { + mgr.storeData(this, key, h.get()); +} + +bool Managed::hasDataKey(const std::string &key) +{ + return mgr.readData(this, key) != nullptr; +} + +Rooted<Managed> Managed::readData(const std::string &key) { + return mgr.readData(this, key); +} + +std::map<std::string, Rooted<Managed>> Managed::readData() { + auto map = mgr.readData(this); + std::map<std::string, Rooted<Managed>> res; + for (auto e : map) { + res.emplace(e.first, e.second); + } + return res; +} + +bool Managed::deleteData(const std::string &key) { + return mgr.deleteData(this, key); +} + +} diff --git a/src/core/Managed.hpp b/src/core/managed/Managed.hpp index 25fa14b..4818c3d 100644 --- a/src/core/Managed.hpp +++ b/src/core/managed/Managed.hpp @@ -19,19 +19,11 @@ #ifndef _OUSIA_MANAGED_HPP_ #define _OUSIA_MANAGED_HPP_ -#include <iostream> -#include <map> -#include <type_traits> -#include <unordered_map> -#include <unordered_set> -#include <vector> +#include "ManagedType.hpp" +#include "Manager.hpp" namespace ousia { -// TODO: Implement clone, getReferenced and getReferencing - -class Managed; - template <class T> class Handle; @@ -41,237 +33,10 @@ 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); } +template <class T> +class DefaultListener; - /** - * Performs garbage collection. - */ - void sweep(); -}; +// TODO: Implement clone, getReferenced and getReferencing /** * The Managed class represents a garbage collected object. Instances of the @@ -332,24 +97,35 @@ public: return Owned<T>{t, this}; } - template <class T> - std::vector<Owned<T>> acquire(const std::vector<Handle<T>> &vec) - { - std::vector<Owned<T>> res; - for (auto &e : vec) { - res.push_back(acquire(e)); - } - return res; + void storeData(const std::string &key, Handle<Managed> h); + + bool hasDataKey(const std::string &key); + + Rooted<Managed> readData(const std::string &key); + + std::map<std::string, Rooted<Managed>> readData(); + + bool deleteData(const std::string &key); + + /** + * Returns the ManagedType instance registered for instances of the type + * of this Managed instance. + * + * @return a reference to the registered ManagedType for this particular + * Managed class. + */ + const ManagedType& type() const { + return ManagedType::typeOf(typeid(*this)); } - template <class T> - std::vector<Owned<T>> acquire(const std::vector<T *> &vec) - { - std::vector<Owned<T>> res; - for (auto &e : vec) { - res.push_back(acquire(e)); - } - return res; + /** + * Returns true if this Managed instance is of the given ManagedType. + * + * @param true if the ManagedType registered for this particular Managed + * class is + */ + bool isa(const ManagedType &t) const { + return type().isa(t); } }; diff --git a/src/core/managed/ManagedContainer.hpp b/src/core/managed/ManagedContainer.hpp new file mode 100644 index 0000000..071db2c --- /dev/null +++ b/src/core/managed/ManagedContainer.hpp @@ -0,0 +1,591 @@ +/* + 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 ManagedContainer.hpp + * + * Container classes for conviniently storing managed instances. + * + * @author Andreas Stöckel (astoecke@techfak.uni-bielefeld.de) + */ + +#ifndef _OUSIA_MANAGED_CONTAINER_H_ +#define _OUSIA_MANAGED_CONTAINER_H_ + +#include <unordered_map> +#include <unordered_set> +#include <vector> +#include <map> +#include <type_traits> + +#include "Manager.hpp" +#include "Managed.hpp" + +namespace ousia { + +template <class T> +class Handle; + +/** + * Default accessor class for accessing the managed element within a list value + * type. + * + * @tparam ValueType is the list value type that should be accessed. + */ +template <class ValueType> +struct ListAccessor { + Managed *getManaged(const ValueType &val) const { return val.get(); } +}; + +/** + * Default accessor class for accessing the managed element within a map value + * type. + * + * @tparam ValueType is the map value type that should be accessed. + */ +template <class ValueType> +struct MapAccessor { + Managed *getManaged(const ValueType &val) const + { + return val.second.get(); + } +}; + +/** + * Default implementation of a Listener class. With empty functions. + */ +template <class ValueType> +struct DefaultListener { + void addElement(const ValueType &val, Managed *owner) {} + void deleteElement(const ValueType &val, Managed *owner) {} +}; + +/** + * Template class which can be used to collect refrences to a certain type of + * managed objects. 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). + * + * @tparam T is the type of the Managed object that should be managed. + * @tparam Collection is the underlying STL collection and should contain + * pointers of type T as value. + * @tparam Accessor is a type that allows to resolve the STL value type to the + * actual, underlying pointer to T -- this is important to generically support + * maps, where the value type is a pair of key type and the actual value. + * @tparam Listener is an optional type that allows to execute arbitrary code + * whenever data is read or written to the collection. + */ +template <class T, class Collection, class Accessor, class Listener> +class ManagedContainer { +public: + using own_type = ManagedContainer<T, Collection, Accessor, Listener>; + using value_type = typename Collection::value_type; + using reference = typename Collection::reference; + using const_reference = typename Collection::const_reference; + using iterator = typename Collection::iterator; + using const_iterator = typename Collection::const_iterator; + using size_type = typename Collection::size_type; + +private: + /** + * Handle containing a reference to the owner of the collection. + */ + Managed *owner; + + /** + * Accessor used to access the managed instance inside a "reference type". + */ + Accessor accessor; + + /** + * Listener which is notified whenever an element is added to or removed + * from the list. + */ + Listener listener; + + /** + * Calls the "addElement" function of each element and thus initializes + * the references from the owner to the elements. + */ + void initialize() + { + Manager &manager = this->getManager(); + for (const auto &elem : *this) { + addElement(manager, elem); + } + } + + /** + * Calls the "deleteElement" function of each element and thus finalizes + * the references from the owner to the elements. + */ + void finalize() + { + if (owner) { + Manager &manager = this->getManager(); + for (const auto &elem : *this) { + deleteElement(manager, elem); + } + } + } + +protected: + /** + * Underlying STL collection. + */ + Collection c; + + /** + * Function to be called whenever an element is added to the collection. + * This function makes sure that the association from the owner to the added + * element is established. + * + * @param managed is the managed instance that is being added to the + * container. + * @param elem is a reference to the actual element that is being added to + * the underlying container. + */ + void addElement(Manager &manager, const value_type &elem) + { + manager.addRef(accessor.getManaged(elem), owner); + listener.addElement(elem, owner); + } + + /** + * Function to be called whenever an element is removed from the collection. + * This function makes sure that the association from the owner to the added + * element is removed. + * + * @param managed is the managed instance that is being deleted from the + * container. + * @param elem is a reference to the actual element that is being removed + * from the underlying container. + */ + void deleteElement(Manager &manager, const value_type &elem) + { + manager.deleteRef(accessor.getManaged(elem), owner); + listener.deleteElement(elem, owner); + } + +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<Managed> owner) : owner(owner.get()) {}; + + /** + * Copy constructor. Creates a copy of the given container with the same + * owner as the given container. + * + * @param other is the other coontainer that should be copied. + */ + ManagedContainer(const own_type &other) : owner(other.owner), c(other.c) + { + initialize(); + } + + /** + * Copy constructor. Creates a copy of the given container with another + * owner. + * + * @param other is the other container that should be copied. + */ + ManagedContainer(Handle<Managed> owner, const own_type &other) + : owner(owner.get()), c(other.c) + { + initialize(); + } + + /** + * Copy constructor. Creates a copy of the given container and takes over + * ownership. + */ + ManagedContainer(Handle<Managed> owner, const Collection &collection) + : owner(owner.get()), c(collection) + { + initialize(); + } + + /** + * Move constructor. Moves the other instance to this instance. + * + * @param other is the other container that should be moved. + */ + ManagedContainer(own_type &&other) + : owner(other.owner), c(std::move(other.c)) + { + other.owner = nullptr; + } + + /** + * Copy constructor. Creates a copy of the given container with another + * owner. + * + * @param other is the other container that should be moved. + */ + ManagedContainer(Handle<Managed> owner, own_type &&other) + : owner(owner.get()), c(std::move(other.c)) + { + other.finalize(); + other.owner = nullptr; + initialize(); + } + + /** + * Copy constructor. 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 <class InputIterator> + ManagedContainer(Handle<Managed> owner, InputIterator first, + InputIterator last) + : owner(owner.get()) + { + auto it = end(); + for (auto it2 = first; it2 != last; it2++) { + it = insert(it, *it2); + it++; + } + } + + /** + * Destructor of the ManagedContainer class. Calls the "deleteElement" + * function for each element in the container. + */ + ~ManagedContainer() { finalize(); }; + + /** + * Copy assignment operator. + * + * @param other is the collection instance that should be copied. + * @return this instance. + */ + own_type &operator=(const own_type &other) + { + finalize(); + owner = other.owner; + c = other.c; + initialize(); + return *this; + } + + /** + * Move assignment operator. + * + * @param other is the collection instance that should be moved; + * @return this instance. + */ + own_type &operator=(own_type &&other) + { + finalize(); + owner = other.owner; + c = std::move(other.c); + other.owner = nullptr; + return *this; + } + + /** + * Equality operator. + */ + bool operator==(const own_type &other) + { + return (owner == other.owner) && (c == other.c); + } + + /** + * Inequality operator. + */ + bool operator!=(const own_type &other) + { + return (owner != other.owner) || (c != other.c); + } + + /** + * Returns the owner of the ManagedContainer instance. + */ + Managed *getOwner() const { return owner; } + + /** + * Returns the manager instance associated with the owner. + */ + Manager &getManager() const { return owner->getManager(); } + + /* State functions */ + + /** + * Returns the size of the container. + * + * @return the number of elements in the container. + */ + size_type size() const noexcept { return c.size(); } + + /** + * Returns whether the container is empty. + * + * @return true if the container is empty, false otherwise. + */ + 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(); } + + /** + * Removes all elements from the container. + */ + void clear() noexcept + { + for (const_iterator it = cbegin(); it != cend(); it++) { + deleteElement(this->getManager(), *it); + } + c.clear(); + } + + /** + * Generic insert operation. + */ + iterator insert(const_iterator position, value_type val) + { + addElement(this->getManager(), val); + return c.insert(position, val); + } + + /** + * Erases the element at the given position. + * + * @param position is the position at which the element should be removed. + * @return an iterator to the element after the deleted element. + */ + iterator erase(iterator position) + { + deleteElement(this->getManager(), *position); + return c.erase(position); + } + + /** + * Erases a range of elements from the collection. + * + * @param position is the position at which the element should be removed. + * @return an iterator to the element after the deleted element. + */ + iterator erase(iterator first, iterator last) + { + for (const_iterator it = first; it != last; it++) { + this->deleteElement(this->getManager(), *it); + } + return c.erase(first, last); + } +}; + +/** + * 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 T* + */ +template <class T, class Collection, class Accessor, class Listener> +class ManagedGenericList + : public ManagedContainer<T, Collection, Accessor, Listener> { +private: + using Base = ManagedContainer<T, Collection, Accessor, Listener>; + +public: + 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; + + using Base::ManagedContainer; + using Base::insert; + + /* 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 */ + + template <class InputIterator> + 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 value_type &val) + { + for (iterator it = Base::begin(); it != Base::end(); it++) { + if (*it == val) { + return it; + } + } + return Base::end(); + } + + const_iterator find(const value_type &val) const + { + for (const_iterator it = Base::cbegin(); it != Base::cend(); it++) { + if (*it == val) { + return it; + } + } + return Base::cend(); + } + + void push_back(Handle<T> h) + { + this->addElement(this->getManager(), h.get()); + Base::c.push_back(h.get()); + } + + void pop_back() + { + if (!Base::empty()) { + this->deleteElement(this->getManager(), back()); + } + Base::c.pop_back(); + } +}; + +/** + * Special type of ManagedContainer based on an STL map. + */ +template <class K, class T, class Collection, class Accessor, class Listener> +class ManagedGenericMap + : public ManagedContainer<T, Collection, Accessor, Listener> { +private: + using Base = ManagedContainer<T, Collection, Accessor, Listener>; + +public: + 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; + + using Base::ManagedContainer; + using Base::erase; + using Base::insert; + + std::pair<iterator, bool> insert(value_type val) + { + this->addElement(this->getManager(), val); + return Base::c.insert(val); + } + + iterator insert(const_iterator position, value_type val) + { + this->addElement(this->getManager(), val); + return Base::c.insert(position, val); + } + + template <class InputIterator> + void insert(InputIterator first, InputIterator last) + { + for (auto it = first; it != last; it++) { + insert(*it); + } + } + + size_t erase(const key_type &k) + { + iterator pos = find(k); + if (pos != Base::end()) { + erase(pos); + return 1; + } + return 0; + } + + 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 T, class Listener = DefaultListener<Handle<T>>> +class ManagedVector + : public ManagedGenericList<T, std::vector<Handle<T>>, + ListAccessor<Handle<T>>, Listener> { +public: + using Base = ManagedGenericList<T, std::vector<Handle<T>>, + ListAccessor<Handle<T>>, Listener>; + using Base::ManagedGenericList; +}; + +/** + * Special type of ManagedGenericMap based on an STL map. + */ +template <class K, class T, + class Listener = DefaultListener<std::pair<K, Handle<T>>>> +class ManagedMap + : public ManagedGenericMap<K, T, std::map<K, Handle<T>>, + MapAccessor<std::pair<K, Handle<T>>>, Listener> { +public: + using Base = + ManagedGenericMap<K, T, std::map<K, Handle<T>>, + MapAccessor<std::pair<K, Handle<T>>>, Listener>; + using Base::ManagedGenericMap; +}; +} + +#endif /* _OUSIA_MANAGED_CONTAINER_H_ */ + diff --git a/src/core/managed/ManagedType.cpp b/src/core/managed/ManagedType.cpp new file mode 100644 index 0000000..ed4c7da --- /dev/null +++ b/src/core/managed/ManagedType.cpp @@ -0,0 +1,52 @@ +/* + 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 "ManagedType.hpp" + +namespace ousia { + +/* Instantiation of static variables */ + +const ManagedType ManagedType::None; + +/* Class ManagedType */ + +const ManagedType &ManagedType::typeOf(const std::type_info &nativeType) +{ + auto it = table().find(std::type_index{nativeType}); + if (it == table().end()) { + return None; + } else { + return *(it->second); + } +} + +bool ManagedType::isa(const ManagedType &other) const +{ + if (&other == this) { + return true; + } + for (auto t : parents) { + if (t->isa(other)) { + return true; + } + } + return false; +} +} + diff --git a/src/core/managed/ManagedType.hpp b/src/core/managed/ManagedType.hpp new file mode 100644 index 0000000..f3ed5fd --- /dev/null +++ b/src/core/managed/ManagedType.hpp @@ -0,0 +1,119 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#ifndef _OUSIA_MANAGED_TYPE_HPP_ +#define _OUSIA_MANAGED_TYPE_HPP_ + +#include <typeinfo> +#include <typeindex> +#include <unordered_map> +#include <unordered_set> + +namespace ousia { + +/** + * The ManagedType is used to register type information that can be retrieved + * using the "type" method of the Managed class. + */ +class ManagedType { +private: + /** + * Used internally to store all registered native types and their + * corresponding type information. + */ + static std::unordered_map<std::type_index, ManagedType *>& table() { + static std::unordered_map<std::type_index, ManagedType *> table; + return table; + } + + /** + * Name of the type -- for messages and debug output. + */ + const std::string name; + + /** + * Set containing references to the parent types. + */ + const std::unordered_set<ManagedType *> parents; + +public: + /** + * ManagedType of no particular type. + */ + static const ManagedType None; + + /** + * Returns the ManagedType for the given type_info structure. + */ + static const ManagedType &typeOf(const std::type_info &nativeType); + + /** + * Default constructor. Creates a ManagedType instance with name "unknown" + * and no parents. + */ + ManagedType() : name("unknown") {} + + /** + * Creates a new ManagedType instance and registers it in the global type + * table. + * + * @param name is the name of the type. + * @param nativeType is the underlying C++ class the type should be attached + * to. + */ + ManagedType(std::string name, const std::type_info &nativeType) + : name(std::move(name)) + { + table().emplace(std::make_pair(std::type_index{nativeType}, this)); + } + + /** + * Creates a new ManagedType instance and registers it in the global type + * table. + * + * @param name is the name of the type. + * @param nativeType is the underlying C++ class the type should be attached + * to. + * @param parents is a list of parent types. + */ + ManagedType(std::string name, const std::type_info &nativeType, + std::unordered_set<ManagedType *> parents) + : name(std::move(name)), parents(parents) + { + table().emplace(std::make_pair(std::type_index{nativeType}, this)); + } + + /** + * Returns the name of this type. + */ + std::string getName() const { return name; } + + /** + * Returns true if this ManagedType instance is the given type or has the + *given + * type as one of its parents. + * + * @param other is the other type for which the relation to this type + * should be checked. + */ + bool isa(const ManagedType &other) const; +}; +} + +#endif /* _OUSIA_MANAGED_TYPE_HPP_ */ + diff --git a/src/core/Managed.cpp b/src/core/managed/Manager.cpp index f3a68a3..b81d89f 100644 --- a/src/core/Managed.cpp +++ b/src/core/managed/Manager.cpp @@ -17,9 +17,9 @@ */ #include <cassert> -#include <queue> #include "Managed.hpp" +#include "Manager.hpp" namespace ousia { @@ -50,49 +50,14 @@ public: ~ScopedIncrement() { i--; } }; -/* Class ObjectDescriptor */ +/* Class Manager::ObjectDescriptor */ -int ObjectDescriptor::refInCount() const +bool Manager::ObjectDescriptor::hasInRef() 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; + return rootRefCount > 0 || !refIn.empty(); } -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 +77,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 +118,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 +129,9 @@ Manager::~Manager() } } -ObjectDescriptor *Manager::getDescriptor(Managed *o) +/* Class Manager: Garbage collection */ + +Manager::ObjectDescriptor *Manager::getDescriptor(Managed *o) { if (o) { auto it = objects.find(o); @@ -181,6 +149,11 @@ void Manager::manage(Managed *o) void Manager::addRef(Managed *tar, Managed *src) { + // Make sure the source and target manager are the same + if (src) { + assert(&tar->getManager() == &src->getManager()); + } + // Fetch the Managed descriptors for the two objects ObjectDescriptor *dTar = getDescriptor(tar); ObjectDescriptor *dSrc = getDescriptor(src); @@ -212,13 +185,14 @@ 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 it has no root reference, add it to the "marked" set which is - // subject to tracing garbage collection - if (dTar->refInCount() == 0) { + // 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 + // Insert the Managed into the list of objects to be inspected by + // garbage // collection marked.insert(tar); } @@ -239,15 +213,17 @@ void Manager::deleteObject(Managed *o, ObjectDescriptor *descr) } // 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. + // 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 the data store entry + store.erase(o); + // Remove all output references of this Managed while (!descr->refOut.empty()) { deleteRef(descr->refOut.begin()->first, o, true); @@ -292,7 +268,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 +310,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; @@ -361,4 +339,80 @@ void Manager::sweep() purgeDeleted(); } } + +/* Class Manager: Attached data */ + +void Manager::storeData(Managed *ref, const std::string &key, Managed *data) +{ + // Add the new reference from the reference object to the data object + addRef(data, ref); + + // Make sure a data map for the given reference object exists + auto &map = store.emplace(ref, std::map<std::string, Managed *>{}).first->second; + + // Insert the given data for the key, decrement the references if + auto it = map.find(key); + if (it == map.end()) { + map.insert(it, std::make_pair(key, data)); + } else { + // Do nothing if the same data is stored + if (it->second == data) { + return; + } + + // Delete the reference from "ref" to the previously stored element. + deleteRef(it->second, ref); + + // Insert a new reference and add the element to the map + map.insert(map.erase(it), std::make_pair(key, data)); + } +} + +Managed *Manager::readData(Managed *ref, const std::string &key) const +{ + // Try to find the reference element in the store + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + // Try to find the key in the map for the element + auto &map = storeIt->second; + auto mapIt = map.find(key); + if (mapIt != map.end()) { + return mapIt->second; + } + } + return nullptr; +} + +std::map<std::string, Managed *> Manager::readData(Managed *ref) const +{ + // Try to find the map for the given reference element and return it + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + return storeIt->second; + } + return std::map<std::string, Managed *>{}; +} + +bool Manager::deleteData(Managed *ref, const std::string &key) +{ + // Find the reference element in the store + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + // Delete the key from the data map + auto &map = storeIt->second; + auto mapIt = map.find(key); + if (mapIt != map.end()) { + // Delete the reference from "ref" to the previously stored element + deleteRef(mapIt->second, ref); + + // Remove the element from the list + map.erase(mapIt); + + return true; + } + } + return false; } + +} + diff --git a/src/core/managed/Manager.hpp b/src/core/managed/Manager.hpp new file mode 100644 index 0000000..ae0d130 --- /dev/null +++ b/src/core/managed/Manager.hpp @@ -0,0 +1,306 @@ +/* + 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 <cstdint> +#include <map> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <vector> +#include <queue> + +namespace ousia { + +// Forward declaration +class Managed; + +/** + * The Manager class implements tracing garbage collection. Garbage Collection + * is implemented as a simple directed reference graph with connected component + * detection. Garbage collection is performed whenever the number of objects + * marked as "probably unreachable" surpasses a certain threshold. + */ +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; + + /** + * 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; + + /** + * Map storing the data attached to managed objects. + */ + std::unordered_map<Managed *, std::map<std::string, Managed *>> store; + + /** + * Map for storing the tagged memory regions. + */ + std::map<uintptr_t, std::pair<uintptr_t, void*>> tags; + + /** + * 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 as long as other Managed objects + * still hold references to it. + * + * @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(); + + /** + * Registers some arbitrary data (in form of a Managed object) for the + * given reference Managed object under a certain (string) key. Overrides + * references to existing data for that key. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key under which the data should be stored. + * @param data is a reference to Managed object containing the data that + * should be stored. + */ + void storeData(Managed *ref, const std::string &key, Managed *data); + + /** + * Returns the arbitrary data stored for the given reference managed object. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key for which the data should be retrieved. + * @return a reference to the associated data with the given key. + */ + Managed *readData(Managed *ref, const std::string &key) const; + + /** + * Returns a const reference to a map containing all keys and the associated + * data objects. + * + * @param ref is the Managed object for which the data should be stored. + * @return a reference to the internal map from keys to managed objects. + */ + std::map<std::string, Managed *> readData(Managed *ref) const; + + /** + * Deletes the data stored for the given object with the given key. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key for which the data should be retrieved. + * @return true if data for this key was deleted, false otherwise. + */ + bool deleteData(Managed *ref, const std::string &key); +}; +} + +#endif /* _OUSIA_MANAGER_HPP_ */ + diff --git a/src/core/model/Domain.hpp b/src/core/model/Domain.hpp index c163254..535330c 100644 --- a/src/core/model/Domain.hpp +++ b/src/core/model/Domain.hpp @@ -82,7 +82,7 @@ #ifndef _OUSIA_MODEL_DOMAIN_HPP_ #define _OUSIA_MODEL_DOMAIN_HPP_ -#include <core/ManagedContainers.hpp> +#include <core/managed/ManagedContainer.hpp> #include <core/Node.hpp> #include "Typesystem.hpp" diff --git a/src/core/model/Typesystem.hpp b/src/core/model/Typesystem.hpp index 77a862b..347adb8 100644 --- a/src/core/model/Typesystem.hpp +++ b/src/core/model/Typesystem.hpp @@ -30,7 +30,6 @@ #include <map> #include <vector> -#include <core/ManagedContainers.hpp> #include <core/Node.hpp> #include <core/common/Exceptions.hpp> #include <core/common/Logger.hpp> @@ -361,7 +360,7 @@ public: class Typesystem : public Node { private: - ManagedVector<Type> types; + NodeVector<Type> types; public: Typesystem(Manager &mgr, std::string name, Handle<Node> parent = nullptr) |