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_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
45    Run* firstRun() const { return m_firstRun; }
46    Run* lastRun() const { return m_lastRun; }
47    Run* logicallyLastRun() const { return m_logicallyLastRun; }
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
60    void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
61
62    void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns);
63
64private:
65    void clearWithoutDestroyingRuns();
66
67    Run* m_firstRun;
68    Run* m_lastRun;
69    Run* m_logicallyLastRun;
70    unsigned m_runCount;
71};
72
73template <class Run>
74inline void BidiRunList<Run>::addRun(Run* run)
75{
76    if (!m_firstRun)
77        m_firstRun = run;
78    else
79        m_lastRun->m_next = run;
80    m_lastRun = run;
81    m_runCount++;
82}
83
84template <class Run>
85inline void BidiRunList<Run>::prependRun(Run* run)
86{
87    ASSERT(!run->m_next);
88
89    if (!m_lastRun)
90        m_lastRun = run;
91    else
92        run->m_next = m_firstRun;
93    m_firstRun = run;
94    m_runCount++;
95}
96
97template <class Run>
98inline void BidiRunList<Run>::moveRunToEnd(Run* run)
99{
100    ASSERT(m_firstRun);
101    ASSERT(m_lastRun);
102    ASSERT(run->m_next);
103
104    Run* current = 0;
105    Run* next = m_firstRun;
106    while (next != run) {
107        current = next;
108        next = current->next();
109    }
110
111    if (!current)
112        m_firstRun = run->next();
113    else
114        current->m_next = run->m_next;
115
116    run->m_next = 0;
117    m_lastRun->m_next = run;
118    m_lastRun = run;
119}
120
121template <class Run>
122inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
123{
124    ASSERT(m_firstRun);
125    ASSERT(m_lastRun);
126    ASSERT(run != m_firstRun);
127
128    Run* current = m_firstRun;
129    Run* next = current->next();
130    while (next != run) {
131        current = next;
132        next = current->next();
133    }
134
135    current->m_next = run->m_next;
136    if (run == m_lastRun)
137        m_lastRun = current;
138
139    run->m_next = m_firstRun;
140    m_firstRun = run;
141}
142
143template <class Run>
144void BidiRunList<Run>::replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns)
145{
146    ASSERT(newRuns.runCount());
147    ASSERT(m_firstRun);
148    ASSERT(toReplace);
149
150    if (m_firstRun == toReplace)
151        m_firstRun = newRuns.firstRun();
152    else {
153        // Find the run just before "toReplace" in the list of runs.
154        Run* previousRun = m_firstRun;
155        while (previousRun->next() != toReplace)
156            previousRun = previousRun->next();
157        ASSERT(previousRun);
158        previousRun->setNext(newRuns.firstRun());
159    }
160
161    newRuns.lastRun()->setNext(toReplace->next());
162
163    // Fix up any of other pointers which may now be stale.
164    if (m_lastRun == toReplace)
165        m_lastRun = newRuns.lastRun();
166    if (m_logicallyLastRun == toReplace)
167        m_logicallyLastRun = newRuns.logicallyLastRun();
168    m_runCount += newRuns.runCount() - 1; // We added the new runs and removed toReplace.
169
170    delete toReplace;
171    newRuns.clearWithoutDestroyingRuns();
172}
173
174template <class Run>
175void BidiRunList<Run>::clearWithoutDestroyingRuns()
176{
177    m_firstRun = 0;
178    m_lastRun = 0;
179    m_logicallyLastRun = 0;
180    m_runCount = 0;
181}
182
183template <class Run>
184void BidiRunList<Run>::deleteRuns()
185{
186    if (!m_firstRun)
187        return;
188
189    Run* curr = m_firstRun;
190    while (curr) {
191        Run* s = curr->next();
192        delete curr;
193        curr = s;
194    }
195
196    clearWithoutDestroyingRuns();
197}
198
199template <class Run>
200void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
201{
202    if (start >= end)
203        return;
204
205    ASSERT_WITH_SECURITY_IMPLICATION(end < m_runCount);
206
207    // Get the item before the start of the runs to reverse and put it in
208    // |beforeStart|. |curr| should point to the first run to reverse.
209    Run* curr = m_firstRun;
210    Run* beforeStart = 0;
211    unsigned i = 0;
212    while (i < start) {
213        i++;
214        beforeStart = curr;
215        curr = curr->next();
216    }
217
218    Run* startRun = curr;
219    while (i < end) {
220        i++;
221        curr = curr->next();
222    }
223    Run* endRun = curr;
224    Run* afterEnd = curr->next();
225
226    i = start;
227    curr = startRun;
228    Run* newNext = afterEnd;
229    while (i <= end) {
230        // Do the reversal.
231        Run* next = curr->next();
232        curr->m_next = newNext;
233        newNext = curr;
234        curr = next;
235        i++;
236    }
237
238    // Now hook up beforeStart and afterEnd to the startRun and endRun.
239    if (beforeStart)
240        beforeStart->m_next = endRun;
241    else
242        m_firstRun = endRun;
243
244    startRun->m_next = afterEnd;
245    if (!afterEnd)
246        m_lastRun = startRun;
247}
248
249} // namespace WebCore
250
251#endif // BidiRunList
252