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/Noncopyable.h"
     27 
     28 namespace WebCore {
     29 
     30 template <class Run>
     31 class BidiRunList {
     32     WTF_MAKE_NONCOPYABLE(BidiRunList);
     33 public:
     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 
     64 private:
     65     void clearWithoutDestroyingRuns();
     66 
     67     Run* m_firstRun;
     68     Run* m_lastRun;
     69     Run* m_logicallyLastRun;
     70     unsigned m_runCount;
     71 };
     72 
     73 template <class Run>
     74 inline 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 
     84 template <class Run>
     85 inline 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 
     97 template <class Run>
     98 inline 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 
    121 template <class Run>
    122 inline 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 
    143 template <class Run>
    144 void 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 
    174 template <class Run>
    175 void BidiRunList<Run>::clearWithoutDestroyingRuns()
    176 {
    177     m_firstRun = 0;
    178     m_lastRun = 0;
    179     m_logicallyLastRun = 0;
    180     m_runCount = 0;
    181 }
    182 
    183 template <class Run>
    184 void 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     m_firstRun = 0;
    197     m_lastRun = 0;
    198     m_runCount = 0;
    199 }
    200 
    201 template <class Run>
    202 void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
    203 {
    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 WebCore
    252 
    253 #endif // BidiRunList
    254