diff options
Diffstat (limited to 'src/core')
| -rw-r--r-- | src/core/dom/Node.cpp | 9 | ||||
| -rw-r--r-- | src/core/dom/Node.hpp | 259 | ||||
| -rw-r--r-- | src/core/dom/NodeClasses.cpp | 80 | ||||
| -rw-r--r-- | src/core/dom/NodeClasses.hpp | 138 |
4 files changed, 364 insertions, 122 deletions
diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp index 7c4852a..cdf8137 100644 --- a/src/core/dom/Node.cpp +++ b/src/core/dom/Node.cpp @@ -217,15 +217,14 @@ void NodeManager::deleteRef(Node *tar, Node *src, bool all) if (dTar->refInCount() == 0) { deleteNode(tar, dTar); } else if (dTar->rootRefCount == 0) { - // Call the tracing garbage collector if the number of marked nodes - // is larger than the threshold value and this function was not - // called from inside the deleteNode function + // Insert the node into the list of nodes to be inspected by garbage + // collection marked.insert(tar); } } - // Call the garbage collector if the marked size is larger than the actual - // value + // Call the tracing garbage collector if the marked size is larger than the + // actual value if (marked.size() >= threshold) { sweep(); } diff --git a/src/core/dom/Node.hpp b/src/core/dom/Node.hpp index 6869253..10572e7 100644 --- a/src/core/dom/Node.hpp +++ b/src/core/dom/Node.hpp @@ -30,6 +30,15 @@ namespace dom { class Node; +template <class T> +class Handle; + +template <class T> +class Rooted; + +template <class T> +class Owned; + /** * Enum used for specifying the Reference direction. */ @@ -251,20 +260,11 @@ public: void sweep(); }; -template <class T> -class BaseHandle; - -template <class T> -class RootedHandle; - -template <class T> -class Handle; - /** * The Node class builds the main class in the DOM graph. The Node class * instances are managed by a NodeManager which performs garbage collection of * the Node instances. Do not pass raw Node pointers around, always wrap them - * inside a RootedHandle or Handle class. + * inside a Rooted or Owned class. */ class Node { protected: @@ -278,29 +278,29 @@ public: NodeManager &getManager() { return mgr; } template <class T> - Handle<T> acquire(const BaseHandle<T> &h) + Owned<T> acquire(const Handle<T> &h) { - return Handle<T>{h, this}; + return Owned<T>{h, this}; } template <class T> - Handle<T> acquire(BaseHandle<T> &&h) + Owned<T> acquire(Handle<T> &&h) { - return Handle<T>{h, this}; + return Owned<T>{h, this}; } template <class T> - Handle<T> acquire(T *t) + Owned<T> acquire(T *t) { - return Handle<T>{t, this}; + return Owned<T>{t, this}; } }; template <class T> -class BaseHandle { +class Handle { protected: - friend class RootedHandle<T>; - friend class Handle<T>; + friend class Rooted<T>; + friend class Owned<T>; static_assert(std::is_base_of<Node, T>::value, "T must be a Node"); @@ -311,11 +311,29 @@ protected: public: /** - * Constructor of the base handle class. + * Constructor of the base Owned class. + * + * @param ptr is the pointer to the node the Owned 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 derived class to this Handle instance. * - * @param ptr is the pointer to the node the handle should represent. + * @param h is the Handle that should be asigned to this instance. */ - BaseHandle(T *ptr) : ptr(ptr) {} + template <class T2> + Handle(const Handle<T2> &h) + : ptr(h.get()) + { + } /** * Returns the underlying pointer. @@ -333,101 +351,111 @@ public: T &operator*() { return *ptr; } /** - * Comparison operator between base handle and base handle. + * Comparison operator between base Owned and base Owned. */ - bool operator==(const BaseHandle &h) const { return ptr == h.ptr; } + bool operator==(const Handle &h) const { return ptr == h.ptr; } /** - * Comparison operator between base handle and pointer. + * Comparison operator between base Owned and pointer. */ - friend bool operator==(const BaseHandle &h, const Node *n) + friend bool operator==(const Handle &h, const Node *n) { return h.ptr == n; } /** - * Comparison operator between base handle and pointer. + * Comparison operator between base Owned and pointer. */ - friend bool operator==(const Node *n, const BaseHandle &h) + friend bool operator==(const Node *n, const Handle &h) { return h.ptr == n; } + + /** + * 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(); } }; /** - * A RootedHandle represents a directed, garbage collected pointer at a Node + * Null represents a null handle. + */ +static const Handle<Node> Null{nullptr}; + +/** + * A Rooted represents a directed, garbage collected pointer at a Node * instance. The lifetime of the represented node is guaranteed to be at least - * as long as the lifetime of the RootedHandle instance. + * as long as the lifetime of the Rooted instance. */ template <class T> -class RootedHandle : public BaseHandle<T> { +class Rooted : public Handle<T> { private: void addRef() { - if (BaseHandle<T>::ptr) { - BaseHandle<T>::ptr->getManager().addRef(BaseHandle<T>::ptr, - nullptr); + if (Handle<T>::ptr) { + Handle<T>::ptr->getManager().addRef(Handle<T>::ptr, nullptr); } } void deleteRef() { - if (BaseHandle<T>::ptr) { - BaseHandle<T>::ptr->getManager().deleteRef(BaseHandle<T>::ptr, - nullptr); + if (Handle<T>::ptr) { + Handle<T>::ptr->getManager().deleteRef(Handle<T>::ptr, nullptr); } } public: /** - * Creates an empty handle. + * Creates an empty Owned. */ - RootedHandle() : BaseHandle<T>(nullptr){}; + Rooted() : Handle<T>(nullptr){}; /** - * Copies the given handle to this handle instance. Both handles are - * indistinguishable after the operation. + * Copies the given Rooted to this Rooted instance. Both handles + * are indistinguishable after the operation. * - * @param h is the handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - RootedHandle(const RootedHandle<T> &h) : BaseHandle<T>(h.ptr) { addRef(); } + Rooted(const Rooted<T> &h) : Handle<T>(h.ptr) { addRef(); } /** - * Move constructor. Moves the given rvalue handle to this instance. + * Move constructor. Moves the given rvalue Rooted to this instance. * - * @param h is the handle to be moved to this instance. + * @param h is the Rooted to be moved to this instance. */ - RootedHandle(RootedHandle<T> &&h) : BaseHandle<T>(h.ptr) - { - h.ptr = nullptr; - } + Rooted(Rooted<T> &&h) : Handle<T>(h.ptr) { h.ptr = nullptr; } /** - * Constructor of the handle class. + * Constructor of the Owned class. * - * @param ptr is the node the handle should represent. + * @param ptr is the node the Owned should represent. */ - RootedHandle(T *ptr) : BaseHandle<T>(ptr) { addRef(); } + Rooted(T *ptr) : Handle<T>(ptr) { addRef(); } /** - * Constructor of the handle class. + * Constructor of the Owned class. * - * @param h is another handle whose Node should be used. + * @param h is another Owned whose Node should be used. */ template <class T2> - RootedHandle(const BaseHandle<T2> &h) - : BaseHandle<T>(h.get()) + Rooted(const Handle<T2> &h) + : Handle<T>(h.get()) { addRef(); } /** - * Assignment operator. Assigns the given handle to this handle instance. + * Assignment operator. Assigns the given Owned to this Owned instance. * Both handles are indistinguishable after the operation. * - * @param h is the handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - RootedHandle<T> &operator=(const RootedHandle<T> &h) + Rooted<T> &operator=(const Rooted<T> &h) { deleteRef(); this->ptr = h.ptr; @@ -436,12 +464,12 @@ public: } /** - * Move assignment operator. Moves the given rvalue handle into this + * Move assignment operator. Moves the given rvalue Owned into this * instance. * - * @param h is the handle to be moved to this instance. + * @param h is the Owned to be moved to this instance. */ - RootedHandle<T> &operator=(RootedHandle<T> &&h) + Rooted<T> &operator=(Rooted<T> &&h) { deleteRef(); this->ptr = h.ptr; @@ -450,26 +478,27 @@ public: } /** - * Assignment operator. Assigns the given handle to this handle instance. + * Assignment operator. Assigns the given Owned to this Owned instance. * Both handles are indistinguishable after the operation. * - * @param h is the handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - RootedHandle<T> &operator=(const BaseHandle<T> &h) + template <class T2> + Rooted<T> &operator=(const Handle<T2> &h) { deleteRef(); - this->ptr = h.ptr; + this->ptr = h.get(); addRef(); return *this; } /** - * Move assignment operator. Moves the given rvalue handle into this + * Move assignment operator. Moves the given rvalue Owned into this * instance. * - * @param h is the handle to be moved to this instance. + * @param h is the Owned to be moved to this instance. */ - RootedHandle<T> &operator=(BaseHandle<T> &&h) + Rooted<T> &operator=(Handle<T> &&h) { deleteRef(); this->ptr = h.ptr; @@ -478,85 +507,86 @@ public: } /** - * Destructor of the RootedHandle class, deletes all refrences the class is + * Destructor of the Rooted class, deletes all refrences the class is * still holding. */ - ~RootedHandle() { deleteRef(); } + ~Rooted() { deleteRef(); } }; /** - * The handle class represents a directed, garbage collected pointer at a Node + * The Owned class represents a directed, garbage collected pointer at a Node * instance. The lifetime of the represented node is guaranteed to be at last * as long as the lifetime of the Node instance which owns this reference. */ template <class T> -class Handle : public BaseHandle<T> { +class Owned : public Handle<T> { private: Node *owner; void addRef() { - if (BaseHandle<T>::ptr && owner) { - owner->getManager().addRef(BaseHandle<T>::ptr, owner); + if (Handle<T>::ptr && owner) { + owner->getManager().addRef(Handle<T>::ptr, owner); } } void deleteRef() { - if (BaseHandle<T>::ptr && owner) { - owner->getManager().deleteRef(BaseHandle<T>::ptr, owner); + if (Handle<T>::ptr && owner) { + owner->getManager().deleteRef(Handle<T>::ptr, owner); } } public: /** - * Creates an empty handle. + * Creates an empty Owned. */ - Handle() : BaseHandle<T>(nullptr), owner(nullptr){}; + Owned() : Handle<T>(nullptr), owner(nullptr){}; /** - * Copies the given handle to this handle instance. Both handles are - * indistinguishable after the operation. Note that especially the handle + * 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 handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - Handle(const Handle<T> &h) : BaseHandle<T>(h.get()), owner(h.getOwner()) + Owned(const Owned<T> &h) : Handle<T>(h.get()), owner(h.getOwner()) { addRef(); } /** - * Copies the given handle of another derived type to this handle instance. + * 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 handle owner is copied. + * type). Note that especially the Owned owner is copied. * - * @param h is the handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - template<class T2> - Handle(const Handle<T2> &h) : BaseHandle<T>(h.get()), owner(h.getOwner()) + template <class T2> + Owned(const Owned<T2> &h) + : Handle<T>(h.get()), owner(h.getOwner()) { addRef(); } /** - * Move constructor. Moves the given rvalue handle to this instance. + * Move constructor. Moves the given rvalue Owned to this instance. * - * @param h is the handle to be moved to this instance. + * @param h is the Owned to be moved to this instance. */ - Handle(Handle<T> &&h) : BaseHandle<T>(h.get()), owner(h.getOwner()) + Owned(Owned<T> &&h) : Handle<T>(h.get()), owner(h.getOwner()) { h.ptr = nullptr; } /** - * Assignment operator. Assigns the given handle to this handle instance. + * Assignment operator. Assigns the given Owned to this Owned instance. * Both handles are indistinguishable after the operation. Note that - * especially the handle owner is copied. + * especially the Owned owner is copied. * - * @param h is the handle that should be asigned to this instance. + * @param h is the Owned that should be asigned to this instance. */ - Handle<T> &operator=(const Handle<T> &h) + Owned<T> &operator=(const Owned<T> &h) { deleteRef(); this->ptr = h.ptr; @@ -566,12 +596,12 @@ public: } /** - * Move assignment operator. Moves the given rvalue handle into this + * Move assignment operator. Moves the given rvalue Owned into this * instance. * - * @param h is the handle to be moved to this instance. + * @param h is the Owned to be moved to this instance. */ - Handle<T> &operator=(Handle<T> &&h) + Owned<T> &operator=(Owned<T> &&h) { deleteRef(); this->ptr = h.ptr; @@ -581,46 +611,41 @@ public: } /** - * Constructor of the handle class. + * Constructor of the Owned class. * - * @param ptr is the node the handle should represent. - * @param owner is the node which owns this handle instance. The ptr node + * @param ptr is the node the Owned should represent. + * @param owner is the node which owns this Owned instance. The ptr node * is guaranteed to live at least as long as the owner. */ - Handle(T *ptr, Node *owner) : BaseHandle<T>(ptr), owner(owner) { addRef(); } + Owned(T *ptr, Node *owner) : Handle<T>(ptr), owner(owner) { addRef(); } /** - * Constructor of the handle class. + * Constructor of the Owned class. * - * @param h is another handle whose Node should be used. - * @param owner is the node which owns this handle instance. The ptr node + * @param h is another Owned whose Node should be used. + * @param owner is the node which owns this Owned instance. The ptr node * is guaranteed to live at least as long as the owner. */ template <class T2> - Handle(const BaseHandle<T2> &h, Node *owner) - : BaseHandle<T>(h.get()), owner(owner) + Owned(const Handle<T2> &h, Node *owner) + : Handle<T>(h.get()), owner(owner) { addRef(); } /** - * Destructor of the Handle class, deletes all refrences the class is still + * Destructor of the Owned class, deletes all refrences the class is still * holding. */ - ~Handle() { deleteRef(); } + ~Owned() { deleteRef(); } /** - * Returns the reference to the owner of the handle. + * Returns the reference to the owner of the Owned. * - * @return the handle owner. + * @return the Owned owner. */ - Node* getOwner() const { - return owner; - } + Node *getOwner() const { return owner; } }; - -using RootedNode = RootedHandle<Node>; -using NodeHandle = Handle<Node>; } } diff --git a/src/core/dom/NodeClasses.cpp b/src/core/dom/NodeClasses.cpp new file mode 100644 index 0000000..a3c321c --- /dev/null +++ b/src/core/dom/NodeClasses.cpp @@ -0,0 +1,80 @@ +/* + 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 <string> +#include <unordered_map> +#include <vector> + +#include "Node.hpp" + +namespace ousia { +namespace dom { + +/* Class NamedNode */ + +void NamedNode::doResolve(const std::vector<Rooted<Node>> &res, + const std::vector<std::string> &path, + ResolutionCallback callback, void *callbackData, + int idx, const VisitorMap &visited) +{ + // Do nothing in the default implementation +} + +void NamedNode::resolve(const std::vector<Rooted<Node>> &res, + const std::vector<std::string> &path, + ResolutionCallback *callback, void *callbackData, + int idx, const VisitorMap &visited) +{ + // Abort if this node was already visited for this path index + std::pair<Node *, int> recKey = std::make_pair(this, idx); + if (visited.find(recKey) != visited.end()) { + return res.size(); + } + visited.insert(recKey); + + // Check whether the we can continue the path + if (path[idx] == name) { + // If we have reached the end of the path and the node is successfully + // tested by the callback function, add it to the result. Otherwise + // continue searching along the path + if (idx == path.size() - 1) { + if (!callback || callback(this, callbackData)) { + res.push_back(this); + } + } else { + doResolve(res, path, callback, callbackData, idx + 1, visited); + } + } + + // Restart the search from here in order to find all possible nodes that can + // be matched to the given path + doResolve(res, path, callback, callbackData, 0, visited); +} + +std::vector<Rooted<Node>> NamedNode::resolve( + const std::vector<std::string> &path, ResolutionCallback callback, + void *callbackData) +{ + std::vector<Rooted<Node>> res; + VisitorMap visited; + resolve(res, path, callback, callbackData, 0, visited); + return res; +} +} +} + diff --git a/src/core/dom/NodeClasses.hpp b/src/core/dom/NodeClasses.hpp new file mode 100644 index 0000000..2164386 --- /dev/null +++ b/src/core/dom/NodeClasses.hpp @@ -0,0 +1,138 @@ +/* + 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_DOM_NODE_CLASSES_HPP_ +#define _OUSIA_DOM_NODE_CLASSES_HPP_ + +#include <string> +#include <unordered_map> +#include <vector> + +#include "Node.hpp" + +namespace ousia { +namespace dom { + +/** + * The ResolutionCallback is used when resolving names to Node instances. The + * callback tests whether the given node meets the requirements for inclusion + * in the result list. + * + * @param node is the node which should be tested. + * @param userData is user-defined data which is passed to the callback. + * @return true if the node should be included in the result set, false + * otherwise. + */ +typedef bool (*ResolutionCallback)(Handle<Node> node, void *userData); + +/** + * The NamedNode class can be used as a mixin for other node classes which want + * to have a unique name which is known at construction time (this includes + * nodes representing domains, classes, types, etc.). + */ +class NamedNode : virtual public Node { +protected: + struct VisitorHash { + size_t operator()(const std::pair<Node *, int> &p) const + { + return hash<Node *>(p.first) + 37 * hash<int>(p.second); + } + }; + + using VisitorMap = std::unordered_map<std::pair<Node *, int>, VisitorHash>; + + /** + * Function which should be overwritten by derived classes in order to + * resolve node names to a list of possible nodes. The implementations of + * this function do not need to do anything but call the "resovle" function + * of any child instance of NamedNode. + * + * @param res is the result list containing all possible nodes matching the + * name specified in the path. + * @param path is a list specifying a path of node names which is meant to + * specify a certain named node. + * @param idx is the current index in the path. + * @param visited is a map which is used to prevent unwanted recursion. + * @param callback is a callback function which may check whether a certain + * node should be in the result set. If nullptr is given, all nodes matching + * the path are included. The callback function can be used to restrict the + * type of matched functions. + * @param callbackData is user-defined data that should be passed to the + * callback. + */ + virtual void doResolve(const std::vector<Rooted<Node>> &res, + const std::vector<std::string> &path, + ResolutionCallback callback, void *callbackData, + int idx, const VisitorMap &visited); + + /** + * Function which resolves a name paht to a list of possible nodes. + * + * @param res is the result list containing all possible nodes matching the + * name specified in the path. + * @param path is a list specifying a path of node names which is meant to + * specify a certain named node. + * @param callback is a callback function which may check whether a certain + * node should be in the result set. If nullptr is given, all nodes matching + * the path are included. The callback function can be used to restrict the + * type of matched functions. + * @param callbackData is user-defined data that should be passed to the + * callback. + * @param idx is the current index in the path. + * @param visited is a map which is used to prevent unwanted recursion. + */ + void resolve(const std::vector<Rooted<Node>> &res, + const std::vector<std::string> &path, + ResolutionCallback callback, void *callbackData, int idx, + const VisitorMap &visited); + +public: + /** + * Constructor of the NamedNode class. + * + * @param name is the name the element should be known under. + */ + Named(std::string name) : name{name} {}; + + /** + * Name of the node. + */ + const std::string name; + + /** + * Function which resolves a name paht to a list of possible nodes. + * + * @param path is a list specifying a path of node names which is meant to + * specify a certain named node. + * @param callback is a callback function which may check whether a certain + * node should be in the result set. If nullptr is given, all nodes matching + * the path are included. The callback function can be used to restrict the + * type of matched functions. + * @param callbackData is user-defined data that should be passed to the + * callback. + * @return a vector containing all found node references. + */ + std::vector<Rooted<Node>> resolve(const std::vector<std::string> &path, + ResolutionCallback callback = nullptr, + void *callbackData = nullptr); +}; +} +} + +#endif /* _OUSIA_DOM_NODE_CLASSES_HPP_ */ + |