Line data Source code
1 : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : // vim:cindent:ts=2:et:sw=2:
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 : /* base class for nsCounterList and nsQuoteList */
8 :
9 : #include "nsGenConList.h"
10 : #include "nsLayoutUtils.h"
11 : #include "nsIContent.h"
12 :
13 : void
14 8 : nsGenConList::Clear()
15 : {
16 : // Delete entire list.
17 8 : mNodes.Clear();
18 8 : while (nsGenConNode* node = mList.popFirst()) {
19 0 : delete node;
20 0 : }
21 8 : mSize = 0;
22 8 : mLastInserted = nullptr;
23 8 : }
24 :
25 : bool
26 0 : nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
27 : {
28 : // This algorithm relies on the invariant that nodes of a frame are
29 : // put contiguously in the linked list. This is guaranteed because
30 : // each frame is mapped to only one (nsIContent, pseudoType) pair,
31 : // and the nodes in the linked list are put in the tree order based
32 : // on that pair and offset inside frame.
33 0 : nsGenConNode* node = mNodes.GetAndRemove(aFrame).valueOr(nullptr);
34 0 : if (!node) {
35 0 : return false;
36 : }
37 0 : MOZ_ASSERT(node->mPseudoFrame == aFrame);
38 :
39 0 : while (node && node->mPseudoFrame == aFrame) {
40 0 : nsGenConNode* nextNode = Next(node);
41 0 : Destroy(node);
42 0 : node = nextNode;
43 : }
44 :
45 : // Modification of the list invalidates the cached pointer.
46 0 : mLastInserted = nullptr;
47 :
48 0 : return true;
49 : }
50 :
51 : /**
52 : * Compute the type of the pseudo and the content for the pseudo that
53 : * we'll use for comparison purposes.
54 : * @param aContent the content to use is stored here; it's the element
55 : * that generated the ::before or ::after content, or (if not for generated
56 : * content), the frame's own element
57 : * @return -1 for ::before, +1 for ::after, and 0 otherwise.
58 : */
59 0 : inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent)
60 : {
61 0 : nsIAtom *pseudo = aFrame->StyleContext()->GetPseudo();
62 0 : if (pseudo == nsCSSPseudoElements::before) {
63 0 : *aContent = aFrame->GetContent()->GetParent();
64 0 : return -1;
65 : }
66 0 : if (pseudo == nsCSSPseudoElements::after) {
67 0 : *aContent = aFrame->GetContent()->GetParent();
68 0 : return 1;
69 : }
70 0 : *aContent = aFrame->GetContent();
71 0 : return 0;
72 : }
73 :
74 : /* static */ bool
75 0 : nsGenConList::NodeAfter(const nsGenConNode* aNode1, const nsGenConNode* aNode2)
76 : {
77 0 : nsIFrame *frame1 = aNode1->mPseudoFrame;
78 0 : nsIFrame *frame2 = aNode2->mPseudoFrame;
79 0 : if (frame1 == frame2) {
80 0 : NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
81 0 : return aNode1->mContentIndex > aNode2->mContentIndex;
82 : }
83 : nsIContent *content1;
84 : nsIContent *content2;
85 0 : int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
86 0 : int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
87 0 : if (pseudoType1 == 0 || pseudoType2 == 0) {
88 0 : if (content1 == content2) {
89 0 : NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
90 0 : return pseudoType2 == 0;
91 : }
92 : // We want to treat an element as coming before its :before (preorder
93 : // traversal), so treating both as :before now works.
94 0 : if (pseudoType1 == 0) pseudoType1 = -1;
95 0 : if (pseudoType2 == 0) pseudoType2 = -1;
96 : } else {
97 0 : if (content1 == content2) {
98 0 : NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
99 0 : return pseudoType1 == 1;
100 : }
101 : }
102 : // XXX Switch to the frame version of DoCompareTreePosition?
103 0 : int32_t cmp = nsLayoutUtils::DoCompareTreePosition(content1, content2,
104 0 : pseudoType1, -pseudoType2);
105 0 : MOZ_ASSERT(cmp != 0, "same content, different frames");
106 0 : return cmp > 0;
107 : }
108 :
109 : void
110 0 : nsGenConList::Insert(nsGenConNode* aNode)
111 : {
112 : // Check for append.
113 0 : if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
114 0 : mList.insertBack(aNode);
115 0 : } else if (mLastInserted && mLastInserted != mList.getLast() &&
116 0 : NodeAfter(aNode, mLastInserted) &&
117 0 : NodeAfter(Next(mLastInserted), aNode)) {
118 : // Fast path for inserting many consecutive nodes in one place
119 0 : mLastInserted->setNext(aNode);
120 : } else {
121 : // Binary search.
122 :
123 : // the range of indices at which |aNode| could end up.
124 : // (We already know it can't be at index mSize.)
125 0 : uint32_t first = 0, last = mSize - 1;
126 :
127 : // A cursor to avoid walking more than the length of the list.
128 0 : nsGenConNode* curNode = mList.getLast();
129 0 : uint32_t curIndex = mSize - 1;
130 :
131 0 : while (first != last) {
132 0 : uint32_t test = (first + last) / 2;
133 0 : if (last == curIndex) {
134 0 : for ( ; curIndex != test; --curIndex)
135 0 : curNode = Prev(curNode);
136 : } else {
137 0 : for ( ; curIndex != test; ++curIndex)
138 0 : curNode = Next(curNode);
139 : }
140 :
141 0 : if (NodeAfter(aNode, curNode)) {
142 0 : first = test + 1;
143 : // if we exit the loop, we need curNode to be right
144 0 : ++curIndex;
145 0 : curNode = Next(curNode);
146 : } else {
147 0 : last = test;
148 : }
149 : }
150 0 : curNode->setPrevious(aNode);
151 : }
152 0 : ++mSize;
153 :
154 0 : mLastInserted = aNode;
155 :
156 : // Set the mapping only if it is the first node of the frame.
157 : // The DEBUG blocks below are for ensuring the invariant required by
158 : // nsGenConList::DestroyNodesFor. See comment there.
159 0 : if (IsFirst(aNode) ||
160 0 : Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
161 : #ifdef DEBUG
162 0 : if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
163 0 : MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
164 : "oldFrameFirstNode should now be immediately after "
165 : "the newly-inserted one.");
166 : } else {
167 : // If the node is not the only node in the list.
168 0 : if (!IsFirst(aNode) || !IsLast(aNode)) {
169 0 : nsGenConNode* nextNode = Next(aNode);
170 0 : MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
171 : "There shouldn't exist any node for this frame.");
172 : // If the node is neither the first nor the last node
173 0 : if (!IsFirst(aNode) && !IsLast(aNode)) {
174 0 : MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
175 : "New node should not break contiguity of nodes of "
176 : "the same frame.");
177 : }
178 : }
179 : }
180 : #endif
181 0 : mNodes.Put(aNode->mPseudoFrame, aNode);
182 : } else {
183 : #ifdef DEBUG
184 0 : nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
185 0 : MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
186 0 : for (nsGenConNode* curNode = Prev(aNode);
187 0 : curNode != frameFirstNode; curNode = Prev(curNode)) {
188 0 : MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
189 : "Every node between frameFirstNode and the new node inserted "
190 : "should refer to the same frame.");
191 0 : MOZ_ASSERT(!IsFirst(curNode),
192 : "The newly-inserted node should be in a contiguous run after "
193 : "frameFirstNode, thus frameFirstNode should be reached before "
194 : "the first node of mList.");
195 : }
196 : #endif
197 : }
198 :
199 0 : NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
200 : "sorting error");
201 0 : NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode),
202 : "sorting error");
203 0 : }
|
