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
DisplayItemHashEntry(KeyTypePointer aKey)26 explicit DisplayItemHashEntry(KeyTypePointer aKey) : mKey(*aKey) {}
27 DisplayItemHashEntry(DisplayItemHashEntry&&) = default;
28
29 ~DisplayItemHashEntry() = default;
30
GetKey()31 KeyType GetKey() const { return mKey; }
KeyEquals(KeyTypePointer aKey)32 bool KeyEquals(KeyTypePointer aKey) const { return mKey == *aKey; }
33
KeyToPointer(KeyType & aKey)34 static KeyTypePointer KeyToPointer(KeyType& aKey) { return &aKey; }
HashKey(KeyTypePointer 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>
SpanContains(mozilla::Span<const T> & aSpan,T aItem)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 {
IndexIndex62 Index() : val(0) {}
IndexIndex63 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;
DirectedAcyclicGraph(DirectedAcyclicGraph && aOther)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
Length()110 size_t Length() { return mNodesInfo.Length(); }
111
GetDirectPredecessors(Index<T> aNodeIndex)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>
EnsureCapacityFor(const DirectedAcyclicGraph<OtherUnits> & aOther)120 void EnsureCapacityFor(const DirectedAcyclicGraph<OtherUnits>& aOther) {
121 mNodesInfo.SetCapacity(aOther.mNodesInfo.Length());
122 mDirectPredecessorList.SetCapacity(aOther.mDirectPredecessorList.Length());
123 }
124
Clear()125 void Clear() {
126 mNodesInfo.Clear();
127 mDirectPredecessorList.Clear();
128 }
129
130 struct NodeInfo {
NodeInfoNodeInfo131 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
AddedToMergedListOldItemInfo149 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);
IsUsedOldItemInfo160 bool IsUsed() { return mUsed; }
161
IsDiscardedOldItemInfo162 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_
181