layout/painting/RetainedDisplayListHelpers.h

   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 RETAINEDDISPLAYLISTHELPERS_H_
   8 #define RETAINEDDISPLAYLISTHELPERS_H_
   9
  10 #include "PLDHashTable.h"
  11
  12 struct DisplayItemKey {
  13   bool operator==(const DisplayItemKey& aOther) const {
  14     return mFrame == aOther.mFrame && mPerFrameKey == aOther.mPerFrameKey;
  15   }
  16
  17   nsIFrame* mFrame;
  18   uint32_t mPerFrameKey;
  19 };
  20
  21 class DisplayItemHashEntry : public PLDHashEntryHdr {
  22  public:
  23   typedef DisplayItemKey KeyType;
  24   typedef const DisplayItemKey* KeyTypePointer;
  25
  26   explicit DisplayItemHashEntry(KeyTypePointer aKey) : mKey(*aKey) {}
  27   DisplayItemHashEntry(DisplayItemHashEntry&&) = default;
  28
  29   ~DisplayItemHashEntry() = default;
  30
  31   KeyType GetKey() const { return mKey; }
  32   bool KeyEquals(KeyTypePointer aKey) const { return mKey == *aKey; }
  33
  34   static KeyTypePointer KeyToPointer(KeyType& aKey) { return &aKey; }
  35   static PLDHashNumber HashKey(KeyTypePointer aKey) {
  36     if (!aKey) {
  37       return 0;
  38     }
  39
  40     return mozilla::HashGeneric(aKey->mFrame, aKey->mPerFrameKey);
  41   }
  42   enum { ALLOW_MEMMOVE = true };
  43
  44   DisplayItemKey mKey;
  45 };
  46
  47 template <typename T>
  48 bool SpanContains(mozilla::Span<const T>& aSpan, T aItem) {
  49   for (const T& i : aSpan) {
  50     if (i == aItem) {
  51       return true;
  52     }
  53   }
  54   return false;
  55 }
  56
  57 class OldListUnits {};
  58 class MergedListUnits {};
  59
  60 template <typename Units>
  61 struct Index {
  62   Index() : val(0) {}
  63   explicit Index(size_t aVal) : val(aVal) {
  64     MOZ_RELEASE_ASSERT(aVal < std::numeric_limits<uint32_t>::max(),
  65                        "List index overflowed");
  66   }
  67
  68   bool operator==(const Index<Units>& aOther) const {
  69     return val == aOther.val;
  70   }
  71
  72   uint32_t val;
  73 };
  74 typedef Index<OldListUnits> OldListIndex;
  75 typedef Index<MergedListUnits> MergedListIndex;
  76
  77 template <typename T>
  78 class DirectedAcyclicGraph {
  79  public:
  80   DirectedAcyclicGraph() = default;
  81   DirectedAcyclicGraph(DirectedAcyclicGraph&& aOther)
  82       : mNodesInfo(std::move(aOther.mNodesInfo)),
  83         mDirectPredecessorList(std::move(aOther.mDirectPredecessorList)) {}
  84
  85   DirectedAcyclicGraph& operator=(DirectedAcyclicGraph&& aOther) {
  86     mNodesInfo = std::move(aOther.mNodesInfo);
  87     mDirectPredecessorList = std::move(aOther.mDirectPredecessorList);
  88     return *this;
  89   }
  90
  91   Index<T> AddNode(
  92       mozilla::Span<const Index<T>> aDirectPredecessors,
  93       const mozilla::Maybe<Index<T>>& aExtraPredecessor = mozilla::Nothing()) {
  94     size_t index = mNodesInfo.Length();
  95     mNodesInfo.AppendElement(NodeInfo(mDirectPredecessorList.Length(),
  96                                       aDirectPredecessors.Length()));
  97     if (aExtraPredecessor &&
  98         !SpanContains(aDirectPredecessors, aExtraPredecessor.value())) {
  99       mNodesInfo.LastElement().mDirectPredecessorCount++;
 100       mDirectPredecessorList.SetCapacity(mDirectPredecessorList.Length() +
 101                                          aDirectPredecessors.Length() + 1);
 102       mDirectPredecessorList.AppendElements(aDirectPredecessors);
 103       mDirectPredecessorList.AppendElement(aExtraPredecessor.value());
 104     } else {
 105       mDirectPredecessorList.AppendElements(aDirectPredecessors);
 106     }
 107     return Index<T>(index);
 108   }
 109
 110   size_t Length() { return mNodesInfo.Length(); }
 111
 112   mozilla::Span<Index<T>> GetDirectPredecessors(Index<T> aNodeIndex) {
 113     NodeInfo& node = mNodesInfo[aNodeIndex.val];
 114     return mozilla::MakeSpan(mDirectPredecessorList)
 115         .Subspan(node.mIndexInDirectPredecessorList,
 116                  node.mDirectPredecessorCount);
 117   }
 118
 119   template <typename OtherUnits>
 120   void EnsureCapacityFor(const DirectedAcyclicGraph<OtherUnits>& aOther) {
 121     mNodesInfo.SetCapacity(aOther.mNodesInfo.Length());
 122     mDirectPredecessorList.SetCapacity(aOther.mDirectPredecessorList.Length());
 123   }
 124
 125   void Clear() {
 126     mNodesInfo.Clear();
 127     mDirectPredecessorList.Clear();
 128   }
 129
 130   struct NodeInfo {
 131     NodeInfo(size_t aIndexInDirectPredecessorList,
 132              size_t aDirectPredecessorCount)
 133         : mIndexInDirectPredecessorList(aIndexInDirectPredecessorList),
 134           mDirectPredecessorCount(aDirectPredecessorCount) {}
 135     size_t mIndexInDirectPredecessorList;
 136     size_t mDirectPredecessorCount;
 137   };
 138
 139   nsTArray<NodeInfo> mNodesInfo;
 140   nsTArray<Index<T>> mDirectPredecessorList;
 141 };
 142
 143 struct RetainedDisplayListBuilder;
 144 class nsDisplayItem;
 145
 146 struct OldItemInfo {
 147   explicit OldItemInfo(nsDisplayItem* aItem);
 148
 149   void AddedToMergedList(MergedListIndex aIndex) {
 150     MOZ_ASSERT(!IsUsed());
 151     mUsed = true;
 152     mIndex = aIndex;
 153     mItem = nullptr;
 154   }
 155
 156   void AddedMatchToMergedList(RetainedDisplayListBuilder* aBuilder,
 157                               MergedListIndex aIndex);
 158   void Discard(RetainedDisplayListBuilder* aBuilder,
 159                nsTArray<MergedListIndex>&& aDirectPredecessors);
 160   bool IsUsed() { return mUsed; }
 161
 162   bool IsDiscarded() {
 163     MOZ_ASSERT(IsUsed());
 164     return mDiscarded;
 165   }
 166
 167   bool IsChanged();
 168
 169   nsDisplayItem* mItem;
 170   nsTArray<MergedListIndex> mDirectPredecessors;
 171   MergedListIndex mIndex;
 172   bool mUsed;
 173   bool mDiscarded;
 174   bool mOwnsItem;
 175 };
 176
 177 bool AnyContentAncestorModified(nsIFrame* aFrame,
 178                                 nsIFrame* aStopAtFrame = nullptr);
 179
 180 #endif  // RETAINEDDISPLAYLISTHELPERS_H_