From 467d8d52ffda8b5d520ee0eb1e42125bdb533ff4 Mon Sep 17 00:00:00 2001 From: Andreas Stöckel Date: Sat, 13 Dec 2014 12:33:07 +0100 Subject: started to refactor Managed package --- src/core/managed/Manager.cpp | 333 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 333 insertions(+) create mode 100644 src/core/managed/Manager.cpp (limited to 'src/core/managed/Manager.cpp') diff --git a/src/core/managed/Manager.cpp b/src/core/managed/Manager.cpp new file mode 100644 index 0000000..7b562a8 --- /dev/null +++ b/src/core/managed/Manager.cpp @@ -0,0 +1,333 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include "Managed.hpp" +#include "Manager.hpp" + +namespace ousia { + +/* Private Class ScopedIncrement */ + +/** + * The ScopedIncrement class is used by the Manager to safely increment a + * variable when a scope is entered and to decrement it when the scope is left. + */ +class ScopedIncrement { +private: + /** + * Reference to the variable that should be incremented. + */ + int &i; + +public: + /** + * Constructor of ScopedIncrement. Increments the given variable. + * + * @param i is the variable that should be incremented. + */ + ScopedIncrement(int &i) : i(i) { i++; } + + /** + * Destructor of ScopedIncrement. Decrements the referenced variable. + */ + ~ScopedIncrement() { i--; } +}; + +/* Class ObjectDescriptor */ + +bool Manager::ObjectDescriptor::hasInRef() const +{ + return rootRefCount > 0 || !refIn.empty(); +} + +void Manager::ObjectDescriptor::incrDegree(RefDir dir, Managed *o) +{ + // If the given Managed is null it refers to an input rooted reference + if (o == nullptr) { + rootRefCount++; + return; + } + + // Fetch a reference to either the input or the output reference map + auto &m = dir == RefDir::IN ? refIn : refOut; + + // Insert a new entry or increment the corresponding reference counter + auto it = m.find(o); + if (it == m.end()) { + m.emplace(std::make_pair(o, 1)); + } else { + it->second++; + } +} + +bool Manager::ObjectDescriptor::decrDegree(RefDir dir, Managed *o, bool all) +{ + // If the given Managed is null it refers to an input rooted reference + if (o == nullptr) { + if (rootRefCount > 0) { + if (all) { + rootRefCount = 0; + } else { + rootRefCount--; + } + return true; + } + return false; + } + + // Fetch a reference to either the input or the output reference map + auto &m = dir == RefDir::IN ? refIn : refOut; + + // Decrement corresponding reference counter, delete the entry if the + // reference counter reaches zero + auto it = m.find(o); + if (it != m.end()) { + it->second--; + if (it->second == 0 || all) { + m.erase(it); + } + return true; + } + return false; +} + +/* Class Manager */ + +Manager::~Manager() +{ + // Perform a final sweep + sweep(); + + // All objects should have been deleted! + assert(objects.empty()); + + // Free all objects managed by the Managed manager (we'll get here if + // assertions + // are disabled) + if (!objects.empty()) { + ScopedIncrement incr{deletionRecursionDepth}; + for (auto &e : objects) { + delete e.first; + } + } +} + +Manager::ObjectDescriptor *Manager::getDescriptor(Managed *o) +{ + if (o) { + auto it = objects.find(o); + if (it != objects.end()) { + return &(it->second); + } + } + return nullptr; +} + +void Manager::manage(Managed *o) +{ + objects.emplace(std::make_pair(o, ObjectDescriptor{})); +} + +void Manager::addRef(Managed *tar, Managed *src) +{ + // Fetch the Managed descriptors for the two objects + ObjectDescriptor *dTar = getDescriptor(tar); + ObjectDescriptor *dSrc = getDescriptor(src); + + // Store the tar <- src reference + assert(dTar); + dTar->incrDegree(RefDir::IN, src); + if (src) { + // Store the src -> tar reference + assert(dSrc); + dSrc->incrDegree(RefDir::OUT, tar); + } else { + // We have just added a root reference, remove the element from the + // list of marked objects + marked.erase(tar); + } +} + +void Manager::deleteRef(Managed *tar, Managed *src, bool all) +{ + // Fetch the Managed descriptors for the two objects + ObjectDescriptor *dTar = getDescriptor(tar); + ObjectDescriptor *dSrc = getDescriptor(src); + + // Decrement the output degree of the source Managed first + if (dSrc) { + dSrc->decrDegree(RefDir::OUT, tar, all); + } + + // Decrement the input degree of the input Managed + if (dTar && dTar->decrDegree(RefDir::IN, src, all)) { + // If the Managed has a zero in degree, it can be safely deleted, + // otherwise + // if it has no root reference, add it to the "marked" set which is + // subject to tracing garbage collection + if (!dTar->hasInRef()) { + deleteObject(tar, dTar); + } else if (dTar->rootRefCount == 0) { + // Insert the Managed into the list of objects to be inspected by + // garbage + // collection + marked.insert(tar); + } + } + + // Call the tracing garbage collector if the marked size is larger than the + // actual value + if (marked.size() >= threshold) { + sweep(); + } +} + +void Manager::deleteObject(Managed *o, ObjectDescriptor *descr) +{ + // Abort if the Managed already is on the "deleted" list + if (deleted.find(o) != deleted.end()) { + return; + } + + // Increment the recursion depth counter. The "deleteRef" function called + // below + // may descend further into this function and the actual deletion should be + // done in a single step. + { + ScopedIncrement incr{deletionRecursionDepth}; + + // Add the Managed to the "deleted" set + deleted.insert(o); + + // Remove all output references of this Managed + while (!descr->refOut.empty()) { + deleteRef(descr->refOut.begin()->first, o, true); + } + + // Remove the Managed from the "marked" set + marked.erase(o); + } + + purgeDeleted(); +} + +void Manager::purgeDeleted() +{ + // Perform the actual deletion if the recursion level is zero + if (deletionRecursionDepth == 0 && !deleted.empty()) { + // Increment the recursion depth so this function does not get called + // again while deleting objects + ScopedIncrement incr{deletionRecursionDepth}; + + // Deleting objects might add new objects to the deleted list, thus the + // iterator would get invalid and we have to use this awkward + // construction + while (!deleted.empty()) { + auto it = deleted.begin(); + Managed *o = *it; + deleted.erase(it); + marked.erase(o); + objects.erase(o); + delete o; + } + } +} + +void Manager::sweep() +{ + // Only execute sweep on the highest recursion level + if (deletionRecursionDepth > 0) { + return; + } + + // Set containing objects which are reachable from a rooted Managed + std::unordered_set reachable; + + // Deletion of objects may cause other objects to be added to the "marked" + // list + // so we repeat this process until objects are no longer deleted + while (!marked.empty()) { + // Repeat until all objects in the "marked" list have been visited + while (!marked.empty()) { + // Increment the deletionRecursionDepth counter to prevent deletion + // of objects while sweep is running + ScopedIncrement incr{deletionRecursionDepth}; + + // Fetch the next Managed in the "marked" list and remove it + Managed *curManaged = *(marked.begin()); + + // Perform a breadth-first search starting from the current Managed + bool isReachable = false; + std::unordered_set visited{{curManaged}}; + std::queue queue{{curManaged}}; + while (!queue.empty() && !isReachable) { + // Pop the next element from the queue, remove the element from + // the marked list as we obviously have evaluated it + curManaged = queue.front(); + queue.pop(); + marked.erase(curManaged); + + // Fetch the Managed descriptor + ObjectDescriptor *descr = getDescriptor(curManaged); + if (!descr) { + continue; + } + + // If this Managed is rooted, the complete visited subgraph is + // rooted + if (descr->rootRefCount > 0) { + isReachable = true; + break; + } + + // Iterate over all objects leading to the current one + for (auto &src : descr->refIn) { + Managed *srcManaged = src.first; + + // Abort if the Managed already in the reachable list, + // otherwise add the Managed to the queue if it was not + // visited + if (reachable.find(srcManaged) != reachable.end()) { + isReachable = true; + break; + } else if (visited.find(srcManaged) == visited.end()) { + visited.insert(srcManaged); + queue.push(srcManaged); + } + } + } + + // Insert the objects into the list of to be deleted objects or + // reachable objects depending on the "isReachable" flag + if (isReachable) { + for (auto o : visited) { + reachable.insert(o); + } + } else { + for (auto o : visited) { + deleteObject(o, getDescriptor(o)); + } + } + } + + // Now purge all objects marked for deletion + purgeDeleted(); + } +} +} + -- cgit v1.2.3