tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

TreeIterator.h (4024B)

      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>
     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:
     42  explicit TreeIterator(nsIContent& aRoot) : mRoot(aRoot), mCurrent(&aRoot) {}
     43 
     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>
     63 inline 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>
     80 inline 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 = std::move(parentIterators);
    101  mCurrent = &aContent;
    102  return true;
    103 }
    104 
    105 template <typename ChildIterator>
    106 template <typename TreeIterator<ChildIterator>::Direction aDirection>
    107 inline void TreeIterator<ChildIterator>::Advance() {
    108  MOZ_ASSERT(mCurrent);
    109  const bool startAtBeginning = aDirection == Direction::Forward;
    110  ChildIterator children(mCurrent, startAtBeginning);
    111  if (nsIContent* first = GetNextChild<aDirection>(children)) {
    112    mCurrent = first;
    113    mParentIterators.AppendElement(std::move(children));
    114    return;
    115  }
    116 
    117  AdvanceSkippingChildren<aDirection>();
    118 }
    119 
    120 template <typename ChildIterator>
    121 inline nsIContent* TreeIterator<ChildIterator>::GetNext() {
    122  Advance<Direction::Forward>();
    123  return GetCurrent();
    124 }
    125 
    126 template <typename ChildIterator>
    127 inline nsIContent* TreeIterator<ChildIterator>::GetPrev() {
    128  Advance<Direction::Backwards>();
    129  return GetCurrent();
    130 }
    131 
    132 template <typename ChildIterator>
    133 inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() {
    134  AdvanceSkippingChildren<Direction::Forward>();
    135  return GetCurrent();
    136 }
    137 
    138 template <typename ChildIterator>
    139 inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() {
    140  AdvanceSkippingChildren<Direction::Backwards>();
    141  return GetCurrent();
    142 }
    143 
    144 }  // namespace dom
    145 }  // namespace mozilla
    146 
    147 #endif