Home | History | Annotate | Download | only in text 
      1 /*
      2  * Copyright (C) 2000 Lars Knoll (knoll (at) 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 
     29 namespace WebCore {
     30 
     31 template <class Run>
     32 class BidiRunList {
     33     WTF_MAKE_NONCOPYABLE(BidiRunList);
     34 public:
     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 
     65 private:
     66     void clearWithoutDestroyingRuns();
     67 
     68     Run* m_firstRun;
     69     Run* m_lastRun;
     70     Run* m_logicallyLastRun;
     71     unsigned m_runCount;
     72 };
     73 
     74 template <class Run>
     75 inline 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 
     85 template <class Run>
     86 inline 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 
     98 template <class Run>
     99 inline 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 
    122 template <class Run>
    123 inline 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 
    144 template <class Run>
    145 void 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 
    175 template <class Run>
    176 void BidiRunList<Run>::clearWithoutDestroyingRuns()
    177 {
    178     m_firstRun = 0;
    179     m_lastRun = 0;
    180     m_logicallyLastRun = 0;
    181     m_runCount = 0;
    182 }
    183 
    184 template <class Run>
    185 void 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     m_firstRun = 0;
    198     m_lastRun = 0;
    199     m_runCount = 0;
    200 }
    201 
    202 template <class Run>
    203 void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
    204 {
    205     ASSERT(m_runCount);
    206     if (start >= end)
    207         return;
    208 
    209     ASSERT(end < m_runCount);
    210 
    211     // Get the item before the start of the runs to reverse and put it in
    212     // |beforeStart|. |curr| should point to the first run to reverse.
    213     Run* curr = m_firstRun;
    214     Run* beforeStart = 0;
    215     unsigned i = 0;
    216     while (i < start) {
    217         i++;
    218         beforeStart = curr;
    219         curr = curr->next();
    220     }
    221 
    222     Run* startRun = curr;
    223     while (i < end) {
    224         i++;
    225         curr = curr->next();
    226     }
    227     Run* endRun = curr;
    228     Run* afterEnd = curr->next();
    229 
    230     i = start;
    231     curr = startRun;
    232     Run* newNext = afterEnd;
    233     while (i <= end) {
    234         // Do the reversal.
    235         Run* next = curr->next();
    236         curr->m_next = newNext;
    237         newNext = curr;
    238         curr = next;
    239         i++;
    240     }
    241 
    242     // Now hook up beforeStart and afterEnd to the startRun and endRun.
    243     if (beforeStart)
    244         beforeStart->m_next = endRun;
    245     else
    246         m_firstRun = endRun;
    247 
    248     startRun->m_next = afterEnd;
    249     if (!afterEnd)
    250         m_lastRun = startRun;
    251 }
    252 
    253 } // namespace WebCore
    254 
    255 #endif // BidiRunList
    256