1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this file, 5 * You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef TreeIterator_h 8 #define TreeIterator_h 9 10 #include "mozilla/Attributes.h" 11 #include "nsIContent.h" 12 13 /** 14 * A generic pre-order tree iterator on top of ChildIterator. 15 * 16 * See ChildIterator.h for the kind of iterators you can use as the template 17 * argument for this class. 18 */ 19 20 namespace mozilla { 21 namespace dom { 22 23 template <typename ChildIterator> 24 class MOZ_STACK_CLASS TreeIterator { 25 enum class Direction { 26 Forward, 27 Backwards, 28 }; 29 30 template <Direction aDirection> GetNextChild(ChildIterator & aIter)31 nsIContent* GetNextChild(ChildIterator& aIter) { 32 return aDirection == Direction::Forward ? aIter.GetNextChild() 33 : aIter.GetPreviousChild(); 34 } 35 36 template <Direction> 37 inline void Advance(); 38 template <Direction> 39 inline void AdvanceSkippingChildren(); 40 41 public: TreeIterator(nsIContent & aRoot)42 explicit TreeIterator(nsIContent& aRoot) : mRoot(aRoot), mCurrent(&aRoot) {} 43 GetCurrent()44 nsIContent* GetCurrent() const { return mCurrent; } 45 46 // Note that this keeps the iterator state consistent in case of failure. 47 inline bool Seek(nsIContent&); 48 inline nsIContent* GetNext(); 49 inline nsIContent* GetNextSkippingChildren(); 50 inline nsIContent* GetPrev(); 51 inline nsIContent* GetPrevSkippingChildren(); 52 53 private: 54 using IteratorArray = AutoTArray<ChildIterator, 30>; 55 56 nsIContent& mRoot; 57 nsIContent* mCurrent; 58 IteratorArray mParentIterators; 59 }; 60 61 template <typename ChildIterator> 62 template <typename TreeIterator<ChildIterator>::Direction aDirection> AdvanceSkippingChildren()63inline void TreeIterator<ChildIterator>::AdvanceSkippingChildren() { 64 while (true) { 65 if (MOZ_UNLIKELY(mParentIterators.IsEmpty())) { 66 mCurrent = nullptr; 67 return; 68 } 69 70 if (nsIContent* nextSibling = 71 GetNextChild<aDirection>(mParentIterators.LastElement())) { 72 mCurrent = nextSibling; 73 return; 74 } 75 mParentIterators.RemoveLastElement(); 76 } 77 } 78 79 template <typename ChildIterator> Seek(nsIContent & aContent)80inline bool TreeIterator<ChildIterator>::Seek(nsIContent& aContent) { 81 IteratorArray parentIterators; 82 nsIContent* current = &aContent; 83 while (current != &mRoot) { 84 nsIContent* parent = ChildIterator::GetParent(*current); 85 if (!parent) { 86 return false; 87 } 88 89 ChildIterator children(parent); 90 if (!children.Seek(current)) { 91 return false; 92 } 93 94 parentIterators.AppendElement(std::move(children)); 95 current = parent; 96 } 97 98 parentIterators.Reverse(); 99 100 mParentIterators.Clear(); 101 mParentIterators.SwapElements(parentIterators); 102 mCurrent = &aContent; 103 return true; 104 } 105 106 template <typename ChildIterator> 107 template <typename TreeIterator<ChildIterator>::Direction aDirection> Advance()108inline void TreeIterator<ChildIterator>::Advance() { 109 MOZ_ASSERT(mCurrent); 110 const bool startAtBeginning = aDirection == Direction::Forward; 111 ChildIterator children(mCurrent, startAtBeginning); 112 if (nsIContent* first = GetNextChild<aDirection>(children)) { 113 mCurrent = first; 114 mParentIterators.AppendElement(std::move(children)); 115 return; 116 } 117 118 AdvanceSkippingChildren<aDirection>(); 119 } 120 121 template <typename ChildIterator> GetNext()122inline nsIContent* TreeIterator<ChildIterator>::GetNext() { 123 Advance<Direction::Forward>(); 124 return GetCurrent(); 125 } 126 127 template <typename ChildIterator> GetPrev()128inline nsIContent* TreeIterator<ChildIterator>::GetPrev() { 129 Advance<Direction::Backwards>(); 130 return GetCurrent(); 131 } 132 133 template <typename ChildIterator> GetNextSkippingChildren()134inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() { 135 AdvanceSkippingChildren<Direction::Forward>(); 136 return GetCurrent(); 137 } 138 139 template <typename ChildIterator> GetPrevSkippingChildren()140inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() { 141 AdvanceSkippingChildren<Direction::Backwards>(); 142 return GetCurrent(); 143 } 144 145 } // namespace dom 146 } // namespace mozilla 147 148 #endif 149