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
28namespace WebCore {
29
30template <class Run>
31class BidiRunList {
32 WTF_MAKE_NONCOPYABLE(BidiRunList);
33public:
34 BidiRunList()
35 : m_lastRun(nullptr)
36 , m_logicallyLastRun(nullptr)
37 , m_runCount(0)
38 {
39 }
40
41 // FIXME: Once BidiResolver no longer owns the BidiRunList,
42 // then ~BidiRunList should call deleteRuns() automatically.
43
44 Run* firstRun() const { return m_firstRun.get(); }
45 Run* lastRun() const { return m_lastRun; }
46 Run* logicallyLastRun() const { return m_logicallyLastRun; }
47 unsigned runCount() const { return m_runCount; }
48
49 void appendRun(std::unique_ptr<Run>&&);
50 void prependRun(std::unique_ptr<Run>&&);
51
52 void moveRunToEnd(Run*);
53 void moveRunToBeginning(Run*);
54
55 void clear();
56 void reverseRuns(unsigned start, unsigned end);
57 void reorderRunsFromLevels();
58
59 void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
60
61 void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns);
62
63private:
64
65 // The runs form a singly-linked-list, where the links (Run::m_next) imply ownership (and are of type std::unique_ptr).
66 // The raw pointers below point into the singly-linked-list.
67 std::unique_ptr<Run> m_firstRun; // The head of the list
68 Run* m_lastRun;
69 Run* m_logicallyLastRun;
70 unsigned m_runCount;
71};
72
73template <class Run>
74inline void BidiRunList<Run>::appendRun(std::unique_ptr<Run>&& run)
75{
76 if (!m_firstRun) {
77 m_firstRun = WTFMove(run);
78 m_lastRun = m_firstRun.get();
79 } else {
80 m_lastRun->setNext(WTFMove(run));
81 m_lastRun = m_lastRun->next();
82 }
83 m_runCount++;
84}
85
86template <class Run>
87inline void BidiRunList<Run>::prependRun(std::unique_ptr<Run>&& run)
88{
89 ASSERT(!run->next());
90
91 if (!m_lastRun)
92 m_lastRun = run.get();
93 else
94 run->setNext(WTFMove(m_firstRun));
95 m_firstRun = WTFMove(run);
96 m_runCount++;
97}
98
99template <class Run>
100inline void BidiRunList<Run>::moveRunToEnd(Run* run)
101{
102 ASSERT(m_firstRun);
103 ASSERT(m_lastRun);
104 ASSERT(run->next());
105
106 Run* previous = nullptr;
107 Run* current = m_firstRun.get();
108 while (current != run) {
109 previous = current;
110 current = previous->next();
111 }
112
113 if (!previous) {
114 ASSERT(m_firstRun.get() == run);
115 std::unique_ptr<Run> originalFirstRun = WTFMove(m_firstRun);
116 m_firstRun = originalFirstRun->takeNext();
117 m_lastRun->setNext(WTFMove(originalFirstRun));
118 } else {
119 std::unique_ptr<Run> target = previous->takeNext();
120 previous->setNext(current->takeNext());
121 m_lastRun->setNext(WTFMove(target));
122 }
123}
124
125template <class Run>
126inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
127{
128 ASSERT(m_firstRun);
129 ASSERT(m_lastRun);
130 ASSERT(run != m_firstRun.get());
131
132 Run* previous = m_firstRun.get();
133 Run* current = previous->next();
134 while (current != run) {
135 previous = current;
136 current = previous->next();
137 }
138
139 std::unique_ptr<Run> target = previous->takeNext();
140 previous->setNext(run->takeNext());
141 if (run == m_lastRun)
142 m_lastRun = previous;
143
144 target->setNext(WTFMove(m_firstRun));
145 m_firstRun = WTFMove(target);
146}
147
148template <class Run>
149void BidiRunList<Run>::replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns)
150{
151 ASSERT(newRuns.runCount());
152 ASSERT(m_firstRun);
153 ASSERT(toReplace);
154
155 m_runCount += newRuns.runCount() - 1; // We are adding the new runs and removing toReplace.
156
157 // Fix up any pointers which may end up stale.
158 if (m_lastRun == toReplace)
159 m_lastRun = newRuns.lastRun();
160 if (m_logicallyLastRun == toReplace)
161 m_logicallyLastRun = newRuns.logicallyLastRun();
162
163 if (m_firstRun.get() == toReplace) {
164 newRuns.m_lastRun->setNext(m_firstRun->takeNext());
165 m_firstRun = WTFMove(newRuns.m_firstRun);
166 } else {
167 // Find the run just before "toReplace" in the list of runs.
168 Run* previousRun = m_firstRun.get();
169 while (previousRun->next() != toReplace)
170 previousRun = previousRun->next();
171 ASSERT(previousRun);
172
173 std::unique_ptr<Run> target = previousRun->takeNext();
174 previousRun->setNext(WTFMove(newRuns.m_firstRun));
175 newRuns.m_lastRun->setNext(target->takeNext());
176 }
177
178 newRuns.clear();
179}
180
181template <class Run>
182void BidiRunList<Run>::clear()
183{
184 m_firstRun = nullptr;
185 m_lastRun = nullptr;
186 m_logicallyLastRun = nullptr;
187 m_runCount = 0;
188}
189
190template <class Run>
191void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
192{
193 if (start >= end)
194 return;
195
196 ASSERT_WITH_SECURITY_IMPLICATION(end < m_runCount);
197
198 // Get the item before the start of the runs to reverse and put it in
199 // |beforeStart|. |curr| should point to the first run to reverse.
200 Run* curr = m_firstRun.get();
201 Run* beforeStart = nullptr;
202 unsigned i = 0;
203 for (; i < start; ++i) {
204 beforeStart = curr;
205 curr = curr->next();
206 }
207 Run* startRun = curr;
208
209 for (; i < end; ++i)
210 curr = curr->next();
211
212 if (!curr->next())
213 m_lastRun = startRun;
214
215 // Standard "sliding window" of 3 pointers
216 std::unique_ptr<Run> previous = curr->takeNext();
217 std::unique_ptr<Run> current = beforeStart ? beforeStart->takeNext() : WTFMove(m_firstRun);
218 while (current) {
219 std::unique_ptr<Run> next = current->takeNext();
220 current->setNext(WTFMove(previous));
221 previous = WTFMove(current);
222 current = WTFMove(next);
223 }
224
225 if (beforeStart)
226 beforeStart->setNext(WTFMove(previous));
227 else
228 m_firstRun = WTFMove(previous);
229}
230
231} // namespace WebCore
232
233#endif // BidiRunList
234