1 /*
2 * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3 * Copyright (C) 2003, 2004, 2006, 2007, 2008 Apple Inc. All right reserved.
4 * Copyright (C) 2011 Google, Inc. All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #ifndef BidiRunList_h
24 #define BidiRunList_h
25
26 #include "wtf/Assertions.h"
27 #include "wtf/Noncopyable.h"
28
29 namespace blink {
30
31 template <class Run>
32 class BidiRunList {
33 WTF_MAKE_NONCOPYABLE(BidiRunList);
34 public:
BidiRunList()35 BidiRunList()
36 : m_firstRun(0)
37 , m_lastRun(0)
38 , m_logicallyLastRun(0)
39 , m_runCount(0)
40 {
41 }
42
43 // FIXME: Once BidiResolver no longer owns the BidiRunList,
44 // then ~BidiRunList should call deleteRuns() automatically.
45
firstRun()46 Run* firstRun() const { return m_firstRun; }
lastRun()47 Run* lastRun() const { return m_lastRun; }
logicallyLastRun()48 Run* logicallyLastRun() const { return m_logicallyLastRun; }
runCount()49 unsigned runCount() const { return m_runCount; }
50
51 void addRun(Run*);
52 void prependRun(Run*);
53
54 void moveRunToEnd(Run*);
55 void moveRunToBeginning(Run*);
56
57 void deleteRuns();
58 void reverseRuns(unsigned start, unsigned end);
59 void reorderRunsFromLevels();
60
setLogicallyLastRun(Run * run)61 void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
62
63 void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns);
64
65 private:
66 void clearWithoutDestroyingRuns();
67
68 Run* m_firstRun;
69 Run* m_lastRun;
70 Run* m_logicallyLastRun;
71 unsigned m_runCount;
72 };
73
74 template <class Run>
addRun(Run * run)75 inline void BidiRunList<Run>::addRun(Run* run)
76 {
77 if (!m_firstRun)
78 m_firstRun = run;
79 else
80 m_lastRun->m_next = run;
81 m_lastRun = run;
82 m_runCount++;
83 }
84
85 template <class Run>
prependRun(Run * run)86 inline void BidiRunList<Run>::prependRun(Run* run)
87 {
88 ASSERT(!run->m_next);
89
90 if (!m_lastRun)
91 m_lastRun = run;
92 else
93 run->m_next = m_firstRun;
94 m_firstRun = run;
95 m_runCount++;
96 }
97
98 template <class Run>
moveRunToEnd(Run * run)99 inline void BidiRunList<Run>::moveRunToEnd(Run* run)
100 {
101 ASSERT(m_firstRun);
102 ASSERT(m_lastRun);
103 ASSERT(run->m_next);
104
105 Run* current = 0;
106 Run* next = m_firstRun;
107 while (next != run) {
108 current = next;
109 next = current->next();
110 }
111
112 if (!current)
113 m_firstRun = run->next();
114 else
115 current->m_next = run->m_next;
116
117 run->m_next = 0;
118 m_lastRun->m_next = run;
119 m_lastRun = run;
120 }
121
122 template <class Run>
moveRunToBeginning(Run * run)123 inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
124 {
125 ASSERT(m_firstRun);
126 ASSERT(m_lastRun);
127 ASSERT(run != m_firstRun);
128
129 Run* current = m_firstRun;
130 Run* next = current->next();
131 while (next != run) {
132 current = next;
133 next = current->next();
134 }
135
136 current->m_next = run->m_next;
137 if (run == m_lastRun)
138 m_lastRun = current;
139
140 run->m_next = m_firstRun;
141 m_firstRun = run;
142 }
143
144 template <class Run>
replaceRunWithRuns(Run * toReplace,BidiRunList<Run> & newRuns)145 void BidiRunList<Run>::replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns)
146 {
147 ASSERT(newRuns.runCount());
148 ASSERT(m_firstRun);
149 ASSERT(toReplace);
150
151 if (m_firstRun == toReplace) {
152 m_firstRun = newRuns.firstRun();
153 } else {
154 // Find the run just before "toReplace" in the list of runs.
155 Run* previousRun = m_firstRun;
156 while (previousRun->next() != toReplace)
157 previousRun = previousRun->next();
158 ASSERT(previousRun);
159 previousRun->setNext(newRuns.firstRun());
160 }
161
162 newRuns.lastRun()->setNext(toReplace->next());
163
164 // Fix up any of other pointers which may now be stale.
165 if (m_lastRun == toReplace)
166 m_lastRun = newRuns.lastRun();
167 if (m_logicallyLastRun == toReplace)
168 m_logicallyLastRun = newRuns.logicallyLastRun();
169 m_runCount += newRuns.runCount() - 1; // We added the new runs and removed toReplace.
170
171 delete toReplace;
172 newRuns.clearWithoutDestroyingRuns();
173 }
174
175 template <class Run>
clearWithoutDestroyingRuns()176 void BidiRunList<Run>::clearWithoutDestroyingRuns()
177 {
178 m_firstRun = 0;
179 m_lastRun = 0;
180 m_logicallyLastRun = 0;
181 m_runCount = 0;
182 }
183
184 template <class Run>
deleteRuns()185 void BidiRunList<Run>::deleteRuns()
186 {
187 if (!m_firstRun)
188 return;
189
190 Run* curr = m_firstRun;
191 while (curr) {
192 Run* s = curr->next();
193 delete curr;
194 curr = s;
195 }
196
197 clearWithoutDestroyingRuns();
198 }
199
200 template <class Run>
reverseRuns(unsigned start,unsigned end)201 void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
202 {
203 ASSERT(m_runCount);
204 if (start >= end)
205 return;
206
207 ASSERT(end < m_runCount);
208
209 // Get the item before the start of the runs to reverse and put it in
210 // |beforeStart|. |curr| should point to the first run to reverse.
211 Run* curr = m_firstRun;
212 Run* beforeStart = 0;
213 unsigned i = 0;
214 while (i < start) {
215 i++;
216 beforeStart = curr;
217 curr = curr->next();
218 }
219
220 Run* startRun = curr;
221 while (i < end) {
222 i++;
223 curr = curr->next();
224 }
225 Run* endRun = curr;
226 Run* afterEnd = curr->next();
227
228 i = start;
229 curr = startRun;
230 Run* newNext = afterEnd;
231 while (i <= end) {
232 // Do the reversal.
233 Run* next = curr->next();
234 curr->m_next = newNext;
235 newNext = curr;
236 curr = next;
237 i++;
238 }
239
240 // Now hook up beforeStart and afterEnd to the startRun and endRun.
241 if (beforeStart)
242 beforeStart->m_next = endRun;
243 else
244 m_firstRun = endRun;
245
246 startRun->m_next = afterEnd;
247 if (!afterEnd)
248 m_lastRun = startRun;
249 }
250
251 } // namespace blink
252
253 #endif // BidiRunList
254