diff options
Diffstat (limited to 'src/core/managed/Manager.hpp')
| -rw-r--r-- | src/core/managed/Manager.hpp | 250 |
1 files changed, 250 insertions, 0 deletions
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_ */ + |