summaryrefslogtreecommitdiffstats
path: root/gfx/layers/TreeTraversal.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--gfx/layers/TreeTraversal.h276
1 files changed, 276 insertions, 0 deletions
diff --git a/gfx/layers/TreeTraversal.h b/gfx/layers/TreeTraversal.h
new file mode 100644
index 0000000000..4c02a4e5b5
--- /dev/null
+++ b/gfx/layers/TreeTraversal.h
@@ -0,0 +1,276 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_layers_TreeTraversal_h
+#define mozilla_layers_TreeTraversal_h
+
+#include <queue>
+#include <type_traits>
+
+namespace mozilla {
+namespace layers {
+
+/*
+ * Returned by |aPostAction| and |aPreAction| in ForEachNode, indicates
+ * the behavior to follow either action:
+ *
+ * TraversalFlag::Skip - the node's children are not traversed. If this
+ * flag is returned by |aPreAction|, |aPostAction| is skipped for the
+ * current node, as well.
+ * TraversalFlag::Continue - traversal continues normally.
+ * TraversalFlag::Abort - traversal stops immediately.
+ */
+enum class TraversalFlag { Skip, Continue, Abort };
+
+/*
+ * Iterator types to be specified in traversal function calls:
+ *
+ * ForwardIterator - for nodes using GetFirstChild() and GetNextSibling()
+ * ReverseIterator - for nodes using GetLastChild() and GetPrevSibling()
+ */
+class ForwardIterator {
+ public:
+ template <typename Node>
+ static Node* FirstChild(Node* n) {
+ return n->GetFirstChild();
+ }
+ template <typename Node>
+ static Node* NextSibling(Node* n) {
+ return n->GetNextSibling();
+ }
+ template <typename Node>
+ static Node FirstChild(Node n) {
+ return n.GetFirstChild();
+ }
+ template <typename Node>
+ static Node NextSibling(Node n) {
+ return n.GetNextSibling();
+ }
+};
+class ReverseIterator {
+ public:
+ template <typename Node>
+ static Node* FirstChild(Node* n) {
+ return n->GetLastChild();
+ }
+ template <typename Node>
+ static Node* NextSibling(Node* n) {
+ return n->GetPrevSibling();
+ }
+ template <typename Node>
+ static Node FirstChild(Node n) {
+ return n.GetLastChild();
+ }
+ template <typename Node>
+ static Node NextSibling(Node n) {
+ return n.GetPrevSibling();
+ }
+};
+
+/*
+ * Do a depth-first traversal of the tree rooted at |aRoot|, performing
+ * |aPreAction| before traversal of children and |aPostAction| after.
+ *
+ * Returns true if traversal aborted, false if continued normally. If
+ * TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
+ * is not performed.
+ *
+ * |Iterator| should have static methods named NextSibling() and FirstChild()
+ * that accept an argument of type Node. For convenience, classes
+ * |ForwardIterator| and |ReverseIterator| are provided which implement these
+ * methods as GetNextSibling()/GetFirstChild() and
+ * GetPrevSibling()/GetLastChild(), respectively.
+ */
+template <typename Iterator, typename Node, typename PreAction,
+ typename PostAction>
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
+ const PostAction& aPostAction)
+ -> std::enable_if_t<
+ std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag> &&
+ std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>,
+ bool> {
+ if (!aRoot) {
+ return false;
+ }
+
+ TraversalFlag result = aPreAction(aRoot);
+
+ if (result == TraversalFlag::Abort) {
+ return true;
+ }
+
+ if (result == TraversalFlag::Continue) {
+ for (Node child = Iterator::FirstChild(aRoot); child;
+ child = Iterator::NextSibling(child)) {
+ bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
+ if (abort) {
+ return true;
+ }
+ }
+
+ result = aPostAction(aRoot);
+
+ if (result == TraversalFlag::Abort) {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/*
+ * Do a depth-first traversal of the tree rooted at |aRoot|, performing
+ * |aPreAction| before traversal of children and |aPostAction| after.
+ */
+template <typename Iterator, typename Node, typename PreAction,
+ typename PostAction>
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
+ const PostAction& aPostAction)
+ -> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void> &&
+ std::is_same_v<decltype(aPostAction(aRoot)), void>,
+ void> {
+ if (!aRoot) {
+ return;
+ }
+
+ aPreAction(aRoot);
+
+ for (Node child = Iterator::FirstChild(aRoot); child;
+ child = Iterator::NextSibling(child)) {
+ ForEachNode<Iterator>(child, aPreAction, aPostAction);
+ }
+
+ aPostAction(aRoot);
+}
+
+/*
+ * ForEachNode pre-order traversal, using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PreAction>
+auto ForEachNode(Node aRoot, const PreAction& aPreAction) -> std::enable_if_t<
+ std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag>, bool> {
+ return ForEachNode<Iterator>(
+ aRoot, aPreAction, [](Node aNode) { return TraversalFlag::Continue; });
+}
+
+/*
+ * ForEachNode pre-order, not using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PreAction>
+auto ForEachNode(Node aRoot, const PreAction& aPreAction)
+ -> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void>,
+ void> {
+ ForEachNode<Iterator>(aRoot, aPreAction, [](Node aNode) {});
+}
+
+/*
+ * ForEachNode post-order traversal, using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PostAction>
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
+ -> std::enable_if_t<
+ std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>, bool> {
+ return ForEachNode<Iterator>(
+ aRoot, [](Node aNode) { return TraversalFlag::Continue; }, aPostAction);
+}
+
+/*
+ * ForEachNode post-order, not using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PostAction>
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
+ -> std::enable_if_t<std::is_same_v<decltype(aPostAction(aRoot)), void>,
+ void> {
+ ForEachNode<Iterator>(
+ aRoot, [](Node aNode) {}, aPostAction);
+}
+
+/*
+ * Do a breadth-first search of the tree rooted at |aRoot|, and return the
+ * first visited node that satisfies |aCondition|, or nullptr if no such node
+ * was found.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node()
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node BreadthFirstSearch(Node aRoot, const Condition& aCondition) {
+ if (!aRoot) {
+ return Node();
+ }
+
+ std::queue<Node> queue;
+ queue.push(aRoot);
+ while (!queue.empty()) {
+ Node node = queue.front();
+ queue.pop();
+
+ if (aCondition(node)) {
+ return node;
+ }
+
+ for (Node child = Iterator::FirstChild(node); child;
+ child = Iterator::NextSibling(child)) {
+ queue.push(child);
+ }
+ }
+
+ return Node();
+}
+
+/*
+ * Do a pre-order, depth-first search of the tree rooted at |aRoot|, and
+ * return the first visited node that satisfies |aCondition|, or nullptr
+ * if no such node was found.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node().
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node DepthFirstSearch(Node aRoot, const Condition& aCondition) {
+ Node result = Node();
+
+ ForEachNode<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
+ if (aCondition(aNode)) {
+ result = aNode;
+ return TraversalFlag::Abort;
+ }
+
+ return TraversalFlag::Continue;
+ });
+
+ return result;
+}
+
+/*
+ * Perform a post-order, depth-first search starting at aRoot.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node().
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition) {
+ Node result = Node();
+
+ ForEachNodePostOrder<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
+ if (aCondition(aNode)) {
+ result = aNode;
+ return TraversalFlag::Abort;
+ }
+
+ return TraversalFlag::Continue;
+ });
+
+ return result;
+}
+
+} // namespace layers
+} // namespace mozilla
+
+#endif // mozilla_layers_TreeTraversal_h