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/Noncopyable.h>
27
28 namespace WebCore {
29
30 template <class Run>
31 class BidiRunList {
32 WTF_MAKE_NONCOPYABLE(BidiRunList);
33 public:
BidiRunList()34 BidiRunList()
35 : m_firstRun(0)
36 , m_lastRun(0)
37 , m_logicallyLastRun(0)
38 , m_runCount(0)
39 {
40 }
41
42 // FIXME: Once BidiResolver no longer owns the BidiRunList,
43 // then ~BidiRunList should call deleteRuns() automatically.
44
firstRun()45 Run* firstRun() const { return m_firstRun; }
lastRun()46 Run* lastRun() const { return m_lastRun; }
logicallyLastRun()47 Run* logicallyLastRun() const { return m_logicallyLastRun; }
runCount()48 unsigned runCount() const { return m_runCount; }
49
50 void addRun(Run*);
51 void prependRun(Run*);
52
53 void moveRunToEnd(Run*);
54 void moveRunToBeginning(Run*);
55
56 void deleteRuns();
57 void reverseRuns(unsigned start, unsigned end);
58 void reorderRunsFromLevels();
59
setLogicallyLastRun(Run * run)60 void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
61
62 private:
63 Run* m_firstRun;
64 Run* m_lastRun;
65 Run* m_logicallyLastRun;
66 unsigned m_runCount;
67 };
68
69 template <class Run>
addRun(Run * run)70 inline void BidiRunList<Run>::addRun(Run* run)
71 {
72 if (!m_firstRun)
73 m_firstRun = run;
74 else
75 m_lastRun->m_next = run;
76 m_lastRun = run;
77 m_runCount++;
78 }
79
80 template <class Run>
prependRun(Run * run)81 inline void BidiRunList<Run>::prependRun(Run* run)
82 {
83 ASSERT(!run->m_next);
84
85 if (!m_lastRun)
86 m_lastRun = run;
87 else
88 run->m_next = m_firstRun;
89 m_firstRun = run;
90 m_runCount++;
91 }
92
93 template <class Run>
moveRunToEnd(Run * run)94 inline void BidiRunList<Run>::moveRunToEnd(Run* run)
95 {
96 ASSERT(m_firstRun);
97 ASSERT(m_lastRun);
98 ASSERT(run->m_next);
99
100 Run* current = 0;
101 Run* next = m_firstRun;
102 while (next != run) {
103 current = next;
104 next = current->next();
105 }
106
107 if (!current)
108 m_firstRun = run->next();
109 else
110 current->m_next = run->m_next;
111
112 run->m_next = 0;
113 m_lastRun->m_next = run;
114 m_lastRun = run;
115 }
116
117 template <class Run>
moveRunToBeginning(Run * run)118 inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
119 {
120 ASSERT(m_firstRun);
121 ASSERT(m_lastRun);
122 ASSERT(run != m_firstRun);
123
124 Run* current = m_firstRun;
125 Run* next = current->next();
126 while (next != run) {
127 current = next;
128 next = current->next();
129 }
130
131 current->m_next = run->m_next;
132 if (run == m_lastRun)
133 m_lastRun = current;
134
135 run->m_next = m_firstRun;
136 m_firstRun = run;
137 }
138
139 template <class Run>
deleteRuns()140 void BidiRunList<Run>::deleteRuns()
141 {
142 if (!m_firstRun)
143 return;
144
145 Run* curr = m_firstRun;
146 while (curr) {
147 Run* s = curr->next();
148 curr->destroy();
149 curr = s;
150 }
151
152 m_firstRun = 0;
153 m_lastRun = 0;
154 m_runCount = 0;
155 }
156
157 template <class Run>
reverseRuns(unsigned start,unsigned end)158 void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
159 {
160 if (start >= end)
161 return;
162
163 ASSERT(end < m_runCount);
164
165 // Get the item before the start of the runs to reverse and put it in
166 // |beforeStart|. |curr| should point to the first run to reverse.
167 Run* curr = m_firstRun;
168 Run* beforeStart = 0;
169 unsigned i = 0;
170 while (i < start) {
171 i++;
172 beforeStart = curr;
173 curr = curr->next();
174 }
175
176 Run* startRun = curr;
177 while (i < end) {
178 i++;
179 curr = curr->next();
180 }
181 Run* endRun = curr;
182 Run* afterEnd = curr->next();
183
184 i = start;
185 curr = startRun;
186 Run* newNext = afterEnd;
187 while (i <= end) {
188 // Do the reversal.
189 Run* next = curr->next();
190 curr->m_next = newNext;
191 newNext = curr;
192 curr = next;
193 i++;
194 }
195
196 // Now hook up beforeStart and afterEnd to the startRun and endRun.
197 if (beforeStart)
198 beforeStart->m_next = endRun;
199 else
200 m_firstRun = endRun;
201
202 startRun->m_next = afterEnd;
203 if (!afterEnd)
204 m_lastRun = startRun;
205 }
206
207 } // namespace WebCore
208
209 #endif // BidiRunList
210