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 toReplace->destroy(); 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 curr->destroy(); 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(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