summaryrefslogtreecommitdiff
path: root/src/core/managed
diff options
context:
space:
mode:
Diffstat (limited to 'src/core/managed')
-rw-r--r--src/core/managed/Managed.cpp27
-rw-r--r--src/core/managed/Managed.hpp504
-rw-r--r--src/core/managed/ManagedContainer.cpp24
-rw-r--r--src/core/managed/ManagedContainer.hpp391
-rw-r--r--src/core/managed/Manager.cpp333
-rw-r--r--src/core/managed/Manager.hpp250
6 files changed, 1529 insertions, 0 deletions
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/Managed.hpp b/src/core/managed/Managed.hpp
new file mode 100644
index 0000000..04c2f84
--- /dev/null
+++ b/src/core/managed/Managed.hpp
@@ -0,0 +1,504 @@
+/*
+ Ousía
+ Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef _OUSIA_MANAGED_HPP_
+#define _OUSIA_MANAGED_HPP_
+
+#include "Manager.hpp"
+
+namespace ousia {
+
+template <class T>
+class Handle;
+
+template <class T>
+class Rooted;
+
+template <class T>
+class Owned;
+
+// TODO: Implement clone, getReferenced and getReferencing
+
+/**
+ * The Managed class represents a garbage collected object. Instances of the
+ * Managed class are managed (e.g. freed) by an instance of the Manager class.
+ * Never free instances of this class yourself (even by playing an instance of
+ * this class on the steck). Create any new instance of any managed object with
+ * the makeRooted and makeOwned functions.
+ */
+class Managed {
+protected:
+ /**
+ * mgr is the reference to the managed object manager which owns this
+ * managed object.
+ */
+ Manager &mgr;
+
+public:
+ /**
+ * Constructor of the Managed class. Associates the new instance with the
+ * given Manager, which is now in charge for managing this instance. Never
+ * manually free instances of this class (even by using stack instances).
+ * Always use the Rooted and Owned smart pointer classes when refering to
+ * types derived from Managed.
+ *
+ * @param mgr is the Manager which should take ownership of this instance.
+ */
+ Managed(Manager &mgr) : mgr(mgr) { mgr.manage(this); };
+
+ /**
+ * Virtual destuctor which may be overwritten by child classes.
+ */
+ virtual ~Managed(){};
+
+ /**
+ * Returns a reference ot the manager instance which owns this managed
+ * object.
+ */
+ Manager &getManager() { return mgr; }
+
+ /**
+ * Acquires a reference to the object wraped in the given handle.
+ */
+ template <class T>
+ Owned<T> acquire(const Handle<T> &h)
+ {
+ return Owned<T>{h, this};
+ }
+
+ template <class T>
+ Owned<T> acquire(Handle<T> &&h)
+ {
+ return Owned<T>{h, this};
+ }
+
+ template <class T>
+ Owned<T> acquire(T *t)
+ {
+ 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;
+ }
+
+ 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;
+ }
+};
+
+/**
+ * The Handle class is the base class for handles pointing at managed objects.
+ * It implements methods for comparing handles to each other and to pointers
+ * of the represented managed object type. Furthermore all other handle types
+ * and pointers can be conveniently converted to a Handle instance. However,
+ * the Handle class does not qualify the represented pointer for garbage
+ * collection. Thus the Handle class should only be used as type for input
+ * parameters in methods/functions and at no other ocasion. Use the Rooted or
+ * the Owned class if the represented object should actually be garbage
+ * collected.
+ */
+template <class T>
+class Handle {
+protected:
+ friend class Rooted<T>;
+ friend class Owned<T>;
+
+ /**
+ * Reference to the represented managed object.
+ */
+ T *ptr;
+
+public:
+ /**
+ * Constructor of the base Handle class.
+ *
+ * @param ptr is the pointer to the managed object the Handle should
+ * represent.
+ */
+ Handle(T *ptr) : ptr(ptr) {}
+
+ /**
+ * Copies the given Handle to this Handle instance.
+ *
+ * @param h is the Handle that should be asigned to this instance.
+ */
+ Handle(const Handle<T> &h) : ptr(h.get()) {}
+
+ /**
+ * Copies the given Handle for a managed object of a derived class to this
+ * Handle instance.
+ *
+ * @param h is the Handle that should be asigned to this instance.
+ */
+ template <class T2>
+ Handle(const Handle<T2> &h)
+ : ptr(h.get())
+ {
+ }
+
+ /**
+ * Returns the underlying pointer.
+ */
+ T *get() const { return ptr; }
+
+ /**
+ * Provides access to the underlying managed object.
+ */
+ T *operator->() { return ptr; }
+
+ /**
+ * Provides access to the underlying managed object for immutable handles.
+ */
+ const T *operator->() const { return ptr; }
+
+ /**
+ * Provides access to the underlying managed object.
+ */
+ T &operator*() { return *ptr; }
+
+ /**
+ * Provides access to the underlying managed object for immutable handles.
+ */
+ const T &operator*() const { return *ptr; }
+
+ /**
+ * Comparison operator between base Owned and base Owned.
+ */
+ template <class T2>
+ bool operator==(const Handle<T2> &h) const
+ {
+ return ptr == h.get();
+ }
+
+ /**
+ * Comparison operator between base Owned and pointer.
+ */
+ friend bool operator==(const Handle<T> &h, const Managed *o)
+ {
+ return h.get() == o;
+ }
+
+ /**
+ * Comparison operator between base Owned and pointer.
+ */
+ friend bool operator==(const Managed *o, const Handle<T> &h)
+ {
+ return o == h.get();
+ }
+
+ /**
+ * Returns true if the handle is the null pointer.
+ */
+ bool isNull() const { return ptr == nullptr; }
+
+ /**
+ * Returns true if the handle is the null pointer.
+ */
+ bool operator!() const { return isNull(); }
+
+ /**
+ * Statically casts the handle to a handle of the given type.
+ */
+ template <class T2>
+ Handle<T2> cast()
+ {
+ return Handle<T2>{static_cast<T2 *>(ptr)};
+ }
+};
+
+/**
+ * A Rooted represents a directed, garbage collected pointer at a managed
+ * object. The lifetime of the represented managed object is guaranteed to be at
+ * least as long as the lifetime of the Rooted handle instance.
+ */
+template <class T>
+class Rooted : public Handle<T> {
+private:
+ void addRef()
+ {
+ if (Handle<T>::ptr) {
+ Handle<T>::ptr->getManager().addRef(Handle<T>::ptr, nullptr);
+ }
+ }
+
+ void deleteRef()
+ {
+ if (Handle<T>::ptr) {
+ Handle<T>::ptr->getManager().deleteRef(Handle<T>::ptr, nullptr);
+ }
+ }
+
+public:
+ /**
+ * Creates an empty Owned.
+ */
+ Rooted() : Handle<T>(nullptr){};
+
+ /**
+ * Copies the given Rooted to this Rooted instance. Both handles
+ * are indistinguishable after the operation.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ Rooted(const Rooted<T> &h) : Handle<T>(h.ptr) { addRef(); }
+
+ /**
+ * Move constructor. Moves the given rvalue Rooted to this instance.
+ *
+ * @param h is the Rooted to be moved to this instance.
+ */
+ Rooted(Rooted<T> &&h) : Handle<T>(h.ptr) { h.ptr = nullptr; }
+
+ /**
+ * Constructor of the Rooted class.
+ *
+ * @param ptr is the managed object the Rooted handle should represent.
+ */
+ Rooted(T *ptr) : Handle<T>(ptr) { addRef(); }
+
+ /**
+ * Constructor of the Rooted class.
+ *
+ * @param h is another Rooted whose managed object should be used.
+ */
+ template <class T2>
+ Rooted(const Handle<T2> &h)
+ : Handle<T>(h.get())
+ {
+ addRef();
+ }
+
+ /**
+ * Assignment operator. Assigns the given Owned to this Owned instance.
+ * Both handles are indistinguishable after the operation.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ Rooted<T> &operator=(const Rooted<T> &h)
+ {
+ deleteRef();
+ this->ptr = h.ptr;
+ addRef();
+ return *this;
+ }
+
+ /**
+ * Move assignment operator. Moves the given rvalue Owned into this
+ * instance.
+ *
+ * @param h is the Owned to be moved to this instance.
+ */
+ Rooted<T> &operator=(Rooted<T> &&h)
+ {
+ deleteRef();
+ this->ptr = h.ptr;
+ h.ptr = nullptr;
+ return *this;
+ }
+
+ /**
+ * Assignment operator. Assigns the given Owned to this Owned instance.
+ * Both handles are indistinguishable after the operation.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ template <class T2>
+ Rooted<T> &operator=(const Handle<T2> &h)
+ {
+ deleteRef();
+ this->ptr = h.get();
+ addRef();
+ return *this;
+ }
+
+ /**
+ * Move assignment operator. Moves the given rvalue Owned into this
+ * instance.
+ *
+ * @param h is the Owned to be moved to this instance.
+ */
+ Rooted<T> &operator=(Handle<T> &&h)
+ {
+ deleteRef();
+ this->ptr = h.ptr;
+ h.ptr = nullptr;
+ return *this;
+ }
+
+ /**
+ * Destructor of the Rooted class, deletes all refrences the class is
+ * still holding.
+ */
+ ~Rooted() { deleteRef(); }
+};
+
+/**
+ * The Owned class represents a directed, garbage collected pointer at a managed
+ * instance. The lifetime of the represented managed object is guaranteed to be
+ * at last as long as the lifetime of the Managed instance which owns this
+ * reference.
+ */
+template <class T>
+class Owned : public Handle<T> {
+private:
+ Managed *owner;
+
+ void addRef()
+ {
+ if (Handle<T>::ptr && owner) {
+ owner->getManager().addRef(Handle<T>::ptr, owner);
+ }
+ }
+
+ void deleteRef()
+ {
+ if (Handle<T>::ptr && owner) {
+ owner->getManager().deleteRef(Handle<T>::ptr, owner);
+ }
+ }
+
+public:
+ /**
+ * Creates an empty Owned.
+ */
+ Owned() : Handle<T>(nullptr), owner(nullptr){};
+
+ /**
+ * Copies the given Owned to this Owned instance. Both handles are
+ * indistinguishable after the operation. Note that especially the Owned
+ * owner is copied.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ Owned(const Owned<T> &h) : Handle<T>(h.get()), owner(h.getOwner())
+ {
+ addRef();
+ }
+
+ /**
+ * Copies the given Owned of another derived type to this Owned instance.
+ * Both handles are indistinguishable after the operation (except for the
+ * type). Note that especially the Owned owner is copied.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ template <class T2>
+ Owned(const Owned<T2> &h)
+ : Handle<T>(h.get()), owner(h.getOwner())
+ {
+ addRef();
+ }
+
+ /**
+ * Move constructor. Moves the given rvalue Owned to this instance.
+ *
+ * @param h is the Owned to be moved to this instance.
+ */
+ Owned(Owned<T> &&h) : Handle<T>(h.get()), owner(h.getOwner())
+ {
+ h.ptr = nullptr;
+ }
+
+ /**
+ * Assignment operator. Assigns the given Owned to this Owned instance.
+ * Both handles are indistinguishable after the operation. Note that
+ * especially the Owned owner is copied.
+ *
+ * @param h is the Owned that should be asigned to this instance.
+ */
+ Owned<T> &operator=(const Owned<T> &h)
+ {
+ deleteRef();
+ this->ptr = h.ptr;
+ this->owner = h.getOwner();
+ addRef();
+ return *this;
+ }
+
+ /**
+ * Move assignment operator. Moves the given rvalue Owned into this
+ * instance.
+ *
+ * @param h is the Owned to be moved to this instance.
+ */
+ Owned<T> &operator=(Owned<T> &&h)
+ {
+ deleteRef();
+ this->ptr = h.ptr;
+ this->owner = h.getOwner();
+ h.ptr = nullptr;
+ return *this;
+ }
+
+ /**
+ * Constructor of the Owned class.
+ *
+ * @param ptr is a pointer at the managed object the Owned handle should
+ * represent.
+ * @param owner is the managed object which owns this Owned handle instance.
+ * The managed object pointed to in the handle is guaranteed to live at
+ * least as long as the owner.
+ */
+ Owned(T *ptr, Managed *owner) : Handle<T>(ptr), owner(owner) { addRef(); }
+
+ /**
+ * Constructor of the Owned class.
+ *
+ * @param h is another Owned whose managed object should be used.
+ * @param owner is the managed object which owns this Owned handle instance.
+ * The managed object pointed to in the handle is guaranteed to live at
+ * least as long as the owner.
+ */
+ template <class T2>
+ Owned(const Handle<T2> &h, Managed *owner)
+ : Handle<T>(h.get()), owner(owner)
+ {
+ addRef();
+ }
+
+ /**
+ * Destructor of the Owned class, deletes all refrences the class is still
+ * holding.
+ */
+ ~Owned() { deleteRef(); }
+
+ /**
+ * Returns the reference to the owner of the Owned.
+ *
+ * @return the Owned owner.
+ */
+ Managed *getOwner() const { return owner; }
+};
+
+}
+
+#endif /* _OUSIA_MANAGED_HPP_ */
+
diff --git a/src/core/managed/ManagedContainer.cpp b/src/core/managed/ManagedContainer.cpp
new file mode 100644
index 0000000..e7f30fa
--- /dev/null
+++ b/src/core/managed/ManagedContainer.cpp
@@ -0,0 +1,24 @@
+/*
+ Ousía
+ Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "ManagedContainer.hpp"
+
+namespace ousia {
+
+}
+
diff --git a/src/core/managed/ManagedContainer.hpp b/src/core/managed/ManagedContainer.hpp
new file mode 100644
index 0000000..9ff75d5
--- /dev/null
+++ b/src/core/managed/ManagedContainer.hpp
@@ -0,0 +1,391 @@
+/*
+ Ousía
+ Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#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"
+
+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_CONTAINER_H_ */
+
diff --git a/src/core/managed/Manager.cpp b/src/core/managed/Manager.cpp
new file mode 100644
index 0000000..7b562a8
--- /dev/null
+++ b/src/core/managed/Manager.cpp
@@ -0,0 +1,333 @@
+/*
+ Ousía
+ Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#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<Managed *> 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<Managed *> visited{{curManaged}};
+ std::queue<Managed *> queue{{curManaged}};
+ while (!queue.empty() && !isReachable) {
+ // Pop the next element from the queue, remove the element from
+ // the marked list as we obviously have evaluated it
+ curManaged = queue.front();
+ queue.pop();
+ marked.erase(curManaged);
+
+ // Fetch the Managed descriptor
+ ObjectDescriptor *descr = getDescriptor(curManaged);
+ if (!descr) {
+ continue;
+ }
+
+ // If this Managed is rooted, the complete visited subgraph is
+ // rooted
+ if (descr->rootRefCount > 0) {
+ isReachable = true;
+ break;
+ }
+
+ // Iterate over all objects leading to the current one
+ for (auto &src : descr->refIn) {
+ Managed *srcManaged = src.first;
+
+ // Abort if the Managed already in the reachable list,
+ // otherwise add the Managed to the queue if it was not
+ // visited
+ if (reachable.find(srcManaged) != reachable.end()) {
+ isReachable = true;
+ break;
+ } else if (visited.find(srcManaged) == visited.end()) {
+ visited.insert(srcManaged);
+ queue.push(srcManaged);
+ }
+ }
+ }
+
+ // Insert the objects into the list of to be deleted objects or
+ // reachable objects depending on the "isReachable" flag
+ if (isReachable) {
+ for (auto o : visited) {
+ reachable.insert(o);
+ }
+ } else {
+ for (auto o : visited) {
+ deleteObject(o, getDescriptor(o));
+ }
+ }
+ }
+
+ // Now purge all objects marked for deletion
+ purgeDeleted();
+ }
+}
+}
+
diff --git a/src/core/managed/Manager.hpp b/src/core/managed/Manager.hpp
new file mode 100644
index 0000000..95d08e1
--- /dev/null
+++ b/src/core/managed/Manager.hpp
@@ -0,0 +1,250 @@
+/*
+ Ousía
+ Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <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_ */
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-01 00:47:01 +0000