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 29namespace blink { 30 31template <class Run> 32class BidiRunList { 33 WTF_MAKE_NONCOPYABLE(BidiRunList); 34public: 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 46 Run* firstRun() const { return m_firstRun; } 47 Run* lastRun() const { return m_lastRun; } 48 Run* logicallyLastRun() const { return m_logicallyLastRun; } 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 61 void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; } 62 63 void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns); 64 65private: 66 void clearWithoutDestroyingRuns(); 67 68 Run* m_firstRun; 69 Run* m_lastRun; 70 Run* m_logicallyLastRun; 71 unsigned m_runCount; 72}; 73 74template <class Run> 75inline 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 85template <class Run> 86inline 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 98template <class Run> 99inline 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 122template <class Run> 123inline 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 144template <class Run> 145void 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 175template <class Run> 176void BidiRunList<Run>::clearWithoutDestroyingRuns() 177{ 178 m_firstRun = 0; 179 m_lastRun = 0; 180 m_logicallyLastRun = 0; 181 m_runCount = 0; 182} 183 184template <class Run> 185void 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 200template <class Run> 201void 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