1 /*
2 * Copyright (C) 2005 Allan Sandfeld Jensen (kde@carewolf.com)
3 * Copyright (C) 2006, 2007 Apple Inc. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22 #include "config.h"
23 #include "CounterNode.h"
24
25 #include "RenderCounter.h"
26 #include "RenderObject.h"
27 #include <stdio.h>
28
29 namespace WebCore {
30
CounterNode(RenderObject * o,bool hasResetType,int value)31 CounterNode::CounterNode(RenderObject* o, bool hasResetType, int value)
32 : m_hasResetType(hasResetType)
33 , m_value(value)
34 , m_countInParent(0)
35 , m_owner(o)
36 , m_rootRenderer(0)
37 , m_parent(0)
38 , m_previousSibling(0)
39 , m_nextSibling(0)
40 , m_firstChild(0)
41 , m_lastChild(0)
42 {
43 }
44
~CounterNode()45 CounterNode::~CounterNode()
46 {
47 resetRenderers();
48 }
49
create(RenderObject * owner,bool hasResetType,int value)50 PassRefPtr<CounterNode> CounterNode::create(RenderObject* owner, bool hasResetType, int value)
51 {
52 return adoptRef(new CounterNode(owner, hasResetType, value));
53 }
54
nextInPreOrderAfterChildren(const CounterNode * stayWithin) const55 CounterNode* CounterNode::nextInPreOrderAfterChildren(const CounterNode* stayWithin) const
56 {
57 if (this == stayWithin)
58 return 0;
59
60 const CounterNode* current = this;
61 CounterNode* next;
62 while (!(next = current->m_nextSibling)) {
63 current = current->m_parent;
64 if (!current || current == stayWithin)
65 return 0;
66 }
67 return next;
68 }
69
nextInPreOrder(const CounterNode * stayWithin) const70 CounterNode* CounterNode::nextInPreOrder(const CounterNode* stayWithin) const
71 {
72 if (CounterNode* next = m_firstChild)
73 return next;
74
75 return nextInPreOrderAfterChildren(stayWithin);
76 }
77
lastDescendant() const78 CounterNode* CounterNode::lastDescendant() const
79 {
80 CounterNode* last = m_lastChild;
81 if (!last)
82 return 0;
83
84 while (CounterNode* lastChild = last->m_lastChild)
85 last = lastChild;
86
87 return last;
88 }
89
previousInPreOrder() const90 CounterNode* CounterNode::previousInPreOrder() const
91 {
92 CounterNode* previous = m_previousSibling;
93 if (!previous)
94 return m_parent;
95
96 while (CounterNode* lastChild = previous->m_lastChild)
97 previous = lastChild;
98
99 return previous;
100 }
101
computeCountInParent() const102 int CounterNode::computeCountInParent() const
103 {
104 int increment = actsAsReset() ? 0 : m_value;
105 if (m_previousSibling)
106 return m_previousSibling->m_countInParent + increment;
107 ASSERT(m_parent->m_firstChild == this);
108 return m_parent->m_value + increment;
109 }
110
addRenderer(RenderCounter * value)111 void CounterNode::addRenderer(RenderCounter* value)
112 {
113 if (!value) {
114 ASSERT_NOT_REACHED();
115 return;
116 }
117 if (value->m_counterNode) {
118 ASSERT_NOT_REACHED();
119 value->m_counterNode->removeRenderer(value);
120 }
121 ASSERT(!value->m_nextForSameCounter);
122 for (RenderCounter* iterator = m_rootRenderer;iterator; iterator = iterator->m_nextForSameCounter) {
123 if (iterator == value) {
124 ASSERT_NOT_REACHED();
125 return;
126 }
127 }
128 value->m_nextForSameCounter = m_rootRenderer;
129 m_rootRenderer = value;
130 if (value->m_counterNode != this) {
131 if (value->m_counterNode) {
132 ASSERT_NOT_REACHED();
133 value->m_counterNode->removeRenderer(value);
134 }
135 value->m_counterNode = this;
136 }
137 }
138
removeRenderer(RenderCounter * value)139 void CounterNode::removeRenderer(RenderCounter* value)
140 {
141 if (!value) {
142 ASSERT_NOT_REACHED();
143 return;
144 }
145 if (value->m_counterNode && value->m_counterNode != this) {
146 ASSERT_NOT_REACHED();
147 value->m_counterNode->removeRenderer(value);
148 }
149 RenderCounter* previous = 0;
150 for (RenderCounter* iterator = m_rootRenderer;iterator; iterator = iterator->m_nextForSameCounter) {
151 if (iterator == value) {
152 if (previous)
153 previous->m_nextForSameCounter = value->m_nextForSameCounter;
154 else
155 m_rootRenderer = value->m_nextForSameCounter;
156 value->m_nextForSameCounter = 0;
157 value->m_counterNode = 0;
158 return;
159 }
160 previous = iterator;
161 }
162 ASSERT_NOT_REACHED();
163 }
164
resetRenderers()165 void CounterNode::resetRenderers()
166 {
167 while (m_rootRenderer)
168 m_rootRenderer->invalidate(); // This makes m_rootRenderer point to the next renderer if any since it disconnects the m_rootRenderer from this.
169 }
170
resetThisAndDescendantsRenderers()171 void CounterNode::resetThisAndDescendantsRenderers()
172 {
173 CounterNode* node = this;
174 do {
175 node->resetRenderers();
176 node = node->nextInPreOrder(this);
177 } while (node);
178 }
179
recount()180 void CounterNode::recount()
181 {
182 for (CounterNode* node = this; node; node = node->m_nextSibling) {
183 int oldCount = node->m_countInParent;
184 int newCount = node->computeCountInParent();
185 if (oldCount == newCount)
186 break;
187 node->m_countInParent = newCount;
188 node->resetThisAndDescendantsRenderers();
189 }
190 }
191
insertAfter(CounterNode * newChild,CounterNode * refChild,const AtomicString & identifier)192 void CounterNode::insertAfter(CounterNode* newChild, CounterNode* refChild, const AtomicString& identifier)
193 {
194 ASSERT(newChild);
195 ASSERT(!newChild->m_parent);
196 ASSERT(!newChild->m_previousSibling);
197 ASSERT(!newChild->m_nextSibling);
198 ASSERT(!refChild || refChild->m_parent == this);
199
200 if (newChild->m_hasResetType) {
201 while (m_lastChild != refChild)
202 RenderCounter::destroyCounterNode(m_lastChild->owner(), identifier);
203 }
204
205 CounterNode* next;
206
207 if (refChild) {
208 next = refChild->m_nextSibling;
209 refChild->m_nextSibling = newChild;
210 } else {
211 next = m_firstChild;
212 m_firstChild = newChild;
213 }
214
215 newChild->m_parent = this;
216 newChild->m_previousSibling = refChild;
217
218 if (!newChild->m_firstChild || newChild->m_hasResetType) {
219 newChild->m_nextSibling = next;
220 if (next) {
221 ASSERT(next->m_previousSibling == refChild);
222 next->m_previousSibling = newChild;
223 } else {
224 ASSERT(m_lastChild == refChild);
225 m_lastChild = newChild;
226 }
227
228 newChild->m_countInParent = newChild->computeCountInParent();
229 newChild->resetThisAndDescendantsRenderers();
230 if (next)
231 next->recount();
232 return;
233 }
234
235 // The code below handles the case when a formerly root increment counter is loosing its root position
236 // and therefore its children become next siblings.
237 CounterNode* last = newChild->m_lastChild;
238 CounterNode* first = newChild->m_firstChild;
239
240 newChild->m_nextSibling = first;
241 first->m_previousSibling = newChild;
242 // The case when the original next sibling of the inserted node becomes a child of
243 // one of the former children of the inserted node is not handled as it is believed
244 // to be impossible since:
245 // 1. if the increment counter node lost it's root position as a result of another
246 // counter node being created, it will be inserted as the last child so next is null.
247 // 2. if the increment counter node lost it's root position as a result of a renderer being
248 // inserted into the document's render tree, all its former children counters are attached
249 // to children of the inserted renderer and hence cannot be in scope for counter nodes
250 // attached to renderers that were already in the document's render tree.
251 last->m_nextSibling = next;
252 if (next)
253 next->m_previousSibling = last;
254 else
255 m_lastChild = last;
256 for (next = first; ; next = next->m_nextSibling) {
257 next->m_parent = this;
258 if (last == next)
259 break;
260 }
261 newChild->m_firstChild = 0;
262 newChild->m_lastChild = 0;
263 newChild->m_countInParent = newChild->computeCountInParent();
264 newChild->resetRenderers();
265 first->recount();
266 }
267
removeChild(CounterNode * oldChild)268 void CounterNode::removeChild(CounterNode* oldChild)
269 {
270 ASSERT(oldChild);
271 ASSERT(!oldChild->m_firstChild);
272 ASSERT(!oldChild->m_lastChild);
273
274 CounterNode* next = oldChild->m_nextSibling;
275 CounterNode* previous = oldChild->m_previousSibling;
276
277 oldChild->m_nextSibling = 0;
278 oldChild->m_previousSibling = 0;
279 oldChild->m_parent = 0;
280
281 if (previous)
282 previous->m_nextSibling = next;
283 else {
284 ASSERT(m_firstChild == oldChild);
285 m_firstChild = next;
286 }
287
288 if (next)
289 next->m_previousSibling = previous;
290 else {
291 ASSERT(m_lastChild == oldChild);
292 m_lastChild = previous;
293 }
294
295 if (next)
296 next->recount();
297 }
298
299 #ifndef NDEBUG
300
showTreeAndMark(const CounterNode * node)301 static void showTreeAndMark(const CounterNode* node)
302 {
303 const CounterNode* root = node;
304 while (root->parent())
305 root = root->parent();
306
307 for (const CounterNode* current = root; current; current = current->nextInPreOrder()) {
308 fprintf(stderr, "%c", (current == node) ? '*' : ' ');
309 for (const CounterNode* parent = current; parent && parent != root; parent = parent->parent())
310 fprintf(stderr, " ");
311 fprintf(stderr, "%p %s: %d %d P:%p PS:%p NS:%p R:%p\n",
312 current, current->actsAsReset() ? "reset____" : "increment", current->value(),
313 current->countInParent(), current->parent(), current->previousSibling(),
314 current->nextSibling(), current->owner());
315 }
316 fflush(stderr);
317 }
318
319 #endif
320
321 } // namespace WebCore
322
323 #ifndef NDEBUG
324
showCounterTree(const WebCore::CounterNode * counter)325 void showCounterTree(const WebCore::CounterNode* counter)
326 {
327 if (counter)
328 showTreeAndMark(counter);
329 }
330
331 #endif
332