summaryrefslogtreecommitdiffstats
path: root/dom/base/TreeIterator.h
diff options
context:
space:
mode:
Diffstat (limited to 'dom/base/TreeIterator.h')
-rw-r--r--dom/base/TreeIterator.h147
1 files changed, 147 insertions, 0 deletions
diff --git a/dom/base/TreeIterator.h b/dom/base/TreeIterator.h
new file mode 100644
index 0000000000..67c8457ef0
--- /dev/null
+++ b/dom/base/TreeIterator.h
@@ -0,0 +1,147 @@
+/* -*- 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 TreeIterator_h
+#define TreeIterator_h
+
+#include "mozilla/Attributes.h"
+#include "nsIContent.h"
+
+/**
+ * A generic pre-order tree iterator on top of ChildIterator.
+ *
+ * See ChildIterator.h for the kind of iterators you can use as the template
+ * argument for this class.
+ */
+
+namespace mozilla {
+namespace dom {
+
+template <typename ChildIterator>
+class MOZ_STACK_CLASS TreeIterator {
+ enum class Direction {
+ Forward,
+ Backwards,
+ };
+
+ template <Direction aDirection>
+ nsIContent* GetNextChild(ChildIterator& aIter) {
+ return aDirection == Direction::Forward ? aIter.GetNextChild()
+ : aIter.GetPreviousChild();
+ }
+
+ template <Direction>
+ inline void Advance();
+ template <Direction>
+ inline void AdvanceSkippingChildren();
+
+ public:
+ explicit TreeIterator(nsIContent& aRoot) : mRoot(aRoot), mCurrent(&aRoot) {}
+
+ nsIContent* GetCurrent() const { return mCurrent; }
+
+ // Note that this keeps the iterator state consistent in case of failure.
+ inline bool Seek(nsIContent&);
+ inline nsIContent* GetNext();
+ inline nsIContent* GetNextSkippingChildren();
+ inline nsIContent* GetPrev();
+ inline nsIContent* GetPrevSkippingChildren();
+
+ private:
+ using IteratorArray = AutoTArray<ChildIterator, 30>;
+
+ nsIContent& mRoot;
+ nsIContent* mCurrent;
+ IteratorArray mParentIterators;
+};
+
+template <typename ChildIterator>
+template <typename TreeIterator<ChildIterator>::Direction aDirection>
+inline void TreeIterator<ChildIterator>::AdvanceSkippingChildren() {
+ while (true) {
+ if (MOZ_UNLIKELY(mParentIterators.IsEmpty())) {
+ mCurrent = nullptr;
+ return;
+ }
+
+ if (nsIContent* nextSibling =
+ GetNextChild<aDirection>(mParentIterators.LastElement())) {
+ mCurrent = nextSibling;
+ return;
+ }
+ mParentIterators.RemoveLastElement();
+ }
+}
+
+template <typename ChildIterator>
+inline bool TreeIterator<ChildIterator>::Seek(nsIContent& aContent) {
+ IteratorArray parentIterators;
+ nsIContent* current = &aContent;
+ while (current != &mRoot) {
+ nsIContent* parent = ChildIterator::GetParent(*current);
+ if (!parent) {
+ return false;
+ }
+
+ ChildIterator children(parent);
+ if (!children.Seek(current)) {
+ return false;
+ }
+
+ parentIterators.AppendElement(std::move(children));
+ current = parent;
+ }
+
+ parentIterators.Reverse();
+
+ mParentIterators = std::move(parentIterators);
+ mCurrent = &aContent;
+ return true;
+}
+
+template <typename ChildIterator>
+template <typename TreeIterator<ChildIterator>::Direction aDirection>
+inline void TreeIterator<ChildIterator>::Advance() {
+ MOZ_ASSERT(mCurrent);
+ const bool startAtBeginning = aDirection == Direction::Forward;
+ ChildIterator children(mCurrent, startAtBeginning);
+ if (nsIContent* first = GetNextChild<aDirection>(children)) {
+ mCurrent = first;
+ mParentIterators.AppendElement(std::move(children));
+ return;
+ }
+
+ AdvanceSkippingChildren<aDirection>();
+}
+
+template <typename ChildIterator>
+inline nsIContent* TreeIterator<ChildIterator>::GetNext() {
+ Advance<Direction::Forward>();
+ return GetCurrent();
+}
+
+template <typename ChildIterator>
+inline nsIContent* TreeIterator<ChildIterator>::GetPrev() {
+ Advance<Direction::Backwards>();
+ return GetCurrent();
+}
+
+template <typename ChildIterator>
+inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() {
+ AdvanceSkippingChildren<Direction::Forward>();
+ return GetCurrent();
+}
+
+template <typename ChildIterator>
+inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() {
+ AdvanceSkippingChildren<Direction::Backwards>();
+ return GetCurrent();
+}
+
+} // namespace dom
+} // namespace mozilla
+
+#endif