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