From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- gfx/layers/TreeTraversal.h | 276 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 276 insertions(+) create mode 100644 gfx/layers/TreeTraversal.h (limited to 'gfx/layers/TreeTraversal.h') 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 +#include + +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 + static Node* FirstChild(Node* n) { + return n->GetFirstChild(); + } + template + static Node* NextSibling(Node* n) { + return n->GetNextSibling(); + } + template + static Node FirstChild(Node n) { + return n.GetFirstChild(); + } + template + static Node NextSibling(Node n) { + return n.GetNextSibling(); + } +}; +class ReverseIterator { + public: + template + static Node* FirstChild(Node* n) { + return n->GetLastChild(); + } + template + static Node* NextSibling(Node* n) { + return n->GetPrevSibling(); + } + template + static Node FirstChild(Node n) { + return n.GetLastChild(); + } + template + 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 +static auto ForEachNode(Node aRoot, const PreAction& aPreAction, + const PostAction& aPostAction) + -> std::enable_if_t< + std::is_same_v && + std::is_same_v, + 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(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 +static auto ForEachNode(Node aRoot, const PreAction& aPreAction, + const PostAction& aPostAction) + -> std::enable_if_t && + std::is_same_v, + void> { + if (!aRoot) { + return; + } + + aPreAction(aRoot); + + for (Node child = Iterator::FirstChild(aRoot); child; + child = Iterator::NextSibling(child)) { + ForEachNode(child, aPreAction, aPostAction); + } + + aPostAction(aRoot); +} + +/* + * ForEachNode pre-order traversal, using TraversalFlag. + */ +template +auto ForEachNode(Node aRoot, const PreAction& aPreAction) -> std::enable_if_t< + std::is_same_v, bool> { + return ForEachNode( + aRoot, aPreAction, [](Node aNode) { return TraversalFlag::Continue; }); +} + +/* + * ForEachNode pre-order, not using TraversalFlag. + */ +template +auto ForEachNode(Node aRoot, const PreAction& aPreAction) + -> std::enable_if_t, + void> { + ForEachNode(aRoot, aPreAction, [](Node aNode) {}); +} + +/* + * ForEachNode post-order traversal, using TraversalFlag. + */ +template +auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction) + -> std::enable_if_t< + std::is_same_v, bool> { + return ForEachNode( + aRoot, [](Node aNode) { return TraversalFlag::Continue; }, aPostAction); +} + +/* + * ForEachNode post-order, not using TraversalFlag. + */ +template +auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction) + -> std::enable_if_t, + void> { + ForEachNode( + 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 +Node BreadthFirstSearch(Node aRoot, const Condition& aCondition) { + if (!aRoot) { + return Node(); + } + + std::queue 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 +Node DepthFirstSearch(Node aRoot, const Condition& aCondition) { + Node result = Node(); + + ForEachNode(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 +Node DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition) { + Node result = Node(); + + ForEachNodePostOrder(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 -- cgit v1.2.3