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