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 private:
     63     Run* m_firstRun;
     64     Run* m_lastRun;
     65     Run* m_logicallyLastRun;
     66     unsigned m_runCount;
     67 };
     68 
     69 template <class Run>
     70 inline void BidiRunList<Run>::addRun(Run* run)
     71 {
     72     if (!m_firstRun)
     73         m_firstRun = run;
     74     else
     75         m_lastRun->m_next = run;
     76     m_lastRun = run;
     77     m_runCount++;
     78 }
     79 
     80 template <class Run>
     81 inline void BidiRunList<Run>::prependRun(Run* run)
     82 {
     83     ASSERT(!run->m_next);
     84 
     85     if (!m_lastRun)
     86         m_lastRun = run;
     87     else
     88         run->m_next = m_firstRun;
     89     m_firstRun = run;
     90     m_runCount++;
     91 }
     92 
     93 template <class Run>
     94 inline void BidiRunList<Run>::moveRunToEnd(Run* run)
     95 {
     96     ASSERT(m_firstRun);
     97     ASSERT(m_lastRun);
     98     ASSERT(run->m_next);
     99 
    100     Run* current = 0;
    101     Run* next = m_firstRun;
    102     while (next != run) {
    103         current = next;
    104         next = current->next();
    105     }
    106 
    107     if (!current)
    108         m_firstRun = run->next();
    109     else
    110         current->m_next = run->m_next;
    111 
    112     run->m_next = 0;
    113     m_lastRun->m_next = run;
    114     m_lastRun = run;
    115 }
    116 
    117 template <class Run>
    118 inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
    119 {
    120     ASSERT(m_firstRun);
    121     ASSERT(m_lastRun);
    122     ASSERT(run != m_firstRun);
    123 
    124     Run* current = m_firstRun;
    125     Run* next = current->next();
    126     while (next != run) {
    127         current = next;
    128         next = current->next();
    129     }
    130 
    131     current->m_next = run->m_next;
    132     if (run == m_lastRun)
    133         m_lastRun = current;
    134 
    135     run->m_next = m_firstRun;
    136     m_firstRun = run;
    137 }
    138 
    139 template <class Run>
    140 void BidiRunList<Run>::deleteRuns()
    141 {
    142     if (!m_firstRun)
    143         return;
    144 
    145     Run* curr = m_firstRun;
    146     while (curr) {
    147         Run* s = curr->next();
    148         curr->destroy();
    149         curr = s;
    150     }
    151 
    152     m_firstRun = 0;
    153     m_lastRun = 0;
    154     m_runCount = 0;
    155 }
    156 
    157 template <class Run>
    158 void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
    159 {
    160     if (start >= end)
    161         return;
    162 
    163     ASSERT(end < m_runCount);
    164 
    165     // Get the item before the start of the runs to reverse and put it in
    166     // |beforeStart|. |curr| should point to the first run to reverse.
    167     Run* curr = m_firstRun;
    168     Run* beforeStart = 0;
    169     unsigned i = 0;
    170     while (i < start) {
    171         i++;
    172         beforeStart = curr;
    173         curr = curr->next();
    174     }
    175 
    176     Run* startRun = curr;
    177     while (i < end) {
    178         i++;
    179         curr = curr->next();
    180     }
    181     Run* endRun = curr;
    182     Run* afterEnd = curr->next();
    183 
    184     i = start;
    185     curr = startRun;
    186     Run* newNext = afterEnd;
    187     while (i <= end) {
    188         // Do the reversal.
    189         Run* next = curr->next();
    190         curr->m_next = newNext;
    191         newNext = curr;
    192         curr = next;
    193         i++;
    194     }
    195 
    196     // Now hook up beforeStart and afterEnd to the startRun and endRun.
    197     if (beforeStart)
    198         beforeStart->m_next = endRun;
    199     else
    200         m_firstRun = endRun;
    201 
    202     startRun->m_next = afterEnd;
    203     if (!afterEnd)
    204         m_lastRun = startRun;
    205 }
    206 
    207 } // namespace WebCore
    208 
    209 #endif // BidiRunList
    210