DepthOrderedFrameList.h (2506B)
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 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef mozilla_DepthOrderedFrameList_h 8 #define mozilla_DepthOrderedFrameList_h 9 10 #include "mozilla/HashTable.h" 11 #include "mozilla/ReverseIterator.h" 12 #include "nsTArray.h" 13 14 class nsIFrame; 15 16 namespace mozilla { 17 18 class DepthOrderedFrameList { 19 public: 20 // Add a frame to the set being tracked. 21 void Add(nsIFrame* aFrame); 22 23 // Remove this frame if present. 24 void Remove(nsIFrame* aFrame) { 25 mFrames.remove(aFrame); 26 mSortedFrames.ClearAndRetainStorage(); 27 } 28 29 // Remove and return one of the shallowest frames from the list. 30 // (If two frames are at the same depth, order is indeterminate.) 31 nsIFrame* PopShallowestRoot(); 32 33 // Remove all frames. 34 void Clear() { 35 mFrames.clear(); 36 mSortedFrames.Clear(); 37 } 38 39 // Is this frame one of the elements in the list? 40 bool Contains(nsIFrame* aFrame) const { return mFrames.has(aFrame); } 41 42 // Are there no elements? 43 bool IsEmpty() const { return mFrames.empty(); } 44 45 // Is the given frame an ancestor of any dirty root? 46 bool FrameIsAncestorOfAnyElement(nsIFrame* aFrame) const; 47 48 auto IterFromShallowest() const { 49 EnsureSortedList(); 50 return Reversed(mSortedFrames); 51 } 52 53 private: 54 // Set of the frames we're tracking and their depth in the frame tree. This 55 // is the primary record maintained by the Add and Remove methods. The sorted 56 // list in mSortedFrames is created on demand when we need to iterate in depth 57 // order. 58 HashMap<nsIFrame*, uint32_t> mFrames; 59 60 struct FrameAndDepth { 61 nsIFrame* mFrame; 62 uint32_t mDepth; 63 64 // Easy conversion to nsIFrame*, as it's the most likely need. 65 operator nsIFrame*() const { return mFrame; } 66 67 // Used to sort by reverse depths, i.e., deeper < shallower. 68 bool operator<(const FrameAndDepth& aOther) const { 69 // Reverse depth! So '>' instead of '<'. 70 return mDepth > aOther.mDepth; 71 } 72 }; 73 74 // The list of frames sorted by decreasing depths; created/updated lazily. 75 mutable nsTArray<FrameAndDepth> mSortedFrames; 76 77 void EnsureSortedList() const { 78 if (mSortedFrames.IsEmpty() && !mFrames.empty()) { 79 BuildSortedList(); 80 } 81 } 82 83 void BuildSortedList() const; 84 }; 85 86 } // namespace mozilla 87 88 #endif